std::stable_sort

Определено в заголовке `<algorithm>`
	(1)
template< class RandomIt > void stable_sort( RandomIt first, RandomIt last );		(до C++26)
template< class RandomIt > constexpr void stable_sort( RandomIt first, RandomIt last );		(с C++26)
template< class ExecutionPolicy, class RandomIt > void stable_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(с C++17)
	(3)
template< class RandomIt, class Compare > void stable_sort( RandomIt first, RandomIt last, Compare comp );		(до C++26)
template< class RandomIt, class Compare > constexpr void stable_sort( RandomIt first, RandomIt last, Compare comp );		(с 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) в порядке невозрастания. Порядок эквивалентных элементов гарантированно сохраняется.

Последовательность сортируется с помощью компаратора comp таким образом, что для любого итератора it, указывающего на последовательность, и любого неотрицательного целого числа n, при котором it + n является допустимым итератором, указывающим на элемент последовательности, выражение comp(*(it + n), *it) (или *(it + n) < *it) оценивается как false.

1) Элементы сравниваются с помощью operator<.

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)

Параметры

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

Возвращаемое значение

(нет)

Сложность

O(N·log(N)²), где N = std::distance(first, last) применения cmp. Если дополнительная память доступна, то сложность составляет O(N·log(N)).

Исключения

Перегрузки с параметром шаблона, названным ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной в рамках алгоритма, вызывает исключение и ExecutionPolicy является одной из стандартных политик, std::terminate вызывается. Для любой другой ExecutionPolicy, поведение определяется реализацией.
Если алгоритм не может выделить память, std::bad_alloc выбрасывается.

Примечания

Данная функция пытается выделить временный буфер, равный по размеру сортируемой последовательности. Если выделение памяти терпит неудачу, выбирается менее эффективный алгоритм.

Макрокоманда проверки функций	Значение	Std	Функция
`__cpp_lib_constexpr_algorithms`	202306L		`constexpr` устойчивая сортировка

Возможная реализация

См. также реализации в libstdc++ и libc++.

Пример

#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

См. также

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

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