std::stable_sort
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
.
Contents |
[edit] 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: bool cmp(const Type1 &a, const Type2 &b); The signature does not need to have const &, but the function object must not modify the objects passed to it. |
Type requirements | ||
-
RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator .
|
||
-The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible .
|
[edit] Return value
(none)
[edit] 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)).
[edit] 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.
[edit] 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
[edit] See also
sorts the first N elements of a range (function template) |
|
sorts a range into ascending order (function template) |
|
(parallelism TS)
|
parallelized version of std::stable_sort (function template) |