[ новости /+++ | форум | теги | ]

                       Standard C++ Library
             Copyright 1998, Rogue Wave Software, Inc.


NAME
     stable_sort

      - A templatized algorithm for sorting collections of  enti-
     ties.



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  comparisons,  where  N
     equals           last  -  first.  If  enough extra memory is
     available, it does at most NlogN.



EXAMPLE
     //
     // sort.cpp
     //
     #include <vector>
     #include <algorithm>
     #include <functional>
     #include <iostream>
     using namespace std;

     struct associate
      {
     int num;
     char chr;

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


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

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



WARNINGS
     If your compiler does not support default  template  parame-
     ters,  then you always need to supply the Allocator template
     argument. For instance, you need to write:

     vector<int, allocator>

     instead of:

     vector<int>
     If your compiler does not support namespaces,  then  you  do
     not need the using declaration for std.



SEE ALSO
     sort,_partial_sort, partial_sort_copy

Партнёры:

Хостинг: