私は STL コンテナーを調べて、それらが実際に何であるか (つまり、使用されているデータ構造) を把握しようとしていましたが、dequeが私を止めました: 最初は、これは二重にリンクされたリストであり、両端からの挿入と削除が可能になると思いました一定時間ですが、オペレーター[]が一定時間で行うという約束に悩まされています。リンクされたリストでは、任意のアクセスは O(n) のはずですよね?
また、動的配列の場合、要素を一定時間で追加するにはどうすればよいでしょうか? 再配分が発生する可能性があること、および O(1) はvector の場合と同様に償却コストであることに注意してください。
では、一定時間内に任意のアクセスを可能にし、同時に新しい大きな場所に移動する必要がないこの構造は何なのだろうか。
両端キューは幾分再帰的に定義されます。内部的に、固定サイズのチャンクの両端キューを維持します。各チャンクはベクトルであり、チャンクのキュー (下図の「マップ」) 自体もベクトルです。
パフォーマンス特性の優れた分析と、CodeProjectvectorでのオーバーとの比較があります。
GCC 標準ライブラリの実装は、内部的に a を使用しT**てマップを表します。各データ ブロックは、固定サイズ(に依存)T*で割り当てられるです。__deque_buf_sizesizeof(T)
ベクトルのベクトルとして想像してみてください。それらだけが標準ではありませんstd::vector。
外側のベクトルには、内側のベクトルへのポインターが含まれています。その容量が再割り当てによって変更されると、空きスペースのすべてを最後に割り当てるのではなくstd::vector、ベクターの最初と最後で空きスペースを均等に分割します。これによりpush_front、push_backと このベクトルの両方が償却された O(1) 時間で発生します。
内部ベクトルの動作は、それが の前面にあるか背面にあるかに応じて変更する必要がありdequeます。std::vector後ろでは、最後に成長し、push_backO(1) 時間で発生する標準として動作できます。先頭では反対のことをする必要があり、最初はそれぞれpush_front. 実際には、これは、フロント要素にポインタを追加し、サイズとともに成長方向を追加することで簡単に実現できます。この単純な変更により、push_frontO(1) 時間になることもあります。
任意の要素へのアクセスには、O(1) で発生する適切な外部ベクトル インデックスへのオフセットと分割、および同じく O(1) である内部ベクトルへのインデックスが必要です。これは、 の先頭または末尾のものを除いて、内部ベクトルがすべて固定サイズであると仮定していdequeます。
deque = 両端キュー
どちらの方向にも成長できるコンテナ。
通常、 Deque はvectorofとして実装されますvectors(ベクトルのリストは一定時間のランダム アクセスを提供できません)。セカンダリ ベクトルのサイズは実装に依存しますが、一般的なアルゴリズムでは一定のサイズをバイト単位で使用します。
(これは私が別のスレッドで与えた回答です。本質的に、単一の を使用するかなり素朴な実装でさえvector、「一定の非償却 push_{front,back}」の要件に準拠していると主張しています。驚くかもしれません。 、これは不可能だと思いますが、驚くべき方法でコンテキストを定義する標準の他の関連する引用を見つけました. ご容赦ください; この回答で間違いを犯した場合、どのことを特定するのが非常に役立つでしょう.私は正しく、どこで私の論理が壊れているかを言いました. )
この回答では、適切な実装を特定しようとしているのではなく、C++ 標準の複雑さの要件を解釈するのを手助けしようとしているだけです。N3242から引用しています。これは、 Wikipediaによると、自由に入手できる最新の C++11 標準化ドキュメントです。(最終標準とは異なって編成されているように見えるので、正確なページ番号は引用しません。もちろん、これらの規則は最終標準で変更された可能性がありますが、私はそれが起こったとは思いません。)
を使用するdeque<T>ことで、 を正しく実装できますvector<T*>。すべての要素がヒープにコピーされ、ポインターがベクターに格納されます。(ベクトルについては後で詳しく説明します)。
なぜT*代わりにT？規格で要求されているため、
「両端キューのいずれかの端に挿入すると、両端キューへのすべての反復子が無効になりますが、両端キューの要素への参照の有効性には影響しません。」
（私の強調）。それT*を満たすのに役立ちます。また、これを満たすのにも役立ちます。
「両端キューの先頭または末尾に単一の要素を挿入すると、常に ..... T のコンストラクターが 1 回呼び出されます。」
さて、（物議を醸す）ビットについて。vectorを格納するT*ために を使用する理由 これにより、ランダム アクセスが可能になります。これは良いスタートです。vector の複雑さについてはしばらく忘れて、慎重に構築していきましょう。
標準は、「含まれるオブジェクトに対する操作の数」について述べています。正確に 1 つのオブジェクトが構築され、既存のオブジェクトが何らかの方法で読み取られたりスキャンされたりしないためdeque::push_front、これは明らかに 1 です。この数 1 は明らかに定数であり、現在両端キューにあるオブジェクトの数とは無関係です。これにより、次のことが言えます。TT
「私たちのdeque::push_frontでは、含まれているオブジェクト (Ts) に対する操作の数は固定されており、すでに両端キューにあるオブジェクトの数とは無関係です。」
もちろん、 での操作の数はT*それほど適切ではありません。がvector<T*>大きくなりすぎると、再割り当てされ、多くT*の がコピーされます。そうです、 での操作の数はT*大きく異なりますが、 での操作の数はT影響を受けません。
Tでの操作のカウントと での操作のカウントのこの違いを気にするのはなぜT*ですか? それは、標準に次のように記載されているためです。
この節のすべての複雑さの要件は、含まれるオブジェクトに対する操作の数に関してのみ述べられています。
の場合deque、含まれるオブジェクトはTではなくです。T*つまり、 をコピー (または再割り当て) する操作は無視できますT*。
ベクターが両端キューでどのように動作するかについては、あまり説明していません。おそらく、これを循環バッファーとして解釈します (ベクターは常に最大値を使用しcapacity()、ベクターがいっぱいになるとすべてをより大きなバッファーに再割り当てします。詳細は問題ではありません。
最後の数段落deque::push_frontで、deque 内のオブジェクトの数と、含まれているオブジェクトに対して push_front によって実行された操作の数との関係を分析しましたT。そして、それらが互いに独立していることを発見しました。標準では、複雑さは操作に関するものであることが義務付けられているため、Tこれには一定の複雑さがあると言えます。
はい、Operations-On-T*-Complexityは ( により) 償却されますが、 Operations-On-T-Complexityvectorのみに関心があり、これは一定です (非償却)。
vector::push_back または vector::push_front の複雑さは、この実装では関係ありません。これらの考慮事項は操作に関係するT*ため、無関係です。標準が「従来の」複雑さの理論的概念に言及していた場合、「含まれるオブジェクトに対する操作の数」に明示的に制限されていなかったでしょう。私はその文を過度に解釈していますか?
標準は特定の実装を義務付けていませんが (一定時間のランダム アクセスのみ)、deque は通常、連続したメモリ「ページ」のコレクションとして実装されます。必要に応じて新しいページが割り当てられますが、ランダム アクセスは引き続き可能です。とは異なりstd::vector、データが連続して格納されるとは限りませんが、ベクターと同様に、途中での挿入には多くの再配置が必要です。