学步园

Algorithms

Up to this point we have discussed how to use STL at a bare minimum, now we need to delve into the most important part of the collections. How do we manipulate a collection? For example, if we had list of strings, what would we need to sort the list in alphabetical order, or if we wanted to search a collection for a set of elements that matched a given criterion. This is where STL algorithms are used. In your visual studio installation, under include directory, you will find an include file, algorithm. In algorithm a set of template based functions are declared. These functions can be used to manipulate STL collections. The functions can be categorized in the following: sequence, sorting and numeric. Using these categories, we can list all of the methods of algorithms:

Sequence

count, count_if, find, find_if, adjacent_find, for_each, mismatch, equal, search copy, copy_backward, swap, iter_swap, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, transform, remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, stable_partition

Sorting

Sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, pop_heap, sort_heap, min, max, min_element, max_element, lexographical_compare, next_permutation, prev_permutation

Numeric

Accumulate, inner_product, partial_sum, adjacent_difference

Since this is an extensive list, we will only examine a few of the methods in the algorithms. It is very important to note that the methods here are templated so we are not required to use the STL containers to use the methods. For example, we could have a list of ints and to sort this list then we could do:

#include <vector>
#include <algorithm>
#include <iostream>

vector<int>              myVec;
vector<int>::iterator    item;
ostream_iterator<int>    out(cout," ");
// generate array
for ( long i=0; i<10; i++ )
    myVec.push_back(i);
// shuffle the array
random_shuffle( myVec.begin(), myVec.end() );
copy( myVec.begin(), myVec.end(), out );
// sort the array in ascending order
sort( myVec.begin(), myVec.end() );
copy( myVec.begin(), myVec.end(), out );

This example shows how declare the vector and then sort it, using STL containers. We could do the same without using containers:

ostream_iterator<int>  out(cout," ");
// generate array (note: one extra element, end in STL is one element past last valid)
int myVec[11];
for ( long i=0; i<10; i++ )
    myVec[i] = i;
int * begin = &myVec[0];
int * end = &myVec[10];
// shuffle the array
random_shuffle( begin, end );
copy( begin, end, out );
// sort the array in ascending order
sort( begin, end );
copy( begin, end, out );

How you use the algorithms is largely up to you, but they provide a rich set of methods for manipulating containers.