c++ - stl vector がランダムアクセスを与える方法

Question

昨日の夕方、仕事に std::vector を使用していたのですが、この質問が頭に浮かびました: vector はどのようにしてランダムアクセスを提供するのでしょうか?

コードを調べようとしましたが、失敗しました。誰でもいくつかの指針を与えることができますか?

ありがとう、アルン

Answer 1

ベクターは連続したメモリを使用するため、基本的に配列と同じ方法でランダムアクセスを提供します。開始アドレスと要素のサイズを認識し、ポインター計算を行います。

Answer 2

確かに、ここにいくつかの指針があります：

int *x, *y;

しかし、真剣に、 avectorは内部的に配列として実装されているだけです。オーバーロードされたインデックス演算子 ( []) を提供して、配列のようにアクセスできるようにします。

Answer 3

少なくとも 2 倍

実際には、多くの実装では係数 1.5 が使用されます。重要なことは、これが係数であるため、ベクトルが指数関数的に大きくなるということです。

Answer 4

ベクターは通常、動的配列実装を使用します[*]...常にデータがメモリの連続ブロックに格納されるため、ポインター演算を使用して任意の (既存の) 要素への O(1) アクセスを行うことができます。

効率的な動的配列の秘訣 (まだ知らないと仮定して) は、リザーブド ストアのサイズを少なくとも定数倍に常に増やすことです (Jerry Coffin のコメントを参照)。この結果、不特定数の新しい要素を追加すると、単純化のために係数を 2 として、最初の要素が n 番目の追加でコピーされ、(2*n) 番目の追加と (4*n) 番目の追加でコピーされます。そしてその ...

この級数は収束するので、N 個の新しい要素を追加するのに O(N) の時間がかかることを保証できます。ただし、特定の追加では、既存のすべての要素の再割り当てとコピーが必要になる場合があるため、遅延の保証は一切ありません。

[*] 必要なパフォーマンスを実現する別のメカニズムを知りません。誰？