vector reserve c++

Question

我有一个非常大的多维向量，大小随时变化。当我只知道一个良好的大小估计时，使用vector.reserve()函数是否有意义？

基本上，我有一个向量：

A[256*256][x][y]

其中x在程序的每次迭代中从0到50，然后再返回0。 y值可以每次不同，这意味着对于每个[256 * 256] [y]元素，向量y的大小可以不同，但仍小于256。

因此，为了澄清我的问题，这就是我所拥有的：

vector<vector<vector<int>>> A;
for(int i =0;i<256*256;i++){
  A.push_back(vector<vector<int>>());
  A[i].push_back(vector<int>());
  A[i][0].push_back(SOME_VALUE);
}

向向量中添加元素...

A.clear();

接着我从顶部再次执行相同的操作。

何时以及如何为向量保留空间。 如果我理解正确，如果我在更改大小时使用reserve，我将节省很多时间？

预留我的向量可以达到最大大小的正面/负面是什么，这将是[256 * 256] [50] [256]在某些情况下。

顺便说一句。 我知道不同的矩阵模板和Boost，但已决定在此问题上使用向量...

编辑： 我还想知道如何在多维数组中使用reserve函数。 如果我只在两个维度上保留向量，那么如果我超过第三个维度的容量，它会复制整个向量吗？

- user119653

---

256256502564 == 3.5 GB。这真的正确吗？ - Will

我很抱歉，确实是这样！但这是最大尺寸...它平均可能会达到25625650*100左右；从技术上讲，最大值永远不会被达到... - user119653

Answer 1

为了帮助讨论，您可以考虑以下typedefs:

typedef std::vector<int> int_t;   // internal vector
typedef std::vector<int_t> mid_t; // intermediate
typedef std::vector<mid_t> ext_t; // external

增加（向量容量增加）int_t的成本只会影响到这个特定向量的内容，并不会影响到其他元素。增加mid_t的成本需要复制存储在该向量中的所有元素，也就是它需要所有的int_t向量，这要比前者更加昂贵。增加ext_t的成本非常巨大：需要复制容器中已经存储的所有元素。

为了提高性能，更重要的是要得到正确的ext_t大小（似乎在您的问题中固定为256*256）。然后，要正确地获取中间的mid_t大小，以便昂贵的重新分配尽可能少。

你所说的内存量非常庞大，因此你可能想考虑一些非标准的方法来解决你的问题。首先想到的是添加一个额外的间接级别。如果你不是持有实际的向量，而是持有指向向量的智能指针，你就可以降低增加mid_t和ext_t向量的成本（如果ext_t大小是固定的，只需使用mid_t向量的向量）。现在，这将意味着使用你的数据结构的代码将更加复杂（或者最好添加一个包装器来处理间接引用）。每个int_t向量只会在内存中分配一次，并且永远不会在mid_t或ext_t重新分配中移动。重新分配mid_t的成本与分配的int_t向量数成比例，而不是实际插入的整数数目。

using std::tr1::shared_ptr; // or boost::shared_ptr
typedef std::vector<int> int_t;
typedef std::vector< shared_ptr<int_t> > mid_t;
typedef std::vector< shared_ptr<mid_t> > ext_t;

另一个需要考虑的问题是，std::vector::clear() 只会销毁容器内的对象并将大小设置为0，而不会释放向量中分配的内部空间。也就是说，调用 clear() 永远不会释放内存。实际上释放向量中分配的内存的模式如下：

typedef std::vector<...> myvector_type;
myvector_type myvector;
...
myvector.swap( myvector_type() ); // swap with a default constructed vector

- David Rodríguez - dribeas

---

@David - 你确定第一个片段中的 internal_t 和 intermediate_t 部分是正确的吗？ - Manuel

Answer 2

每当您将一个向量推入另一个向量时，请在被推入的向量构造函数中设置大小：

 A.push_back(vector<vector<int> >( somesize ));

- anon

---

">>"在模板中并不总是被正确处理。加入空格使其更具可移植性。只是小问题。 - Roman Shapovalov

Answer 3

您已经有一个可工作的实现，但担心性能问题。如果您的分析显示它是瓶颈，可以考虑使用裸的C风格整数数组，而不是向量的向量的向量。

请参见如何在C中使用动态多维数组的示例

您可以每次重复使用相同的分配，根据需要进行realloc，并最终将其保持在使用高潮处。

如果确实是向量成为了瓶颈，那么除了避免每个循环迭代上的大小调整操作之外，性能很可能会受到您对数组的访问模式的支配。尝试按顺序访问最高级别。

- Will

---

不要这样做。向量会为您处理重新分配。在C++程序中使用realloc()几乎肯定是错误的做法。 - anon

在这个特定的例子中，POD 的向量的向量的向量，malloc/realloc/free 怎么可能是不合适的？ - Will

至少，如果我使用向量，由于“第三”维中有不同的大小，我可以轻松访问大小... - user119653

Answer 4

如果您在构建向量时知道其大小，请将大小传递给构造函数并使用operator[]进行分配，而不是使用push_back。如果您对最终大小不确定，请猜测一下（可能增加一点），并使用reserve来预留足够的内存。

在某些情况下，预留我的向量可以达到最大大小，即[256 * 256] [50] [256]的正面/负面是什么？

负面影响：潜在的内存浪费。积极方面：更少的CPU时间，更少的堆碎片。这是内存/ CPU权衡，最佳选择取决于您的应用程序。如果您没有受到内存限制（在大多数消费者机器上有足够的RAM），请考虑提前保留。

要决定要保留多少内存，请查看平均内存消耗，而不是峰值（除非经常需要这样的尺寸，否则不建议保留256 * 256 * 50 * 256）

- Alexander Gessler