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: 反转范围（函数模板）