配列の動的なサイズ変更を可能にするためにC++のベクトルクラスはどのように実装されていますか？

Question

配列の動的なサイズ変更を可能にするためにC++ベクタクラスはどのように実装されていますか？

リンクリストタイプの実装によって行われますか？ 要素を追加または削除するたびに新しい配列が作成されますか？

おかげで、R

Answer 1

典型的な動作：内部、std::vectorは長capacityの連続した配列を有しています。どの時点でも、実際にはsize個の要素しか使用されていません。いずれの点でもsizeがcapacityを超えている場合（push_back()とよく言わせてください）、新しい、より大きな内部配列が割り当てられます（capacityが2倍になるかもしれません）。古い配列のすべての要素が新しい配列にコピーされ、古い要素と配列が削除されます。

Answer 2

詳細は実装に依存しますが、ベクトルによって割り当てられるメモリブロックは連続していることが保証されています。

GCCはメモリを再割り当てするときに2.0係数を使用しますが、MSVCは1.5係数を使用しています。

Answer 3

ほとんどの実装では単純な配列を使用し、配列がいっぱいになるたびに容量を2倍にします。これには、既存の要素を新しいメモリブロックにコピーすることが含まれますが、これをもう一度やり直す必要はないという事実によって補償されます。このような手法を使用すると、要素の追加は償却された一定時間で実行されます。