STL

---

概要

よく利用されるアルゴリズムとデータ構造を実装したクラステンプレートおよび関数テンプレートの集まり。

TOP

---

基本要素

コンテナ(container)

他のオブジェクトを格納するオブジェクト。

アルゴリズム(algorithm)

反復子を用いて、コンテナを操作する。
コンテナ内の要素初期化、ソート、検索、変換などがある。

反復子(iteraitor)

ポインタと似ており、コンテナ内の要素間を移動する。

反復子の種類

種類	可能なアクセス
ランダムアクセス反復子 (random access iterator)	値の設定、取得、及び各要素にランダムアクセス。
双方向反復子 (bidirectional iterator)	値の設定、取得、及び前方後方へ移動。
前方反復子 (forward iterator)	値の設定、取得、及び前方へのみ移動。
入力反復子 (input iterator)	値を設定でき、前方へのみ移動。
出力反復子 (output iterator)	値を設定でき、前方へのみ移動。

TOP

---

標準コンポーネント

アロケータ(allocator)

コンテナのメモリ割り当てを管理する。

関数オブジェクト(function object)

operator()が定義されているクラス。

アダプタ(adapter)

あるオブジェクトを別のオブジェクトに変換する。

TOP

---

コンテナクラス一覧

コンテナ	説明	必要なヘッダ
vector	動的な配列。	#include <vector>
list	線形リスト（双方向リスト）。	#include <list>
set	要素の重複が許されない集合。	#include <set>
multiset	要素の重複が許される集合。	#include <set>
map	キーと値のペアを要素とするコンテナ。一つのキーは一つの値に対応する。	#include <map>
multimap	キーと値のペアを要素とするコンテナ。一つのキーが複数の値に対応する。	#include <map>
queue	キュー。	#include <queue>
priority_queue	優先順位付きキュー。	#include <queue>
deque	両端から操作できるキュー。	#include <deque>
stack	スタック。	#include <stack>

TOP

---

コンテナクラス比較

機能	vector	deque	list	set	multiset	map	multimap
構成	動的配列	両端から操作できるキュー	線形リスト（双方向リスト）	要素の重複が許されない集合（二分木）	要素の重複が許される集合（二分木）	キーと値のペアのコンテナ（二分木）	キーと値のペアのコンテナ（二分木）
要素	値	値	値	値	値	キー・値	キー・値
重複	○	○	○	×	○	キー×・値○	○
ランダムアクセス	○	○	×	×	×	キー○・値×	×
反復子	ランダムアクセス	ランダムアクセス	双方向	双方向/要素は定数	双方向/要素は定数	双方向/キーは定数	双方向/キーは定数
要素の検索	遅い	遅い	非常に遅い	速い	速い	キーは速い	キーは速い
要素の挿入・削除	末尾高速	先頭末尾高速	高速	-	-	-	-
挿入・削除による反復子・参照・ポインタの無効化	再割り当て時	常に	なし	なし	なし	なし	なし
削除された要素のメモリ開放	なし	ときどき	常に	常に	常に	常に	常に
メモリの予約	可	不可	-	-	-	-	-
トランザクションセーフ（成功 or 無効）	末尾のpop()/push()	先頭と末尾のpop()/push()	sort()と代入以外	複数要素の挿入以外	複数要素の挿入以外	複数要素の挿入以外	複数要素の挿入以外

• デフォルトとして、vectorを使用すべきである。

vectorは、内部構造が最も単純でランダムアクセスをサポートしている。したがって、データのアクセスが便利かつ柔軟で、データの処理も十分に速くなる場合が多い。

• シーケンスの先頭や末尾で、要素の挿入 or 削除が多い場合、dequeを使用すべきである。

要素の削除時に、コンテナが内部で使うメモリの量を減らしたい場合にも、dequeを使う。
vectorは、要素に一つのメモリブロックを使うことが多い為、複数のメモリブロックを使うdequeの方がより多くの要素を含む場合が多い。

• コンテナの途中で、要素の挿入・削除・移動が多い場合、listの使用を考慮すべきである。

listには、一定の時間でコンテナから別のコンテナに要素を移動する特別なメンバ関数がある。
但し、listはランダムアクセスを提供しない為、listの先頭だけを認識している時にlistの途中の要素にアクセスする場合、
非常にパフォーマンスが低い。
ノードをベースとする全てのコンテナは、要素がコンテナの一部である限り、要素を参照するlistの反復子が無効になることはない。
vectorでは、要素がコンテナの容量を超過すると、反復子・ポインタ・参照は全て無効になり、挿入や削除によっても、
一部の反復子・ポインタ・参照が無効になる。また、dequeではサイズが変わると、反復子・ポインタ・参照が無効になる。

• 例外処理に関して、個々の演算が成功または効果無しのどちらかになるコンテナが必要な場合、listまたは連想コンテナを使用すべきである。

但し、listでは、代入演算とsort()、及び要素の比較によって、例外が発生する可能性がある場合には、merge()、remove()、remove_if()、unique()を呼び出すことができない。また、連想コンテナでは、複数の要素を挿入する演算、および比較の基準のコピーや代入によって、例外が発生する可能性がある場合には、swap()を呼び出すことはできない。

• 何らかの基準に従って要素を頻繁に検索しなければならない場合、ある基準に従って、要素がソートされるsetまたはmultisetを使うべきである。

1000個の要素をソートする場合、対数的な複雑さであれば、線形の複雑さより論理的には10倍も優れたパフォーマンスを発揮する。これは、二分木の典型的なメリットである。ハッシュテーブルによる参照は、二分木より５～１０倍高速であることが普通である。したがって、ハッシュコンテナが利用可能であれば、標準化されていなくても、ハッシュテーブルの使用を検討すべき場合もある。但し、ハッシュコンテナには順序がない為、要素の順序に依存する用途には適していない。
また、ハッシュコンテナにはC++の標準ライブラリに含まれていない為、移植性を保持するには、ソースコードが必要である。

• キーと値のペアを処理するには、mapやmultimap（または、利用可能であれば、ハッシュマップ）を使う。
• 連想配列が必要であれば、mapを使う。
• 辞書が必要であれば、multimapを使う。

TOP

---

コメント

TOP

---