C++のSTLのコンテナ一覧とイテレータの説明

C++の色々とあるSTLのコンテナ型とイテレータを勉強がてらまとめます。

vector, list, set, map, deque, arrya, bitset, stackなどについてまとめています。

STLとは

Standard Template Libraryの略で、汎用的かつ型に依存しないデータ構造や処理

Template とは

コンパイル時に有効になるクラスや関数に対するパラメータ

型によらない機能を提供するのが代表的な用法

STLのコンテナ型とは

複数の要素を保持する型。配列のようなイメージ。

コンテナ型の種類

vector

メモリ上に等間隔で要素を並べて保持しているので配列と同じように、アクセスできる（ランダムアクセス）。

メモリの消費も少ない。（変数を格納する領域＋ポインタ変数X2：領域の起点＋領域のサイズ）

ただ、要素の挿入や削除には時間がかかる。

それを解決するのが、list

list

双方向連結リスト。C++11ではfoward_list(一方向連結リスト）もある。（下記図参照）

要素の挿入と削除は速い。

k番目の要素を取得というランダムアクセスが多い場合は、次の要素→次の要素→次の要素というように辿らないといけないため、

アクセスが遅くなる。

メモリ消費は、vectorよりは1要素につきポインタ変数が２つ必要になるので、多い。

（一方向連結リストなら１つ）

set ＆ map　系統

setは、vectorやlistに比べると検索時間が早いコンテナ型。

ユニークな値を格納する（重複しない値）。要素がキーとなり、ある要素が存在するか否かを高速に判定可能。

なお、値は自動で並び替えられる。それが嫌な場合は、unordered_set(C++11)がある。他にも重複した値を入れたいとき用に、multisetがある。

mapは、連想配列ともいう。Pythonだと辞書。キーとバリュー（値）のセット。

setとmapの違いは、前者はキーのみ持つのに対し、後者はキーとバリューを持つこと。

ごちゃごちゃになってきたので表にまとめます。

queue & stack & deque & priority_queue

queueはFIFO(First in First out)の先入れ先出しのデータ構造。ラーメン屋さんの行列のイメージ。

stackはLIFO(Last in First out)の後入れ先出しのデータ構造。積み上げた本を上から取るイメージ。

dequeは、double-ended-queueの略（二重終端キュー）でFIFOとLIFOどちらも対応している。

priority_queueは、入れた要素を大きさ順で取り出せる。

例えば、3, 1, 4とプッシュした場合は、4, 3, 1の順で出てくる。

bitset

固定長のビット配列。01の演算を行う。

array

普通の固定長配列。

ちなみに普通に教科書に載っているいわゆる配列のことを生配列というらしい。

そして、生配列を使うよりはstd::arrayを使う方が良いらしい。

テンプレートなので色々使えるからですかね？

size lengthを知ってどうしたいのか、何をしたいのかという視点から考えると良いかも。

lengthは1つ1つの要素が固定で、それを知ることで、配列の最初から最後までのように使える。

サイズは、領域だし、それを知ることで、領域の確保とかにつながるのでは？

イテレータ

個人的にこれが何なのかよく分からずテキトウに使っていたわけですが…。

「要素の列挙を抽象化したもの」です。

ちょっと分かりにくいですが、vectorとlistを考えると分かりやすいことに気づきました。

例えば、vectorは可変長配列なので、普通の配列のように、array[1]でも任意の要素を得ることができますが（ランダムアクセスOK）、

listは、上述したように、双方向に繋がっておりランダムアクセスに時間がかかるので、任意の箇所のデータを配列のように、list[1]のようには取ることができません。

そんなコンテナ型ごとの特性の違いを吸収して、データへのアクセスを容易にしてくれるものがイテレータです。

配列のインデックスが、上述の様々なコンテナ型で共通で使えるようになったバージョンと考えれば良いのかと思います。

参考文献

C++のSTLのコンテナ型を概観する

とんでもなく分かりやすかったです。ありがとうございます。