std::stable_sort() algorithm
- since C++26
- od C++17
- do C++17
// (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 );
// (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 );
// (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 );
Sorts the elements in the range [first
; last
) in non-descending order.
The order of equivalent elements is guaranteed to be preserved.
A sequence is sorted with respect to a comparator comp
if for any iterator it
pointing to the sequence
and any non-negative integer n
such that it + n
is a valid iterator pointing to an element of the sequence,
comp(*(it + n), *it) (or *(it + n) < *it)
evaluates to false
.
-
(1) Elements are compared using
operator<
. -
(2) Elements are compared using the given binary comparison function
comp
. -
(3, 4) Same as (1) and (2), but executed according to policy.
Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
istrue
. (do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
istrue
. (od C++20)
Parameters
first last | The range of elements to sort. |
policy | The execution policy to use. See execution policy for details. |
cmp | Comparison function object (i.e. an object that satisfies the requirements of Compare). The signature of the comparison function should be equivalent to the following:
|
Type requirements
RandomIt | ValueSwappable LegacyRandomAccessIterator |
Type of dereferenced RandomIt | MoveAssignable MoveConstructible |
Compare | Compare |
Return value
(none)
Complexity
Given N
as std::distance(first, last)
O(N * pow(log(N), 2)) applications of comp
.
If additional memory is available, then the complexity is O(N * log(N)).
Regardless of implementation, guaranteed O(N * log(N)) comparisons, where N is std::distance(first, last)
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Notes
This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted. If the allocation fails, the less efficient algorithm is chosen.
Examples
#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
Hover to see the original license.