〔ＳＴＬ-コンテナ〕

■コンテナ共通の項目

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

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

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

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 の特徴

 

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

 

ビットでbool値を表現するため、普通にvectorのboolを宣言した場合のサイズ的な問題が1/8サイズに縮小されている。 ビット演算に特化したため、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 の特徴

 

要素の挿入と削除は、先頭と末尾の両端で高速である。　逆に、コレクションの途中に要素を追加／削除する作業は遅くなる。 dequeの領域は、直線上のベクトル構造に見えるが、内部構造自体は同一メモリ上に配置されていないため、反復子はスマートポインタで構成される。 dequeは、再割り当ての容量調整機能をサポートしていない（capacity/reserveメソッドが無い）　そのため、要素を追加／削除した場合にいつ反復子が無効になるのかは不明である。　追加／削除した後は、反復子をdequeから再取得する必要性が生じる。 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 の特徴

 

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

• 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) に指定される演算の戻り値の必要条件について Compare(x,y) が真ならば、Compare(y,x) は偽になる。 Compare(x,y) が真かつ、Compare(y,z) が真ならば、Compare(x,z) は真になる。 Compare(x,x) は必ず偽になる。

set/multiset の特徴

 

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

• 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) に指定される演算の戻り値の必要条件について Compare(x,y) が真ならば、Compare(y,x) は偽になる。 Compare(x,y) が真かつ、Compare(y,z) が真ならば、Compare(x,z) は真になる。 Compare(x,x) は必ず偽になる。

map/multimap の特徴

 

map/multimap は、キーを比較準拠関数オブジェクトでソートした平衡二分木として実装される。　各々の要素は、キーと値のペアで組み合わせられる。 mapは、キーの重複を許さない一方で multimapは、キーの重複を許す。 登録したキーの値を変更する行為は、ソート準拠に反するためサポートされない。（値は変更可能） 要素の順序は、不定形であるため、要素自体を直接アクセスするメソッドは利用できない。　一方で　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)) ;


 

┘

■反復子の種類

 

反復子の機能

入力反復子	前方に向かって読み取る。	入力ストリーム
出力反復子	前方に向かって書き込む。	出力ストリーム、挿入反復子
前方反復子	前方に向かって読み書きする。
双方向反復子	前方・後方に向かって読み書きする	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　となる。
• 戻り値は、書き込みが終了した位置より一つ大きい位置を返す。

┘