std :: dequeサブアレイのサイズが固定されているのはなぜですか？

Question

背景

std::dequeは、その要素を格納するためにサブアレイを使用します。そのサブアレイを追跡するための追加のブック管理データ構造を持っています。このように、std::vectorと比較して、std::dequeは、償却されたO（1）と比較して、より早く（O（1））、O（n）と比較してOこれは、std::dequeがどちらかの端にサブアレイを追加するだけで、ブックのデータ構造を変更する必要があるためです。

---

質問

hereを説明するようにサブアレイが自分のサイズが固定されている理由を私は理解していないことである。

典型的な実装は、個別に割り当てられた固定サイズのシーケンスを使用アレイ

固定サイズのサブアレイを持たないという利点があります。たとえば、サブアレイのサイズは固定されているため、中間の挿入はO（n）の複雑さでなければなりません。ここで、nは最も近い端までの要素の数です。しかし、サブアレイが自由に成長する場合、中央の挿入はO（k）になります。ここで、kはサブアレイ内の要素の数であり、特にstd::dequeに多くのサブアレイがある場合はずっと高速です。途中から削除する場合も同じです。

std::dequeはサブアレイのバランスを保ちたいと考えていますか？これは、サブアレイが大きすぎる/小さすぎると分割またはマージすることを可能にすることで簡単に緩和できます。複雑さはちょうどO（k）になります。ここでkは最大サブアレイのサイズです。 （または、最小のサブアレイとそれより小さな隣のサブアレイの合計サイズ）

固定サイズのサブアレイはランダムな反復を高速化するためですか？たとえば、n番目の要素が必要な場合は、ブックを保持しているデータ構造を調べて、複雑さO（k）を作るすべての前の部分配列のサイズを追加する必要があります。ここで、kはブック構造のサイズです。 しかし、これは大きな問題ではありません。std::dequeは、二重にリンクされたリストであるとアドバタイズされています。

---

EDIT：std::dequeは、リンクリストの実装と配列の実装間のちょうど真ん中の男です。私は私の質問は、その本来の意味を失っているし、それはより多くのサブアレイが自分のサイズが固定されている理由

Answer 1

は、私が理解していないことであるベクトルよりも、リンクリストのように振る舞うべきであると示唆された推測

これは、コメントで指摘されているように、標準によって要求される一定の複雑さのランダムアクセスを可能にするためです。

---

しかし、これは私が反対し、そしておそらくその標準委員会は希望

巨大な契約ではありません。 std::deque以来

は二重にリンクされたリストであることが宣伝されて...

それは、次のような広告を出していません。