3

10個の要素を持つベクトルVがあるとします。を使用して最初の要素（インデックス0）を消去した場合、v.erase(v.begin())STLベクトルはこれをどのように処理しますか？

別の新しいベクトルを作成し、古いベクトルから新しいベクトルに要素をコピーして、古いベクトルの割り当てを解除しますか？または、インデックス1から始まる各要素をコピーし、その要素をインデックス1にコピーしますか？

一度にサイズ100,000のベクトルが必要で、後でそれほど多くのスペースを使用しない場合、たとえばサイズ10のベクトルのみが必要な場合、サイズは自動的に縮小されますか？（ 私はそうは思わない）

オンラインで調べたところ、STLライブラリの使用方法はAPIとチュートリアルしかありません。STLライブラリの実装または複雑さについてのアイデアを得ることができる良い参考資料はありますか？

4

5 に答える 5

5

実際には、の実装はvectorテンプレートであるため表示されます。詳細については、以下を調べることができます。

iterator erase(const_iterator _Where)
    {   // erase element at where
    if (_Where._Mycont != this
        || _Where._Myptr < _Myfirst || _Mylast <= _Where._Myptr)
        _DEBUG_ERROR("vector erase iterator outside range");
    _STDEXT unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);
    _Destroy(_Mylast - 1, _Mylast);
    _Orphan_range(_Where._Myptr, _Mylast);
    --_Mylast;
    return (iterator(_Where._Myptr, this));
    }

基本的に、ライン

unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);

あなたが思ったことを正確に実行します-次の要素をコピーします（または、bames53が指摘したようにC ++ 11でそれらを移動します）。

2番目の質問に答えるために、いいえ、容量はそれ自体で減少することはできません。

のアルゴリズムの複雑さはstdhttp://www.cplusplus.com/reference/stl/にあり、前述のように実装が表示されます。

于 2012-06-13T22:19:44.403 に答える
1

インデックス1から始まる各要素をコピーし、その要素をインデックス1にコピーしますか？

はい（C ++ 11以降は実際に移動しますが）。

自動的にサイズが小さくなりますか？

いいえ、サイズを小さくすると、通常、既存の要素へのイテレータが無効になります。これは、特定の関数呼び出しでのみ許可されます。

オンラインで調べたところ、STLライブラリの使用方法はAPIとチュートリアルしかありません。STLライブラリの実装または複雑さについてのアイデアを得ることができる良い参考資料はありますか？

実装に関して何が許可され、何が許可されていないかを正確に示すC++仕様を読むことができます。実際の実装を見に行くこともできます。

于 2012-06-13T22:22:03.767 に答える
1

Vectorは要素を先頭にコピー（C ++ 11で移動）します。そのため、コレクションの先頭から挿入および消去する場合は、dequeを使用する必要があります。ベクトルの内部バッファのサイズを本当に変更したい場合は、次のように実行できます。

vector<Type>(v).swap(v);

これにより、正しいサイズの一時ベクトルが作成され、その内部バッファーが古いものと交換され、一時ベクトルがスコープ外になり、大きなバッファーの割り当てが解除されます。

他の人が指摘したようにvector::shrink_to_fit()、C++11で使用できます。

于 2012-06-13T22:28:07.053 に答える
0

これは、C ++に対する私の（多くの）反対意見の1つです。誰もが「標準ライブラリを使用する」と言います...しかし、STLソース（さまざまな場所から無料で入手できます。この場合はヘッダーファイル自体を含みます！）がある場合でも、基本的に理解できない悪夢です。掘り下げて理解しようとします。

（Cのみの）Linuxカーネルは、対照的に単純さと明快さのパラゴンです。

しかし、私たちは逸脱します:)

これがあなたの質問に対する10,000フィートの答えです：

http://www.cplusplus.com/reference/stl/vector/

ベクトルコンテナは動的配列として実装されます。通常の配列と同様に、ベクターコンテナの要素は連続した保存場所に保存されます。つまり、イテレータを使用するだけでなく、要素への通常のポインタのオフセットを使用して要素にアクセスできます。

ただし、通常の配列とは異なり、ベクトルのストレージは自動的に処理されるため、必要に応じて拡張および縮小できます。

ベクトルは次の点で優れています。

  • 位置インデックス（一定時間）による個々の要素へのアクセス。
  • 要素を任意の順序で反復します（線形時間）。
  • その終わりから要素を追加および削除します（一定の償却時間）。

アレイと比較すると、これらのタスクでほぼ同じパフォーマンスを提供し、さらに簡単にサイズを変更することができます。ただし、容量が自動的に処理される場合、通常はアレイよりも多くのメモリを消費します（これは、将来の拡張に備えて追加のストレージスペースに対応するためです）。

他の基本標準シーケンスコンテナ（両端キューとリスト）と比較すると、ベクトルは一般に、要素にアクセスしたり、シーケンスの最後から要素を追加または削除したりするのに最も効率的です。末尾以外の位置で要素を挿入または削除する操作の場合、両端キューやリストよりもパフォーマンスが低く、リストよりも反復子と参照の一貫性が低くなります。

..。

再割り当ては、一般に、新しい場所にコピーされるベクトルによって使用されるストレージスペース全体を伴うため、パフォーマンスの点でコストのかかる操作になる可能性があります。メンバー関数vector::reservedを使用して、ベクトルの容量を事前に示すことができます。これは、多くの拡張が計画されている場合に、ストレージスペースを最適化し、再割り当ての数を減らすのに役立ちます。

..。

于 2012-06-13T22:21:51.170 に答える
-1

サイズ10のベクトルだけが必要ですが、自動的にサイズが小さくなりますか？

いいえ、自動的に縮小しません。
従来、ベクトルを新しい空のベクトルと交換します。stlベクトルの容量を減らします。

ただし、C++x11にはstd::vector :: shrink_to_fit（）が含まれており、これを直接実行します。

于 2012-06-13T22:23:46.103 に答える