From cppreference.com
Defined in header
template<classRandomIt>voidstable_sort(RandomItfirst,RandomItlast); (1)(constexpr since C++26)template<classRandomIt,classCompare>voidstable_sort(RandomItfirst,RandomItlast,Comparecomp); (2)(constexpr since C++26)template<classExecutionPolicy,classRandomIt>voidstable_sort(ExecutionPolicy&&policy,RandomItfirst,RandomItlast); (3) (since C++17)template<classExecutionPolicy,classRandomIt,classCompare>voidstable_sort(ExecutionPolicy&&policy,RandomItfirst,RandomItlast,Comparecomp); (4) (since C++17)Sorts the elements in the target range [first, last). The order of equivalent elements is guaranteed to be preserved.
1) Elements are
with respect to operator<(until C++20)std::less{}(since C++20).
2) Elements are sorted with respect to comp.
3,4) Same as (1,2), but executed according to policy.
These overloads participate in overload resolution only if the value of the following expression is true:
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20)If any of the following conditions is satisfied, the behavior is undefined:
Parameters
first, last - the pair of iterators defining the target
comp - comparison function object (i.e. an object that satisfies the requirements of
) which returns true if the first argument is less than (i.e. is ordered before) the second. The signature of the comparison function should be equivalent to the following:
boolcmp(constType1&a,constType2&b);
While the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of
(thus, Type1& is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy(since C++11)).
The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them.
policy - the
to use Type requirements -RandomIt must meet the requirements of
. -Compare must meet the requirements of
. Complexity
Given N as last-first:
1,3)𝓞(N·log2(N)) comparisons using operator<(until C++20)std::less{}(since C++20) (or only 𝓞(N·log(N)) comparisons if enough extra memory is available).
2,4)𝓞(N·log2(N)) applications of the comparator comp (or only 𝓞(N·log(N)) comparisons if enough extra memory is available).
Exceptions
3,4) During the execution process:
If the temporary memory resources required for parallelization are not available,
is thrown.
If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for
,
is invoked).
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.
macroValueStdFeature
__cpp_lib_constexpr_algorithms
(C++26)constexpr stable sorting, overloads (
)Possible implementation
See also the implementations in
and
.
Example
Run this code
#include<algorithm>#include<array>#include<iostream>#include<string>#include<vector>structEmployee{intage;std::stringname;// Does not participate in comparisons};booloperator<(constEmployee&lhs,constEmployee&rhs){returnlhs.age<rhs.age;}#if __cpp_lib_constexpr_algorithms >= 202306Lconstevalautoget_sorted(){autov=std::array{3,1,4,1,5,9};std::stable_sort(v.begin(),v.end());returnv;}static_assert(std::ranges::is_sorted(get_sorted()));#endifintmain(){std::vector<Employee>v{{108,"Zaphod"},{32,"Arthur"},{108,"Ford"}};std::stable_sort(v.begin(),v.end());for(constEmployee&e:v)std::cout<<e.age<<", "<<e.name<<'\n';}Output:
32, Arthur 108, Zaphod 108, Ford See also
(C++20)
sorts a range of elements while preserving relative order between equivalent elements
(algorithm function object)
sorts a range of elements
(function template & algorithm function object)
(C++20)
sorts the first N elements of a range
(function template & algorithm function object)
(C++20)
divides elements into two groups while preserving their relative order within each group
(function template & algorithm function object)
(C++20)