deque

「(STLの)dequeって、配列をいくつかつないだやつ〜」とか、少し前に誰かさんが言ってた。
（誰が言っていたのかさえ、忘れてしまったんだけれども）
　
……あれ、そうだっけ？　環状バッファのことじゃなかったっけ？
　
とか思いつつも、ちと自信がなかったので指摘しなかったんだけれども。
　
std::dequeの定義、、、
　
A、前方・後方への挿入削除がO(1)
B、ランダムアクセスが可能 ( つまり、n番目の要素へのアクセスがO(1) )
　
配列いくつか繋げりゃAは満たせるけどBが満たせない。
てか、そもそも配列をつなげたって、それは連結リストと何も違わない。
　
そういえば、バッファ不足の場合のオーダーって、その時の要素数がNだとして、新しいバッファにコピーすることを考えれば、vectorもdequeも、挿入コストがO(1)とは思えない。最悪O(N)なんじゃないかとか。
しかしバッファオーバーが起こるタイミングを考えてみると、N回の挿入が行われた時、1回だけ挿入コストがO(N)になるわけで……遅延コストが発生していると思えば、1回辺りの平均コストはO(1)で行けそう……
　
もっと具体的に証明すると、要素数Nでメモリ拡張する時、2Nのメモリ領域に拡張すれば……
　
挿入回数 -> コピーコスト
N -> N
2N -> N + 2N
4N -> N + 2N + 4N
8N -> N + 2N + 4N + 8N
(2^M)N -> (2(2^M)-1)N
　
なので、メモリオーバーの際は2倍の領域にメモリ確保してやるようにすれば、挿入コストをO(1)と証明可能。
　
STLでのメモリ拡張時に、1.5倍とかでは決してなくて、2倍の領域拡張を行っているのには、こうした理由があったわけですね。