並べ替え

並べ替え

sort/stable_sort

void sort(RandIterator first, RandIterator last)
void sort(RandIterator first, RandIterator last, BinPred comp)
void stable_sort(RandIterator first, RandIterator last)
void stable_sort(RandIterator first, RandIterator last, BinPred comp)

  • [first, last)の区間を昇順でソートする
  • operator< を用いる
  • compは二項述語
  • Random Access Iteratorを必要とするため,listには適用できない
 (listではメンバ関数sort()を用いる)
  • stable_sortは,等価な要素に対しての順序性を保存する

partial_sort

void partial_sort(RandIterator first, RandIterator middle, RandIterator last)
void partial_sort(RandIterator first, RandIterator middle, RandIterator last, BinPred comp)

  • [first, last) の要素の中から,middle - first 個の最小要素を昇順でソートし,[first, middle)へ詰める
  • 残りの要素は [middle, last) に不定の順序で格納される

nth_element

void nth_element(RandIterator first, RandIterator nth, RandIterator last)
void nth_element(RandIterator first, RandIterator nth, RandIterator last, BinPred comp)

  • [first, last)の要素の中から,nth-first 個の最小要素を[first, nth)へ詰める。ソートはされない。
  • 残りの要素は[nth, last) へ格納する
  • [first, nth)の要素 *i は *nth < *i とならない要素となる
  • [nth + 1, last) の要素 *j は *j < *nth とならない要素となる

partition/stable_partition

ForIterator partition(ForIterator first, ForIterator last, UnPred pred)
ForIterator stable_partition(ForIterator first, ForIterator last, UnPred pred)

  • 単項述語 pred が true となる要素を前に,falseとなる要素を後ろへ並べ替える
  • 戻り値 iterator middleに対して,[first, middle) の要素 *i は pred(*i) == true となり,
 [middle, last)の要素 *i は pred(*i) == false となる
  • stable_partitionは,並び順を保存する。true(またはfalse)になる要素同士の前後の順序は同じである。

  • 最終更新:2009-04-29 23:48:46

このWIKIを編集するにはパスワード入力が必要です

認証パスワード