ダイアグラムの方がいいと思います...アスキーアートで遊んでみましょう！
通常、deque はメモリ チャンクの配列ですが、フロント メモリ チャンクとバック メモリ チャンクはすべて満杯です。これが必要なのは、deque が RandomAccessContainer であり、任意のコンテナーへの O(1) アクセスを取得するために、サイズを読み取るコンテナーの無制限の数を持つことができないためです。
bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; }
T& operator[](size_t i) {
if (i < first.size) { return first[SIZE - i]; }
size_t const correctedIndex = i - first.size;
return buckets[correctedIndex / SIZE][correctedIndex % SIZE];
}
これらの演算は、乗算/除算により O(1) です!
この例では、メモリ チャンクに 8 つの要素が含まれている場合、メモリ チャンクがいっぱいであると想定します。実際には、すべての内側のバケットが同じサイズでなければならないというだけで、サイズを固定する必要があるとは誰も言いませんでした。
// Deque
0: ++
1: ++++++++
2: ++++++++
3: ++++++++
4: +++++
ここで、インデックス 13 に挿入したいとします。これは、2 というラベルの付いたバケットのどこかに収まります。考えられるいくつかの戦略があります。
- 拡張バケット 2 (のみ)
- 2 の前または後に新しいバケットを導入し、いくつかの要素のみをシャッフルする
しかし、これら 2 つの戦略は、すべての「内部」バケットが同じ数の要素を持つという不変条件に違反します。
したがって、この場合、最初または最後 (どちらか安い方) に向かって要素をシャッフルする必要があります。
// Deque
0: +++
1: ++++++++
2: +O++++++
3: ++++++++
4: +++++
バケット 0 がどのように成長したかに注意してください。
このシャッフルは、最悪の場合、要素の半分 (O(N/2)) を移動することを意味します。
dequeただし、最初または最後に O(1) 挿入があります。これは、要素を適切な場所に追加するか、(バケットがいっぱいの場合) 新しいバケットを作成するだけの問題だからです。
B+ Treesに基づいて、ランダムなインデックスでより優れた挿入/消去動作を持つ他のコンテナーがあります。インデックス付きの B+ ツリーでは、「キー」の代わりに (または並行して)、特定の位置より前の要素の数を内部的に維持できます。これを効率的に行うためのさまざまなテクニックがあります。最後に、次のコンテナを取得します。
- O(1): 空、サイズ
- O(log N): at、insert、erase
blistこのような構造に裏打ちされた Python リストのような要素を実装する Pythonのモジュールを確認できます。