Let me know!
Chris Riesbeck
Last updated: July 3, 2009
This is a quick summary of some of the most useful algorithms in the Standard Template Library.
See also the STL set algorithms.
Algorithm: a generic function for searching or modifying STL containers.
Note that these functions take iterators, not containers. This is an important pattern of the STL that should be followed in your own generic code.
Many of them also take functional arguments. What you can do with generic algorithms, iterators, and functional arguments can be pretty amazing.
The generic functions use iterators just as you use pointers in C to get elements from and store elements to various containers. Some generic functions can work with the minimal iterators, others may require the extra features. So a certain algorithm may require certain containers because only those containers can return the necessary kind of iterators.
Many of the generic algorithms take functions as arguments. This brings to C++ the same kind of higher order programming found in Scheme and Lisp.
The concepts behind higher order functions are covered in EECS 111.
Musser et al. call these nonmutating sequence algorithms. They are used to search containers and collect information, but they do not change the contents of the containers.
InputIterator find(InputIterator begin,
InputIterator end,
const T& value);find looks for value in the container, starting at begin, and stopping with end. As usual for all STL algorithms, end is not looked at. It is the location just past the last item to check.
resultIter = find(v.begin(), v.end(), value); if (resultIter != v.end()) cout << "Found it!" << endl;
Notice that find doesn't return a boolean value, it returns an iterator. That iterator points to the place where the value was found. This lets us search for more occurrences, if we want to. We just add the following code to the above:
resultIter = find(resultIter++, v.end(), value); if (resultIter != v.end()) cout << "Found it again!" << endl;
We could easily use this to write a loop to count how many times the value occurs in the container, but the STL already provides a count algorithm for us.
find_if is for searching with a general predicate rather than a value.
InputIterator find_if(InputIterator begin,
InputIterator end,
Predicate pred);find_if returns an iterator pointing to the first value in the range satisfying the predicate.
As is typical with the STL, we create predicates using function objects, i.e., defining a class that overloads operator(). There are lots of variations on how to do this. The code below finds the first even number in a container, by defining a function object IsEven and an instance of it, evenPred, in one declaration, and passing evenPred to find_if:
class IsEven {
public:
bool operator() (int x) const
{ return ((x % 2) == 0); }
} evenPred;
resultIter = find_if(v.begin(), v.end(), evenPred);
if (resultIter != v.end())
cout << "Found the even number " << (*resultIter) << endl;count is for counting occurrences of a value in a container.
size_t count(InputIterator begin,
InputIterator end,
const T& value);count counts the number of occurrences of the value between begin and end and adds the result to n. size_t is an integer type defined to be large enough to hold the maximum size of any container.
int num = count(v.begin(), v.end(), 10); cout << "Found " << num << " occurrences of 10." << endl;
count_if is like count and find_if. It counts every element in the range that satisfies the predicate.
size_t count_if(InputIterator begin,
InputIterator end,
Predicate pred);The following code, using the same evenPred function object defined above, counts the even numbers in the given range:
int numEvens = count_if(v.begin(), v.end(), evenPred); cout << "Found " << numEvens << " even numbers" << endl;
Several algorithms are primarilly for working with containers of numbers.
max_element and min_element find the maximum and minimum element of a range of elements in a container. Like find and find_if, they return an iterator pointing to the element found. If none is found, the iterator will point to the end of the range.
ForwardIterator
max_element(ForwardIterator begin,
ForwardIterator end)
ForwardIterator
min_element(ForwardIterator begin,
ForwardIterator end)Notice that max_element and min_element rquire ForwardIterator's, not just InputIterator's. This is because they have to save the iterator of the largest or smallest element found, and InputIterator's don't support saving.
Here is a simple usage:
vector<int> v; vector<int>::iterator result; ... cout << "Looking for max number" << endl; result = max_element(stats.begin(), stats.end()); if (result != stats.end()) cout << "Found " << (*result) << endl;
These versions of max_element and min_element uses operator< to find the biggest and smallest items. You can also pass a function object to max_element and min_element. The function should return true when the second argument is "bigger" in some sense than the first argument.
ForwardIterator
max_element(ForwardIterator begin,
ForwardIterator end,
Compare pred)
ForwardIterator
min_element(ForwardIterator begin,
ForwardIterator end,
Compare pred)Here's code to find the largest odd number:
class MaxOdd {
public:
bool operator() (int theMax, int x)
{ return ((x % 2) == 1) && (x > theMax); }
};
...
cout << "Looking for max odd" << endl;
result = max_element(stats.begin(), stats.end(), MaxOdd());
if (result != stats.end())
cout << "Found " << (*result) << endl;Can you think of a situation in which the above code might return an even number?
accumulate adds up a range of elements in a container.
T accumulate(InputIterator begin,
InputIterator end,
T initial_value)To add up all the numbers in our vector,
cout << "Sum of all the numbers is "
<< accumulate(stats.begin(), stats.end(), 0)
<< endl;The third argument, 0 in this case, is the initial value for the sum.
The above call to accumulate uses operator+ but you can pass a function as a fourth argument to change this. That function should take two arguments. The first argument will be the "sum" so far, starting with the initial value given. Each element will be passed in turn to the second element.
T accumulate(InputIterator begin,
InputIterator end,
T initial_value,
BinaryOperation op)So, to add up just the odd numbers:
class SumOdd {
public:
int operator() (int sum, int y)
{ return ((y % 2) == 1) ? sum + y : sum; }
};
...
cout << "Sum of all the odd numbers is "
<< accumulate(stats.begin(), stats.end(), 0, SumOdd())
<< endl;Copying algorithms copy ranges of elements from one container to another.
OutputIterator
copy(InputIterator begin1,
InputIterator end1,
OutputIterator begin2)
OutputIterator
remove_copy(InputIterator begin1,
InputIterator end1,
OutputIterator begin2,
const T& value)
OutputIterator
remove_copy_if(InputIterator begin1,
InputIterator end1,
OutputIterator begin2,
Predicate pred)
OutputIterator
transform(InputIterator begin1,
InputIterator end1,
OutputIterator begin2
UnaryOperation op)copy() copies the elements in the first range to the output iterator given. remove_copy() does the same thing except that it doesn't copy anything == to value. remove_copy_if() is the same as remove_copy() except that it doesn't copy anything satisfying the predicate. transform() is the same as copy() except that it applies op to each element and stores the result.
Why is there no copy_if()? Stroustrup apologies for accidentally leaving out this algorithm (The C++ Programming Language, 3rd Ed., p 530). He gives the following definition, which shows how easy it is to define many of the basic generic algorithms:
template<class In, class Out, class Pred>
Out copy_if(In begin, In end, Out dest, Pred p)
{
while (begin != end) {
if (P (*begin)) *dest++ = *begin;
++end;
}
return dest;
}Of course, you can always just use remove_copy_if() with a predicate that selects what you don't want to copy.
If the output iterator is a normal iterator pointer to a container, then the elements being copied replace the existing elements in the output container. It is an error if there's not enough room in the output container.
If the output iterator is an insertion iterator, then the elements being copied are inserted into the container.
If the output iterator is an ostream iterator, then the elements being copied are written to the output stream.
Here's an example of copying all the odd numbers from a vector to a new vector, using a function object evenPred that returns true for even numbers:
remove_copy_if(v1.begin(), v1.end(),
back_inserter(v2),
evenPred);Here's an example of using transform. Assume that the vector sv contains Employee structures that have integer idNum values. We can copy those values into a simple vector of integers iv thus:
int getIdNum(const Employee &e) { return e.idNum; }
transform(sv.begin(), sv.end(),
back_inserter(iv),
getIdNum);The STL has a rich assortment of sorting-related algorithms. Just a few are described here.
sort sorts a range of elements in a container.
void sort(RandomAccessIterator begin,
RandomAccessIterator end)This is pretty obvious. Given a container that support random access iterators, it sorts the elements in the range specified by the iterators, using operator< as overloaded by the underlying elements.
To sort the vector v, we just say
sort(v.begin(), v.end());
Not surprisingly, instead of using operator< you can give a specific comparison function to use:
void sort(RandomAccessIterator begin,
RandomAccessIterator end,
Compare comp)sort is guaranteed to be O(n log n) on the average, but neither stable nor immune to worst case behavior of O(n2).
To get a stable sort, which will also be O(n log n) but probably slower than sort, use stable_sort. It takes the same arguments as sort.
Finally, if you only need the first N elements, e.g., the 5 biggest numbers, you can partially sort the container and save time:
void partial_sort(RandomAccessIterator begin,
RandomAccessIterator middle,
RandomAccessIterator end)
void partial_sort(RandomAccessIterator begin,
RandomAccessIterator middle,
RandomAccessIterator end,
Compare comp)This says "sort the elements in the range until you've gotten the elements from begin to middle sorted." It's left undetermined what order the elements from middle to end are in.
For example, to get the first 5 elements sorted:
partial_sort(v.begin(), v.begin()+5, v.end());
Comments?
Let me know!