algorithm

std::algorithm

algorithm

algorithm†

STLのコンテナを対象とした様々なアルゴリズムが定義されている．各関数はコンテナでなく従来の配列でも使えるようになっている(反復子の代わりにポインタを渡せばよい)．

#include <algorithm>

↑

ソート†

↑

ソート(sort, stable_sort)†

template <class RandomAccessIterator>
 void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
 void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sortは[first,last)の範囲の要素を値の昇順でソートする．デフォルトではオペレータ"<"で比較され，比較方法を自分で指定したい場合は2番目の定義を使う． sortでは値が同じだったときに元の順番になることは保証されていない(いわゆる安定なソートではない)．

template <class RandomAccessIterator>
 void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
 void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

stable_sortはsortと同じく要素を並び替えるものであるが，値が同じ要素の元の順番は保存される．

コード例

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct vec2
{
    int x, y;
};
inline std::ostream &operator<<(std::ostream &out, const vec2 &a)
{
    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, 9), (4, 1), (1, 3), (4, 4)
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, 7), (4, 5), (4, 1), (4, 4)

↑

部分ソート(partial_sort, partial_sort_copy)†

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)の要素をソートする．ただし，ソート結果が書き込まれるのは[first, middle)の範囲のみで，それ以降の要素の順番はソートされていない．コンテナ中の部分的な範囲だけでソートするのではなく，全体でソートしてその途中(middle)で打ち切るような処理．

partial_sortは[first, last)に結果を上書きするが，異なるコンテナにコピーしたい場合はpartial_sort_copyを用いる．

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_first,result_last)のサイズである．

コード例

#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());
        
    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(); ++i) cout << *i << (i == c.end()-1 ? "" : ", ");
    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)†

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, last)の要素のうち，nthで示される要素の値より小さい値を持つ要素はnthの前に，大きい値を持つ要素はnthの後に置かれる．再配置後の要素の順番は保証されない．

コード例

#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, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare>
 void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

ヒープ構造を持つコンテナ[first, last)をヒープソートによりソートする．ヒープとは親ノードが常に子ノードより大きい(or小さい)ツリーのことであり，単にヒープと呼んだ場合，バイナリツリー(バイナリヒープ，二分ヒープ)を指すことが多い．ルートノードは常に最大値もしくは最小値を持つ要素になる．そのため，ルートノードを取り出していくことでソートを行うことができる(ヒープソート,O(N log N))．

ヒープ構造を作成するための関数としてmake_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);

ヒープは配列内に下図のように格納される．

そのため，front()を用いることでルートノードを参照することができる．

また，ヒープからの要素の取り出し，挿入関数(pop_heap, push_heap)もある．

template <class RandomAccessIterator> 
 void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare> 
 void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template <class RandomAccessIterator> 
 void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare> 
 void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

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だけの場合と違い，取り出し，挿入後もヒープ構造が保たれる．

コード例

#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

真ん中の結果を図にして確認すると以下のようになる．

↑

ソートの計算時間†

ソートの計算時間は環境によると思いますが，一般的にはnth_element < sort == partial_sort < stable_sortだと思われます． sortにはクイックソートが用いられているので計算時間はO(N log N) ～ O(N^2)です．

Visual Studio 2010で実装して計測した結果を以下に示します．

実装コード

#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;
}

実行結果

partial_sortがかなり遅くなっています．Visual Studioではpartial_sortの中身はstable_sortになっているのかもしれません．

↑

検索†

↑

値検索(find,find_if,find_first_of)†

find

template <class InputIterator, class T> 
 InputIterator find(InputIterator first, InputIterator last, const T& value);

[first, last)内からvalueと同じ値を持つ最初の要素のイテレータを返す．

find_if

template <class InputIterator, class Predicate>
 InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

[first, last)内から比較関数predが真となる最初の要素のイテレータを返す．

find_first_of

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)内の任意の要素に一致する最初の要素のイテレータを返す．

↑

シーケンス検索(search, find_end)†

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)のシーケンスに一致する部分を最初から検索し，見つかった位置の最初(first2に一致する要素)のイテレータを返す．

find_end

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)のシーケンスに一致する部分を最後から検索し，見つかった位置の最初(first2に一致する要素)のイテレータを返す．

↑

連続する要素の検索(adjacent_find, search_n)†

adjacent_find

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)内から同じ値を持つ要素が連続している最初の位置を返す．

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>
 ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, 
                          BinaryPredicate pred);

[first1, last1)内からvalueがcount回連続で続く最初の位置を返す．例えば，

  1
  2

    int a[] = {1, 3, 3, 8, 8, 5};
    cout << search_n(a, a+6, 2, 8)-a << endl;

の場合，結果は"3"となる．

↑

連続しない要素の検索(mismatch)†

mismatch

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)の要素を最初から操作していき，first2で始まる範囲の要素と異なる値を持つ要素が出てきたらそのペアを作成して返す． predに相違条件を指定することも可能(等しいときにtrueを返す関数)．

コード例

#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_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) << ", " << *(result.second) << endl;
    cout << endl;
 
    cout << c << endl;
    cout << d << endl;
    pair<string::iterator, string::iterator> result2;
    result2 = mismatch(c.begin(), c.end(), d.begin(), comp_str);
    cout << "pair of mismatch = " << *(result2.first) << ", " << *(result2.second) << endl;
 
    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_bound, lower_bound)†

equal_range

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);

ソート済みの[first, last)内からvalueと等しい値を持つ要素の連続する範囲を返す．例えば，

    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 << ")" << endl;

の場合，結果は"[4, 7)"となる．ちなみにソート無しだと"[6, 7)"となった(環境によるかもしれない)．

upper_bound

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より大きい値を持つ最初の要素を返す．

lower_bound

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より小さい値を持つ最初の要素を返す．例えば，

    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)†

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)からbinary search(二分探索)によりvalueに一致する要素を検索し，もしあればtrueを返す．ソートする必要があるので，sortと組み合わせて使うことが多い．例えば，

    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)†

min_element

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)内から最小の値を持つ要素のイテレータを返す．

max_element

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)内から最大の値を持つ要素のイテレータを返す．例えば，

    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 << ")" << endl;
    cout << "max element : " << maxp-e << "(" << *maxp << ")" << endl;

結果は以下のようになる．

min element : 2(1)
max element : 6(4)

↑

コンテナの操作†

↑

置き換え(replace, replace_if, replace_copy, replacy_copy_if)†

replace

template <class ForwardIterator, class T> 
 void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

コンテナ・配列の範囲[first, last)内の要素で値がold_valueのものをnew_valueに置き換える．

replace_if

template <class ForwardIterator, class Predicate, class T>
 void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

コンテナ・配列の範囲[first, last)内の要素でpredで示された関数がtrueを返したものをnew_valueで置き換える．

replace_copy

template <class InputIterator, class OutputIterator, class T>
 OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, 
                             const T& old_value, const T& new_value);

コンテナ・配列の範囲[first, last)内の要素で値がold_valueのものをnew_valueに置き換えた結果を resultで始まるコンテナにコピーする．

replace_copy_if

template <class InputIterator, class OutputIterator, class Predicate, class T>
 OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, 
                                Predicate pred, const T& new_value);

コンテナ・配列の範囲[first, last)内の要素でpredで示された関数がtrueを返したものをnew_valueに置き換えた結果を resultで始まるコンテナにコピーする．

コード例

#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_if, unique, unique_copy)†

remove

template <class ForwardIterator, class T> 
 ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

範囲[first, last)内の要素で値がvalueと一致するものを削除する．

remove_if

template <class ForwardIterator, class Predicate> 
 ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

範囲[first, last)内の要素でpredの条件と一致するものを削除する．

remove_copy

template <class InputIterator, class OutputIterator, class T>
 OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);

範囲[first, last)内の要素で値がvalueと一致するものを削除した結果をresultに格納する．

remove_copy_if

template <class InputIterator, class OutputIterator, class Predicate>
 OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

範囲[first, last)内の要素でpredの条件と一致するものを削除した結果をresultに格納する．

unique
```
template <class ForwardIterator> 
 ForwardIterator unique(ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
 ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);
```
範囲[first, last)を最初から走査して，同じ値を持つ連続した2つの要素の後ろの方を削除する．これを指定した範囲全てで行う．例えば，1, 1, 2, 3, 3, 3, 1, 1 という配列に適用すると 1, 2, 3, 1 という結果が得られる．

unique_copy

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);

上記uniqueのコピー版．結果をresultから始まるコンテナ・配列に格納する．

↑

代入(fill, fill_n, generate, generate_n)†

fill

template <class ForwardIterator, class T> 
 void fill(ForwardIterator first, ForwardIterator last, const T& value);

範囲[first, last)の要素にvalueをセットする．

fill_n

template <class OutputIterator, class Size, class T> 
 void fill_n(OutputIterator first, Size n, const T& value);

firstから始まるn個の要素にvalueをセットする．

generate

template <class ForwardIterator, class Generator>
 void generate(ForwardIterator first, ForwardIterator last, Generator gen);

引数をとらず値だけを返す関数genにより，範囲[first, last)に値をセットする．

generate_n
```
template <class OutputIterator, class Size, class Generator>
 void generate_n(OutputIterator first, Size n, Generator gen)
```
引数をとらず値だけを返す関数genにより，firstから始まるn個の要素に値をセットする．

↑

コピー(copy, copy_backward)†

copy
```
template <class InputIterator, class OutputIterator> 
 OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
```
範囲[first, last)の値をresultから始まるコンテナ／配列にコピーする(コピー元:[first,last)，コピー先:result)．

copy_backward

template <class BidirectionalIterator1, class BidirectionalIterator2> 
 BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, 
                                      BidirectionalIterator2 result);

範囲[first, last)の値をresultで終わる領域にコピーする．つまり，最初にlast-1の値がresult-1にコピーされ，次にlast-2がresult-2にコピーという順番．

↑

反転(reverse, reverse_copy)†

reverse

template <class BidirectionalIterator> 
 void reverse(BidirectionalIterator first, BidirectionalIterator last);

範囲[first, last)の要素の並びを反転する．

reverse_copy

template <class BidirectionalIterator, class OutputIterator> 
 OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

範囲[first, last)の要素の並びを反転した結果をresultにコピーする．

↑

ローテーション(rotate, rotate_copy)†

rotate

template <class ForwardIterator>
 void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

範囲[first, last)の要素の並びをmiddleが最初になるようにローテーションする．

rotate_copy

template <class ForwardIterator, class OutputIterator> 
 OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, 
                            OutputIterator result);

範囲[first, last)の要素の並びをmiddleが最初になるようにローテーションした結果をresultにコピーする．

↑

並び替え(partition, stable_partition)†

partition template <class BidirectionalIterator, class Predicate>
```
 BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, 
                                 Predicate pred);
```
predがtrueを返す値を持つ要素を前に，falseを返す要素を後ろになるように並び替える．並び替え後の元の順番は保証されない．

stable_partition template <class BidirectionalIterator, class Predicate>
```
 BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last,
                                        Predicate pred);
```
predがtrueを返す値を持つ要素を前に，falseを返す要素を後ろになるように並び替える．並び替え後の元の順番が保証される．

↑

ランダムシャッフル(random_shuffle)†

random_shuffle

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)の要素をランダムシャッフルする．

↑

要素の交換(swap, swap_ranges)†

swap

template <class T> void swap(T& a, T& b);

二つの値a,bを交換する．

swap_ranges template <class ForwardIterator1, class ForwardIterator2>
```
 ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
```
二つの範囲の要素を交換する．

↑

マージ(merge, inplace_merge)†

merge

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);

ソート済みの[first1,last1)と[first2,last2)をマージする．マージ後のコンテナ(result)はソートされている． compはソートの比較関数(デフォルトは"<")．

inplace_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)をマージする．マージ後の領域([fisrt, last))はソートされている． compはソートの比較関数(デフォルトは"<")．個々の領域([first, middle)と[middle, last))はソートされていなければならない．たとえば，
```
1, 3, 5, 2, 4, 6
```
の値が入った配列aに対して，[a[0], a[3])と[a[2], a[6])をinplace_mergeすると，aは
```
1, 2, 3, 4, 5, 6
```
となる．

↑

集合演算(set_difference, set_intersection, set_symmetric_difference, set_union)†

set_difference

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)の差の集合を計算して，resultに格納する．返値はresultに格納された要素の末尾である．つまり，[first1,last1)の要素の中で[first2,last2)に含まれないものをresultに格納する．たとえば，

1, 2, 3, 4, 5

から

2, 4, 6, 8, 10

の差をとると，

1, 3, 5

となる．
ここでは[first1,last1)-[first2,last2)だけであり，その逆はない．双方向の差をとる場合はset_symmetric_differenceを用いる．

set_intersection

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)両方に含まれる要素の集合(交差)を計算して，resultに格納する．返値はresultに格納された要素の末尾である．たとえば，

1, 2, 3, 4, 5

と

2, 4, 6, 8, 10

の交差をとると，

2, 4

となる．

set_symmetric_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)の双方向差の集合を計算して，resultに格納する．返値はresultに格納された要素の末尾である．たとえば，

1, 2, 3, 4, 5

と

2, 4, 6, 8, 10

の双方向差をとると，

1, 3, 5, 6, 8, 10

となる．

set_union

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)の和の集合を計算して，resultに格納する．返値はresultに格納された要素の末尾である．たとえば，

1, 2, 3, 4, 5

と

2, 4, 6, 8, 10

の和をとると，

1, 2, 3, 4, 5, 6, 8, 10

となる．

↑

その他†

↑

カウント(count, count_if)†

count

template <class InputIterator, class T> 
 size_t count(ForwardIterator first, ForwardIterator last, const T& value);

領域[first, last)から要素の値がvalueと等しいものの数を返す．

count_if

template <class InputIterator, class Predicate> 
 size_t count_if(ForwardIterator first, ForwardIterator last, Predicate pred);

領域[first, last)から要素の値を関数predに渡したときにtrueを返すものの数を返す．

↑

比較(equal, includes, lexicographical_compare, max, min)†

equal

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);

領域[first1, last1)とfirst2から始まる領域のすべての要素を順番に比較してすべて等しい (or 2引数をとる関数predがtrueを返す)場合trueを返す．一つでも異なる要素があればfalseを返す．

includes

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)のすべての要素が含まれればtrueを返す．

lexicographical_compare

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，そうでないときはfalseを返す．主に多数の文字列を辞書順に並び替えるときに用いられる．たとえば，

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)†

for_each

template <class InputIterator, class Function> 
 Function for_each(InputIterator first, InputIterator last, Function f);

領域[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, class UnaryOperator> 
 OutputIterator transform(InputIterator first1, InputIterator last1,
                          OutputIterator result, UnaryOperator op);

template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperator> 
 OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
                          InputIterator2 first2, OutputIterator result,
                          BinaryOperator binary_op );
```
for_eachでは各要素に関数を適用できるが，適用結果を他の配列に格納したい場合はtransformが使える． transformは，領域[first1, last1)のすべての要素に関数opを適用して，その結果(返値)をresultに格納する(opは1引数をとり，値を返す関数)． 2つめの定義は領域[first1, last1)とfirst2から始まる領域の要素を関数opに渡して，その結果を(返値)をresultに格納する(opは2引数をとり，値を返す関数)．

↑

順列(next_permutation, prev_permutation)†

next_permutation

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)の要素で構成される順列(要素数をNとするとN!個)のうち，辞書順で次にくるものを探して，[first,last)の要素の順番を入れ替える．

prev_permutation

template <class BidirectionalIterator>
 bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
 bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

next_permutationの逆で，領域[first, last)の要素で構成される順列のうち，辞書順で前にくるものを探して，[first,last)の要素の順番を入れ替える．

Menu

algorithm†

ソート†

ソート(sort, stable_sort)†

部分ソート(partial_sort, partial_sort_copy)†

再配置(nth_element)†

ヒープソート(sort_heap, make_heap, pop_heap, push_heap)†

ソートの計算時間†

検索†

値検索(find,find_if,find_first_of)†

シーケンス検索(search, find_end)†

連続する要素の検索(adjacent_find, search_n)†

連続しない要素の検索(mismatch)†

ソート済みコンテナに対する検索(equal_range, upper_bound, lower_bound)†

二分探索(binary_search)†

最小値，最大値検索(min_element, max_element)†

コンテナの操作†

置き換え(replace, replace_if, replace_copy, replacy_copy_if)†

要素削除(remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy)†

代入(fill, fill_n, generate, generate_n)†

コピー(copy, copy_backward)†

反転(reverse, reverse_copy)†

ローテーション(rotate, rotate_copy)†

並び替え(partition, stable_partition)†

ランダムシャッフル(random_shuffle)†

要素の交換(swap, swap_ranges)†

マージ(merge, inplace_merge)†

集合演算(set_difference, set_intersection, set_symmetric_difference, set_union)†

その他†

カウント(count, count_if)†

比較(equal, includes, lexicographical_compare, max, min)†

任意関数の適用(for_each, transform)†

順列(next_permutation, prev_permutation)†