vectorとlistどのように使い分けますか


`vector`と`list`どのように使い分けますか？この様な質問を受けました。

そこで私は、`vector`は配列で`list`はリストだろう。  
具体的な使い分けとなると、リストは切ったりつなげたりが得意で[`vector`は配列メモリが消費が少ない。](http://d.hatena.ne.jp/ponkotuy/20111216/1324027752)  
けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。  
中間地点への一つのデータを頻繁に削除・挿入するのだとしたら検索まで含めると`map`や`set`の方が早い気がします。  
最初や最後の地点だとしたら`list`でなくても`queue`で足りるはずです。  
となると、メモリを多く消費して実例の見当たらない切ったりつなげたりの動作が必要になる場面が思い浮かばず、「`vector`の方が優れています。」と言ってしまいました。

stlのデータ構造のどれを差し置いてもlistで表現するのが適切となるアルゴリズムやプログラムは存在しますか




大抵のケースでは `vector<T>` 利用で十分かと思います。（`T`は要素の型）

Scott Meyers, "[Effective
STL](http://rads.stackoverflow.com/amzn/click/0201749629)" でも、Item 1で次の言及があります

> `vector` is the type of sequence that should be used by default.

`list<T>`
の方が好ましいのは、下記条件を満たすときくらいです。どの程度なら"頻繁／多く／大きい"といえるかは、処理内容や要素型に強く依存するので、最終的には実測して判断すべきでしょう。

  * 中間位置に対する要素の挿入／削除が **頻繁** に行われ、
  * コンテナに格納される要素数が **非常に多く** 、
  * 要素型のサイズ(`sizeof T`)が **十分大きい** とき。

* * *

下記に、`vector` と `list` の主な特徴を挙げておきます。

## `std::vector`シーケンスコンテナ

  * いわゆる「可変長配列(variable length array)」コンテナ。
  * 1要素あたりのメモリ使用量のオーバーヘッドが小さい。目安として `sizeof T`×容量＋ポインタ型1個＋整数型2個 分のメモリしか利用しないため、特に`T`型が小さいときに有利。  
  

    * 動的メモリ確保されるのは "×容量(`capacity()`)" であって、"×要素数(`size()`)" ではない事に注意。事前に要素数を予測できる場合は、適切な容量指定しておく(`reserve()`)ことで、要素挿入時のメモリ再確保コストを削減できる。
  

  * 任意位置要素へのランダムアクセス(`operator[]`)が定数時間（ほぼゼロコスト）で可能。
  * 末尾位置以外への要素挿入は、線形時間がかかる。  
  

    * 末尾位置への挿入(`push_back()`)かつ容量＞要素数のときのみ、定数時間で要素挿入を行える。容量拡張が必要になる場合は、動的メモリ再確保により最大で2.5～3倍程度のメモリを要求する。
  

  * 全要素が連続したメモリ領域に配置されると保証されるため、配列型(`T*`など)を要求するレガシーAPIに渡す事ができる。  
  

    * 要素の順次走査ではCPUキャッシュの利用効率が良く、高速な走査を期待できる。（データ局所性が高く、ハードウェア・プリフェッチャ機構と相性が良い）
  

  * 要素の挿入／削除をおこなうと、他要素をさすイテレータが無効化されてしまう。
  * 要素数取得(`size()`)は定数時間（ほぼゼロコスト）で可能。

## `std::list`シーケンスコンテナ

  * いわゆる「双方向連結リスト(doubly-linked list)」コンテナ。
  * 1要素あたりのメモリ使用量のオーバーヘッドが大きい。目安として (`sizeof T`＋ポインタ型2個)×要素数 を利用するため、特に`T`型が小さいときは無駄が大きい。  
  

    * 容量という概念をもたず、常に "×要素数(`size()`)" オーダーのメモリを消費する。
  

  * 先頭要素(`front()`)／末尾要素(`back()`)へは定数時間でアクセスできるが、中間要素へのアクセスは順次走査（線形時間）が必要となる。
  * 任意位置への要素の挿入／削除を定数時間で行える。
  * 要素同士は離れたメモリ位置に配置される。  
  

    * 順次走査であってもCPUキャッシュラインを浪費しがちで、一般に`vector`よりも低速な走査となる。（特に挿入／削除が頻繁に行われた場合、データの局所性が失われている。）
  

  * 要素の挿入／削除をおこなっても、他要素をさすイテレータは無効化されない。
  * 要素数取得(`size()`)には線形時間が必要となる。C++11以降ならば定数時間が仕様上保証されるが、使用するコンパイラやライブラリの対応状況を確認のこと。




大抵のケースでは `vector<T>` 利用で十分かと思います。（`T`は要素の型）

Scott Meyers, "[Effective
STL](http://rads.stackoverflow.com/amzn/click/0201749629)" でも、Item 1で次の言及があります

> `vector` is the type of sequence that should be used by default.

`list<T>`
の方が好ましいのは、下記条件を満たすときくらいです。どの程度なら"頻繁／多く／大きい"といえるかは、処理内容や要素型に強く依存するので、最終的には実測して判断すべきでしょう。

  * 中間位置に対する要素の挿入／削除が **頻繁** に行われ、
  * コンテナに格納される要素数が **非常に多く** 、
  * 要素型のサイズ(`sizeof T`)が **十分大きい** とき。

* * *

下記に、`vector` と `list` の主な特徴を挙げておきます。

## `std::vector`シーケンスコンテナ

  * いわゆる「可変長配列(variable length array)」コンテナ。
  * 1要素あたりのメモリ使用量のオーバーヘッドが小さい。目安として `sizeof T`×容量＋ポインタ型1個＋整数型2個 分のメモリしか利用しないため、特に`T`型が小さいときに有利。  
  

    * 動的メモリ確保されるのは "×容量(`capacity()`)" であって、"×要素数(`size()`)" ではない事に注意。事前に要素数を予測できる場合は、適切な容量指定しておく(`reserve()`)ことで、要素挿入時のメモリ再確保コストを削減できる。
  

  * 任意位置要素へのランダムアクセス(`operator[]`)が定数時間（ほぼゼロコスト）で可能。
  * 末尾位置以外への要素挿入は、線形時間がかかる。  
  

    * 末尾位置への挿入(`push_back()`)かつ容量＞要素数のときのみ、定数時間で要素挿入を行える。容量拡張が必要になる場合は、動的メモリ再確保により最大で2.5～3倍程度のメモリを要求する。
  

  * 全要素が連続したメモリ領域に配置されると保証されるため、配列型(`T*`など)を要求するレガシーAPIに渡す事ができる。  
  

    * 要素の順次走査ではCPUキャッシュの利用効率が良く、高速な走査を期待できる。（データ局所性が高く、ハードウェア・プリフェッチャ機構と相性が良い）
  

  * 要素の挿入／削除をおこなうと、他要素をさすイテレータが無効化されてしまう。
  * 要素数取得(`size()`)は定数時間（ほぼゼロコスト）で可能。

## `std::list`シーケンスコンテナ

  * いわゆる「双方向連結リスト(doubly-linked list)」コンテナ。
  * 1要素あたりのメモリ使用量のオーバーヘッドが大きい。目安として (`sizeof T`＋ポインタ型2個)×要素数 を利用するため、特に`T`型が小さいときは無駄が大きい。  
  

    * 容量という概念をもたず、常に "×要素数(`size()`)" オーダーのメモリを消費する。
  

  * 先頭要素(`front()`)／末尾要素(`back()`)へは定数時間でアクセスできるが、中間要素へのアクセスは順次走査（線形時間）が必要となる。
  * 任意位置への要素の挿入／削除を定数時間で行える。
  * 要素同士は離れたメモリ位置に配置される。  
  

    * 順次走査であってもCPUキャッシュラインを浪費しがちで、一般に`vector`よりも低速な走査となる。（特に挿入／削除が頻繁に行われた場合、データの局所性が失われている。）
  

  * 要素の挿入／削除をおこなっても、他要素をさすイテレータは無効化されない。
  * 要素数取得(`size()`)には線形時間が必要となる。C++11以降ならば定数時間が仕様上保証されるが、使用するコンパイラやライブラリの対応状況を確認のこと。

