STLコンテナ

arrayクラスやvectorクラスはSTLコンテナというC++標準で用意されている機能です。
SLTは「Standard Template Library」の略で、C++のテンプレートを利用していろいろなデータ型を格納(コンテナ)できる標準ライブラリという意味になります。
vectorクラスが色々なデータ型を格納できるのもテンプレートを使用しているからです。

ここではSTLコンテナ型について説明します。

コンテナ型の一覧

STLコンテナ型は、大別してシーケンスコンテナ、連想コンテナ、非順序連想コンテナの三種類があります。
すべてstd名前空間に属します。

シーケンスコンテナ

シーケンスコンテナは、要素の順序がプログラマが追加/削除した通りに保たれるコンテナ型です。

シーケンスコンテナ

array
(C++11)
固定長配列
要素数の増減不可
vector
動的配列
末尾要素の追加、削除が高速
deque
両端キュー
先頭および末尾要素の追加、削除が高速
list
双方向リスト
任意の位置への挿入、削除が高速
ランダムアクセス不可
(イテレータに[]や+が使えない)
forward_list
(C++11)
単方向リスト
任意の位置への挿入、削除が高速
ランダムアクセス不可
イテレータの--演算不可
(後方向に戻れない)

これらのクラスの主な違いは要素の追加や削除の速度です。
速度を無視すればすべてvectorクラスで代用することもできます。

連想コンテナ

連想コンテナは、要素の追加/削除のたびに順序が自動的にソート(並べ替え)されるクラスです。

連想コンテナ

set
集合
要素の重複を許可しない
ランダムアクセス不可
multiset
集合
要素の重複を許可する
ランダムアクセス不可
map
連想配列
キーと値のペア
キーの重複を許可しない
multimap
連想配列
キーと値のペア
キーの重複を許可する

これらのコンテナ型は二分探索木という方法で要素の順序付けが行われ、要素の追加や削除、検索が比較的高速に行えるクラスです。
ただしシーケンスコンテナのように「先頭から○番目の要素にアクセス」と言った操作はできません。

なお「ソート」といっても配列の並べ替えのように高コストなものではなく、各要素の順序の情報(アドレス)の更新で、メモリ上の保存位置は変更されないのでほとんどコストはかかりません。

非順序連想コンテナ

非順序連想コンテナ(unordered associative containers)は、要素の追加/削除のたびに順序が自動的にソートされない連想コンテナです。
これらのクラスはすべてC++11から使用できます。

非順序連想コンテナ

unordered_set
ハッシュ
順序に意味を持たない
要素の重複を許可しない
unordered_multiset
ハッシュ
順序に意味を持たない
要素の重複を許可する
unordered_map
連想配列
キーと値のペア
順序に意味を持たない
キーの重複を許可しない
unordered_multimap
連想配列
キーと値のペア
順序に意味を持たない
キーの重複を許可する

これらのクラスは要素の管理にハッシュテーブルという手法を使用していて、要素の挿入/削除、検索を連想コンテナよりもさらに高速に行うことができます。

なお、この機能は他のプログラミング言語ではhashsetやhashmapの名前で提供されていることが多いです。

stringクラス

文字列の格納に使用するstringクラスもコンテナクラスの要件を満たしていますが、扱う対象が文字に限定されるため分けて考えることが多いです。
しかし共通する部分も多く、以下に説明する関数のうちresize関数、emplace関数、emplace_back関数以外を使用することができます。

コンテナクラスに共通の関数

コンテナクラスには共通して使用できる関数が存在します。
関数の詳細についてはそれぞのページで改めて説明します。

全てのコンテナクラスで共通

イテレータ

begin
先頭要素のイテレータを取得
cbegin
先頭要素のconstイテレータを取得
(C++11)
end
末尾要素の次の要素のイテレータを取得
cend
末尾要素の次の要素のconstイテレータを取得
(C++11)

その他

empty
コンテナが空か否かを取得
size
コンテナのサイズを取得
ただしforward_listでは使用できない
max_size
コンテナが確保できる最大容量を取得
swap
コンテナオブジェクト同士の中身を入れ替える

array以外のコンテナクラスで共通

clear
コンテナを空にする
insert
(任意の位置に)要素を挿入
コンテナクラスによっては位置の指定は強制できない
forward_listではinsert_afterという関数を使用する
emplace
(任意の位置に)要素を構築して挿入
コンテナクラスによっては位置の指定は強制できない
forward_listではemplace_afterという関数を使用する
erase
指定の要素を削除する
forward_listではerase_afterという関数を使用する
get_allocator
アロケーターオブジェクトを取得

コンテナアダプタ

コンテナクラスではありませんが、内部にSTLコンテナを使用して機能を提供するクラスをコンテナアダプタといいます。
コンテナアダプタには以下があります。

stack
スタック構造
後入れ先出し
LIFO
(Last In First Out)
queue
キュー構造
先入れ先出し
FIFO
(First In First Out)
priority_queue
優先順位付きキュー
要素に優先順位をつけ、その順位が高い順に取り出す

stackは「積み上げる」と言う意味で、データを上にどんどん重ねるイメージです。
最初に入れたデータを取り出すには、上のデータから順に取り出していかなければなりません。
つまり「後に入れたものから先に取り出す」データ構造です。

queueは「列」の意味で、順番待ちの列の先頭からデータが取り出されるイメージです。
つまり「先に入れたものから先に取り出す」データ構造です。

コンテナアダプタは独自のメンバ関数で操作します。
イテレータはありません。

イテレータが無効化される操作

コンテナクラスはイテレータで操作しますが、要素の挿入や削除の操作によってそれまでに取得していたイテレータおよび参照が無効になることがあります。
読み取りのみを行う操作では無効化されることはありません。

以下は無効になるケースについての一覧です。
(表示スペース節約のためunordered_setなどの「unordered_」の箇所は「u_」と略記しています)

○=有効、×=無効、-=操作なし

コンテナ 条件 挿入 削除 備考
イテレータ  参照  イテレータ  参照 
シーケンスコンテナ
array - - - - - 要素の増減不可
vector 変更した要素の前 ○ ○ ○ ○ 容量が拡張された場合は全て無効
変更した要素とその後ろ × × × ×
deque 先頭/末尾要素の変更 × ○ ○※ ○※ -
途中の要素の変更 × × × ×
list - ○ ○ ○※ ○※ -
forward_list - ○ ○ ○※ ○※ -
連想コンテナ
set - ○ ○ ○※ ○※ -
multiset - ○ ○ ○※ ○※ -
map - ○ ○ ○※ ○※ -
multimap - ○ ○ ○※ ○※ -
非順序連想コンテナ
u_set - ○ ○ ○※ ○※ 再ハッシュが発生した場合イテレータは無効
参照は有効
u_multiset - ○ ○ ○※ ○※
u_map - ○ ○ ○※ ○※
u_multimap - ○ ○ ○※ ○※

※削除された要素自体へのイテレータや参照は無効。

処理速度について

コンテナクラスのオブジェクト(インスタンス)は、基本的な操作として「要素アクセス」「挿入(追加)と削除」「検索」などを行えます。
これらはクラスによって速度が異なったり、特定の操作が不可能だったりします。
ここではデータ構造などの話はできるだけ抑えて、操作とその処理速度について簡単に説明します。

コンテナクラスの基本操作の速度には「要素数に関係なく一定の処理時間がかかるもの」「要素数に正比例して処理時間が増えるもの」「処理毎に対数関数的に残りの処理回数が減るもの」があります。

定数時間

配列は「先頭のアドレス + (インデックス * 要素サイズ)」で任意の位置の要素にアクセスすることができます。
これは配列の要素数がいくつであってもアクセスにかかる時間は変わりません。
これを定数時間といいます。
ちなみに、目的の要素へ直接アクセスすることをランダムアクセスといいます。

定数時間の処理はコンテナの状態に依存せずに常に一定なので高速です。

線形時間

配列内に特定の要素が含まれるか否かを調べる場合、配列の要素数が増えるにつれて処理時間が正比例します。
これを線形時間といいます。

線形時間の処理はコンテナクラスの基本操作の中では低速の部類になります。
数万個程度までのデータであれば十分実用的な範囲ですが、低速な処理を何度も繰り返すような場合は別のコンテナクラスの利用を検討したほうがいいでしょう。

仮に目的とする要素が先頭付近にある場合は検索はすぐに終わりますが、末尾付近にある場合や目的の要素が含まれない場合もあり得ます。
処理時間の計算では最も時間がかかるケース(最悪実行時間)を想定します。
(平均的な処理時間で考えることもあります)

対数時間

例えば要素を検索する時、検索する前に要素をあらかじめ昇順(小さい順)に並べておきます。
検索時には要素をちょうど半分の位置でふたつに分け、その位置の値と目的の値とを比較します。
目的の値のほうが小さければ要素の前半を、大きければ要素の後半を再度検索します。
これを繰り返して目的の値にたどり着きます。
要素数が100ならば「50→25→13→7→4→2→1」の7回の比較で済むので、先頭からひとつずつ検索するよりもはるかに高速です。
このように、処理時間が対数的に増えるものを対数時間といいます。
(要素数の増加によって処理時間は増えるが、緩やなカーブで増加する)
ちなみにこの検索方法は二分探索木というもので、連想コンテナクラスで用いられています。

コンテナクラスの基本の要素操作は上記のいずれかの速度で行えます。
(厳密には異なる場合もありますが)
当サイトでは、定数時間を高速、対数時間を中速、線形時間を低速と表現します。
あくまで速度分類上の表現であって、「低速」の線形時間の処理でもよほど膨大なサイズのコンテナの操作でなければ十分実用レベルな速度です。