c++ - std::vector 容量智能实现

Question

我知道 std::vector 容量行为是特定于实现的，是否有任何智能实现可以做到这一点:

vector<int> v;
for(int i = 0; i < 10000 ; ++i){
    v.push_back(i);
}

在初始化时，它可以预测“vector”的容量，在本例中它将初始化容量为10000

我问这个是因为我一直认为 gcc 会做这种预测，但我找不到任何关于这个的东西......我想我在某个地方看到过这个，那么有没有实现这个的？

Answer 1

什么都预测不到。然而:

• 可以使用reserve 来预先分配所需的最大元素数量。 push_back 将永远不需要重新分配。

• push_back 使用分配不止一个 mor 元素的 vector 增长策略。 IIRC 增长因子为 2，这意味着一系列 push_back 中的重新分配数量趋于对数。因此，对 push_back 的 N 次调用的成本收敛于 log2(N)。