Standard C++ LibraryCopyright 1996, Rogue Wave Software, Inc.

NAME

  stable_sort  - Templated algorithm for sorting collections of entities.

SYNOPSIS

  #include <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);

DESCRIPTION

  The stable_sort algorithm sorts the elements in the range [first, last).
  The first version of the algorithm uses less than (<) as the comparison
  operator  for the sort.  The second version uses the comparison function
  comp.

  The stable_sort algorithm is considered stable because the relative order
  of the equal elements is preserved.

COMPLEXITY

  stable_sort does at most N(logN) **2, where N equals last  -first,
  comparisons;  if enough extra memory is available, it is NlogN.

EXAMPLE

  //
  // sort.cpp
  //
   #include <vector>
   #include <algorithm>
   #include <functional>
   #include <iostream.h>

  struct associate
   {
    int num;
    char chr;

    associate(int n, char c) : num(n), chr(c){};
    associate() : num(0), chr(' '){};
   };

  bool operator<(const associate &x, const associate &y)
   {
    return x.num < y.num;
   }

  ostream& operator<<(ostream &s, const associate &x)
   {
    return s << "<" << x.num << ";" << x.chr << ">";
   }

  int main ()
   {
    vector<associate>::iterator i, j, k;

    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, ' ')};

     // Set up vectors
    vector<associate> v(arr, arr+20), v1((size_t)20),
                  v2((size_t)20);

     // Copy original vector to vectors #1 and #2
    copy(v.begin(), v.end(), v1.begin());
    copy(v.begin(), v.end(), v2.begin());

     // Sort vector #1
    sort(v1.begin(), v1.end());

     // Stable sort vector #2
     stable_sort(v2.begin(), v2.end());

     // Display the results
    cout << "Original    sort      stable_sort" << endl;
    for(i = v.begin(), j = v1.begin(), k = v2.begin();
        i != v.end(); i++, j++, k++)
    cout << *i << "     " << *j << "     " << *k << endl;

    return 0;
   }

  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; >

WARNING

  If your compiler does not support default template parameters, then you
  need to always supply the Allocator template argument. For instance, you
  will need to write :

  vector<int, allocator>

  instead of :

  vector<int>

SEE ALSO

  sort, partial_sort,  partial_sort_copy

STANDARDS CONFORMANCE

  ANSI X3J16/ISO WG21 Joint C++ Committee



privacy and legal statement