c++ - std::vector内部

Question

どのstd::vectorデータ構造を使用して、どのように実装されますか？私が書くとき

void f(int n) {
  std::vector<int> v(n);
  ...
}

ベクトルvはスタックに割り当てられていますか？

Answer 1

vectorオブジェクトはスタックに割り当てられ、ヒープ上の要素の先頭へのポインターを内部的に含みます。

ヒープ上の要素により、vectorクラスは必要に応じて拡大および縮小できます。

スタックvector上にある間、スコープ外に出るときにオブジェクトが破壊されるという利点があります。

あなたの[]質問に関して、vectorクラスは演算子をオーバーロードします。私はあなたがするときそれが基本的にこのようなことをしている[]と内部的に言うでしょう：array[1]

return *(_Myfirst+ (n * elementSize))

vectorが内部ヒープの開始を追跡する場所_Myfirst。

いっぱいにvectorなり始めると、より多くのメモリが割り当てられます。一般的な方法は、毎回必要なメモリの量を2倍にすることです。

次のメンバーを含むvectorから継承することに注意してください。_Vector_val

pointer _Myfirst;   // pointer to beginning of array
pointer _Mylast;    // pointer to current end of sequence
pointer _Myend; // pointer to end of array
_Alty _Alval;   // allocator object for values

Answer 2

あなたvは自動メモリに割り当てられます。（一般にスタックとして知られています、はい）

実装の詳細は指定されていませんが、最も一般的には、以前の割り当てで保持できるよりも多くの要素を追加しようとするとサイズが変更される動的配列を使用して実装されます。

この標準では、インターフェース（どのメソッドが必要か）と実行時間の境界のみが指定されています。

vectorはテンプレートであるため、実装が表示されます。ファイルを見つけて検査<vector>を開始してください。

Answer 3

void f(int n) {
  std::vector<int> v(n);
  ...
}

上記のベクトルには自動保存期間があり、スタックに割り当てられます。ただし、ベクターが管理するデータ配列はヒープに割り当てられます。

ベクトルの内部は実装固有ですが、一般的な実装には3つのポインターが含まれます。配列の開始、ベクトルのサイズ、およびベクトルの容量を追跡するために1つずつ。