6008


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

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

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


CC BY-SA 3.0
2015-02-05T11:10:35.850
5997
2015-09-26T15:42:13.083
2015-02-06T10:22:08.270
question
c++ アルゴリズム stl
vectorと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`が適している場面は単純に「挿入削除が頻繁に起こる場面」という事になります。


CC BY-SA 3.0
2015-02-05T11:56:42.290
6002
2015-02-05T12:05:20.300
2015-02-05T12:05:20.300
6119
6119
5997
answer


大抵のケースでは `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以降ならば定数時間が仕様上保証されるが、使用するコンパイラやライブラリの対応状況を確認のこと。


CC BY-SA 3.0
2015-02-05T12:56:39.047
6008
2015-02-06T02:50:51.673
2015-02-06T02:50:51.673
49
49
5997
answer


他の方が述べておられる、中間位置への挿入/削除のパフォーマンスの良さに加えて、

  * 要素型のサイズが非常に大きく、コピーが非常に高コストであり、
  * コンテナ間での要素のやりとりが頻繁

といった状況でも、`splice`や`merge`が使えるlistは、有効な選択肢の一つだったのだろうな、と思います。もっとも、C++11以降では、`move`が使えるため、この利点が生きる状況はあまりないかもしれませんが。


CC BY-SA 3.0
2015-02-06T03:06:20.013
6043
2015-02-06T03:06:20.013
7344
5997
answer


`vector`と`list`のほか、`deque`も検討に入れてみてはどうでしょうか。

  * 先頭・終端での挿入・削除が`O(1)`で、中間では`O(N)`です。ただし、実際には要素のサイズが小さくなければ`vector`より速いです。
  * ランダムアクセスは`O(1)`です。ただし、全要素がメモリ上連続ではないので、`vector`よりは多少劣ります。

ちょうどいいデータを[C++ benchmark – std::vector VS std::list VS std::deque |
@Blog("Baptiste Wicht")](http://baptiste-wicht.com/posts/2012/12/cpp-
benchmark-vector-list-deque.html)で見つけました。

  * random_insert (8/32/4096 bytes)では、`deque`が1位または1位とほぼ並ぶ速さ。
  * random_remove (8/32/4096 bytes)も同様。ただし、random_remove 4096 bytesを除く（`list`にそこそこ離されて2位）。


CC BY-SA 3.0
2015-09-26T15:42:13.083
16969
2015-09-26T15:42:13.083
8616
5997
answer