C++/STL Algorithms Sorting/sort — различия между версиями
Admin (обсуждение | вклад) м (1 версия: Импорт контента...) |
|
(нет различий)
| |
Версия 14:21, 25 мая 2010
Содержание
- 1 Sort all element in an array
- 2 Sort a string array with sort()
- 3 Sort a subset of the container
- 4 Sort a vector and print out the sorted elements
- 5 Sort a vector into ascending order of id members
- 6 Sort elements in deque
- 7 Sort elements reversely with custom function
- 8 Sorting user-defined class
- 9 Sort into descending order by using greater
- 10 Sort part of the elements in an array
- 11 Sort random number
- 12 Sort the entire container
- 13 Use custom function and sort to sort strings by length
- 14 Using an in-place generic sort algorithm
- 15 Using the generic sort algorithm with a binary predicate: greater
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 "
*/