整列及びその関連演算 (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 回の比較が行われる。ただし、N は last - 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 回の比較が行われる。ただし、N は last - 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 回の比較を行う。ただし、N は last - 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 †
集合の対称差
形式
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 回の比較が行われる。ただし、N は last - 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?
返却値
最小値を返す。
解説
a と b を比較し、小さい方を返す。最初の形式では比較に < 演算子?を、2 番目の形式では comp を使用する。a と b が等しい場合は 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?
返却値
最大値を返す。
解説
a と b を比較し、大きい方を返す。最初の形式では比較に < 演算子?を、2 番目の形式では comp を使用する。a と b が等しい場合は 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
Last-modified: Thu, 24 Nov 2005 13:53:01 JST (5446d)