c++ - 填充未知大小的 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);<br/>
// Do work<br/>
targetArray.shrink_to_fit();

2. 在不生成对象的情况下对元素进行计数，然后根据需要分配尽可能多的内存，然后再循环一次。

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

我发现我的每一种方法都存在巨大的战术错误。有其他方法吗？

Answer 1

您在这里所做的称为过早优化。默认情况下，std::vector 将以指数方式增加其内存占用，因为它用完内存来存储新对象。例如，第一个 push_back 将分配 2 个元素。第三个 push_back 将使大小加倍等。只需坚持使用 push_back 并让您的代码正常工作。

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

在每一步都调整数组大小是不好的，除非你努力尝试，否则 std::vector 不会真正做到这一点。

通过对象列表进行额外的循环会有所帮助，但它也可能会造成伤害，因为您很容易浪费 CPU 周期、膨胀 CPU 缓存等。如果有疑问 - 分析它。