C++/STL Algorithms Sorting/sort — различия между версиями

Материал из C\C++ эксперт
Перейти к: навигация, поиск
м (1 версия: Импорт контента...)
 
м (1 версия: Импорт контента...)
 
(нет различий)

Текущая версия на 10:27, 25 мая 2010

Sort all element in an array

  
 
/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
    int coll[] = { 5, 6, 2, 4, 1, 3 };
    // sort beginning with the second element
    sort (coll, coll+6);
    // print all elements
    copy (coll, coll+6,
          ostream_iterator<int>(cout," "));
    cout << endl;
}
/* 
1 2 3 4 5 6
 */


Sort a string array with sort()

  
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
   string words[5] = { "ABCD", "BCDEF", "CERF","DERT", "EFRE"};
   string*   where;
   where = find(words, words + 5, "CD");
   
   cout << *++where << endl;                
   
   sort(words, words + 5);
   
   where = find(words, words + 5, "ER");
   cout << *++where << endl;              
}


Sort a subset of the container

  
#include <cstdlib>
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
void show(const char *msg, vector<int> vect);
int main()
{
  vector<int> v(10);
  for(unsigned i=0; i < v.size(); i++)
    v[i] = rand() % 100;
  show("Original order:", v);
  sort(v.begin()+2, v.end()-2);
  show("sorting elements v[2] to v[7] into natural order:", v);
  return 0;
}
void show(const char *msg, vector<int> vect) {
  cout << msg << endl;
  for(unsigned i=0; i < vect.size(); ++i)
    cout << vect[i] << endl;
  
}


Sort a vector and print out the sorted elements

  
 
/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    vector<int> coll;
    vector<int>::iterator pos;
    // insert elements from 1 to 6 in arbitrary order
    coll.push_back(2);
    coll.push_back(5);
    coll.push_back(4);
    coll.push_back(1);
    coll.push_back(6);
    coll.push_back(3);
    // sort all elements
    sort (coll.begin(), coll.end());
    // print all elements
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        cout << *pos << " ";
    }
}
 /* 
1 2 3 4 5 6 
 */


Sort a vector into ascending order of id members

  
 
#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
class MyClass : public binary_function<MyClass, MyClass, bool> {
public:
  int id;
  bool operator()(const MyClass& x, const MyClass& y) const {
     return x.id >= y.id;
  }
  friend ostream& operator<<(ostream& o, const MyClass& x) {
    o << x.id;
    return o;
  }
};
int main()
{
  vector<MyClass> vector1(100);
  for (int i = 0; i != 100; ++i)
    vector1[i].id = 100 - i - 1;
  sort(vector1.begin(), vector1.end(), not2(MyClass()));
  for (int k = 0; k != 100; ++k)
    cout << vector1[k].id << " ";
  return 0;
}
/* 
0 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 8
3 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 "
 */


Sort elements in deque

  
 
/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <numeric>
/* PRINT_ELEMENTS()
 * - prints optional C-string optcstr followed by
 * - all elements of the collection coll
 * - separated by spaces
 */
template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
    typename T::const_iterator pos;
    std::cout << optcstr;
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        std::cout << *pos << " ";
    }
    std::cout << std::endl;
}
/* INSERT_ELEMENTS (collection, first, last)
 * - fill values from first to last into the collection
 * - NOTE: NO half-open range
 */
template <class T>
inline void INSERT_ELEMENTS (T& coll, int first, int last)
{
    for (int i=first; i<=last; ++i) {
        coll.insert(coll.end(),i);
    }
}
using namespace std;
int main()
{
    deque<int> coll;
    INSERT_ELEMENTS(coll,1,9);
    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"on entry: ");
    // sort elements
    sort (coll.begin(), coll.end());
    PRINT_ELEMENTS(coll,"sorted:   ");
}
/* 
on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
sorted:   1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
 */


Sort elements reversely with custom function

  
 
/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <numeric>
/* PRINT_ELEMENTS()
 * - prints optional C-string optcstr followed by
 * - all elements of the collection coll
 * - separated by spaces
 */
template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
    typename T::const_iterator pos;
    std::cout << optcstr;
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        std::cout << *pos << " ";
    }
    std::cout << std::endl;
}
/* INSERT_ELEMENTS (collection, first, last)
 * - fill values from first to last into the collection
 * - NOTE: NO half-open range
 */
template <class T>
inline void INSERT_ELEMENTS (T& coll, int first, int last)
{
    for (int i=first; i<=last; ++i) {
        coll.insert(coll.end(),i);
    }
}
using namespace std;
int main()
{
    deque<int> coll;
    INSERT_ELEMENTS(coll,1,9);
    INSERT_ELEMENTS(coll,1,9);
    PRINT_ELEMENTS(coll,"on entry: ");
    // sorted reverse
    sort (coll.begin(), coll.end(),    // range
          greater<int>());             // sorting criterion
    PRINT_ELEMENTS(coll,"sorted >: ");
}
/* 
on entry: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
sorted >: 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1
 */


Sorting user-defined class

  
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
class MyClass
{
   public:
   MyClass( int num_points = 0 );
   bool operator<( const MyClass& rhs ) const;
   int num_points() const;
   void print() const;
   private:
   vector<float> data_;
};
inline
MyClass::MyClass( int num_points ): data_( num_points ){}    
inline bool MyClass::operator<( const MyClass& rhs ) const { 
   return num_points() < rhs.num_points(); 
}
inline
int MyClass::num_points() const {  
   return static_cast<int>( data_.size() ); 
}
inline void MyClass::print() const{ 
   cout << "\nThis experiment has " << num_points() << " data points";
}
bool less_than_iterator( const vector<MyClass>::iterator i,const vector<MyClass>::iterator j );
// evaluate *i < *j
int main( )
{
   vector<MyClass> v;
   int num_v = 3;
   v.reserve( num_v );
   v.push_back( MyClass( 3 ) );
   v.push_back( MyClass( 9 ) );
   v.push_back( MyClass( 5 ) );
   for_each( v.begin(), v.end(),mem_fun_ref( &MyClass::print ) );
   vector< vector<MyClass>::iterator > iterators( v.size() );
   vector< vector<MyClass>::iterator >::iterator j = iterators.begin();
   vector<MyClass>::iterator i = v.begin();
   vector<MyClass>::iterator v_end = v.end();
   while( i != v_end )
      *j++ = i++;
   sort( iterators.begin(), iterators.end(), less_than_iterator );
   vector< vector<MyClass>::iterator >::iterator iterators_end = iterators.end();
   for( j = iterators.begin(); j != iterators_end; ++j )
      (*j)->print();
   for_each( v.begin(), v.end(), mem_fun_ref( &MyClass::print ) );
}
bool less_than_iterator( const vector<MyClass>::iterator i,const vector<MyClass>::iterator j )
{  
   return *i < *j;   
}


Sort into descending order by using greater

  
#include <cstdlib>
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
void show(const char *msg, vector<int> vect);
int main()
{
  vector<int> v(10);
  for(unsigned i=0; i < v.size(); i++)
    v[i] = rand() % 100;
  show("Original order:", v);
  sort(v.begin(), v.end(), greater<int>());
  show("Order after sorting into descending order:", v);
  return 0;
}
void show(const char *msg, vector<int> vect) {
  cout << msg << endl;
  for(unsigned i=0; i < vect.size(); ++i)
    cout << vect[i] << endl;
}


Sort part of the elements in an array

  
 
/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
using namespace std;
int main()
{
    int coll[] = { 5, 6, 2, 4, 1, 3 };
    // sort beginning with the second element
    sort (coll+3, coll+6);
    // print all elements
    copy (coll, coll+6,ostream_iterator<int>(cout," "));
    cout << endl;
}
 /* 
5 6 2 1 3 4
 */


Sort random number

  
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5;
int main()
{
   int    d[N], i, *e = d + N;
   for (i = 0; i < N; ++i){
      d[i] = rand();
   }   
   sort(d, e);
   for (i = 0; i < N; ++i){
      cout << d[i];
   }   
}


Sort the entire container

  
#include <cstdlib>
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
void show(const char *msg, vector<int> vect);
int main()
{
  vector<int> v(10);
  for(unsigned i=0; i < v.size(); i++)
    v[i] = rand() % 100;
  show("Original order:", v);
  sort(v.begin(), v.end());
  show("Order after sorting into natural order:", v);
  return 0;
}
void show(const char *msg, vector<int> vect) {
  cout << msg << endl;
  for(unsigned i=0; i < vect.size(); ++i)
    cout << vect[i] << endl;
}


Use custom function and sort to sort strings by length

  
 
/* The following code example is taken from the book
 * "The C++ Standard Library - A Tutorial and Reference"
 * by Nicolai M. Josuttis, Addison-Wesley, 1999
 *
 * (C) Copyright Nicolai M. Josuttis 1999.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 */
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <numeric>
/* PRINT_ELEMENTS()
 * - prints optional C-string optcstr followed by
 * - all elements of the collection coll
 * - separated by spaces
 */
template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
    typename T::const_iterator pos;
    std::cout << optcstr;
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        std::cout << *pos << " ";
    }
    std::cout << std::endl;
}
/* INSERT_ELEMENTS (collection, first, last)
 * - fill values from first to last into the collection
 * - NOTE: NO half-open range
 */
template <class T>
inline void INSERT_ELEMENTS (T& coll, int first, int last)
{
    for (int i=first; i<=last; ++i) {
        coll.insert(coll.end(),i);
    }
}
using namespace std;
bool lessLength (const string& s1, const string& s2)
{
    return s1.length() < s2.length();
}
int main()
{
    vector<string> coll1;
    vector<string> coll2;
    // fill both collections with the same elements
    coll1.push_back ("1xxx");
    coll1.push_back ("2x");
    coll1.push_back ("3x");
    coll1.push_back ("4x");
    coll1.push_back ("5xx");
    coll1.push_back ("6xxxx");
    coll1.push_back ("7xx");
    coll1.push_back ("8xxx");
    coll1.push_back ("9xx");
    coll1.push_back ("10xxx");
    coll1.push_back ("11");
    coll1.push_back ("12");
    coll1.push_back ("13");
    coll1.push_back ("14xx");
    coll1.push_back ("15");
    coll1.push_back ("16");
    coll1.push_back ("17");
    coll2 = coll1;
    PRINT_ELEMENTS(coll1,"on entry:\n ");
    // sort (according to the length of the strings)
    sort (coll1.begin(), coll1.end(),           // range
          lessLength);                          // criterion
    stable_sort (coll2.begin(), coll2.end(),    // range
                 lessLength);                   // criterion
    PRINT_ELEMENTS(coll1,"\nwith sort():\n ");
    PRINT_ELEMENTS(coll2,"\nwith stable_sort():\n ");
}
 /* 
on entry:
 1xxx 2x 3x 4x 5xx 6xxxx 7xx 8xxx 9xx 10xxx 11 12 13 14xx 15 16 17
with sort():
 17 2x 3x 4x 16 15 13 12 11 9xx 7xx 5xx 8xxx 14xx 1xxx 10xxx 6xxxx
with stable_sort():
 2x 3x 4x 11 12 13 15 16 17 5xx 7xx 9xx 1xxx 8xxx 14xx 6xxxx 10xxx
 */


Using an in-place generic sort algorithm

  
 
#include <iostream>
#include <algorithm>
#include <cassert>
using namespace std;
int main() {
  int a[1000];
  int i;
  
  for (i = 0; i < 1000; ++i) 
    a[i] = 1000 - i - 1;
  sort(&a[0], &a[1000]);
  for (i = 0; i < 1000; ++i) 
    assert (a[i] == i);
  
  return 0;
}


Using the generic sort algorithm with a binary predicate: greater

  
 
#include <iostream>
#include <algorithm>
#include <cassert>
#include <functional>
using namespace std;
int main() {
  int a[100];
  int i;
  for (i = 0; i < 100; ++i)
    a[i] = i;
  random_shuffle(&a[0], &a[100]);
  for (i = 0; i < 100; ++i)
    cout <<  a[i] << " ";
  cout <<"\n\n\n\n";
  // Sort into descending order:
  sort(&a[0], &a[100], greater<int>());

  for (i = 0; i < 100; ++i)
    cout <<  a[i] << " ";

  return 0;
}
/* 
12 1 9 98 96 27 58 82 86 90 18 62 32 40 71 51 91 41 94 17 8 47 64 66 65 7 6 76 5
 99 77 81 54 35 56 39 25 3 87 16 61 68 14 13 24 55 97 19 20 59 75 33 21 28 78 15
 50 34 36 44 83 38 46 60 84 95 57 22 37 23 70 89 31 79 73 92 11 2 88 42 30 52 72
 53 67 29 85 43 74 69 45 26 93 10 48 80 0 63 49 4

99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73
 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 4
6 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 "
 */
Источник — «http://cppe.ru/index.php?title=C%2B%2B/STL_Algorithms_Sorting/sort&oldid=1832»