参考: Standard Template Library Programmer's Guide

概要

Standard Template Libraryの略。

コンテナ・イテレータ（反復子）・アルゴリズム・関数オブジェクト と呼ばれる各要素から成っている

コンテナ には、「ベクター」、「リスト」、「キュー」、「スタック」をはじめさまざまな コンポーネントが標準で用意されている。それぞれ一長一短で、用途によって使い分けることができる。 また自分で作成することもできる。

アルゴリズム には「データの追加」、「ソート」、「検索」など約60個有用なアルゴリズムが 用意されている

このようなコンテナとアルゴリズムを組みあわせることにより、自分でデータ格納や データ整理などに関する関数やクラスを作らなくてもよいため、プログラムの部品化が可能で、 再利用性の高いプログラムを作ることができる。

反復子 とは、ポインタのようなもので、コンテナに格納されているデータの場所を示すものです。 コンテナとアルゴリズムとを直接関係づけるのではなく、コンテナとアルゴリズムの間に、イタレーターを はさむことによって、コンテナはアルゴリズムを、アルゴリズムはコンテナを意識せずに使うこと(作ること)が できるのです。

コンテナ機能特徴及びパフォーマンス比較

第1章　STLプログラミングの基礎

1.1　Vectorの基本的な操作の例
1.2　Vector要素の追加と削除： pop_back()とempty()を使用する
1.3　反復子を介してVector要素の巡回： iteratorの最初例
1.4　end()メンバ関数の使用例： end()関数は最後の要素の1つ後を指す反復子を返す
1.5　反復子を使用して削除と挿入： insert()とerase()関数
1.6　Listの基本用例
1.7　Listの結合とマージを行う： Listのmerge()とsplice()関数
1.8　Listの先頭追加と末尾追加： push_back()とpush_front()の違い
1.9　count()アリゴリズム： シーケンスのStartからendまでの範囲にある要素のうち、値がvalである要素の数を返す
1.10　count_if()アリゴリズム： シーケンスのStartからendまでの範囲にある要素のうち、単項述語がtrueを返す要素の数を返す
1.11　remove_copy()とreplace_copy()アリゴリズム： 元のシーケンス内の特定の項目だけを含む新しいシーケンスを作成するまたは特定の要素を別の要素に書き換える
1.12　reverse()アリゴリズム： シーケンスの反転
1.13　transform()アリゴリズム： シーケンスの置換
1.14　アリゴリズムの効力： ListをVectorにコピーする
1.15　単項関数オブジェクトを使用する： negate関数オブジェクトでList内の値の符号を反転する
1.16　二項関数オブジェクトを使用する： divides関数オブジェクト用例

第2章　dequeコンテナ

・ 両端キュー（両頭待ち行列）を実装する
・ 要素をコンテナの先頭と末尾の両方からプッシュできる
・ 要素を中間に挿入削除する事もできる、但し線形時間かかる
・ 一番利点は要素先頭に削除と挿入場合はVectorより速く、線形時間じゃなくて定数時間かかる
・ ランダムアクセスできる

2.1　両端キューの使用例
2.2　push_front()、pop_front()、front()メンバ関数： dequeの先頭と末尾を使用し、dequeを反転しながらコピーする例
2.3　両端キューを回転する
2.4　reverse_iterator逆方向反復子を使用する： rbegin()関数はコンテナの末尾を指す反復子を返す、rend()関数はコンテナの先頭を指す反復子返す
2.5　逆方向反復子を使ったコンテナのコピー：
2.6　コンテナに値を代入する： "="代入とassign()メンバ関数代入
2.7　swap()の使用： ２つのdequeコンテナの要素を交換する
2.8　size()、max_size()、resize()、clear()関数： resize()の使用でコンテナのサイズを変更する
2.9　挿入によって反復子が無効になる例
2.10　クラスオブジェクトをdequeに格納する

第3章　vectorコンテナ

・ 動的な配列をサポートする
・ 最高速ランダム（任意の要素に）アクセス（定数時間で）（他の列コンテナと比べる）
・ 末尾へ高速な削除と挿入できる（定数時間で）
・ 先頭に削除と挿入場合は線形時間かかる。よく先頭に削除と挿入場合はDqueueがいい。
・ (要素中間に削除と挿入場合はvectorよりlistがいい)

3.1　vectorの4つの構築方法
3.2　capacity()メンバ関数： 容量とサイズの違い用例
3.3　reserve(9()メンバ関数： パケットを格納する容量を確保する、reserve()を使って再割当てを回避する例
3.4　vectorは必要なメモリよりも多くのメモリを割り当てる場合がある
3.5　at()関数とoperator[]()関数は位置iにある要素への参照を返す： []とat()の動作の違い例
3.6　clear()関数例： 呼び出し先のコンテナからすべての要素を削除する、コンテナのサイズが0になる
3.7　高速にアクセスできる動的な配列が必要な場合はVectorを使用する。 端に対する挿入と削除が頻に行われる場合はdequeを使用する。 データの集合の平均と標準偏差を計算する用例
3.8　クラスのオブジェクトをvectorに格納する

第4章　listコンテナ

・ 両方向のシーケンスコンテナを提供する
・ 要素をコンテナの中間に追加または削除する回数が多く、要素へのランダムアクセスが必要でない場合はListクラスが有効
・ ランダムアクセス反復子機能がなし（定数時間で追加または削除を実現するため）、ソートのような共通アルゴリズムガ使用できない
・ 要素のどこでも追加と削除が定数時間がかかる。
・ アクセスは線形時間かかる

4.1　merge()の使用例： マージを行うとマージ元のリストは空になる、ソート済のリストだけがマージできる
4.2　ソートされていないリストのマージ： リストがソートされていないと混合は正しく行われない
4.3　降順にマージする
4.4　splice()関数：基本的に「Cut&Paste」と同じである
4.5　sort()関数： リストをソートする
4.6　remove()関数： リストから特定値の要素を削除する
4.7　unique()関数： 連続する重複要素を削除
4.8　reverse()関数： リストを反転する。reverse()を使った回文テスター例
4.9　クラスオブジェクトをlistに格納する： メールアドレスをリストに格納する用例

第5章　コンテナアダプタ

・ コンテナアダプタは反復子をサポートしない
・ queueクラスは一般的な先入先出(FIFO)方式のキューをサポートするキューには要素を一方の端から挿入し、もう一方の端から削除する。それ以外の方法でキューの要素にアクセスする事ができない。
・ priority_queueクラスは、一つの端点だけを持ち、要素間に順序があるキューをサポートする。優先順位付きのキューでは、各要素が優先度に従って並べられる。
・ stackクラスは、後入れ先出(LIFO)方式のスタックをサポートする。

5.1　queueクラスの用例
5.2　キューを回転する
5.3　priority_queueの使用例
5.4　優先順位付きのキューを逆順に並べる用例： 比較関数オプジェクトとしてgreaterが使用される
5.5　priority_queueにクラスオブジェクトを格納する
5.6　簡単なスタックの使用例
5.7　逆ポーランド方式の四則計算機用例

第6章　mapとmultimap

・ 連想コンテナ(associative container)はキーと値を関連付けて格納し、キーから値を取得する手段を提供する
・ mapのキーは重複してはならない
・ multimapのキーは重複してもかまわない
・ mapのfind()、insert ()は対数時間かかる

6.1　mapの簡単な使用例
6.2　反復子を使ってmapを巡回する： mapの要素はキーによって昇順にソートされる
6.3　mapを逆順に巡回する用例
6.4　mapの[]演算子：インデックスではなくキーを指定する
6.5　[]演算子で存在しない要素にアクセスすると、その要素がmapに自動的に挿入される
6.6　[]を使って要素をmapに挿入する例
6.7　mapには重複するキーを格納できない
6.8　mapにクラスオブジェクトを格納する用例
6.9　比較関数オプジェクの指定用例： greaterを使ってmap内のキーを逆順でソードする
6.10　multimapに値を格納する： 同じキーの範囲を見つけるには、upper_bound()、lower_bound()及びequal_range()関数を使用する
6.11　multimapにクラスオブジェクトを格納する用例

第7章　setとmultiset

・ setとmultisetは連想コンテナである、キーと値が別れていない点がmapと違う
・ setクラスは重複しないキーを格納するsetをサポートする。キーは昇順に格納される。

7.1　setの簡単な使用例
7.2　setにクラスオブジェクトを格納する用例： setに格納されるオプジェクトのクラスは、<演算子をオーバーロードし、引数を持たないコンストラクタを提供する必要がある
7.3　multisetにクラスオブジェクトを格納する
7.4　選択形式の質問への回答をmultisetを使って記録する用例

第8章　アルゴリズムの詳細

・ アルゴリズムでは、同時に二つの異なる型のコンテナを使用できる

8.1　copy()を用例： コピー先のコンテナは要素を受取るための十分な大きさが必要である
8.2　swap_ranges()用例： 指定される範囲の要素を別の要素と交換する
8.3　シーケンス検索find()とfind_if()の使用例
8.4　search()の使用例
8.5　mismatch()： 二つのシーケンスが最初に相違する位置が検索される
8.6　sort()： ランダムアクセス反復子(vector,deque等)をサポートするコンテナにのみ適用できる
8.7　partial_sort()： ある範囲の中の要素だけをソートする
8.8　binary_search()： ソート済シーケンスの検索. 対数時間がかかる
8.9　ソート済シーケンスの要素を指す反復子を取得する関数： lower_bound()用例、upper_bound()、equal_range()
8.10　要素の削除と置換： remove()とreplace()の使用例
8.11　特定の範囲から、隣接した同じ値の要素を削除する： unique()の使用例
8.12　シーケンスの変換transform()： 特定の範囲の要素に関数を適用し、結果をシーケンスに格納する
8.13　シーケンスの生成generate()： 既存のシーケンスに依存しないシーケンスを作成する
8.14　シーケンスを左方向回転するrotate()：
8.15　逆方向反復子を使用してシーケンスを右方向に回転する用例：
8.16　シーケンスの要素をランダムに並べ替えるrandom_shuffle()関数使用例：
8.17　2つのシーケンスをマージするmerge()関数用例：
8.18　同一シーケンス内でマージを行うinplace_merge()関数用例：
8.19　集合アルゴリズム関数用例：
二つのソートされた集合の和、差を求める―set_union()、set_difference()。
二つのソートされた集合の一方にだけ含まれる要素を求める―set_symmetric_difference()。
二つのソートされた集合の交差を求める―set_intersection()。
特定のソートされた集合のすべての要素が別の集合に含まれているかどうかを調べる―includes()。
8.20　ソート済リストの任意の順列を作成する： next_permutation()用例、prev_permutation()
8.21　ヒープを構築し、要素を追加と削除を行う： make_heap()、push_heap()、pop_heap()
8.22　最小値と最大値の検索： max_element()、min_element()
8.23　定義される範囲の要素に関数を適用する： for_each()の用例
8.24　独自のアルゴリズムを作成する例

第9章　関数オブジェクト、バインダ、否定回路、および関数アダプタ

・ 関数オブジェクトは述語をアルゴリズムに渡す場合等に関数ポインタの代わりに使用される。
・ 単項関数オブジェクトにはlogical_notと()negate()がある。
・ 二項関数オブジェクトにはplus()、minus()、multiplies()、divides()、modules()、equal_to()、not_equal_to()、greater()、greater_equal()、less()、less_equal()、logical_and()、logical_or()がある。
・ バインダは二項関数オブジェクトの引数の一つに値を結び付ける。バインダにはbind2nd()とbind1st()の二つがある。
・ 否定回路は述語の否定を返す。否定回路にはnot1()とnot2()がある。
・ 関数アダプタを使用すると、関数をバインダとともに使用できる形式に変換することができる。

9.1　logical_not単項関数オブジェクトを使用して、 bool値のvectorの値を反転させる例
9.2　二項関数オプジェクトgreaterを使用して、ベクタを降順にソートする例
9.3　単項関数オブジェクトを作成する用例： 単項関数オブジェクトを使って偶数/奇数を判定する
9.4　テンプレート版の単項関数オブジェクトを作成する用例： テンプレート版の単項関数オブジェクトを使って偶数と奇数を判別する
9.5　逆数を返す単項関数オブジェクトを作成する用例：
9.6　二項関数オブジェクトを作成する用例：
9.7　bind2nd()の使用例： 二項関数オブジェクトの第2の引数に値を結び付けたものを単項関数オプジェクトとして返す。
9.8　単項述語に適用される否定回路not1()の使用例：
9.9　二項述語に適用される否定回路not2()の使用例：
9.10　関数ポインタアダプタptr_fun()の用例：
9.11　マンバ関数ポインタアダプタmem_fun()およびmem_fun1()の用例： ポインタを介してメンバ関数を呼出す
9.12　参照を介してメンバ関数を呼出すmem_fun_ref()関数用例：

第10章　反復子

11.1　挿入反復子insert_iteratorの使用例： 挿入反復子を使って要素をvectorに挿入する
11.2　挿入反復子を使ってvectorをほかのvectorに挿入する
11.3　要素をコンテナの末尾に挿入するback_insert_iteratorクラスの使用例
11.4　要素をコンテナの先頭に挿入するfront_insert_iteratorの使用例
11.5　ストリーム反復子istream_iteratorを使ってさまざまなデータ型を読み取る用例
11.6　copyアルゴリズムを使ってcinからvectorに格納する
11.7　ostream_iteratorを使ってデータをストリームに書き込む
11.8　ostream_iteratorを使用する例： listの内容をcoutにコピーする
11.9　低水準の文字ストリーム反復子： istreambuf_iterator、ostreambuf_iterator、およびreplace_copy()を使ってファイルをフィルタ処理する
11.10　advance()とdistance()の使用例

第11章　アロケータ、カスタムコンテナ、およびその他の高度な話題

11.1　allocatorのmax_size()関数の使用例
11.2　raw_storage_iteratorの使用例
11.3　配列をコンテナとして使用する
11.4　bitsetの使用例
11.5　NP_Arrayの基本的な操作の例
11.6　関連する演算子の使用例
11.7　クラスオブジェクトをNP_Arrayに格納する

　

その他　valarrayクラス

1　valarrayの使用例
2　sliceの使用例
3　gslice()の使用例

その他　数値に対するアルゴリズム

1　accumulate()の使用例
2　adjacent_difference()の使用例
3　inner_product()の使用例
4　partial_sum()の使用例