STLリファレンス

<algorithm>

[ for_each ]

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

[first,last)にあるすべてのiに対し、f(*i)を行います。f(*i)の戻り値は無視されます。

[ find, find_if ]

- 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を返します。

[ 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)が見つかる(部分列が存在する)なら、最後に見つかった位置を返します。
見つからない場合はlast1を返します。

[ 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)の要素のどれかが見つかれば、その位置を返します。
見つからない場合はlast1を返します。

[ 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)にあるiとi+1に対し、*i == *(i+1), pred(*i,*(i+1)) != falseとなるiを返します。
つまりは隣接する等しい要素を探してくれます。

[ count, count_if ]

- 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の個数を返します。

[ 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)にあるiとj=first2+(i-first1)に対し、*i != *j, pred(*i.*j) == falseとなるi,jのpairを返します。
すなわち2つのシーケンスの不一致箇所を見つけます。

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

2つのシーケンス[first1,last1)と[first2,last2)の対応する要素がすべて等しい(*i == *j, pred(*i,*j) != false)ならばtrueを返します。

[ search ]

- 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)が現れる(部分列が存在する)なら、その位置を返します。

  // ABRACADABRA の中にある CAD の位置
  char a[] = "ABRACADABRA";
  char b[] = "CAD";
  char* p = search(a, a+11, b, b+3);
  cout << a << " contains " << b
       << " at #" << distance(a,p) << endl;

  実行結果:
    ABRACADABRA contains CAD at #4

[ 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を返します。

[ copy, copy_backward ]

- 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となります。

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

2つのシーケンス[first1,last1),[first2,...)のそれぞれの要素を交換します。

  // 最初の7文字を交換
  char a[] = "small   letters";
  char b[] = "CAPITAL LETTERS";
  cout << "before: a = " << a << " ,  b = " <<  b << endl;
  swap_ranges(a, a+7, b);
  cout << "after:  a = " << a << " ,  b = " <<  b << endl;

  実行結果:
    before: a = small   letters ,  b = CAPITAL LETTERS
    after:  a = CAPITAL letters ,  b = small   LETTERS

[ iter_swap ]

- template<class ForwardIterator1, class ForwardIterator2>
  void
  iter_swap(ForwardIterator1 a,
            ForwardIterator2 b);

*aと*bの内容を交換します。

[ transform ]

- 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を返します。

[ replace, replace_if ]

- 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を代入します。

[ replace_copy, replace_copy_if ]

- 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を返します。

[ fill, fill_n ]

- 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で埋めます。

[ generate, genarate_n ]

- 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()の戻り値で埋めます。

[ remove, remove_if ]

- 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)が新たなシーケンスとなります。
取り除かれた要素に対するメモリの返却などの後始末は行われません。これは要素の削除を伴うその他のアルゴリズムでも同様です。
ですからたとえばvector<int> ivから値が0の要素を取り除くには:

 vector<int> iv;
 vector<int>::iterator i = remove(iv.begin(), iv.end(), 0);
 iv.erase(i, iv.end()); // これが必要

[ remove_copy, remove_copy_if ]

- 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を返します。

[ 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)にあるi,i-1に対し、*i==*(i-1),pred(*i,*(i-1))!=falseである*iをシーケンスから取り除きます。
隣接する愛等しい要素を取り除いたシーケンスの末尾(の直後)を返します。

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

隣接する相等しい要素を取り除いたシーケンスを[result,result+N)に作ります(N:得られた要素の個数)。
result+Nを返します。

[ reverse, reverse_copy ]

- 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を返します。

[ rotate, rotate_copy ]

- 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を返します。

[ 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)をかき混ぜます。
関数オブジェクトrandは1個の引数nを取り、[0,n)の範囲にある乱数を返さなければなりません。

  // 配列をシャッフルする
  int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  cout << "before: "; iter_print(a, a+10);
  random_shuffle(a,a+10);
  cout << "after:  "; iter_print(a, a+10);

  実行結果:
    before: [0 1 2 3 4 5 6 7 8 9]
    after:  [4 3 0 2 6 7 8 9 5 1]

[ partition, stable_partition ]

- 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を行います。

  // 大文字と小文字に分割する
  char str[] = "AbcDEfGhiJ";
  char* first = str;
  char* last  = str + strlen(str);
  cout << "before: "; iter_print(first,last);
  char* middle = stable_partition(first,last,isupper);
  cout << "after:  "; iter_print(first,middle,last);

  実行結果:
    before: [A b c D E f G h i J]
    after:  [A D E G J|b c f h i]

[sort,stabe_sort]

- 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は元の順序を保った安定なソートを行います。

[ partial_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)にある要素の順序は不定となります。

[ 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_last-result_first個をソートしたシーケンスを[result_first,result_last)に置きます。
ただしlast-first < result_last-result_firstであるときは、ソートされる要素の個数はlast-firstで抑えられます。
partial_sort_copyはresult_lastもしくはresult_first+(last-first)を返します。

[ 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,nth)の範囲にある任意のiと[nth,last)の範囲にある任意のjに対し、!(*i>*j),comp(*i,*j)==false)となるように要素の入れ替えを行います。

  // 大きい順に並べたときの上位5つ
  int a[] = { 3, 5, 2, 4, 7, 6, 8, 6, 9, 7 };
  int* first  = a;
  int* nth    = a + 5;
  int* last   = a + 10;
  cout << "before: "; iter_print(first,nth,last);
  nth_element(first,nth,last,greater<int>());
  cout << "after:  "; iter_print(first,nth,last);

  実行結果:
    before: [3 5 2 4 7|6 8 6 9 7]
    after:  [9 8 7 7 6|6 5 4 3 2]

[ 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 a[] = { 0, 1, 3, 3, 6, 7, 7, 8, 9, 9 };
  int* point;
  point = lower_bound(a, a+10, 3);
  cout << "lower bound of 3: "; iter_print(a,point,a+10);
  point = lower_bound(a, a+10, 5);
  cout << "lower bound of 5: "; iter_print(a,point,a+10);

  実行結果:
    lower bound of 3: [0 1|3 3 6 7 7 8 9 9]
    lower bound of 5: [0 1 3 3|6 7 7 8 9 9]

[ 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より大きい最初の要素の位置を返します。

  int a[] = { 0, 1, 3, 3, 6, 7, 7, 8, 9, 9 };
  int* point;
  point = upper_bound(a, a+10, 3);
  cout << "upper bound of 3: "; iter_print(a,point,a+10);
  point = upper_bound(a, a+10, 5);
  cout << "upper bound of 5: "; iter_print(a,point,a+10);

  実行結果:
    upper bound of 3: [0 1 3 3|6 7 7 8 9 9]
    upper bound of 5: [0 1 3 3|6 7 7 8 9 9]

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

lower_boundおよびupper_boundのそれぞれの結果をfirst,secondとするpairを返します。

  int a[] = { 0, 1, 3, 3, 6, 7, 7, 8, 9, 9 };
  pair<int*,int*> range;
  range = equal_range(a, a+10, 3);
  cout << "range of 3: "; iter_print(a,range,a+10);
  range = equal_range(a, a+10, 5);
  cout << "range of 5: "; iter_print(a,range,a+10);

  実行結果:
    range of 3: [0 1(3 3)6 7 7 8 9 9]
    range of 5: [0 1 3 3()6 7 7 8 9 9]

[ 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)に対して二分検索を行い、valueと等しいものが存在すればtrueを返します。

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

ソートされた2つのシーケンス[first1,last1),[first2,last2)をマージし、ソートされた結果を[result,RET)に置きます。
RETはmergeの戻り値です。

[ 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)をマージし、結果を[first,last)に置きます。

  int a[] = { 0, 2, 4, 6, 8, 1, 3, 5, 7, 9 };
  cout << "before: "; iter_print(a,a+5,a+10);
  inplace_merge(a,a+5,a+10);
  cout << "after:  "; iter_print(a,a+10);

  実行結果:
    before: [0 2 4 6 8|1 3 5 7 9]
    after:  [0 1 2 3 4 5 6 7 8 9]

[ 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)に対し、[first2,last2)にあるすべての要素が[first1,last1)に含まれていればtrueを返します。

[ 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)に対し、[first1,last1)と[first2,last2)の和集合を[result,RET)に作ります。
RETはset_unionの戻り値です。

[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)に対し、[first1,last1)と[first2,last2)の積集合を[result,RET)に作ります。
RETはset_intersectionの戻り値です。

[ 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)に対し、[first1,last1)と[first2,last2)の差集合、すなわち[first1,last1)にあって[first2,last2)にない要素からなる集合を[result,RET)に作ります。
RETはset_differenceの戻り値です。

[ 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)に対し、[first1,last1)と[first2,last2)のいずれか一方にのみ存在する要素からなる集合を[result,RET)に作ります。
RETはset_symmetric_differenceの戻り値です。

[ push_heap, pop_heap, make_heap ]

- 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化します。

  // vectorをheapとして使う
  vector<int> v;
  int i;
  for ( i = 0; i < 10; ++i )
    v.push_back(i);
  cout << "initial: "; iter_print(v.begin(),v.end());
  make_heap(v.begin(),v.end());
  cout << "heap:    "; iter_print(v.begin(),v.end());
  v.push_back(5);
  push_heap(v.begin(),v.end());
  cout << "push 5:  "; iter_print(v.begin(),v.end());
  cout << "pop 3 times ..." << endl;
  vector<int>::iterator last = v.end();
  for ( i = 0; i < 3; ++i ) {
    pop_heap(v.begin(),last);
    cout << "         "; iter_print(v.begin(),--last,v.end());
  }

  実行結果:
    initial: [0 1 2 3 4 5 6 7 8 9]
    heap:    [9 8 6 7 4 5 2 0 3 1]
    push 5:  [9 8 6 7 5 5 2 0 3 1 4]
    pop 3 times ...
             [8 7 6 4 5 5 2 0 3 1|9]
             [7 5 6 4 1 5 2 0 3|8 9]
             [6 5 5 4 1 3 2 0|7 8 9]

[ sort_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)をソートします。

  // heapによる配列のソート
  int a[] = { 1, 6, 2, 3, 9, 7, 8, 0, 4, 5 };
  cout << "initial: "; iter_print(a, a+10);
  make_heap(a, a+10);
  cout << "heap:    "; iter_print(a, a+10);
  sort_heap(a, a+10);
  cout << "sorted:  "; iter_print(a, a+10);

  実行結果:
    initial: [1 6 2 3 9 7 8 0 4 5]
    heap:    [9 6 8 4 5 7 2 0 3 1]
    sorted:  [0 1 2 3 4 5 6 7 8 9]

[ min, max ]

- 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の大きい方を返します。

[ min_element, max_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)中の最小要素の位置を返します。

- 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 a[] = { 1, 6, 2, 3, 9, 7, 8, 0, 4, 5 };
  cout << "input: "; iter_print(a, a+10);
  int* p;
  p = min_element(a,a+10);
  cout << "min = " << *p << " at #" << distance(a,p) << endl;
  p = max_element(a,a+10);
  cout << "max = " << *p << " at #" << distance(a,p) << endl;

  実行結果:
    input: [1 6 2 3 9 7 8 0 4 5]
    min = 0 at #7
    max = 9 at #4

[ 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を返します。

[bnext_permutation,bprev_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)を並び替え、(辞書順に並べたときの)次の順列を作ります。
次の順列が作れない、すなわちシーケンス[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を返します。