動的メモリをstd :: vectorでどのように管理しますか？

Question

std :: vectorは要素数の変化をどのように管理するのですか？realloc（）関数を使用しているのか、それともリンクリストを使用していますか？

ありがとうございました。

Answer 1

2番目のテンプレートパラメータとして与えられたアロケータを使用します。これと同じように。そのような

... 
if(_size == _capacity) { // size is never greater than capacity 
    // reallocate 
    T * _begin1 = alloc.allocate(_capacity * 2, 0); 
    size_type _capacity1 = _capacity * 2; 

    // copy construct items (copy over from old location). 
    for(size_type i=0; i<_size; i++) 
     alloc.construct(_begin1 + i, *(_begin + i)); 
    alloc.construct(_begin1 + _size, t); 

    // destruct old ones. dtors are not allowed to throw here. 
    // if they do, behavior is undefined (17.4.3.6/2) 
    for(size_type i=0;i<_size; i++) 
     alloc.destroy(_begin + i); 
    alloc.deallocate(_begin, _capacity); 

    // set new stuff, after everything worked out nicely 
    _begin = _begin1; 
    _capacity = _capacity1; 
} else { // size less than capacity 
    // tell the allocator to allocate an object at the right 
    // memory place previously allocated 
    alloc.construct(_begin + _size, t); 
} 
_size++; // now, we have one more item in us 
... 

は何か：tをプッシュするオブジェクトで聞かせて、それが一backであると言います。アロケータはメモリの割り当てに注意します。それはメモリを割り振り、そのメモリにオブジェクトを構築するステップを保持するので、メモリを事前に割り当てることができますが、まだコンストラクタを呼び出すことはできません。再割り当て中に、ベクターはコピーコンストラクタによってスローされる例外に注意を払わなければならず、そのことはいくらか問題を複雑にする。上のコードは実際のコードではなく、おそらく多くのバグを含んでいる疑似コードスニペットです。サイズが容量を上回った場合、それはアロケータに新しいより大きなメモリブロックを割り当てるように要求します。そうでなければ、以前に割り当てられたスペースで構築します。

これの正確なセマンティクスは、アロケータによって異なります。それは、標準アロケータであれば、構築

new ((void*)(_start + n)) T(t); // known as "placement new" 

そして割り当てるallocateを行いますちょうど::operator newからメモリを取得します。 destroyはアロケータとベクトルの背後に抽象化されているすべてはそれを使用しています

(_start + n)->~T(); 

デストラクタを呼び出します。スタック・アロケータまたはプール・アロケータは、全く異なった動作をする可能性がありますreserve(N)への呼び出しの後

• 重要なvectorに関するいくつかの重要なポイントは、あなたが再割り当てを危険にさらすことなく、あなたのベクターに挿入までのNのアイテムを持つことができます。それまではsize() <= capacity()の長さであり、その要素に対する参照とイテレータは有効なままです。
• ベクターのストレージは連続しています。 & v [0]は、あなたのベクトルに現在ある多くの要素を含むバッファーとして扱うことができます。

Answer 2

std::vectorによって管理されるメモリは、連続的であることが保証されているため、&vec[0]を動的配列の先頭へのポインタとして扱うことができます。

これを考えると、実際にその割り当てをどのように管理するかは実装固有です。

Answer 3

ベクトルの厳密な規則の1つは、データが1つの連続したメモリブロックに格納されることです。

あなたは理論的にこれを行うことができます知っているその方法：

const Widget* pWidgetArrayBegin = &(vecWidget[0]); 

あなたは、パラメータとして配列をしたい関数に pWidgetArrayBeginを渡すことができます。

これ以外の例外は、std :: vector <bool>特殊化です。それは実際には全くブールではありませんが、それは別の話です。

std :: vectorはメモリを再割り当てし、リンクリストを使用しません。

これは、あなたがこのことで足に自分自身を撮影することができます意味：あなたが知っているすべてのために

Widget* pInteresting = &(vecWidget.back()); 
vecWidget.push_back(anotherWidget); 

を、一back呼び出しが無効、メモリの全く新しいブロックに、その内容をシフトするベクトルが発生することがありました、興味深い。。

Answer 4

std :: vectorは連続したメモリブロックにデータを格納します。

ベクトルを

と宣言しているとします。std :: vector intvect;

最初はx要素のメモリが作成されます。ここでxは実装に依存します。

ユーザーがx個以上の要素を挿入している場合、新しいメモリブロックより2倍（2倍のサイズ）の要素が作成され、初期ベクトルがこのメモリブロックにコピーされます。

予約番号 関数を呼び出すことによって、ベクトル用のメモリを予約することを常に推奨する理由は何ですか？

intvect.reserve（100）;

となるので、ベクターデータの削除やコピーを避けることができる。