Christopher Baus and Thomas Becker
Zephyr Associates Inc.
christopher@baus.net
thomas@styleadvisor.com
The iterators that come with the STL typically represent ranges within an STL container. In other words, the range of data items that is represented by a pair of these iterators is present in memory in the form of an STL container object. We have found many situations where a program needs to iterate through sequentially structured data, but this data is not or should not be present in memory in the form of a range in a container. The STL allows the client programmer to write custom iterators that gather or generate their data in ways other than pulling it sequentially out of a container. Writing such an iterator for a specific situation is a rather elementary task. However, it is possible to identify unifying concepts among these custom iterators and implement them generically.
One purpose of this article is to present several generic custom iterator class templates. Another, perhaps more important purpose is to demonstrate how understanding and applying the generic programming paradigm has helped us to unleash the full power of the STL.
It did not take long for us to become quite enthralled with the elegance and ease of use afforded by the container-iterator-algorithm trinity. Therefore, the idea of letting our own classes expose iterators came quite naturally. More precisely, whenever a class contains sequentially organized data that it wishes to expose through its interface, it should do so by exposing STL-style iterators. One reason for doing this is that these iterators may be used to pass the data to custom or STL algorithms. Another, equally valid reason is ease of use and uniformity of style. As an example, consider the time series class that lies at the heart of every financial analytics application. This class represents the total historical return data of a financial instrument. The interface of this class tends to be on the fat side, and its internals are quite complex. At its core, however, is a simple sequence of doubles, typically implemented as an STL vector, or, if it is legacy code, as a C-style dynamically allocated array. In either case, access to the raw numbers is most conveniently provided through the use of iterators. Here, it is clear that the iterators will be passed to algorithms, e.g., in order to calculate statistics such as compound return or standard deviation.
Another example is a class that represents a path name. If it is expected that clients will want to iterate through the components of the path, it is convenient to do so using iterators. In this case, it is rather unlikely that the iterators will be passed to an algorithm. Using them is simply a matter of convenience, and also a way of increasing the readability and maintainability of the code through uniformity of style: when iterating, use iterators.
All these user-defined iterators have one thing in common with the iterators that the STL containers expose: they are essentially pointers. They refer to a data item that exists in a certain memory location and is part of a range of data items. Moreover, they know how to get to the next item in that sequence, and possibly also the previous one. The only possible difference between such an iterator and an actual pointer is that operations such as dereferencing or advancing may involve actions like retrieving the data within a node, or stepping from one node to the next. However, the STL would not be a very good example of generic programming if there were anything that required iterators to resemble pointers in this way. The requirements on iterators are, of course, much weaker than that. For a complete discussion of these requirements, see e.g. Chapter 7 of Matt Austern's book ([1]). In essence, all one has to observe when writing an iterator class is that, depending on the category that the iterator will belong to, certain operators such as dereferencing and incrementing must be implemented, and, again depending on the iterator category, certain plausibility conditions have to be met. For example, if you take a random access iterator that is not at its end position, derefence it, increment it, decrement it, and dereference it again, the two dereferenced values must be equal under operator==(). It is clear that none of this places any restrictions on the origin of the data that the iterator retrieves. Interestingly, at the very beginning of his book on the STL ([1], p.4), Matt Austern gives an example of an iterator that gathers data from a place other than a range in memory. His iterator line_iterator retrieves lines from an input stream. The operator++() reads the next line and stores it, and the operator*() returns that stored line.
The next step on our path to generic programming enlightenment was the realization that such "non-pointer-like" iterators came in handy in many situations. In fact, in some parts of our software, they are now the rule rather than the exception. To see examples, consider an application that crunches numbers and then presents the results to the user in charts such as lines, scatter plots, bar charts, and so on. When the charting code draws these charts, it must essentially iterate through sequences of numbers and use them as coordinates in the appropriate manner. If you subscribe to the STL way of handling sequential data, you will of course let the number cruncher store its results in STL containers. The charting code retrieves these results through iterators: when iterating, use iterators. If the numbers that are stored represent the result of lengthy calculations, all is well. Now suppose the number cruncher has already stored two equally long sequences of numbers, and you need to expose to the client a third sequence representing the pointwise difference between these two sequences. (The excess return of your favorite mutual fund over the S&P500 comes to mind.) The naive way to do this is to store the sequence of differences in a third container and expose iterators to this container. It is clear that this is a horrible thing to do in terms of time vs. space trade-off. Taking the difference between two doubles is an operation of almost negligible complexity. Of course, we want to calculate this difference on demand rather than storing the entire sequence of differences. Do we have to abandon the STL iterator idiom to accommodate our efficiency requirements? Of course not, because an iterator does not have to iterate through an actual, physical range of data. It can gather or generate its data on the fly. For the particular purpose of the difference of two existing sequences, it is quite easy to see how to write an appropriate iterator class. This class holds two iterators, one into each of the two ranges. Operations such as advancing the iterator are implemented by performing the respective operation on both iterators. Dereferencing the iterator returns the difference between the dereferenced values of the two iterators. There are of course some immediate questions as to the kind of iterator we obtain here: const or non-const, what category? We will address these issues shortly. For now, we have one more step to climb on the stairway to generic programming heaven. If we were to write a custom iterator from scratch for every situation such as the one described above, we would be missing a level of genericity. It is possible to identify several commonly occurring concepts and implement them generically as class templates.
We will present five different custom iterator concepts here: combining iterators, processing iterators, dereferencing iterators, iterators to members, and generating iterators. Needless to say, we do not claim that these are comprehensive in any way. They are all based on class templates that were originally developed in the trenches as the need arose while working toward deadlines. One purpose of this article is to take a step back and apply some finishing strokes to get the genericity and the STL compliance right. The reader should not view these concepts as the ultimate solution to the problem of finding generic custom iterators. Rather, they should serve as an inspiration to be open-minded and creative about iterators, and more generally, as a reminder of rule number one when working with the STL: "Think Generic."
There are several design questions to be addressed. First of all, should we require that the individual iterators held by the combining iterator are all of the same type? Obviously, such a requirement places a restriction on the generality of the concept. On the other hand, having this requirement allows us to hold the member iterators in a collection rather than in individual member variables. Thus, we can have one class that allows the number of member iterators to be specified at runtime, upon construction. To cover the more general case, where the individual iterators can have different types, we would have to write one combining iterator class with two member iterators, another one with three member iterators, and so on (unless, of course, we require the member iterators to be derived from a common base class, clearly a no-no in the world of STL iterators). In view of all this, it is clear that there is no easy answer to this design question. We have opted for the requirement that all member iterators must have the same type, simply because that was good enough for our needs. It will not be good enough for everybody's needs. (We have not tried to apply template-metaprogramming techniques in the design of the combining iterator. Using these techniques may result in a more general and more widely applicable solution.)
The second design question is whether we should make provisions for the combining iterator to be a non-const iterator. Whenever we have used a combining iterator, the point was to gather data from different places, process it through a functional, and return a value. Theoretically, one could conceive of an iterator that simultaneously modifies data in several places through several iterators. However, we have never seen a situation where it would make sense to use a combining iterator for that purpose. In our experience, combining iterators are hunters and gatherers whose job it is to get data, not to set it. Therefore, our combining iterators are meant to be const iterators. This is reflected by the typedefs inside our combining iterator and by the result type of its operator*():
template<
typename _It, // type of member iterators
typename _Func // type of functional
>
class combining_iterator
{
public:
typedef typename _Func::result_type value_type;
typedef const typename _Func::result_type* pointer;
typedef const typename _Func::result_type& reference;
// ...
value_type operator*() const;
// ...
};
As you can see, we let the return value of the combining iterator's
operator*() be the result type of the functional
that the combining iterator uses. The functional, in turn, is forced to
return its result by value and not by reference. If you use a functional
that returns a reference, you get a compile-time error from the reference typedef.
Thereby, we force the return value of operator*()
to be a non-lvalue, and hence our combining iterator to be a const iterator. Normally,
operator*() of an iterator
returns the iterator's reference type. For a const iterator, that reference type is
a const reference. The combining iterator is one of those rare cases where the
appropriate return type for operator*() is the
iterator's value type. As we said before, we do not see this as a real restriction.
It has the advantage that we now know how to properly typedef the combining
iterator's value_type,
pointer, and reference.
The third question is, what is the iterator category of the combining iterator? The short answer is, it is the same as the category of the member iterators. That is what we set as the default by placing an appropriate typedef inside the combining iterator class. The catch is that this is true only if the functional that gets applied upon dereferencing has no state, i.e., is a function that deterministically returns equal values for equal arguments. If the functional holds state, then it is entirely possible that the member iterators of the combining iterator are random access iterators, and yet only one simple pass through the data is allowed, thus downgrading the combining iterator to an input iterator. Obviously, it must be the responsibility of the client to set the iterator category correctly in that case. This can be done by providing a specialization or partial specialization, as the case may be, of the STL's iterator_traits for the combining iterator in question. With the basic design issues settled, we may now look at the complete implementation of the combining iterator class template:
template<
typename _It, // type of member iterators
typename _Func // type of functional
>
class combining_iterator
{
public:
typedef typename
std::iterator_traits<_It>::iterator_category
iterator_category;
typedef typename _Func::result_type value_type;
typedef typename
std::iterator_traits<_It>::difference_type
difference_type;
typedef const typename _Func::result_type* pointer;
typedef const typename _Func::result_type& reference;
// Construct an uninitialized combining iterator.
combining_iterator(){}
// Construct a combining iterator from a collection of
// iterators.
template
combining_iterator(
_IteratorCollectionIterator it1,
_IteratorCollectionIterator it2,
_Func(func)
) :
m_vect_its(it1, it2), m_func(func) {}
// The operators * and [] apply the functional to the
// collection of values of the embedded iterators.
value_type operator*() const;
value_type operator[](difference_type n) const;
// All other operators behave the standard way.
combining_iterator& operator++();
const combining_iterator operator++(int);
combining_iterator& operator--();
const combining_iterator operator--(int);
combining_iterator& operator+=(difference_type n);
combining_iterator operator+(difference_type n) const;
combining_iterator& operator-=(difference_type n);
combining_iterator operator-(difference_type n) const;
difference_type operator-(
const combining_iterator& rhs
) const;
bool operator==(
const combining_iterator<_It, _Func>& rhs
) const
{ return m_vect_its == rhs.m_vect_its; }
bool operator!=(
const combining_iterator<_It, _Func>& rhs
) const
{ return m_vect_its != rhs.m_vect_its; }
private:
std::vector<_It> m_vect_its;
_Func m_func;
} ;
template
inline combining_iterator<_It, _Func>::value_type
combining_iterator<_It, _Func>::operator*() const
{ return m_func(m_vect_its.begin(), m_vect_its.end()); }
template
inline combining_iterator<_It, _Func>::value_type
combining_iterator<_It, _Func>::operator[](
difference_type n
) const
{ return *(*this + n); }
template
inline combining_iterator<_It, _Func>&
combining_iterator<_It, _Func>::operator++()
{
std::vector<_It>::iterator it = m_vect_its.begin();
while( it != m_vect_its.end() ) { ++*it; ++it; }
return *this;
}
template
inline const combining_iterator<_It, _Func>
combining_iterator<_It, _Func>::operator++(int)
{
combining_iterator<_It, _Func> tmp = *this;
++*this;
return tmp;
}
template
inline combining_iterator<_It, _Func>&
combining_iterator<_It, _Func>::operator--()
{
std::vector<_It>::iterator it = m_vect_its.begin();
while( it != m_vect_its.end() ) { --*it; ++it; }
return *this;
}
template
inline const combining_iterator<_It, _Func>
combining_iterator<_It, _Func>::operator--(int)
{
combining_iterator<_It, _Func> tmp = *this;
--*this;
return tmp;
}
template
inline combining_iterator<_It, _Func>&
combining_iterator<_It,
_Func>::operator+=(difference_type n)
{
std::vector<_It>::iterator it = m_vect_its.begin();
while( it != m_vect_its.end() ) { *it += n; ++it; }
return *this;
}
template
inline combining_iterator<_It, _Func>
combining_iterator<_It, _Func>::operator+(
difference_type n
) const
{
combining_iterator<_It, _Func> Tmp(*this);
Tmp += n;
return Tmp;
}
template
inline combining_iterator<_It, _Func>&
combining_iterator<_It, _Func>::operator-
=(difference_type n)
{
std::vector<_It>::iterator it = m_vect_its.begin();
while( it != m_vect_its.end() ) { *it -= n; ++it; }
return *this;
}
template
inline combining_iterator<_It, _Func>
combining_iterator<_It, _Func>::operator-(
difference_type n
) const
{
combining_iterator<_It, _Func> Tmp(*this);
Tmp -= n;
return Tmp;
}
template
inline combining_iterator<_It, _Func>::difference_type
combining_iterator<_It, _Func>::operator-(
const combining_iterator<_It, _Func>& rhs
) const
{
if(0 < m_vect_its.size() && 0 < rhs.m_vect_its.size())
return m_vect_its[0] - rhs.m_vect_its[0];
else
return 0;
}
template
struct combining_iterator_traits
{
typedef typename
std::vector<_It>::const_iterator functional_arg_type;
};
There are a few points about this code that merit discussion. First of all, notice that we
have one single class that implements all operators for moving the iterator and for
taking differences. If the template argument _It is
anything less than a random access iterator, then some of these operator definitions
do not compile, because the type _It does not provide
them. There is not really a problem with that, because member functions that
are never called should not be compiled. Of course, we have just now entered the
shady realm of compiler dependency hell, and there is no guarantee as to what
your compiler will do. Also, there is one serious restriction here: you cannot
do an explicit template instantiation with our combining iterator class template
unless the underlying iterator type is a random access iterator. That is because
an explicit template instantiation will necessarily try to compile all member
functions of the class, some of which are not compilable if
the underlying iterator type is not a random access iterator.
Note that the type of the functional that the combining iterator uses must provide its return type through the typedef result_type. For a functional with less than three arguments, this should be done by deriving from std::unary_function or std::binary_function. Otherwise, you must explicitly put a line such as
typedef int result_type;into the declaration of your functional.
Another thing to note about the functional is that its argument type is somewhat unintuitive. Conceptually, the functional operates on the current values of the member iterators of the combining iterator. Technically, when the functional is called inside the combining iterator's operator*(), it gets passed two iterators. These two iterators delimit a range that contains the member iterators at their current position. Think of this as an STL-ish way of passing arguments to a functional: rather than passing an argument list, you give a range consisting of iterators, and the actual argument list is obtained by iterating over this range of iterators and dereferencing each.
It is time for an example. Let us use the combining iterator class to write the difference operator that we discussed before. Suppose we have two vectors of doubles of equal length:
std::vectorWe wish to produce an iterator that can be used to parallel-iterate through these two vectors and produce their difference. First, we need the functional. Think generic: when writing the functional, we should not specify the exact nature of our two ranges of doubles. Therefore, we let the type of iterator that is suitable for use with these ranges be a template argument to our functional. Also, instead of just doubles, we should allow any type for which subtraction is defined:vect_of_doubles_1(42); std::vector vect_of_doubles_2(42); // Do something that sets values in vect_of_doubles_1 // and vect_of_doubles_2
templateAs you can see, the type of the arguments passed to the functional is provided by the helper type combining_iterator_traits for convenience. In order to write the functional, you have to understand what that type is: it is an iterator into the collection of member iterators of the combining iterator. Dereferencing such an iterator once takes you to a member iterator, dereferencing it twice takes you to the current value of a member iterator. Our combining iterator class guarantees that functional_arg_type is always a random access iterator. Therefore, the expression **(it1 + 1) in our functional is fine.class func_diff : public std::binary_function< combining_iterator_traits<_It>::functional_arg_type, combining_iterator_traits<_It>::functional_arg_type, _T> { public: _T operator()( combining_iterator_traits<_It>::functional_arg_type it1, combining_iterator_traits<_It>::functional_arg_type it2 ) const { return **it1 - **(it1 + 1); } };
Besides writing the functional, the only other thing about using combining iterators that is somewhat less than intuitive is constructing a combining iterator. What you must do is throw the prospective member iterators of your combining iterator into a collection, then pass to the constructor iterators to the begin and end position of that collection. Here is the code to print out the sequence of differences between our two vectors of doubles: