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

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


NAME
     partial_sort

      - Templatized algorithm for sorting  collections  of  enti-
     ties.



SYNOPSIS
     #include <algorithm>
     template <class RandomAccessIterator>
     void partial_sort (RandomAccessIterator first,
                        RandomAccessIterator middle,
                        RandomAccessIterator last);

     template <class RandomAccessIterator, class Compare>
     void partial_sort (RandomAccessIterator first,
                        RandomAccessIterator middle,
                        RandomAccessIterator last,
                        Compare comp);



DESCRIPTION
     The partial_sort algorithm takes the range [first,last)  and
     places  the  first  middle - first values into sorted order.
     The result is that the range [first, middle) is sorted  like
     it  would  be  if the entire range [first,last) were sorted.
     The remaining elements  in  the  range  (those  in  [middle,
     last))  are  not  in any defined order. The first version of
     the algorithm uses less than (operator<) as  the  comparison
     operator  for  the  sort.  The  second version uses the com-
     parison function comp.



COMPLEXITY
     partial_sort  does   approximately   (last    -   first)   *
     log(middle-first) comparisons.



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

     int main()
      {
       int d1[20] = {17, 3,  5,  -4, 1, 12, -10, -1, 14, 7,
                      -6, 8, 15, -11, 2, -2,  18,  4, -3, 0};
        //
        // Set up a vector.
        //
       vector<int> v1(d1+0, d1+20);
        //
        // Output original vector.
        //
       cout << "For the vector: ";
       copy(v1.begin(), v1.end(),
            ostream_iterator<int,char>(cout," "));
        //
        // Partial sort the first seven elements.
        //
        partial_sort(v1.begin(), v1.begin()+7, v1.end());
        //
        // Output result.
        //
       cout << endl << endl << "A partial_sort of seven elements
                                gives: "
             << endl << "     ";
       copy(v1.begin(), v1.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl;
        //
        // A vector of ten elements.
        //
       vector<int> v2(10, 0);
        //
        // Sort the last ten elements in v1 into v2.
        //
       partial_sort_copy(v1.begin()+10, v1.end(), v2.begin(),
                         v2.end());
        //
        // Output result.
        //
       cout << endl << "A partial_sort_copy of the last ten
             elements gives: "
             << endl << "     ";
       copy(v2.begin(), v2.end(),
            ostream_iterator<int,char>(cout," "));
       cout << endl;
       return 0;
      }

     Program Output



     For the vector: 17 3 5 -4 1 12 -10 -1 14 7 -6 8 15 -11 2  -2
     18 4 -3 0
     A partial_sort of seven elements gives:
          -11 -10 -6 -4 -3 -2 -1 17 14 12 7 8 15 5 3 2 18 4 1 0
     A partial_sort_copy of the last ten elements gives:
         0 1 2 3 4 5 7 8 15 18



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

     vector<int, allocator<int> >

     instead of:

     vector<int>

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



SEE ALSO
     sort, stable_sort, partial_sort_copy_

Партнёры:

Хостинг: