-From: Ross Smith <ross.s@ihug.co.nz>
-Newsgroups: comp.lang.c++.moderated
-Subject: Writing iterators (was: Re: Non-template functions that take iterators)
-Date: 28 Jun 2001 12:07:10 -0400
-
-Andre Majorel wrote:
-> Any pointers handy on "writing STL-compatible iterators for
-> dummies ?"
-
-I'll give it a try...
-
-The usual situation requiring user-defined iterators is that you have
-a type that bears some resemblance to an STL container, and you want
-to provide iterators so it can be used with STL algorithms. You need
-to ask three questions:
-
-First, is this simply a wrapper for an underlying collection of
-objects that's held somewhere as a real STL container, or is it a
-"virtual container" for which iteration is (under the hood) more
-complicated than simply incrementing some underlying iterator (or
-pointer or index or whatever)? In the former case you can frequently
-get away with making your container's iterators simply typedefs for
-those of the underlying container; your begin() function would call
-member_container.begin(), and so on.
-
-Second, do you only need read-only iterators, or do you need separate
-read-only (const) and read-write (non-const) iterators?
-
-Third, which kind of iterator (input, output, forward, bidirectional,
-or random access) is appropriate? If you're familiar with the
-properties of the iterator types (if not, visit
-<a href="http://www.sgi.com/tech/stl/">http://www.sgi.com/tech/stl/</a>), the appropriate choice should be
-obvious from the semantics of the container.
-
-I'll start with forward iterators, as the simplest case that's likely
-to come up in normal code. Input and output iterators have some odd
-properties and rarely need to be implemented in user code; I'll leave
-them out of discussion. Bidirectional and random access iterators are
-covered below.
-
-The exact behaviour of a forward iterator is spelled out in the
-Standard in terms of a set of expressions with specified behaviour,
-rather than a set of member functions, which leaves some leeway in how
-you actually implement it. Typically it looks something like this
-(I'll start with the const-iterator-only situation):
-
- #include <iterator>
-
- class container {
- public:
- typedef something_or_other value_type;
- class const_iterator:
- public std::iterator<std::forward_iterator_tag, value_type> {
- friend class container;
- public:
- const value_type& operator*() const;
- const value_type* operator->() const;
- const_iterator& operator++();
- const_iterator operator++(int);
- friend bool operator==(const_iterator lhs,
- const_iterator rhs);
- friend bool operator!=(const_iterator lhs,
- const_iterator rhs);
- private:
- //...
- };
- //...
- };
-
-An iterator should always be derived from an instantiation of the
-std::iterator template. The iterator's life cycle functions
-(constructors, destructor, and assignment operator) aren't declared
-here; in most cases the compiler-generated ones are sufficient. The
-container needs to be a friend of the iterator so that the container's
-begin() and end() functions can fill in the iterator's private members
-with the appropriate values.
-
-<i>[Chris's Note: I prefer to not make my iterators friends. Instead, two
-ctor's are provided for the iterator class: one to start at the end of the
-container, and one at the beginning. Typically this is done by providing
-two constructors with different signatures.]</i>
-
-There are normally only three member functions that need nontrivial
-implementations; the rest are just boilerplate.
-
- const container::value_type&
- container::const_iterator::operator*() const {
- // find the element and return a reference to it
- }
-
- const container::value_type*
- container::const_iterator::operator->() const {
- return &**this;
- }
-
-If there's an underlying real container, operator*() can just return a
-reference to the appropriate element. If there's no actual container
-and the elements need to be generated on the fly -- what I think of as
-a "virtual container" -- things get a bit more complicated; you'll
-probably need to give the iterator a value_type member object, and
-fill it in when you need to. This might be done as part of the
-increment operator (below), or if the operation is nontrivial, you
-might choose the "lazy" approach and only generate the actual value
-when one of the dereferencing operators is called.
-
-The operator->() function is just boilerplate around a call to
-operator*().
-
- container::const_iterator&
- container::const_iterator::operator++() {
- // the incrementing logic goes here
- return *this;
- }
-
- container::const_iterator
- container::const_iterator::operator++(int) {
- const_iterator old(*this);
- ++*this;
- return old;
- }
-
-Again, the incrementing logic will usually be trivial if there's a
-real container involved, more complicated if you're working with a
-virtual container. In particular, watch out for what happens when you
-increment past the last valid item -- this needs to produce an
-iterator that will compare equal to container.end(), and making this
-work is often nontrivial for virtual containers.
-
-The post-increment function is just boilerplate again (and
-incidentally makes it obvious why all the experts recommend using
-pre-increment wherever possible).
-
- bool operator==(container::const_iterator lhs,
- container::const_iterator rhs) {
- // equality comparison goes here
- }
-
- bool operator!=(container::const_iterator lhs,
- container::const_iterator rhs) {
- return !(lhs == rhs);
- }
-
-For a real container, the equality comparison will usually just
-compare the underlying iterators (or pointers or indices or whatever).
-The semantics of comparisons for virtual container iterators are often
-tricky. Remember that iterator comparison only needs to be defined for
-iterators into the same container, so you can often simplify things by
-taking for granted that lhs and rhs both point into the same container
-object. Again, the second function is just boilerplate.
-
-It's a matter of taste whether iterator arguments are passed by value
-or reference; I've shown tham passed by value to reduce clutter, but
-if the iterator contains several data members, passing by reference
-may be better.
-
-That convers the const-iterator-only situation. When we need separate
-const and mutable iterators, one small complication is added beyond
-the simple addition of a second class.
-
- class container {
- public:
- typedef something_or_other value_type;
- class const_iterator;
- class iterator:
- public std::iterator<std::forward_iterator_tag, value_type> {
- friend class container;
- friend class container::const_iterator;
- public:
- value_type& operator*() const;
- value_type* operator->() const;
- iterator& operator++();
- iterator operator++(int);
- friend bool operator==(iterator lhs, iterator rhs);
- friend bool operator!=(iterator lhs, iterator rhs);
- private:
- //...
- };
- class const_iterator:
- public std::iterator<std::forward_iterator_tag, value_type> {
- friend class container;
- public:
- const_iterator();
- const_iterator(const iterator& i);
- const value_type& operator*() const;
- const value_type* operator->() const;
- const_iterator& operator++();
- const_iterator operator++(int);
- friend bool operator==(const_iterator lhs,
- const_iterator rhs);
- friend bool operator!=(const_iterator lhs,
- const_iterator rhs);
- private:
- //...
- };
- //...
- };
-
-There needs to be a conversion from iterator to const_iterator (so
-that mixed-type operations, such as comparison between an iterator and
-a const_iterator, will work). This is done here by giving
-const_iterator a conversion constructor from iterator (equivalently,
-we could have given iterator an operator const_iterator()), which
-requires const_iterator to be a friend of iterator, so it can copy its
-data members. (It also requires the addition of an explicit default
-constructor to const_iterator, since the existence of another
-user-defined constructor inhibits the compiler-defined one.)
-
-Bidirectional iterators add just two member functions to forward
-iterators:
-
- class iterator:
- public std::iterator<std::bidirectional_iterator_tag, value_type> {
- public:
- //...
- iterator& operator--();
- iterator operator--(int);
- //...
- };
-
-I won't detail the implementations, they're obvious variations on
-operator++().
-
-Random access iterators add several more member and friend functions:
-
- class iterator:
- public std::iterator<std::random_access_iterator_tag, value_type> {
- public:
- //...
- iterator& operator+=(difference_type rhs);
- iterator& operator-=(difference_type rhs);
- friend iterator operator+(iterator lhs, difference_type rhs);
- friend iterator operator+(difference_type lhs, iterator rhs);
- friend iterator operator-(iterator lhs, difference_type rhs);
- friend difference_type operator-(iterator lhs, iterator rhs);
- friend bool operator<(iterator lhs, iterator rhs);
- friend bool operator>(iterator lhs, iterator rhs);
- friend bool operator<=(iterator lhs, iterator rhs);
- friend bool operator>=(iterator lhs, iterator rhs);
- //...
- };
-
- container::iterator&
- container::iterator::operator+=(container::difference_type rhs) {
- // add rhs to iterator position
- return *this;
- }
-
- container::iterator&
- container::iterator::operator-=(container::difference_type rhs) {
- // subtract rhs from iterator position
- return *this;
- }
-
- container::iterator operator+(container::iterator lhs,
- container::difference_type rhs) {
- return iterator(lhs) += rhs;
- }
-
- container::iterator operator+(container::difference_type lhs,
- container::iterator rhs) {
- return iterator(rhs) += lhs;
- }
-
- container::iterator operator-(container::iterator lhs,
- container::difference_type rhs) {
- return iterator(lhs) -= rhs;
- }
-
- container::difference_type operator-(container::iterator lhs,
- container::iterator rhs) {
- // calculate distance between iterators
- }
-
- bool operator<(container::iterator lhs, container::iterator rhs) {
- // perform less-than comparison
- }
-
- bool operator>(container::iterator lhs, container::iterator rhs) {
- return rhs < lhs;
- }
-
- bool operator<=(container::iterator lhs, container::iterator rhs) {
- return !(rhs < lhs);
- }
-
- bool operator>=(container::iterator lhs, container::iterator rhs) {
- return !(lhs < rhs);
- }
-
-Four of the functions (operator+=(), operator-=(), the second
-operator-(), and operator<()) are nontrivial; the rest are
-boilerplate.
-
-One feature of the above code that some experts may disapprove of is
-the declaration of all the free functions as friends, when in fact
-only a few of them need direct access to the iterator's private data.
-I originally got into the habit of doing this simply to keep the
-declarations together; declaring some functions inside the class and
-some outside seemed awkward. Since then, though, I've been told that
-there's a subtle difference in the way name lookup works for functions
-declared inside a class (as friends) and outside, so keeping them
-together in the class is probably a good idea for practical as well as
-aesthetic reasons.
-
-I hope all this is some help to anyone who needs to write their own
-STL-like containers and iterators.
-
---
-Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand