填充未知大小的std :: vector的最快方法

Question

我有一长串数据(n个实体).此数组中的每个对象都有一些值(比方说,对象的m值).我有一个周期:

myType* A; 

// reading the array of objects   
std::vector<anotherType> targetArray;
int i, j, k = 0;
for (i = 0; i < n; i++)
     for (j = 0; j < m; j++)
     { 
         if (check((A[i].fields[j]))
         {
             // creating and adding the object to targetArray
             targetArray[k] = someGenerator(A[i].fields[j]);
             k++;
         }
     } 

在某些情况下,我有n*m个有效对象,有些(n*m)/ 10或更少.
问题是如何为内存分配内存targetArray？

1. targetArray.reserve(n*m);
// Do work
targetArray.shrink_to_fit();

2. 计算元素而不生成对象,然后根据需要分配尽可能多的内存,再循环一次.

3. 在每次创建新对象的迭代中调整数组大小.

我在每个方法中都看到了一个巨大的战术错误.是另一种方式吗？

Answer 1

你在这做什么叫做过早优化.默认情况下,当std::vector内存不足以存储新对象时,将以指数方式增加其内存占用量.例如,第一个push_back将分配2个元素.第三个push_back将加倍大小等.只需坚持push_back并让你的代码工作.

只有当上述方法证明自己是设计中的瓶颈时,才应该开始考虑内存分配优化.如果发生这种情况,我认为最好的办法是为许多有效对象提供一个很好的近似值,然后调用reserve()一个向量.像你的第一个方法.只需确保缩小以适应实现是正确的,因为矢量不喜欢缩小.你必须使用swap.

在每一步调整数组大小都没有用std::vector,除非你努力,否则不会真正做到这一点.

在对象列表中执行额外的循环可能会有所帮助,但也可能会因为您可能轻易浪费CPU周期,膨胀CPU缓存等而受到伤害.如果有疑问 - 请对其进行分析.