アルゴリズムと関数オブジェクト

標準C++にはコンテナに対する最も一般的で基本的なニーズに答える70もの汎用アルゴリズムが用意されている．これらはコンテナを本当に役に立つようにするためのもので，サイズ判定，コピー，反復操作，整列，探索などの基本演算からなっている．汎用アルゴリズムはすべてstd名前空間に含めれており，その宣言は$<$algorithm$>$に含まれている．

関数オブジェクト(Function Objects)

多くのアルゴリズムは，反復子を用いてシーケンスと値だけを用いて動作する．例えば，find()アルゴリズムを使えば，シーケンスに含まれる値3の最初の要素を探すことができる．
　void f(list$<$int$>$& l)
　{
　　list$<$int$>$::iterator it = find(l.begin(), l.end(), 3);
　．．．
　}

しかし，これよりも面白いことができるようになっている．それは，アルゴリズムにユーザが作成したコードを実行させることである．例えば，3よりも小さな値をもつ最初の要素は，次のようにして探すことができる．
　bool less_than_3(int v)
　{
　　return v < 3; 　}
　void f(list$<$int$>$& l)
　{
　　list$<$int$>$::const_iterator p = find_if(l.begin(), l.end(), less_than_3);
　　．．．
　}

引数として関数を渡す方法には，さまざまな用途がある．例えば，論理判定，算術演算，要素からの情報の抜き出しなどである．このような関数をいちいち別に書いていたのでは不便だし効率的でもない．また，1つの関数では表現したいことをすべて表現するためには論理的に無理な場合もある．ここの要素のために呼び出される関数は，関数の呼び出しの間でデータを保持しなければならないことが多いし，複数回に渡る適用の結果を返さなければならないことも多い．クラスのメンバ関数はデータを保持するオブジェクトの助けを借りられるので，独立した関数よりもこのニーズにうまく答えられることが多い．さらに，クラスはデータの初期設定，取得のための演算を提供できる．

ここで，和を求める関数的クラスの書き方について考えてみる．
　template$<$class T$>$ class Sum {
　　　T result;
　　public:
　　　Sum(T i=0) : result(i) {} //初期設定
　　　void operator()(T x){result += x;}//合計を取得
　　　T result() const {return result;}//合計を返す
　};

Sumは0による初期設定と+=演算子が定義されている算術型のために設計されている．例えば，次のようになる．
　void f(list$<$double$>$& ld)
　{
　　Sum$<$double$>$ s;
　　s = for_each(ld.begin(), ld.end(), s);
　　cout $<<$ "the sum is " $<<$ s.result() $<<$ endl;
　}

これがうまく機能する理由は，for_eachが第3引数を関数と見なしていないからである．for_each()は，適切な引数つきで呼び出せるものとして第3引数を見ている．適切に定義されたオブジェクトは，関数と同等に動作する．または，よりよく機能することも多い．なぜならば，クラスの関数呼び出し演算子の方が，関数ポインタとして渡された関数よりもインライン化しやすい．したがって，関数オブジェクトは通常の関数よりも高速実行されることが多い．関数呼び出し演算子を持つクラスのオブジェクトは，関数的オブジェクトあるいは単純に関数オブジェクトと呼ばれる． 標準関数オブジェクトもstd名前空間に含まれているが，宣言は$<$functional$>$に含まれている．

叙述関数(Predicate Functions)

boolを返す関数または関数オブジェクトを叙述関数という．例えば，$<$functional$>$では次のものを定義している．

template $<$class T$>$ struct logical_not:public unary_function$<$T, bool$>${
　　bool operator()(const T& x) const {return !x;}
　};

アルゴリズムで叙述関数を用いるものには次のようなものもある．

　class Odd
　{
　　public:
　　　bool operator()(int n) {return n%2 ? true : false;}
　};

このクラスはOdd()関数として渡される．

　int main()
　{
　　int a[] = {0,1,0,1,1,1,0,1,1,0}
　　print(a,10);
　　int n = count_if(a,a+10,Odd());
　}

ForwardIterator	Fit	BidirectionIterator	Bit	InputIterator	In
OutputIterator	Out	RandomAccessIterator	Rit	Predicate	Pre
UnaryOperation	Una	Generator	gen

探索と整列アルゴリズム$<$algorithm$>$
binary_search()	2分探索法で探索を行なう
template $<$class Fit, class T$>$ bool binary_search(Fit first, Fit last, const T& value)
inplace_merge()	2つの連続した整列済み部分シーケンスを結合する
template $<$class Bit, class T$>$ void inplace_merge(Bit first, Bit middle, Bit last)
lower_bound()	値が最初に現れた場所を探索する
template $<$class Fit, class T$>$ Fit lower_bound(Fit first, Fit last, const T& value)
merge()	2つの整列済みシーケンスを結合する
template $<$class In1, class In2, class Out$>$ Out merge(In first1, In last1, In first2,
In last2, Out result)
nth_element()	n番目の要素を適切な位置に移動する
template $<$class Rit$>$ void nth_element(Rit first, Rit nth, Rit last)
partial_sort()	シーケンスの先頭部分を並べ替える
template $<$class Rit$>$ void partial_sort(Rit first, Rit middle, Rit last)
partial_sort()_copy()	先頭部分を並べ替えたシーケンスのコピーを作る
template $<$class In, class Rit$>$ Rit partial_sort_copy(In first, Int last,
Rit result_first, Rit result_last)
partition()	関数P(x)を満足させる要素を先頭にまとめる
template $<$class Bit, class Pre$>$ Bit partition(Bit first, Bit last, Pre pred)
sort()	平均時間計算量が少ない方法で整列を行なう
template $<$class Rit$>$ void sort(Rit first, Rit last)
upper_bound()	指定された値と同じ大きさをもつシーケンス
	最後の要素を探索する
template $<$class Fit, class T$>$ Fit upper_bound(Fit first, Fit last, const T& value)

変更なしのシーケンスアルゴリズム$<$algorithm$>$
adjacent_find()	シーケンスで最初に隣り合う値の対を探索する
template $<$class Fit$>$ Fit adjacent_find(Fit first, Fit last)
count()	指定された値の個数を返す
template $<$class In, class T$>$ typename it erator_traits$<$In$>$::difference_type
count(In first, In last, const T& value);
count_if()	指定された関数P(x)を満たす要素の個数を返す
template $<$class In, class Pre$>$ typename iterator_traits$<$In$>$::difference_type
count(In first, In last, Pre pred);
equal()	2つのシーケンスの要素が対単位で等しいときに真を返す
template $<$class In1, class In2$>$ bool equal(In first1, In last1, In first2)
find()	シーケンス内で指定された値が最初に現れる要素を探索する
template $<$class In, class T$>$ In find(In first, In last, const T& value);
find_first_of()	あるシーケンスから別のシーケンスに含まれている要素を探索する
template $<$class Fit1, class Fit2$>$ Fit1 find_first_of(Fit1 first1, Fit1 last1,
Fit2 first2, Fit2 last2);
find_if()	シーケンス内で指定された関数P(x)を満足させる
	最初の要素を探索する
template $<$class In, class Pre$>$ In find(In first, In last, Pre pred);
for_each()	シーケンス内の個々の要素を操作する
template $<$class In, class Function$>$ Function for_each(In first, In last, Function f);
mismatch()	2つのシーケンスが最初に違いを見せる位置を探索する
template $<$class In1, class In2$>$ pair$<$In1, In2$>$ mismatch(In1 last1, In2 first2);
search()	部分シーケンスが最初に現れる位置を返す
template $<$class Fit1, class Fit2$>$ Fit1 search(Fit1 first1, Fit1 last1, Fit2 first2, Fit2 last2);
search_n()	指定された値がn番目に現れる位置を返す
template $<$class Fit, class Size, class T$>$ Fit search_n(Fit first, Fit last,
Size count, count T& value);

シーケンス変更アルゴリズム$<$algorithm$>$
copy()	先頭要素を出発点としてシーケンスをコピーする
template $<$class In, class Out$>$ Out copy(In first,In last, Out resutl);
copy_backward()	末尾の要素を出発点としてシーケンスをコピーする
template $<$class Bit1, class Bit2$>$ Bit2 copy_backward(Bit1 first,Bit1 last, Bit2 resutl);
fill()	指定された値を持つすべての要素を置換する
template $<$class Fit, class T$>$ void fill(Fit first, Fit last, const T& value);
fill_n()	指定された値を持つ先頭からn個の要素を置換する
template $<$class Fit, class T$>$ void fill(Fit first, Fit last, const T& value);
generate()	ある演算の結果によってすべての要素を置換する
template $<$class Fit, class Gen$>$ void generate(Fit first, Fit last, Gen gen);
generate_n()	ある演算の結果によって先頭からn個の要素を置換する
template $<$class Out, class Size, class Gen$>$ void generate_n(Out first, Size n, Gen gen);
iter_swap()	反復子が指す2つの要素を交換する
template $<$class Fit1, class Fit2$>$ void iter_swap(Fit1 a, Fit2 lb);
random_shuffle()	要素を均質に分散させる
template $<$class Rit$>$ void random_shuffle(Rit first, Rit last);
remove()	指定された値を持つ要素を削除する
template $<$class Fit, class T$>$ void remove(Fit first, Fit last, const T& value);
remove_copy()	指定された値を削除されたシーケンスのコピーを作る
template $<$class In, class Out, class T$>$ Out remove_copy(In first, In last,
Out result, const T& value);
remove_copy_if()	指定された関数P(x)を満たす要素を削除した
	シーケンスのコピーを作る
template $<$class In, class Out, classPre$>$ Out remove_copy(In first, In last,
Out result, Pre pred);
remove_if()	指定された関数P(x)を満たす要素を削除する
template $<$class Fit, class Pre$>$ Fit remove_if(Fit first, Fit last, Pre pred);
replace()	指定された値を持つ要素を置換する
template $<$class Fit, class T$>$ void replace(Fit first, Fit last,
const T& old_value, const T& new_value);
replace_copy()	指定された値を持つ要素を置換したシーケンスのコピーを作る
template $<$class In, class Out, class T$>$ Out replace_copy(In first,
In last, Out result, const T& old_value, const T& new_value);
replace_copy_if()	指定された関数P(x)を満たす要素を置換した
	シーケンスのコピーを作る
template $<$class In, class Out, class Pred, class T$>$ Out replace_copy_if(In first,
In last, Out result, Pre pred, const T& new_value);
replace_if()	指定された関数P(x)を満たす要素を置換する
template $<$class Fit, class Pre, class T$>$ void replace_if(Fit first, Fit last,
Pre pred, const T& new_value);

reverse()	要素の順を逆にする
template $<$class Bit$>$ void reverse(Bit first, Bit last);
reverse_copy()	要素の順を逆にしたシーケンスのコピーを作る
template $<$class Bit, class Out$>$ Out reverse_copy(Bit first, Bit last, Out result);
rotate()	要素を回転させる
template $<$class Fit$>$ void rotate(Fit first, Fit middle, Fit last);
rotate_copy()	要素を回転させたシーケンスのコピーを作る
template $<$class Fit, class Out$>$ Out reverse_copy(Fit first,
Fit middle, Fit last, Out result);
swap()	2つの要素を交換する
template $<$class T$>$ void swap(T& a, T& b);
transform()	シーケンスのすべての要素にある演算を適用し，
	その結果を別のシーケンスに格納する
template $<$class In, class Out, class Una$>$ Out transforme(In first,
In last, Out resutl, Una op);
unique()	隣り合う等しい要素を削除する
template $<$class Fit$>$ Fit unique(Fit first, Fit last);
unique_copy()	隣り合う等しい要素を削除されたシーケンスのコピーを作る．
template $<$class In, class Out$>$ Out unique_copy(In first, In last, Out result);

比較アルゴリズム$<$algorithm$>$
lexicographical_compare()	2つのシーケンスの冒頭部を辞書的に比較する
template $<$class In1, class In2$>$ bool lexicographical_compare(In1 first1,
In1 last1, In2 first2, In2 last2);
max()	2つの値の中で大きいほうを選択する
template $<$class T$>$ const T& max(const T& a, cosnt T& b);
max_element()	シーケンスの中で最も大きい要素を選択する
template $<$class Fit$>$ Fit max_element(Fit first, Fit last);
min()	2つの値の中で小さいほうを選択するす
template $<$class T$>$ const T& min(const T& a, cosnt T& b);
min_element()	シーケンスの中で最も小さい要素を選択する
template $<$class Fit$>$ Fit min_element(Fit first, Fit last);

集合アルゴリズム$<$algorithm$>$
includes()	シーケンスがもう一つのシーケンスに含まれていれば
	真を返す
template $<$class In1, class In2$>$ bool includes(In1 first1,
In2 first2, IN2 first2, In2 last2);
set_difference()	整列済みの差集合を作る
template $<$class In1, class In2, class Out$>$ out set_difference(In1 first1,
In1 last1, In2 first2, In2 last2, Out result);
set_intersection()	整列済みの積集合を作る
template $<$class In1, class In2, class Out$>$ out set_intersection(In1 first1,
In1 last1, In2 first2, In2 last2, Out result);
set_symetric_difference()	2つのシーケンスの対称差から別のシーケンスを作る
template $<$class In1, class In2, class Out$>$ out set_symmetric_difference(In1 first1,
In1 last1, In2 first2, In2 last2, Out result);
set_union()	整列済みの和集合を作る
template $<$class In1, class In2, class Out$>$ out set_union(In1 first1,
In1 last1, In2 first2, In2 last2, Out result);

ヒープアルゴリズム$<$algorithm$>$
make_heap()	ヒープとして使えるシーケンスを作る
template $<$class Rit$>$ void make_heap(Rit first, Rit last);
pop_heap()	最初の要素を最後に移動し，make_heap()を用いて
	ヒープを作成する
template $<$class Rit$>$ void pop_heap(Rit first, Rit last);
push_heap()	ヒープに要素を追加する
template $<$class Rit$>$ void push_heap(Rit first, Rit last);
sort_heap()	pop_heap()を用いてヒープをソートする
template $<$class Rit$>$ void sort_heap(Rit first, Rit last);

順列アルゴリズム$<$algorithm$>$
next_permuatation()	辞書的な順番で次に当たる順列を返す
template $<$class Bit$>$ bool next_permutation(Bit first, Bit last);
prev_permutation()	辞書的な順番で前に当たる順列を返す
template $<$class Bit$>$ bool prev_permutation(Bit first, Bit last);

アルゴリズムの用法

$<$algorithm$>$の演算

次のprint()関数を配列aのn個の要素a[0],a[1],...,a[n-1]を表示するのに用いる．

void print(int* a, int n)
{
　cout $<<$ "n=" $<<$ n $<<$ ": " $<<$ a[0];
　for(int i=1;i $<$ n;i++){
　　cout $<<$ "," $<<$ a[i];
　}
　cout $<<$ "" $<<$ endl;
}

例題 16.1   adjacent_find()

==============================================

int main()
{
　int a[] = {0,1,1,2,3,5,8,13,21,34};
　print(a,10);
　int* r = adjacent_find(a,a+10);
　cout $<<$ "*r=" $<<$ *r $<<$ endl;
　cout $<<$ "r-a=" $<<$ r-a $<<$ endl;
}
==============================================

例題 16.2   binary_search()

==============================================

int main()
{
　int a[] = {0,1,1,2,3,5,8,13,21,34};
　print(a,10);
　bool found = binary_search(a,a+10,13);
　cout $<<$ "found=" $<<$ found $<<$ endl;
　bool found = binary_search(a,a+7,13);
　cout $<<$ "found=" $<<$ found $<<$ endl;
}
==============================================

例題 16.3   copy()

==============================================

int main()
{
　int a[] = {0,1,1,2,3,5,8,13,21,34};
　print(a,10);
　copy(a+7,a+10,a+2);
　print(a,10);
　int b[3];
　copy(a+7,a+10,b);
　print(b,3);
}
==============================================

例題 16.4   copy_backward()

==============================================

int main()
{
　int a[] = {0,1,1,2,3,5,8,13,21,34};
　print(a,10);
　copy_backward(a+7,a+10,a+2);
　print(a,10);
　int b[3];
　copy_backward(a+7,a+10,b);
　print(b,3);
}
==============================================

標準ライブラリは$<$numeric$>$を介して，$<$algorithm$>$の非数学アルゴリズムと同じようなスタイルで汎用数学アルゴリズムを提供している．

汎用数学アルゴリズム$<$algorithm$>$
accumulate()	１つのシーケンスに対する足し算の結果を蓄積する
template $<$class In, class T$>$ T accumulate(In first, In last, T init)
adjacent_difference()	1つのシーケンスに対する演算によってシーケンスを生成する
template $<$class In, class Out$>$ Out adjacent_difference(In first, In last, Out result)
inner_product()	2つのシーケンスに対する内積の結果を蓄積する
template $<$class In1, class In2, class T$>$ T inner_product(In1 first1, In1 last1, In2 first2, T int)
partial_sum()	1つのシーケンスに対する部分和によってシーケンスを生成する
template $<$class In, class Out$>$ Out partial_sum(In first, In last, Out result)

アルゴリズムの用法

$<$numeric$>$の演算

ここでは，print()関数として
void print(const Vector& v)
{
　cout $<$$<$ "" $<$$<$ v[0];
　for(int i=1;i$<$v.size();i++){
　　cout $<$$<$ "," $<$$<$ v[i];
　}
　cout $<$$<$ "";
}
を用いる．

例題 16.5   accumulate()

==============================================

#include $<$iostream$>$
#include $<$numeric$>$
#include $<$vector$>$
using namespace std;
typedef vector$<$int$>$ Vector;
typedef vector$<$int$>$::iterator It;
void print(const Vector&);
int main()
{
　Vector v(10);
　v[0] = 0, v[1] = 1;
　for(int i=2;i$<$10;i++)
　　v[i] = v[i-1] + v[i-2];
　print(v);
　It it;
　int sum = accumulate(it=v.begin(),it+9,0);
　cout $<$$<$ "sum =" $<$$<$ sum $<$$<$ endl;
}
==============================================

例題 16.6   adjacent_difference()

==============================================

#include $<$iostream$>$
#include $<$numeric$>$
#include $<$vector$>$
using namespace std;
typedef vector$<$int$>$ Vector;
typedef vector$<$int$>$::iterator It;
void print(const Vector&);
int main()
{
　Vector v(10);
　v[0] = 0, v[1] = 1;
　for(int i=2;i$<$10;i++)
　　v[i] = v[i-1] + v[i-2];
　print(v);
　It it;
　int a[10];
　adjacent_difference(it=v.begin(),it+10,a);
　Vector w(10);
　for(int i=0;i$<$10;i++)
　　w[i] = a[i];
　print(w);
}
==============================================