|
stable_sort
function template
<algorithm>
template <class RandomAccessIterator>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
Sort elements preserving order of equivalents
Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort grants that the relative order of the elements with equivalent values is preserved.
The elements are compared using operator< for the first version, and comp for the second.
Parameters
- first, last
- Random-Access iterators to the initial and final positions of the sequence to be sorted. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.
- comp
- Comparison function object that, taking two values of the same type than those contained in the range, returns true if the first argument goes before the second argument in the specific strict weak ordering it defines, and false otherwise.
Return value
none
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
// stable_sort example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool compare_as_ints (double i,double j)
{
return (int(i)<int(j));
}
int main () {
double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};
vector<double> myvector;
vector<double>::iterator it;
myvector.assign(mydoubles,mydoubles+8);
cout << "using default comparison:";
stable_sort (myvector.begin(), myvector.end());
for (it=myvector.begin(); it!=myvector.end(); ++it)
cout << " " << *it;
myvector.assign(mydoubles,mydoubles+8);
cout << "\nusing 'compare_as_ints' :";
stable_sort (myvector.begin(), myvector.end(), compare_as_ints);
for (it=myvector.begin(); it!=myvector.end(); ++it)
cout << " " << *it;
cout << endl;
return 0;
}
|
compare_as_ints is a function that compares only the integral part of the elements, therefore, elements with the same integral part are considered equivalent. stable_sort preserves the relative order these had before the sorting. Output:
using default comparison: 1.32 1.42 1.62 1.73 2.58 2.72 3.14 4.67
using 'compare_as_ints' : 1.41 1.73 1.32 1.62 2.72 2.58 3.14 4.67
|
Complexity
Between N*logN and N*(LogN^2) comparisons (where N is last-first).
See also
| sort | Sort elements in range (function template) |
| partial_sort | Partially Sort elements in range (function template) |
| search | Find subsequence in range (function template) |
| reverse | Reverse range (function template) |
|