なぜstd :: vectorはオフセットを使用しませんか？

Question

本当に簡単な質問です。ベクトルの前面に追加したり削除したりするとき、なぜこの変更に対応するためにすべての要素をシフトする必要がありますか？ベクトルにインデックスを付けるときに与えられたインデックスを変更する代わりにオフセットを使用すると、この問題は解決します。これにより、（最大で）2つの連続したデータブロックのメモリが得られる可能性がありますが、これは線形演算を一定時間に減らすために支払う小さな値段のようです。

['A', 'B', 'C', _, _, _, _, _] offset is 0, 4th through 8th position unused. 
push_front('M') 
['A', 'B', 'C, _, _, _, _, 'M'] offset is -1 

、その後

operator[](size_t index) { 
    return backing_array[(index + offset) % size] 
} 

のインデックスを作成するとき、私はこれがデータの1純粋な連続したブロックであってよいが、1から動いていない可能性がありますを意味し得る：

はここで、可能な限り明確にすることの例です2への一定の時間のプッシュとポップのフロントと引き換えに、巨大な取引のようには見えません。

Answer 1

私は、これはありません、それはすぐそこに物語の終わりだデータ

の1純粋な連続したブロックは存在しない可能性がありますを意味し得ます。 vectorの全体点は、がであり、 "純粋な連続したデータブロック"であるということです。これは実装の基本要件です。

これを行う能力はvectorの全体の目的の核心部分である：

T *ptr = &vec[0]; 
ptr+1; 
ptr == &vec[1]; 

したがって、インタフェースは、連続であることからvectorを妨げる追加の要件を提供することができません。

Answer 2

ベクトル全体の考え方は、単一の連続したデータ・ブロックのためである：たとえば、あなたは、C APIへの（最初の要素のほか、アドレス）にそれらを渡すことができ、あなたは良いキャッシュの局所性を得る、など

標準dequeの正確には必要なシナリオ：コンテナの前面/背面の高速プッシュ/ポップ。