Defined in header <algorithm> | ||
---|---|---|
template< class RandomIt > void stable_sort( RandomIt first, RandomIt last ); | (1) | |
template< class RandomIt, class Compare > void stable_sort( RandomIt first, RandomIt last, Compare comp ); | (2) |
Sorts the elements in the range [first, last)
in ascending order. The order of equal elements is guaranteed to be preserved. The first version uses operator<
to compare the elements, the second version uses the given comparison function comp
.
Parameters
first, last | - | the range of elements to sort |
comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare ) 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:
The signature does not need to have |
Type requirements | ||
- RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator . | ||
-The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible . |
Return value
(none).
Complexity
O(N·log2(N)), where N = std::distance(first, last)
applications of cmp
. If additional memory is available, then the complexity is O(N·log(N)).
Notes
This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted, typically by calling std::get_temporary_buffer
. If the allocation fails, the less efficient algorithm is chosen.
Example
#include <algorithm> #include <iostream> #include <string> #include <vector> struct Employee { Employee(int age, std::string name) : age(age), name(name) { } int age; std::string name; // Does not particpate in comparisons }; bool operator<(const Employee &lhs, const Employee &rhs) { return lhs.age < rhs.age; } int main() { std::vector<Employee> v = { Employee(108, "Zaphod"), Employee(32, "Arthur"), Employee(108, "Ford"), }; std::stable_sort(v.begin(), v.end()); for (const Employee &e : v) { std::cout << e.age << ", " << e.name << '\n'; } }
Output:
32, Arthur 108, Zaphod 108, Ford
See also
sorts the first N elements of a range (function template) | |
sorts a range into ascending order (function template) | |
std::experimental::parallel::stable_sort
(parallelism TS) | parallelized version of std::stable_sort (function template) |
Please login to continue.