4

据我所知，当 vector::resize 需要增加时，C++ 标准并没有具体说明如何增加矢量容量。但是有一个“典型”的实现吗？

具体来说：我不知道我的向量需要多大。此外，元素以随机顺序出现。所以对于每个元素我都有这个：

if ( index >= vector.size() ) {
    vector.resize ( index + 1 );
}
vector.at ( index ) = element;

如果元素以递增的索引顺序出现，每次调用调整大小时向量容量是否会增加一（在典型实现中）？我希望不会...

4

2 回答 2

4

该标准不保证重复调用resize(). 容器将简单地将容量增加到精确所需的目标大小是完全可行的。事实上，这可能是大多数标准用例（例如只使用一次）的理想行为（即最不浪费的行为）。resize()

如果您担心，只需实现自己的几何增长：

if (index + 1 > v.size()
{
    if (v.capacity() < index + 1)
    {
        v.reserve(2 * (index + 1));   // I had 2 * capacity() here first, but
                                      // I think this version is better
    }
    v.resize(index + 1);
}
于 2011-12-22T13:07:48.543 回答
0

正如您所提到的，什么resize完全取决于您的实现（并且可能在同一实现的不同版本之间发生变化）。

在兼容的实现中，push_back每次必须增加容量都会导致容量翻倍，这与一系列push_back's 的摊销复杂性有关。如果每次将容量增加 1，则N添加的复杂度将是O(N^2)，而如果push_back每次将容量增加一倍，则同一系列添加的复杂度将只是O(N)- 一个大问题。

至于你的问题 - 如果你事先知道最大值index，只需预先分配。否则，我认为你最好std::map：

map<int, T> M;
for (...) {
  M[index] = element;
}

这将具有添加的复杂性O(N log N)，N但不会在没有相应element' 的索引上浪费内存。

于 2011-12-22T13:07:06.873 回答