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 если первый аргумент меньше второго (т.е. упорядочен перед вторым). Сигнатура функции сравнения должна быть эквивалентна следующей: bool cmp ( const Type1 & a, const Type2 & b ) ; Хотя сигнатура не обязана содержать const & , функция не должна модифицировать передаваемые объекты и должна быть способна принимать все значения типов (возможно const) `Type1` и `Type2` независимо от категории значения (следовательно, `Type1&` не допускается , как и `Type1` , если для `Type1` перемещение не эквивалентно копированию (since C++11) ). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt мог быть разыменован и неявно преобразован к обоим из них.
Требования к типам
- `RandomIt` должен удовлетворять требованиям LegacyRandomAccessIterator .
- `Compare` должен удовлетворять требованиям Compare .

Сложность

Дано $\scriptsize N$ $N$ как last - first :

1,2)

O(N\cdotlog(N))

сравнений с использованием operator < (до C++20) std:: less { } (начиная с C++20) при наличии достаточного объема дополнительной памяти, в противном случае

O(N\cdotlog 2 (N))

сравнений.

3,4)

O(N\cdotlog(N))

применений компаратора comp при наличии достаточного объема дополнительной памяти, в противном случае

O(N\cdotlog 2 (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; // Не участвует в сравнениях
};
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)	сортирует диапазон элементов, сохраняя относительный порядок между эквивалентными элементами (объект-функция алгоритма)

Поддержка компиляторов
Автономные и размещённые реализации
Язык
Стандартная библиотека
Заголовки стандартной библиотеки
Именованные требования
Макросы для проверки возможностей (C++20)
Библиотека поддержки языка
Библиотека концепций (C++20)
Библиотека диагностики
Библиотека управления памятью
Библиотека метапрограммирования (C++11)
Библиотека общих утилит
Библиотека контейнеров
Библиотека итераторов
Библиотека диапазонов (C++20)
Библиотека алгоритмов
Библиотека строк
Библиотека обработки текста
Библиотека численных операций
Библиотека даты и времени
Библиотека ввода/вывода
Библиотека файловой системы (C++17)
Библиотека поддержки конкурентности (C++11)
Библиотека управления выполнением (C++26)
Технические спецификации
Индекс символов
Внешние библиотеки

ru.cppreference.net

Namespaces

Variants