4

私の知る限り、C++ 標準では、vector::resize で増加が必要な場合にベクトル容量をどのように増加させるかを正確に指定していません。しかし、「典型的な」実装はありますか?

具体的には、ベクターの大きさがどのくらい必要かわかりません。さらに、要素はランダムな順序で表示されます。だから私はこれを持っている各要素のために：

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

要素がインデックスの昇順で来る場合、ベクトル容量はサイズ変更の呼び出しごとに 1 ずつ増加しますか (一般的な実装で)? ないことを願っています...

4

2 に答える 2

4

標準は、 への繰り返し呼び出しの漸近性について保証しませんresize()。コンテナーが必要な目標サイズまで正確に容量を拡張することは十分に可能です。実際、これは、 の標準的な使用例(たとえば、1 回だけ使用される場合) の大部分において、おそらく望ましい動作 (つまり、無駄が最も少ない) です。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は、容量を増やす必要があるたびに容量が 2 倍になります。これは、一連の の償却後の複雑さに関係していpush_backます。容量を毎回 1 ずつ増やすと、N追加の複雑さは になりますがO(N^2)、push_back容量を毎回 2 倍にすると、同じ一連の追加の複雑さは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 に答える