当向量的维度必须递增时,避免重新分配向量

Question

我有一个

vector< pair<vector<double> , int>> samples;

该向量将包含许多元素.为了效率rason我以这种方式初始化它:

vector< pair<vector<double> , int>> samples(1000000);

我从另一个容器中预先知道了(不是编译时)的大小.问题是我必须减少1个元素的向量维度.实际上,这种情况不是问题,因为调整尺寸小于初始没有重新分配.我可以这样做

samples.resize(999999);

问题是在某些情况下,而不是减少1个元素的维度,我必须增加元素的维度.如果我做

samples.resize(1000001);

存在重新分配的风险,我希望避免效率rasons.我问是否可能解决我的问题是这样的:

vector< pair<vector<double> , int> samples;
samples.reserve(1000001);
samples.resize(1000000);
.
. Elaboration that fill samples 
.
samples.resize(1000001); //here I don't want reallocation

或者如果有更好的解决方案？提前致谢!

(我正在使用C++ 11编译器)

Answer 1

刚写了一个示例程序来演示,resize如果向量的容量足够,那就不会重新分配空间:

#include <iostream>
#include <vector>
#include <utility>
#include <cassert>

using namespace std;

int main() 
{
  vector<pair<vector<double>, int>> samples;
  samples.reserve(10001);

  auto data = samples.data();

  assert(10001==samples.capacity());

  samples.resize(10000);
  assert(10001 == samples.capacity());
  assert(data == samples.data());

  samples.resize(10001); //here I don't want reallocation
  assert(10001==samples.capacity());
  assert(data == samples.data());  
}

此演示基于以下假设:std :: vector保证连续内存,如果data指针没有更改,则不会发生realloc.这一点也很明显,capacity()结果是10001在每次通话结束后仍然存在resize().

向量的cppreference:

矢量的存储自动处理,根据需要进行扩展和收缩.向量通常占用比静态数组更多的空间,因为分配了更多的内存来处理未来的增长.这样,每次插入元素时,向量都不需要重新分配,但仅在附加内存耗尽时才需要重新分配.可以使用capacity()函数查询分配的内存总量.

cppreference上reserve:

正确使用reserve()可以防止不必要的重新分配,但是不恰当地使用reserve()(例如,在每次push_back()调用之前调用它)实际上可能会增加重新分配的数量(通过使容量线性增长而不是指数增长)和导致计算复杂性增加和性能下降.

cppreference也符合resize:

复杂

线性在当前大小和计数之间的差异.如果容量小于计数,则可能由于重新分配而导致额外的复杂性