ホーム | ブログ | C++辞典 | サイトマップ | FAQ | 掲示板 | リンク集
メイン・メニュー
インデックス
プログラミング
その他
Top / <algorithm>ヘッダ / 25.3整列及びその関連演算


整列及びその関連演算 (sorting and related operations)

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)²回の比較を行う。メモリが十分にある場合には 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, 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:  比較対象となる第 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
Counter: 5431, today: 1, yesterday: 1
Last-modified: Thu, 24 Nov 2005 13:53:01 JST (4443d)
 ホーム | プロフィール | メール | ログイン | 管理
Copyright © 2005-2009 by TAKAGI Nobuhisa