std::
stable_sort
函数模板 <algorithm> 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,last)范围内的元素按升序排序。 与sort类似，但stable_sort保留了具有相等值的元素的相对顺序。
第一个版本使用operator<比较元素，第二个版本使用comp比较元素。
☲ 参数
- first, last
- 指向一个要排序的序列初始和最终位置的随机访问迭代器。使用的范围是[first,last)， 它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。 随机访问迭代器(RandomAccessIterator)应该指向一个正确定义了swap的类型， 并且该类型既可以移动构造，也可以移动赋值。
- comp
-
二元函数，接受范围内的两个元素作为参数，并返回可转换为bool的值。
返回的值表明，作为第一个参数传递的元素是否按照其定义的严格弱顺序先于第二个参数。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
none
☣ 示例
// 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_int是一个只比较元素的整型部分的函数，
因此具有相同整型部分的元素被认为是等效的。Stable_sort保留了调用之前的相对顺序。
可能输出:
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
可能输出:
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
✥ 复杂度
如果有足够的额外内存可用，则对first and last之间的距离进行线性运算: 执行最多N*log2(N)个元素比较(其中N是这个距离)，并移动最多N个元素。
否则，在该距离内线性的多重对数函数: 执行最多N*log22(N)个元素的比较和最多N个元素的交换。
⇄ 数据竞争
范围[first,last)中的对象将被修改。
☂ 异常安全性
如果任何元素比较、元素交换(或移动)或迭代器上的操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| sort | 对范围内的元素进行排序(函数模板) |
| partial_sort | 对范围内的元素进行部分排序(函数模板) |
| search | 搜索范围的子序列(函数模板) |
| reverse | 反转元素(函数模板) |