std::vector capacity智能实现

Question

我知道std::vector的容量行为是特定于实现的，有没有什么聪明的实现可以做到这一点：

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

在初始化时，它可以预测‘向量’的容量，在这个例子中，它将初始化容量到10000

我问这个是因为我一直认为gcc会做这种预测，但我找不到任何关于这方面的东西……我想我在什么地方见过这种情况，那么有没有什么实现可以做到这一点呢？

Answer 1

没有什么是可以预测的。但是：

• one可以使用reserve预先分配所需的最大数量的元素。然后，push_back将永远不需要reallocate.
• push_back使用vector的增长策略，即只分配一个以上的元素。IIRC增长因子是2，这意味着在一系列push_back中重新分配的次数趋于对数。因此，对log2(N).

的N个push_back调用的成本收敛

Answer 2

它为std::vector提供了不同的构造函数。其中一种可能是将缺省值和您想要的值的数量传递给向量。

来自std::vector的文档

// constructors used in the same order as described above:
std::vector<int> first;                                // empty vector of ints
std::vector<int> second (4,100);                       // four ints with value 100
std::vector<int> third (second.begin(),second.end());  // iterating through second
std::vector<int> fourth (third);                       // a copy of third

如果事先知道向量的最大大小，这将非常有用。