複雑::挿入（）

Question

私は次のようにC++標準2003（章23.2.1.3）からdeque::insert()の複雑さを学びました：

を最悪の場合には、両端キューに、単一の要素を挿入するには時間がかかります挿入点から両端キューの開始点までの距離と挿入点から端点までの距離の最小値で直線的です。

私はいつもメモリチャンクのコレクションとしてのstl dequeの実装を理解しています。したがって、挿入は、挿入位置と同じメモリチャンク内の要素にのみ影響します。私の質問は、標準が意味することは、「挿入点から両端キューの始めまでの距離と挿入点から端点までの距離の最小値が直線的」とはどういう意味ですか？

私の理解は、C++標準がdequeの特定の実装を強制しないためです。複雑さは、最悪の場合の一般的なものです。しかし、コンパイラでの実際の実装では、メモリチャンク内の要素の数に比例します。これは、要素のサイズによって異なる場合があります。

insert()はすべてのイテレータを無効にするので、dequeはすべてのイテレータを更新する必要があります。したがって、それは線形です。

Answer 1

std :: dequeは通常、メモリチャンクのコレクションとして実装されています（）。通常、コレクションの途中に1つの新しい要素を挿入するだけでは全く新しいチャンクを挿入しません。そのため、挿入ポイントが開始または終了に近いかどうかを確認し、既存の要素をシャッフルして、既存のチャンク内の新しい要素のための領域を確保します。それは、コレクションの最初または最後にメモリの新しい塊を追加するだけです。

Answer 2

挿入された要素数の直線性（コピー構成）。さらに、特定のライブラリ実装に応じて、位置と両端キューの両端の1つの間の要素数までの追加の線形時間。 Reference...

Answer 3

あなたの推測は... 99.9％です。 すべては実際の実装が何であるかによって異なります。規格が規定しているのは、実装者（仕様に適合しない場合は標準ではないと主張することができない）とユーザ（実装に依存しないコードを書く場合は「より良い性能」を期待してはならない）の両方に対する最小要件です。

仕様の背後にあるアイデアは、初期化されていないメモリのチャンク（== 1）です。 途中に挿入するとシフトします。フロントまたはエンドに挿入すると、その場に構築されます。 （スペースがない場合、再割り当てが行われます） インデックスとイテレータは、変更後には何がシフトされたのか、どの方向であるのかを仮定することはできません。

より効率的な実装では、単一のチャンクを使用せず、複数のチャンクを使用して、「シフト」問題を再配布し、メモリを一定のサイズで割り当てます（したがって、再割り当てとフラグメンテーションは制限されます）。 あなたがそれらの1つをターゲットにしている場合、より良いパフォーマンスが期待できます。そうしないと、構造の最適化を想定しない方がよいでしょう。

Answer 4

私はあなたがダイアグラムの方がいいと思っています... ASCIIアートで遊ぼう！

通常、両端キューはメモリチャンクの配列ですが、離れていってもフロントとバックメモリチャンクはいっぱいです。これが必要である両端キューが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つの要素が含まれているといっぱいになっていると仮定します。実際には、誰もサイズが固定されているとは言わず、内側のバケツはすべて同じサイズでなければなりません。

• バケット2（のみ）
を拡張：

// Deque 
0:  ++ 
1: ++++++++ 
2: ++++++++ 
3: ++++++++ 
4: +++++ 

は、今、私たちが考えることができるいくつかの戦略があります。それは2ラベルされたバケツのどこかに落ち、我々はインデックス13で挿入したいことを言います

• は2の前または後に新しいバケットを紹介し、いくつかの要素だけ

をシャッフルしかし、これらの2つの戦略は、すべての「内側」バケットが同じNUMを持っていることを不変に違反します要素のber。そこで我々は、我々の場合には、（どちらが安いです）のいずれか先頭や末尾に向かって、周りの要素をシャッフルして残っている

：バケット0が成長する方法

// Deque 
0:  +++ 
1: ++++++++ 
2: +O++++++ 
3: ++++++++ 
4: +++++ 

は注意してください。

このシャッフルは、最悪の場合、要素の半分（O（N/2））を移動することを意味します。

dequeには、正しい場所に要素を追加するか、（バケットがいっぱいである場合）新しいバケットを作成するだけでO（1）の挿入があります。

B+ Treesに基づいて、ランダムインデックスでの挿入/消去の動作が優れている他のコンテナがあります。インデックス付きのB +ツリーでは、「キー」（または並行して）ではなく、特定の位置より前の要素の数を内部的に維持することができます。これを効率的に行うためのさまざまな技術があります。終わりに、あなたがコンテナを取得する：

• O（1）：空、サイズ
• O（Nを記録）：、挿入、で

を消去あなたにはblistモジュールを確認することができますPythonは、このような構造に裏打ちされたPythonのリストのような要素を実装しています。