How to correctly implement custom iterators and const_iterators ?

Question

I have a custom container class for which I'd like to write the iterator and const_iterator classes.

I never did this before and I failed to find an appropriate how-to. What are the guidelines regarding iterator creation, and what should I be aware of ?

I'd also like to avoid code duplication (I feel that const_iterator and iterator share many things; should one subclass the other ?).

Thanks.

Foot note: I'm pretty sure Boost has something to ease this but I can't use it here, for many stupid reasons.

Answer 1

I don't know if Boost has anything that would help.

My preferred pattern is simple: take a template argument which is equal to value_type, either const qualified or not. If necessary, also a node type. Then, well, everything kind of falls into place.

Just remember to parameterize (template-ize) everything that needs to be, including the copy constructor and operator==. For the most part, the semantics of const will create correct behavior.

template< class ValueType, class NodeType >
struct my_iterator
 : std::iterator< std::bidirectional_iterator_tag, T > {
    ValueType &operator*() { return cur->payload; }

    template< class VT2, class NT2 >
    friend bool operator==
        ( my_iterator const &lhs, my_iterator< VT2, NT2 > const &rhs );

    // etc.

private:
    NodeType *cur;

    friend class my_container;
    my_iterator( NodeType * ); // private constructor for begin, end
};

typedef my_iterator< T, my_node< T > > iterator;
typedef my_iterator< T const, my_node< T > const > const_iterator;

Answer 2

They often forget that iterator must convert to const_iterator but not the other way around. Here is a way to do that:

template<class T, class Tag = void>
class IntrusiveSlistIterator
   : public std::iterator<std::forward_iterator_tag, T>
{
private:
    typedef SlistNode<Tag> Node;
    Node* node_;

public:
    IntrusiveSlistIterator(Node* node);

    T& operator*() const;
    T* operator->() const;

    IntrusiveSlistIterator& operator++();
    IntrusiveSlistIterator operator++(int);

    bool operator==(IntrusiveSlistIterator b) const;
    bool operator!=(IntrusiveSlistIterator b) const;

    // one way conversion: iterator -> const_iterator
    operator IntrusiveSlistIterator<T const, Tag>() const;
};

In the above notice how IntrusiveSlistIterator<T> converts to IntrusiveSlistIterator<T const>. If T is already const this conversion never gets used.

Answer 3

Boost has something to help: the Boost.Iterator library.

More precisely this page: boost::iterator_adaptor.

What's very interesting is the Tutorial Example which shows a complete implementation, from scratch, for a custom type.

The main point, as has been cited already, is to use a single template implementation and typedef it.