質問: `vector`と`list`どのように使い分けますか?この様な質問を受けました。 そこで私は、`vector`は配列で`list`はリストだろう。 具体的な使い分けとなると、リストは切ったりつなげたりが得意で`vector`は配列メモリが消費が少ない。 けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。 中間地点への一つのデータを頻繁に削除・挿入するのだとしたら検索まで含めると`map`や`set`の方が早い気がします。 最初や最後の地点だとしたら`list`でなくても`queue`で足りるはずです。 となると、メモリを多く消費して実例の見当たらない切ったりつなげたりの動作が必要になる場面が思い浮かばず、「`vector`の方が優れています。」と言ってしまいました。 stlのデータ構造のどれを差し置いてもlistで表現するのが適切となるアルゴリズムやプログラムは存在しますか
回答: `list`で表現するのが適切なアルゴリズムやプログラムは数多く存在します。 むしろ、`vector`の方が使う場面を選ぶかと。 `vector`の最大の利点はメモリ消費量ではなく、アクセス速度です。 動的にサイズが変更できるのに、メモリ上は連続した領域となっている為にランダムアクセス可能というのが`vector`の利点です。 欠点はサイズ変更や削除を行う際に巨大なコピーコストがかかる部分です。内部的には配列なので。 また、細かい事を言えば`vector`は内部的に必要量の最大1.5倍~2倍程度のメモリを確保するため、メモリ消費量はむしろ大きくなります。 `list`の利点は、書かれている通り挿入/削除に対するパフォーマンスが良い部分です。 `vector`は途中の要素を削除した場合、削除部分以降の要素全てに移動が起こりますが、 `list`は最小限のコストで済みます。 その代わり、ランダムアクセスが不可能なので検索は遅くなります。 `set`や`map`は、`list`や`vector`とは用途が違います。 `set`や`map`は基本的に検索用途のコンテナです。 検索速度を上げる為に、以下の性質を持っています。 1. `set`や`map`は同一要素(キー)を2つ以上保持できない。 2. `set`や`map`の内部要素は、insert時に自動的にソートされる。 例えば、`set`に対して、1,2,3,9,8,7,6,5,4,1,2,3 という順番で数値を`insert`したとしても、 取り出す内容・順番は1,2,3,4,5,6,7,8,9になってしまいます。 以上の理由により、`list`が適している場面は単純に「挿入削除が頻繁に起こる場面」という事になります。