std::stable_sort() 算法

自 C++26 起

// (1)
template< class RandomIt >
constexpr void stable_sort( RandomIt first, RandomIt last );

// (2)
template< class RandomIt, class Compare >
constexpr void stable_sort( RandomIt first, RandomIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class RandomIt >
void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );

自 C++17 起

// (1)
template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );

// (2)
template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class RandomIt >
void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );

C++17 之前

// (1)
template< class RandomIt >
void stable_sort( RandomIt first, RandomIt last );

// (2)
template< class RandomIt, class Compare >
void stable_sort( RandomIt first, RandomIt last, Compare comp );

以非降序对范围 [first; last) 中的元素进行排序。

等效元素的顺序保证保持不变。

如果对于指向序列的任何迭代器it和任何非负整数n，使得it + n是指向序列元素的有效迭代器，则comp(*(it + n), *it) (或 *(it + n) < *it)的计算结果为false，则序列相对于比较器comp是已排序的。

• (1) 元素使用 operator< 进行比较。

• (2) 元素使用给定的二元比较函数 comp 进行比较。

• (3, 4) 与 (1) 和 (2) 相同，但根据策略执行。

  重载决议

  这些重载仅在 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 起)

参数

first last	要排序的元素范围。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
cmp	比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容： bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受所有类型（可能为 const）Type 和 Type2 的值，无论值类别如何（因此不允许Type1&，除非对于Type1，移动等同于复制，否则也不允许Type1 (自 C++11 起)） `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

RandomIt	ValueSwappable LegacyRandomAccessIterator
解引用RandomIt的类型	MoveAssignable MoveConstructible
Compare	Compare

返回值

(无)

复杂度

给定 N 为 std::distance(first, last)

O(N * pow(log(N), 2)) 次comp应用。

如果额外内存可用，则复杂度为O(N * log(N))。

无论实现如何，保证进行O(N * log(N)) 次比较，其中N是std::distance(first, last)。

异常

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

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

备注

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

示例

Main.cpp

#include <algorithm>
#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;
}

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