C++stlアルゴリズム
24783 ワード
目次
1.概要
2一般的なアルゴリズムの概要
2.1ソートアルゴリズム
2.2関数の検索
2.3.アルゴリズムの削除と置換
2.4配列組合せアルゴリズム
2.5.数値アルゴリズム
2.6.生成と変異アルゴリズム
2.7.リレーショナルアルゴリズム
2.8.しゅうごうアルゴリズム
2.9ヒープアルゴリズム
1.概要
C++のstlについては,いくつかの基本構造といくつかの独自の関数に加えて,関数テンプレートを用いて実現されるアルゴリズムがstlをサポートしている.これらのアルゴリズムは主に、から構成されています.stlを使用するアルゴリズム関数にはヘッダファイル、数値アルゴリズムには
2一般的なアルゴリズムの概要
2.1ソートアルゴリズム sort(),stable_sort()——全要素をソートし、stable_とは異なるsort()は、等しい要素の相対関係 を保証する. partial_sort():区間全体の要素を並べ替えますが、[beg,sortend]のみを に並べ替えます. nth_Element:n番目の要素を順番に並べます.すなわち、n番目の要素のみを位置に配置し、n番目の要素より小さい要素を左側に配置し、n番目の要素より大きい要素を右側に配置します(ただし、結果はすべて並べ替えられたように見えますが、sortと区別はありませんか?) reverse:コンテナ内の要素を逆方向に格納(再ロード不可) random_shuffle:指定した範囲内の要素に対してランダムに順序を調整します. merge:2つのシーケンスを結合し、別のシーケンス に格納する
2.2関数の検索 adjacent_find():end() を返す範囲内の最初の隣接する重複要素のセットを返します. count():統計範囲内で選択された要素の個数 count_if:統計範囲内で条件を満たす要素の個数 binary_search:秩序化シーケンスで要素 を検索する equal_range:1対の反復器を返し、最初はlowerを表します.bound,2番目はupperを表すbround find():選択した要素に対応する額反復器 を範囲内で返す. find_if():範囲内で を返す search():範囲内でサブシーケンスを検索する位置 search_n():範囲内でサブシーケンスを検索してn回繰り返す位置
2.3.アルゴリズムの削除と置換 copy():コピーシーケンス copy_backward():逆レプリケーションシーケンス iter_swap:2つの反復器の値を交換する remove:指定範囲内の指定した要素と等しいすべての要素を削除する . remove_copy:一致しないすべての要素を指定されたコンテナ にコピーします. remove_if:指定範囲内の入力操作結果trueのすべての要素 を削除する. remove_copy_if:すべての不一致要素を指定されたコンテナ にコピーする replace:指定範囲の選択したすべての要素を指定要素 に置き換える. replace_copy:指定範囲の選択したすべての要素を指定した要素に置き換え、指定したコンテナ にコピーします. replace_if:指定範囲内に入力操作結果trueのすべての要素を指定要素 に置き換える. replace_copy_if:指定範囲に入力操作結果trueのすべての要素を指定要素に置き換え、指定されたコンテナ にコピーする. swap:2つのオブジェクトに格納値 を交換する. swap_range:指定範囲内の要素と別のシーケンス要素の値を交換する unique:シーケンス内の重複する要素を消去する unique_copy:シーケンス内の重複する要素を消去し、結果を別のコンテナに入力する .
2.4配列組合せアルゴリズム next_permutation:abc->acb->bac->bca->cab->cbaで選択した文字列の次の など、辞書の順序を指定します. prev_permutation:辞書の順序を示す前の
2.5.数値アルゴリズム accumulate:コンテナ内の要素の和を初期値の に加算 partial_sum:各要素が指定した先頭までの要素の和 を表す新しいシーケンスを作成します. inner_product:2つのシーケンスを内積する adjacent_difference:現在の要素と前の要素の差 を表す新しいシーケンスを作成します.
2.6.生成と変異アルゴリズム fill:フラグ範囲内の要素 に入力値を付与する. fill_n:入力値をfirstからfirst+nの範囲内のすべての要素 に割り当てる. for_each:指定関数で指定範囲内のすべての要素を順次反復アクセス generate:指定範囲 を満たすために入力関数を連続的に呼び出す. generate_n:generate関数と同様に、指定したiteratorから始まるn要素を入力します. transform:入力操作を指定範囲内の各要素に作用させ、新しいシーケンス を生成する.
2.7.リレーショナルアルゴリズム equal:両方のシーケンスがフラグ範囲内の要素が等しい場合はtrueを返します. includes:1番目の指定範囲内のすべての要素が2番目の範囲に含まれているかどうかを判断し、最下位要素の
max:2つの要素のうち大きい1つを返します.リロード・バージョンでは、カスタム比較操作を使用します. min:2つの要素のうち小さい1つを返します.リロード・バージョンでは、カスタム比較操作を使用します. max_Element:シーケンス内の最大要素を示すForwardIteratorを返します.リロード・バージョンでは、カスタム比較操作を使用します. min_Element:シーケンスの最小要素を示すForwardIteratorを返します.リロード・バージョンでは、カスタム比較操作を使用します. mismatch:2つのシーケンスを並列に比較し、最初の一致しない位置を指摘し、1対のiteratorを返し、最初の一致しない要素の位置を示す.一致する場合は、各コンテナのlastを返します.リロード・バージョンでは、カスタム比較操作が使用されます.
2.8.しゅうごうアルゴリズム set_union:2つのシーケンスのすべての重複しない要素を含む秩序化されたシーケンスを構築します.リロード・バージョンでは、カスタム比較操作が使用されます. set_intersection:要素が2つのシーケンスに存在する秩序化されたシーケンスを構築します.リロード・バージョンでは、カスタム比較操作が使用されます. set_difference:1番目のシーケンスに存在し、2番目に存在しない要素のみを保持する秩序化されたシーケンスを構築します.リロード・バージョンでは、カスタム比較操作が使用されます. set_symmetric_difference:2つのシーケンスの対称差セット(並列セット-交差)をとる秩序化シーケンスを構築します.
2.9ヒープアルゴリズム make_heap:指定した範囲内の要素をスタックに生成します.最大値が与えられた範囲の一番前にあることを保証し、他の値の位置が不確定で、リロードバージョンはカスタム比較操作を使用します. pop_Heap:スタックトップ(与えられた範囲の一番前)要素を与えられた範囲の最後に移動し、新しい最大値を与えられた範囲の一番前 に配置する. push_heap:firstからlast-1が有効なスタックであると仮定し、スタックに追加される要素を位置last-1に保存し、スタックを再生成する.この関数を指す前に、コンテナに要素を挿入してからにする必要があります.リロード・バージョンでは、指定した比較操作が使用されます.
1.概要
2一般的なアルゴリズムの概要
2.1ソートアルゴリズム
2.2関数の検索
2.3.アルゴリズムの削除と置換
2.4配列組合せアルゴリズム
2.5.数値アルゴリズム
2.6.生成と変異アルゴリズム
2.7.リレーショナルアルゴリズム
2.8.しゅうごうアルゴリズム
2.9ヒープアルゴリズム
1.概要
C++のstlについては,いくつかの基本構造といくつかの独自の関数に加えて,関数テンプレートを用いて実現されるアルゴリズムがstlをサポートしている.これらのアルゴリズムは主に、から構成されています.stlを使用するアルゴリズム関数にはヘッダファイル、数値アルゴリズムには
2一般的なアルゴリズムの概要
2.1ソートアルゴリズム
#include
#include
#include
#include // greater()
using namespace std;
//
template
struct display
{
void operator()(const T&x) const
{
cout << x << " ";
}
};
// , , :
// ,
bool Comp(const int& a, const int& b) {
return a > b;
}
int main(int argc, char* argv[])
{
int iarr1[] = { 0, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8 };
vector iv1(iarr1, iarr1 + sizeof(iarr1) / sizeof(int));
vector iv2(iarr1 + 4, iarr1 + 8); // 4 5 6 6
vector iv3(15);
/*** merge: , ***/
// iv1 iv2 iv3 ( )
merge(iv1.begin(), iv1.end(), iv2.begin(), iv2.end(), iv3.begin());
cout << "merge : ";
for_each(iv3.begin(), iv3.end(), display());
cout << endl;
/*** random_shuffle: 。 ***/
int iarr2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
vector iv4(iarr2, iarr2 + sizeof(iarr2) / sizeof(int));
//
random_shuffle(iv4.begin(), iv4.end());
cout << "random_shuffle : ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;
/*** reverse: 。 ***/
reverse(iv4.begin(), iv4.begin());
cout << "reverse : ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;
/*** partial_sort(): , [beg,sortend) 。 ***/
partial_sort(iv4.begin(), iv4.begin()+3, iv4.end());
cout << "partial_sort : ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;
random_shuffle(iv4.begin(), iv4.end());
/*** nth_element: 。 ***/
// iv.begin+5
nth_element(iv4.begin(), iv4.begin() + 5, iv4.end());
cout << "nth_element : ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;
/*** sort: 。 ***/
// sort(iv4.begin(), iv4.end(), Comp); // Comp()
sort(iv4.begin(), iv4.end(), greater());
cout << "sort ( ): ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;
/*** stable_sort: sort , 。 ***/
int iarr3[] = { 0, 1, 2, 3, 3, 4, 4, 5, 6 };
vector iv5(iarr3, iarr3 + sizeof(iarr3) / sizeof(int));
stable_sort(iv5.begin(), iv5.end(), greater());
cout << "stable_sort ( ): ";
for_each(iv5.begin(), iv5.end(), display());
cout << endl;
return 0;
}
2.2関数の検索
#include
#include
#include
#include
using namespace std;
int main(int argc, char* argv[])
{
int iarr[] = { 0, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8 };
vector iv(iarr, iarr + sizeof(iarr) / sizeof(int));
/*** adjacent_find: iterator , ***/
// : _FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last)
cout << "adjacent_find: ";
cout << *adjacent_find(iv.begin(), iv.end()) << endl;
/*** count: , , 。 ***/
// : count(_InIt _First, _InIt _Last, const _Ty& _Val)
cout << "count(==6): ";
cout << count(iv.begin(), iv.end(), 6) << endl;// 6
/*** count_if: , , true 。 ***/
// : count_if(_InIt _First, _InIt _Last, _Pr _Pred)
// 7 :9
cout << "count_if(<7): ";
cout << count_if(iv.begin(), iv.end(), bind2nd(less(), 7)) << endl;
/*** binary_search: value, true。 ***/
// : bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
cout << "binary_search: ";
cout << binary_search(iv.begin(), iv.end(), 4) << endl; // true
/*** equal_range: equal, iterator, lower_bound, upper_bound。 ***/
// : equal_range(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
pair::iterator, vector::iterator> pairIte;
pairIte = equal_range(iv.begin(), iv.end(), 3);
cout << "pairIte.first:" << *(pairIte.first) << endl;// lowerbound 3
cout << "pairIte.second:" << *(pairIte.second) << endl; // upperbound 4
/*** find: , 。 ***/
// : _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
cout << "find: ";
cout << *find(iv.begin(), iv.end(), 4) << endl; // 4
/*** find_if: find。 ***/
// : _InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
cout << "find_if: " << *find_if(iv.begin(), iv.end(), bind2nd(greater(), 2)) << endl; // 2 :3
/*** search: , ForwardIterator, 。 ***/
// : _FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1, _FwdIt2 _First2, _FwdIt2 _Last2)
// iv 2 3
int iarr3[3] = { 2, 3 };
vector iv3(iarr3, iarr3 + 2);
cout << "search: " << *search(iv.begin(), iv.end(), iv3.begin(), iv3.end()) << endl;
/*** search_n: val n 。 ***/
// : _FwdIt1 search_n(_FwdIt1 _First1, _FwdIt1 _Last1, _Diff2 _Count, const _Ty& _Val)
// iv 2 6
cout << "search_n: " << *search_n(iv.begin(), iv.end(), 2, 6) << endl;
return 0;
}
2.3.アルゴリズムの削除と置換
#include
#include
#include
#include // greater()
using namespace std;
template
struct display
{
void operator()(const T&x) const
{
cout << x << " ";
}
};
int main(int argc, char* argv[])
{
int iarr1[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
vector iv1(iarr1, iarr1 + sizeof(iarr1) / sizeof(int));
vector iv2(9);
/*** copy: ***/
// : _OutIt copy(_InIt _First, _InIt _Last,_OutIt _Dest)
copy(iv1.begin(), iv1.end(), iv2.begin());
cout << "copy(iv2): ";
for_each(iv2.begin(), iv2.end(), display());
cout << endl;
/*** copy_backward: copy , 。 ***/
// : _BidIt2 copy_backward(_BidIt1 _First, _BidIt1 _Last,_BidIt2 _Dest)
copy_backward(iv1.begin(), iv1.end(), iv2.rend());
cout << "copy_backward(iv2): ";
for_each(iv2.begin(), iv2.end(), display());
cout << endl;
/*** iter_swap: ***/
// :void iter_swap(_FwdIt1 _Left, _FwdIt2 _Right)
iter_swap(iv2.begin(), iv2.end()-1);
cout << "iter_swap(iv2.begin(), iv2.end()):";
for_each(iv2.begin(), iv2.end(), display());
cout << endl;
/*** remove: 。 ***/
// : _FwdIt remove(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
remove(iv1.begin(), iv1.end(), 5); // 5
cout << "remove(iv1): ";
for_each(iv1.begin(), iv1.end(), display());
cout << endl;
/*** remove_copy: , OutputIterator 。 ***/
// : _OutIt remove_copy(_InIt _First, _InIt _Last,_OutIt _Dest, const _Ty& _Val)
vector iv3(8);
remove_copy(iv1.begin(), iv1.end(), iv3.begin(), 4); // 4
cout << "remove_copy(iv3): ";
for_each(iv3.begin(), iv3.end(), display());
cout << endl;
/*** remove_if: true 。 ***/
// : _FwdIt remove_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
remove_if(iv3.begin(), iv3.end(), bind2nd(less(), 6)); // 6 " "
cout << "remove_if(iv3): ";
for_each(iv3.begin(), iv3.end(), display());
cout << endl;
/*** remove_copy_if: 。 ***/
// : _OutIt remove_copy_if(_InIt _First, _InIt _Last,_OutIt _Dest, _Pr _Pred)
// iv1 6 " " , iv3
remove_copy_if(iv1.begin(), iv1.end(), iv2.begin(), bind2nd(less(), 4));
cout << "remove_if(iv2): ";
for_each(iv2.begin(), iv2.end(), display());
cout << endl;
/*** replace: ***/
// :void replace(_FwdIt _First, _FwdIt _Last,const _Ty& _Oldval, const _Ty& _Newval)
replace(iv2.begin(), iv2.end(), 8, 5);
cout << "replace(iv2.begin(), iv2.end(), 8, 5): ";
for_each(iv2.begin(), iv2.end(), display());
cout << endl;
/*** replace_copy: , ***/
// :_OutIt replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest, const _Ty& _Oldval, const _Ty& _Newval):
vector iv4(8);
replace_copy(iv3.begin(), iv3.end(), iv4.begin(), 8, 5);
cout << "replace_copy(iv3.begin(), iv3.end(), iv4.begin(), 8, 5): ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;
/*** replace_if: true ***/
// :_OutIt replace_copy(_InIt _First, _InIt _Last, _OutIt _Dest, const _Ty& _Oldval, const _Ty& _Newval):
replace_if(iv3.begin(), iv3.end(), bind2nd(less(), 7), 8);
cout << "replace_if(iv3.begin(), iv3.end(), bind2nd(less(), 7), 8): ";
for_each(iv3.begin(), iv3.end(), display());
cout << endl;
/*** replace_copy_if: true , ***/
// :_OutIt replace_copy_if(_InIt _First, _InIt _Last,_OutIt _Dest, _Pr _Pred, const _Ty& _Val):
replace_copy_if(iv3.begin(), iv3.end(), iv4.begin(), bind2nd(less(), 8), 9);
cout << "replace_copy_if(iv3.begin(), iv3.end(), iv4.begin(), bind2nd(less(), 8), 9): ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;
/*** swap: ***/
// :void swap(vector<_ty _alloc="">& _Left, vector<_ty _alloc="">& _Right)
swap(iv4, iv3);
cout << "swap(iv4, iv3):iv4: ";
for_each(iv4.begin(), iv4.end(), display());
cout << " iv3: ";
for_each(iv3.begin(), iv3.end(), display());
cout << endl;
/*** swap_range: ***/
// :swap_ranges(iv4.begin()+2,iv4.end()-2,iv2.begin()+2)
swap_ranges(iv4.begin()+2,iv4.end()-2,iv2.begin()+2);
cout << "swap_ranges(iv4.begin()+2,iv4.end()-2,iv2.begin()+2):iv4: ";
for_each(iv4.begin(), iv4.end(), display());
cout << " iv2: ";
for_each(iv2.begin(), iv2.end(), display());
cout << endl;
/*** unique: ***/
// :_FwdIt unique(_FwdIt _First, _FwdIt _Last)
unique(iv4.begin(), iv4.end());
cout << "unique(iv4.begin(), iv4.end()): ";
for_each(iv4.begin(), iv4.end(), display());
cout << endl;;
/*** unique_copy: , ***/
unique_copy(iv4.begin(), iv4.end(),iv3.begin());
cout << "unique_copy(iv4.begin(), iv4.end(),iv3.begin()): ";
for_each(iv3.begin(), iv3.end(), display());
cout << endl;
return 0;
}
2.4配列組合せアルゴリズム
#include
#include
#include
using namespace std;
template
struct display
{
void operator()(const T&x) const
{
cout << x << " ";
}
};
int main(int argc, char* argv[])
{
int iarr[] = { 12, 17, 20, 22, 23, 30, 33, 40 };
vector iv(iarr, iarr + sizeof(iarr) / sizeof(int));
/*** next_permutation: , 。***/
// : bool next_permutation(_BidIt _First, _BidIt _Last)
// ( )
next_permutation(iv.begin(), iv.end());
for_each(iv.begin(), iv.end(), display());
cout << endl;
next_permutation(iv.begin(), iv.end());
for_each(iv.begin(), iv.end(), display());
cout << endl;
return 0;
}
2.5.数値アルゴリズム
#include
#include
#include //
#include // ostream_iterator
using namespace std;
int main(int argc, char* argv[])
{
int arr[] = { 1, 2, 3, 4, 5 };
vector vec(arr, arr + 5);
vector vec2(arr, arr + 5);
// accumulate: iterator , val 。
int temp;
int val = 1;
temp = accumulate(vec.begin(), vec.end(), val);
cout << "accumulate(val = 1): " << temp << endl;
// inner_product: ( , ) 。
// :1*1 + 2*2 + 3*3 + 4*4 + 5*5
val = 0;
temp = inner_product(vec.begin(), vec.end(), vec2.begin(), val);
cout << "inner_product(val = 0): " << temp << endl;
// partial_sum: , 。
// ,1 ,1+2 ,1+2+3 ,1+2+3+4
ostream_iterator oit(cout, " "); // cout
cout << "ostream_iterator: ";
partial_sum(vec.begin(), vec.end(), oit);// n
cout << endl;
// ,1 ,1-2 ,1-2-3 ,1-2-3-4
cout << "ostream_iterator(minus): ";
partial_sum(vec.begin(), vec.end(), oit, minus());// ( )
cout << endl;
// adjacent_difference: , 。
// ,1-0 ,2-1 ,3-2 ,4-3
cout << "adjacent_difference: ";
adjacent_difference(vec.begin(), vec.end(), oit); // -
cout << endl;
// ,1+0 ,2+1 ,3+2 ,4+3
cout << "adjacent_difference(plus): ";
adjacent_difference(vec.begin(), vec.end(), oit, plus()); // -
cout << endl;
return 0;
}
2.6.生成と変異アルゴリズム
#include
#include
#include
#include
using namespace std;
template
struct display
{
void operator()(const T&x) const
{
cout << x << " ";
}
};
// , int
void printElem(int& elem)
{
cout << elem << " ";
}
template
struct plus2
{
void operator()(T&x)const
{
x += 2;
}
};
class even_by_two
{
private:
static int _x; //
public:
int operator()()const
{
return _x += 2;
}
};
int even_by_two::_x = 0; //
int main(int argc, char* argv[])
{
int iarr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
vector iv(iarr, iarr + sizeof(iarr) / sizeof(int));
/*** fill: 。 ***/
// : void fill(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
fill(iv.begin(), iv.end(), 5);
cout << "fill: ";
for_each(iv.begin(), iv.end(), display());
cout << endl;
/*** fill_n: first first+n 。 ***/
// : _OutIt fill_n(_OutIt _Dest, _Diff _Count, const _Ty& _Val)
fill_n(iv.begin(), 4, 3); // 4 3 iv
cout << "fill_n: ";
for_each(iv.begin(), iv.end(), display());
cout << endl;
/*** for_each: , 。 ***/
// : _Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
for_each(iv.begin(), iv.end(), plus2()); // +2
cout << "for_each: ";
for_each(iv.begin(), iv.end(), printElem); //
cout << endl;
/*** generate: 。 ***/
// : void generate(_FwdIt _First, _FwdIt _Last, _Fn0 _Func)
// even_by_two() , iv
generate(iv.begin(), iv.end(), even_by_two());
cout << "generate: ";
for_each(iv.begin(), iv.end(), display());
cout << endl;
/*** generate_n: generate , iterator n 。 ***/
// : _OutIt generate_n(_OutIt _Dest, _Diff _Count, _Fn0 _Func)
// even_by_two() , iv
generate_n(iv.begin(), 3, even_by_two());
cout << "generate_n: ";
for_each(iv.begin(), iv.end(), display()); // _X static
cout << endl;
/*** transform: , 。 ***/
// : _OutIt transform(_InIt _First, _InIt _Last, _OutIt _Dest, _Fn1 _Func)
// 2
transform(iv.begin(), iv.end(), iv.begin(), bind2nd(minus(), 2));
cout << "transform: ";
for_each(iv.begin(), iv.end(), display()); // _X static
cout << endl;
return 0;
}
2.7.リレーショナルアルゴリズム
#include
#include
#include
using namespace std;
int main(int argc, char* argv[])
{
int iarr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector iv1(iarr, iarr + 5);
vector iv2(iarr, iarr + 9);
// equal: , true。
cout << "equal: " << equal(iv1.begin(), iv1.end(), iv2.begin()) << endl;// 1 , iv1
// includes: , ::iterator, vector::iterator> pa;
pa = mismatch(iv1.begin(), iv1.end(), iv2.begin());
if (pa.first == iv1.end()) // true , iv1
cout << " " << endl;
else
{
cout << " -- :" << *(pa.first) << endl; // , end
cout << " -- :" << *(pa.second) << endl;
}
return 0;
}
2.8.しゅうごうアルゴリズム
#include
#include
#include
#include
using namespace std;
template
struct display
{
void operator()(const T&x) const
{
cout << x << " ";
}
};
int main(int argc, char* argv[])
{
int iarr1[] = { 1, 3, 5, 7, 9, 11 };
int iarr2[] = { 1, 1, 2, 3, 5, 8, 13 };
multiset s1(iarr1, iarr1 + 6);
multiset s2(iarr2, iarr2 + 7);
cout << "s1: ";
for_each(s1.begin(), s1.end(), display());
cout << endl;
cout << "s2: ";
for_each(s2.begin(), s2.end(), display());
cout << endl;
/*** set_union: , 。 ***/
// : _OutIt set_union(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
cout << "union of s1 and s2: ";
// , max(m,n)。
set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), ostream_iterator(cout, " "));
cout << endl;
/*** set_intersection: , 。 ***/
// : _OutIt set_union(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
cout << "Intersection of s1 and s2: ";
// , min(m,n).
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), ostream_iterator(cout, " "));
cout << endl;
/*** set_difference: , 。 ***/
// : _OutIt set_union(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
cout << "Intersection of s1 and s2: ";
// S1 s2
set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), ostream_iterator(cout, " "));
cout << endl;
/*** set_symmetric_difference: , ( - )。 ***/
// : _OutIt set_union(_InIt1 _First1, _InIt1 _Last1, _InIt2 _First2, _InIt2 _Last2, _OutIt _Dest)
cout << "Intersection of s1 and s2: ";
// : 。 , ,
// abs(m-n)
set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), ostream_iterator(cout, " "));
cout << endl;
return 0;
}
2.9ヒープアルゴリズム
#include
#include
#include
using namespace std;
template
struct display
{
void operator()(const T&x) const
{
cout << x << " ";
}
};
int main(int argc, char* argv[])
{
int iarr[] = { 9,5, 1, 7, 8 };
vector iv(iarr, iarr + sizeof(iarr) / sizeof(int));
/*** make_heap: 。 ***/
// : void make_heap(_RanIt _First, _RanIt _Last)
make_heap(iv.begin(), iv.end());
cout << "make_heap: ";
for_each(iv.begin(), iv.end(), display());
cout << endl;
/*** pop_heap: , 。 ***/
// : void pop_heap(_RanIt _First, _RanIt _Last)
pop_heap(iv.begin(), iv.end());
iv.pop_back();
cout << "pop_heap: ";
for_each(iv.begin(), iv.end(), display());
cout << endl;
/*** push_heap: first last-1 , last-1, 。 ***/
// : void push_heap(_RanIt _First, _RanIt _Last)
iv.push_back(6);
push_heap(iv.begin(), iv.end());
cout << "push_heap: ";
for_each(iv.begin(), iv.end(), display());
cout << endl;
return 0;
}