Module: Standard C++ Library Library: Algorithms
Function
Generic algorithm for sorting collections of entities
#include <algorithm>
namespace std {
template <class RandomAccessIterator>
void stable_sort(RandomAccessIterator start,
RandomAccessIterator finish);
template <class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator start,
RandomAccessIterator finish, Compare comp);
}
The stable_sort() algorithm sorts the elements in the range [start, finish) in ascending order. The first version of the algorithm uses operator<() for the sort. The second version uses the function object comp.
The stable_sort() algorithm is considered stable because the relative order of equivalent elements is maintained.
stable_sort() does approximately N * (log(N))2 comparisons, where N equals finish - start. The algorithm calls std::get_temporary_buffer<>() to obtain extra memory. If enough extra memory is available, it does at most N * log(N) comparisons (i.e., the same as sort()).
//
// sort.cpp
//
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
struct associate
{
int num;
char chr;
associate (int n, char c) : num (n), chr (c){};
associate () : num (0), chr ('\0'){};
};
inline bool operator< (const associate &x, const associate &y)
{
return x.num < y.num;
}
inline std::ostream& operator<< (std::ostream &s,
const associate &x)
{
return s << '<' << x.num << ';' << x.chr << '>';
}
int main ()
{
const associate arr [20] = {
associate (-4, ' '), associate (16, ' '),
associate (17, ' '), associate (-3, 's'),
associate (14, ' '), associate (-6, ' '),
associate (-1, ' '), associate (-3, 't'),
associate (23, ' '), associate (-3, 'a'),
associate (-2, ' '), associate (-7, ' '),
associate (-3, 'b'), associate (-8, ' '),
associate (11, ' '), associate (-3, 'l'),
associate (15, ' '), associate (-5, ' '),
associate (-3, 'e'), associate (15, ' ')};
typedef std::vector<associate, std::allocator<associate> >
Vector;
// Set up vectors.
Vector v (arr, arr + sizeof arr / sizeof *arr);
Vector v1 (sizeof arr / sizeof *arr);
Vector v2 (sizeof arr / sizeof *arr);
// Copy original vector to vectors #1 and #2.
std::copy (v.begin (), v.end (), v1.begin ());
std::copy (v.begin (), v.end (), v2.begin ());
// Sort vector #1.
std::sort (v1.begin (), v1.end ());
// Stable sort vector #2.
std::stable_sort (v2.begin (), v2.end ());
// Display the results.
std::cout << "Original sort stable_sort"
<< std::endl;
for (Vector::iterator i = v.begin (), j = v1.begin (),
k = v2.begin ();
i != v.end (); i++, j++, k++)
std::cout << *i << " " << *j << " "
<< *k << std::endl;
return 0;
}
Program Output:
Original sort stable_sort <-4; > <-8; > <-8; > <16; > <-7; > <-7; > <17; > <-6; > <-6; > <-3;s> <-5; > <-5; > <14; > <-4; > <-4; > <-6; > <-3;e> <-3;s> <-1; > <-3;s> <-3;t> <-3;t> <-3;l> <-3;a> <23; > <-3;t> <-3;b> <-3;a> <-3;b> <-3;l> <-2; > <-3;a> <-3;e> <-7; > <-2; > <-2; > <-3;b> <-1; > <-1; > <-8; > <11; > <11; > <11; > <14; > <14; > <-3;l> <15; > <15; > <15; > <15; > <15; > <-5; > <16; > <16; > <-3;e> <17; > <17; > <15; > <23; > <23; >
sort(), partial_sort(), partial_sort_copy(), get_temporary_buffer()
ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25.3.1.2
Copyright (c) 1994-2006 Rogue Wave Software, a Quovadx Division.
Licensed under the Apache License, Version 2.0.
Contact Rogue Wave about documentation or support issues. You can also seek help from other developers through the Apache stdcxx community (see below).