ホーム | ブログ | C++辞典 | サイトマップ | FAQ | 掲示板 | リンク集
メイン・メニュー
インデックス
プログラミング
その他
<algorithm>ヘッダ のバックアップ(No.10)


<algorithm>ヘッダ

ヘッダ内容

namespace std {

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

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

  template<class ForwardIterator1?, class ForwardIterator2?>
    ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                                                ForwardIterator2 first2, ForwardIterator2 last2);

  template<class ForwardIterator1?, class ForwardIterator2?, ckass BinaryPredicate?>
    ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                                                ForwardIterator2 first2, ForwardIterator2 last2,
                                                BinaryPredicate? pred);

  template<class ForwardIterator1?, class ForwardIterator2?>
    ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                                                      ForwardIterator2 first2, ForwardIterator2 last2);

  template<class ForwardIterator1?, class ForwardIterator2?, BinaryPredicate? pred>
    ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                                                      ForwardIterator2 first2, ForwardIterator2 last2,
                                                      BinaryPredicate? pred);

  template<class ForwardIterator?>
    ForwardIterator? adjacent_find(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class Predicate>
    ForwardIterator? adjacent_find(ForwardIterator? first, ForwardIterator? last,~                                                         Predicate pred);

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

  template<class InputIterator1?, class InputIterator2?>
    pair<InputIterator1, InputIterator2>
        mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

  template<class InputIterator1?, class InputIterator2?, class Predicate>
    pair<InputIterator1, InputIterator2>
        mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
                        Predicate pred);

  template<class InputIterator1?, class InputIterator2?>
    bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

  template<class InputIterator1?, class InputIterator2?, Predicate pred>
    bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
                      Predicate pred);

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

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

  template<class InputIterator?, class OutputIterator?>
    OutputIterator? copy(InputIterator? first, InputIterator? last, OutputIterator? result);

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

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

  template<class ForwardIterator1?, class ForwardIterator2?>
    ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                                                        ForwardIterator2 first2);

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

  template<class InputIterator?, class OutputIterator?, class UnaryOperator?>
    OutputIterator? transform(InputIterator? first, InputIterator? last,
                                                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);

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

  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 InputIterator?, class OutputIterator?, class Predicate, class T>
    OutputIterator? replace_copy_if(InputIterator? first, InputIterator? last,
                                                         OutputIterator? result,
                                                         Predicate pred, const T& new_value);

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

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

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

  template<class ForwardIterator?, class Size, class Generator>
    void generate_n(ForwardIterator? first, Size n, Generator gen);

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

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

  template<class ForwardIterator?>
    ForwardIterator? unique(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class BinaryPredicate?>
    ForwardIterator? unique(ForwardIterator? first, ForwardIterator? last,
                                            BinaryPredicate? pred);

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

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

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

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

  template<class RandomAccessIterator?>
    void random_shuffle(RandomAccessIterator? first, RandomAccessIterator? last);

  template<class RandomAccessIterator?, class RandomNumberGenerator?>
    void random_shuffle(RandomAccessIterator? first, RandomAccessIterator? last
                                      RandomNumberGenerator?& rand);

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

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

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

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

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

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

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

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

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

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? merge(InputIterator1 first1, InoputIterator1 last1,
                                          InputIterator2 first2, InputIterator2 last2,
                                          OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? merge(InputIterator1 first1, InoputIterator1 last1,
                                          InputIterator2 first2, InputIterator2 last2,
                                          OutputIterator? result, Compare comp);

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

  template<class InputIterator1?, class InputIterator2?>
    bool includes(InputIterator1 first1, InoputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2);

  template<class InputIterator1?, class InputIterator2?, class Compare>
    bool includes(InputIterator1 first1, InoputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2
                           Compare comp);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_union(InputIterator1 first1, InoputIterator1 last1,
                                               InputIterator2 first2, InputIterator2 last2
                                               OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_union(InputIterator1 first1, InoputIterator1 last1,
                                               InputIterator2 first2, InputIterator2 last2
                                               OutputIterator? result, Compare comp);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_intersection(InputIterator1 first1, InoputIterator1 last1,
                                                         InputIterator2 first2, InputIterator2 last2
                                                         OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_intersection(InputIterator1 first1, InoputIterator1 last1,
                                                         InputIterator2 first2, InputIterator2 last2
                                                         OutputIterator? result, Compare comp);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_difference(InputIterator1 first1, InoputIterator1 last1,
                                                       InputIterator2 first2, InputIterator2 last2
                                                       OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_difference(InputIterator1 first1, InoputIterator1 last1,
                                                       InputIterator2 first2, InputIterator2 last2
                                                       OutputIterator? result, Compare comp);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_symmetric_difference(InputIterator1 first1, InoputIterator1 last1,
                                                                          InputIterator2 first2, InputIterator2 last2
                                                                          OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_symmetric_difference(InputIterator1 first1, InoputIterator1 last1,
                                                                          InputIterator2 first2, InputIterator2 last2
                                                                          OutputIterator? result, 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);

  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 make_heap(RandomAccessIterator? first, RandomAccessIterator? last);

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

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

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

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

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

  template<class ForwardIterator?>
    ForwardIterator? min_element(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class Compare>
    ForwardIterator? min_element(ForwardIterator? first, ForwardIterator? last,
                                                       Comapre comp);

  template<class ForwardIterator?>
    ForwardIterator? max_element(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class Compare>
    ForwardIterator? max_element(ForwardIterator? first, ForwardIterator? last,
                                                       Comapre comp);

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

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

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

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

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

}

関数

for_each

各要素に対する処理

形式
  template<class InputIterator?, class Funtion>
    Function for_each(InputIterator? first, InputIterator? last, Function f);

引数
  first:  先頭要素を指す InputIterator?
  last:  終端要素の次を指す InputIterator?
  f:  各要素に適用する処理

返却値
 f を返す。

解説
 区間 [first, last-1) の各反復子 iter に対して、f(*iter) を実行する。f が何らかの返却値を返す場合には、その値は単に無視される。

計算量
 f がちょうど last - first 回適用される。

find

の探索

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

引数
  first:  先頭要素を指す InputIterator?
  last:  終端要素の次を指す InputIterator?
  value:  探索対象の。型 T は EqualityComparable?

返却値
 探査に成功すれば検出位置を指す反復子を、失敗した場合は last を返す。

解説
 区間 [first, last) の反復子 iter であり、かつ *iter == value となる最初の要素を探索する。

計算量
 *iter == value の評価を、多くとも last - first 回実行する。

参照
find_if

find_if

条件に一致する要素の探索

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

引数
  first:  先頭要素を指す InputIterator?
  last:  終端要素の次を指す InputIterator?
  pred:  探索条件となる述語?

返却値
 探査に成功すれば検出位置を指す反復子を、失敗した場合は last を返す。

解説
 区間 [first, last) の反復子 iter であり、かつ pred(iter) != false となる最初の要素を探索する。

計算量
 述語?の適応を、多くとも last - first 回実行する。

参照
find

find_end

最後の部分列の探索

形式
  template<class ForwardIterator1?, class ForwardIterator2?>
    ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                                                ForwardIterator2 first2, ForwardIterator2 last2);

  template<class ForwardIterator1?, class ForwardIterator2?, ckass BinaryPredicate?>
    ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                                                ForwardIterator2 first2, ForwardIterator2 last2,
                                                BinaryPredicate? pred);

引数
  first1:  探索対象となる列の先頭要素を指す ForwardIterator?
  last1:  探索対象となる列の終端要素の次を指す ForwardIterator?
  first2:  探索する部分列の先頭要素を指す ForwardIterator?
  last2:  探索する部分列の終端要素の次を指す ForwardIterator?
  pred:  述語?

返却値
 探索に成功した場合、見つけた部分列の先頭要素を指す反復子を返す。失敗した場合には last1 を返す。

解説
 区間 [first1, last1 - (last2 - first2)) で定義される列から区間 [first2, last2) で定義される最後の部分列を探索する。具体的には、区間 [first1, last1 - (last2 - first2)) にある反復子 iter および n < last2 - first2 である負でない n に対して、最初の形式では *(iter + n) == *(first2 + n) が、2 番目の形式では pred(*(iter + n), *(first2 + n)) != false が成立する最後の iter を見つけ出す。

計算量
 多くとも (last2 - first2)×(last1 - first1 - (last2 - first2) + 1) 回比較または述語が適用が行われる。

参照
serach

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?, BinaryPredicate? pred>
    ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                                                      ForwardIterator2 first2, ForwardIterator2 last2,
                                                      BinaryPredicate? pred);

引数
  first1:  探索対象となる列の先頭要素を指す ForwardIterator?
  last1:  探索対象となる列の終端要素の次を指す ForwardIterator?
  first2:  値集合の先頭要素を指す ForwardIterator?
  last2:  値集合の終端要素の次を指す ForwardIterator?
  pred:  述語?

返却値
 値集合のひとつに一致する要素が見つかった場合には、その要素を指す反復子を返す。それ以外の場合には last1 を返す。

解説
 区間 [first1, last1) で定義される列から、区間 [first2, last2) で定義される値集合のひとつに一致する要素を探索する。具体的には、区間 [first1, last1) にある反復子 iter1 および区間 [first2, last2) にある反復子 iter2 に対して、最初の形式では *iter1 == *iter2 が、2 番目の形式では pred(*iter1, *iter2) != false が成立する最初の iter1 を見つける。

計算量
 多くとも (last1 - first1)×(last2 - first2) 回比較または述語の適用が行われる。

adjacent_find

隣接する同値要素の探索

形式
  template<class ForwardIterator?>
    ForwardIterator? adjacent_find(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class Predicate>
    ForwardIterator? adjacent_find(ForwardIterator? first, ForwardIterator? last,~                                                         Predicate pred);

引数
  first:  探索対象となる列の先頭要素を指す ForwardIterator?
  last:  探索対象となる列の終端要素の次を指す ForwardIterator?
  pred:  述語?

返却値
 隣接する同値の要素が見つかった場合、その要素を指す反復子を、見つからなかった場合は last を返す。

解説
 区間 [first, last) にある反復子 iter および iter + 1 に対して、最初の形式では *iter == *(iter + 1) が、2 番目の形式では pred(*iter, *(iter + 1)) が成立する最初の iter を見つける。

計算量
 ちょうど find(find, last, value) - first 回比較または述語の適用が行われる。

count

要素の個数

形式
  template<class InputIterator?, class T>
    typename iterator_traits<InputIterator?>::difference_type
        count(InputIterator? first, InputIterator? last, const T& value);

引数
  first:  計数対象となる列の先頭要素を指す InputIterator?
  last:  計数対象となる列の終端要素の次を指す InputIterator?
  value:  計数の対象となる値。型 T は EqualityComparable?

返却値
 計数した個数を返す。

解説
 区間 [first, last) にある反復子 iter に対して、*iter == value が成立する反復子の個数を数える。

計算量
 ちょうど last - first 回比較が行われる。

参照
count_if

count_if

条件が成立する要素の個数

形式
  template<class InputIterator?, class Predicate>
    typename iterator_traits<InputIterator?>::difference_type
        count_if(InputIterator? first, InputIterator? last, Predicate pred);

引数
  first:  計数対象となる列の先頭要素を指す InputIterator?
  last:  計数対象となる列の終端要素の次を指す InputIterator?
  pred:  述語?

返却値
 計数した個数を返す。

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, value) != false が成立する反復子の個数を数える。

計算量
 ちょうど last - first 回述語が適用される。

参照
count

mismatch

不一致要素の探索

形式
  template<class InputIterator1?, class InputIterator2?>
    pair<InputIterator1, InputIterator2>
        mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

  template<class InputIterator1?, class InputIterator2?, class Predicate>
    pair<InputIterator1, InputIterator2>
        mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
                        Predicate pred);

引数
  first1:  比較対象となる一方の列の先頭要素を指す InputIterator?
  last1:  比較対象となる一方の列の終端要素の次を指す InputIterator?
  first2:  比較対象となる他方の列の先頭要素を指す InputIterator?
  pred:  述語?

返却値
 不一致要素が見つかった場合、不一致要素を指す反復子の対を返す。不一致要素が見つからなければ それぞれの列の終端要素の次を指す反復子が格納される。

解説
 区間 [first1, last1) で定義される列と区間 [first2, first2 + (last1 - first1)) の各要素を比較し、不一致要素を見つける。不一致要素が見つかった場合の返却値の .first は区間 [first1, last1) 側の、.second は区間 [first2, first2 + (last1 - first1)) 側の反復子が格納される。

計算量
 多くとも last1 - first1 回比較または述語の適用が行われる。

equal

列の等価判定

形式
  template<class InputIterator1?, class InputIterator2?>
    bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

  template<class InputIterator1?, class InputIterator2?, Predicate pred>
    bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2,
                      Predicate pred);

引数
  first1:  比較対象となる一方の列の先頭要素を指す InputIterator?
  last1:  比較対象となる一方の列の終端要素の次を指す InputIterator?
  first2:  比較対象となる他方の列の先頭要素を指す InputIterator?
  pred:  述語?

返却値
 比較対象の 2 つの列が等価の場合は true を、そうでなければ false を返す。

解説
 区間 [first1, last1) で定義される列と区間 [first2, first2 + (last1 - first1)) で定義される列の各要素を比較する。具体的には、区間 [first1, last1) にある反復子 iter に対して、最初の形式の場合は *iter == *(first2 + (iter - first1)) が、2 番目の形式の場合は pred(*iter, *(first2 + (iter - first1))) が成立する場合に 2 つの列が等価であると判定される。

計算量
 多くとも last1 - first1 回比較または述語の適用が行われる。

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:  探索対象となる列の先頭要素を指す ForwardIterator?
  last1:  探索対象となる列の終端要素の次を指す ForwardIterator?
  first2:  探索する部分列の先頭要素を指す ForwardIterator?
  last2:  探索する部分列の終端要素の次を指す ForwardIterator?
  pred:  述語?

返却値
 探索に成功した場合、見つけた部分列の先頭要素を指す反復子を返す。失敗した場合には last1 を返す。

解説
 区間 [first1, last1 - (last2 - first2)) で定義される列から区間 [first2, last2) で定義される部分列を探索する。具体的には、区間 [first1, last1 - (last2 - first2)) にある反復子 iter および n < last2 - first2 である負でない n に対して、最初の形式では *(iter + n) == *(first2 + n) が、2 番目の形式では pred(*(iter + n), *(first2 + n)) != false が成立する最初の iter を見つけ出す。

計算量
 多くとも (last1 - first1)×(last2 - first2) 回比較または述語が適用が行われる。

参照
serach_n, find_end

search_n

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

引数
  first:  探索対象となる列の先頭要素を指す ForwardIterator?
  last:  探索対象となる列の終端要素の次を指す ForwardIterator?
  count:  探索する部分列の要素数
  value:  探索する部分列の要素の値
  pred:  述語?

返却値
 探索に成功した場合、見つけた部分列の先頭要素を指す反復子を返す。失敗した場合には last1 を返す。

解説
 区間 [first, last - count) で定義される列から count 個の value からなる部分列を探索する。具体的には、区間 [first, last - count) にある反復子 iter および n < count である負でない n に対して、最初の形式では *(iter + n) == valueが、2 番目の形式では pred(*(iter + n), value) が成立する最初の iter を見つけ出す。

計算量
 多くとも (last - firstcount 回比較または述語が適用が行われる。

参照
serach

copy

列のコピー

形式
  template<class InputIterator?, class OutputIterator?>
    OutputIterator? copy(InputIterator? first, InputIterator? last, OutputIterator? result);

引数
  first:  コピー元である列の先頭要素を指す InputIterator?
  last:  コピー元である列の終端要素の次を指す InputIterator?
  result:  コピー先である列の先頭要素を指す OutputIterator?

返却値
 コピー先である列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) から区間 [result, result + (last - first)) へ、first から順に各要素をコピーする。result は区間 [first, last) にあってはならない。

計算量
 ちょうど last - first 回の代入を行う。

参照
copy_backward

copy_backward

列の逆方向コピー

形式
  template<class BidirectionalIterator1?, class BidirectionalIterator2?>
    BidirectionalIterator2 copy_backward
                                           (BidirectionalIterator? first, BidirectionalIterator? last,
                                            BidirectionalIterator? result);

引数
  first:  コピー元である列の先頭要素を指す BidirectionalIterator?
  last:  コピー元である列の終端要素の次を指す BidirectionalIterator?
  result:  コピー先である列の終端要素の次を指す BidirectionalIterator?

返却値
 コピー先である列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) から区間 [result - (last - first), result) へ、last - 1 から順に first まで各要素をコピーする。result は区間 [first, last) にあってはならない。

参考
last が区間 [result - (last - first), result) にある場合には、copy 関数より copy_backward 関数を使う方がよい。

計算量
 ちょうど last - first 回の代入を行う。

参照
copy_backward

swap

値の交換

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

引数
  a:  交換対象のオブジェクトへの参照
  b:  交換対象のオブジェクトへの参照

返却値
 なし

解説
 2 つの実引数? a および b に格納されている値を交換する。

参照
swap_ranges, iter_swap

swap_ranges

列の各要素の値交換

形式
  template<class ForwardIterator1?, class ForwardIterator2?>
    ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
                                                        ForwardIterator2 first2);

引数
  first1:  対象となる一方の列の先頭要素を指す ForwardIterator?
  last1:  対象となる一方の列の終端要素の次を指す ForwardIterator?
  first2:  対象となる他方の列の先頭要素を指す ForwardIterator?

返却値
 (first2 + (last1 - first1)) を返す。

解説
 区間 [first1, last1) で定義される列および区間 [first2, first2 + (last1 - first1)) で定義される列のそれぞれの要素の値を交換する。具体的には、n < (last1 - first) である負でない整数値 n に対して、swap(*(first1 + n), *(first2 + n)) を実行する。交換対象となる 2 つのの区間は重なっていてはならない。

計算量
 ちょうど last1 - first1 回の交換が行われる。

参照
swap, iter_swap

iter_swap

反復子が指す値の交換

形式
  template<class ForwardIterator1?, class ForwardIterator2?>
    void iter_swap(ForwardIterator1 a, ForwardIterator1 b);

引数
  a:  交換対象の反復子   b:  交換対象の反復子

返却値
 なし

解説
 2 つの反復子 a および b が指す値を交換する。

参照
swap

transform

各要素の変換

形式
  template<class InputIterator?, class OutputIterator?, class UnaryOperator?>
    OutputIterator? transform(InputIterator? first, InputIterator? last,
                                                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);

引数
  first:  対象列の先頭要素を指す InputIterator?
  last:  対象列の終端要素の次を指す InputIterator?
  first1:  二項変換で用いる第 1 項用の列の先頭要素を指す InputIterator?
  last1:  二項変換で用いる第 1 項用の列の終端要素の次を指す InputIterator?
  first2:  二項変換で用いる第 2 項用の列の先頭要素を指す InputIterator?
  result:  出力先の列の先頭要素を指す OutputIterator?
  op:  単項変換用の述語?
  binary_op:  二項変換用の述語?

返却値
 結果列の終端要素の次を指す反復子を返す。

解説
 最初の形式では、区間 [first, last) にある反復子 iter に対して、op(*iter) を適用した結果を、result から始まる列に出力する。resultfirst と同じであっても構わない。
 2 番目の形式では、区間 [first1, last1) にある反復子 iter1 および区間 [first2, first2 + (last1 - first1)) にある反復子 iter2 に対して、binary_op(*iter1, *iter2) を適用した結果を、result から始まる列に出力する。resultfirst1 または first2 と同じであっても構わない。

計算量
 ちょうど last - first または last1 - first1 回述語が適用される。

replace

要素の置換

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  old_value:  置換対象の値。型 T は Assignable かつ EqualityComparable?
  new_value:  置換後の値。型 T は Assignable かつ EqualityComparable?

返却値]
 なし

解説
 区間 [first, last) にある反復子 iter に対して、*iter == old_value が成立する各要素に対して、new_value を代入する。

計算量
 ちょうど last - first 回比較が行われる。

参照
replace_if, replace_copy, replace_copy_if

replace_if

条件が成立する要素の置換

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  pred:  述語?
  new_value:  置換後の値。型 T は Assignable

返却値]
 なし

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, old_value) != false が成立する各要素に対して、new_value を代入する。

計算量
 ちょうど last - first 回述語が適用される。

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:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  result:  出力先となる列の先頭要素を指す OutputIterator?
  old_value:  置換対象の値。型 T は Assignable かつ EqualityComparable?
  new_value:  置換後の値。型 T は Assignable かつ EqualityComparable?

返却値]
 結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にある反復子 iter に対して、*iter == old_value が成立する場合は new_value を、それ以外は *iterresult から始まる列にコピーする。元の列と出力先の列は重なっていてはならない。

計算量
 ちょうど last - first 回比較が行われる。

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:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  result:  出力先となる列の先頭要素を指す OutputIterator?
  pred:  述語?
  new_value:  置換後の値。型 T は Assignable

返却値]
 結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, old_value) != false が成立する場合は new_value を、それ以外は *iterresult から始まる列にコピーする。元の列と出力先の列は重なっていてはならない。

計算量
 ちょうど last - first 回述語が適用される。

fill

列を指定値で埋める

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  value:  列を埋める値

返却値
 なし

解説
 区間 [first, last) にあるすべての反復子を通して、各要素に value代入?する。

計算量
 ちょうど last - first 回代入が行われる。

fill_n

n 要素の列を指定値で埋める

形式
  template<class ForwardIterator?, class Size, class T>
    void fill_n(ForwardIterator? first, Size n, const T& value);

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  n:  対象となる列の要素数
  value:  列を埋める値

返却値
 なし

解説
 区間 [first, first + n) にあるすべての反復子を通して、各要素に value代入?する。

計算量
 ちょうど n 回代入が行われる。

generate

列の生成

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

引数
  first:  生成対象となる列の先頭要素を指す ForwardIterator?
  last:  生成対象となる列の終端要素の次を指す ForwardIterator?
  gen:  生成関数

返却値
 なし

解説
 区間 [first, last) にあるすべての反復子を通して、gen返却値代入?する。gen実引数?を取らない。

計算量
 ちょうど last - firstgen が呼び出される。

参照
generate_n

generate_n

n 要素の列を生成

形式
  template<class ForwardIterator?, class Size, class Generator>
    void generate_n(ForwardIterator? first, Size n, Generator gen);

引数
  first:  生成対象となる列の先頭要素を指す ForwardIterator?
  n:  生成対象となる列の要素数
  gen:  生成関数

返却値
 なし

解説
 区間 [first, first + n) にあるすべての反復子を通して、gen返却値代入?する。gen実引数?を取らない。また、型 Size は汎整数型?に変換できなければならない。

計算量
 ちょうど ngen が呼び出される。

参照
generate

remove

要素の削除

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  value:  削除対象。型 T は EualityComparable?

返却値  結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にある反復子 iter に対して、*iter == value が成立する要素を削除する。削除されない要素の相対順序は、元の相対順序が保存される。

計算量
 ちょうど last - first 回比較が行われる。

参照
remove_if, remove_copy, remove_copy_if

remove_if

条件が成立する要素の削除

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  pred:  述語?

返却値  結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, value) != false が成立する要素を削除する。削除されない要素の相対順序は、元の相対順序が保存される。

計算量
 ちょうど last - first 回述語が適用される。

参照
remove, remove_copy, remove_copy_if

remove_copy

指定要素を除くコピー

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  result:  出力先の先頭要素を指す OutputIterator?
  value:  削除対象。型 T は EualityComparable?

返却値  結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にある反復子 iter に対して、*iter == value が成立する要素を除き、result から始まる列にコピーする。削除されない要素の相対順序は、元の相対順序が保存される。元の列と出力先の列は重複していてはならない。

計算量
 ちょうど last - first 回比較が行われる。

remove_copy_if

条件が成立する要素を除くコピー

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  result:  出力先の先頭要素を指す OutputIterator?
  pred:  述語?

返却値  結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にある反復子 iter に対して、pred(*iter, value) != false が成立する要素を除き、result から始まる列にコピーする。削除されない要素の相対順序は、元の相対順序が保存される。元の列と出力先の列は重複していてはならない。

計算量
 ちょうど last - first 回述語が適用される。

unique

連続した重複要素の除去

形式
  template<class ForwardIterator?>
    ForwardIterator? unique(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class BinaryPredicate?>
    ForwardIterator? unique(ForwardIterator? first, ForwardIterator? last,
                                            BinaryPredicate? pred);

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  pred:  述語?

返却値
 結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にあるすべての重複要素を取り除く。すなわち、区間内の (先頭位置を除く) 反復子 iter に対して、最初の形式では *iter == *(iter - 1) を、2 番目の形式では pred(*iter, *(iter - 1)) == false が成立する最長の部分から、その先頭要素を残して他の要素が除去される。

計算量
 列が空でなければ、ちょうど (last - first) - 1 回比較または述語? が適用される。そうでなければ、比較または述語は 1 回も適用されることはない。

参照
unique_copy

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

引数
  first:  対象となる列の先頭要素を指す ForwardIterator?
  last:  対象となる列の終端要素の次を指す ForwardIterator?
  result:  出力先の先頭要素を指す OutputIterator?
  pred:  述語?

返却値
 結果列の終端要素の次を指す反復子を返す。

解説
 区間 [first, last) にあるすべての重複要素を除いて、result から始まる列にコピーする。すなわち、区間内の (先頭位置を除く) 反復子 iter に対して、最初の形式では *iter == *(iter - 1) を、2 番目の形式では pred(*iter, *(iter - 1)) == false が成立する最長の部分から、その先頭要素のみがコピーされる。

計算量
 ちょうど (last - first) - 1 回比較または述語? が適用される。

参照
unique

reverse

列の逆順再配置

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

引数
  first:  再配置対象となる列の先頭要素を指す BidirectionalIterator?
  last:  再配置対象となる列の終端要素の次を指す BidirectionalIterator?

返却値
 なし

解説
 区間 [iter, last) で定義される列を iter_swap により逆順に再配置する。

計算量
 多くとも last - first 回の交換を行う。

参照
reverse_copy

reverse_copy

列の逆順コピー

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

引数
  first:  対象となる列の先頭要素を指す BidirectionalIterator?
  last:  対象となる列の終端要素の次を指す BidirectionalIterator?
  result:  出力先となる列の先頭要素を指す OutputIterator?

返却値
 なし

解説
 区間 [iter, last) で定義される列を、result から始まる列に、逆順にコピーする。元の列と出力先の列が重なっていてはならない。

計算量
 ちょうど last - first 回の代入が行われる。

参照
reverse

rotate

列の回転

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

引数
  first:  回転対象となる列の先頭要素を指す ForwardIterator?
  middle:  回転後に先頭に移動する要素を指す ForwardIterator?
  last:  回転対象となる列の終端要素の次を指す ForwardIterator?

返却値
 なし

解説
 区間 [first, last) を、middle が指す要素が先頭になるように回転しする。区間 [first, middle) および区間 [middle, last) は正しい列でなければならない。

計算量
 多くとも last - first 回の交換が行われる。

参照
rotate_copy

rotate_copy

列の回転とコピー

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

引数
  first:  回転対象となる列の先頭要素を指す ForwardIterator?
  middle:  回転後に先頭に移動する要素を指す ForwardIterator?
  last:  回転対象となる列の終端要素の次を指す ForwardIterator?
  result:  出力先となる列の先頭要素を指す OutputIterator?

返却値
 結果列の終端位置の次を指す反復子を返す。

解説
 区間 [first, last) を、middle が指す要素が先頭になるように回転し、その結果を result から始まる列に格納する。区間 [first, middle) および区間 [middle, last) は正しい列でなければならない。また、元の列と出力先の列が重なっていてはならない。

計算量
 ちょうど last - first 回の代入が行われる。

参照
rotate

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:  シャッフル対象となる列の先頭要素を指す RandomAccessIterator?
  last:  シャッフル対象となる列の終端要素の次を指す RandomAccessIterator?
  rand:  乱数生成関数オブジェクト?

返却値
 なし

解説
 区間 [first, last) で定義される列を一様にシャッフルする。乱数生成関数オブジェクト? rand は任意のものを指定してもよいが、[[iterator_traits>#<iterator>ヘッダ#iterator_traits]]<RandomAccessIterator?>:: difference_type 型の正の実引数? n に対して、rand(n) は、iterator_traits<RandomAccessIterator?>:: difference_type 型に変換可能な型を持ち、かつ値域 [0, n) の中からランダムに抽出された値を返さなければならない。

計算量
 ちょうど (last - first) - 1 回の交換が行われる。

参照
rand, srand

partition

列の分割

形式
  template<class BidirectionalIterator?, class Predicate>
    BidirectionalIterator? partition(BidirectionalIterator? first, BidirectionalIterator? last,
                                                      Predicate pred);

引数
  first:  分割対象となる列の先頭要素を指す BidirectionalIterator?
  last:  分割対象となる列の終端要素の次を指す BidirectionalIterator?
  pred:  述語?

返却値
 分割位置を指す反復子を返す。

解説
 区間 [first, last) で定義される列を、述語? pred が成立する要素を前に、成立しない要素を後ろに再配置する。

計算量
 多くとも (last - first) / 2 回の交換が行われる。メモリが十分にある場合には線形になる可能性がある。また、last - first 回だけ述語 pred が適用される。

参照
stable_partition

stable_partition

列の安定な分割

形式
  template<class BidirectionalIterator?, class Predicate>
    BidirectionalIterator? stable_partition(BidirectionalIterator? first,
                                                                  BidirectionalIterator? last, Predicate pred);

引数
  first:  分割対象となる列の先頭要素を指す BidirectionalIterator?
  last:  分割対象となる列の終端要素の次を指す BidirectionalIterator?
  pred:  述語?

返却値
 分割位置を指す反復子を返す。

解説
 区間 [first, last) で定義される列を、述語? pred が成立する要素を前に、成立しない要素を後ろに再配置する。同値の要素の順序は、再配置後も保存される。

計算量
 多くとも (last - first)×log(last - first) 回の交換が行われる。メモリが十分にある場合には線形になる可能性がある。また、last - first 回だけ述語 pred が適用される。

参照
partition

sort

整列

形式
  template<class RandomAccessIterator?>
    void sort(RandomAccessIterator? first, RandomAccessIterator? last);

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

引数
  first:  整列対象となる列の先頭要素を指す RandomAccessIterator?
  last:  整列対象となる列の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 区間 [first, last) で定義される列を整列する。

計算量
 平均的に N log N 回の比較が行われる。ただし、Nlast - first である。

参照
stable_sort

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

引数
  first:  整列対象となる列の先頭要素を指す RandomAccessIterator?
  last:  整列対象となる列の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 区間 [first, last) で定義される列を整列する。同値の要素の順序は整列後も保存される。

計算量
 多くとも N (log N) 2 回の比較を行う。メモリが十分にある場合には N log N 回の比較が行われる。ただし、Nlast - first である。

参照
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:  整列対象となる列の先頭要素を指す RandomAccessIterator?
  middle:  整列結果となる列の終端要素の次を指す RandomAccessIterator?
  last:  整列対象となる列の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 区間 [first, last) を整列した場合の最初の middle - first 個の要素を、区間 [first, middle) に格納する。実行後の区間 [middle, last) の内容は未規定である。

計算量
 ほぼ (last - first)×log(middle - first) 回の比較を行う。

参照
partial_sort_copy

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:  元の列の先頭要素を指す InputIterator?
  last:  元の列の終端要素の次を指す InputIterator?
  result_first:  出力先となる列の先頭要素を指す RandomAccessIterator?
  result_last:  出力先となる列の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 結果の列の終端要素の次を指す反復子を返す。

解説
 first から始まる、区間 [first, last) または区間 [result_first, result_last) のうちの小さい方の要素数を整列して、result_first から始まる列に出力する。

計算量
 ほぼ (last - first)×log( min( (last - first), (result_last - result_first) ) ) 回の比較が行われる。

参照
partial_sort

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:  分割対象となる列の先頭要素を指す RandomAccessIterator?
  nth:  分割の基準位置を指す RandomAccessIterator?
  last:  分割対象となる列の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 区間 [first, nth) にある任意の反復子 iter1 が、区間 [nth, last) にある任意の反復子 iter2 に対して、最初の形式では !(*iter1 > *iter2) が、2 番目の形式では comp(*iter2, *iter1) == false が成立するように再配置する。nth の位置には、列全体を整列したときにその位置に来る要素が格納される。

計算量
 平均で線形である。

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:  探索対象となる列の先頭要素を指す ForwardIterator?
  last:  探索対象となる列の終端要素の次を指す ForwardIterator?
  value:  探索する値。型 T は LessThanComparable?
  comp:  比較関数

返却値
 順を乱さずに value を挿入できる最初の位置 (下限) を指す反復子を返す。

解説
 区間 [first, last) にある任意の反復子 iter の位置に、順序を乱さずに要素 value を挿入することができる最初の位置を探索する。順序を乱さずに挿入ができるとは、最初の形式では !(*iter < value) && !(value < *iter) が、2 番目の形式では !comp(*iter, value) && !comp(value, *iter) が成立することを意味する。

計算量
 多くとも log(last - first) + 1 回の比較が行われる。

参照
upper_bound, equal_range

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:  探索対象となる列の先頭要素を指す ForwardIterator?
  last:  探索対象となる列の終端要素の次を指す ForwardIterator?
  value:  探索する値。型 T は LessThanComparable?
  comp:  比較関数

返却値
 順を乱さずに value を挿入できる最後の位置 (上限) を指す反復子を返す。

解説
 区間 [first, last) にある任意の反復子 iter の位置に、順序を乱さずに要素 value を挿入することができる最後の位置を探索する。順序を乱さずに挿入ができるとは、最初の形式では !(*iter < value) && !(value < *iter) が、2 番目の形式では !comp(*iter, value) && !comp(value, *iter) が成立することを意味する。

計算量
 多くとも log(last - first) + 1 回の比較が行われる。

参照
lower_bound, equal_range

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:  探索対象となる列の先頭要素を指す ForwardIterator?
  last:  探索対象となる列の終端要素の次を指す ForwardIterator?
  value:  探索する値。型 T は LessThanComparable?
  comp:  比較関数

返却値
 返却値のメンバ .first には value を順を乱さずに要素を挿入できる最初の位置 (下限) を、.second には最後の位置 (上限) が格納される。対応する範囲が見つからなかった場合は .first および .second には last が格納される。

解説
 区間 [first, last) にある任意の反復子 iter の位置に、順序を乱さずに要素 value を挿入することができる最大の範囲を返す。順序を乱さずに挿入ができるとは、最初の形式では !(*iter < value) && !(value < *iter) が、2 番目の形式では !comp(*iter, value) && !comp(value, *iter) が成立することを意味する。

計算量
 多くとも 2×log(last - first) + 1 回の比較が行われる。

参照
lower_bound, upper_bound

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:  探索対象となる列の先頭要素を指す ForwardIterator?
  last:  探索対象となる列の終端要素の次を指す ForwardIterator?
  value:  探索する値。型 T は LessThanComparable?
  comp:  比較関数

返却値
 探索に成功すれば true を、失敗すれば false を返す。

解説
 区間 [first, last) にある反復子 iter に対して、最初の形式では !(*iter < value) && !(value < *iter) が、2 番目の形式では comp(*iter, value) == false && comp(value, *iter) == false が成立する要素を探索する。

計算量
 多くとも log(last - first) + 2 回の比較が行われる。

参照
bsearch

merge

併合

形式
  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? merge(InputIterator1 first1, InoputIterator1 last1,
                                          InputIterator2 first2, InputIterator2 last2,
                                          OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? merge(InputIterator1 first1, InoputIterator1 last1,
                                          InputIterator2 first2, InputIterator2 last2,
                                          OutputIterator? result, Compare comp);

引数'
  first1:  第 1 区間の先頭要素を指す InputIterator?
  last1:  第 1 区間の終端要素の次を指す InputIterator?
  first2:  第 2 区間の先頭要素を指す InputIterator?
  last2:  第 2 区間の終端要素の次を指す InputIterator?
  result:  結果集合の出力先の先頭要素を指す OutputIterator?
  comp:  比較関数

返却値'
 結果集合の終端要素の次を指す反復子を返す。

解説
 2 つの整列された区間を併合する。構築された集合は昇順に整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。両方の区間に存在する同じ値の要素は、第 1 区間にあったものが第 2 区間にあったものより前に格納される。

計算量
 多くとも (last1 - first1) + (last2 - first2) - 1 回の比較が行われる。

参照
inplace_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);

引数
  first:  第 1 区間の先頭要素を指す BidirectionalIterator?
  middle:  第 1 区間の終端要素の次であり、かつ第 2 区間の先頭要素を指す BidirectionalIterator?
  last:  第 2 区間の終端要素の次を指す BidirectionalIterator?
  comp:  比較関数

返却値
 なし

解説
 2 つの連続している整列された区間 [first, middle) および [middle, last) を併合し、結果を [first, last) に格納する。結果の区間は昇順に整列される。両方の区間に存在する同じ値の要素は、第 1 区間にあったものが第 2 区間にあったものより前に格納される。

計算量
 メモリが十分にある場合には (last - first) - 1 回の比較が行われる。メモリが十分でない場合には N log N 回の比較を行う。ただし、Nlast - first である。

参照
merge

includes

部分集合の判別

形式
  template<class InputIterator1?, class InputIterator2?>
    bool includes(InputIterator1 first1, InoputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2);

  template<class InputIterator1?, class InputIterator2?, class Compare>
    bool includes(InputIterator1 first1, InoputIterator1 last1,
                           InputIterator2 first2, InputIterator2 last2
                           Compare comp);

引数'
  first1:  比較対象となる第 1 集合の先頭要素を指す InputIterator?
  last1:  比較対象となる第 1 集合の終端要素の次を指す InputIterator?
  first2:  比較対象となる第 2 集合の先頭要素を指す InputIterator?
  last2:  比較対象となる第 2 集合の終端要素の次を指す InputIterator?
  result:  結果集合の出力先の先頭要素を指す OutputIterator?
  comp:  比較関数

返却値'
 第 2 集合が第 1 集合の部分集合であれば true を、そうでなければ false を返す。

解説
 区間 [first2, last2) で定義される集合のすべての要素が区間 [first1, last1) で定義される集合に含まれるかどうかを判別する。

計算量
 多くとも 2×( (last1 - first1) + (last2 - first2) ) - 1 回の比較が行われる。

set_union

集合の和

形式
  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_union(InputIterator1 first1, InoputIterator1 last1,
                                               InputIterator2 first2, InputIterator2 last2
                                               OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_union(InputIterator1 first1, InoputIterator1 last1,
                                               InputIterator2 first2, InputIterator2 last2
                                               OutputIterator? result, Compare comp);

引数'
  first1:  比較対象となる第 1 集合の先頭要素を指す InputIterator?
  last1:  比較対象となる第 1 集合の終端要素の次を指す InputIterator?
  first2:  比較対象となる第 2 集合の先頭要素を指す InputIterator?
  last2:  比較対象となる第 2 集合の終端要素の次を指す InputIterator?
  result:  結果集合の出力先の先頭要素を指す OutputIterator?
  comp:  比較関数

返却値'
 結果集合の終端要素の次を指す反復子を返す。

解説
 2 つの区間の和集合、すなわち、区間 [first1, last1) で定義される第 1 集合および区間 [first2, last2) で定義される第 2 集合のいずれかに存在する要素の集合を構築する。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

計算量
 多くとも 2×( (last1 - first1) + (last2 - first2) ) - 1 回の比較が行われる。

参照
set_intersection

set_intersection

集合の積

形式
  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_intersection(InputIterator1 first1, InoputIterator1 last1,
                                                         InputIterator2 first2, InputIterator2 last2
                                                         OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_intersection(InputIterator1 first1, InoputIterator1 last1,
                                                         InputIterator2 first2, InputIterator2 last2
                                                         OutputIterator? result, Compare comp);

引数'
  first1:  比較対象となる第 1 集合の先頭要素を指す InputIterator?
  last1:  比較対象となる第 1 集合の終端要素の次を指す InputIterator?
  first2:  比較対象となる第 2 集合の先頭要素を指す InputIterator?
  last2:  比較対象となる第 2 集合の終端要素の次を指す InputIterator?
  result:  結果集合の出力先の先頭要素を指す OutputIterator?
  comp:  比較関数

返却値'
 結果集合の終端要素の次を指す反復子を返す。

解説
 2 つの区間の積集合、すなわち、区間 [first1, last1) で定義される第 1 集合および区間 [first2, last2) で定義される第 2 集合の両方に存在する要素の集合を構築する。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

計算量
 多くとも 2×( (last1 - first1) + (last2 - first2) ) - 1 回の比較が行われる。

参照
set_union

set_difference

集合の差

形式
  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_difference(InputIterator1 first1, InoputIterator1 last1,
                                                       InputIterator2 first2, InputIterator2 last2
                                                       OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_difference(InputIterator1 first1, InoputIterator1 last1,
                                                       InputIterator2 first2, InputIterator2 last2
                                                       OutputIterator? result, Compare comp);

引数'
  first1:  比較対象となる第 1 集合の先頭要素を指す InputIterator?
  last1:  比較対象となる第 1 集合の終端要素の次を指す InputIterator?
  first2:  比較対象となる第 2 集合の先頭要素を指す InputIterator?
  last2:  比較対象となる第 2 集合の終端要素の次を指す InputIterator?
  result:  結果集合の出力先の先頭要素を指す OutputIterator?
  comp:  比較関数

返却値'
 結果集合の終端要素の次を指す反復子を返す。

解説
 区間 [first1, last1) で定義される第 1 集合に存在し、区間 [first2, last2) で定義される第 2 集合には存在しない要素を、result から始まる区間にコピーする。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

計算量
 多くとも 2×( (last1 - first1) + (last2 - first2) ) - 1 回の比較が行われる。

参照
set_symmetric_difference

set_symmetric_difference

集合の対称差

形式
  template<class InputIterator1?, class InputIterator2?, class OutputIterator?>
    OutputIterator? set_symmetric_difference(InputIterator1 first1, InoputIterator1 last1,
                                                                          InputIterator2 first2, InputIterator2 last2
                                                                          OutputIterator? result);

  template<class InputIterator1?, class InputIterator2?, class OutputIterator?,
                  class Compare>
    OutputIterator? set_symmetric_difference(InputIterator1 first1, InoputIterator1 last1,
                                                                          InputIterator2 first2, InputIterator2 last2
                                                                          OutputIterator? result, Compare comp);

引数'
  first1:  比較対象となる第 1 集合の先頭要素を指す InputIterator?
  last1:  比較対象となる第 1 集合の終端要素の次を指す InputIterator?
  first2:  比較対象となる第 2 集合の先頭要素を指す InputIterator?
  last2:  比較対象となる第 2 集合の終端要素の次を指す InputIterator?
  result:  結果集合の出力先の先頭要素を指す OutputIterator?
  comp:  比較関数

返却値'
 結果集合の終端要素の次を指す反復子を返す。

解説
 区間 [first1, last1) で定義される第 1 集合および区間 [first2, last2) で定義される第 2 集合のいずれかにのみ存在しない要素を、result から始まる区間にコピーする。構築された集合は整列される。結果の区間は、元の集合の区間のいずれとも重なっていてはならない。

計算量
 多くとも 2×( (last1 - first1) + (last2 - first2) ) - 1 回の比較が行われる。

参照
set_difference

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

引数
  first:  ヒープ?の先頭要素を指す RandomAccessIterator?
  last:  ヒープ?の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 last - 1 の位置にある要素を移動し、区間 [first, last) をヒープ?にする。元の区間 [first, last) は正しいヒープでなければならない。

計算量
 多くとも log(last - first) 回の比較が行われる。

参照
pop_heap, make_heap, sort_heap

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

引数
  first:  ヒープ?の先頭要素を指す RandomAccessIterator?
  last:  ヒープ?の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 first の位置にある要素と last - 1 の位置にある要素を交換し、区間 [first, last - 1) をヒープ?にする。元の区間 [first, last) は正しいヒープでなければならない。

計算量
 多くとも 2×log(last - first) 回の比較が行われる。

参照
push_heap, make_heap, sort_heap

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

引数
  first:  ヒープ?の先頭要素を指す RandomAccessIterator?
  last:  ヒープ?の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 区間 [first, last) からヒープ?を構築する。

計算量
 多くとも 3×(last - first) 回の比較が行われる。

参照
push_heap, pop_heap, sort_heap

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

引数
  first:  ヒープ?の先頭要素を指す RandomAccessIterator?
  last:  ヒープ?の終端要素の次を指す RandomAccessIterator?
  comp:  比較関数

返却値
 なし

解説
 区間 [first, last) で定義されるヒープ?を整列する。整列は安定ではない。

計算量
 多くとも N log N 回の比較が行われる。ただし、Nlast - first である。

参照
push_heap, pop_heap, make_heap

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:  
  comp:  比較関数。型 T は LessThanComparable? かつ CopyConstructible?

返却値
 最小値を返す。

解説
 ab を比較し、小さい方を返す。最初の形式では比較に < 演算子?を、2 番目の形式では comp を使用する。ab が等しい場合は a を返す。

参照
max

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:  
  comp:  比較関数。型 T は LessThanComparable? かつ CopyConstructible?

返却値
 最大値を返す。

解説
 ab を比較し、大きい方を返す。最初の形式では比較に < 演算子?を、2 番目の形式では comp を使用する。ab が等しい場合は a を返す。

参照
min

min_element

最小要素の探索

形式
  template<class ForwardIterator?>
    ForwardIterator? min_element(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class Compare>
    ForwardIterator? min_element(ForwardIterator? first, ForwardIterator? last,
                                                       Comapre comp);

引数
  first:  探索対象の先頭要素を指す ForwardIterator?
  last:  探索対象の終端要素の次を指す ForwardIterator?
  comp:  比較関数

返却値
 最小要素を指す反復子を返す。first == last の場合は last を返す。 

解説
 区間 [first, last) 内の反復子 iter1 であり、任意の反復子 iter2 に対して、!(*iter2 < *iter1) または comp(*iter2, *iter1) == false が成立する最初の iter1 を探索する。

計算量
 ちょうど max( (last - first) - 1, 0) ) 回比較が行われる。

参照
max_element

max_element

最大要素の探索

形式
  template<class ForwardIterator?>
    ForwardIterator? max_element(ForwardIterator? first, ForwardIterator? last);

  template<class ForwardIterator?, class Compare>
    ForwardIterator? max_element(ForwardIterator? first, ForwardIterator? last,
                                                       Comapre comp);

引数
  first:  探索対象の先頭要素を指す ForwardIterator?
  last:  探索対象の終端要素の次を指す ForwardIterator?
  comp:  比較関数

返却値
 最大要素を指す反復子を返す。first == last の場合は last を返す。 

解説
 区間 [first, last) 内の反復子 iter1 であり、任意の反復子 iter2 に対して、!(*iter1 < *iter2) または comp(*iter1, *iter2) == false が成立する最初の iter1 を探索する。

計算量
 ちょうど max( (last - first) - 1, 0) ) 回比較が行われる。

参照
min_element

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:  比較対象となる一方の列の先頭要素を指す InputIterator?
  last1:  比較対象となる一方の列の終端要素の次を指す InputIterator?
  first2:  比較対象となる他方の列の先頭要素を指す InputIterator?
  last2:  比較対象となる他方の列の終端要素の次を指す InputIterator?
  comp:  比較関数

返却値
 区間 [first1, last1) の列が区間 [first2, last2) の列より小さい場合は true を、そうでなければ false を返す。 

解説
 区間 [first1, last1) で定義される列と区間 [first2, last2)で定義される列を辞書順で比較する。最初の形式では、比較には < 演算子?を使用し、2 番目の形式では comp を使用する。

計算量
 多くとも 2×min( (last1 - first1), (last2 - first2) ) 回の比較を行う。

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:  先頭要素を指す BidirectionalIterator?
  last:  終端要素の次を指す BidirectionalIterator?
  comp:  比較関数

返却値
 次の順列が存在する場合は true を、そうでなければ false を返す。

解説
 区間 [first, last) の列を前の順列に変換する。次の順列とは、< 演算子?または述語? comp によって辞書順に整列した場合に直前の位置に来る列である。次の順列が存在しない場合、昇順に整列した列に変換する。

計算量
 多くとも (last - first) / 2 の交換が行われる。

参照
prev_permutation

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

引数
  first:  先頭要素を指す BidirectionalIterator?
  last:  終端要素の次を指す BidirectionalIterator?
  comp:  比較関数

返却値
 前の順列が存在する場合は true を、そうでなければ false を返す。

解説
 区間 [first, last) の列を前の順列に変換する。前の順列とは、< 演算子?または述語? comp によって辞書順に整列した場合に直前の位置に来る列である。前の順列が存在しない場合には、降順に整列した列に変換する。

計算量
 多くとも (last - first) / 2 の交換が行われる。

参照
next_permutation


トップ   一覧 単語検索   ヘルプ   最終更新のRSS
 ホーム | プロフィール | メール | ログイン | 管理
Copyright © 2005-2009 by TAKAGI Nobuhisa