algorithm
をテンプレートにして作成
[
トップ
|
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
開始行:
std::algorithm
-----
#contents
-----
*algorithm [#xc14b6df]
STLのコンテナを対象とした様々なアルゴリズムが定義されてい...
各関数はコンテナでなく従来の配列でも使えるようになってい...
#include <algorithm>
**ソート [#l1bcbfcc]
***ソート(sort, stable_sort) [#ofe815bb]
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessItera...
template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessItera...
sortは[first,last)の範囲の要素を値の昇順でソートする．デ...
比較方法を自分で指定したい場合は2番目の定義を使う．
sortでは値が同じだったときに元の順番になることは保証され...
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAcce...
template <class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAcce...
stable_sortはsortと同じく要素を並び替えるものであるが，値...
コード例
#code(C){{
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct vec2
{
int x, y;
};
inline std::ostream &operator<<(std::ostream &out, const ...
{
return out << "(" << a.x << ", " << a.y << ")";
}
bool comp_vec2(vec2 a, vec2 b)
{
return a.x < b.x;
}
int main(void)
{
const int N = 10;
srand(1234567);
vector<int> a(N);
vec2 b[N];
for(int i = 0; i < N; ++i){
a[i] = rand()%10;
b[i].x = rand()%5;
b[i].y = rand()%10;
}
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
cout << "b : ";
for(int i = 0; i < N; ++i) cout << b[i] << (i == N-1 ? "...
cout << endl;
sort(a.begin(), a.end());
stable_sort(b, b+N, comp_vec2);
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
cout << "b : ";
for(int i = 0; i < N; ++i) cout << b[i] << (i == N-1 ? "...
cout << endl;
return 0;
}
}}
実行結果
a : 0, 4, 2, 6, 0, 9, 7, 8, 7, 5
b : (1, 0), (3, 3), (4, 5), (1, 6), (0, 6), (3, 7), (1, ...
a : 0, 0, 2, 4, 5, 6, 7, 7, 8, 9
b : (0, 6), (1, 0), (1, 6), (1, 9), (1, 3), (3, 3), (3, ...
***部分ソート(partial_sort, partial_sort_copy) [#ofe815bb]
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAcc...
template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAcc...
範囲[first, last)の要素をソートする．ただし，ソート結果が...
それ以降の要素の順番はソートされていない．コンテナ中の部...
全体でソートしてその途中(middle)で打ち切るような処理．
partial_sortは[first, last)に結果を上書きするが，異なるコ...
template <class InputIterator, class RandomAccessIterato...
RandomAccessIterator partial_sort_copy(InputIterator fi...
RandomAccessIter...
template <class InputIterator, class RandomAccessIterato...
RandomAccessIterator partial_sort_copy(InputIterator fi...
RandomAccessIter...
Compare comp);
[first, last)のサイズ >= [result_first,result_last)のサイ...
コード例
#code(C){{
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
const int N = 10;
srand(1234567);
vector<int> a(N), b(N);
vector<int> c(N/2);
for(int i = 0; i < N; ++i){
a[i] = b[i] = rand()%10;
}
cout << "a,b : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
partial_sort(a.begin(), a.begin()+5, a.end());
//sort(a.begin(), a.begin()+5); // 単なる部分ソートとは...
cout << " a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
partial_sort_copy(b.begin(), b.end(), c.begin(), c.end());
cout << " c : ";
for(vector<int>::iterator i = c.begin(); i != c.end(); +...
cout << endl;
return 0;
}
}}
実行結果
a,b : 0, 1, 0, 4, 3, 3, 2, 4, 5, 6
a : 0, 0, 1, 2, 3, 4, 3, 4, 5, 6
c : 0, 0, 1, 2, 3
sort(a.begin(), a.begin()+5)にした場合は，
a,b : 0, 1, 0, 4, 3, 3, 2, 4, 5, 6
a : 0, 0, 1, 3, 4, 3, 2, 4, 5, 6
c : 0, 0, 1, 2, 3
となる．
***再配置(nth_element) [#r3578f46]
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAcce...
template <class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAcce...
範囲[first, last)の要素のうち，nthで示される要素の値より...
コード例
#code(C){{
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
const int N = 10;
srand(12345);
vector<int> a(N);
for(int i = 0; i < N; ++i){
a[i] = rand()%10;
}
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
nth_element(a.begin(), a.begin()+3, a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
return 0;
}
}}
実行結果(Visual Studio 2010)
a : 4, 4, 5, 5, 8, 5, 7, 3, 2, 4
a : 2, 3, 4, 4, 4, 5, 5, 5, 7, 8
***ヒープソート(sort_heap, make_heap, pop_heap, push_heap...
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccess...
template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccess...
ヒープ構造を持つコンテナ[first, last)をヒープソートにより...
ヒープとは親ノードが常に子ノードより大きい(or小さい)ツリ...
単にヒープと呼んだ場合，バイナリツリー(バイナリヒープ，二...
ルートノードは常に最大値もしくは最小値を持つ要素になる．
そのため，ルートノードを取り出していくことでソートを行う...
ヒープ構造を作成するための関数としてmake_heapが用意されて...
template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccess...
template <class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccess...
ヒープは配列内に下図のように格納される．
#ref(binary_tree.jpg);
そのため，front()を用いることでルートノードを参照すること...
また，ヒープからの要素の取り出し，挿入関数(pop_heap, push...
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessI...
template <class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessI...
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccess...
template <class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccess...
pop_heapはfirstをlast-1に移動して，それ以外の要素でヒープ...
pop_heap(a.begin(), a.end());
a.pop_back()
とすることで実際に値が取り出される．push_heapの場合は逆で，
a.push_back(100);
push_heap(a.begin(), a.end());
となる．つまり，push_heapはlast-1の要素をヒープに新しく追...
これらにより，push_backやpop_backだけの場合と違い，取り出...
コード例
#code(C){{
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
const int N = 10;
vector<int> a(N);
for(int i = 0; i < N; ++i){
a[i] = i+1;
}
random_shuffle(a.begin(), a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
make_heap(a.begin(), a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
sort_heap(a.begin(), a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
return 0;
}
}}
実行結果
a : 9, 2, 10, 3, 1, 6, 8, 4, 5, 7
a : 10, 7, 9, 5, 2, 6, 8, 4, 3, 1
a : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
真ん中の結果を図にして確認すると以下のようになる．
#ref(binary_tree2.jpg);
***ソートの計算時間 [#p39aed21]
ソートの計算時間は環境によると思いますが，
一般的にはnth_element < sort == partial_sort < stable_sor...
sortにはクイックソートが用いられているので計算時間はO(N l...
Visual Studio 2010で実装して計測した結果を以下に示します．
実装コード
#code(C){{
#include <ctime>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
int n = 10000;
clock_t t1, t2;
vector<int> a;
ofstream fo;
fo.open("time.txt"); // 計測結果をファイル出力
for(int k = 0; k < 4; ++k){
fo << n << ", ";
a.resize(n);
for(int i = 0; i < n; ++i){
a[i] = n;
}
random_shuffle(a.begin(), a.end());
t1 = clock();
sort(a.begin(), a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << ", ";
random_shuffle(a.begin(), a.end());
t1 = clock();
stable_sort(a.begin(), a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << ", ";
random_shuffle(a.begin(), a.end());
t1 = clock();
partial_sort(a.begin(), a.begin()+n/2, a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << ", ";
random_shuffle(a.begin(), a.end());
t1 = clock();
nth_element(a.begin(), a.begin()+n/2, a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << endl;
n *= 10;
}
fo.close();
return 0;
}
}}
実行結果
#ref(sort_time.jpg);
partial_sortがかなり遅くなっています．Visual Studioではpa...
**検索 [#l766c100]
***値検索(find,find_if,find_first_of) [#ca4f1adf]
-find
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator l...
[first, last)内からvalueと同じ値を持つ最初の要素のイテレ...
-find_if
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterato...
[first, last)内から比較関数predが真となる最初の要素のイテ...
-find_first_of
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of(ForwardIterator1 first1,...
ForwardIterator2 first2,...
template <class ForwardIterator1, class ForwardIterator2...
ForwardIterator1 find_first_of(ForwardIterator1 first1,...
ForwardIterator2 first2,...
BinaryPredicate pred);
[first1, last1)内から[first2, last2)内の任意の要素に一致...
***シーケンス検索(search, find_end) [#hc73bc1f]
-search
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, Forwar...
ForwardIterator2 first2, Forwar...
template <class ForwardIterator1, class ForwardIterator2...
ForwardIterator1 search(ForwardIterator1 first1, Forwar...
ForwardIterator2 first2, Forwar...
BinaryPredicate pred);
[first1, last1)内から[first2, last2)のシーケンスに一致す...
見つかった位置の最初(first2に一致する要素)のイテレータを...
-find_end
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, Forw...
ForwardIterator2 first2, Forw...
template <class ForwardIterator1, class ForwardIterator2...
ForwardIterator1 find_end(ForwardIterator1 first1, Forw...
ForwardIterator2 first2, Forw...
BinaryPredicate pred);
[first1, last1)内から[first2, last2)のシーケンスに一致す...
見つかった位置の最初(first2に一致する要素)のイテレータを...
***連続する要素の検索(adjacent_find, search_n) [#l371a038]
-adjacent_find
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, Fo...
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, Fo...
[first, last)内から同じ値を持つ要素が連続している最初の位...
-search_n
template <class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator first, Forward...
template <class ForwardIterator, class Size, class T, cl...
ForwardIterator search_n(ForwardIterator first, Forward...
BinaryPredicate pred);
[first1, last1)内からvalueがcount回連続で続く最初の位置を...
#code(C){{
int a[] = {1, 3, 3, 8, 8, 5};
cout << search_n(a, a+6, 2, 8)-a << endl;
}}
の場合，結果は"3"となる．
***連続しない要素の検索(mismatch) [#v02efc46]
-mismatch
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIter...
template <class InputIterator1, class InputIterator2, cl...
pair<InputIterator1, InputIterator2> mismatch(InputIter...
BinaryPre...
範囲[first1, last1)の要素を最初から操作していき，first2で...
predに相違条件を指定することも可能(等しいときにtrueを返す...
コード例
#code(C){{
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T>
void output(T x, int n)
{
for(int i = 0; i < n; ++i) cout << x[i] << (i == n-1 ? "...
cout << endl;
}
// 文字が1つずれていたら真を返す
bool comp_str(char x, char y){ return (x+1 == y); }
int main(void)
{
const int N = 10;
vector<int> a(N);
int b[N];
string c = "aabbaa";
string d = "bbcdbb";
for(int i = 0; i < N; ++i){
a[i] = i;
b[i] = i%5;
}
output(a, N); output(b, N);
pair<vector<int>::iterator, int*> result;
result = mismatch(a.begin(), a.end(), b);
cout << "pair of mismatch = " << *(result.first) << ", "...
cout << endl;
cout << c << endl;
cout << d << endl;
pair<string::iterator, string::iterator> result2;
result2 = mismatch(c.begin(), c.end(), d.begin(), comp_s...
cout << "pair of mismatch = " << *(result2.first) << ", ...
return 0;
}
}}
実行結果
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 2, 3, 4, 0, 1, 2, 3, 4
pair of mismatch = 5, 0
aabbaa
bbcdbb
pair of mismatch = b, d
***ソート済みコンテナに対する検索(equal_range, upper_boun...
-equal_range
template <class ForwardIterator, class T>
pair<ForwardIterator,ForwardIterator> equal_range(Forwa...
template <class ForwardIterator, class T, class Compare>
pair<ForwardIterator,ForwardIterator> equal_range(Forwa...
Compa...
ソート済みの[first, last)内からvalueと等しい値を持つ要素...
例えば，
#code(C){{
int c[] = {1, 3, 2, 3, 2, 1, 3, 4};
sort(c, c+8); // 1, 2, 2, 3, 3, 3, 4
pair<int*, int*> range;
range = equal_range(c, c+8, 3);
cout << "[" << range.first-c << ", " << range.second-c <...
}}
の場合，結果は"[4, 7)"となる．ちなみにソート無しだと"[6, ...
-upper_bound
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, Forw...
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, Forw...
ソート済みの[first, last)内からvalueより大きい値を持つ最...
-lower_bound
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, Forw...
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, Forw...
ソート済みの[first, last)内からvalueより小さい値を持つ最...
例えば，
#code(C){{
int d[] = {1, 3, 2, 3, 2, 1, 3, 4};
sort(d, d+8); // 1, 2, 2, 3, 3, 3, 4
int *low = lower_bound(d, d+8, 3);
int *up = upper_bound(d, d+8, 3);
cout << "[" << low-d << ", " << up-d << ")" << endl;
}}
でequal_rangeと同じ"[4, 7)"の結果が得られる．
***二分探索(binary_search) [#ube71784]
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterat...
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterat...
ソート済みの[first, last)からbinary search(二分探索)によ...
ソートする必要があるので，sortと組み合わせて使うことが多...
#code(C){{
int b[] = {1, 3, 2, 5, 4, 1};
sort(b, b+6);
if(binary_search(b, b+6, 5)){
cout << "5 is found." << endl;
}
}}
***最小値，最大値検索(min_element, max_element) [#e7d8b462]
-min_element
template <class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, Forw...
template <class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, Forw...
[first, last)内から最小の値を持つ要素のイテレータを返す．
-max_element
template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, Forw...
template <class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, Forw...
[first, last)内から最大の値を持つ要素のイテレータを返す．
例えば，
#code(C){{
int e[] = {3, 2, 1, 3, 2, 1, 4, 3};
int *minp = min_element(e, e+8);
int *maxp = max_element(e, e+8);
cout << "min element : " << minp-e << "(" << *minp << ")...
cout << "max element : " << maxp-e << "(" << *maxp << ")...
}}
結果は以下のようになる．
min element : 2(1)
max element : 6(4)
**コンテナの操作 [#qcdc8ef4]
***置き換え(replace, replace_if, replace_copy, replacy_co...
-replace
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator las...
コンテナ・配列の範囲[first, last)内の要素で値がold_value...
-replace_if
template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator ...
コンテナ・配列の範囲[first, last)内の要素でpredで示された...
-replace_copy
template <class InputIterator, class OutputIterator, cla...
OutputIterator replace_copy(InputIterator first, InputI...
const T& old_value, const T...
コンテナ・配列の範囲[first, last)内の要素で値がold_value...
resultで始まるコンテナにコピーする．
-replace_copy_if
template <class InputIterator, class OutputIterator, cla...
OutputIterator replace_copy_if(InputIterator first, Inp...
Predicate pred, const T&...
コンテナ・配列の範囲[first, last)内の要素でpredで示された...
resultで始まるコンテナにコピーする．
コード例
#code(C){{
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T>
void output(T x, int n)
{
for(int i = 0; i < n; ++i) cout << x[i] << (i == n-1 ? "...
cout << endl;
}
bool comp_func(int x){ return (x%2 == 0); }
int main(void)
{
const int N = 10;
vector<int> a(N);
int b[N];
string c = "aabbaa";
string d;
d.resize(c.size());
for(int i = 0; i < N; ++i){
a[i] = i%3;
b[i] = i+1;
}
output(a, N);
replace(a.begin(), a.end(), 1, 2);
cout << " --> "; output(a, N);
output(b, N);
replace_if(b, b+N, comp_func, 0);
cout << " --> "; output(b, N);
replace_copy(c.begin(), c.end(), d.begin(), 'b', 'a');
cout << c << endl;
cout << " --> " << d << endl;
return 0;
}
}}
実行結果
0, 1, 2, 0, 1, 2, 0, 1, 2, 0
--> 0, 2, 2, 0, 2, 2, 0, 2, 2, 0
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
--> 1, 0, 3, 0, 5, 0, 7, 0, 9, 0
aabbaa
--> aaaaaa
***要素削除(remove, remove_if, remove_copy, remove_copy_i...
-remove
template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIt...
範囲[first, last)内の要素で値がvalueと一致するものを削除...
-remove_if
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, Forwar...
範囲[first, last)内の要素でpredの条件と一致するものを削除...
-remove_copy
template <class InputIterator, class OutputIterator, cla...
OutputIterator remove_copy(InputIterator first, InputIt...
範囲[first, last)内の要素で値がvalueと一致するものを削除...
-remove_copy_if
template <class InputIterator, class OutputIterator, cla...
OutputIterator remove_copy_if(InputIterator first, Inpu...
範囲[first, last)内の要素でpredの条件と一致するものを削除...
-unique
template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIt...
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIt...
範囲[first, last)を最初から走査して，同じ値を持つ連続した...
例えば，1, 1, 2, 3, 3, 3, 1, 1 という配列に適用すると 1, ...
-unique_copy
template <class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIt...
template <class InputIterator, class OutputIterator, cla...
OutputIterator unique_copy(InputIterator first, InputIt...
上記uniqueのコピー版．結果をresultから始まるコンテナ・配...
***代入(fill, fill_n, generate, generate_n) [#wb8e70b3]
-fill
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, ...
範囲[first, last)の要素にvalueをセットする．
-fill_n
template <class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& valu...
firstから始まるn個の要素にvalueをセットする．
-generate
template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator la...
引数をとらず値だけを返す関数genにより，範囲[first, last)...
-generate_n
template <class OutputIterator, class Size, class Genera...
void generate_n(OutputIterator first, Size n, Generator...
引数をとらず値だけを返す関数genにより，firstから始まるn個...
***コピー(copy, copy_backward) [#cbf6c873]
-copy
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator ...
範囲[first, last)の値をresultから始まるコンテナ／配列にコ...
-copy_backward
template <class BidirectionalIterator1, class Bidirectio...
BidirectionalIterator2 copy_backward(BidirectionalItera...
BidirectionalItera...
範囲[first, last)の値をresultで終わる領域にコピーする．つ...
次にlast-2がresult-2にコピーという順番．
***反転(reverse, reverse_copy) [#w9c597c0]
-reverse
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, Bidirectional...
範囲[first, last)の要素の並びを反転する．
-reverse_copy
template <class BidirectionalIterator, class OutputItera...
OutputIterator reverse_copy(BidirectionalIterator first...
範囲[first, last)の要素の並びを反転した結果をresultにコピ...
***ローテーション(rotate, rotate_copy) [#vd1caded]
-rotate
template <class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator midd...
範囲[first, last)の要素の並びをmiddleが最初になるようにロ...
-rotate_copy
template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, Forwa...
OutputIterator result);
範囲[first, last)の要素の並びをmiddleが最初になるようにロ...
***並び替え(partition, stable_partition) [#u1f569c5]
-partition
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator f...
Predicate pred);
predがtrueを返す値を持つ要素を前に，falseを返す要素を後ろ...
-stable_partition
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(BidirectionalIte...
Predicate pred);
predがtrueを返す値を持つ要素を前に，falseを返す要素を後ろ...
***ランダムシャッフル(random_shuffle) [#zf86514c]
-random_shuffle
template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomA...
template <class RandomAccessIterator, class RandomNumber...
void random_shuffle(RandomAccessIterator first, RandomA...
範囲[first, last)の要素をランダムシャッフルする．
***要素の交換(swap, swap_ranges) [#jcde5eb3]
-swap
template <class T> void swap(T& a, T& b);
二つの値a,bを交換する．
-swap_ranges
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, F...
二つの範囲の要素を交換する．
***マージ(merge, inplace_merge) [#j96bcfd7]
-merge
template <class InputIterator1, class InputIterator2, cl...
OutputIterator merge(InputIterator1 first1, InputIterat...
InputIterator2 first2, InputIterat...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator merge(InputIterator1 first1, InputIterat...
InputIterator2 first2, InputIterat...
OutputIterator result, Compare com...
ソート済みの[first1,last1)と[first2,last2)をマージする．...
compはソートの比較関数(デフォルトは"<")．
-inplace_merge
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first, Bidirec...
template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first, Bidirec...
Compare comp);
連続した2つのソート済みの領域[first, middle)と[middle, la...
compはソートの比較関数(デフォルトは"<")．
個々の領域([first, middle)と[middle, last))はソートされて...
たとえば，
1, 3, 5, 2, 4, 6
の値が入った配列aに対して，[a[0], a[3])と[a[2], a[6])をin...
1, 2, 3, 4, 5, 6
となる．
***集合演算(set_difference, set_intersection, set_symmetr...
-set_difference
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_difference(InputIterator1 first1, In...
InputIterator2 first2, In...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_difference(InputIterator1 first1, In...
InputIterator2 first2, In...
OutputIterator result, Co...
ソート済みの[first1,last1)と[first2,last2)の差の集合を計...
つまり，[first1,last1)の要素の中で[first2,last2)に含まれ...
たとえば，
1, 2, 3, 4, 5
から
2, 4, 6, 8, 10
の差をとると，
1, 3, 5
となる．~
ここでは[first1,last1)-[first2,last2)だけであり，その逆は...
-set_intersection
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_intersection(InputIterator1 first1, ...
InputIterator2 first2, ...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_intersection(InputIterator1 first1, ...
InputIterator2 first2, ...
OutputIterator result, ...
ソート済みの[first1,last1)と[first2,last2)両方に含まれる...
たとえば，
1, 2, 3, 4, 5
と
2, 4, 6, 8, 10
の交差をとると，
2, 4
となる．
-set_symmetric_difference
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_symmetric_difference(InputIterator1 ...
InputIterator2 ...
OutputIterator ...
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_symmetric_difference(InputIterator1 ...
InputIterator2 ...
OutputIterator ...
ソート済みの[first1,last1)と[first2,last2)の双方向差の集...
たとえば，
1, 2, 3, 4, 5
と
2, 4, 6, 8, 10
の双方向差をとると，
1, 3, 5, 6, 8, 10
となる．
-set_union
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_union(InputIterator1 first1, InputIt...
InputIterator2 first2, InputIt...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_union(InputIterator1 first1, InputIt...
InputIterator2 first2, InputIt...
OutputIterator result, Compare...
ソート済みの[first1,last1)と[first2,last2)の和の集合を計...
たとえば，
1, 2, 3, 4, 5
と
2, 4, 6, 8, 10
の和をとると，
1, 2, 3, 4, 5, 6, 8, 10
となる．
**その他 [#b4185572]
***カウント(count, count_if) [#mebd1e12]
-count
template <class InputIterator, class T>
size_t count(ForwardIterator first, ForwardIterator las...
領域[first, last)から要素の値がvalueと等しいものの数を返...
-count_if
template <class InputIterator, class Predicate>
size_t count_if(ForwardIterator first, ForwardIterator ...
領域[first, last)から要素の値を関数predに渡したときにtrue...
***比較(equal, includes, lexicographical_compare, max, mi...
-equal
template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,...
template <class InputIterator1, class InputIterator2, cl...
bool equal(InputIterator1 first1, InputIterator1 last1,...
領域[first1, last1)とfirst2から始まる領域のすべての要素を...
(or 2引数をとる関数predがtrueを返す)場合trueを返す．一つ...
-includes
template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 las...
InputIterator2 first2, InputIterator2 las...
template <class InputIterator1, class InputIterator2, cl...
bool includes(InputIterator1 first1, InputIterator1 las...
InputIterator2 first2, InputIterator2 las...
Compare comp);
ソート済みの領域[first1, last1)に[first2, last2)のすべて...
-lexicographical_compare
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, Inp...
InputIterator2 first2, Inp...
template <class InputIterator1, class InputIterator2, cl...
bool lexicographical_compare(InputIterator1 first1, Inp...
InputIterator2 first2, Inp...
Compare comp );
領域[first1,last1)と[first2,last2)を辞書順でどちらが先に...
もし[first1,last1)の方が先に来る場合はtrue，そうでないと...
主に多数の文字列を辞書順に並び替えるときに用いられる．
たとえば，
kagawa
kouchi
を比べるとkagawaが前に来ると判定される．
-max
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を比べて大きい方を返す．
-min
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を比べて小さい方を返す．
***任意関数の適用(for_each, transform) [#nb669d56]
-for_each
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator la...
領域[first,last)の全要素に関数fを適用する．
たとえば，
vector<int> a(10);
という配列があるとする．
vector<int>::iterator iter = a.begin();
for(; iter != a.end(); ++iter){
f(*iter);
}
という処理をしたいとき，for_eachを用いると，
for_each(a.begin(), a.end(), f);
とコンパクトに書くことができる．
-transform
template <class InputIterator, class OutputIterator, cla...
OutputIterator transform(InputIterator first1, InputIte...
OutputIterator result, UnaryOp...
template <class InputIterator1, class InputIterator2, cl...
OutputIterator transform(InputIterator1 first1, InputIt...
InputIterator2 first2, OutputI...
BinaryOperator binary_op );
for_eachでは各要素に関数を適用できるが，適用結果を他の配...
transformは，領域[first1, last1)のすべての要素に関数opを...
2つめの定義は領域[first1, last1)とfirst2から始まる領域の...
***順列(next_permutation, prev_permutation) [#d231a72b]
-next_permutation
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, Bidi...
template <class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, Bidi...
領域[first, last)の要素で構成される順列(要素数をNとすると...
-prev_permutation
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, Bidi...
template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, Bidi...
next_permutationの逆で，
領域[first, last)の要素で構成される順列のうち，辞書順で前...
終了行:
std::algorithm
-----
#contents
-----
*algorithm [#xc14b6df]
STLのコンテナを対象とした様々なアルゴリズムが定義されてい...
各関数はコンテナでなく従来の配列でも使えるようになってい...
#include <algorithm>
**ソート [#l1bcbfcc]
***ソート(sort, stable_sort) [#ofe815bb]
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessItera...
template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessItera...
sortは[first,last)の範囲の要素を値の昇順でソートする．デ...
比較方法を自分で指定したい場合は2番目の定義を使う．
sortでは値が同じだったときに元の順番になることは保証され...
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAcce...
template <class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAcce...
stable_sortはsortと同じく要素を並び替えるものであるが，値...
コード例
#code(C){{
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct vec2
{
int x, y;
};
inline std::ostream &operator<<(std::ostream &out, const ...
{
return out << "(" << a.x << ", " << a.y << ")";
}
bool comp_vec2(vec2 a, vec2 b)
{
return a.x < b.x;
}
int main(void)
{
const int N = 10;
srand(1234567);
vector<int> a(N);
vec2 b[N];
for(int i = 0; i < N; ++i){
a[i] = rand()%10;
b[i].x = rand()%5;
b[i].y = rand()%10;
}
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
cout << "b : ";
for(int i = 0; i < N; ++i) cout << b[i] << (i == N-1 ? "...
cout << endl;
sort(a.begin(), a.end());
stable_sort(b, b+N, comp_vec2);
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
cout << "b : ";
for(int i = 0; i < N; ++i) cout << b[i] << (i == N-1 ? "...
cout << endl;
return 0;
}
}}
実行結果
a : 0, 4, 2, 6, 0, 9, 7, 8, 7, 5
b : (1, 0), (3, 3), (4, 5), (1, 6), (0, 6), (3, 7), (1, ...
a : 0, 0, 2, 4, 5, 6, 7, 7, 8, 9
b : (0, 6), (1, 0), (1, 6), (1, 9), (1, 3), (3, 3), (3, ...
***部分ソート(partial_sort, partial_sort_copy) [#ofe815bb]
template <class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAcc...
template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAcc...
範囲[first, last)の要素をソートする．ただし，ソート結果が...
それ以降の要素の順番はソートされていない．コンテナ中の部...
全体でソートしてその途中(middle)で打ち切るような処理．
partial_sortは[first, last)に結果を上書きするが，異なるコ...
template <class InputIterator, class RandomAccessIterato...
RandomAccessIterator partial_sort_copy(InputIterator fi...
RandomAccessIter...
template <class InputIterator, class RandomAccessIterato...
RandomAccessIterator partial_sort_copy(InputIterator fi...
RandomAccessIter...
Compare comp);
[first, last)のサイズ >= [result_first,result_last)のサイ...
コード例
#code(C){{
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
const int N = 10;
srand(1234567);
vector<int> a(N), b(N);
vector<int> c(N/2);
for(int i = 0; i < N; ++i){
a[i] = b[i] = rand()%10;
}
cout << "a,b : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
partial_sort(a.begin(), a.begin()+5, a.end());
//sort(a.begin(), a.begin()+5); // 単なる部分ソートとは...
cout << " a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
partial_sort_copy(b.begin(), b.end(), c.begin(), c.end());
cout << " c : ";
for(vector<int>::iterator i = c.begin(); i != c.end(); +...
cout << endl;
return 0;
}
}}
実行結果
a,b : 0, 1, 0, 4, 3, 3, 2, 4, 5, 6
a : 0, 0, 1, 2, 3, 4, 3, 4, 5, 6
c : 0, 0, 1, 2, 3
sort(a.begin(), a.begin()+5)にした場合は，
a,b : 0, 1, 0, 4, 3, 3, 2, 4, 5, 6
a : 0, 0, 1, 3, 4, 3, 2, 4, 5, 6
c : 0, 0, 1, 2, 3
となる．
***再配置(nth_element) [#r3578f46]
template <class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAcce...
template <class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAcce...
範囲[first, last)の要素のうち，nthで示される要素の値より...
コード例
#code(C){{
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
const int N = 10;
srand(12345);
vector<int> a(N);
for(int i = 0; i < N; ++i){
a[i] = rand()%10;
}
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
nth_element(a.begin(), a.begin()+3, a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
return 0;
}
}}
実行結果(Visual Studio 2010)
a : 4, 4, 5, 5, 8, 5, 7, 3, 2, 4
a : 2, 3, 4, 4, 4, 5, 5, 5, 7, 8
***ヒープソート(sort_heap, make_heap, pop_heap, push_heap...
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccess...
template <class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccess...
ヒープ構造を持つコンテナ[first, last)をヒープソートにより...
ヒープとは親ノードが常に子ノードより大きい(or小さい)ツリ...
単にヒープと呼んだ場合，バイナリツリー(バイナリヒープ，二...
ルートノードは常に最大値もしくは最小値を持つ要素になる．
そのため，ルートノードを取り出していくことでソートを行う...
ヒープ構造を作成するための関数としてmake_heapが用意されて...
template <class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccess...
template <class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccess...
ヒープは配列内に下図のように格納される．
#ref(binary_tree.jpg);
そのため，front()を用いることでルートノードを参照すること...
また，ヒープからの要素の取り出し，挿入関数(pop_heap, push...
template <class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessI...
template <class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessI...
template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccess...
template <class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccess...
pop_heapはfirstをlast-1に移動して，それ以外の要素でヒープ...
pop_heap(a.begin(), a.end());
a.pop_back()
とすることで実際に値が取り出される．push_heapの場合は逆で，
a.push_back(100);
push_heap(a.begin(), a.end());
となる．つまり，push_heapはlast-1の要素をヒープに新しく追...
これらにより，push_backやpop_backだけの場合と違い，取り出...
コード例
#code(C){{
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
const int N = 10;
vector<int> a(N);
for(int i = 0; i < N; ++i){
a[i] = i+1;
}
random_shuffle(a.begin(), a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
make_heap(a.begin(), a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
sort_heap(a.begin(), a.end());
cout << "a : ";
for(int i = 0; i < N; ++i) cout << a[i] << (i == N-1 ? "...
cout << endl;
return 0;
}
}}
実行結果
a : 9, 2, 10, 3, 1, 6, 8, 4, 5, 7
a : 10, 7, 9, 5, 2, 6, 8, 4, 3, 1
a : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
真ん中の結果を図にして確認すると以下のようになる．
#ref(binary_tree2.jpg);
***ソートの計算時間 [#p39aed21]
ソートの計算時間は環境によると思いますが，
一般的にはnth_element < sort == partial_sort < stable_sor...
sortにはクイックソートが用いられているので計算時間はO(N l...
Visual Studio 2010で実装して計測した結果を以下に示します．
実装コード
#code(C){{
#include <ctime>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
int n = 10000;
clock_t t1, t2;
vector<int> a;
ofstream fo;
fo.open("time.txt"); // 計測結果をファイル出力
for(int k = 0; k < 4; ++k){
fo << n << ", ";
a.resize(n);
for(int i = 0; i < n; ++i){
a[i] = n;
}
random_shuffle(a.begin(), a.end());
t1 = clock();
sort(a.begin(), a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << ", ";
random_shuffle(a.begin(), a.end());
t1 = clock();
stable_sort(a.begin(), a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << ", ";
random_shuffle(a.begin(), a.end());
t1 = clock();
partial_sort(a.begin(), a.begin()+n/2, a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << ", ";
random_shuffle(a.begin(), a.end());
t1 = clock();
nth_element(a.begin(), a.begin()+n/2, a.end());
t2 = clock();
fo << (double)(t2-t1)/CLOCKS_PER_SEC << endl;
n *= 10;
}
fo.close();
return 0;
}
}}
実行結果
#ref(sort_time.jpg);
partial_sortがかなり遅くなっています．Visual Studioではpa...
**検索 [#l766c100]
***値検索(find,find_if,find_first_of) [#ca4f1adf]
-find
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator l...
[first, last)内からvalueと同じ値を持つ最初の要素のイテレ...
-find_if
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterato...
[first, last)内から比較関数predが真となる最初の要素のイテ...
-find_first_of
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of(ForwardIterator1 first1,...
ForwardIterator2 first2,...
template <class ForwardIterator1, class ForwardIterator2...
ForwardIterator1 find_first_of(ForwardIterator1 first1,...
ForwardIterator2 first2,...
BinaryPredicate pred);
[first1, last1)内から[first2, last2)内の任意の要素に一致...
***シーケンス検索(search, find_end) [#hc73bc1f]
-search
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, Forwar...
ForwardIterator2 first2, Forwar...
template <class ForwardIterator1, class ForwardIterator2...
ForwardIterator1 search(ForwardIterator1 first1, Forwar...
ForwardIterator2 first2, Forwar...
BinaryPredicate pred);
[first1, last1)内から[first2, last2)のシーケンスに一致す...
見つかった位置の最初(first2に一致する要素)のイテレータを...
-find_end
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, Forw...
ForwardIterator2 first2, Forw...
template <class ForwardIterator1, class ForwardIterator2...
ForwardIterator1 find_end(ForwardIterator1 first1, Forw...
ForwardIterator2 first2, Forw...
BinaryPredicate pred);
[first1, last1)内から[first2, last2)のシーケンスに一致す...
見つかった位置の最初(first2に一致する要素)のイテレータを...
***連続する要素の検索(adjacent_find, search_n) [#l371a038]
-adjacent_find
template <class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, Fo...
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, Fo...
[first, last)内から同じ値を持つ要素が連続している最初の位...
-search_n
template <class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator first, Forward...
template <class ForwardIterator, class Size, class T, cl...
ForwardIterator search_n(ForwardIterator first, Forward...
BinaryPredicate pred);
[first1, last1)内からvalueがcount回連続で続く最初の位置を...
#code(C){{
int a[] = {1, 3, 3, 8, 8, 5};
cout << search_n(a, a+6, 2, 8)-a << endl;
}}
の場合，結果は"3"となる．
***連続しない要素の検索(mismatch) [#v02efc46]
-mismatch
template <class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(InputIter...
template <class InputIterator1, class InputIterator2, cl...
pair<InputIterator1, InputIterator2> mismatch(InputIter...
BinaryPre...
範囲[first1, last1)の要素を最初から操作していき，first2で...
predに相違条件を指定することも可能(等しいときにtrueを返す...
コード例
#code(C){{
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T>
void output(T x, int n)
{
for(int i = 0; i < n; ++i) cout << x[i] << (i == n-1 ? "...
cout << endl;
}
// 文字が1つずれていたら真を返す
bool comp_str(char x, char y){ return (x+1 == y); }
int main(void)
{
const int N = 10;
vector<int> a(N);
int b[N];
string c = "aabbaa";
string d = "bbcdbb";
for(int i = 0; i < N; ++i){
a[i] = i;
b[i] = i%5;
}
output(a, N); output(b, N);
pair<vector<int>::iterator, int*> result;
result = mismatch(a.begin(), a.end(), b);
cout << "pair of mismatch = " << *(result.first) << ", "...
cout << endl;
cout << c << endl;
cout << d << endl;
pair<string::iterator, string::iterator> result2;
result2 = mismatch(c.begin(), c.end(), d.begin(), comp_s...
cout << "pair of mismatch = " << *(result2.first) << ", ...
return 0;
}
}}
実行結果
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
0, 1, 2, 3, 4, 0, 1, 2, 3, 4
pair of mismatch = 5, 0
aabbaa
bbcdbb
pair of mismatch = b, d
***ソート済みコンテナに対する検索(equal_range, upper_boun...
-equal_range
template <class ForwardIterator, class T>
pair<ForwardIterator,ForwardIterator> equal_range(Forwa...
template <class ForwardIterator, class T, class Compare>
pair<ForwardIterator,ForwardIterator> equal_range(Forwa...
Compa...
ソート済みの[first, last)内からvalueと等しい値を持つ要素...
例えば，
#code(C){{
int c[] = {1, 3, 2, 3, 2, 1, 3, 4};
sort(c, c+8); // 1, 2, 2, 3, 3, 3, 4
pair<int*, int*> range;
range = equal_range(c, c+8, 3);
cout << "[" << range.first-c << ", " << range.second-c <...
}}
の場合，結果は"[4, 7)"となる．ちなみにソート無しだと"[6, ...
-upper_bound
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, Forw...
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, Forw...
ソート済みの[first, last)内からvalueより大きい値を持つ最...
-lower_bound
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, Forw...
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, Forw...
ソート済みの[first, last)内からvalueより小さい値を持つ最...
例えば，
#code(C){{
int d[] = {1, 3, 2, 3, 2, 1, 3, 4};
sort(d, d+8); // 1, 2, 2, 3, 3, 3, 4
int *low = lower_bound(d, d+8, 3);
int *up = upper_bound(d, d+8, 3);
cout << "[" << low-d << ", " << up-d << ")" << endl;
}}
でequal_rangeと同じ"[4, 7)"の結果が得られる．
***二分探索(binary_search) [#ube71784]
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterat...
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterat...
ソート済みの[first, last)からbinary search(二分探索)によ...
ソートする必要があるので，sortと組み合わせて使うことが多...
#code(C){{
int b[] = {1, 3, 2, 5, 4, 1};
sort(b, b+6);
if(binary_search(b, b+6, 5)){
cout << "5 is found." << endl;
}
}}
***最小値，最大値検索(min_element, max_element) [#e7d8b462]
-min_element
template <class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, Forw...
template <class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, Forw...
[first, last)内から最小の値を持つ要素のイテレータを返す．
-max_element
template <class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, Forw...
template <class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, Forw...
[first, last)内から最大の値を持つ要素のイテレータを返す．
例えば，
#code(C){{
int e[] = {3, 2, 1, 3, 2, 1, 4, 3};
int *minp = min_element(e, e+8);
int *maxp = max_element(e, e+8);
cout << "min element : " << minp-e << "(" << *minp << ")...
cout << "max element : " << maxp-e << "(" << *maxp << ")...
}}
結果は以下のようになる．
min element : 2(1)
max element : 6(4)
**コンテナの操作 [#qcdc8ef4]
***置き換え(replace, replace_if, replace_copy, replacy_co...
-replace
template <class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator las...
コンテナ・配列の範囲[first, last)内の要素で値がold_value...
-replace_if
template <class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator ...
コンテナ・配列の範囲[first, last)内の要素でpredで示された...
-replace_copy
template <class InputIterator, class OutputIterator, cla...
OutputIterator replace_copy(InputIterator first, InputI...
const T& old_value, const T...
コンテナ・配列の範囲[first, last)内の要素で値がold_value...
resultで始まるコンテナにコピーする．
-replace_copy_if
template <class InputIterator, class OutputIterator, cla...
OutputIterator replace_copy_if(InputIterator first, Inp...
Predicate pred, const T&...
コンテナ・配列の範囲[first, last)内の要素でpredで示された...
resultで始まるコンテナにコピーする．
コード例
#code(C){{
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T>
void output(T x, int n)
{
for(int i = 0; i < n; ++i) cout << x[i] << (i == n-1 ? "...
cout << endl;
}
bool comp_func(int x){ return (x%2 == 0); }
int main(void)
{
const int N = 10;
vector<int> a(N);
int b[N];
string c = "aabbaa";
string d;
d.resize(c.size());
for(int i = 0; i < N; ++i){
a[i] = i%3;
b[i] = i+1;
}
output(a, N);
replace(a.begin(), a.end(), 1, 2);
cout << " --> "; output(a, N);
output(b, N);
replace_if(b, b+N, comp_func, 0);
cout << " --> "; output(b, N);
replace_copy(c.begin(), c.end(), d.begin(), 'b', 'a');
cout << c << endl;
cout << " --> " << d << endl;
return 0;
}
}}
実行結果
0, 1, 2, 0, 1, 2, 0, 1, 2, 0
--> 0, 2, 2, 0, 2, 2, 0, 2, 2, 0
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
--> 1, 0, 3, 0, 5, 0, 7, 0, 9, 0
aabbaa
--> aaaaaa
***要素削除(remove, remove_if, remove_copy, remove_copy_i...
-remove
template <class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIt...
範囲[first, last)内の要素で値がvalueと一致するものを削除...
-remove_if
template <class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, Forwar...
範囲[first, last)内の要素でpredの条件と一致するものを削除...
-remove_copy
template <class InputIterator, class OutputIterator, cla...
OutputIterator remove_copy(InputIterator first, InputIt...
範囲[first, last)内の要素で値がvalueと一致するものを削除...
-remove_copy_if
template <class InputIterator, class OutputIterator, cla...
OutputIterator remove_copy_if(InputIterator first, Inpu...
範囲[first, last)内の要素でpredの条件と一致するものを削除...
-unique
template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIt...
template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIt...
範囲[first, last)を最初から走査して，同じ値を持つ連続した...
例えば，1, 1, 2, 3, 3, 3, 1, 1 という配列に適用すると 1, ...
-unique_copy
template <class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first, InputIt...
template <class InputIterator, class OutputIterator, cla...
OutputIterator unique_copy(InputIterator first, InputIt...
上記uniqueのコピー版．結果をresultから始まるコンテナ・配...
***代入(fill, fill_n, generate, generate_n) [#wb8e70b3]
-fill
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, ...
範囲[first, last)の要素にvalueをセットする．
-fill_n
template <class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& valu...
firstから始まるn個の要素にvalueをセットする．
-generate
template <class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator la...
引数をとらず値だけを返す関数genにより，範囲[first, last)...
-generate_n
template <class OutputIterator, class Size, class Genera...
void generate_n(OutputIterator first, Size n, Generator...
引数をとらず値だけを返す関数genにより，firstから始まるn個...
***コピー(copy, copy_backward) [#cbf6c873]
-copy
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator ...
範囲[first, last)の値をresultから始まるコンテナ／配列にコ...
-copy_backward
template <class BidirectionalIterator1, class Bidirectio...
BidirectionalIterator2 copy_backward(BidirectionalItera...
BidirectionalItera...
範囲[first, last)の値をresultで終わる領域にコピーする．つ...
次にlast-2がresult-2にコピーという順番．
***反転(reverse, reverse_copy) [#w9c597c0]
-reverse
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, Bidirectional...
範囲[first, last)の要素の並びを反転する．
-reverse_copy
template <class BidirectionalIterator, class OutputItera...
OutputIterator reverse_copy(BidirectionalIterator first...
範囲[first, last)の要素の並びを反転した結果をresultにコピ...
***ローテーション(rotate, rotate_copy) [#vd1caded]
-rotate
template <class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator midd...
範囲[first, last)の要素の並びをmiddleが最初になるようにロ...
-rotate_copy
template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, Forwa...
OutputIterator result);
範囲[first, last)の要素の並びをmiddleが最初になるようにロ...
***並び替え(partition, stable_partition) [#u1f569c5]
-partition
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator f...
Predicate pred);
predがtrueを返す値を持つ要素を前に，falseを返す要素を後ろ...
-stable_partition
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(BidirectionalIte...
Predicate pred);
predがtrueを返す値を持つ要素を前に，falseを返す要素を後ろ...
***ランダムシャッフル(random_shuffle) [#zf86514c]
-random_shuffle
template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomA...
template <class RandomAccessIterator, class RandomNumber...
void random_shuffle(RandomAccessIterator first, RandomA...
範囲[first, last)の要素をランダムシャッフルする．
***要素の交換(swap, swap_ranges) [#jcde5eb3]
-swap
template <class T> void swap(T& a, T& b);
二つの値a,bを交換する．
-swap_ranges
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1, F...
二つの範囲の要素を交換する．
***マージ(merge, inplace_merge) [#j96bcfd7]
-merge
template <class InputIterator1, class InputIterator2, cl...
OutputIterator merge(InputIterator1 first1, InputIterat...
InputIterator2 first2, InputIterat...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator merge(InputIterator1 first1, InputIterat...
InputIterator2 first2, InputIterat...
OutputIterator result, Compare com...
ソート済みの[first1,last1)と[first2,last2)をマージする．...
compはソートの比較関数(デフォルトは"<")．
-inplace_merge
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first, Bidirec...
template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first, Bidirec...
Compare comp);
連続した2つのソート済みの領域[first, middle)と[middle, la...
compはソートの比較関数(デフォルトは"<")．
個々の領域([first, middle)と[middle, last))はソートされて...
たとえば，
1, 3, 5, 2, 4, 6
の値が入った配列aに対して，[a[0], a[3])と[a[2], a[6])をin...
1, 2, 3, 4, 5, 6
となる．
***集合演算(set_difference, set_intersection, set_symmetr...
-set_difference
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_difference(InputIterator1 first1, In...
InputIterator2 first2, In...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_difference(InputIterator1 first1, In...
InputIterator2 first2, In...
OutputIterator result, Co...
ソート済みの[first1,last1)と[first2,last2)の差の集合を計...
つまり，[first1,last1)の要素の中で[first2,last2)に含まれ...
たとえば，
1, 2, 3, 4, 5
から
2, 4, 6, 8, 10
の差をとると，
1, 3, 5
となる．~
ここでは[first1,last1)-[first2,last2)だけであり，その逆は...
-set_intersection
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_intersection(InputIterator1 first1, ...
InputIterator2 first2, ...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_intersection(InputIterator1 first1, ...
InputIterator2 first2, ...
OutputIterator result, ...
ソート済みの[first1,last1)と[first2,last2)両方に含まれる...
たとえば，
1, 2, 3, 4, 5
と
2, 4, 6, 8, 10
の交差をとると，
2, 4
となる．
-set_symmetric_difference
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_symmetric_difference(InputIterator1 ...
InputIterator2 ...
OutputIterator ...
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_symmetric_difference(InputIterator1 ...
InputIterator2 ...
OutputIterator ...
ソート済みの[first1,last1)と[first2,last2)の双方向差の集...
たとえば，
1, 2, 3, 4, 5
と
2, 4, 6, 8, 10
の双方向差をとると，
1, 3, 5, 6, 8, 10
となる．
-set_union
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_union(InputIterator1 first1, InputIt...
InputIterator2 first2, InputIt...
OutputIterator result);
template <class InputIterator1, class InputIterator2, cl...
OutputIterator set_union(InputIterator1 first1, InputIt...
InputIterator2 first2, InputIt...
OutputIterator result, Compare...
ソート済みの[first1,last1)と[first2,last2)の和の集合を計...
たとえば，
1, 2, 3, 4, 5
と
2, 4, 6, 8, 10
の和をとると，
1, 2, 3, 4, 5, 6, 8, 10
となる．
**その他 [#b4185572]
***カウント(count, count_if) [#mebd1e12]
-count
template <class InputIterator, class T>
size_t count(ForwardIterator first, ForwardIterator las...
領域[first, last)から要素の値がvalueと等しいものの数を返...
-count_if
template <class InputIterator, class Predicate>
size_t count_if(ForwardIterator first, ForwardIterator ...
領域[first, last)から要素の値を関数predに渡したときにtrue...
***比較(equal, includes, lexicographical_compare, max, mi...
-equal
template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,...
template <class InputIterator1, class InputIterator2, cl...
bool equal(InputIterator1 first1, InputIterator1 last1,...
領域[first1, last1)とfirst2から始まる領域のすべての要素を...
(or 2引数をとる関数predがtrueを返す)場合trueを返す．一つ...
-includes
template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 las...
InputIterator2 first2, InputIterator2 las...
template <class InputIterator1, class InputIterator2, cl...
bool includes(InputIterator1 first1, InputIterator1 las...
InputIterator2 first2, InputIterator2 las...
Compare comp);
ソート済みの領域[first1, last1)に[first2, last2)のすべて...
-lexicographical_compare
template <class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1, Inp...
InputIterator2 first2, Inp...
template <class InputIterator1, class InputIterator2, cl...
bool lexicographical_compare(InputIterator1 first1, Inp...
InputIterator2 first2, Inp...
Compare comp );
領域[first1,last1)と[first2,last2)を辞書順でどちらが先に...
もし[first1,last1)の方が先に来る場合はtrue，そうでないと...
主に多数の文字列を辞書順に並び替えるときに用いられる．
たとえば，
kagawa
kouchi
を比べるとkagawaが前に来ると判定される．
-max
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を比べて大きい方を返す．
-min
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を比べて小さい方を返す．
***任意関数の適用(for_each, transform) [#nb669d56]
-for_each
template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator la...
領域[first,last)の全要素に関数fを適用する．
たとえば，
vector<int> a(10);
という配列があるとする．
vector<int>::iterator iter = a.begin();
for(; iter != a.end(); ++iter){
f(*iter);
}
という処理をしたいとき，for_eachを用いると，
for_each(a.begin(), a.end(), f);
とコンパクトに書くことができる．
-transform
template <class InputIterator, class OutputIterator, cla...
OutputIterator transform(InputIterator first1, InputIte...
OutputIterator result, UnaryOp...
template <class InputIterator1, class InputIterator2, cl...
OutputIterator transform(InputIterator1 first1, InputIt...
InputIterator2 first2, OutputI...
BinaryOperator binary_op );
for_eachでは各要素に関数を適用できるが，適用結果を他の配...
transformは，領域[first1, last1)のすべての要素に関数opを...
2つめの定義は領域[first1, last1)とfirst2から始まる領域の...
***順列(next_permutation, prev_permutation) [#d231a72b]
-next_permutation
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, Bidi...
template <class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, Bidi...
領域[first, last)の要素で構成される順列(要素数をNとすると...
-prev_permutation
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, Bidi...
template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, Bidi...
next_permutationの逆で，
領域[first, last)の要素で構成される順列のうち，辞書順で前...
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
