命名空间
变体
操作

std::stable_sort

来自 cppreference.cn
< cpp‎ | 算法
 
 
算法库
有约束算法与针对范围的算法 (C++20)
有约束的算法,例如 ranges::copyranges::sort 等……
执行策略 (C++17)
排序及相关操作
划分操作
排序操作
二分搜索操作
(于已划分范围上)
集合操作(于已排序范围上)
归并操作(于已排序范围上)
堆操作
最小/最大值操作
(C++11)
(C++17)
字典序比较操作
排列操作
C 库
数值操作
未初始化内存上的操作
 
定义于头文件 <algorithm>
template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );
(1) (C++26 起为 constexpr)
template< class ExecutionPolicy, class RandomIt >

void stable_sort( ExecutionPolicy&& policy,

                  RandomIt first, RandomIt last );
(2) (C++17 起)
template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );
(3) (C++26 起为 constexpr)
template< class ExecutionPolicy, class RandomIt, class Compare >

void stable_sort( ExecutionPolicy&& policy,

                  RandomIt first, RandomIt last, Compare comp );
(4) (C++17 起)

以非降序对范围 [firstlast) 中的元素进行排序。保证保持等价元素的顺序。

1) 元素根据 operator<(C++20 前)std::less{}(C++20 起) 进行排序
3) 元素根据 comp 排序。
2,4)(1,3),但按 policy 执行。
仅当满足所有以下条件时,这些重载才参与重载决议

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>true

(C++20 前)

std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>true

(C++20 起)

如果满足以下任何条件,则行为是未定义的:

(C++11 前)
(C++11 起)

目录

[编辑] 参数

first, last - 定义待排序元素 范围 的迭代器对
policy - 要使用的 执行策略
comp - 比较函数对象(即满足 Compare 要求的对象),若第一个参数小于(即在第二个参数之前排序)第二个参数则返回 ​true

比较函数的签名应等效于以下内容

bool cmp(const Type1& a, const Type2& b);

尽管函数签名不需要含有 const&,但函数不可修改传递给它的对象,且必须能接受 Type1Type2 类型(可能带 const)的所有值,而无论其值类别(因此,不允许 Type1&,也不允许 Type1,除非对于 Type1 移动等价于复制(C++11 起))。
类型 Type1Type2 必须使得类型为 RandomIt 的对象能够被解引用,然后隐式转换为二者。​

类型要求
-
RandomIt 必须满足 LegacyRandomAccessIterator 的要求。
-
Compare 必须满足 Compare 的要求。

[编辑] 复杂度

给定 Nlast - first

1,2) 如果有足够的额外内存可用,使用 operator<(C++20 前)std::less{}(C++20 起) 进行 O(N·log(N)) 次比较,否则进行 O(N·log2
(N))
次比较。
3,4) 如果有足够的额外内存可用,对比较器 comp 进行 O(N·log(N)) 次应用,否则进行 O(N·log2
(N))
次应用。

[编辑] 异常

带有模板参数 ExecutionPolicy 的重载按如下方式报告错误

  • 若作为算法一部分调用的函数执行抛出异常,且 ExecutionPolicy标准策略之一,则调用 std::terminate。对于任何其他 ExecutionPolicy,行为是实现定义的。
  • 如果算法未能分配内存,则抛出 std::bad_alloc

[编辑] 可能的实现

另请参阅 libstdc++libc++ 中的实现。

[编辑] 注意

此函数尝试分配一个大小等于要排序序列的临时缓冲区。如果分配失败,则选择效率较低的算法。

特性测试 标准 特性
__cpp_lib_constexpr_algorithms 202306L (C++26) constexpr 稳定排序,重载 (1)(3)

[编辑] 示例

#include <algorithm>
#include <array>
#include <iostream>
#include <string>
#include <vector>
 
struct Employee
{
    int age;
    std::string name; // Does not participate in comparisons
};
 
bool operator<(const Employee& lhs, const Employee& rhs)
{
    return lhs.age < rhs.age;
}
 
#if __cpp_lib_constexpr_algorithms >= 202306L
consteval auto get_sorted()
{
    auto v = std::array{3, 1, 4, 1, 5, 9};
    std::stable_sort(v.begin(), v.end());
    return v;
}
static_assert(std::ranges::is_sorted(get_sorted()));
#endif
 
int main()
{
    std::vector<Employee> v{{108, "Zaphod"}, {32, "Arthur"}, {108, "Ford"}};
 
    std::stable_sort(v.begin(), v.end());
 
    for (const Employee& e : v)
        std::cout << e.age << ", " << e.name << '\n';
}

输出

32, Arthur
108, Zaphod
108, Ford

[编辑] 另请参阅

将一个范围按升序排序
(函数模板) [编辑]
对一个范围的前 N 个元素进行排序
(函数模板) [编辑]
将元素分成两组,同时保留它们的相对顺序
(函数模板) [编辑]
对一个范围的元素进行排序,同时保留相等元素之间的顺序
(算法函数对象)[编辑]