[解決済み】STLのdequeって実際どうなの？

質問

STLコンテナを見て、その実態（使用されるデータ構造）を把握しようとしたところ ディーク と思いました。最初は二重リンクリストだと思い、両端からの挿入・削除が一定時間でできるのではと思ったのですが、悩むのは 約束 演算子[]が一定時間で行われるようにすることです。リンクリストでは、任意のアクセスはO(n)になるはずですよね？

また、動的配列であれば、どのようにして 要素を追加する を一定時間で実行できますか？再割り当てが起こる可能性があること、O(1)は償却コストであることを述べておく必要があります。 ベクターのように .

では、一定の時間で任意のアクセスが可能で、同時に新しい大きな場所に移動する必要がないこの構造は何だろうと考えています。

どのように解決するのか？

dequeはやや再帰的に定義されており、内部的には、以下のようなダブルエンドのキューを維持します。 チャンク 固定サイズの 各チャンクはベクトルであり、チャンクの待ち行列（下の図では「マップ」）自体もベクトルである。

性能特性と比較した素晴らしい分析があります。 vector にて。 コードプロジェクト .

GCC標準ライブラリの実装では、内部で T** を使用してマップを表現します。各データブロックは T* これは、ある固定サイズで割り当てられる __deque_buf_size (に依存する）。 sizeof(T) ).