The Standard Template Library includes functions that programmers can use to sort a variety of containers. One of these functions is the sort function. The sort function performs a fast sort (typically a quicksort) on a container.
| 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: | #include <iostream>#include <cstdlib>#include <ctime>#include <vector>#include <algorithm>#include <iterator> using namespace std; int random_less_than_50(void) { return (rand() % 50);} int main(int argc, char* argv[]) { // seed the random number generator srand( time(0) ); // create a vector with ten random elements (all less than 50) vector<int> v; back_insert_iterator< vector<int> > back_itr(v); generate_n(back_itr, 10, random_less_than_50); // display its contents ostream_iterator<int> out(cout, " "); copy(v.begin(), v.end(), out); // sort the vector sort(v.begin(), v.end()); // display its contents, sorted cout << endl; copy(v.begin(), v.end(), out); return EXIT_SUCCESS;} |
| Listing 2 Using the sort algorithm |
Listing 2 uses a few other functions that warrant explanation. First, the STL function generate_n is used in Listing 2 to populate a vector with ten random numbers. This function takes as parameters an output iterator, a number of items to generate, and a function to use to generate each item. The generated items are placed in the output iterator specified in the first parameter. In this case, the output iterator is a back_insert_iterator for the vector v. Thus, all items generated by the function in the third parameter are placed at the end of vector v. The function specified in the third parameter is a wrapper for the C-library function rand. The function rand returns a random number from the runtime's random number generator. This random number can be quite large, so a wrapper function is used to reduce the number returned to a smaller range of values.
The sort function can operate only on containers that provide random access iterators. Containers such as vector, deque, and string all provide random access iterators. Since the STL list container does not provide random access iterators the general-purpose sort function on a list object results in a compile-time error. Since linked lists often need to be sorted, the list container has a special sort member function. Listing 3 demonstrates its use.
| 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: | #include <iostream>#include <cstdlib>#include <ctime>#include <list>#include <algorithm>#include <iterator> using namespace std; int random_less_than_50(void) { return (rand() % 50);} int main(int argc, char* argv[]) { // seed the random number generator srand( time(0) ); // create a list with ten random elements // (all less than 50) list<int> ls; back_insert_iterator< list<int> > back_itr(ls); generate_n(back_itr, 10, random_less_than_50); // display its contents ostream_iterator<int> out(cout, " "); copy(ls.begin(), ls.end(), out); // sort the list // The following can NOT be used since lists // do not provide random access iterators // sort(ls.begin(), ls.end()); ls.sort(); // display its contents again cout << endl; copy(ls.begin(), ls.end(), out); return EXIT_SUCCESS;} |
| Listing 3 Sorting a list |
In addition to sorting, the STL provides the ability to shuffle the contents of a container. Shuffling, the opposite of sorting, is the random arrangement of data in a set. The following listing demonstrates the STL function random_shuffle.
| 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: | // create a deque with 10 elementsdeque<int> d;for (int i = 1; i <= 10; i++) { d.push_back(i);} ostream_iterator<int> out(cout, " "); for (int j = 1; j <= 5; j++) { // display its contents copy(d.begin(), d.end(), out); cout << endl; random_shuffle(d.begin(), d.end()); copy(d.begin(), d.end(), out); cout << endl << endl; sort(d.begin(), d.end());} |
| Listing 4 Shuffling a container |