某所で話題に上っていたせいで気になってstd::dequeの実装(P.J. Plaugerさんのヤツ)を覗いちゃったじゃないか!ヽ(`Д´)ノ ウワァァン!!
おかげで2時間もいらんことに費やしてしまったじゃないか!ヽ(`Д´)ノ ウワァァン!!
最初circular queueで実装していると知らずに読んでいたせいでちんぷんかんぷんだったんだぞ!ヽ(`Д´)ノ ウワァァン!!
特に,後方にbufferを拡大しているだけでどうやってfront insertionの定数償却性を保証しているかさっぱり分からずに相当苦戦してしまったじゃないか!ヽ(`Д´)ノ ウワァァン!!
で,circularだと気がついた後で,よく見たらソースの最初の方にほんのちょこっと申し訳程度に「circular queue」って書いてあるし!ヽ(`Д´)ノ ウワァァン!!
こういう大事なことはでっかくAAででも書いておけ!ヽ(`Д´)ノ ウワァァン!!
で,結局のところ,std::deque
ブロック化は最適化のための実装詳細で,dequeの本質にはあんまり関係ないじゃないか!ヽ(`Д´)ノ ウワァァン!!
やっぱり(Back Insertion Sequenceとしてなら)std::vector最強!ヽ(`Д´)ノ ウワァァン!!