To use STL iterators efficiently, you need to make decisions based on iterator type. The beauty of generic programming is that you can make those decisions at compile time.
Introduction
In my last column, I introduced you to the STL iterator concept by discussing the iterators that the STL containers expose. In order to get the maximum benefit out of using the STL, it is very important to understand that STL iterators are much more than just an interface into STL containers. Understanding and using STL-style iterators as a programming concept will significantly improve the readability, maintainability, and efficiency of your code, and it will increase the productivity in your shop. In this column, I will show how iterators fit into the big picture of software design and generic programming. This will lead us to some of the more complex aspects of the STL iterator concept, namely, iterator categories and iterator traits. Once we have mastered these, the stage is set for all kinds of creative uses of iterators.
Iterators in the Big Picture: an Example
If you have ever driven past one of these huge oil refineries, or a similar chemical processing plant, then you have probably wondered how on earth these people keep track of what’s flowing where in this maze of pipes and tanks and valves and what have you not. The first real C++ project I ever worked on was an extension to a popular general-purpose CAD (computer-aided design) system. The purpose of the extension was to facilitate the drawing of various kinds of blueprints for large systems of pipes, tanks, and related accessories, as found in oil refineries and other chemical plants. Once these plants are up and running, pretty much the only visible human activity in there is people crawling around checking for corrosion and attrition. This is done by taking measurements of the thickness of the metal walls and the welding seams, using sonar and X-ray technologies so that it can be done from the outside and while the plant is in operation. The people who do this must of course be given “roadmaps” to help them find their way around and to identify the points where they are supposed to take measurements. Most of our customers used our software to draw these “roadmaps,” and to update them when modifications were made to the plant, or when the maintenance people decided to change the locations of the measurements.
When I joined the team, our software was strictly a drawing tool. The results of the measurements were stored in a completely separate database, typically on a different machine in a different building. When it came to evaluating the maintenance state of the plant, someone made printouts of the numbers and printouts of our drawings and then mulled over this mound of papers, trying to figure out what parts of the system, if any, needed attention. Needless to say, it didn’t take long for people to come up with the idea to integrate the database holding the measurements with our software, which in turn was integrated with the CAD system. That way, the maintenance people would be able to bring up our drawings in the CAD system, click on a point of measurement, or an entire pipe or tank, and then bring up a variety of charts and tables displaying important items: the history of the wall thickness at one point of measurement, the thinnest point along a pipe as of the most recent measurement, the standard deviation of the most recent measurements along a pipe, and so on. It was our task to write and integrate the software to do this.
Figure 1 shows the obvious overall architecture of such a system. At the top, there is a UI layer that consists of two parts. The part labeled “User Request Input” gathers one or more requests from the user. This part is responsible for bringing up dialog boxes when the user has selected an element in the drawing, and for packaging the user’s request into some object format. The other part of the UI layer is responsible for displaying raw numbers as charts or tables in windows that are separate from the one that shows the drawing.
At the bottom of the architecture is a database access layer that is responsible for pulling numbers out of the database and placing them into appropriately designed objects. Since we were working with an existing relational database, we were actually designing a prehistoric object-relational mapping module here, but since it was all read-only access, that was not a big issue.
Right above the database access layer sits a number cruncher that performs any calculations that a particular request may require, such as computing a standard deviation. In many cases, this layer just forwards raw numbers. The center of the whole thing is a request broker that looks at a user request, obtains the necessary numbers from the number cruncher, and passes them on to the display module together with the instruction to display these numbers in a certain chart or table format.
Why am I discussing the overall architecture of an ancient piece of software when I should be talking about the creative use of STL-style iterators? The reason is that I want to emphasize how generic programming in general and STL-style iterators in particular are much more than just low-level implementation techniques. Software design at all levels is influenced by the paradigms that are available in the respective solution space. Much like the object paradigm, generic programming is an important programming paradigm that is available in the solution space provided by the C++ language. It will therefore have an impact on many high-level design decisions [1].
When we designed and wrote the software that I’m talking about, there was no STL. Therefore, I’ll be discussing how I would use generic programming and the STL in the design and implementation of such a program today (and have in fact used them in similar situations). As far as generic programming techniques are concerned, the most important thing to notice in our example is the fact that the results that are passed from the database access layer to the number cruncher and on to the display engine are typically sequences. When I display the thickness of the metal at a certain point on a pipe versus time, then I am looking at a sequence of points in a coordinate system, given by a sequence of dates as my x-coordinates and a sequence of numbers as my y-coordinates. Similarly, the rows or columns of a table often come naturally as sequences. One of the first global design decisions that should be made here — in fact, it should be a general design rule for all software that is to be implemented in C++ — is to pass around all sequences of numbers, dates, and the like, as pairs of iterators. Moreover, all functions that accept such a pair of iterators should be written as function templates with the type of iterator as a template parameter.
There are at least two major benefits to be reaped from such a design. First of all, and this is not to be underestimated, it makes for uniformity of style, which in turn improves readability and maintainability of the code. Secondly, by giving the components of your software generic interfaces, you greatly increase their interoperability and reusability. If you follow the rule of representing sequences as pairs of iterators and templatizing iterator types wherever possible, then every module that exposes sequences can work with any module that accepts sequences as its input.
Now let us look at the impact of this design decision on the relevant components in our example. Of the five modules in the example, three are affected strongly by this decision, namely, the display module, the database access module, and the number cruncher. For the display module, it means that the interface methods that accept the sequences of numbers or dates to be displayed in charts or tables must be function templates that accept a pair of iterators, with the type of the iterators being the template parameter. Somewhere deep inside this module, the drawing code will perform an iteration over these sequences, using them as x- and y-coordinate sequences of points to be drawn. If the actual drawing is deferred to a third-party charting package, then it may be necessary to insert an adaptation layer in order to translate the iterator idiom into whatever interface the charting package uses.
Recall that in the database access layer, we read sequences of numbers and dates out of a relational database and place them into various kinds of objects. An example would be an object that holds the measurents of wall thickness taken along one particular pipe on one particular date. This object holds all manner of general information such as the identifier of the pipe, the date the measurement was taken, information about the device used and the person or team that took the measurement, and so on. The actual numbers would naturally be placed into an STL vector in ascending order, according to the numbering of the points of measurement along the pipe. This sequence must then be exposed to the client of the class through a pair of iterators. Listing 1 shows the typical way to do this. Exposing a typedef for the type of iterator makes client code easier to write and look prettier, and it gives the author of the class the discretion to change the way the numbers are internally stored (which is not very likely to happen in this simple example, but it can be in more complex examples). Other than that, all that needs to be done is to forward the begin, end, and size methods to the underlying vector. Since the numbers are to be read-only by the client, it would be very poor style to expose non-const iterators here.
Next, let us assume that we also have a class that holds the measurements taken at a single point at different dates. Naturally, you would store this data inside the class as a vector of pairs, where each pair holds a date and a double. Now, exposing plain iterators for this collection to the clients of this class won’t do you much good. There may of course be some use for iterators pointing to such pairs. But clients will also want to do things such as calculating the median of the sequence of numbers. To be able to use generic algorithms for these purposes, clients of the class will want one pair of iterators that represents the sequence of numbers and another that represents the sequence of dates.
One way to do this would be to store the data in two parallel vectors rather than as a vector of pairs. This might be acceptable in this simple example, but it is certainly not a very satisfactory general solution for the issue at hand. In the spirit of the generic programming paradigm, what is called for here is a generic adaptor mechanism to turn an iterator pointing to a class or struct with public data members into an iterator pointing to a particular member of this class or struct. The STL does not provide such a mechanism. Instead, this is a perfect example of how the STL can and should be extended. That way, using the STL is much more than just using somebody else’s library; it is a starting point for introducing the generic programming paradigm into your software design. The adapting mechanism that I am talking about is in fact provided under the name IteratorToMember in an article that I wrote for this journal in 1998 [2]. I will look at this in more detail in my next column, after we have discussed iterator categories and iterator traits.
The third and last of the three modules in our example that are strongly affected by the use of iterators is the number crunching module. This module will provide a collection of algorithms to calculate things such as the standard deviation of a sequence of numbers. In keeping with the principles of generic programming, these must be written as function templates that receive their input sequence as a pair of iterators, with the type of the iterator being the template argument. Listing 2 shows an implementation of the sample standard deviation that follows this style [3].
One thing you should notice about this implementation is that it is somewhat inefficient when the iterators are of type std::vector::iterator. In this case, the number of points could have been determined more efficiently as
double dblNumPoints = static_cast<double>(it2 - it1);But we also know that other iterators, such as STL list, map, or set iterators, do not define subtraction. Therefore, using the above line in our algorithm would seriously take away from its genericity.
This would be a very annoying situation if the STL did not have a solution to it. First of all, the STL defines a categorization of iterators. This allows us to identify those categories for which an operation such as subtraction of iterators is defined and those for which it isn’t. Secondly, and more importantly, the STL provides us with a generic mechanism, called traits, to determine what category an iterator type belongs to and to select which operation to use accordingly. In our example, this mechanism will allow us to use the most efficient way of calculating the number of points in the sequence. The rest of this column will be devoted to a discussion of iterator categories and iterator traits.
Iterator Categories
The STL defines five different categories of iterators, namely, input iterators, output iterators, forward iterators, bidirectional iterators, and random access iterators. For a detailed discussion of these iterators, see for example Section 2.3 and Chapter 7 in Matt Austern’s book [4]. Another source that does a very nice job explaining iterator categories is Nicolai Josuttis’ book [5]. Here, I will just give you a brief description and an example for each of the categories.
An input iterator is an iterator that can be dereferenced in order to retrieve the value at the current position, but not to set that value. An input iterator can be moved forward by one step by means of operator++. Finally, when a sequence is given by a pair of input iterators, only one pass through the sequence is allowed. A subsequent pass through the sequence may yield different values. An output iterator obeys restrictions very similar to those of the input iterator, except that the dereferenced value of the iterator can only be set, but not retrieved.
Standard examples for input and output iterators are the STL stream and stream buffer iterators. Listing 3 shows an example. The first line defines an iterator for the stream buffer that is connected to cin. This is an input iterator. Upon dereferencing, it will return the current character; when incremented, the iterator will point to the next character from the stream buffer. The second line defines a default-constructed stream buffer iterator, which serves as an end-of-stream indicator. The third line defines an iterator for the stream buffer that is connected to cout. This is an output iterator. Assigning to *it_out will write the assigned character to the stream buffer; incrementing is actually a no-op in this case.
The call to std::copy in the last line of Listing 3 iterates over the sequence that is delimited by it_in and eos and copies each value of this sequence to a sequence of equal length that begins with it_out. It should now be clear what the overall effect of this code snippet is: it echoes keyboard input back to the console until the user enters Ctrl-Z. For more information on stream buffers and their iterators, you may want to go back to Matt Austern’s column in the March 2001 issue of this journal [6].
The third iterator category that the STL defines are forward iterators. A forward iterator is, in a sense, a combination of an input and output iterator insofar as it allows both reading and writing of its dereferenced value. Writing the value is of course prohibited when the iterator in question is a const iterator, but that restriction is independent of the iterator category. Moreover, forward iterators allow arbitrarily many passes through the sequences they delimit; that is, the dereferenced values will be the same no matter how many times you iterate over the sequence. A restriction that forward iterators share with input and output iterators is that they can only be incremented, not decremented, and incrementing happens one step at a time. A natural example for a forward iterator would be the iterator that is exposed by a singly linked list. The STL does not have singly linked lists, but they are an extension to the STL that is commonly found in STL implementations (see for example [4], Section 16.1.3 for more details). It should be clear that the iterators exposed by a list whose nodes have forward pointers to the respective next node, but no backward pointers to the respective previous node, will match the above description of forward iterators.
The fourth iterator category is bidirectional iterators. Bidirectional iterators add just one feature to forward iterators, namely, the ability to be decremented by one step. The natural example is, of course, the iterator that is exposed by a doubly linked list, such as std::list.
The last iterator category, random access iterators, adds to the properties of bidirectional iterators the ability to increment and decrement the iterator by arbitrarily many steps by means of operator+(int) and operator-(int), and to retrieve the distance between two iterators by subtracting one from the other, all in amortized constant time. Another way of viewing random access iterators is to say that they truly behave like C-style pointers, whereas the iterators in the other categories are similar to pointers, but lack certain features that we would expect from a pointer-like object. Examples of random access iterators are, well, C-style pointers. In the STL, the natural example of a random access iterator is std::vector::iterator. This is another reason for making std::vector the default choice among the STL containers: it gives you the best iterator.
Iterator Traits
So far, the STL’s categorization of iterators is nothing more than terminology. I said before that the STL actually enables us to write our templatized algorithms in such a way that we make the best use of the iterator type supplied as a template argument. What makes this problem a bit tricky is that the “branching” of the code according to the iterator category has to take place at compile time. That is because some iterator types use methods that others don’t even have, so the code used for one iterator type would not even compile for another.
I’ll take you to the STL’s solution to this problem in two steps. First of all, the STL defines, for each iterator category, a corresponding struct with an empty definition:
struct input_iterator_tag {}; struct output_iterator_tag {}; struct forward_iterator_tag : public input_iterator_tag {}; struct bidirectional_iterator_tag : public forward_iterator_tag {}; struct random_access_iterator_tag : public bidirectional_iterator_tag {};You can see that the inheritance hierarchy that these structs form reflects the refinement hierarchy of the iterator categories’ definition. The only flaw is that forward_iterator_tag should be derived from both input_iterator_tag and output_iterator_tag. Nobody seems to have an explanation for why it isn’t [7].
Each iterator class written for use with the STL contains a typedef that identifies the category of the iterator. For example, every time we write a random access iterator, we put
typedef random_access_iterator_tag iterator_category;inside the iterator’s definition. We may then use function overloading to make our algorithms select the appropriate code according to the category of the iterator type. Listing 4 shows how we would write our standard deviation algorithm using this technique. The top-level function calls an internal helper function that takes an additional dummy argument. A temporary object whose type is the respective iterator category is passed as this argument. The helper function is overloaded on this dummy argument, and voila, we have branched out according to the iterator category.
This all sounds very nice, but it still falls short of being a satisfactory solution to our problem of selecting code according to iterator category. The problem is that iterators may be primitive types, namely, plain old pointers. It is impossible to make the category typedef a part of these iterators’ definition. We must have a way to “affix” the iterator category externally to these types. To this end, the STL introduces a struct called iterator_traits:
template<typename _It> struct iterator_traits { typedef typename _It::iterator_category iterator_category; // some more stuff };The struct iterator_traits contains just typedefs. I will only talk about iterator_category here; I’ll let you use your favorite book to learn about the other typedefs in iterator_traits. To see how iterator_traits are used, look at Listing 5. Here, you see the final version of the algorithm SampleStandardDeviation. Only the top-level algorithm changes from Listing 4; the internal helpers remain the same. At first glance, this seems to be just an unnecessarily complicated version of what we did in Listing 4. Rather than getting the iterator category from the iterator directly, as in
_It::iterator_categorythe version of Listing 4 goes through iterator_traits<_It>, as in
std::iterator_traits<_It>:: iterator_categoryBut the latter is typedefed to be the former, so there is no difference at all. What have we gained by introducing the iterator_traits? Let’s look at the case that caused trouble before, namely, the case where the iterator is in fact a plain old pointer. What the STL does is define a partial specialization of iterator_traits that covers all plain pointers:
template<typename T> struct iterator_traits<T*> { typedef std::random_access_iterator_tag iterator_category; // some more stuff };Therefore, whenever the algorithm SampleStandardDeviation gets called with two plain pointers as its arguments, the function will no longer try to get the iterator category from the iterator type’s definition. Instead, it will use the above partial specialization and will thus find that the pointers are random access iterators. Quod erat demonstrandum, which was to be shown. Be sure to understand the supreme beauty of this solution. By default, all iterator classes define their iterator category by typedefing iterator_category in their definition. If that cannot be done because the iterator type is a basic type, or because the iterator class was written by a third party without consideration for use with the STL, then a specialization or partial specialization of iterator_traits steps in to “attach” the iterator category to the iterator type.
Two remarks are in order. The first one is good news: this technique of using a traits struct in order to branch on the type of a template argument is not limited to iterators. It is a powerful tool in generic programming. A very nice introduction by Andrei Alexandrescu to this technique can be found in one of the last issues of the now defunct C++ Report [8]. I will come back to this subject in this column sometime in the near future. The second remark is terrible news. This whole beautiful setup of iteator_traits is not going to work with the compiler that many of you are probably using, namely Microsoft’s Visual C++. The reason is that this compiler does not support partial template specialization as required by the Standard. But we just saw that partial template specialization is an integral part of the iterator_traits mechanism. Pop, goes the weasel. In my next column, I will touch briefly on how the STL implementation that comes with Visual C++ works around this shortcoming.
Addendum
In my last column, I used the example of the word-counting program to explain some things about std::map. My discussion was centered around this piece of code:
++(mapWordCount.insert (std::make_pair(strCurrentWord, 0)) .first->second);Several readers have pointed out that I should have mentioned an alternative, and much simpler way of expressing the same thing:
++mapWordCount[strCurrentWord];std::map offers operator[] as an alternative to the insert method. As a rule, using operator[] makes the code simpler to read. My original line of code is, in fact, a textbook example for how operator[] simplifies the code. However, it is important to realize that there is no gain in efficiency [9]. If you step into std::map::operator[], you will see that it is indeed little more than a convenient shorthand notation for std::map::insert. In order to understand what is going on, there is no way around going through the lengthy discussion that I gave in my last column. Using array-style notation is nothing more than syntactic sugar, but, as astute reader David Callaway so aptly put it, very sweet syntactic sugar indeed.
Notes and References
[1] For an enlightening treatise on the relationship between problem domain and solution domain in software design, see James O. Coplien, Multiparadigm Design for C++ (Addison-Wesley, 1998).
[2] Thomas Becker. “Smart Iterators and STL,” C/C+ Users Journal, September 1998, pp. 39-45.
[3] In this context, the word “sample” does not refer to sample code or anything like that. In statistics, there are two different kinds of standard deviation, the sample standard deviation and the population standard deviation, and this is the sample one.
[4] Matthew H. Austern. Generic Programming and the STL (Addison-Wesley, 1998).
[5] Nicolai M. Josuttis. The C++ Standard Library: A Tutorial and Reference (Addison-Wesley, 1999).
[6] Matthew H. Austern. “The Standard Librarian: Streambufs and Streambuf Iterators,” C/C++ Users Journal, March 2001, pp. 72-76
[7] In Section 19.2.3 of his book, The C++ Programming Language, Third Edition (Addison-Wesley, 1997), Bjarne Stroustrup says: “... we would expect forward_iterator_tag to be derived from output_iterator_tag as well as from input_iterator_tag. The reasons that it is not are obscure and probably invalid. However, I have yet to see an example in which that derivation would have simplified real code.”
[8] Andrei Alexandrescu. “Traits: The else-if-then of Types,” C++ Report, April 2000, pp. 22-25, 31
[9] It is true that there are some very subtle efficiency considerations when it comes to choosing between map::insert and map::operator[]. These considerations have to do with constructing objects of the map's value type. Therefore, this is pretty much a moot point when the value type is int.
Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, NV. He can be reached at thomas@styleadvisor.com.