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

Sort elements preserving order of equivalents

Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.

元素使用第一個版本的 operator< 進行比較，第二個版本使用 comp 進行比較。

引數

first, last: Random-access iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
RandomAccessIterator shall point to a type for which swap is properly defined and which is both move-constructible and move-assignable.
comp: Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.
該函式不得修改其任何引數。
This can either be a function pointer or a function object.

返回值

無

示例

// stable_sort example
#include <iostream>     // std::cout
#include <algorithm>    // std::stable_sort
#include <vector>       // std::vector

bool compare_as_ints (double i,double j)
{
  return (int(i)<int(j));
}

int main () {
  double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};

  std::vector<double> myvector;

  myvector.assign(mydoubles,mydoubles+8);

  std::cout << "using default comparison:";
  std::stable_sort (myvector.begin(), myvector.end());
  for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  myvector.assign(mydoubles,mydoubles+8);

  std::cout << "using 'compare_as_ints' :";
  std::stable_sort (myvector.begin(), myvector.end(), compare_as_ints);
  for (std::vector<double>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

compare_as_ints is a function that compares only the integral part of the elements, therefore, elements with the same integral part are considered equivalent. stable_sort preserves the relative order these had before the call.

可能的輸出

using default comparison: 1.32 1.41 1.62 1.73 2.58 2.72 3.14 4.67
using 'compare_as_ints' : 1.41 1.73 1.32 1.62 2.72 2.58 3.14 4.67

複雜度

If enough extra memory is available, linearithmic in the distance between first and last: Performs up to N*log₂(N) element comparisons (where N is this distance), and up to that many element moves.
Otherwise, polyloglinear in that distance: Performs up to N*log₂²(N) element comparisons, and up to that many element swaps.

資料競爭

範圍[first,last)內的物件將被修改。

異常

如果任何元素比較、元素交換（或移動）或迭代器操作丟擲異常，則會丟擲異常。
請注意，無效引數會導致未定義行為。

另見

sort: 對範圍中的元素進行排序（函式模板）

partial_sort: 對範圍中的元素進行部分排序（函式模板）

search: 在範圍中搜索子序列（函式模板）

reverse: 反轉範圍（函式模板）