Wait! Don’t write that algorithm! Someone already did. But if you insist, follow this advice.
Introduction
When I started this column a little more than a year ago, one of the first things that I said about the STL was that it consists of three major components, which I referred to as the “Three Pillars of the STL,” namely, containers, iterators, and algorithms. So far, I have discussed containers and iterators, and I have spent a total of four columns on these two subjects. Therefore, you might now expect at least two columns on the subject of algorithms. Indeed, I could easily fill several columns discussing what kind of algorithms there are in the STL and then looking at each of them individually. But then, this is the kind of information you can get more easily and more systematically from your favorite book on the STL. Personally, I like the presentation that’s given in Josuttis’ book [1] and also the one in Chapter 18 of Stroustrup’s book on the C++ language [2]. Here, I will be content with giving you a little bit of general advice and direction on how to use the algorithms that the STL provides, and how to write your own.
My advice to you on the subject of algorithms can be summarized as follows:
- Make yourself familiar with the algorithms that the STL offers and use them wisely.
- Whenever you write a function that operates on a range of elements, write it as a generic STL-style algorithm.
Let me now elaborate on each of these two points in more detail.
STL Algorithms Are Non-Intrusive
An STL algorithm operates on one or more ranges of elements. Each range is given by a pair of iterators. In certain rare cases, of which I’ll give an example shortly, a single iterator pointing to the begin position of a range suffices to specify the range. The standard example of an STL algorithm is our old friend std::find. Here’s how it’s typically implemented:
template<typename _It, typename _T> inline _It find(_It beg, _It end, const _T& val) { for(; beg != end; ++beg) if(val == *beg) break; return beg; }If you don’t already know what std::find does, you can easily deduce it from the code above. The point that I’m trying to illustrate here is that an algorithm has no knowledge whatsoever of the exact nature of the data structure that holds the range of elements. As a matter of fact, there does not have to be a data structure at all. Consider the following example:
std::istreambuf_iterator<char> it_in(std::cin.rdbuf()); std::istreambuf_iterator<char> eos; it_in = std::find(it_in, eos, 'x');Here, the algorithm std::find looks at characters as the user enters them and returns when either ’x’ is read, or when the user enters Ctrl-Z. The fact that algorithms have so little knowledge of the nature of the ranges that they operate on is the key to their reusability. On the other hand, it does of course impose certain limitations on the actions that an algorithm can possibly perform on a range of elements. It is extremely important to understand these limitations, or else you may end up misinterpreting the action of certain algorithms completely. A famous example of this kind of possible misinterpretation is the algorithm std::remove. Suppose you have an std::vector with some integers in it, some of which equal 42 [3], as in:
std::vector<int> vect(4); vect[0] = 41; vect[1] = 42; vect[2] = 43; vect[3] = 42;In order to remove all occurrences of 42 from the vector, you make the following call:
std::vector<int>::iterator ret_it = std::remove(vect.begin(), vect.end(), 42);Someone with a superficial understanding of the STL might think that after this call, the vector vect has two elements, namely, 41 and 43. That is of course impossible. When the algorithm std::remove gets called with the vector’s begin and end iterators as arguments, it gains access to the elements of the vector in the sense that it can read any element or modify any element or both, depending on the nature of the iterator. It does not have access to or even any kind of knowledge of the vector’s member functions that modify its size.
So if it didn’t change the vector’s size, then in what sense did std::remove get rid of the occurrences of 42 in the vector? The key to the answer lies in the fact that std::remove returns an iterator. std::remove promises that after the call:
ret_it = std::remove(beg, end, val);the range that is delimited by beg and ret_it contains the elements that were previously in the range delimited by beg and end, in the original order, with all occurrences of val omitted. It is not hard to see how this can indeed be accomplished given nothing but the two iterators beg and end and the value to be removed: conceptually, the algorithm iterates through the given range, and every time it finds an occurrence of val, it copies all subsequent elements to the position immediately to their left, thereby overwriting the occurrence of val. All that’s needed to do this is a pair of forward iterators. Listing 1 shows a typical implementation, which, of course, goes about shifting elements in a way that’s much smarter than what I just described. Only one pass through the range is required, and at most n-1 copy operations take place. By the way, the STL makes no guarantee about what elements you’ll find in the “leftover range” from ret_it to end.
If this kind of “non-intrusive” removal is not good enough, and you need to really throw the leftover elements out of your vector, then you need to follow the call to std::remove with a call to std::vector::erase, like this:
vect.erase( std::remove(vect.begin(), vect.end(),42), vect.end() );If you have read a good book on the STL, or if you regularly read the columns in this magazine, then you probably already know why the following alternative to the code above is not good at all. The net effect of the code above could also have been achieved using just the member function std::vector::erase like this:
std::vector<int>::iterator beg = vect.begin(); while(beg != vect.end()) { if(42 == *beg) beg = vect.erase(beg); else ++beg; }This is bad, bad, bad, for at least two reasons. First of all, it is very poor style to write an explicit loop when an STL algorithm does the job just as well. Using a one-line call to an algorithm will greatly improve the readability and maintainability of your code, and it will make it much less error-prone. Due to inlining and the fact that the designer of the algorithm probably knew more about the problem at hand than you and me, using an algorithm is also likely to result in better performance. And that takes us to the second reason why the code above is bad. It betrays ignorance of std::vector’s efficiency characteristics. Every time the loop finds an occurrence of 42, it completely rearranges the vector so as to eliminate this particular occurrence. This will most certainly result in copying all elements to the right of the occurrence. Worse still, it may well result in a reallocation of memory and subsequent copying of all remaining elements in the vector. Compare this to the remove-erase solution, where you iterate through the vector just once, copy each element at most once, and then perform one resizing operation.
So now we know that the remove-erase trick is the best way to perform conditional erasing from a vector. This is important because we frequently choose std::vector as our container for other, more important reasons and then find ourselves in need of conditional erasing. If, on the other hand, conditional erasing is a frequently occurring and performance-critical operation, then std::vector was probably the wrong choice of container to begin with: we should have used std::list, which is specifically geared toward efficient insertion and deletion of elements at arbitrary positions.
This takes me to another very important point concerning the use of STL algorithms, namely, the issue of algorithms versus member functions.
Algorithms vs. Member Functions
If we have chosen std::list as the container type for the sake of more efficient insertion and deletion at arbitrary positions, then the example above would look like this:
std::list<int> li; li.push_back(41); li.push_back(42); li.push_back(43); li.push_back(42); li.remove(42);After the call to std::list::remove, our list will contain the two elements 41 and 43, and nothing else. The member function std::list::remove did, of course, make use of the specific structure of a linked list to perform the deletion of elements in the most efficient way. No shifting of elements has occurred; all that std::list::remove did was to iterate linearly through the list, bend a few pointers here and there, and zap some deleted elements. Given the fact that an algorithm such as std::remove has no access to the internal structure of the container that it operates on (in fact, it does not even know whether it’s operating on a container or not), it is clear that you can reap the benefit of std::list’s efficient deletion only by using the member function std::list::remove rather than the algorithm std::remove.
Another important example of this relationship between algorithms and member functions is std::find versus the find member function of the STL’s associative containers, such as std::map and std::set. If you call std::find on a range of elements, you will be iterating linearly through the range, stopping at the first occurrence of an element with the value you are looking for. The STL’s associative containers are designed for a vastly more efficient type of lookup, namely, lookup of no more than logarithmic complexity. However, you cannot get the benefit of this enormous gain in efficiency unless you use the respective container’s member function find rather than the algorithm std::find.
Algorithms and Insert Iterators
I said before that STL algorithms are non-intrusive in the sense that they cannot modify the structure of a container that they operate on, the reason being that they don’t even know whether or not they’re operating on a container at all. However, there is a fairly common STL idiom that allows you to cheat on this restriction of algorithms. Let’s take a look at the algorithm std::transform.
template<typname _InIt, typename _OutIt, typename _Func> std::transform( _InIt in_beg, _InIt in_end, _OutIt out_beg, _Func func );This algorithm iterates over a range of elements given by a pair of input iterators: in_beg and in_end. To each element in the range, it applies a function that is supplied by the caller as a function pointer or a function object. The return values are copied to a second range, whose begin position is specified by a single output iterator out_beg. Here’s an example:
std::istreambuf_iterator<char> it_in(std::cin.rdbuf()); std::istreambuf_iterator<char> eos; std::ostreambuf_iterator<char> it_out(std::cout.rdbuf()); std::transform(it_in, eos, it_out, toupper);This call to std::transform will read characters from the input and write an up-cased version of each character to the output until the user enters Ctrl-Z. Notice that I have passed the address of the function toupper from the C run-time library’s ctype.h as the last argument to std::transform. From the C++ Standard library’s viewpoint, this is poor style. However, doing it right will in this case open several cans of worms (one of them being quite ugly) that I don’t want to talk about now. I promise that I’ll come back to this in my next column.
Now assume that rather than writing the up-cased characters to the standard output stream, you want to write them to a vector. The problem is that we don’t know ahead of time how many characters the user will enter. But the algorithm std::transform assumes that it can write as many elements as it finds in its input range, given by in_beg and in_end, to the range that begins at out_beg. If out_beg is the begin iterator of some vector, then that vector’s size must be greater than or equal to the number of elements in the input range. There is no way for the algorithm std::transform to manipulate the vector’s size as it goes along. This problem would be a rather unpleasant restriction to the use of algorithms, such as std::transform, if the STL did not have a solution for it. The answer is insert iterators. The STL has several kinds of insert iterators, and you should make yourself familiar with all of them. What they all have in common is the fact that they hold a reference to the container that they operate on. Therefore, they can do what regular iterators cannot do: they can modify the size of the container that they refer to. A suitable example of std::transform trying to write to a vector is std::back_insert_iterator:
std::vector<char> vect; std::back_insert_iterator<std::vector<char> > inserter(vect); std::istreambuf_iterator<char> it_in(std::cin.rdbuf()); std::istreambuf_iterator<char> eos; std::transform(it_in, eos, inserter, toupper);Every time that std::transform performs an assignment to inserter, as in:
*inserter = toupper(c);the back_insert_iterator inserter internally calls std::vector’s push_back member function on the vector vect. This is possible because inserter holds a reference to vect. Therefore, the up-cased characters read from the input stream will be pushed onto the back of the vector in an orderly manner.
In this example, we are forced to use an insert iterator with std::transform because we don’t know ahead of time how many elements the algorithm std::transform will find in its input range. When the length of the input range is known or can easily be determined as the difference between the two iterators that specify the input range, then a regular iterator could be used after sizing the target vector, as in the following example. Here, beg and end are random access iterators that dereference to chars.
std::vector<char> vect(end - beg); std::transform(beg, end, vect.begin(), toupper);Even though we could thus avoid the use of insert iterators in this situation, a better solution in general is as follows:
std::vector<char> vect; vect.reserve(end - beg); std::back_insert_iterator<std::vector<char> > inserter(vect); std::transform(beg, end, inserter, toupper);For vectors of chars there is probably no discernible difference between this solution and the previous one. But if the element type of the vector is something more complex than a char, then sizing the vector upfront is likely to result in superfluous calls to the default constructor, which can be avoided altogether by calling reserve and then adding elements through an insert iterator, as shown above.
Here are some more scenarios where the use of an insert iterator is or could be preferable to the use of a regular iterator with algorithms such as std::transform:
- The target container is a list. Here, sizing the container upfront and then assigning through a regular iterator is in fact more expensive than repeatedly calling push_front or push_back or insert through an insert iterator.
- The target container is an associative container, such as std::set. Here, sizing the container upfront and then assigning through a regular iterator does not even make sense. An insert iterator is the only option.
- The input range is given by a pair of iterators that are not random access iterators. In this case, determining the size of the input range, if it is possible at all, is an expensive operation whose cost must be weighed carefully in the decision between the use of insert iterators and regular iterators.
Writing Your Own Algorithms
It should be clear by now that in the interest of reusability, any function that operates on one or more ranges of elements should be written as an STL-style algorithm, where the ranges are given by pairs of iterators, and the types of the iterators are template arguments, one for each pair of iterators. In fact, I have already shown you an example in my April column in connection with iterator traits, namely, the sample standard deviation algorithm. Writing STL-style algorithms is usually a rather straightforward affair. There is only one thing that I need to remind you of: whenever your algorithm is such that it can operate more efficiently on iterators of a certain category, then you should write the algorithm in such a way that it branches out at compile time according to the iterator category. Again, I already showed you that in the April column, where the algorithm was able to perform better for random access iterators as opposed to all other iterator categories. Listing 2 shows you how this compile-time branching is set up. Listing 3 shows the _Iter_cat kludge that you must resort to if you are working with a compiler that is behind on template support, such as Microsoft’s Visual C++.
Let’s do one more concrete example of an STL-style algorithm. Suppose you need to determine the median of a range of numbers that are already sorted in ascending or descending order. Basically, what the algorithm must do is find out the length of the range and then proceed to the position in the middle. These are typical examples of operations that can be performed for all forward iterators, but they can be done much more efficiently for random access iterators than for all other forward iterators: for random access iterators, these operations can be performed in constant time using expressions such as end-beg and beg+n. For all other forward iterators, one must hop through the sequence in linear time using only operator++.
Therefore, you might expect to have to set up compile-time branching as shown in Listing 2 for your median algorithm. As it happens so often, the STL already has a few building blocks that make our lives quite easy. I am talking about std::advance and std::distance. The first of these will advance an iterator by a given number of steps; the second one will determine the number of elements in the range given by a pair of iterators. Both are function templates that internally branch at compile time on the category of the iterator arguments, thereby employing the most efficient strategy to perform their respective tasks. Listing 4 shows how we can now easily implement our median algorithm without any further branching.
Conclusion
Make sure you know what the STL has to offer in the way of algorithms, or else you’ll be missing out on a lot of powerful functionality. But don’t forget: before you use an algorithm on a container or parts of a container, make sure that there isn’t a container member function that does the same job more efficiently. Make it a habit to write all functions that operate on ranges of elements as reusable STL-style algorithms. For more valuable advice along the lines of this column, see Chapter 5 of Scott Meyers’s Effective STL [4].
References
[1] Nicolai M. Josuttis. The C++ Standard Library: A Tutorial and Reference (Addison-Wesley, 1999).
[2] Bjarne Stroustrup. The C++ Programming Language, 3rd Edition (Addison-Wesley, 1997).
[3] In case you haven’t heard, Douglas Adams, author of The Hitchhiker’s Guide to the Galaxy and many other fine books, passed away on May 11, 2001 at the age of 48. A sad and untimely demise, no doubt, but at least he lived long enough to give us the answer.
[4] Scott Meyers. Effective STL (Addison-Wesley, 2001).
Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, NV. He can be reached at thomas@styleadvisor.com.