C++解説11(dequeとlist)

「deque」と「list」は「vector」と同じ順序コンテナと呼ばれるものです。

「deque」は「vector」に対して配列の先頭に要素加する事も
高速で実現ができるコンテナで
その他については「vector」と同一と考えて問題ないでしょう。
これだけを書くと「vector」は不必要で「deque」だけ存在すれば良いのではないか？
という感じもします。

実際問題、多くのケースは「deque」だけで問題ないと思います。
逆の言い方をすれば、「vector」だけで
問題ないケースがほとんどかもしれません。
どのようなプログラムを記述するかに依存しますが
配列の先頭に要素追加を行う必要性がないのであれば
「vector」で良いのではないかというのが
私の考え方ではあります。

もし、後で配列の先頭に要素追加を行う必要が存在した場合
「deque」と「vector」の関係であれば、よっぽどの事がない限り
配列の定義部分のみを変更してしまえば動くのではないかと思います。
まあ、この事態は設計ミスという事になりますが。
（言語が設計ミスをカバーするってもの変な話です）

「vector」を使えれば、間違いなく「deque」は使用できます。
以下に違いを示しますが大きい問題ではない事が分かると思います。

「deque」のみ存在する関数
pop_front() 先頭要素を削除する
push_front() 両端キューの先頭に要素を追加する

「vector」のみ存在する関数
capacity() ベクタが保持できる要素数
reserve() ベクタが保持できる要素数を設定する

相互変更をする場合に上記関数を使用していなかった場合
それぞれ置き換える事が可能という事になります。
「deque」を使用していて「pop_front」「pop_back」を
使用していないのは、ちょっと理解できないですね。

「vector」が準備している「capacity」、「reserve」というものは
ほとんど使わないのではないでしょうか。

「reserve」を使用するのは本当の意味での
高速プログラムを実現する時です。
「vector」は要素を無限(これは言い過ぎですがまあ嘘にはならないかな)
に追加できるのが特徴ですが、その裏では「メモリを確保」して、
「確保したメモリに既存のデータをコピー」してといった
容易に想像できる処理が動いています。

しかし、この確保するメモリを多くすれば拡張回数を減らす事ができます。
かと言って、多すぎるメモリの確保は
獲得コストが必要以上に要する事態が発生します。

つまり通常発生するデータの格納個数をＡ、
突発的な事故が発生しデータ量が増えるケースを予期した戸数をＢとした場合
一番最初に「Ａ」の分だけ「reserve」してしまえば
無駄なメモリの確保、コピーが減るという事になります。
しかも多くの場合、領域の確保、データのコピーというものは発生しないでしょう。
このような対策を「reserve」を上手く利用する事で行える事になります。

しかし、この処理にコストがかかると言っても
何秒といった時間が係るわけでもないため
ここまで性能を追求するプログラムを作成する
機会というのは少ない気もします。

要するに、「reserve」など使う機会がほとんどないですよ！
って事を言いたいのです。
それは「capacity」にも言える事で、私が思うに「capacity」って
一度も使った事が無いかもしれません。
覚えている限りではないです。(練習は除きますよ)

この事から、「vector」から「deque」にコンテナを移す事は
多くの場合で容易にできる事が分かると思います。

「list」は多少２つに比べると特徴に違いがあります。
最大の違いは「ランダムアクセス」不可というコンテナであるところです。
「ランダムアクセス」とは直接アクセスだと考えて下さい。
イテレータのところで扱った「random_iterator」が扱えないという事です。
つまり配列のインデックスを指定する際に「[]」という演算子を指定しますが
「list」にはそれができないという事になります。
これだけでもかなりの特徴があると思います。

vector v;
deque d;
list l;

v[0]=1;
d[0]=1;
l[0]=1; ← 出来ない！

という事です。何故か？というと「list」というコンテナが
「ランダムアクセス」を行われることを前提に設計されていないからです。
「ランダムアクセスを行えるようにする」場合と
「ランダムアクセスを行えなくても良い」場合では
何が違うのかというとメモリが連続領域である必要がないというところです。

つまり配列サイズが10となっている「a」の５番目の要素を削除したい場合
配列を確保するメモリが連続領域である必要のある
「vector」「deque」については、５番目の要素を削除後に
それより後ろに格納されている全てのデータを１つ前に移動させる必要があります。

それに対して「list」は連続領域である必要がないため
「Ｎ番目のデータの次はＮ＋２番目である」
「Ｎ＋２番目のデータの前はＮ番目である」という
２つの処理を行う事で要素の削除が行えることになります。
逆も同じで配列途中に要素を追加する事を考える場合、
「vector」「deque」は追加する要素位置以降に存在する要素を
全て追加する要素分後ろにずらしてから、要素の追加を行います。
「list」は「Ｎ番目のデータの次はＭ番目である」
「Ｎ＋１番目のデータの前はＭ番目である」という
２つの処理を行う事で要素の追加が行えます。

データの追加、削除を配列の途中に頻繁に行う場合、
「list」というコンテナは非常に有用です。
少量のデータであれば、気にするポイントではないかもしれませんが
大量のデータを扱う場合にはパフォーマンスなど
コンテナを選択した段階で決まっているようなものです。
どんなに、高速なプログラムを組んでも
設計が間違っていれば高速にはなりきれないという事です。

扱い方は「vector」「deque」と同じです。
これがＳＴＬの素晴らしいところですね。