STL Samples : <algorithm>
適用
- template<class InputIterator, class Function>
Function
for_each(InputIterator first,
InputIterator last,
Function f);
[first,last)にあるすべてのiに対し、f(*i)を行います。f(*i)の戻り値は無視されます。
#include <iostream> #include <algorithm> #include <vector> #include "to_string.h" using namespace std; struct print { void operator()(const int& i) { cout << i << ','; } }; void printfun(const int& t) { cout << t << ','; } void std_for_each() { cout << "for_each" << endl; const int N = 5; int input[N] = { 1, 2, 3, 4, 5 }; for_each(input, input+N, print()); cout << endl; vector<int> iv(input, input+N); for_each(iv.begin(), iv.end(), &printfun); cout << endl; }
検索
- template<class InputIterator, class T>
InputIterator
find(InputIterator first,
InputIterator last,
const T& value);
- template<class InputIterator, class Predicate>
InputIterator
find_if(InputIterator first,
InputIterator last,
Predicate pred);
[first,last)にあるiに対し*i == value, pred(*i) != falseとなる最初のiを返します。条件を満たすiが存在しないときはlastを返します。
- template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_end(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
- template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_end(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
BinaryPredicate pred);
シーケンス[first1,last1)の中にシーケンス[first2,last2)が見つかる(部分列が存在する)なら、最後に見つかった位置を返します。見つからない場合はlast1を返します。
- template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_first_of(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
- template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
find_first_of(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
BinaryPredicate pred);
シーケンス[first1,last1)の中からシーケンス[first2,last2)の要素のどれかが見つかれば、その位置を返します。見つからない場合はlast1を返します。
- template<class ForwardIterator>
ForwardIterator
adjacent_find(ForwardIterator first,
ForwardIterator last);
- template<class ForwardIterator, class BinaryPredicate>
ForwardIterator
adjacent_find(ForwardIterator first,
ForwardIterator last,
BinaryPredicate pred);
[first,last)にあるiとi+1に対し、*i == *(i+1), pred(*i,*(i+1)) != falseとなるiを返します。つまりは隣接する等しい要素を探してくれます。
- template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
search(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);
- template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1
search(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2,
BinaryPredicate pred);
シーケンス[first1,last1)の中にシーケンス[first2,last2)が現れる(部分列が存在する)なら、その位置を返します。
search_n
- template<class ForwardIterator, class Size, class T>
ForwardIterator
search_n(ForwardIterator first,
ForwardIterator last,
Size count,
const T& value);
- template<class ForwardIterator, class Size, class T,
class BinaryPredicate>
ForwardIterator1
search_n(ForwardIterator first,
ForwardIterator last,
Size count,
const T& value,
BinaryPredicate pred);
シーケンス[first,last-count)にあるiﾆ対し､*i==value,pred(*i,value)!=falseを満たすiを返します。
- template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2);
- template <class InputIterator1, class InputIterator2,
class BinaryPredicate>
pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
BinaryPredicate pred);
[first1,last1)にあるiとj=first2+(i-first1)に対し、*i != *j, pred(*i.*j) == falseとなるi,jのpairを返します。すなわち2つのシーケンスの不一致箇所を見つけます。
- template<class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value);
- template<class ForwardIterator, class T, class Compare>
ForwardIterator
lower_bound(ForwardIterator first,
ForwardIterator last,
const T& value,
Compare comp);
ソートされたシーケンス[first,last)に対し、valueより大きいか等しい最初の要素の位置を返します。
- template<class ForwardIterator, class T>
ForwardIterator
upper_bound(ForwardIterator first,
ForwardIterator last,
const T& value);
- template<class ForwardIterator, class T, class Compare>
ForwardIterator
upper_bound(ForwardIterator first,
ForwardIterator last,
const T& value,
Compare comp);
ソートされたシーケンス[first,last)に対し、valueより大きい最初の要素の位置を返します。
- template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last,
const T& value);
- template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first,
ForwardIterator last,
const T& value,
Compare comp);
lower_boundおよびupper_boundのそれぞれの結果をfirst,secondとするpairを返します。
- template<class ForwardIterator, class T>
bool
binary_search(ForwardIterator first,
ForwardIterator last,
const T& value);
- template<class ForwardIterator, class T, class Compare>
bool
binary_search(ForwardIterator first,
ForwardIterator last,
const T& value,
Compare comp);
ソートされたシーケンス[first,last)に対して二分検索を行い、valueと等しいものが存在すればtrueを返します。
#include <iostream> #include <algorithm> #include <functional> #include "to_string.h" using namespace std; void std_find() { cout << "find, find_if" << endl; const int N = 5; int input[N] = { 1, 4, 3, 5, 2 }; int* ip = find(input, input+N, 6); cout << "6 が " << to_string(input,input+N) << " の "; if ( ip != input+N ) cout << distance(input,ip) << " 番目に見つかりました" << endl; else cout << "中に見つかりませんでした" << endl; cout << to_string(input,input+N) << " の中の3より大きい数は "; for ( ip = input; (ip = find_if(ip, input+N, bind2nd(greater<int>(),3))) != input+N; ++ip ) cout << *ip << ' '; cout << endl; } void std_find_end() { cout << "find_end" << endl; const int N = 11; const char input[] = "ABRACADABRA"; const char* ip = find_end(input, input+N, input, input+2); cout << to_string(input,input+N) << " の最後に現れる " << to_string(input,input+2) << " は :" << to_string(input, ip, ip+2, input+N) << endl; } void std_find_first_of() { cout << "find_first_of" << endl; const int N = 11; const char input[] = "ABRACADABRA"; const char target[] = "RED"; const char* ip = find_first_of(input, input+N, target, target+3); cout << to_string(input,input+N) << " の中にある [" << to_string(target,target+3) << " のいずれか]の位置:" << to_string(input, ip, input+N) << endl; } bool both_even(const int& x, const int& y) { return !(x%2) && !(y%2); } void std_adjacent_find() { cout << "adjacent_find" << endl; const int N = 6; int input[N] = { 1, 2, 4, 3, 3, 5 }; int* ip = adjacent_find(input, input+N); cout << to_string(input,input+N) << " にある、隣接する等しい要素の位置:" << to_string(input, ip, input+N)<< endl; ip = adjacent_find(input, input+N, both_even); cout << to_string(input,input+N) << " にある、隣接する偶数の位置:" << to_string(input, ip, input+N) << endl; } void std_search() { cout << "search" << endl; const int N = 6; int input[] = { 1, 2, 3, 4, 5, 6 }; int target[] = { 3, 4, 5 }; int* it = search(input, input+N, target, target+3, equal_to<int>()); cout << to_string(input,input+N) << " にある " << to_string(target,target+3) << " の位置:" << to_string(input, it, it+3, input+N) << endl; } void std_mismatch() { cout << "mismatch" << endl; const int N = 6; int input1[N] = { 1, 2, 3, 4, 5, 6 }; int input2[N] = { 1, 2, 3, 6, 8, 6 }; pair<int*,int*> ip = mismatch(input1, input1+N, input2); cout << to_string(input1, input1+N) << " と " << to_string(input2, input2+N) << " の不一致個所; " << to_string(input1, ip.first, input1+N) << " , " << to_string(input2, ip.second, input2+N) << endl; } void std_find_sorted() { cout << "lower_bound, upper_bound, equal_range, binary_search" << endl; const int N = 6; int input[N] = { 1, 2, 3, 3, 3, 6 }; int* lp = lower_bound(input, input+N, 3); int* up = upper_bound(input, input+N, 3); pair<int*,int*> r = equal_range(input, input+N, 3); cout << to_string(input, input+N) << " にある､" << endl << "'3以上' の位置:" << to_string(input, lp, input+N) << endl << "'3未満' の位置:" << to_string(input, up, input+N) << endl << " 3 の範囲:" << to_string(input, r, input+N) << endl; cout << "5 は " << to_string(input, input+N) << " の中に " << ( binary_search(input, input+N, 5) ? "ある" : "ない" ) << endl; }
係数
- template<class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first,
InputIterator last,
const T& value);
- template<class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first,
InputIterator last,
Predicate pred);
[first,last)にあるiに対し、*i == value, pred(*i) != falseとなるiの個数を返します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; bool is_even(const int& x) { return !(x%2); } void std_count() { cout << "count, count_if" << endl; const int N = 6; int input[N] = { 2, 2, 4, 3, 2, 5 }; cout << to_string(input, input+N) << " 内にある、" << endl << " 2 の数: " << count(input, input+N, 2) << endl << " 偶数の数: " << count_if(input, input+N, is_even) << endl; }
比較
- template<class InputIterator1, class InputIterator2>
bool
equal(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2);
- template <class InputIterator1, class InputIterator2,
class BinaryPredicate>
bool
equal(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
BinaryPredicate pred);
2つのシーケンス[first1,last1)と[first2,last2)の対応する要素がすべて等しい(*i == *j, pred(*i,*j) != false)ならばtrueを返します。
- template<class InputIterator1, class InputIterator2>
bool
lexicographical_compare(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2);
- template<class InputIterator1, class InputIterator2, class Compare>
bool
lexicographical_compare(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
Compare comp);
シーケンス[first1,last1)と[first2,last2)をそれぞれの要素の大小関係にしたがって辞書順にならべたとき、シーケンス[first1,last1)が先に現れるならtrueを返します。
#include <iostream> #include <algorithm> #include <functional> #include "to_string.h" using namespace std; void std_equal() { cout << "equal" << endl; const int N = 6; int input1[N] = { 1, 2, 3, 4, 5, 6 }; int input2[N] = { 1, 2, 3, 4, 6, 6 }; cout << to_string(input1, input1+4) << " と " << to_string(input2, input2+4) << " は " << ( equal(input1, input1+4, input2) ? "等しい" : "等しくない" ) << endl; cout << to_string(input1, input1+N) << " と " << to_string(input2, input2+N) << " は " << ( equal(input1, input1+6, input2, equal_to<int>()) ? "等しい" : "等しくない" ) << endl; } void std_lexicographical_compare() { cout << "lexicographical_compare" << endl; int input1[] = { 1,2,3,4 }; int input2[] = { 1,2,3,4,1 }; cout << to_string(input1, input1+4) << ( lexicographical_compare(input1,input1+4,input2,input2+5) ? " < " : " >= " ) << to_string(input2, input2+5) << endl; }
複写
- template<class InputIterator, class OutputIterator>
OutputIterator
copy(InputIterator first,
InputIterator last,
OutputIterator result);
- template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
シーケンス[first,last)を[result,result+N)にコピーします(N=last-first)。copy_backwardは各要素を末尾(last-1)から逆順にコピーします。反転するわけではありません。戻り値はコピー終了時のコピー先iteratorとなります。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_copy() { cout << "copy, copy_backward" << endl; const int Ns = 10; int src[Ns] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; const int Nd = 5; int dst[Nd] = { 0, 0, 0, 0, 0 }; cout << to_string(src, src+Nd) << " を " << to_string(dst, dst+Nd) << " にコピー: "; copy(src, src+Nd, dst); cout << to_string(dst, dst+Nd) << endl; cout << to_string(src+6, src+9) << " を " << to_string(dst, dst+Nd) << " に(後から)コピー: "; copy_backward(src+6, src+9, dst+Nd); cout << to_string(dst, dst+Nd) << endl; }
交換
- template<class T>
void
swap(T& a,
T& b);
aとbの内容を交換します。
- template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2
swap_ranges(ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2);
2つのシーケンス[first1,last1),[first2,...)のそれぞれの要素を交換します。
- template<class ForwardIterator1, class ForwardIterator2>
void
iter_swap(ForwardIterator1 a,
ForwardIterator2 b);
*aと*bの内容を交換します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_swap() { cout << "swap, iter_swap, swap_rages" << endl; int a = 2, b = 3; cout << a << ',' << b << " を交換: "; swap(a,b); cout << a << ',' << b << endl; cout << "もう一度: "; iter_swap(&a,&b); cout << a << ',' << b << endl; const int N = 5 ; int x[N] = { 0, 1, 2, 3, 4 }; int y[N] = { 5, 6, 7, 8, 9 }; cout << to_string(x,x+N) << ',' << to_string(y,y+N) << " の始めの3つを交換: "; swap_ranges(x, x+3, y); cout << to_string(x,x+N) << ',' << to_string(y,y+N) << endl; }
変換
- template<class InputIterator, class OutputIterator,
class UnaryOperation>
OutputIterator
transform(InputIterator first,
InputIterator last,
OutputIterator result,
UnaryOperation op);
[first,last)にあるiに対し、op(*i)の結果を[result,result+N)に代入します(N=last-first)。result+Nを返します。
- template<class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation>
OutputIterator
transform(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
OutputIterator result,
BinaryOperation binary_op);
[first1,last1)にあるiとj=first2+(i-first1)に対し、op(*i,*j)の結果を[result,result+N)に代入します(N=last-first)。result+Nを返します。
#include <iostream> #include <algorithm> #include <functional> #include "to_string.h" using namespace std; static int quad(const int& n) { return n * 4; } void std_transform() { cout << "transform" << endl; const int N = 5; int x[N] = { 0, 1, 2, 3, 4 }; int y[N] = { 0, 0, 0, 0, 0 }; int z[N] = { 0, 0, 0, 0, 0 }; cout << "x[] : " << to_string(x,x+N) << endl; transform(x, x+N, y, quad); cout << "y[n] = x[n] * 4 : " << to_string(y,y+N) << endl; transform(x ,x+N, y, z, plus<int>()); cout << "z[n] = x[n] + y[n] : " << to_string(z,z+N) << endl; }
置換
- template<class ForwardIterator, class T>
void
replace(ForwardIterator first,
ForwardIterator last,
const T& old_value,
const T& new_value);
- template<class ForwardIterator, class Predicate, class T>
void
replace_if(ForwardIterator first,
ForwardIterator last,
Predicate pred,
const T& new_value);
[first,last)にあるiに対し、*i==old_value, pred(*i)!=falseならば*iにnew_valを代入します。
- template<class InputIterator, class OutputIterator, class T>
OutputIterator
replace_copy(InputIterator first,
InputIterator last,
OutputIterator result,
const T& old_value,
const T& new_value);
- template<class Iterator, class OutputIterator, class Predicate,
class T>
OutputIterator
replace_copy_if(Iterator first,
Iterator last,
OutputIterator result,
Predicate pred,
const T& new_value);
[first,last)にあるiに対し、*i==old_val,pred(*i)!=falseならばnew_valが、そうでなければ*iが[result,result+N)に代入されます(N=last-first)。result+Nを返します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; static bool is_one(const int& n) { return n == 1; } void std_replace() { cout << "replace, replace_if, replace_copy, replace_copy_if" << endl; const int N = 5; int x[N] = { 0, 1, 0, 3, 0 }; int y[N] = { 0, 0, 0, 0, 0 }; cout << to_string(x,x+N) << " の 0 を 1 に置換:"; replace(x, x+N, 0, 1); cout << to_string(x,x+N) << endl; cout << to_string(x,x+N) << " の 1 を 0 に置換:"; replace_if(x, x+N, is_one, 0); cout << to_string(x,x+N) << endl; cout << to_string(x,x+N) << " の 3 を 0 に置換(コピー):"; replace_copy(x, x+N, y, 3, 0); cout << to_string(y,y+N) << endl; cout << to_string(x,x+N) << " の 1 を 3 に置換(コピー):"; replace_copy_if(x, x+N, y, is_one, 3); cout << to_string(y,y+5) << endl; }
充填
- template<class ForwardIterator, class T>
void
fill(ForwardIterator first,
ForwardIterator last,
const T& value);
シーケンス[first,last)の各要素をvalueで埋めます。
- template<class OutputIterator, class Size, class T>
void
fill_n(OutputIterator first,
Size n,
const T& value);
シーケンス[first,first+n)をvalueで埋めます。
- template<class ForwardIterator, class Generator>
void generate(ForwardIterator first,
ForwardIterator last,
Generator gen);
genは引数を持たない関数オブジェクトです。シーケンス[first,last)をgen()の戻り値で埋めます。
- template<class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first,
Size n,
Generator gen);
シーケンス[first,first+n)をgen()の戻り値で埋めます。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_fill() { cout << "fill, fill_n" << endl; const int N = 5; int x[N] = { 0, 1, 2, 3, 4 }; cout << to_string(x,x+N) << " を 9 で充填: "; fill(x, x+N, 9); cout << to_string(x,x+N) << endl; cout << to_string(x,x+N) << " の始めの3つを 0 で充填: "; fill_n(x, 3, 0); cout << to_string(x,x+N) << endl; } void std_generate() { cout << "generate, generate_n" << endl; const int N = 5; int x[N] = { 0, 0, 0, 0, 0 }; cout << to_string(x,x+N) << " を乱数で埋める: "; generate(x, x+N, rand); cout << to_string(x,x+5) << endl; cout << to_string(x,x+N) << " の始めの3つを乱数で埋める: "; generate_n(x, 3, rand); cout << to_string(x,x+N) << endl; }
削除
- template<class ForwardIterator, class T>
ForwardIterator
remove(ForwardIterator first,
ForwardIterator last,
const T& value);
- template<class ForwardIterator, class Predicate>
ForwardIterator
remove_if(ForwardIterator first,
ForwardIterator last,
Predicate pred);
[first,last)にあるiに対し、*i==value,pred(*i)!=falseとなるものを取り除きます。 remove/remove_ifの戻り値をRETとすると、シーケンス[first,RET)が新たなシーケンスとなります。取り除かれた要素に対するメモリの返却などの後始末は行われません。
- template<class InputIterator, class OutputIterator, class T>
OutputIterator
remove_copy(InputIterator first,
InputIterator last,
OutputIterator result,
const T& value);
- template<class InputIterator, class OutputIterator, class Predicate>
OutputIterator
remove_copy_if(InputIterator first,
InputIterator last,
OutputIterator result,
Predicate pred);
[first,last)にあるiに対し、*i==value,pred(*i)!=falseでないもののみを[result,result+N)にコピーします(N:条件を満たした要素の個数)。resutl+Nを返します。
- template<class ForwardIterator>
ForwardIterator
unique(ForwardIterator first,
ForwardIterator last);
- template<class ForwardIterator, class BinaryPredicate>
ForwardIterator
unique(ForwardIterator first,
ForwardIterator last,
BinaryPredicate pred);
隣接する相等しい要素を削除、すなわち[first,last)にあるi,i-1に対し、*i==*(i-1),pred(*i,*(i- 1))!=falseである*iをシーケンスから取り除きます。隣接する愛等しい要素を取り除いたシーケンスの末尾(の直後)を返します。
- template<class InputIterator, class OutputIterator>
OutputIterator
unique_copy(InputIterator first,
InputIterator last,
OutputIterator result);
- template<class InputIterator, class OutputIterator,
class BinaryPredicate>
OutputIterator
unique_copy(InputIterator first,
InputIterator last,
OutputIterator result,
BinaryPredicate pred);
隣接する相等しい要素を取り除いたシーケンスを[result,result+N)に作ります(N:得られた要素の個数)。result+Nを返します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; static bool is_even(const int& n) { return (n%2) == 0; } void std_remove() { cout << "remove, remove_if, remove_copy, remove_copy_if" << endl; const int N = 6; int x[N] = { 1, 2, 3, 4, 5, 2 }; int y[N] = { 0, 0, 0, 0, 0, 0 }; cout << to_string(x,x+N) << " から 2 を削除(コピー): "; int* last = remove_copy(x, x+N, y, 2); cout << to_string(y,last) << endl; cout << to_string(x,x+N) << " から偶数を削除(コピー): "; last = remove_copy_if(x, x+N, y, is_even); cout << to_string(y,last) << endl; cout << to_string(x,x+N) << " から 2 を削除: "; last = remove(x, x+N, 2); cout << to_string(x,last) << endl; cout << to_string(x,last) << " から偶数を削除: "; last = remove_if(x, last, is_even); cout << to_string(x,last) << endl; } bool both_even(const int& x, const int& y) { return !(x%2) && !(y%2); } void std_unique() { cout << "unique, unique_copy" << endl; const int N = 7; int x[N] = { 1, 1, 2, 4, 4, 4, 5 }; int y[N] = { 0, 0, 0, 0, 0, 0, 0 }; cout << to_string(x,x+N) << " から隣接する等しい要素を削除(コピー): "; int* last = unique_copy(x, x+N, y); cout << to_string(y,last) << endl; cout << to_string(x,x+N) << " から隣接する偶数を削除: "; last = unique(x, x+N, both_even); cout << to_string(x,last) << endl; }
反転
- template<class BidirectionalIterator>
void
reverse(BidirectionalIterator first,
BidirectionalIterator last);
- template<class BidirectionalIterator, class OutputIterator>
OutputIterator
reverse_copy(BidirectionalIterator first,
BidirectionalIterator last,
OutputIterator result);
シーケンス[first,last)を反転します。reverse_copyは反転したシーケンスを[result,result+N)に作ります(N=last-first)。result+Nを返します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_reverse() { cout << "eeverse, reverse_copy" << endl; const int N = 5; int x[N] = { 1, 2, 3, 4, 5 }; int y[N] = { 0, 0, 0, 0, 0 }; cout << to_string(x,x+N) << " を反転(コピー): "; reverse_copy(x, x+N, y); cout << to_string(y, y+N) << endl; cout << to_string(x,x+N) << " の始めの3つを反転: "; reverse(x, x+3); cout << to_string(x, x+N) << endl; }
回転
- template<class ForwardIterator>
void
rotate(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last);
- template<class ForwardIterator, class OutputIterator>
OutputIterator
rotate_copy(ForwardIterator first,
ForwardIterator middle,
ForwardIterator last,
OutputIterator result);
[middle,last)、続いて[first,middle)の順に並び替えます。rotate_copyは並び替えたシーケンスを[result,result+N)に作ります(N=last-fiest)。result+Nを返します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_rotate() { cout << "rotate, rotate_copy" << endl; const int N = 6; int input[N] = { 1, 2, 3, 4, 5, 6 }; int result[N] = { 0, 0, 0, 0, 0, 0 }; cout << to_string(input, input+4, input+N) << " を回転(コピー): "; rotate_copy(input, input+4, input+N, result); cout << to_string(result, result+N) << endl; cout << to_string(input, input+2, input+N) << " を回転: "; rotate(input, input+2, input+N); cout << to_string(input, input+N) << endl; }
攪拌
- template<class RandomAccessIterator>
void
random_shuffle(RandomAccessIterator first,
RandomAccessIterator last);
- template<class RandomAccessIterator, class RandomNumberGenerator>
void
random_shuffle(RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator& rand);
シーケンス[first,last)をかき混ぜます。関数オブジェクトrandは1個の引数nを取り、[0,n)の範囲にある乱数を返さなければなりません。
#include <iostream> #include <algorithm> #include <cstdlib> #include "to_string.h" using namespace std; struct random_gen { int operator()(int x) const { return rand() % x; } }; void std_random_shuffle() { cout << "random_shuffle" << endl; const int N = 6; int input[N] = { 1, 2, 3, 4, 5, 6 }; cout << to_string(input, input+N) << " を攪拌: "; random_shuffle(input, input+N); cout << to_string(input, input+N) << endl; cout << to_string(input, input+N) << " を攪拌: "; random_shuffle(input, input+N, random_gen()); cout << to_string(input, input+N) << endl; }
分類
- template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
- template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
partitonの戻り値をiとすると、[first,i)にあるすべてのjに対してpred(*j)!=falseとなるようシーケンスが並び替えられます。すなわち条件predを満たす要素をシーケンスの前方にまとめます。stable_partitionは元の順序を保ちながらpartitionを行います。
- template<class RandomAccessIterator>
void
nth_element(RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
nth_element(RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last,
Compare comp);
[first,nth)の範囲にある任意のiと[nth,last)の範囲にある任意のjに対し、!(*i>*j),comp(*i,*j)==false)となるように要素の入れ替えを行います。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; bool is_even(const int& n) { return (n%2) == 0; } void std_partition() { cout << "partition, stable_partition" << endl; const int N = 8; int x[N] = { 1, 2, 3, 4, 5, 6, 7, 8 }; int y[N] = { 1, 2, 3, 4, 5, 6, 7, 8 }; cout << to_string(x,x+N) << " を偶数と奇数に分類: "; int* middle = partition(x, x+N, is_even); cout << to_string(x,middle,x+N) << endl; cout << to_string(y,y+N) << " を偶数と奇数に分類(stable): "; middle = stable_partition(y, y+N, is_even); cout << to_string(y,middle,y+N) << endl; } void std_nth_element() { cout << "nth_element" << endl; const int N = 6; int input[] = { 5,4,3,1,2,2 }; cout << to_string(input, input+N) << " の小さい方から3つを抽出: "; nth_element(input,input+3,input+N); cout << to_string(input, input+3, input+N) << endl; }
整列
- template<class RandomAccessIterator>
void
sort(RandomAccessIterator first,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
sort(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
- template<class RandomAccessIterator>
void
stable_sort(RandomAccessIterator first,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
stable_sort(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
シーケンス[first,last)を昇順に並び替えます。比較オブジェクトcompはoperator()が2つの引数を取り、大小関係に基づいて bool(true/false)を返してください。たとえばcomp(x,y)がx>yのときtrueを返すならば、 sort(first,last,comp)は[first,last)を大きい順に並び替えます。stable_sortは元の順序を保った安定なソートを行います。
- template<class RandomAccessIterator>
void
partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
シーケンス[first,last)のうち、小さいものからmiddle-first個をソートして[first,middle)に置きます。[middle,last)にある要素の順序は不定となります。
- template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
- template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
シーケンス[first,last)のうち、小さいものからresult_last-result_first個をソートしたシーケンスを [result_first,result_last)に置きます。ただしlast-first < result_last-result_firstであるときは、ソートされる要素の個数はlast-firstで抑えられます。 partial_sort_copyはresult_lastもしくはresult_first+(last-first)を返します。
#include <iostream> #include <algorithm> #include <complex> #include "to_string.h" using namespace std; namespace std { bool operator<(const complex<int>& x, const complex<int>& y) { return x.real() < y.real(); } } void std_sort() { cout << "sort, stable_sort, partial_sort, partial_sort_copy" << endl; const int N = 7; complex<int> source[N] = { complex<int>(2,1), complex<int>(2,2), complex<int>(2,3), complex<int>(1,1), complex<int>(1,2), complex<int>(1,3), complex<int>(2,4) }; complex<int> output[N]; copy(source, source+N, output); cout << to_string(output,output+N) << " をソート:"; sort(output, output+N); cout << to_string(output,output+N) << endl; copy(source, source+N, output); cout << to_string(output,output+N) << " をソート(stable):"; stable_sort(output, output+N); cout << to_string(output,output+N) << endl; copy(source, source+N, output); cout << to_string(output,output+N) << " の小さい方から4つをソート:"; partial_sort(output, output+4, output+N); cout << to_string(output,output+4,output+N) << endl; cout << to_string(source,source+N) << " の小さい方から4つをソート(コピー):"; partial_sort_copy(source, source+4, source+N, output); cout << to_string(output,output+4) << endl; }
併合
- template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
merge(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result);
- template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
merge(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result,
Compare comp);
ソートされた2つのシーケンス[first1,last1),[first2,last2)をマージし、ソートされた結果を[result,RET)に置きます。RETはmergeの戻り値です。
- template<class BidirectionalIterator>
void
inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
- template<class BidirectionalIterator, class Compare>
void
inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
ソートされた2つのシーケンス[first,middle)と[middle,last)をマージし、結果を[first,last)に置きます。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_merge() { cout << "merge, inplace_merge" << endl; const int N = 4; const int N2 = N+N; int input1[N] = { 1,3,5,7 }; int input2[N] = { 2,4,6,8 }; int output[N2] = { 0,0,0,0,0,0,0,0 }; cout << to_string(input1, input1+N) << " と " << to_string(input2, input2+N) << " をマージ: "; merge(input1, input1+N, input2, input2+N, output); cout << to_string(output,output+N2) << endl; int input[N2] = { 1,3,5,7,2,4,6,8 }; cout << to_string(input, input+N, input+N2) << " をマージ(inplace): "; inplace_merge(input, input+N, input+N2); cout << to_string(input, input+N2) << endl; }
集合
- template<class InputIterator1, class InputIterator2>
bool
includes(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2);
- template<class InputIterator1, class InputIterator2, class Compare>
bool
includes(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
Compare comp);
ソートされたシーケンス[first1,last1)と[first2,last2)に対し、[first2,last2)にあるすべての要素が[first1,last1)に含まれていればtrueを返します。
- template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_union(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result);
- template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_union(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result,
Compare comp);
ソートされたシーケンス[first1,last1)と[first2,last2)に対し、[first1,last1)と[first2,last2)の和集合を[result,RET)に作ります。RETはset_unionの戻り値です。
- template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_intersection(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result);
- template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_intersection(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result,
Compare comp);
ソートされたシーケンス[first1,last1)と[first2,last2)に対し、[first1,last1)と[first2,last2)の積集合を[result,RET)に作ります。RETはset_intersectionの戻り値です。
- template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_difference(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result);
- template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_difference(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result,
Compare comp);
ソートされたシーケンス[first1,last1)と[first2,last2)に対し、[first1,last1)と[first2,last2)の差集合、すなわち[first1,last1)にあって[first2,last2)にない要素からなる集合を[result,RET)に作ります。 RETはset_differenceの戻り値です。
- template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator
set_symmetric_difference(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result);
- template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator
set_symmetric_difference(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
OutputIterator result,
Compare comp);
ソートされたシーケンス[first1,last1)と[first2,last2)に対し、[first1,last1)と[first2,last2)のいずれか一方にのみ存在する要素からなる集合を[result,RET)に作ります。RETはset_symmetric_differenceの戻り値です。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_set_operation() { cout << "includes, set_union, set_intersection, set_difference, set_symmetric_difference" << endl; const int N = 4; const int N2 = N+N; int A[N] = { 1,2,3,4 }; int B[N] = { 2,4,6,8 }; int R[N2]; cout << to_string(A,A+N) << " は " << to_string(B,B+2) << " を " << ( includes(A, A+N, B, B+2) ? "含む" : "含まない") << endl; cout << "A: " << to_string(A,A+N) << " と " << "B: " << to_string(B,B+N) << " に対し、" << endl; cout << "A または B: "; int* last = set_union(A, A+N, B, B+N, R); cout << to_string(R, last) << endl; cout << "A かつ B: "; last = set_intersection(A, A+N, B, B+N, R); cout << to_string(R, last) << endl; cout << "A にあるが B にない: "; last = set_difference(A, A+N, B, B+N, R); cout << to_string(R, last) << endl; cout << "A と B のどちらか一方にある: "; last = set_symmetric_difference(A, A+N, B, B+N, R); cout << to_string(R, last) << endl; }
堆積
- template<class RandomAccessIterator>
void
push_heap(RandomAccessIterator first,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
push_heap(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
heap化されたシーケンス[first,last-1)に*(last-1)を加えてheap列[first,last)を作ります。
- template<class RandomAccessIterator>
void
pop_heap(RandomAccessIterator first,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
pop_heap(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
heap列[first,last)の*firstと*(last-1)を入れ替え、heap列[first,last-1)を作り直します。この結果、*(last-1)はheap列中の最大値が格納されます。
- template<class RandomAccessIterator>
void
make_heap(RandomAccessIterator first,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
make_heap(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
シーケンス[first,last)をheap化します。
- template<class RandomAccessIterator>
void
sort_heap(RandomAccessIterator first,
RandomAccessIterator last);
- template<class RandomAccessIterator, class Compare>
void
sort_heap(RandomAccessIterator first,
RandomAccessIterator last,
Compare comp);
heap化されたシーケンス[first,last)をソートします。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; void std_heap() { cout << "push_heap, pop_heap, make_heap, sort_heap" << endl; const int N = 8;; int input[] = { 1,2,3,4,5,6,7,8 }; cout << "入力 : "<< to_string(input, input+N) << endl; make_heap(input, input+4); cout << "始めの4つをheap化: " << to_string(input, input+4, input+N) << endl; push_heap(input, input+5); cout << "5 をheapに追加: " << to_string(input, input+5, input+N) << endl; push_heap(input, input+6); push_heap(input, input+7); push_heap(input, input+8); cout << "6,7,8 をheapに追加: " << to_string(input, input+N) << endl; pop_heap(input, input+8); pop_heap(input, input+7); cout << "2つの要素を取り出す:" << to_string(input, input+6, input+N) << endl; sort_heap(input,input+6); cout << "heapをソート: " << to_string(input, input+6, input+N) << endl; }
最大/最小
- template<class T>
const T&
min(const T& a,
const T& b);
- template<class T, class Compare>
const T&
min(const T& a,
const T& b,
Compare comp);
aとbの小さい方を返します。
- template<class T>
const T&
max(const T& a,
const T& b);
- template<class T, class Compare>
const T&
max(const T& a,
const T& b,
Compare comp);
aとbの大きい方を返します。
- template<class ForwardIterator>
ForwardIterator
min_element(ForwardIterator first,
ForwardIterator last);
- template<class ForwardIterator, class Compare>
ForwardIterator
min_element(ForwardIterator first,
ForwardIterator last,
Compare comp);
シーケンス[first,last)中の最小要素の位置を返します。
- template<class ForwardIterator>
ForwardIterator
max_element(ForwardIterator first,
ForwardIterator last);
- template<class ForwardIterator, class Compare>
ForwardIterator
max_element(ForwardIterator first,
ForwardIterator last,
Compare comp);
シーケンス[first,last)中の最大要素の位置を返します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; /* min/max : * Visual C++ では、windef.h に同名のマクロが * 定義されているため * min->_cpp_min, max->_cpp_max * となっている。 */ void std_minmax() { cout << "min, max, min_elemets, max_element" << endl; cout << "min(1,2) = " << _cpp_min(1,2) << endl; cout << "max(1,2) = " << _cpp_max(1,2) << endl; const int N = 4; int input[] = { 2, 1 , 4, 3 }; cout << to_string(input, input+N) << " の、" << endl << "最小値の位置: " << to_string(input, min_element(input, input+N), input+N) << endl << "最大値の位置: " << to_string(input, max_element(input, input+N), input+N) << endl; }
順列
- template<class BidirectionalIterator>
bool
next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
- template<class BidirectionalIterator, class Compare>
bool
next_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Compare comp);
シーケンス[first,last)を並び替え、(辞書順に並べたときの)次の順列を作ります。次の順列が作れない、すなわちシーケンス[first,last)が降順に並んでいたときは、昇順にソートしてfalseを返します。
- template<class BidirectionalIterator>
bool
prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
- template<class BidirectionalIterator, class Compare>
bool
prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
シーケンス[first,last)を並び替え、(辞書順に並べたときの)前の順列を作ります。前の順列が作れない、すなわちシーケンス[first,last)が昇順に並んでいたときは、降順にソートしてfalseを返します。
#include <iostream> #include <algorithm> #include "to_string.h" using namespace std; /* Visual C++ の prev_permutation にはバグがあるようだ。 * 正しくは: // TEMPLATE FUNCTION prev_permutation template<class _BI> inline bool prev_permutation(_BI _F, _BI _L) {_BI _I = _L; if (_F == _L || _F == --_I) return (false); for (; ; ) {_BI _Ip = _I; // if (!(*--_I < *_Ip)) // old if ( *_Ip < *--_I ) // new (episteme) {_BI _J = _L; // for (; *_I < *--_J; ) // old for (; !( *--_J < *_I); ) // new (episteme) ; iter_swap(_I, _J); reverse(_Ip, _L); return (true); } if (_I == _F) {reverse(_F, _L); return (false); }}} // TEMPLATE FUNCTION prev_permutation WITH PRED template<class _BI, class _Pr> inline bool prev_permutation(_BI _F, _BI _L, _Pr _P) {_BI _I = _L; if (_F == _L || _F == --_I) return (false); for (; ; ) {_BI _Ip = _I; // if (!_P(*--_I, *_Ip)) // old if ( _P(*Ip, *--_I) ) // new (episteme) {_BI _J = _L; // for (; _P(*_I, *--_J); ) // old for (; !_P(*--_J, *_I); ) // new (episteme) ; iter_swap(_I, _J); reverse(_Ip, _L); return (true); } if (_I == _F) {reverse(_F, _L); return (false); }}} */ void std_permutation() { cout << "next_permutation, prev_permutation" << endl; const int N = 4; int input[] = { 1, 2, 2, 3 }; cout << to_string(input,input+N) << " から順列を生成" << endl; cout << "正順:" << endl; do { cout << to_string(input,input+N) << endl; } while ( next_permutation(input, input+N) ); reverse(input, input+N); cout << "逆順:" << endl; cout << to_string(input,input+N) << " から順列を生成" << endl; do { cout << to_string(input,input+N) << endl; } while ( prev_permutation(input, input+N) ); }