performance - vector::reserve() 似乎没有分配空间

Question

所附代码包含对 std::vector::assign() 的三个调用。在第一次调用之前，调用 std::vector::reserve() 来分配适当的内存量，然后填充向量。对 allocate() 的第二次调用在填充第二个向量之前不会调用 Reserve()，因此我预计在对 allocate() 的调用期间至少会发生一次分配。第三次调用 allocate() 用于用新数据重新填充第一个向量。代码中的第四个 block 使用 new 分配一个 int 数组并填充它。

我希望第一、第三和第四 block 的性能相同，而第二 block 由于所需的分配而需要额外的时间。我实际发现，第一个和第二个 block 花费相同的时间，而第三个和第四个 block 运行速度明显更快(~30%)。在我看来，对 Reserve() 的调用实际上并没有分配所需的空间，而是将分配推迟到对 allocate() 的调用为止。

我在两个平台上对此进行了测试:使用 Visual C++ 2010 编译器编译的 Windows Vista 和使用 gcc 4.3.2 编译器编译的 SUSE linux。我尝试了不同级别的优化(包括不优化)，并继续看到相同的行为。有什么想法为什么 Reserve() 没有达到我的预期吗？如果我看到的是正确的行为，那么 Reserve() 的意义何在？

谢谢，乔什

#include <vector>
#include <time.h>
#include <stdio.h>
#include <iostream>

int main()
{
  int     len=1E8, nloops=100;
  clock_t start, stop;
  double  wr=0.0, wor=0.0, wc=0.0, pb=0.0;

  printf("Number of values tested = %d\n", len);
  printf("Number of loops = %d\n", nloops);

  std::vector<int> vec1a, vec1b;
  for(int i=0; i<len; i++) vec1a.push_back(i);
  for(int i=len; i>0; i--) vec1b.push_back(i);

  for(int i=0; i<nloops; i++)
  {
    std::vector<int>  vec2, vec3;
    int              *vec4;

//First block
    vec2.reserve(len);
    start = clock();
    vec2.assign(vec1a.begin(), vec1a.end());
    stop = clock();
    wr += ((double)(stop-start))/((double)(CLOCKS_PER_SEC));

//Second block
    start = clock();
    vec3.assign(vec1a.begin(), vec1a.end());
    stop = clock();
    wor += ((double)(stop-start))/((double)(CLOCKS_PER_SEC));

//Third block
    vec2.clear();
    start = clock();
    vec2.assign(vec1b.begin(), vec1b.end());
    stop = clock();
    wc += ((double)(stop-start))/((double)(CLOCKS_PER_SEC));

//Fourth block
    start = clock();
    vec4 = new int[len];
    for(int j=0; j<len; j++) vec4[j] = vec1a[j];
    stop = clock();
    pb += ((double)(stop-start))/((double)(CLOCKS_PER_SEC));
    delete []vec4;
  }

  printf("With reserve()    = %10.4lE\n", wr);
  printf("Without reserve() = %10.4lE\n", wor);
  printf("With clear()      = %10.4lE\n", wc);
  printf("newed int array   = %10.4lE\n", pb);

  return 0;
}

Answer 1

考虑到向量的源全部在头文件中，您可以搜索 .assign 的作用。在分配内部，它会一次性分配所需数量的项目。该模板足够聪明，知道当您执行 vec2.assign(vec1a.begin(), vec1a.end())

时它需要 1E8

如果你真的想测试它，请迭代每个项目并使用push_back而不是assign()

添加

为了澄清，在 .assign() 的调用堆栈中，它计算新容量并调用 _Grow_to (MSVC++10)。实际上，.assign() 进行了保留。