事の発端
以下のAtCoderの問題を解いている時にvectorで実装していたらTLEしたので、調べたところdequeなるコレクションがあるらしい。
記事の結論
- コレクションの先頭要素も追加、削除がある場合はdequeの使用を検討する
- コレクションの末尾への追加、削除とランダムアクセスに強いのはvector
vectorの特徴
メモリは連続した領域に確保される配列型のデータ構造をしている。
連続したメモリ領域に要素が順番に格納されるため、ランダムアクセスが高速で、かつ順番に要素が格納されるから末尾への操作に強い。
あらかじめ確保したメモリ容量よりも多く要素を管理しようとすると、新しい大きな配列を作ってコピーする。（これが起きると遅い）
要素の挿入や削除が起きると、例えば先頭の要素の削除をする場合は配列を詰めようとするためO(N)だけ時間がかかる。
dequeの特徴
両側から挿入と削除が出来るキュー(Double Ended Queueでdequeらしい)
実装的には一定サイズのブロックに分けて要素を格納し、それらをインデックス表で管理している。先頭や末尾のブロックにスペースがあればO(1)で要素の追加が出来る。スペースがないと新しくブロックを確保してそこに要素を詰める。先頭と末尾両方でデータの追加と削除をしてもデータのお引越しが発生しない。(vectorとの差別化ポイント)
名前の由来的にキューならランダムアクセス出来なくね？という気持ちになるが、先に述べたようにどのインデックスの何番かはすぐわかるため、vectorよりも遅いもののO(1)でランダムアクセスが可能。
弱点として、スペースの確保が動的でメモリの連続性も保証されないため、ポインタ操作や予め使用するメモリを確保しておくと言った操作はできない。