是否更有效地预分配向量？ [英] Is it more efficient to preallocate a vector?

问题描述

在C ++ Primer第四版中，由Stanley B.Lippman，Josee Lajoie和Barbara E. Moo声明：

通常最好通过动态添加元素来使向量
增长，因为元素值是
。

和

读者习惯使用c或java可能会期望，因为vector
元素是连续存储的将最好按其预期大小预分配
向量。事实上情况恰恰相反...

和

尽管我们可以在向量中预先分配给定数量的元素，
通常更有效的方法是定义一个空向量，并向它添加
元素。

假设这是正确的（作者声名良好，一个是C ++本身的合着者），那么任何人都可以给我一个证明这个语句，并解释为什么？

解决方案

这取决于。

你不知道最终的大小是什么，然后让向量使用它的分配方案（通常每次加倍，或在那里的某处）分配。这样，您可以避免为每个元素重新分配：

  std :: vector< int& v; 
 
 //好：
 for（/ * populate v * /）//未知的迭代次数
 {
 v.push_back（i）; //可能的重新分配，但不经常
} 
 
 //坏：
 for（/ * populate v * /）//未知迭代次数
 {
 v.reserve（v.size（）+ 1）; //定义重新分配，每次
 v.push_back（i）; //（没有重新分配）
} 
  

但是如果你提前知道， t是重新分配，然后preallocate：

  std :: vector< int> v; 
 
 //好：
 v.reserve（10）; 
 for（/ * populate v * /）//只有10次迭代（例如）
 {
 v.push_back（i）; //没有重分配
} 
 
 //不好，但不是最好的：
 for（/ * populate v * /）//只有10次迭代b $ b {
 v.push_back（i）; //可能的重新分配，但不经常（但多于需要！）
} 
  

In C++ Primer fourth edition, by Stanley B.Lippman, Josee Lajoie and Barbara E. Moo it states:

Because vectors grow efficiently, it is usually best to let the vector grow by adding elements to it dynamically as the element values are known.

and

Readers accustomed to using c or java might expect that because vector elements are stored contiguously, it would be best to preallocate the vector at its expected size. In fact the contrary is the case...

and

Allthough we can preallocate a given number of elements in a vector, it is usually more efficient to define an empty vector and add elements to it.

Assuming this is correct (the authors are as reputable as they come, one is a co-author of C++ itself) then can anyone give me a case that proves this statement, and explain why?

解决方案

It depends.

If you don't know what the final size will be, then let the vector allocate using its allocation scheme (usually doubles each time, or somewhere around there). This way you avoid reallocating for every single element:

std::vector<int> v;

// good:
for (/* populate v */) // unknown number of iterations
{
    v.push_back(i); // possible reallocation, but not often
}

// bad:
for (/* populate v */) // unknown number of iterations
{
    v.reserve(v.size() + 1); // definite reallocation, every time
    v.push_back(i); // (no reallocation)
}

But if you know ahead of time you won't be reallocating, then preallocate:

std::vector<int> v;

// good:
v.reserve(10); 
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // no reallocations
}

// not bad, but not the best:
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // possible reallocation, but not often (but more than needed!)
}

这篇关于是否更有效地预分配向量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！