1

我正在存储和生成一些自然用维度 > 1 表示的数据。但是，我看到许多答案建议程序员使用具有自己的自定义索引的一维向量来表示多个维度。我的问题是：仅使用一维可以获得什么？

在我当前的项目中，性能是一个优先事项（我首先了解代码，然后是配置文件，但是这个项目正在从另一种语言导入到 C++ 中以提高速度）。我可以看到只有一个矢量对象可以减少开销，但它是否比频繁计算索引要多得多？我看到一个答案提到使用嵌套向量：

vector < vector<int> >

导致大量调用new. 我可以看出这是多么令人不安，这是真的吗？

4

1 回答 1

4

首先，astd::vector<std::vector<int>>可以有不同大小的内部向量。但是，我假设您正在专门讨论使用这种类型来模拟 2D 数组。假设您在创建向量时设置了向量的大小，您可能不需要担心动态分配的数量，因为这一切都是一次性发生的。

向量在内部分配其元素的数组。因此，外部向量分配了一个向量数组，而每个内部向量都分配了一个ints 数组。你可以这样想：

┌─────┐
│ vec │
└──╂──┘
   ┃
   ▼
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ vec │ vec │ vec │ vec │ vec │ vec │ vec │ vec │ vec │
└──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┴──╂──┘
   ┃     ┗━━━━━━━━━━┓
   ▼                ▼
┌─────┬─────┬┄   ┌─────┬─────┬┄
│ int │ int │    │ int │ int │
└─────┴─────┴┄   └─────┴─────┴┄

如您所见，ints 的数组彼此完全分开。它们可能位于完全不同的内存位置。这称为碎片。它们几乎肯定不会位于单个连续的内存块中。因此，跨 2D 矢量的不同“行”访问元素可能会导致缓存未命中。

但是，如果您分配 s 的单个向量int并进行自己的二维索引，则您的内存布局更像这样：

┌─────┐
│ vec │
└──╂──┘
   ┃
   ▼
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬┄
│ int │ int │ int │ int │ int │ int │ int │ int │ int │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴┄

s现在int存储在单个连续的内存块中。任何访问都可能具有相似的内存地址并导致缓存命中。这可能会给您带来性能提升。

于 2013-03-27T18:01:05.680 回答