STL 索引

〔STL-コンテナ〕

コンテナ共通の項目

コンストラクタ／デストラクタ
コンテナの共通演算
代入とswap()

vector

vector の特徴
vector のコンストラクタ／デストラクタ
vector 代入の演算
= / assign() / swap()
vector 要素のアクセス
at() / [] / front() / back()
vector 反復子の関数
begin() / end() / rbegin() / rend()
vector の挿入と削除
insert() / push_back() / pop_back() / erase() / resize() / clear()

vector<bool>

vector<bool> の特徴
vector<bool> の特別な演算
flip / []

deque

deque の特徴
deque のコンストラクタ／デストラクタ
反復子の位置が保たれる演算 (コンスタントな演算)
size() / empty() / max_size() / == / != / < > / <= / >= / at() / [] / front() / back() / begin() / end() / rbegin() / rend()
反復子が無効になる演算(コンスタントではない演算)
= / assign() / swap() / insert() / push_back() / pop_back() / push_front() / pop_front() / erase() / resize() / clear()

list

list の特徴
list のコンストラクタ／デストラクタ
list の変更を行わない演算
size() / empty() / max_size() / == / != / < / > / <= / >=
list 要素への直接アクセス演算
front() / back()
list 代入の演算
= / assign() / swap()
list 反復子の関数
begin() / end() / rbegin() / rend()
list 挿入と削除の演算
insert() / push_back() / pop_back() / push_front() / pop_front() / remove() / remove_if() / erase() / resize() /clear()
list 変更を行う特別演算
unique() / splice() / sort() / merge() / reverse()

set/multiset

set/multiset の特徴
set/multiset のコンストラクタ／デストラクタ
set/multiset の変更を行わない演算
size() / empty() / max_size() / == / != / < / > / <= / >=
set/multiset 特別な検索の演算
count() / find() / lower_bound() / upper_bound() / equal_range()
set/multiset 代入の演算
= / swap()
set/multiset 反復子の演算
begin() / end() / rbegin() / rend()
set/multiset 要素の挿入と削除
insert() / erase() / clear()

map/multimap

map/multimap の特徴
map/multimap のコンストラクタ／デストラクタ
map/multimap の変更を行わない演算
size() / empty() / max_size() / == / != / < / > / <= / >=
map/multimap 特別な検索の演算
count() / find() / lower_bound() / upper_bound()/ equal_range()
map/multimap 代入の演算
= / swap() / []
map/multimap 反復子の演算
begin() / end() / rbegin() / rend()
map/multimap 要素の挿入と削除
insert() / erase() / clear()
map/multimap 要素の構成に ::value_type/pair/make_pair を利用する

〔STL-反復子〕

反復子の種類

入力反復子
出力反復子
前方反復子
双方向反復子
ランダムアクセス反復子

反復子の補助関数

advance()
distance()
iter_swap()

反復子アダプタ

逆反復子
挿入反復子
back_insert_iterator / front_insert_iterator / insert_iterator

反復子の特性

output_iterator_tag / input_iterator_tag / forward_iterator_tag / bidirectional_iterator_tag / random_access_iterator_tag / iterator_traits<>
反復子に対する自作関数の作成
value_type / iterator_category
反復子自体の自作について(iterator<>)

〔STL-関数オブジェクト〕

事前定義の関数オブジェクト

negate<> / plus<> / minus<> / multiplies<> / divides<> / modulus<> / equal_to<> / not_equal_to<> / less<> / greater<> / less_equal<> / greater_equal<> / logical_not<> / logical_and<> / logical_or<>

関数アダプタ

bind1st() / bind2nd() / not1() / not2()

メンバ関数のための関数アダプタ

mem_fun_ref() / mem_fun()

通常関数のための関数アダプタ

ptr_fun()

関数オブジェクトの自作

unary_function<> / binary_function<>

関数オブジェクトの合成アダプタ

compose_f_gx() / compose_f_gxy() / compose_f_gx_hx() / compose_f_gx_hy()

〔STL-アルゴリズム〕

見出し順

for_each()アルゴリズム
要素のカウント
最小と最大の要素検出
要素の検索
連続する要素の検索
範囲に一致する要素の検索
最終範囲に一致する要素の検索
候補を指定した要素の検索
隣接する要素の検索
等価性のチェック
異なる最初の要素の検索
辞書順位の比較
要素のコピー
要素の変換と結合
要素の交換
単一の値で要素を埋め尽くす
値を生成して要素を埋め尽くす
要素の検索置換
要素のコピーと検索置換
要素の削除
要素のコピーと削除
隣接の重複した要素の削除
コピーと隣接の重複した要素の削除
要素順序の逆転
要素順序の回転
コピーと要素順序の回転
要素順序のステップソート
要素順序のシャッフル
要素全体の二分割
要素全体のソート
要素の部分ソート
要素の部分ソートによる複写
n番目の要素を基準とした要素の二分割
コンテナのヒープソート
予めソートされた区間の要素一つの存在可否
予めソートされた区間の複数要素の存在可否
予めソートされた区間の最初または最後の要素位置の検索
予めソートされた区間の要素範囲の検索
予めソートされた区間の要素範囲の結合
予めソートされた区間の要素範囲の和
予めソートされた区間の要素範囲の交差
予めソートされた区間の要素範囲の差
予めソートされた区間の要素範囲の差(2)
予めソートされた区間の隣接区間結合
コンテナ要素の合計
コンテナ要素同士の内積
コンテナ要素の各部分合計
コンテナ要素の絶対値を相対値へ変換

アルファベット順

accumulate()
adjacent_difference()
adjacent_find()
binary_search()
copy()
copy_backward()
count()
count_if()
equal()
equal_range()
fill()
fill_n()
find()
find_end()
find_first_of()
find_if()
for_each()
generate()
generate_n()
includes()
inner_product()
inplace_merge()
lexicographical_compare()
lower_bound()
make_heap()
max_element()
merge()
min_element()
mismatch()
next_permutation()
nth_element()
partial_sort()
partial_sort_copy()
partial_sum()
partition()
pop_heap()
prev_permutation()
push_heap()
random_shuffle()
remove()
remove_copy()
remove_copy_if()
remove_if()
replace()
replace_copy()
replace_copy_if()
replace_if()
reverse()
reverse_copy()
rotate()
rotate_copy()
search()
search_n()
set_difference()
set_intersection()
set_symmetric_difference()
set_union()
sort()
sort_heap()
stable_partition()
stable_sort()
swap_ranges()
transform()
unique()
unique_copy()
upper_bound()

〔特殊なコンテナ〕

stack

push() / top() / pop()

queue

push() / front() / back() / pop()

priority_queue

push() / top() / pop()

bitset

<例１> enum フラグとして利用
<例２> ２進表記文字列としての bitset
bitset コンストラクタ／デストラクタ
bitset 変更を行わない演算(const)
size() / count() / any() / none() / test() / == / != / []
bitset 変更を行う演算(constではない)
set() / reset() / flip() / ^= / |= / &= / <<= / >>= / []=
変更を加えたbitsetの複製(const)
~ / << / >> / & / | / ^
bitsetの型変換
to_ulong() / to_string() / istream>> / ostream<<

〔文字列クラス〕

テンプレート定義情報

basic_string<>
string/wstring

コンストラクタ／デストラクタ

文字列クラスとCの文字列

data() / c_str() / copy()

サイズと容量

size() / length() / empty() / max_size() / capacity() / reserve()

要素のアクセス

[] / at()

文字列の比較

< > <= >= == != / compare()

文字列の変更

代入
= / assign()
値の交換
swap()
文字列のクリア
="" / clear() / erase()
文字列の挿入と削除
『追加』 - += / append() / push_back()
『挿入』 - insert()
『削除』 - erase()
『置換』 - replace()

文字列の部分処理

substr

入出力演算子

istream>> / ostream<< / getline()

文字列の検索

find() / rfind() / find_first_of() / find_last_of() / find_first_not_of() / find_last_not_of()

文字列の反復子

begin() / end() / rbegin() / rend()

char_traits<>特性テンプレート

〔valarray〕

テンプレート定義情報

コンストラクタ／デストラクタ

配列の一括演算

min() / max() / sum() / shift() / cshift()

超越関数

abs() / pow() / exp() / sqrt() / log() / log10() / sin() / cos() / tan() / sinh() / cosh() / tanh() / asin() / acos() / atan() / atan2()

サブセット

スライス(slice)
多重構造のスライス(gslice)
マスクを利用したサブセット(valarray<bool>)
間接的なサブセット(valarray<size_t>)


STL - ビギナー・ノート

まずは アッサリさっくりと...
この程度覚えとけば、適当なサマになるものを
なにかしら作れるだろう程度の内容です。

下でよく使われている
A～Bの範囲とは、厳密に言うと、
A～(B-1)の範囲です。
巷の文献記号で書くと、[A,B)のことです。

〔UITILITY〕
■typename T::Subtype Value
#インクルードなし（C++標準実装）
  • template<class T>の内部型 Subtype が明瞭でない場合に「これは型名だぞ」と明示させる。
    • ■pair<class T1,class T2> value(const T1 first, const T2 second)
    #include <utility>
    ※ make_pair(first,second)で一つのpairを暗黙的に生成できる。
    • ２つの型にアクセス可能な１つのオブジェクトを生成する。
    • value.first で１番目の要素、value.second で２番目の要素にアクセスできる。
    ■auto_ptr<class T> ptr(new T)
    #include <memory>
    • ptr をスコープ内部で自動変数化したＴのスマートポインタを生成。
    • 個々のメソッドについては、ptr->でアクセスする(もしくは、(*ptr).でアクセス)。
    • ptr.get()で元オブジェクトの取得が出来る。
    ■min/max
    #include <algorithm>
    template <class T, class Compare> T min(const T&a, const T&b), max(const T&a, const T&b)
    template <class T, class Compare> T min(const T&a, const T&b, Compare comp)
    template <class T, class Compare> T max(const T&a, const T&b, Compare comp)
    • 最小／最大値を返す。
    • 使用時は、型の不一致エラーをコンパイルが出す場合などの時に min<long>(a,b) のように、強制的に<型>を明示することもできる。
    • Compare は、関数オブジェクト型。　bool comp(a,b) で a<b の時、真値を返さなければならない。
    ■void swap(T& a, T& b)
    #include <algorithm>
    • a と b を入れ替える
    ■using namespace std::rel_ops
    #include <utility>
    • 上記を宣言すると、そのスコープ内部で全ての未定義比較演算子について、==、<　の演算子さえ定義してやれば、残りの !=、>、<=、>=　は、自動的に定義される。

    ■offsetof()
    #インクルードなし（C++標準実装）
  • 構造体、または、共用体のメンバのオフセット値を表す。
    • 〔STL〕Standard Template Library
    ■vector<T> value
      #include <vector>
    • value.push_back(T) で要素を後方へ追加。
    • value.pop_back() で要素の最後を削除。
    • value.size()は、要素の個数を表す。
    • value.resize(n) でサイズ調整。
    • value[i] で各要素へアクセス。
    ■deque<T> value
    #inclue <deque>
    • value.push_front(T) で要素を前方へ追加。
    • value.push_back(T) で要素を後方へ追加。
    • value.pop_front() で一番最初の要素を削除する。
    • value.pop_back() で一番最後の要素を削除する。
    • value.size() は、要素の個数を返す。
    • value.resize(n) でサイズ調整。
    • value[i] で各要素へアクセスする。
    ■反復子(iterator)
    • ＊演算子 - その位置にある要素を返す。
    • -> 演算子 - 要素メンバへアクセスする。
    • ++ 演算子 -　反復子を次の要素へ進める。
    • -- 演算子 - 反復子を前の要素へ戻す。
    • ==、!= 演算子 - 反復子が同じ位置であるかどうか。
    • = 演算子 - 反復子に代入する。
    • container.begin() - 先頭の反復子を返す。
    • container.end() - 末端の反復子を返す。　末端とは、終端より一つ進めた存在しないオブジェクトを指し示す。 範囲を指定する処理についても、それは同じことを意味する。
    • 反復子にインクルメント演算子を使う場合(++)、++iterator を使った方が、iterator++ を使うより速い。　iterator++ を利用すると、古い要素を参照するオーバーヘッドが生じる。
    • vector、dequeの反復子は、要素の追加、削除、再割り当てが行われると無効になる。

      • <シンプルな一例>
        vector<T> vect;
        for(vector<T>::iterator iter = vect.begin(); iter != vect.end() ; ++iter) {
          ・・・
        }

    ■逆反復子(rbegin()/rend())
    • container.rbegin() - 逆方向の先頭の反復子。
    • container.rend() - 逆方向の末端の反復子。

    ■list<T> value
    #include <list>
    • value.push_back(T)/.push_front(T) で要素追加。
    • value.pop_back()/.pop_front() で要素の削除。
    • ランダムアクセス出来ないので、 list<T>::iterator を利用する。
    • value.empty() で空チェック。
    • value.size() で要素数取得。
    • value.resize(n) で調整可能。
    ■set/multiset<T,比較テンプレート> value
    #include <set>
    • set は、要素の重複を許さないが、 multiset は、要素の重複を許す。
    • insert(T) で項目を追加する。　項目は、比較テンプレートに応じてソートされ挿入される。
    • ランダムアクセスできないので、反復子を利用する。
    • 比較テンプレートは、 bool Compare(const T &a, const T &b) 型の関数オブジェクト。 真値を返せば、aはｂより前に来る。
    ■map/multimap<T1,T2,比較テンプレート> value
    #include <map>
    • キーと値のペアで要素を構成する。
    • insert(make_pair(T1,T2)) で項目を追加する。
    • map は、キーの重複を許さないが、multimap は、キーの重複を許す。
    • ランダムアクセス出来ないので、反復子を利用する。
    • 要素へのアクセスは、iter->first がキー、iter->second が値を表す。
    • 要素への追加は、value[T1] = T2 としても良い。
    〔ALGORITHM〕#include <algorithm>
    ■min_element/max_element ( iteratorA, iteratorB )
    • Ａ～Ｂの範囲で、最小／最大を表す要素の反復子を返す。
    ■sort ( iteratorA, iteratorB 【,func】)
    sort ( iteratorA, iteratorB )
    • Ａ～Ｂの範囲を昇順で並び替える。
      • sort ( iteratorA, iteratorB, func )
    • Ａ～Ｂの範囲を func(T1,T2) の戻り値で判断して並び替える。 T1<T2　のときに真値を返せば、T1　は　T2　より前に来る。
    ■find ( iteratorA, iteratorB, T)
    • A～Ｂの範囲でＴに等しい反復子を返す。
    ■reverse ( iteratorA, iteratorB )
    • Ａ～Ｂの範囲を逆に並び替える。
    ■equal ( iteratorA, iteratorB, iteratorA2 )
    • Ａ～Ｂの範囲をA2から比較して全く等しいものかどうかを真偽で返す。
    ■copy ( iteratorA, iteratorB, iteratorA2 )
    • Ａ～Ｂの範囲をA2へ複写する。
    • A2から指定された反復子には、Ａ～Ｂ分の要素をコピーできるだけの要素が事前に存在しなければならない。
    • A2に要素が存在しない場合は、back_inserter()等の反復子を利用する。
    ■挿入反復子( back_inserter/front_inserter/inserter )
    • 挿入反復子には、（先頭、末尾、指定位置）に応じて３種類の反復子が用意され、代入するとその位置に挿入される。
        • ① back_inserter (  container )
          push_back() により、同順で挿入される。
        ② front_inserter ( container )
          push_front() により、同順で挿入される。
        ③ inserter ( contrainer, iterator )
          insert() により、iterator の位置へ同順で挿入する。
    • 一つ先に進める++演算子は、この３種類の反復子については、全く影響を受けない。
    ■ストリーム反復子(入出力ファイル用) istream_iterator/ostream_iterator
    ・istream_iterator<型名>(入力元)
    ・入力元の始点を表す。 ( e.g. istream_iterator<string>(cin) )
    ・istream_iterator()
    ・入力元の終点を表す。
    ・ostream_iterator<型名>( 出力先, "区切り文字列" )
    ・出力先を表す。　( e.g. ostream_iterator<string>(out,"\n") )
    ■end = remove( iteratorA, iteratorB, T )
    • Ａ～Ｂの範囲中でＴと一致する値を抹消する。
    • 抹消する処理は、要素を切り詰めるだけで、サイズの変更は行われない。 サイズ調整まで完璧に行うには、remove() が返す戻り値の位置まで erase() する必要がある。
      • coll.erase(iteratorB, end)
    • 連想コンテナでは使用できない。
    ■container.erase( iteratorA, iteratorB )
    • Ａ～Ｂまでの範囲の要素を削除する。
      • <例> coll.erase(remove(coll.begin(),coll.end(),value),coll.end())
    ■container.erase(T)
    • Tの値と同じものを削除する。
    ■func for_each( iteratorA, iteratorB, func )
    • Ａ～Ｂの範囲の要素を func(T) する。 ※ T:=各要素
    ■generate_n( iterator, n, op )
    • iteratorの位置から始めて、op() を n 個上書きする。
    ■generate( iteratorA, iteratorB, op )
    • Ａ～Ｂの範囲の要素を、op() でそれぞれ上書きする。
    ■transform( iteratorA, iteratorB, iteratorA2, func )
    • Ａ～Ｂの範囲の要素を func(T) した戻り値で A2 を始点として上書きする。
    • iteratorA2には、十分な要素があらかじめ設けられているか、もしくは、挿入反復子を利用しなければならない。
    ■transform( iteratorA, iteratorB, iteratorA2, iteratorA3, func )
    • Ａ～Ｂの範囲の要素を func( T, T2 ) した戻り値で A3 を始点として上書きする。
    • iteratorA2には、十分な要素があらかじめ設けられていなければならない。
    • iteratorA3には、十分な要素があらかじめ設けられているか、もしくは、挿入反復子を利用しなければならない。
    ■find_if( iteratorA, iteratorB, func )
    • Ａ～Ｂの範囲を func(T) した戻り値が真の場合にその反復子を返す。
    ■less<T>
    • less<T>( V1, V2 ) が V1<V2 なら真値を返す。
    ■greater<T>
    • greater<T>( V1, V2 ) が V1>V2 なら真値を返す。
    ■negate<T>()
    • negate<T>()(V) は、　-V を返す。
    ■multiplies<T>()
    • multiplies<T>()(V1,V2) は、 V1*V2 を返す。
    ■replace_if( iteratorA, iteratorB, compare, newValue )
    • Ａ～Ｂの範囲を compare(T) した結果が真値であれば、 newValue で置き換える
    ■equal_to<T>(V1,V2)
    • V1==V2 なら、真値を返す。
    ■mem_fun_ref(&class::offset)(T)
    • class::offset(T) を実行させる。 ( class T であることが必須条件 )
      • <例> for_each(coll.begin(),coll.end(),mem_fun_ref(&Person::save))
      ※各々の要素は、Personから派生したものでなければならない。


STL マスター・ノート

より詳しい解説ノートです。

基本的な コンテナ／反復子／関数オブジェクト／アルゴリズム に的を
絞って詳しく解説しています。

stack/queue/priority_queue/bitset/string/rope/valarray/complex については、
また後日、STLプロフェッサー・ノートの方で詳しく解説します。

初歩的な説明は全部とっぱらっていますが、
それでもやっぱり見にくいです。

それから、SGI社のSTLについてはcompose辺りの説明が若干違います。

〔ＳＴＬ-コンテナ〕

■コンテナ共通の項目

  • 全てのコンテナクラスは、デフォルトコンストラクタ、コピーコンストラクタ、デストラクタを提供する。　また、要素の範囲を指定して初期化を出来る。

    • ◆コンストラクタによる初期化のサンプル

      １） コンテナの要素から初期化をする

    std::list<int> l ;
    ＜省略＞
    std::vector<float> c( l.begin() , l.end() ) ;

      2) 配列の要素によって初期化する

    int array[] = { 1 , 2 , 3 , 4 , 5 } ;
    ＜省略＞
    std::set<int> c( array, array + sizeof( array ) / sizeof( array[0] ) ) ;

      3) 標準入力を使って初期化する

    std::deque<int> c( ( std::istream_iterator<int>(std::cin) )
     , ( std::istream_iterator<int>() ) );
  • コンテナの共通演算

    • ContType c
             要素を持たない空のコンテナを生成する。
    ContType c1(c2)
             同じ型のコンテナをコピーする。
    ContType c(beg,end)
             コンテナ[beg,end)のすべての要素をコピーして初期化。
    c.~ContType()
             全ての要素を削除してメモリを解放する。
    c.size()
             要素の実際の数を返す。
    c.empty()
             要素が空であるかどうかチェックする。
    c.max_size()
             格納可能な最大要素数を返す。
    c1 == c2
             c1がc2に等しいかどうか。
    c1 != c2
             c1がc2に等しくないかどうか。
    c1 < c2
             c1がc2より小さいかどうか。
    c1 > c2
             c1がc2より大きいかどうか。
    c1 <= c2
             c1がｃ2以下であるかどうか。
    c1 >= c2
             c1がc2以上であるかどうか。
    c1 = c2
             c2要素をｃ１へすべて代入する。
    c1.swap(c2)
             c1とc2のデータを交換する。
    swap(c1,c2)
             c1とc2のデータを交換する。（グローバル）
    c.begin()
             最初の要素を示す反復子を返す。
    c.end()
             最後の要素の次の要素を返す。
    c.rbegin()
             逆の反復処理をする際の、最初の要素を返す。
    c.rend()
             逆の反復処理をする際の、最後の要素の次の要素を返す。
    c.insert(pos,elem)
             elemのコピーを挿入する。(戻り値とposの意味は、異なる。)
    c.erase(beg,end)
             [beg,end)の範囲の要素を全て削除する。
    c.clear()
             全ての要素を削除する。（コンテナを空にする。）
    c.get_allocator()
             コンテナのメモリモデルを返す。
  • 代入とswap()
      • 　コンテナを他のコンテナへコピーする際、各々の要素を複写する度に、ソースコピーの作成とコピー先の各要素の古いオブジェクトの破棄という代償が付いて回る。　コピーした元のオブジェクトが不必要である場合、swap()を利用した方が高速な処理を期待できる。　swap()は、内部処理としてメモリの参照情報等の必要最低限の情報切替のみを行うため、非常に高速である。
┘

■vector

    // vector ： #include <vector>
    namespace std {
    template<class T,class Allocator = allocator<T> >
    class vector ;
    }

  • vector の特徴

    1. 内部に動的な配列を割り当てた一方向順序付コレクションである。
    2. 要素を末尾に追加／削除する処理は高速だが、先頭／中間で要素を追加／削除する処理には向いていない。
    3. ランダムアクセス反復子を利用して任意の要素へ素早くアクセス出来る。
    4. capacity() メソッドにより、現在割り当てられている要素格納限界数を知ることができ、これを超過した場合に要素の再割り当てのトリガーが発生することを意味する。
    5. 頻繁な要素の再割り当てを防ぐために、reserve(n)を要素追加前に呼び出すと、事前にそれだけの要素を格納できるメモリを割り当てることができる。　また、vectorのコンストラクタに数値を指定して呼び出しても、初期再割り当てとして動作はするが、メモリを予約する訳ではなく、要素のデフォルトコンストラクタを指定数回呼び出し初期化し、事前要素を追加する処理の繰り返しになるので要素のコンストラクタの初期化に比例した時間がかかる。　悪影響を考慮した上で設計を考えると、vectorの空オブジェクトを作成した後にreserve(n)を呼び出した方が効率が良い。
    6. vectorは、一度割り当てたメモリを小さくすることが出来ない。　容量を小さくするには、インラインで生成した名前無しvectorのクローンをswapメソッドで切り替えると処理効率よく容量を縮小できる。
      7. std::vector<T>(vec).swap(vec)
    7. 要素は、一方向順序型であるため、push_back()/pop_back()メソッドは存在するが、push_front()/pop_front()メソッドは存在しない。
    8. C++標準仕様としてまだ定められていないが、 vector は、 &v[i] == &v[0]+i という等式が成り立つことを期待できる。　つまり、同一メモリ上に要素が順序通り並んでいることを表している。
  • vector のコンストラクタ／デストラクタ

    • vector<T> c
             要素を持たない空のvectorを生成する。
    vector<T> c1(c2)
             同じ型のvectorのコピーを生成する。
    vector<T> c(n)
             デフォルトコンストラクタを利用して作成されたｎ個の要素を持つvectorを生成する。
    vector<T> c(n,elem)
             elem要素をn個コピーして生成したvectorを生成する。
    vector<T> c(beg,end)
             [beg,end) の範囲で初期化したvectorを生成する。
    c.~vector<T>()
             全ての要素を破棄してメモリを解放する。
  • vector 代入の演算

    • c1 = c2
             c2の要素をc1へ全て代入する。
    c.assign(n,elem)
             elemという要素のn個のコピーを代入する。
    c.assign(beg,end)
             [beg,end) の範囲の要素を代入する。
    c1.swap(c2)
             c1とc2のデータを交換する。
    swap(c1,c2)
             c1とc2のデータを交換する。(グローバル)
  • vector 要素のアクセス

    • c.at(index) //indexは整数
             indexの位置の要素を返す。（範囲例外エラーチェックの機能が付属している）
    c[index]
             indexの位置の要素を返す。（範囲チェック例外は、発生しないようになっている）
    c.front()
             最初の要素を返す。（範囲例外は発生しない）
    c.back()
             最後の要素を返す。（範囲例外は発生しない）
  • vector 反復子の関数

    • c.begin()
             最初の要素のランダムアクセス反復子を返す。
    c.end()
             最後の要素の次の位置を示すランダムアクセス反復子を返す。
    c.rbegin()
             逆の反復処理を行う際の、最初の要素を示す逆反復子を返す。
    c.rend()
             逆の反復処理を行う際の、最後の要素の次の位置を示す逆反復子を返す。
  • vector の挿入と削除

    • c.insert(iter,elem)
             iter反復子が示す位置にelem要素をコピーして挿入し、新しい位置の反復子を返す。
    c.insert(iter,n,elem)
             iter反復子が示す位置にelem要素をn個コピーして挿入し、新しい位置の反復子を返す。
    c.insert(iter,beg,end)
             iter反復子が示す位置に[beg,end)の範囲の要素をコピーする。（返却値なし）
    c.push_back(elem)
             elem要素をコピーして末尾に追加する。
    c.pop_back()
             最後の要素を削除する。（返却値なし）
    c.erase(iter)
             iterが指定した位置の要素を削除し、削除した要素の次の反復子を返す。
    c.erase(beg,end)
             [beg,end)間の要素を削除し、その次の要素の反復子を返す。
    c.resize(num)
             要素数をnumに変更する。（size()が増える場合は、デフォルトコンストラクタで初期化された要素が増えた分だけ挿入される）
    c.resize(num,elem)
             要素数をnumに変更する。（size()が増える場合は、elemのコピーでそれを補う）
    c.clear()
             全ての要素を削除する。（vectorを空にする）
┘

■vector<bool>

    vector<bool> は、ビット論理値に特化した vector の特別バージョンである。
    // vector<bool> ： #include <vector>
    namespace std {
      class vector<bool> {
        public:
    // []演算子のための補助型
    class reference {
      ・・・
      public:
        // boolへの自動的な型変換
        operator bool() const ;
        // 代入
        reference& operator =(const bool);
        reference& operator =(const reference&);
        // ビットの反転（補数）
        void flip();
    }
    ・・・
    // 要素にアクセスするための演算
    // －戻り値の型は bool ではなく reference
    reference operator[] (size_type n);
    reference at(size_type n);
    reference front();
    reference back();
      };
    }
  • vector<bool> の特徴

    1. ビットでbool値を表現するため、普通にvectorのboolを宣言した場合のサイズ的な問題が1/8サイズに縮小されている。
    2. ビット演算に特化したため、referenceという内部スマートクラスで仮想的なboolを実装しているが、要素の絶対アドレスや、ランダムアクセス反復子を利用できなく、インデックスを指定して実効値を操作するという手法をとっている。
  • vector<bool>　の特別な演算

    • c.flip()
             要素全てのbool値を反転する。
    m[index].flip()
             indexで示された位置にある所定のbool要素を反転させる。
    m[index] = val
             indexで示された位置にある所定のbool要素にval値(bool)を代入する。
    m[index1] = m[index2]
             index1で示された位置にある所定のbool要素をindex2で示された位置にある所定のbool要素で置き換える。
┘

■deque

// deque ： #include <deque>
namespace std {
template<class T,class Allocator = allocator<T> >
class deque ;
}
  • deque の特徴

    1. 要素の挿入と削除は、先頭と末尾の両端で高速である。　逆に、コレクションの途中に要素を追加／削除する作業は遅くなる。
    2. dequeの領域は、直線上のベクトル構造に見えるが、内部構造自体は同一メモリ上に配置されていないため、反復子はスマートポインタで構成される。
    3. dequeは、再割り当ての容量調整機能をサポートしていない（capacity/reserveメソッドが無い）　そのため、要素を追加／削除した場合にいつ反復子が無効になるのかは不明である。　追加／削除した後は、反復子をdequeから再取得する必要性が生じる。
    4. dequeはメモリ管理を自動で行う。　そのため、vectorとは違い、不使用ブロックのメモリが解放されて容量が小さくなる場合も考えられる。　メモリ解放を重視する場合は、vectorよりdequeを利用した方が効率が良いということになる。
  • deque のコンストラクタ／デストラクタ

    • deque<T> c
             要素を持たない空のvectorを生成する。
    deque<T> c1(c2)
             同じ型のdequeのコピーを生成する。
    deque<T> c(n)
             デフォルトコンストラクタを利用して生成されたn個の要素を持つdequeを生成する。
    deque<T> c(n,elem)
             elem要素をn個コピーして生成したdequeを生成する。
    deque<T> c(beg,end)
             [beg,end) の範囲で初期化したdequeを生成する。
    c.~deque<T>()
             全ての要素を破棄してメモリを解放する。
  • 反復子の位置が保たれる演算 (コンスタントな演算)

    • c.size()
             要素の実際の数を返す。
    c.empty()
             dequeが空であるかどうかを返す。
    c.max_size()
             格納可能な最大数を返す。
    c1 == c2
             c1がc2に等しいかどうか返す。
    c1 != c2
             c1がc2に等しくないかどうかを返す。
    c1 < c2
             c1がc2より小さいかどうかを返す。
    c1 > c2
             c1がc2より大きいかどうかを返す。
    c1 <= c2
             c1がc2以下かどうかを返す。
    c1 >= c2
             c1がc2以上かどうかを返す。
    c.at(index)
             indexが示す位置の要素を返す。（範囲チェック例外処理機能付）
    c[index]
             indexが示す位置の要素を返す。
    c.front()
             最初の要素を返す。（範囲例外は発生しない）
    c.back()
             最後の要素を返す。（範囲例外は発生しない）
    c.begin()
             最初の要素を示すランダムアクセス反復子を返す。
    c.end()
             最後の要素の次の位置のランダムアクセス反復子を返す。
    c.rbegin()
             逆の反復処理を行う際の、最初の要素を示す逆反復子を返す。
    c.rend()
             逆の反復処理を行う際の、最後の要素を示す逆反復子を返す。
  • 反復子が無効になる演算(コンスタントではない演算)

    • c1 = c2
             c2の要素をc1へ全て代入する。
    c.assign(n,elem)
             elem要素の複製をn個作成したものを代入する。
    c.assign(beg,end)
             [beg,end) の範囲の要素を代入する。
    c1.swap(c2)
             c1とc2の内容を入れ替える。
    swap(c1,c2)
             c1とc2の内容を入れ替える。（グローバル）
    c.insert(iter,elem)
             iter反復子の位置にelem要素の複製を挿入し、新しい位置を返す。
    c.insert(iter,n,elem)
             elem要素の複製をn個作成して、iterの位置に挿入する。（返却値なし）
    c.insert(iter,beg,end)
             iter反復子の位置に[beg,end)範囲の要素の複製を挿入する。（返却値なし）
    c.push_back(elem)
             elem要素のコピーを末尾に挿入する。
    c.pop_back()
             最後の要素を削除する。
    c.push_front(elem)
             elem要素のコピーを先頭に挿入する。
    c.pop_front()
             最初の要素を削除する。
    c.erase(iter)
             iter反復子が示す位置のオブジェクトを削除し、その次の要素の反復子を返す。
    c.erase(beg,end)
             [beg,end)範囲の要素を削除し、次の要素の位置を返す。
    c.resize(num)
             要素数をnumに変更する。（numがsize()より大きい場合は、デフォルトコンストラクタで生成された要素を追加してゆく）
    c.resize(num,elem)
             要素数をnumに変更する。（numがsize()より大きい場合は、elem要素の複製を追加してゆく）
    c.clear()
             全ての要素を抹消する。（dequeを空にする。）
┘

■list

    // list ： #include <list>
    namespace std {
    template<class T,class Allocator = allocator<T> >
    class list ;
    }
  • list の特徴

    1. listは、双方向リンクリストによって要素を管理する。　そのため、listはランダムアクセス([i]/at(i))を提供しない。　インデックスで指定された要素を得るには、リンクのチェーンをインデックス-1回分順に追っていく必要があるデメリットを持ち合わせる。
    2. 要素の追加／削除は、どの位置でも高速に処理できるようになっている。
    3. 要素の挿入／削除／追加が行われても、反復子は無効にならないというメリットを持っている。
  • list のコンストラクタ／デストラクタ

    • list<T> c
             要素を持たない空のlistを生成する。
    list<T> c1(c2)
             同じ型のlistのコピーを生成する。
    list<T> c(n)
             デフォルトコンストラクタを利用して生成されたn個の要素を持つlistを生成する。
    list<T> c(n,elem)
             elem要素をn個コピーして生成したlistを生成する。
    list<T> c(beg,end)
             [beg,end) の範囲で初期化したlistを生成する。
    c.~list<T>()
             全ての要素を破棄してメモリを解放する。
  • list の変更を行わない演算

    • c.size()
             要素の実際の数を返す。
    c.empty()
             コンテナが空であるかどうかを返す。
    c.max_size()
             格納可能な最大数を返す。
    c1 == c2
             c1がc2に等しいかどうか返す。
    c1 != c2
             c1がc2に等しくないかどうかを返す。
    c1 < c2
             c1がc2より小さいかどうかを返す。
    c1 > c2
             c1がc2より大きいかどうかを返す。
    c1 <= c2
             c1がc2以下かどうかを返す。
    c1 >= c2
             c1がc2以上かどうかを返す。
  • list　要素への直接アクセス演算

    • c.front()
             最初の要素を返す。
    c.back()
             最後の要素を返す。
  • list 代入の演算

    • c1 = c2
             c2の要素をc1へ全て代入する。
    c.assign(n,elem)
             elemという要素のn個のコピーを代入する。
    c.assign(beg,end)
             [beg,end) の範囲の要素を代入する。
    c1.swap(c2)
             c1とc2のデータを交換する。
    swap(c1,c2)
             c1とc2のデータを交換する。(グローバル)
  • list 反復子の関数

    • c.begin()
             最初の要素の双方向反復子を返す。
    c.end()
             最後の要素の次の位置を示す双方向反復子を返す。
    c.rbegin()
             逆の反復処理を行う際の、最初の要素を示す逆反復子を返す。
    c.rend()
             逆の反復処理を行う際の、最後の要素の次の位置を示す逆反復子を返す。
  • list 挿入と削除の演算

    • c.insert(iter,elem)
             iter反復子が示す位置にelem要素をコピーして挿入し、新しい位置の反復子を返す。
    c.insert(iter,n,elem)
             iter反復子が示す位置にelem要素をn個コピーして挿入し、新しい位置の反復子を返す。
    c.insert(iter,beg,end)
             iter反復子が示す位置に[beg,end)の範囲の要素をコピーする。（返却値なし）
    c.push_back(elem)
             elem要素をコピーして末尾に追加する。
    c.pop_back()
             最後の要素を削除する。（返却値なし）
    c.push_front(elem)
             elem要素のコピーを先頭に挿入する。
    c.pop_front()
             最初の要素を削除する。（返却値なし）
    c.remove(val)
             val値と一致する全ての要素を削除する。
    c.remove_if(op)
             op(elem)が真である全ての要素を削除する。
    c.erase(iter)
             iterが指定した位置の要素を削除し、削除した要素の次の反復子を返す。
    c.erase(beg,end)
             [beg,end)間の要素を削除し、その次の要素の反復子を返す。
    c.resize(num)
             要素数をnumに変更する。（size()が増える場合は、デフォルトコンストラクタで初期化された要素が増えた分だけ挿入される）
    c.resize(num,elem)
             要素数をnumに変更する。（size()が増える場合は、elemのコピーでそれを補う）
    c.clear()
             全ての要素を削除する。（listを空にする）
  • list 変更を行う特別演算

    • c.unique()
             同じ値を持ち、連続する要素が重複する場合、重複を取り除く。
    c.unique(op)
             連続する要素が重複する場合、op(elem)が真となるものを削除する。
    c1.splice(iter,c2)
             c2の全ての要素を、c1のiter反復子の位置の手前に移す。
    c1.splice(iter,c2,c2iter)
             c2のc2iter位置にある要素をc1のiter反復子の位置の手前に移す。
    c1.splice(iter,c2,c2beg,c2end)
             c2の[c2beg,c2end)という範囲の要素をc1のpos位置の手前に移す。(c1とc2は、同じリストでもよい)
    c.sort()
             全ての要素を<演算子でソートする。
    c.sort(op)
             全ての要素をop(elem1,elem2)でソートする。
    c1.merge(c2)
             要素がソートされている２つのコンテナ(c1とc2)において、c2の全ての要素をc1にマージする。(c1の要素はソートされた状態になる)
    c1.merge(c2,op)
             op(elem1,elem2)という演算基準に従って、要素がソートされている２つのコンテナ(c1とc2)において、c2の全ての要素をc1にマージする。(c1の要素はソートされた状態になる)
    c.reverse()
             全ての要素の順序を逆順にする。
    ┘

■set/multiset

// set/multiset ： #include <set>
namespace std {
template < class T,
class Compare = less<T>,
class Allocator = allocator<T> >
class set ;
template < class T,
class Compare = less<T>,
class Allocator = allocator<T> >
class multiset ;
}
※　Compare(elem1,elem2) に指定される演算の戻り値の必要条件について
  1. Compare(x,y) が真ならば、Compare(y,x) は偽になる。
  2. Compare(x,y) が真かつ、Compare(y,z) が真ならば、Compare(x,z) は真になる。
  3. Compare(x,x) は必ず偽になる。
  • set/multiset の特徴

    1. set/multiset　は、比較準拠関数オブジェクトでソートした平衡二分木として実装される。　setは、要素の重複を許さない一方で multisetは、要素の重複を許す。
    2. 要素は、予めソート済の二分木で搭載されているため、値を指定した要素位置の探索が非常に高速である。
    3. 登録した要素の値を変更する行為は、ソート準拠に反するためサポートされない。
    4. 要素の順序は、不定形であるため、要素を直接アクセスするメソッドは利用できない。
    • set/multiset のコンストラクタ／デストラクタ

      • set<T[,comp]> c
               要素を持たない空のset/multisetを生成する。
      set<T[,comp]> c(op)
               ソート基準としてop()を用いるset/multisetを生成する。
      set<T[,comp]> c1(c2)
               同じ型のset/multisetのコピーを生成する。
      set<T[,comp]> c(beg,end)
               [beg,end) の範囲で初期化したset/multisetを生成する。
      set<T[,comp]> c(beg,end,op)
               ソート基準としてop()を用い、[beg,end) の範囲で初期化したset/multisetを生成する。
      c.~set<T[,comp]>()
               全ての要素を破棄してメモリを解放する。
      ※ op は、主にスマート関数オブジェクトなど、ソート準拠を事前に特化して多様化する場合に利用すると便利。
    • set/multiset の変更を行わない演算

      • c.size()
               要素の実際の数を返す。
      c.empty()
               コンテナが空であるかどうかを返す。
      c.max_size()
               格納可能な最大数を返す。
      c1 == c2
               c1がc2に等しいかどうか返す。
      c1 != c2
               c1がc2に等しくないかどうかを返す。
      c1 < c2
               c1がc2より小さいかどうかを返す。
      c1 > c2
               c1がc2より大きいかどうかを返す。
      c1 <= c2
               c1がc2以下かどうかを返す。
      c1 >= c2
               c1がc2以上かどうかを返す。
    • set/multiset 特別な検索の演算

      • c.count(elem)
               elemという要素の登録個数を返す。
      c.find(elem)
               elemという要素に一致する最初の要素の反復子、または、end()反復子を返す。
      c.lower_bound(elem)
               elem を挿入できる最初の反復子を返す。(elem以上の最初の反復子)
      c.upper_bound(elem)
               elem を挿入できる最後の反復子を返す。(elemより大きい最初の要素の反復子)
      c.equal_range(elem)
               elem を挿入できる最初と最後の反復子をpair構造体で返す。（elemと等しい要素の範囲）
    • set/multiset 代入の演算

      • c1 = c2
               c2の要素をc1へ全て代入する。
      c1.swap(c2)
               c1とc2のデータを交換する。
      swap(c1,c2)
               c1とc2のデータを交換する。(グローバル)
    • set/multiset 反復子の演算

      • c.begin()
               最初の要素の双方向反復子を返す。（要素は、constとみなされる）
      c.end()
               最後の要素の次の位置を示す双方向反復子を返す。（要素は、constとみなされる）
      c.rbegin()
               逆の反復処理を行う際の、最初の要素を示す逆反復子を返す。（要素は、constとみなされる）
      c.rend()
               逆の反復処理を行う際の、最後の要素の次の位置を示す逆反復子を返す。（要素は、constとみなされる）
    • set/multiset 要素の挿入と削除

      • [set] pair<iter,bool> c.insert(elem)
      [multiset] iter c.insert(elem)
               elemのコピーを挿入し、新しい要素の位置を返す。 setの場合は、挿入に成功したかどうかも戻り値に返す。
      c.insert(iter,elem)
               iter反復子が示す位置にelem要素をコピーして挿入し、新しい位置の反復子を返す。（iterは、挿入するときのヒントとして利用される）
      c.insert(beg,end)
               [beg,end)の範囲の要素コピーを挿入する。（返却値なし）
      c.erase(elem)
               elem要素と一致する値持つ要素を全て削除して、戻り値として削除した総個数を返す。
      c.erase(iter)
               iterが指定した位置の要素を削除し、削除した要素の次の反復子を返す。
      c.erase(beg,end)
               [beg,end)間の要素を削除し、その次の要素の反復子を返す。
      c.clear()
               全ての要素を削除する。（コンテナを空にする）
        ┘

    ■map/multimap

    // map/multimap ： #include <map>
    namespace std {
    template < class Key, class T,
    class Compare = less<Key>,
    class Allocator = allocator<pair<const Key,T> > >
    class map ;
    template < class Key, class T,
    class Compare = less<Key>,
    class Allocator = allocator<pair<const Key,T> > >
    class multimap ;
    }
    ※　Compare(elem1,elem2) に指定される演算の戻り値の必要条件について
    1. Compare(x,y) が真ならば、Compare(y,x) は偽になる。
    2. Compare(x,y) が真かつ、Compare(y,z) が真ならば、Compare(x,z) は真になる。
    3. Compare(x,x) は必ず偽になる。
  • map/multimap の特徴

    1. map/multimap は、キーを比較準拠関数オブジェクトでソートした平衡二分木として実装される。　各々の要素は、キーと値のペアで組み合わせられる。 mapは、キーの重複を許さない一方で multimapは、キーの重複を許す。
    2. 登録したキーの値を変更する行為は、ソート準拠に反するためサポートされない。（値は変更可能）
    3. 要素の順序は、不定形であるため、要素自体を直接アクセスするメソッドは利用できない。　一方で　c[key] = value のようにキーをターゲットに値を直接変更することが出来る。
    • map/multimap のコンストラクタ／デストラクタ

      • map<Key,T[,comp]> c
               要素を持たない空のmap/multimapを生成する。
      map<Key,T[,comp]> c(op)
               ソート基準としてop()を用いるmap/multimapを生成する。
      map<Key,T[,comp]> c1(c2)
               同じ型のmap/multimapのコピーを生成する。
      map<Key,T[,comp]> c(beg,end)
               [beg,end) の範囲で初期化したmap/multimapを生成する。
      map<Key,T[,comp]> c(beg,end,op)
               ソート基準としてop()を用い、[beg,end) の範囲で初期化したmap/multimapを生成する。
      c.~map<Key,T[,comp]>()
               全ての要素を破棄してメモリを解放する。
      ※ op は、主にスマート関数オブジェクトなど、ソート準拠を事前に特化して多様化する場合に利用すると便利。
    • map/multimap の変更を行わない演算

      • c.size()
               要素の実際の数を返す。
      c.empty()
               コンテナが空であるかどうかを返す。
      c.max_size()
               格納可能な最大数を返す。
      c1 == c2
               c1がc2に等しいかどうか返す。
      c1 != c2
               c1がc2に等しくないかどうかを返す。
      c1 < c2
               c1がc2より小さいかどうかを返す。
      c1 > c2
               c1がc2より大きいかどうかを返す。
      c1 <= c2
               c1がc2以下かどうかを返す。
      c1 >= c2
               c1がc2以上かどうかを返す。
    • map/multimap 特別な検索の演算

      • c.count(key)
               key というキーを持つ要素の登録個数を返す。
      c.find(key)
               key というキーを持つ要素に一致する最初の要素の反復子、または、end()反復子を返す。
      c.lower_bound(key)
               key というキーを持つ要素 を挿入できる最初の反復子を返す。(elem以上の最初の反復子)
      c.upper_bound(key)
               key というキーを持つ要素を挿入できる最後の反復子を返す。(elemより大きい最初の要素の反復子)
      c.equal_range(key)
               key というキーを持つ要素を挿入できる最初と最後の反復子をpair構造体で返す。（elemと等しい要素の範囲）
    • map/multimap 代入の演算

      • c1 = c2
               c2の要素をc1へ全て代入する。
      c1.swap(c2)
               c1とc2のデータを交換する。
      swap(c1,c2)
               c1とc2のデータを交換する。(グローバル)
      c[key] = value
               c[key]は、キーという要素の値を返す。　該当する要素が無い場合は、キーをkeyとする要素を作成して新規に挿入される。
      =演算子を利用すれば、その値に直接代入できる。
    • map/multimap 反復子の演算

      • c.begin()
               最初の要素の双方向反復子を返す。（キーは、constとみなされる）
      c.end()
               最後の要素の次の位置を示す双方向反復子を返す。（キーは、constとみなされる）
      c.rbegin()
               逆の反復処理を行う際の、最初の要素を示す逆反復子を返す。（要素は、constとみなされる）
      c.rend()
               逆の反復処理を行う際の、最後の要素の次の位置を示す逆反復子を返す。（要素は、constとみなされる）
    • map/multimap 要素の挿入と削除

      • [map] pair<iter,bool> c.insert(elem)
      [multimap] iter c.insert(elem)
               elemのコピーを挿入し、新しい要素の位置を返す。 setの場合は、挿入に成功したかどうかも戻り値に返す。
      c.insert(iter,elem)
               iter反復子が示す位置にelem要素をコピーして挿入し、新しい位置の反復子を返す。（iterは、挿入するときのヒントとして利用される）
      c.insert(beg,end)
               [beg,end)の範囲の要素コピーを挿入する。（返却値なし）
      c.erase(elem)
               elem要素と一致する値持つ要素を全て削除して、戻り値として削除した総個数を返す。
      c.erase(iter)
               iterが指定した位置の要素を削除し、削除した要素の次の反復子を返す。
      c.erase(beg,end)
               [beg,end)間の要素を削除し、その次の要素の反復子を返す。
      c.clear()
               全ての要素を削除する。（コンテナを空にする）
    • map/multimap 要素の構成に ::value_type/pair/make_pair を利用する

      • map/multimapは、キーと値をペアにしているため、要素の型を扱いにくい。

      ◆暗黙的な型変換を避け、正確な型を扱うには、：：value_type タイプ指定子を利用すると良い。

      std::map<std::string,double> float_data ;
      float_data.insert(std::map<std::string,double>::value_type("PI",3.14)) ;
      ◆また、pair<>を使うことも出来る。
      float_data.insert(std::pair<std::string,double>("PI",3.14)) ;
      ※ 上記は、結果的に暗黙的な型変換が一回行われる。 型変換を防止するには、constとしてstringを事前に扱っておく必要性が生じる。
      float_data.insert(std::pair<const std::string,double>("PI",3.14)) ;
      ◆暗黙的な型変換に任せて要素を扱うなら、単にmake_paiｒ（）を利用すればよい。
      float_data.insert(make_pair("PI",3.14)) ;

        ┘
    〔STL-反復子〕

    ■反復子の種類

      反復子の機能
入力反復子 | 前方に向かって読み取る。 | 入力ストリーム
出力反復子 | 前方に向かって書き込む。 | 出力ストリーム、挿入反復子
前方反復子 | 前方に向かって読み書きする。 |
双方向反復子 | 前方・後方に向かって読み書きする | list set multiset map multimap
ランダムアクセス反復子 | ランダムアクセスによって読み書きする | vector deque 文字列 配列
    .

    ◆入力反復子

      入力反復子は、要素を読み取りながら進む反復子で、読み進める度にデータを外部インターフェイスなどの入力装置から拾ってくる目的で実装される。 この反復子の特徴は、データを読み進めることしかできずに全く書き込めない所にある。　また、一度読み取ったデータを再度読み取ることは出来ない。
    入力反復子の演算
    *iter
             実際の要素に対して読み取りアクセスを提供する。
    iter->member
             要素のメンバにアクセスする。
    ++iter
             １ステップ前進する。（新しい位置を返す）
    iter++
             １ステップ前進する。（前の位置を返す）
    iter1 == iter2
             ２つの反復子が同じ位置かどうか。
    iter1 != iter2
             ２つの反復子の位置が異なっているかどうか。
    TYPE(iter)
             反復子をコピーする。（コピーコンストラクタ）
      この反復子は、種類によっては、データを読み込む(*iterでアクセスする)と、反復子は自動で次の要素を指し示すことがある。
    .

    ◆出力反復子

      出力反復子は、要素を書き込みながら進む反復子で、書き進める度にデータを外部インターフェイスなどの出力装置に排出する目的で実装される。　この反復子の特徴は、出力先の終端を確かめるすべがなく、書き込み専用であるため要素を比較するための演算子が存在しない所にある。 また、一度書き込んだデータは戻って上書きすることができない。
    出力反復子の演算
    *iter = value
             反復子の参照先にvalue要素を書き込む。
    ++iter
             １ステップ前進する。（新しい位置を返す）
    iter++
             １ステップ前進する。（前の位置を返す）
    TYPE(iter)
             反復子をコピーする。（コピーコンストラクタ）
      この反復子は、データが正常に書き込めたかどうかを確かめるすべを持たない。　また、データを書き込むと、反復子は自動で次の要素を指し示す。
    .

    ◆前方反復子

    前方反復子は、入力反復子と出力反復子の両方の機能を持ち合わせる反復子である。　入力反復子や出力反復子とは違い、同じ要素のデータを巻き戻して何度も参照することが出来る。
      前方反復子の演算
      *iter
               実際の要素にアクセスする。
      iter->member
               実際の要素のメンバーにアクセスする。
      ++iter
               １ステップ前進する。（新しい位置を返す）
      iter++
               １ステップ前進する。（前の位置を返す）
      iter1 == iter2
               ２つの反復子の位置が等しいかどうか返す。
      iter1 != iter2
               ２つの反復子の位置が異なっているかどうか返す。
      TYPE()
               反復子を生成する。（デフォルトコンストラクタ）
      TYPE(iter)
               反復子をコピーする。（コピーコンストラクタ）
      iter1 = iter2
               反復子を代入する。
    .

      ◆双方向反復子

        双方向反復子は、前方反復子に逆方向の反復処理をする機能を追加した反復子である。
      前方反復子に追加される双方向反復子の演算
      --iter
               １ステップ後退する。（新しい位置を返す）
      iter--
               １ステップ後退する。（前の位置を返す）
    .

    ◆ランダムアクセス反復子

      ランダムアクセス反復子は、双方向反復子にランダムアクセス機能を追加したものである。　したがって、反復子のオフセットを考慮に入れた計算や比較が可能となる。
    双方向反復子に追加されるランダムアクセス反復子の演算
    iter[i]
             インデックスが i である要素にアクセスする。
    iter += n
             要素 n 個分だけ前進する。（nが負であれば後退する）
    iter -= n
             要素 n 個分だけ後退する。（nが正であれば前進する）
    n + iter
             n 個先の要素を示す反復子を返す。
    iter - n
             n 個前の要素を示す反復子を返す。
    iter1 - iter2
             iter1 と iter2 の差を返す。
    iter1 < iter2
             iter1 が iter2 より前にあるかどうかを返す。
    iter1 > iter2
             iter1 が iter2 より後にあるかどうかを返す。
    iter1 <= iter2
             iter1 が iter2 と同じ位置か前にあるかどうかを返す。
    iter1 >= iter2
             iter1 が iter2 と同じ位置か後にあるかどうかを返す。

      ┘

    ■反復子の補助関数

    ◆advance()による反復子の移動操作

    // advance() ： #include <iterator>
    namespace std {
    void advance( InputIterator& pos, Dist n ) ;
    }
      advance() 関数は、pos で指定された反復子の位置を n だけインクリメントさせる。　反復子が双方向モードをサポートしている場合、n は負でも構わない。　また、 advance() 関数は、ランダムアクセス反復子だけでなく、 ++演算子をサポートする全ての反復子で利用することができる。
    .

    ◆distance()による反復子の差の計算

    // distance() ： #include <iterator>
    namespace std {
    Dist distance( InputIterator pos1, InputIterator pos2 ) ;
    }
      distance() 関数は、２つの反復子の差を返す。　この関数の使用時は、次の鉄則に従わなければならない。
    • どちらの反復子も同じ要素を参照していなければならない。
    • ランダム反復子以外の場合は、pos１ が　pos2 へ到達可能でなければならない。
    .

    ◆iter_swap()による反復子の値の交換

    // iter_swap() ： #include <algorithm>
    namespace std {
    void iter_swap( InputIterator pos1, InputIterator pos2 ) ;
    }
      iter_swap() 関数は、２つの反復子が指し示している『要素』を入れ替える。　要素の型は、代入が可能であれば一致していなくても構わない。
      ┘

    ■反復子アダプタ

    ◆逆反復子

      逆反復子とは、通常の反復子のインクリメント／デクリメントの演算を逆転して再定義したアダプタである。　逆反復子を得るには、各々のコンテナにある rbegin()/rend() メソッドを呼んで取得する。
    • rbegin() - 逆の順序で反復処理を行う最初の要素の位置を示す反復子を返す。
    • rend() - 逆の順序で反復処理を行う最後の要素の次の位置を示す反復子を返す。
      また、通常の反復子を逆反復子に変換する場合は、reverse_iterator タイプ指定子を利用する。
    container<T>::reverse_iterator rpos( pos ) ;
      この変換を行った場合、rpos反復子の位置は、pos-1の位置に無条件に還元される。　これは、半開きの区間を反転するために起こるものと解釈される。　つまり、begin() は rend()、 end() は rbegin() に還元されるために起こる。
      また、逆反復子を通常の反復子に戻すには、逆反復子付属のメソッドbase()を呼べばよい。
    pos = rpos.base() ;
      この反復子の位置もまた posは、rpos-1の位置に還元される。
    .

    ◆挿入反復子

      この反復子の特徴は、値の代入をトリガーに挿入ポイントをインクリメントするところにある。　この反復子に++演算子を利用するとその処理は、完全に無視される特性も持ち合わせる。
      挿入反復子の演算
      *iter
               単にiterそのものを返す。
      iter = value
               iter に value を挿入する。
      ++iter
               単に iter を返す。
      iter++
               単に iter を返す。
      挿入反復子の種類
      挿入反復子
      クラス
      呼び出される関数
      反復子を生成する関数
      末尾挿入反復子
      back_insert_iterator

      push_back(value)

      back_inserter(cont)
      先頭挿入反復子
      front_insert_iteratror

      push_front(value)

      front_inserter(cont)
      汎用挿入反復子
      insert_iterator

      insert(pos,value)

      inserter(cont,pos)
      ┘

    ■反復子の特性

      反復子は、その特性を種別するために各々のタグを提供している。　この型指定子は、iterator_traits の iterator_category として利用される。
    // XXXXX_iterator_tag ： #include <iterator>
    namespace std {
    struct output_iterator_tag {
    };
    struct input_iterator_tag {
    };
    struct forward_iterator_tag
    : public input_iterator_tag {
    };
    struct bidirectional_iterator_tag
    : public forward_iterator_tag {
    };
    struct random_accesss_iterator_tag
    : public bidirectional_iterator_tag {
    };
    }
        反復子は、その特性を定義するために特別なテンプレートを用意する。
      // iterator_traits<> ： #include <iterator>
      namespace std {
      template <class T>
      struct iterator_traits {
      typedef typename T::value_type value_type ;
      typedef typename T::difference_type difference_type ;
      typedef typename T::iterator_category iterator_category ;
      typedef typename T::pointer pointer ;
      typedef typename T::refernce reference ;
      } ;
      template <class T>
      struct iterator_tarits<T*> {
      typedef T value_type ;
      typedef ptrdiff_t difference_type ;
      typedef random_access_iterator_tag iterator_category ;
      typedef T* pointer ;
      typedef T& reference ;
      } ;
      }
    .

      ◆反復子に対する自作関数の作成

        反復子の要素の型を判別して処理を行うには、value_type を利用する。
      template <class ForwardIterator>
      void SampleFunc(ForwardIterator beg, ForwardIterator end)
      {
      typedef typename
      iterator_traits<ForwardIterator>::value_type value_type ;
      if(beg != end) {
      value_type tmp(*beg) ;
      ・・・
      }
      }
      反復子の iterator_category() を利用すると　反復子の種類による場合分け処理を行うことが出来る。
    template <class Iterator>
    //双方向反復子用
    template <class BiIterator>
    void MultiFunc(BiIterator beg, BiIterator end
    ,std::bidirectional_iterator_tag)
    {
      ・・・
    }
    //ランダムアクセス反復子用
    template <class RaIterator>
    void MultiFunc(RaIterator beg, RaIterator end
    ,std::random_access_iterator_tag)
    {
      ・・・
    }
    //自動判別（本体）
    template <class Iterator>
    void MultiFunc(Iterator beg, Iterator end)
    {
    MultiFunc(beg,end
    ,iterator_traits<Iterator>::iterator_category()) ;
    }
    .

      ◆反復子自体の自作について

        反復子自体を自作するには、 iterator<> 構造体を継承して利用すると都合が良い。
      // iterator<> ： #include <iterator>
      namespace std {
        template < class Category, class T,
    class Distance = ptrdiff_t ,
    class Pointer = T* ,
    class Reference = T& >
  struct iterator
  {
    typedef T value_type;
    typedef Distance difference_type;
    typedef Pointer pointer;
    typedef Reference reference;
    typedef Category iterator_category;
  };
      }
      この構造体を継承することによって、反復子に必要な iterator_traits　定義に関する型情報をオリジナルなものにアレンジ出来る仕組みになっている。
    //継承例
    template <class Container>
    class MyIterator
    : public std::iterator < std::output_iterator_tag,
    void, void, void, void > {
    protected:
    Container& container ;
    public:
    explict MyIterator(Container c) : container(c) {
    ・・・
    }
    MyIterator<Container>&
    operator = (const typename Container::value_type& value) {
    container.insert(value);
    return *this ;
    }
    MyIterator<Container>& operator* () {
    return *this ;
    }
    MyIterator<Container>& operator++ () {　// ++p
    return *this ;
    }
    MyIterator<Container>& operator++ (int) { // p++
    return *this ;
    }
    }
      ┘
    〔STL-関数オブジェクト〕

    ■事前定義の関数オブジェクト

      STLには、数多くの事前定義関数オブジェクトをサポートしている。　これらは、要素同士をパラーメータに受け渡す演算で利用される。　関数オブジェクトは、スマートオブジェクトであるため、コンストラクタ()が付加している。　これらのオブジェクトは、ヘッダファイル <functional> で定義されている。
    事前定義の関数オブジェクト
    negate<type>()(param)

    - param

    plus<type>()(param1,param2)

    param1 + param2

    minus<type>()(param1,param2)

    param1 - param2

    multiplies<type>()(param1,param2)

    param1 * param2

    divides<type>()(param1,param2)

    param1 / param2

    modulus<type>()(param1,param2)

    param1 % param2

    equal_to<type>()(param1,param2)

    param1 == param2

    not_equal_to<type>()(param1,param2)

    param1 != param2

    less<type>()(param1,param2)

    param1 < param2

    greater<type>()(param1,param2)

    param1 > param2

    less_equal<type>()(param1,param2)

    param1 <= param2

    greater_equal<type>()(param1,param2)

    param1 >= param2

    logical_not<type>()(param1,param2)

    ! param

    logical_and<type>()(param1,param2)

    param1 && param2

    logical_or<type>()(param1,param2)

    param1 || param2
      ┘

    ■関数アダプタ

      関数アダプタは、関数オブジェクト　と　関数オブジェクト／値　を組み合わせて作る変換用のファンクタである。　これらのオブジェクトは、ヘッダファイル <functional> で定義されている。
    事前定義の関数アダプタ
    bind1st(op,value)(param)

    op(value,param)

    bind2nd(op,value)(param)

    op(param,value)

    not1(op)(param)

    !op(param)

    not2(op)(param1,param2)

    !op(param1,param2)
      ┘

    ■メンバ関数のための関数アダプタ

        パラメタのクラスメンバを呼び出したい場合には、下記の２つの関数アダプタを利用する。
    メンバ関数のための関数アダプタ
    mem_fun_ref(op)(param[,value])
             op() を paramのオブジェクトメンバ関数として呼び出す。
    要するに、param.op( [value] ) を実行する。
    mem_fun(op)(param[,value])
             op() を (*param)のオブジェクトメンバ関数として呼び出す。
    要するに、param->op( [value] ) を実行する。

    op には、下記のようにパラメータを渡す。

    for_each( coll.begin(), coll.end(), mem_fun_ref(&Class::Method) )
    for_each( coll.begin(), coll.end(), mem_fun(&Class::Method) )
    for_each( coll.begin(), coll.end() // value オプションをバインドする例
    , bind2nd(mem_fun_ref(&Class::Method),value) )
    ※ coll の要素は、　Class から派生したものであることが条件。
      ┘

    ■通常関数のための関数アダプタ

        通常の関数は、関数オブジェクトと違い、関数アダプタに合致した型情報を持っていない。　関数アダプタの型として渡す場合に問題が生じる。　このような通常の関数を関数オブジェクト化するための機能が ptr_fun である。
    メンバ関数のための関数アダプタ
    ptr_fun(op)(param[, param2])
             (*op)( param[ , param2] ) を実行する。

    op には、下記のようにパラメータを渡す。

    find_if( coll.begin(), coll.end(), not1(bind2nd(ptr_fun(strcmp),"名前")) )
     // 上記は、 coll の要素が char*型 であり、"名前"と一致する反復子を返す場合の例
      ┘

    ■関数オブジェクトの自作

      関数アダプタに合致した関数オブジェクトを自作するには、 ヘッダファイル functional に定義されている unuary_function／binary_funciton の型定義情報を派生して利用する。
    // unuary_function / binary_function : #include <functional>
    template <class Arg,class Result>
    struct unary_function {
    typedef Arg argument_type ;
    typedef Result result_type ;
    } ;
    template <class Arg1,class Arg2,class Result>
    struct binary_function {
    typedef Arg1 first_argument_type ;
    typedef Arg2 second_argument_type ;
    typedef Result result_type ;
    } ;

      上記の型定義情報を作成して自作関数オブジェクトを作成すると、関数アダプタに渡しても問題のないオブジェクトを作成できる。
    #include <functional>
    template <class T>
    struct multiplies_n : public std::binary_function<T,int,T>
    {
    T operator() (T value, int n) const {
    T result = T(1) ;
    while(n--) {
    result *= value ;
    }
    return result ;
    }
    }

      ┘

    ■関数オブジェクトの合成アダプタ

      STLは、通常の関数アダプタの他、関数オブジェクト同士を合成するアダプタも提供する。
    関数オブジェクトを合成するアダプタ
    compose_f_gx(f,g)(elem)

    f(g(elem)) に展開する。

    compose_f_gxy(f,g)(elem1,elem2)

    f(g(elem1,elem2))　に展開する。

    compose_f_gx_hx(f,g,h)(elem)

    f(g(elem),h(elem)) に展開する。

    compose_f_gx_hy(f,g,h)(elem1,elem2)

    f(g(elem1),h(elem2)) に展開する。
    ┘
    〔STL-アルゴリズム〕

    #include <algorithm>

    ■for_each()アルゴリズム

    UnaryProc
    for_each (InputIterator beg, InputIterator end, UnaryProc op)
  • [beg,end) という範囲の各要素について、op(elem) を実行する。
  • 内部で変更された op のコピーの返す。
  • op に &演算子で要素の引数を指定した場合、op は要素を変更できる。
  • op の戻り値は無視される。
    • ┘

    ■要素のカウント

    difference_type
      count (InputIterator beg, InputIterator end, const T& value)
      count_if (InputIterator beg, InputIterator end, UnaryPredicate op)
    • count() は、value に等しい要素の総数を返す。
    • count_if() は、op(elem) が true を返す要素の総数を返す。
    • op は、呼び出しによって遷移情報を維持することはできない。
    • op に引数として渡される要素の変更を行ってはならない。
    • 連想コンテナ( set/multiset/map/multimap ) は、これと同等の動作をする count() メソッドを持っている。
    ┘

    ■最小と最大の要素検出

    InputIterator
      min_element (InputIterator beg, InputIterator end) ;
      min_element (InputIterator beg, InputIterator end, CompFunc op) ;
      max_element (InputIterator beg, InputIterator end) ;
      max_element (InputIterator beg, InputIterator end, CompFunc op) ;
    • [beg,end)　の範囲において、最小／最大の要素の位置を返す。
    • op を受け取らない演算子は、 < 演算子で要素を比較する。
    • op は、op(elem1,elem2) のように２つの要素を比較する二項叙述関数で構成される。 戻り値は、elem1がelem2より前に来るときに true を返す仕組みを提供しなければならない。
    • 最小／最大値が複数ある場合は、最初のものを返す。
    • op は、引数として渡される要素を変更してはならない。
    ┘

    ■要素の検索

    InputIterator
      find (InputIterator beg, InputIterator end, const T& value)
      find_if (InputIterator beg, InputIterator end, UnaryPredicate op)
    • find() は、[beg,end) という範囲で、value と一致する一番最初の要素の位置を返す。
    • find_if() は、[beg,end) という範囲で、単項叙述関数 op(elem) が true を返却する一番最初の要素の位置を返す。
    • どちらも合致する要素がなければ、end を返す。
    • op は、内部に遷移情報を維持できない。
    • op は、要素として渡された引数を変更してはならない。
    • 範囲がソートされている場合、lower_bound() / upper_bound() / binary_search() のアルゴリズムを利用するべきである。
    • 連想コンテナの場合は、付属メソッドのfind()を利用した方がより高速に処理できる。
    ┘

    ■連続する要素の検索

    InputIterator
      search_n (InputIterator beg, InputIterator end,
      Size count, const T& value)
      search_n (InputIterator beg, InputIterator end,
      Size count, const T& value, BinaryPredicate op)
    • 最初の形式は、[beg,end) という範囲で、要素が value と一致する数が count だけ連続する最初の位置を返す。
    • ２番目の形式は、[beg,end) という範囲で、　二項叙述関数の op(elem,value) が true となる要素が count だけ連続する最初の位置を返す。
    • どちらも合致する要素が無ければ、 end を返す。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    ┘

    ■範囲に一致する要素の検索

    ForwardIterator
      search (ForwardIterator1 beg, ForwardIterator1 end,
      ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
      search (ForwardIterator1 beg, ForwardIterator1 end,
      ForwardIterator2 searchBeg, ForwardIterator2 searchEnd,
      BinaryPredicate op)
    • [beg,end) という範囲で、 [searchBeg,searchEnd) という検索範囲と合致する一番手前の範囲で最初の要素の位置を返す。
    • 最初の形式では、検索範囲とすべて等しい範囲を検索する。
    • ２番目の形式では、二項叙述関数 op(elem,searchElem) が全て true を返す範囲を検索する。
    • 範囲が見つからない場合は、どちらとも end を返す。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    ┘

    ■最終範囲に一致する要素の検索

    ForwardIterator
      find_end (ForwardIterator1 beg, ForwardIterator1 end,
      ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
      find_end (ForwardIterator1 beg, ForwardIterator1 end,
      ForwardIterator2 searchBeg, ForwardIterator2 searchEnd,
      BinaryPredicate op)
    • [beg,end) という範囲で、 [searchBeg,searchEnd) という検索範囲と合致する一番最後の範囲で最初の要素の位置を返す。
    • 最初の形式では、検索範囲とすべて等しい範囲を検索する。
    • ２番目の形式では、二項叙述関数 op(elem,searchElem) が全て true を返す範囲を検索する。
    • 範囲が見つからない場合は、どちらとも end を返す。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    ┘

    ■候補を指定した要素の検索

    ForwardIterator
      find_first_of (ForwardIterator1 beg, ForwardIterator1 end,
      ForwardIterator2 searchBeg, ForwardIterator2 searchEnd)
      find_first_of (ForwardIterator1 beg, ForwardIterator1 end,
      ForwardIterator2 searchBeg, ForwardIterator2 searchEnd,
      BinaryPredicate op)
    • 最初の形式では、[beg,end) という範囲で、 [searchBeg,searchEnd) という範囲の要素の少なくとも一つが一致する一番手前の要素の位置を返す。
    • ２番目の形式では、[beg,end) という範囲で、 [searchBeg,searchEnd) という範囲の要素の少なくとも一つ含まれており、かつ、二項叙述関数 op(elem,searchElem) が全て true を返す一番手前の要素の位置を返す。
    • 範囲が見つからない場合は、どちらとも end を返す。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    • 最後の位置を知るには、 逆反復子を最初の範囲を指定する引数で使用すると良い。
    ┘

    ■隣接する要素の検索

    ForwardIterator
      adjacent_find (InputIterator beg, InputIterator end)
      adjacent_find (InputIterator beg, InputIterator end,
      BinaryPredicate op)
    • 最初の形式では、[beg,end) という範囲で、値がその次のものと一致する一番手前の要素の位置を返す。
    • ２番目の形式では、[beg,end) という範囲で、 二項叙述関数 op(elem,nextElem) が true を返す一番手前の要素の位置を返す。
    • 範囲が見つからない場合は、どちらとも end を返す。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    ┘

    ■等価性のチェック

    bool
      equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
      equal (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg,
      BinaryPredicate op)
    • 最初の形式では、[beg,end) という範囲の要素が、cmpBeg から始まる要素と等しいかどうかを返す。
    • ２番目の形式では、[beg,end) という範囲の要素が、cmpBeg から始まる要素と二項叙述関数 op(elem,cmpElem) で比較した結果がすべて true を返すかどうかを返す。
    • cmpBegの領域の長さは、[beg,end) 以上でなければならない。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    ┘

    ■異なる最初の要素の検索

    pair<InputIterator1,InputIterator2>
      mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg)
      mismatch (InputIterator1 beg, InputIterator1 end, InputIterator2 cmpBeg,
      BinaryPredicate op)
    • 最初の形式では、[beg,end) という範囲の要素が、cmpBeg から始まる要素と比較を始め、一番最初に等しくなくなった反復子の位置を最初の反復子と比較の反復子のペアで返す。
    • ２番目の形式では、[beg,end) という範囲の要素が、cmpBeg から始まる要素と二項叙述関数 op(elem,cmpElem) で比較した結果が最初に false を返す最初の位置を最初の反復子と比較の反復子のペアで返す。
    • 範囲が見つからない場合、返される値の最初の要素は、end となる。
    • cmpBegの領域の長さは、[beg,end) 以上でなければならない。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    ┘

    ■辞書順位の比較

    bool
      lexicographical_compare (InputIterator1 beg2, InputIterator1 end2,
              InputIterator2 beg2, InputIterator2 end2)
      lexicographical_compare (InputIterator1 beg2, InputIterator1 end2,
      InputIterator2 beg2, InputIterator2 end2,
      BinaryPredicate op)
    • [beg1,end1) の範囲が [beg2,end2) の範囲より辞書順位で小さいかどうかを返す。
    • 最初の形式では、< 比較演算子で比較する。
    • ２番目の形式では、op(elem1,elem2) を使って要素を比較する。 elem1 が elem2 より小さい場合に true を返さなければならない。
    • 辞書順位比較とは、 ANSI C の　memcmp や strcmp のように、文字位置の不一致要素の比較処理でソート優先順位が絡む比較を意味する。 ただし、戻り値については、小さいか小さくないかの２通り以外は存在しないことに気をつけなければならない。
    • op は、内部に遷移情報を維持できない。
    • op は、渡された引数を変更してはならない。
    ┘

    ■要素のコピー

    OutputIterator
    copy (InputIterator sourceBeg, InputIterator sourceEnd,
    OutputIterator destBeg)
    BidirectionalIterator2
      copy_backward (BidirectionalIterator1 sourceBeg,
      BidirectionalIterator1 sourceEnd,
      BidirectionalIterator2 destEnd)
    • [sourceBeg,sourceEnd) の範囲を destBeg で始まる(または、destEnd で終わる) 出力先の範囲にコピーする。
    • 返却値は、コピーが終了した次の要素を示す位置を返す。
    • ２つの範囲は、まったく同じものであってはいけない。
    • copy() は、前進して反復処理を繰り返すが、 copy_backward() は、後退して反復処理を繰り返す。　これは、領域が重複する場合に意味を持つ。
    ┘

    ■要素の変換と結合

    OutputIterator
    transform (InputIterator sourceBeg, InputIterator sourceEnd,
    OutputIterator destBeg, UnaryFunc op)
      transform (InputIterator1 source1Beg, InputIterator1 source1End,
      InputIterator2 source2Beg,
      OutputIterator destBeg, BinaryFunc op)
    • 最初の形式は、[sourceBeg,sourceEnd) の範囲を op(elem) の戻り値で destBeg から始まる範囲に上書きする。
    • ２番目の形式は、[source1Beg,source1End) の範囲と、source2Beg から始まる同じだけの範囲を op(elem1,elem2) の戻り値で destBeg から始まる範囲に上書きする。
    • 返却値は、上書きが終了した次の要素を示す位置を返す。
    • source1/source2/dest の範囲は、全く同じものを示していても構わない。
    ┘

    ■要素の交換

    ForwardIterator2
    swap_ranges (ForwardIterator1 beg1, ForwardIterator1 end1,
    ForwardIterator2 beg2)
    • [beg1,end1) の範囲を beg2 から始まる範囲と交換する。
    • 返却値は、交換が終了した2番目の範囲の次の要素を示す位置を返す。
    • ２つの範囲は、重複してはいけない。
    ┘

    ■単一の値で要素を埋め尽くす

    void
    fill (ForwardIterator1 beg, ForwardIterator1 end, const T& newValue)
    fill_n (OutputIterator beg, Size num, const T& newValue)
    • fill は、[beg,end) の範囲を newValue という値で埋め尽くす。
    • fill_n は、beg で始まる範囲を num 回反復して newValue という値で埋め尽くす。
    ┘

    ■値を生成して要素を埋め尽くす

    void
    generate (ForwardIterator1 beg, ForwardIterator1 end, Func op)
    generate_n (OutputIterator beg, Size num, Func op)
    • generate は、[beg,end) の範囲を op() という呼び出しの戻り値で埋め尽くす。
    • generate_n は、beg で始まる範囲を num 回反復して op() という呼び出しの戻り値で埋め尽くす。
    ┘

    ■要素の検索置換

    void
    replace (ForwardIterator beg, ForwardIterator end,
    const T& searchValue, const T& replaceValue)
    replace_if (ForwardIterator beg, ForwardIterator end,
    UnaryPredicate op, const T& replaceValue)
    • replace は、[beg,end) の範囲のうち、searchValue に等しい要素を replaceValue で置き換える。
    • replace_if は、[beg,end) の範囲のうち、op(elem) が true となるすべての要素を replaceValue で埋め尽くす。
    • op() は、内部に遷移情報を維持できない。
    ┘

    ■要素のコピーと検索置換

    OutputIterator
    replace_copy (InputIterator sourceBeg, InputIterator sourceEnd,
    OutputIterator destBeg,
    const T& searchValue, const T& replaceValue)
    replace_copy_if (InputIterator sourceBeg, InputIterator sourceEnd,
    OutputIterator destBeg,
    UnaryPredicate op, const T& replaceValue)
    • replace_copy は、[souceBeg,sourceEnd) の範囲を、destBeg に上書きコピーする。　その際、同時に searchValue に等しい要素を replaceValue で置き換えてコピーを行う。
    • replace_copy_if は、[souceBeg,sourceEnd) の範囲を、destBeg に上書きコピーする。　その際、同時に op(elem) が true となるすべての要素を replaceValue で置き換えてコピーを行う。
    • 返却値は、上書きが終了した範囲の次の要素を示す位置を返す。
    • op() は、内部に遷移情報を維持できない。
    ┘

    ■要素の削除

    ForwardIterator
    remove (ForwardIterator beg, ForwardIterator end,
    const T& value)
    remove_if (ForwardIterator beg, ForwardIterator end,
    UnaryPredicate op)
    • remove は、[beg,end) の範囲のうち、value に等しい要素をすべて削除する。
    • remove_if は、[beg,end) の範囲のうち、op(elem) が true となるすべての要素を削除する。
    • 戻り値は、変更されたシーケンスの論理的な新しい終了位置を意味する。　コンテナのメソッドを利用して削除しているわけではないので、実際には、削除した分が前方へ押しやられるだけでコンテナサイズの縮小は起こらない。　コンテナを正しいサイズに設定するには、この新しい終了位置と古い終了位置をコンテナの erase メソッドに渡して消去する必要がある。
    • op() は、内部に遷移情報を維持できない。
    ┘

    ■要素のコピーと削除

    OutputIterator
    remove_copy (InputIterator sourceBeg, InputIterator sourceEnd,
    OutputIterator destBeg, const T& value)
    remove_copy_if (InputIterator sourceBeg, InputIterator sourceEnd,
    OutputIterator destBeg, UnaryPredicate op)
    • remove_copy は、[beg,end) の範囲のうち、value に等しい要素を排除しながら destBeg へ要素の上書きコピーを行う。
    • remove_copy_if は、[beg,end) の範囲のうち、op(elem) が true となる要素を排除しながら destBeg へ要素の上書きコピーを行う。
    • 返却値は、上書きが終了した範囲の次の要素を示す位置を返す。
    • op() は、内部に遷移情報を維持できない。
    ┘

    ■隣接の重複した要素の削除

    ForwardIterator
    unique (ForwardIterator beg, ForwardIterator end)
    unique (ForwardIterator beg, ForwardIterator end, BinaryPredicate op)
    • 最初の形式は、[beg,end) の範囲のうち、隣接する要素の値が同じものの重複をすべて削除する。
    • ２番目の形式は、[beg,end) の範囲のうち、e を隣接の始まりの要素とする、op(e,elem) が true となる重複の要素をすべて削除する。
    • 戻り値は、変更されたシーケンスの論理的な新しい終了位置を意味する。　コンテナのメソッドを利用して削除しているわけではないので、実際には、削除した分が前方へ押しやられるだけでコンテナサイズの縮小は起こらない。　コンテナを正しいサイズに設定するには、この新しい終了位置と古い終了位置をコンテナの erase メソッドに渡して消去する必要がある。
    • op() は、内部に遷移情報を維持できない。
    ┘

    ■コピーと隣接の重複した要素の削除

    OutputIterator
    unique_copy (InputIterator beg, InputIterator end,
    OutputIterator destBeg)
    unique_copy (InputIterator beg, InputIterator end,
    OutputIterator destBeg, BinaryPredicate op)
    • 最初の形式は、[beg,end) の範囲のうち、隣接する要素の値が同じものの重複を除去しながら destBeg へ上書きコピーを行う。
    • ２番目の形式は、[beg,end) の範囲のうち、e を隣接の始まりの要素とする、op(e,elem) が true となる重複の要素をすべて排除しながら、 destBeg へ上書きコピーを行う。
    • 返却値は、上書きが終了した範囲の次の要素を示す位置を返す。
    • op() は、内部に遷移情報を維持できない。
    ┘

    ■要素順序の逆転

    void
    reverse (BidirectionalIterator beg, BidirectionalIterator end)
    OutputIterator
    reverse_copy (InputIterator beg, InputIterator end,
    OutputIterator destBeg, BinaryPredicate op)
    • reverse は、[beg,end) の範囲の要素の並び順を逆転させる。
    • reverse_copy は、[beg,end) の範囲の要素の並び順を逆転したものを、destBeg へ上書きコピーを行う。
    • reverse_copy の返却値は、上書きが終了した範囲の次の要素を示す位置を返す。
    • op() は、内部に遷移情報を維持できない。
    ┘

    ■要素順序の回転

    void
    rotate (ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end)
    • [beg,end) の範囲の要素の並び順を(*newBeg)が最初の要素に来るように並び順を変える。　アセンブラのローテート命令と同じように、新しい位置から不足した要素は、先頭の要素を循環して連ねる仕組みになっている。
    • newBeg の位置は、[beg,end) の範囲を超えてはならない。
    ┘

    ■コピーと要素順序の回転

    OutputIterator
    rotate_copy (ForwardIterator sourceBeg, ForwardIterator newBeg,
     ForwardIterator sourceEnd, OutputIerator destBeg)
    • [sourceBeg,sourceEnd) の範囲の要素の並び順を(*newBeg)が最初の要素に来るように並び順を変えながら、destBeg を先頭に上書きコピーを行う。　アセンブラのローテート命令と同じように、新しい位置から不足した要素は、先頭の要素を循環して連ねる仕組みになっている。
    • newBeg の位置は、[sourceBeg,sourceEnd) の範囲を超えてはならない。
    • 返却値は、上書きが終了した範囲の次の要素を示す位置を返す。
    ┘

    ■要素順序のステップソート

    bool
    next_permutation (BidirectionalIterator beg, BidirectionalIterator end)
    prev_permutation (BidirectionalIterator beg, BidirectionalIterator end)
    • next_permutation は、[beg,end) 間を一箇所だけ並べ替えて、現在の順列よりもソートの値がひとつだけ大きい順列に組み直す。
    • prev_permutation は、[beg,end) 間を一箇所だけ並べ替えて、現在の順列よりもソートの値がひとつだけ小さい順列に組み直す。
    • 返却値は、順列の組み合わせがみつかって組み直しが成功すれば、true を返す。　次の候補の並び順列が見つからなければ、false を返す。
    ┘

    ■要素順序のシャッフル

    bool
    random_shuffle (RandomAccessIterator beg, RandomAccessIterator end)
    random_shuffle (RandomAccessIterator beg, RandomAccessIterator end,
    RandomFunc& op)
    • 最初の形式 は、[beg,end) 間を均等に分布させるデフォルト乱数ジェネレータを利用してシャッフルを行う。
    • 最初の形式 は、[beg,end) 間をユーザー定義の op() 乱数ジェネレータを利用してシャッフルを行う。　op に指定される型は、引数／戻り値 共に 反復子の difference_type 型で、整数(max) を使って op(max) のように呼び出される。　このとき、 op() は、 0 以上 max 未満の乱数を返さなければならない。
    • 返却値は、順列の組み合わせがみつかって組み直しが成功すれば、true を返す。　次の候補の並び順列が見つからなければ、false を返す。
    • op は、定数ではなく、型参照型であることに注意。　したがって、一時的な値や通常の関数は渡せない。　クラス化された関数オブジェクトの()オペレータできちんと定義しなければならない。
    ┘

    ■要素全体の二分割

    BidirectionalIterator
    partition (BidirectionalIterator beg, BidirectionalIterator end,
    UnaryPredicate op)
    stable_partition (BidirectionalIterator beg, BidirectionalIterator end,
    UnaryPredicate op)
    • [beg,end) 間を op(elem) が true を返す要素をすべて前に移動させる。
    • op(elem) が false を返す最初の位置を返す。
    • ２つのアルゴリズムは、stable_partition が並び替える前と後の相対的な要素の順序が保たれる点に相違がある。
    • op は、内部に遷移情報を維持できない。
    ┘

    ■要素全体のソート

    void
    sort (RandomAccessIterator beg, RandomAccessIterator end)
    sort (RandomAccessIterator beg, RandomAccessIterator end,
    BinaryPredicate op)
    stable_sort (RandomAccessIterator beg, RandomAccessIterator end)
    stable_sort (RandomAccessIterator beg, RandomAccessIterator end,
    BinaryPredicate op)
    • sort() と stable_sort() の最初の形式は、[beg,end) 間を < 演算子によってソートさせる。
    • sort() と stable_sort() の２つめの形式は、ユーザー定義の op(elem1,elem2) をソートの基準としてソートする。
    • ２つのアルゴリズムは、stable_sort が並び替えた後と前の相対的な要素の順序が保たれる点に相違がある。
    • op は、内部に遷移情報を維持できない。
    ┘

    ■要素の部分ソート

    void
    partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd,
    RandomAccessIterator end)
    partial_sort (RandomAccessIterator beg, RandomAccessIterator sortEnd,
    RandomAccessIterator end, BinaryPredicate op)
    • 最初の形式は、[beg,sortEnd) 間の区間が完全にソートされるように、[beg,end) 間を < 演算子でソートする。
    • 2つ目の形式は、[beg,sortEnd) 間の区間が完全にソートされるように、[beg,end) 間をユーザー定義の op(elem1,elem2) をソートの基準としてソートする。
    • op は、内部に遷移情報を維持できない。
    ┘

    ■要素の部分ソートによる複写

    RandomAccessIterator
    partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd,
    RandomAccessIterator destBeg,
    RandomAccessIterator destEnd)
    partial_sort_copy (InputIterator sourceBeg, InputIterator sourceEnd,
    RandomAccessIterator destBeg,
    RandomAccessIterator destEnd,
    BinaryPredicate op)
    • [souceBeg,sourceEnd) 間をソートしながら、[destBeg,destEnd) 間に上書きコピーする。
    • コピーされる要素の個数は、両区間の要素数のうち、少ないほうの要素数分のものとなる。
    • 最初の形式は、<演算子でソートを行う。 ２番目の op　は、ユーザー定義の op(elem1,elem2) をソート基準にした叙述関数を指定する。
    • op は、内部に遷移情報を維持できない。
    • 戻り値は、dest の最後に出力された要素の次の位置を返す。
    ┘

    ■n番目の要素を基準とした要素の二分割

    void
    nth_element (RandomAccessIterator beg, RandomAccessIterator nth,
    RandomAccessIterator end)
    nth_element (RandomAccessIterator beg, RandomAccessIterator nth,
    RandomAccessIterator end, BinaryPredicate op)
    • [beg,end) 間を nth 反復子が示す要素の値を比較して他の要素を nth の前後に分割する。　前後に分けるだけで、ソートは行われない。
    • 最初の形式は、<演算子で分割の基準とする。 ２番目の op　は、ユーザー定義の op(elem1,elem2) を分割基準にした叙述関数を指定する。
    • op は、内部に遷移情報を維持できない。
    ┘

    ■コンテナのヒープソート

      ランダムアクセス反復子を利用するコンテナ(vector/deque)の要素を仮想的な二分木に整列し直すアルゴリズムをヒープソートという。　ヒープソートを行った要素は仮想的な二分木に展開されているため、要素を一つ追加するごとに最小のステップで整合化できるところに特徴がある。

      たとえば、次のような整数順列をヒープソートするとする。

    7 18 9 18 25 19 22
      上記の整数順列は、make_heap() を呼び出して整列させると以下のような形になる。
    25 18 22 7 9 19 18
      一見、何が行われたかわけがわからないが、この二分木構造は、以下のような形を表している。
      つまり、最上を頂点としてディスプレイの走査線のように木構造を構築している。
      この変換された整数順列に対して、sort_heap() を呼び出すと以下のようにソートされた順列に展開することが出来る。
    7 9 18 18 19 22 25
    void
      make_heap (RandomAccessIterator beg, RandomAccessIterator end)
      make_heap (RandomAccessIterator beg, RandomAccessIterator end,
      BinaryPredicate op)
    • [beg,end) 間をヒープに変換する。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    void
      push_heap (RandomAccessIterator beg, RandomAccessIterator end)
      push_heap (RandomAccessIterator beg, RandomAccessIterator end,
      BinaryPredicate op)
    • end の前にある要素間 [beg,end-1) がヒープソートされているコンテナを、end の位置に要素が新たに追加されたこととして範囲全体 [beg,end) をヒープソートする。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
      • <例> - ヒープソート済みのコンテナに新しい値を代入する。
        vect.push_back(new_value) ;
        vect.push_heap(vect.begin(),vect.end()) ;
    void
      pop_heap (RandomAccessIterator beg, RandomAccessIterator end)
      pop_heap (RandomAccessIterator beg, RandomAccessIterator end,
        BinaryPredicate op)
    • 要素の値が一番大きいもの（つまり、頂点の要素）をコンテナの終わりの位置に移動し、残りの要素間 [beg,end-1) を新たにヒープソートする。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
      • <例> - ヒープソート済みのコンテナからソート構造を壊さずに一番大きい値を取り出す。
        vect.pop_heap(vect.begin(),vect.end()) ;
        max_value = vect.back() ;
        vect.pop_back() ;
    void
      sort_heap (RandomAccessIterator beg, RandomAccessIterator end)
      sort_heap (RandomAccessIterator beg, RandomAccessIterator end,
        BinaryPredicate op)
    • 要素間 [beg,end) の予めヒープソートされた区間を、通常のシーケンスソートへ展開する。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の要素一つの存在可否

    bool
    binary_search (ForwardIterator beg, ForwardIterator end, const T& Value)
    binary_search (ForwardIterator beg, ForwardIterator end, const T& Value,
    BinaryPredicate op)
    • 予めソートされた区間 [beg,end) 間に value が含まれるかどうかを調べる。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の複数要素の存在可否

    bool
    includes (InputIterator1 beg, InputIterator1 end,
    InputIterator2 searchBeg, InputIterator2 searchEnd )
    includes (InputIterator1 beg, InputIterator1 end,
    InputIterator2 searchBeg, InputIterator2 searchEnd,
    BinaryPredicate op)
    • 予めソートされた区間 [beg,end) 間に 予めソートされた区間 [searchBeg,searchEnd) の要素がすべて含まれていれば、true を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の最初または最後の要素位置の検索

    ForwardIterator
    lower_bound (ForwardIterator beg, ForwardIterator end, const T& value)
    lower_bound (ForwardIterator beg, ForwardIterator end, const T& value,
    BinrayPredicate op)
    upper_bound (ForwardIterator beg, ForwardIterator end, const T& value)
    upper_bound (ForwardIterator beg, ForwardIterator end, const T& value,
    BinrayPredicate op)
    • lower_bound() は、予めソートされた区間 [beg,end) 間に value が存在する位置の最初の位置を返す。
    • upper_bound() は、予めソートされた区間 [beg,end) 間に value が存在する位置の最後の位置より一つだけ大きい位置を返す。
    • value が存在しなければ、どちらとも end を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の要素範囲の検索

    pair<ForwardIterator, ForwardIterator>
    equal_range (ForwardIterator beg, ForwardIterator end, const T& value)
    equal_range (ForwardIterator beg, ForwardIterator end, const T& value,
    BinrayPredicate op)
    • 予めソートされた区間 [beg,end) 間に value が存在する位置の最初と最後より一つ大きい位置をペアで返す。　これは、 make_pair(lower_bound(,,,),upper_bound(,,,)) と等価である。
    • value が存在しなければ、どちらとも make_pair(end,end) を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の要素範囲の結合

    OutputIterator
    merge (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg)
    merge (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg, BinrayPredicate op)
    • 予めソートされた区間 [source1Beg,source1End) と [source2Beg,source2End) 間を　ソート順序を乱さずに結合しながら destBeg へその結果を上書きする。
    • 戻り値は、出力が終了した次の位置を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の要素範囲の和

    OutputIterator
    set_union (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg)
    set_union (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg, BinrayPredicate op)
    • 予めソートされた区間 [source1Beg,source1End) と [source2Beg,source2End) 間を　ソート順序を乱さずに結合しながら destBeg へその結果を上書きする。　その際、重複した要素がsource1/2両者に出現した場合は、要素全部を結合して書き込むのではなくて、source1/2に含まれている重複要素のうち、要素数の多いものを書き込む。 要するに、{1,1,1,2,2} + {1,1,2,2,2} = { 1,1,1,2,2,2} となる。
    • 戻り値は、書き込みが終了した次の位置を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の要素範囲の交差

    OutputIterator
    set_intersection (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg)
    set_intersection (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg, BinrayPredicate op)
    • 予めソートされた区間 [source1Beg,source1End) と [source2Beg,source2End) 間を　ソート順序を乱さずに結合しながら destBeg へその結果を上書きする。　その際、source1/2両者に共に出現した要素のみを書き込む。 要するに、{1,1,1,2,2,3,5,7,8,8} + {1,1,2,2,2,3,6,7,9} = { 1,1,2,2,3,7} となる。
    • 戻り値は、書き込みが終了した次の位置を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の要素範囲の差

    OutputIterator
    set_difference (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg)
    set_difference (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg, BinrayPredicate op)
    • 予めソートされた区間 [source1Beg,source1End) と [source2Beg,source2End) 間を　ソート順序を乱さずに結合しながら destBeg へその結果を上書きする。　その際、source1には出現するが、source2には出現しない要素のみを書き込む。 要するに、{1,1,1,2,2,3,5,7,8,8} + {1,1,2,2,2,3,6,7,9} = { 5,8,8} となる。
    • 戻り値は、書き込みが終了した次の位置を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の要素範囲の差(2)

    OutputIterator
    set_symmetric_difference (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg)
    set_symmetric_difference (InputIterator source1Beg, InputIterator source1End,
    InputIterator source2Beg, InputIterator source2End,
    OutputIterator destBeg, BinrayPredicate op)
    • 予めソートされた区間 [source1Beg,source1End) と [source2Beg,source2End) 間を　ソート順序を乱さずに結合しながら destBeg へその結果を上書きする。　その際、source1/2のどちらか一方のみに出現した要素のみを書き込む。 要するに、{1,1,1,2,2,3,5,7,8,8} + {1,1,2,2,2,3,6,7,9} = {1,2,5,6,8,8,9} となる。
    • 要素比較参照は、一対一で対応している。 つまり、書き込む要素の重複が現れた場合は、重複要素が重なっていない量分の要素が書き込まれる。 例えば、xという要素が source1 に３つ現れて、source2 に２つ現れれば、　3-2 = 1 個の x が書き込まれることになる。
    • 戻り値は、書き込みが終了した次の位置を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■予めソートされた区間の隣接区間結合

    void
    inplace_merge (BidirectionalIterator beg1,
     BidirectionalIterator end1beg2,
     BidirectionalIterator end2)
    inplace_merge (BidirectionalIterator beg1,
     BidirectionalIterator end1beg2,
     BidirectionalIterator end2, BinrayPredicate op)
    • 予めソートされた隣接区間 [beg1,end1beg2) と [end1beg2,end2) 間を　ソート順序を乱さずに結合しながら [beg1,end2) へ書き込みを行う。
    • 戻り値は、書き込みが終了した次の位置を返す。
    • op は、op(elem1,elem2) のようにソートを基準とする二項叙述関数を指定する。
    ┘

    ■コンテナ要素の合計

    T
    accumulate (InputIterator beg, InputIterator end, T initValue)
    accumulate (InputIterator beg, InputIterator end, T initValue, BinrayFunc op)
    • 最初の形式は、[beg,end) 間を initValue = initValue + elem を繰り返して累計した initValue を戻り値として返す。
    • ２番目の形式は、[beg,end) 間を initValue = op( initValue , elem ) を繰り返してop任せの累計を行った initValue を戻り値として返す。
    ┘

    ■コンテナ要素同士の内積

    T
    inner_product (InputIterator beg1, InputIterator end1,
    InputIterator beg2, InputIterator end2, T initValue)
    inner_product (InputIterator beg1, InputIterator end1,
    InputIterator beg2, InputIterator end2, T initValue,
    BinrayFunc op1, BinrayFunc op2)
    • 最初の形式は、[beg1,end1)/[beg2,end2) 間を initValue = initValue + elem1 * elem2 を繰り返して累計した initValue を戻り値として返す。
    • ２番目の形式は、[beg1,end1)/[beg2,end2) 間を initValue = op1( initValue , op2(elem1 ,elem2) ) を繰り返してop任せの累計を行った initValue を戻り値として返す。
    ┘

    ■コンテナ要素の各部分合計

    OutputIterator
    partial_sum (InputIterator sourceBeg, InputIterator sourceEnd,
     OutputIterator destBeg)
    partial_sum (InputIterator sourceBeg, InputIterator sourceEnd,
     OutputIterator destBeg, BinrayFunc op)
    • 最初の形式は、[sourceBeg,sourceEnd) 間を destElem[i] = Σ（sourceBeg to i） sourceElem[i] として順に destBeg へ 書き込んでいく。
    • ２番目の形式は、[sourceBeg,sourceEnd) 間を destElem[i] = Σ（sourceBeg to i） sourceElem[i] として順に 足し算に op を利用して　destBeg へ 書き込んでいく。
    • 戻り値は、書き込みが終了した位置より一つ大きい位置を返す。
    ┘

    ■コンテナ要素の絶対値を相対値へ変換

    OutputIterator
    adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd,
     OutputIterator destBeg)
    adjacent_difference (InputIterator sourceBeg, InputIterator sourceEnd,
     OutputIterator destBeg, BinrayFunc op)
    • 最初の形式は、[sourceBeg,sourceEnd) 間を destElem[i] = sourceElem[i] - sourceElem[i-1] として順に destBeg へ 書き込んでいく。 ただし、出力される最初の要素は、*sourceBeg　となる。
    • ２番目の形式は、[sourceBeg,sourceEnd) 間を destElem[i] = sourceElem[i] op sourceElem[i-1] として順に destBeg へ 書き込んでいく。 ただし、出力される最初の要素は、*sourceBeg　となる。
    • 戻り値は、書き込みが終了した位置より一つ大きい位置を返す。
    ┘


STL プロフェッサー・ノート

工事中...。

○ stack
○ queue
○ priority_queue
○ bitset
○ string
△ valarray
× complex
× rope

ヒューレットパッカード製のSTL(VC6付属品)を利用する場合は、
文字列クラス同士の比較命令でハングする恐れがあるので、
問題が多発する場合は、
char_traits<> の compare メソッドを
memcmp から strncmp　に書きかえたものを継承すると良いです。
人が創ったものなので、多少のバグは多かれ少なかれ存在します。

〔特殊なコンテナ〕

■stack

  スタックは、シーケンスコンテナのメソッドをスタックに特化させるために別に生成されたカプセル化インラインテンプレートクラスである。
// stack ： #include <stack>
namespace std {
template<class T,class Container = deque<T> >
class stack ;
}

  デフォルトテンプレートで指定されるコンテナは、deque であるが、これは、dequeがvectorと違い、メモリ管理が自動で行われる点を考慮されたものと考えられる。　敢えてメモリを解放しないのであれば、 stack<int,vector<int> > int_vstack などとしてカプセルコンテナを vector に指定することも出来る。
スタックでコンテナへのアクセスが提供されるメソッドは、以下の三種類が主に挙げられる。

push() - 要素を先頭へ積む
top() - 先頭の要素を返す
pop() - 先頭から要素を一つ外す
  要はただのスタックである。　スタック以外の不必要な機能を全部取っ払っている。
  stack については、構造を明記した方が分かり易いだろう。
namespace std {
template<class T,class Container = deque<T> >
class stack {
  public:
typedef typename Container::value_type value_type ;
typedef typename Container::size_type size_type ;
typedef Container container_type ;
  protected:
Container c ; // カプセルコンテナ
  public:
expclict stack(const Container & = Container()) ;
bool empty() const { return c.empty() ; }
size_t size() const { return c.size() ; }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
value_type top() { return c.back(); }
const value_type& top() const { return c.back(); }
template<class T, class Container>
  bool operator== (const stack<T,Container>&
,const stack<T,Container>&);
template<class T, class Container>
  bool operator< (const stack<T,Container>&
,const stack<T,Container>&);
//　operator > <= >= != 省略
};
}
┘

■queue

  キューは、シーケンスコンテナのメソッドを順番待ちに特化させるために別に生成されたカプセル化インラインテンプレートクラスである。　ここで言う順番とは、レストランの行列待ちと同じで店員が客を扱うように、要素を循環させる事を意味している。 push()で新たに並んだ要素は、先客の要素がpop()して出て行かない限り、その要素は顔を現さないということである。
// queue ： #include <queue>
namespace std {
template<class T,class Container = deque<T> >
class queue ;
}

  デフォルトテンプレートで指定されるコンテナは、deque であるが、これは、dequeが順番待ちに一番適したコンテナであることが考慮されたものと考えられる。　例えば、listでそれを敢えて再現したいのであれば、 queue<int,list<int> > int_lqueue などとしてカプセルコンテナをlistに指定することも出来る。
キューでコンテナへのアクセスが提供されるメソッドは、以下の四種類が主に挙げられる。

push() - 要素を並びの最後に追加する
front() - 先頭の要素を返す
back() - 最後の要素を返す
pop() - 先頭から要素を一つ外す
  スタックとの違いは、push()で追加されていった要素を逆順ではなく順番どおりに取り出してゆく所にある。
  queue についても、構造を明記した方が分かり易いだろう。　front/back/pop 以外は、stack と同じような構造をしている。
namespace std {
template<class T,class Container = deque<T> >
class queue {
  public:
typedef typename Container::value_type value_type ;
typedef typename Container::size_type size_type ;
typedef Container container_type ;
  protected:
Container c ; // カプセルコンテナ
  public:
expclict queue(const Container & = Container()) ;
bool empty() const { return c.empty() ; }
size_t size() const { return c.size() ; }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
value_type front() { return c.front(); }
const value_type& front() const { return c.front(); }
value_type back() { return c.back(); }
const value_type& back() const { return c.back(); }
template<class T, class Container>
  bool operator== (const queue<T,Container>&
,const queue<T,Container>&);
template<class T, class Container>
  bool operator< (const queue<T,Container>&
,const queue<T,Container>&);
//　operator > <= >= != 省略
};
}
┘

■priority_queue

  優先度付きキューは、シーケンスコンテナのメソッドを順番待ちに特化させ、かつ優先順に内部にヒープを保持したカプセル化インラインテンプレートクラスである。　内部のコンテナ要素は常にヒープソートで優先順が保たれている。
// priority_queue ： #include <queue>
namespace std {
template<  class T,
class Container = vector<T>,
class Compare = less<typename Container::value_type> >
class priority_queue ;
}

  デフォルトテンプレートで指定されるコンテナは、vector であるが、これにはあまり深い意味がない。 dequeでそれを敢えて再現したいのであれば、 priority_queue<int,deque<int>,greater<int> > int_dgpqueue などとしてカプセルコンテナをdequeに指定することも出来る。
優先度付きキューでコンテナへのアクセスが提供されるメソッドは、以下の３種類が主に挙げられる。

push() - 要素を並びに追加してヒープソートする
top() - 優先度最大の要素を返す
pop() - 優先度最大の要素を一つ外す
  push()で追加されていった要素は、常に優先度付きでソートされる。
  priority_queue についても、stack/queue　と同じような構造をしている。　初期化と要素が挿入される部分で make_heap/push_heap/pop_heap を利用してヒープソートされる辺りが違う。
namespace std {
template<class T,class Container = vector<T>,
 class Compare = less<typename Container::value_type> >
class priority_queue {
  public:
typedef typename Container::value_type value_type ;
typedef typename Container::size_type size_type ;
typedef Container container_type ;
  protected:
Compare comp ; // 比較準拠オブジェクト
Container c ; // カプセルコンテナ
  public:
expclict priority_queue(
const Compare & cmp = Compare(),
const Container & cont = Container() )
: comp(cmp), c(cont) {
    make_heap(c.begin(),c.end(),c.end(),comp) ;
}
template<class InputIterator>
expclict priority_queue(
InputIterator first, InputIterator last,
const Compare & cmp = Compare(),
const Container & cont = Container() )
: comp(cmp), c(cont) {
    c.insert(c.end(),first,last) ;
    make_heap(c.begin(),c.end(),c.end(),comp) ;
}
bool empty() const { return c.empty() ; }
size_t size() const { return c.size() ; }
void push(const value_type& x) {
    c.push_back(x);
    push_heap(c,c.begin(),c.end(),comp) ;
}
void pop() {
    pop_heap(c.c.begin(),c.end(),comp) ;
    c.pop_back();
}
value_type top() { return c.front(); }
};
}
┘

■bitset

  ビット(0と１)の配列と演算に特化したコンテナクラス。
// bitset ： #include <bitset>
namespace std {
template< size_t Bits >
class bitset ;
}

<例１> enum フラグとして利用

enum TMyColor { mcRed,mcGreen,mcBlue,mcMax } ;
// enum 値に相互に対応したbitsetの生成
bitset<mcMax> ColorBits ;
// 赤と青のビットを立てる
ColorBits.set(mcRed) ;
ColorBits.set(mcBlue) ;
// ColorBits のビットが立っているかどうか
if(ColorBits.any()) {
//すべてのフラグを調べる
for(int c= 0 ; c < mcMax ; c++ ) {
//ビットが立っているかどうか
if(ColorBits[(TMyColor)c]) {
・・・
}
}
}

<例２> ２進表記文字列としての bitset

//２進数による出力
cout << "267 as binary short:     "
     << bitset<numeric_limits<unsigned short>::digits>(267)
     << endl;

cout << "267 as binary long:      "
     << bitset<numeric_limits<unsigned long>::digits>(267)
     << endl;

cout << "10,000,000 with 24 bits: "
     << bitset<24>(1e7) << endl;

//２進表現を整数に変換
cout << "\"1000101011\" as number:  "
     << bitset<100>(string("1000101011")).to_ulong() << endl;
出力結果
267 as binary short:     0000000100001011
267 as binary long:      00000000000000000000000100001011
"1000101011" as number:  555

● bitset コンストラクタ／デストラクタ

bitset<bits> c
 すべてのビットを0で初期化したbitsetを生成する。
bitset<bits> c(unsigned long value)
 下位ビットをvalueで満たしたbitsetを生成する。 valueでは足りない上位ビットは0で初期化される。
bitset<bits> c(const string& str) //explict
 bitset を生成し、strという２進表記文字列を解析して初期化する。　ビットに足りない上位ビットは0で埋め尽くされる。
bitset<bits> c(const string& str,
string::size_type str_idx)
 bitset を生成し、strという２進表記文字列を解析して初期化する。 その際、2進の解析は、str_idxで指定された文字列インデックスから最後まで行われる。 ビットに足りない上位ビットは0で埋め尽くされる。
bitset<bits> c(const string& str,
string::size_type str_idx,
string::size_type str_num)
 bitset を生成し、strという２進表記文字列を解析して初期化する。 その際、2進の解析は、str_idxで指定された文字列インデックスからstr_num個の文字数を有効数として行われる。 ビットに足りない上位ビットは0で埋め尽くされる。
c.~bitset<bits>()
 bitsetを破棄してメモリを解放する。

● bitset 変更を行わない演算(const)

c.size()
 ビット数(bits)を返す。
c.count()
 ビットのフラグが立っている(ビットが1である)個数を返す。
c.any()
 フラグが立っているビットが存在するかどうかを論理値で返す。
c.none()
 フラグが立っているビットが存在しないかどうかを論理値で返す(anyの逆値)。
c.test(index)
 indexで指定された位置のビットが立っているかどうかを論理値で返す。
c1 == c2
 c1とc2のフラグの状態が同一のものかどうかを論理値で返す。
c1 != c2
 c1とc2のフラグの状態が異なるかどうかを論理値返す。
c[index]
 indexで指定されたビット要素を論理値で取得する。

● bitset 変更を行う演算(constではない)

c.set()
 全てのビットを立てる（１に設定する）。
c.set(index)
 index で指定された位置のビットを立てる（１に設定する）。
c.set(index,value)
 index で指定された位置のビットを value 整数値が 0 以外であれば 1 を、0 であれば 0 を設定する。
c.reset()
 全てのビットを下ろす（０に設定する）。
c.reset(index)
 indexで指定された位置のビットを０に設定する。
c.flip()
 全てのビットを反転する。
c.flip(index) / c[index].flip()
 index で指定された位置のビットを反転する。
c1 ^= c2
 c1 と c2 のビット同士の排他的論理和(XOR)を求めて c1 へその結果を代入する。
c1 |= c2
 c1 と c2 のビット同士の論理和(OR)を求めて c1 へその結果を代入する。
c1 &= c2
 c1 と c2 のビット同士の論理積(AND)を求めて c1 へその結果を代入する。
c <<= num
 c のビット要素全体を左へnumだけシフトする。
c >>= num
 c のビット要素全体を右へnumだけシフトする。
c[index] = value
 index で指定されたビット要素を論理値valueで設定する。

● 変更を加えたbitsetの複製(const)

~c
 全ビットを反転させた c の複製を返す。
c << num
 全ビットを num だけ左シフトした c の複製を返す。
c >> num
 全ビットを num だけ右シフトした c の複製を返す。
c1 & c2
 c1 と c2 の論理積を行った新しいbitsetを返す。
c1 | c2
 c1 と c2 の論理和を行った新しいbitsetを返す。
c1 ^ c2
 c1 と c2 の排他的論理和を行った新しいbitsetを返す。

● bitsetの型変換

c.to_ulong() //const
 unsigned long の符号なし整数値に還元する。
c.to_string() //const
 ２進数文字列に還元する。
istream >> c
 ２進数文字列を c へ読み込む。　読み込みは、istreamがEOFを検出するか、0,1以外の文字を検出するか、<bits>テンプレートのサイズまで続けられる。
ostream << c //const
 c を２進数文字列へ変換して出力する。 <bits>の桁数出力される。
┘
〔文字列クラス〕

■テンプレート定義情報

●basic_string<>

  STL文字列コンテナの本体は、basic_string<>を基底としている。
// basic_string<> ： #include <string>
namespace std {
template<  class charT,
class traits = char_traits<charT>,
class Allocator = allocator<charT> >
class basic_string ;
}

  charT は、文字列の文字の型を表す。 traits は、文字の演算や比較、コピーの仕方を記述した特性クラスを意味する。

●string/wstring

  stringヘッダでは、一般的な文字列クラスを表す型情報を以下のように string/wstring として事前定義している。
// string/wstring ： #include <string>
namespace std {
typedef basic_string<char> string ;
typedef basic_string<wchar_t> wstring ;
}

  char型/ワイドchar型の基本的な2種類の文字列クラスを表している。

┘

■コンストラクタ／デストラクタ

string s
 空文字列の s を生成する。
string s(str)
 str 文字列を複製した s を生成する。
string s(str, stridx)
 str 文字列のインデックス stridx から始まる文字列の最後までを複製した s を生成する。
string s(str, stridx, strlen)
 str 文字列のインデックス stridx から始まる文字列の文字数 strlen 分を複製した s を生成する。
string s(cstr)
 Cの文字列(NULLで終わるchar*)の複製した s を生成する。
string s(cstr, strlen)
 Cの文字列配列(char*)の strlen 文字数分複製した s を生成する。
string s(beg, end)
 [beg,end) の範囲の文字で初期化した s を生成する。
s.~string()
 全ての文字を破棄し、メモリを解放する。
┘

■文字列クラスとCの文字列

文字列クラスの内容をC言語に準拠した文字列へ還元する方法は、下記の３つの方法が存在する。
  1. data()　メソッドを利用する。　このメソッドは、文字列をCの配列として返す。　注意しなければならないのは、文字の終わりにヌルターミネート '\0' を付加しない点。
  2. c_str()　メソッドを利用する。　このメソッドは、文字列をCの文字列へと復元する。　文字列の終わりには、ヌルターミネート '\0' が付加される。
  3. copy()　メソッドを利用する。　このメソッドは、 C配列へ文字列を複写する。　ただし、 '\0' は付加されないので注意。
＜例＞
int number = atoi(s.c_str()) ; // 文字列を整数に変換
fwrite(s.data(),sizeof(char),s.length(),fp) ; // ストリームへ出力
s.copy(buffer,100) ; // buffer配列へ１００文字出力
s.copy(buffer,80,20) ; // buffer配列へ２１文字目から８０文字出力
┘

■サイズと容量

  文字列型のサイズについては、次の３種類が存在する。
  1. size() と length() については、両方とも現在格納されている文字数を返す。　２つの関数の戻り値は等価であるのでどちらを利用しても構わない。 また、文字数が存在するかどうかを確かめるには、empty() メソッドを利用すれば良いしこの方がある程度処理速度が速い。
  2. max_size() 一つの文字列空間に対して最大の格納できる領域の大きさを表した数値を返す。　通常はインデックス表現が出来る最大の整数要素(INT_MAX等）だが、環境によっては、max_size() を利用し、割り当てられる領域に制限を加えているものも中にはある。
  3. capacity() 内部割り当ての再割り当てを行わずに文字が格納できる最大数を返す。 reserve() メソッドを利用するとこのサイズに事前的な割り当てサイズを指定できる。
  reserve() メソッドについては、次の２種類が存在する。
s.reserve(800) ; // 800文字分予約する。
s.reserve() ; // 現在の文字数に縮小して再割り当てを行う。
┘

■要素のアクセス

  データ要素へのアクセスについては、イテレータでアクセスする他に配列へのアクセスがサポートされる。
  1. s[index] アクセスが許される範囲は、0～length()　まで。 const string 型は、 0～length()-1 となっている。 const でない string については、length() 位置はヌルターミネート '\0' を返す。 文字の範囲を超した範囲の index については、例外が送出されないため、未定義のふるまいとなる。 アンバサンド(&)演算子を利用すると、その文字のポインタの位置を取得できるが、データの再割り当てが行われると無効になる( e.g. &s[index] )。
  2. s.at(index) アクセスが許される範囲は、0～length()-1 まで。　その範囲を超した場合は、out_of_range 例外を発生させる。
┘

■文字列の比較

  文字列を比較するには、次の２通りの方法がある。　どちらも辞書順序優先の比較が行われる。
  1. s1 op s2 比較演算子でコンペアする。 opには、< > <= >= == != が指定できる。 s1 、 s2 どちらか一方が char* 型でも構わない。
  2. s1.compare(s2) 辞書順序優先での比較結果をそのまま返す。　要するに、 strcmp(s1.c_str(),s2.c_str()) と同じ結果を返す。 compare　のフォーマットには他に、 s1.compare(s1_idx, s1_len, s2) / s1.compare(s1_idx, s1_len, s2, s2_idx, s2_len) のように、インデックスと文字数を指定して比較するメソッドを用意している。 s2側は、char* 型でも構わない。
┘

■文字列の変更

●代入

  文字列を変更して新しい値を代入するには、 = 演算子か、assign() メソッドを利用する。
s1 = s2 ;
= 演算子の場合、s2は、文字列クラス以外に、 char * 型、 char 型でも構わない。
s1.assign(s2) ;
s1.assign(s2,s2_idx,s2_len) ;
s1.assign(num,c);
s.assign(beg,end);
  一番目の方法は、s2 の内容を s1 にそのまま代入する。 二番目の方法は、s2 の指定したインデックスから指定文字数分を代入する。　三番目の方法は、 cという文字の複製をnum個作成した文字列を代入する。 四番目の方法は、[beg,end)間の文字を代入する。 s2は、char*型でも構わない。

●値の交換

  値の内容を交換するには、swap() メソッドを利用する。
s1.swap(s2) ;
  以前説明した通り、swap() はメモリの参照等の交換だけで済むので非常に高速であることを保証している。

●文字列のクリア

  文字の消去については、３通りの方法が存在する。　処理内容についてどれも同じである。
s = "" ;
s.clear() ;
s.erase();

●文字列の挿入と削除

  『追加』については、+=演算子、append()、push_back() メソッドを利用する。
s1 += s2 ... ; // s2 は、"AAA" , 'A' でも構わない。
s1.append(s2) ; // s2 は、"AAA" でも構わない。
s1.append(s2,s2_idx,s2_len) ;
s.push_back(c); // 'A'
  『挿入』については、insert() メソッドを利用する。
s1.insert(s1_idx,s2) ; // s2 は、"AAA" でも構わない。
s1.insert(s1_idx,s2,s2_idx,s2_len);
s.insert(pos,c) ; // pos 反復子の位置に c を挿入。
s.insert(idx,num,c) ; // c文字 の複製 n 個 idx 位置へ挿入。
s.insert(pos,num,c) ;
  上記の２種類は、idx と pos が NULL の時にコンフリクトを起こすので、インデックス値0の場合は、敢えて型を明記しなければならない。
s.insert((std::string::size_type)0,num,c) ;
s.insert(pos,beg,end) ; // 反復子を利用した挿入。
  『削除』については、erase() メソッドを利用する。
s.erase(idx) ; // idx の位置の文字を抹消する。
s.erase(idx,num) ; // idx から始まる文字を num 文字抹消する。
s.erase(beg,end) ; // 反復子を利用した削除。
  『置換』については、replace() メソッドを利用する。
s1.replace(s1_idx,s1_repnum,s2) ; // s2 は、"AAA" でも構わない。
  上記は、s1_idx 位置から始まる s1_repnum　個分の部分文字列を s2 で置き換える。
s1.replace(beg,end,s2 または、c) ; // 反復子を利用した置換。
s1.replace(beg,end,s2,num) ;
s1.replace(beg,end,newBeg,newEnd) ;
┘

■文字列の部分処理

  部分文字列の『抽出』については、substr() を利用する。
s.substr() ; // 文字列全体の複製
s.substr(idx) ; // idx 位置から残り最後まで。
s.substr(idx,num) ; // idx 位置から num 文字分。
  文字列の『結合』については、+演算子を利用する。
s = s1 + s2 + s3 + ....
┘

■入出力演算子

  ストリームに文字列を出力する場合は、 << , >> 演算子を利用する。
std::cin >> s ;
std::cout << s ;
  また、ストリームから１行を読み込むには、getline() を利用する。
while(getline(std::cin,s)) ... ;
while(getline(std::cin,s,c)) ... ; // c は、'A'のような文字型。
  改行以外文字をトークンセパレータとして利用したい場合は、上記 c のように指定すると働く。
┘

■文字列の検索

  文字列を検索するメソッドは、多数存在するが、引数等は全く同じもので名前で意味が異なってくる。
find()
 指定された文字にマッチする最初に出現する位置を探す。
rfind()
 指定された文字にマッチする最後に出現する位置を探す。
find_first_of()
 指定された文字が１文字でも含まれていたなら、最初に現われた位置を返す(候補としての文字検索)。
find_last_of()
 指定された文字が１文字でも含まれていたなら、最後に現われた位置を返す(候補としての文字検索)。
find_first_not_of()
 指定された文字が１文字も含まれていない、最初の位置を探す(候補としての文字検索)。
find_last_not_of()
 指定された文字が１文字も含まれていない、最後の位置を探す(候補としての文字検索)。

  ( ) に指定される引数は、次の通り：

１番目の引数には、探す文字列を指定する。
２番目の引数には、探索開始のインデックスを指定する。（オプション）
３番目の引数には、探索開始のインデックスからの探索有効文字数を指定する。（オプション）
  どのメソッドも見つからなければ、string::npos を返す。
┘

■文字列の反復子

  文字列も他のコンテナ同様に反復子を取得し利用できる。
s.begin()
 最初の文字のランダムアクセス反復子を返す。
s.end()
 最後の文字の次の位置を示すランダムアクセス反復子を返す。
s.rbegin()
 逆の反復処理を行う際の、最初の文字を示す逆反復子を返す（つまり一番最後の文字の位置）。
s.rend()
 逆の反復処理を行う際の、最後の文字の次の位置を示す逆反復子を返す（つまり一番最初の文字よりも一つ前の位置）。
┘

■char_traits<>特性テンプレート

  文字列テンプレートの２番目のテンプレート引数 char_trais<> を書き換えると、比較や検索／コピーの仕方に対応できる。
  以下は、デフォルトのcharの特性テンプレート。
// char_traits<> ： #include <string>
namespace std {
template<charT> struct char_traits<char> {
・・・
};
template<> struct char_trais<char> {
    //型定義
    typedef char      char_type  ; //文字の型
    typedef int       int_type   ; //EOF表記の型
    typedef streampos pos_type   ; //ストリーム位置の型
    typedef streamoff off_type   ; //ストリーム位置間の型
    typedef mbstate_t state_type ; //マルチバイトストリームの状況型
    //関数
    static void assign(char& c1, const char& c2) {
      // c2 の文字を c1 に代入する
      c1 = c2 ;
    }
    static bool eq(const char& c1, const char& c2) {
      // c1 の文字と c2 が等しいかどうか
      return c1 == c2 ;
    }
    static bool lt(const char& c1, const char& c2) [
      // c1 の文字が c2 より小さいかどうか
      return c1 < c2 ;
    }
    static size_t length(const char* s) {
      // s 文字列の長さを返す
      return strlen(s) ;
    }
    static char* compare(const char* s1, const char* s2, size_t n) {
      // s1 文字列と s2 文字列を n 文字比較する
      return memcmp(s1,s2,n) ;
    }
    static char* copy(char* s1, const char* s2, size_t n) {
      // s2 の文字列から s1 へ n 文字複写する
      return (char*)memcpy(s1,s2,n) ;
    }
    static char* move(char* s1, const char* s2, size_t n) {
      // s2 の文字列から s1 へ n 文字複写する(重複の許可)
      return (char*)memmove(s1,s2,n) ;
    }
    static char* assign(char* s, size_t n, char c) {
      // s を n 文字分 c 文字で満たす
      return (char*)memset(s,c,n);
    }
    static const char* find(const char* s, size_t n,
                            const char& c) {
      // s 文字列から c を探してそのポインタを返す
      return (const char*)memchr(s,c,n);
    }
    static int eof() {
      // ストリームの終端(EOF)を返す
      return EOF ;
    }
    static int to_int_type(const char& c) {
      // c を int(ストリーム)表記として正しく返す
      return (int)(unsigned char)c ;
    }
    static char to_char_type(const int& i) {
      // i を char 表記として正しく返す
      return (char) i ;
    }
    static int not_eof(const int& i) {
      // EOF である場合は、EOF以外を、それ以外はそのまま返す
      reutrn i!=EOF ? i: !EOF ;
    }
    static bool eq_int_type(const int& i1, const int& i2) {
      // ストリーム文字の等価比較
      reutrn i1 == i2 ;
    }
};
}
  これを継承して作成する簡単な例として、下記のように大／小文字を区別しない文字列特性を自作することも出来る。

//文字列の大／小文字を区別しない文字列特性クラス
struct ignorecase_traits : public std::char_traits<char> {
    // c1 の文字と c2 が等しいかどうか
    static bool eq(const char& c1, const char& c2) {
        return std::toupper(c1)==std::toupper(c2);
    }
    // c1 の文字が c2 より小さいかどうか
    static bool lt(const char& c1, const char& c2) {
        return std::toupper(c1)<std::toupper(c2);
    }
    // s1 文字列と s2 文字列を n 文字比較する
    static int compare(const char* s1, const char* s2,
                       std::size_t n) {
        for (std::size_t i=0; i<n; ++i) {
            if (!eq(s1[i],s2[i])) {
                return lt(s1[i],s2[i])?-1:1;
            }
        }
        return 0;
    }
    // s 文字列からc を探してそのポインタを返す
    static const char* find(const char* s, std::size_t n,
                            const char& c) {
        for (std::size_t i=0; i<n; ++i) {
            if (eq(s[i],c)) {
                return &(s[i]);
            }
        }
        return 0;
    }
};

// 文字列を比較しない文字列型の定義
typedef std::basic_string<char,ignorecase_traits> icstring;

// この型用に用意した出力ストリーム用の << 演算子の定義
std::ostream& operator << (std::ostream& strm, const icstring& s)
{
    // string 型に変換して偽装工作
    return strm << std::string(s.data(),s.length());
}
┘
〔valarray〕　valarray 自体は数値配列に特化した一括演算クラスである。　valarray の設計者は、途中で撤収してしまったという逸話も聞かされるが、現時点の仕様でも差し障りなく利用できる仕様には違いない。　ただし、将来的にこのvalarrayがどのように拡張されていくかは、今のところ不明である。 また、このクラス自体の設計については、最後まできちんとテストされていないため、slice関係のサブセットについてvalarrayのサブセット同士を演算させるために一々型キャストしなければいけない所など、不完全な部分が目立つ。

■テンプレート定義情報

// valarray<> ： #include <valarray>
namespace std {
template<class T> class valarray ; // T型の整数配列
class slice ; // ２次元スライス
template<class T> class slice_array ;
class gslice ; // 多重構造のスライス
template<class T> class gslice_array ;
template<class T> class mask_array ; // マスクしたvalarray
template<class T> class indirect_array  ; // 間接参照のvalarray
}
  • 　valarray は、主に利用される中核クラス。
  • 　slice, gslice は、valarray を行列等で使用する多次元構造の一部を抽出するために用いる。
  • 　slice_array, gslice_array, indirect_array は、内部で利用される型情報でユーザーインターフェイスとしては利用できない。
┘

■コンストラクタ／デストラクタ

valarray<T> va
 空の valarrray を生成する。　resize(n) で設定すると後で容量が調整できる。
valarray<T> va(num)
 T型のデフォルトコンストラクタで作成された値を num 個含む valarray を生成する。
valarray<T> va(value,num)
 T型の value を num 個含む valarray を生成する。
valarray<T> va(array,num)
 T*型の array ポインタから始まる num 個の配列を複写して valarray を生成する。
valarray<T> va(va2)
 va2 というもう一つの valarray を複写して初期化した valarray を生成する。
va.~valarray<T>()
 全ての値を破棄し、メモリを解放する。
┘

■配列の一括演算

  valarray は、主に、配列の一括演算を迅速に処理するためのものである。　ここでは、その演算方法について色々と述べていこう。

valarray は、ランダムアクセス機能を搭載したコンテナと同様に [ ] 演算子を利用できる。

va[0] = 3 * va[1] + va[2] ;
  また、valarray 同士を計算に利用することも出来る。
va1 = 4 * va2 + va3 ;
  上記は、下記と同じ演算結果をもたらす。
va1[0] = 4 * va2[0] + va3[0] ;
va1[1] = 4 * va2[1] + va3[1] ;
va1[2] = 4 * va2[2] + va3[2] ;
                    ・
                    ・
                    ・
va1[n-1] = 4 * va2[n-1] + va3[n-1] ;
  演算に利用される型は、必ず一致していなければならない。
std::valarray<double> va(20) ;
va = 4 * va ; // エラー( 4 は、整数であるので型が一致しない。）
va = 4.0 * va ; // OK
  上記の演算は、比較演算子についても同じことが言える。　通常コンテナでの比較では結果は一つだが、valarray コンテナでは同じ要素分の論理値が格納できる valarray が必要となる。
std::valarray<double> va1(10) ;
std::valarray<double> va2(10) ;
std::valarray<bool> vaResult(10) ;
  …
vaResult = (va1 == va2) ;
  上記もまた、下記と同じ演算結果をもたらす。
vaResult[0] = ( va1[0] == va2[0] ) ;
vaResult[1] = ( va1[1] == va2[1] ) ;
vaResult[2] = ( va1[2] == va2[2] ) ;
                       ・
                       ・
                       ・
vaResult[9] = ( va1[9] == va2[9] ) ;
  すべての値を同じ値にするには、下記のように値を直接代入する。
va = value ;
  また、付属メソッドの min(),max(),sum() を利用すると　最小／最大／合計 を求めることが出来る。
min_value = va.min() ;
max_value = va.max() ;
total_value = va.sum() ;
  valarray は、この他にも要素全体をシフトして新しい valarray を返すメソッドも用意している。
newva = va.shift(num) ;
newva = va.cshift(num) ;
  num が正の場合は、先頭方向へ。負の場合は、末尾方向へシフトする。
  shift では、先頭方向へシフトする場合は、先頭にあった要素は切り捨てられる。逆に、末尾方向へシフトした場合は、デフォルトコンストラクタで生成された要素が先頭へ挿入される。
  cshift では、どちらの方向でも要素の削除や追加は行われずに単に要素を循環させる。
┘

■超越関数

  valarray については、配列の一括演算を行えるのと同じように超越関数( valarray に対して行われる一括算術関数)をいくつか用意している。
vaResult = sqrt(va1) + va2 ;
  上記は、下記と同じ演算結果をもたらす。
vaResult[0] = sqrt(va1[0]) + va2[0] ;
vaResult[1] = sqrt(va1[1]) + va2[1] ;
vaResult[2] = sqrt(va1[2]) + va2[2] ;
                       ・
                       ・
                       ・
vaResult[n-1] = sqrt(va1[n-1]) + va2[n-1] ;
   デフォルトで用意されている超越関数は、以下の通り...
valarray abs (const valarray& va)
valarray pow (const valarray& va1, const valarray& va2)
valarray pow (const valarray& va, const T& value)
valarray exp (const valarray& va)
valarray sqrt (const valarray& va)
valarray log (const valarray& va)
valarray log10 (const valarray& va)
valarray sin (const valarray& va)
valarray cos (const valarray& va)
valarray tan (const valarray& va)
valarray sinh (const valarray& va)
valarray cosh (const valarray& va)
valarray tanh (const valarray& va)
valarray asin (const valarray& va)
valarray acos (const valarray& va)
valarray atan (const valarray& va)
valarray atan2 (const valarray& va1, const valarray& va2)
valarray atan2 (const valarray& va, const T& value)
valarray atan2 (const valarray& value, const valarray &va)
┘

■サブセット

  表題で説明した通り、設計者が途中で撤収したため、valarray のサブセットは、完全とは言えない部分が存在する。　slice や gslice で生成された slice_array 等同士をそのまま演算しようとするとコンパイルエラーが発生する。 これは、演算子がサポートされていないために起こる。
va[std::slice(0,2,3)]
  = va[std::slice(1,2,3)] * va[std::slice(2.2.3)] ; // エラー
  上記のサブセットの演算を正しく動作させるためには、下記のようにvalarrayに戻す静的型キャストをほぼ常時利用しなければならない。
va[std::slice(0,2,3)]
  = static_cast<std::valarray<double> >(va[std::slice(1,2,3)]) *
    static_cast<std::valarray<double> >(va[std::slice(2,2,3)]) ;
  もっと曖昧なキャスト表現では、
va[std::slice(0,2,3)]
  = std::valarray<double>(va[std::slice(1,2,3)]) *
    std::valarray<double>(va[std::slice(2,2,3)]) ;
  となるが、これではあまりにも不憫すぎるので、暗黙の型変換用インラインを一つ用意しておく。
template <class T> inline
std::valarray<typename T::value_type> VA(const T& valarray_subset)
{ return std::valarray<typname T::value_type> (valarray_subset); }
  これを利用すると、下記のように表記できる。
va[std::slice(0,2,3)]
  = VA(va[std::slice(1,2,3)]) *
    VA(va[std::slice(1,2,3)]) ;
  上記の場合、暗黙な型変換のための複製が生成される結果となるので、パフォーマンスの影響は回避できない。
  パフォーマンスの影響を考慮に入れるのであれば、型を明確にすべきところだろう。
typedef valarray<double> DBLVA ;
va[std::slice(0,2,3)]
  = DBLVA(va[std::slice(1,2,3)]) *
    DBLVA(va[std::slice(2,2,3)]) ;
  このように、サブセットを利用する上では、注意が必要である。

●スライス

  スライス(slice)には、下記の３つの意味を持つ引数を渡して利用する。
  1. 開始インデックス
  2. 要素数（サイズ）
  3. 要素間の距離（ストライド）　※負の値でも構わない。
  たとえば、slice を利用して　５ という位置から　７ という間隔で跳々に　４ つの要素を持ったインデックス集合は下記のようになる。
std::slice(5,4,7) // 5,12,19,26 というインデックス集合
  このインデックス集合を利用してサブセットを得るには、valarray の [ ] 演算子の引数としてこれを渡す。
va[std::slice(5,4,7)]
  この変換されたサブセットは、コンスタントでなければ、slice_array というクラス構造体へ変換される。
// valarray<>::operator[]の一部 ： #include <valarray>
namespace std {
template <class T>
class valarray {
  public:
//コンスタントなスライスセット
valarray<T> operator[] ( slice ) const ;
// スライスサブセット
slice_array<T> operator[] ( slice ) ;
} ;
}

  slice_array では、次の演算が定義されている。

  • すべての要素に、一つの値を代入する。
  • 別の valarray ( または、サブセット ) を代入する。
  • += や *= などの計算を行う代入演算子類。
  逆に言えば、これ以外の演算を行おうとするとコンパイルエラーが発生するので、前書きに書いたような　valarray　への強制的な型キャストが必要になる。
va[std::slice(2,3,4)] = value ;
  上記の演算は、下記と同じ意味になる。
va[2] = value ;
va[6] = value ;
va[10] = value ;
  足し算を利用したりする場合は、前述で示した通り、valarray へキャストしてやる必要がある。
va[std::slice(0,2,3)]
  = VA(va[std::slice(1,2,3)]) +
    VA(va[std::slice(2,2,3)]) ;
  図で表すと、以下のようになる。
va[0] = va[1] + va[2] ;
va[3] = va[4] + va[5] ;

●多重構造のスライス

  スライスは、二次元に対する要素の切り分けを行っていたが、多重構造のスライスは、多次元構造にネストした要素の切り分けを行うことが出来る。　多重構造スライス gslice に受け渡す３つのパラメータは、slice と変わらないが、2番目と3番目の引数が valarray<size_t>型の 配列である点が違う。
  1. 開始インデックス
  2. valarray<size_t>型の要素数（サイズ）
  3. valarray<size_t>型の要素間の距離（ストライド）
// valarray<>::operator[]の一部 ： #include <valarray>
namespace std {
template <class T>
class valarray {
  public:
//コンスタントな多重構造のスライスセット
valarray<T> operator[] ( const gslice& ) const ;
// 多重構造のスライスサブセット
gslice_array<T> operator[] ( const gslice& ) ;
} ;
}

  例えば、 以下のような状態の値を gslice に渡すとする。

  1. 開始インデックス　＝　４
  2. 要素数　＝ valarray<size_t> 型であり、 3, 2, 5　の要素が順に入っているとする。
  3. 要素間の距離 ＝ valarray<size_t> 型であり、 30,10,7　の要素が順に入っているとする。
  gslice は、以下のようなインデックス情報を返す。
 4 11 18 25 32
14 21 28 35 42

34 41 48 55 62
44 51 58 65 72

64 71 78 85  92
74 81 88 95 102
  使い方は、slice の ２番目と３番目のパラメータが違うだけで全く同じである。

●マスクを利用したサブセット

  サブセットを得る方法として、スライスの他にブール値をマスクとして利用した mask_array というものがある。　これもコンスタントについては、valarray 自体が返却する。　それ以外は mask_array で返却される。
// valarray<>::operator[]の一部 ： #include <valarray>
namespace std {
template <class T>
class valarray {
  public:
// コンスタントなマスクセット
valarray<T> operator[] ( const valarray<bool>& ) const ;
// 論理値でマスクしたサブセット
mask_array<T> operator[] ( const valarray<bool>& ) ;
} ;
}

  論理値のサブセットは、結果が真であるもの意外を切り捨てる。　つまり、

va[ va < 100 ]
  は、100よりも小さい要素の集積となる。 valarray　の比較演算子については、配列の一括演算でも説明した通り、valarray<bool> を自動的に生成するので上記のように書くとそのような意味を持った論理値をマスクしたサブセットを結果として得ることができる。

●間接的なサブセット

  インデックス構造を指定して間接的にサブセットを得ることもできる。　これもコンスタントについては、valarray 自体が返却する。　それ以外は indirect_array で返却される。
// valarray<>::operator[]の一部 ： #include <valarray>
namespace std {
template <class T>
class valarray {
  public:
// コンスタントなインデックスセット
valarray<T> operator[] ( const valarray<size_t>& ) const ;
// インデックスで指定したサブセット
indirect_array<T> operator[] ( const valarray<size_t>& ) ;
} ;
}

  間接的なサブセットとは名前だけで、インデックス構造を指定した要素をそのままサブセットとして返す。 間接が何処にかかっているかというと、要素をインデックスが間接的に示されているところを言っている。 いわゆる、valarray のインデックスによる間接である。

valarray<int> va(10) ;
for(int i=0;i<va.size();i++)
  va[i] = i*10 ;
valarray<size_t> idx(4) ;
idx[0] = 7 ; idx[1] = 5 ; idx[2] = 2 ; idx[3] = 3 ;
for(int i=0;i<idx.size();i++)
  cout << VA(va[idx])[i] ;
cout << endl ;
  上記のプログラムは、結果として 70, 50, 20, 30 を　画面に出力する。

┘