std::stable_sort

Определено в заголовочном файле `<algorithm>`
template< class RandomIt > void stable_sort( RandomIt first, RandomIt last );	(1)	(constexpr с C++26)
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)	(constexpr с C++26)
template< class ExecutionPolicy, class RandomIt, class Compare > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );	(4)	(с C++17)

Сортирует элементы в диапазоне [first, last) в неубывающем порядке. Порядок эквивалентных элементов гарантированно сохраняется.

1) Элементы сортируются относительно operator<(до C++20)std::less{}(с C++20).

3) Элементы сортируются относительно comp.

2,4) То же, что и (1,3), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки только в том случае, если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(с C++20)

Если выполняется любое из следующих условий, поведение не определено:

Тип `*first` не удовлетворяет требованиям Swappable.	(до C++11)
`RandomIt` не удовлетворяет требованиям ValueSwappable. Тип `first` не удовлетворяет требованиям MoveConstructible. Тип `first` не удовлетворяет требованиям MoveAssignable.	(с C++11)

Параметры

first, last	-	пара итераторов, задающая диапазон сортируемых элементов
policy	-	политика выполнения, которая будет использоваться
comp	-	объект функционального типа для сравнения (то есть объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго (то есть расположен перед ним). Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&b); Хотя сигнатура не обязана содержать const&, функция не должна изменять переданные ей объекты и должна принимать любые значения типов (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` не допускается; также не допускается `Type1`, если только для `Type1` перемещение не эквивалентно копированию(с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt можно было разыменовать, а затем неявно преобразовать к каждому из них.
Требования к типам
-`RandomIt` должен удовлетворять требованиям LegacyRandomAccessIterator.
-`Compare` должен удовлетворять требованиям Compare.

Сложность

Пусть \(\scriptsize N\)N — это last - first:

1,2) \(\scriptsize O(N \cdot \log(N))\)O(N·log(N)) сравнений с использованием operator<(до C++20)std::less{}(с C++20), если доступно достаточно дополнительной памяти; в противном случае — \(\scriptsize O(N \cdot \log^{2}(N))\)O(N·log²(N)) сравнений. 3,4) \(\scriptsize O(N \cdot \log(N))\)O(N·log(N)) применений функции сравнения comp, если доступно достаточно дополнительной памяти; в противном случае — \(\scriptsize O(N \cdot \log^{2}(N))\)O(N·log²(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

См. также

sort	сортирует диапазон элементов (шаблон функции и функциональный объект алгоритма)
ranges::sort (C++20)
partial_sort	сортирует первые N элементов диапазона (шаблон функции и функциональный объект алгоритма)
ranges::partial_sort (C++20)
stable_partition	разделяет элементы на две группы, сохраняя их относительный порядок в каждой группе (шаблон функции и функциональный объект алгоритма)
ranges::stable_partition (C++20)
ranges::stable_sort (C++20)	сортирует диапазон элементов, сохраняя относительный порядок эквивалентных элементов (функциональный объект алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/stable_sort