How to provide STL like iterators for my collection class?

Question

Possible Duplicate:
How to correctly implement custom iterators and const_iterators ?

I would really like to provide a STL like iterator for a entity collection class I've got. As a bonus, I'd like it if the iterator can be easily reusable for other collection classes I got. The problem is I once tried to wade through the STL but it was too complex for me then. Any advice on how to do this? It need not be so complex as STL iterators, but I'd like it if I can just say MyCollection::iterator it = o_MyCollection.begin() and so on. :)

As a second question, what is the basic requirement for this iterator if I am to pass it to a usual algorithm like for_each?

Answer 1

Assuming that your collection is a list indexed by an integer, this iterator class that I use in a custom STL collection might help you. It uses the curiously recurring template pattern. It's not 100% tested but works in my code.

// common_safe_iterator is instantiated to produce both const_iterator and
// iterator types. It called "safe" because it is not necessarily invalidated
// by changes to the collection size, and it calls at() on the target
// collection, which is supposed to throw an exception if the index is
// out-of-range, instead of calling [] which does not.
template<class base>
class common_safe_iterator : public base {
protected:
    // base must contain the following 5 typedefs
    typedef typename base::reference reference;
    typedef typename base::pointer pointer;
    typedef typename base::vector_t vector_t;
    typedef typename base::const_iterator_t const_iterator_t;
    typedef typename base::iterator_t iterator_t;
    vector_t* _vec;
    size_type _pos;
public:
    typedef common_safe_iterator<base> self;
    friend const_iterator_t;

    common_safe_iterator(vector_t* vec, size_type pos) : _vec(vec), _pos(pos) { }
    common_safe_iterator(const iterator_t& copy) : _vec(copy._vec), _pos(copy._pos) { }

    reference operator*() const { return _vec->at(_pos); }
    pointer operator->() const { return &_vec->at(_pos); }

    self& operator++() // prefix ++
        { ++_pos; return *this; }
    self& operator--() // prefix --
        { --_pos; return *this; }
    self& operator+=(int amt) 
        { _pos += amt; return *this; }
    bool operator==(const self& x) const
        { return (x._vec == _vec) && (x._pos == _pos); }
    int operator-(const self& base) const
        { assert(base._vec == _vec); return _pos - base._pos; }
    // Returns true if the iterator can be dereferenced
    bool is_valid() const
        { return _vec != NULL && _pos < _vec->size(); }

    /////////////////////////////////////////////////////////
    // Operators that are defined in terms of other operators

    self operator++(int) // postfix ++
    {
        self tmp = *this; // copy ourselves
        ++*this;
        return tmp;
    }
    self operator--(int) // postfix --
    {
        self tmp = *this; // copy ourselves
        --*this;
        return tmp;
    }
    self& operator-=(int amt)
    {
        return *this += -amt;
    }
    bool operator!=(const self& x) const
    {
        return !(*this == x);
    }
    bool operator>(const self& x) const
    {
        return *this - x > 0;
    }
    bool operator>=(const self& x) const
    {
        return *this - x >= 0;
    }
    bool operator<(const self& x) const
    {
        return *this - x < 0;
    }
    bool operator<=(const self& x) const
    {
        return *this - x <= 0;
    }
    self operator+(int amt) const
    {
        self tmp = *this;
        return tmp += amt;
    }
    self operator-(int amt) const
    {
        self tmp = *this;
        return tmp -= amt;
    }
    reference operator[](int index) const
    {
        self tmp = *this;
        tmp += index;
        return *tmp;
    }
};

STL expects you to provide both a "const_iterator" and a non-const "iterator" class. To do this, write two base classes with 5 typedefs each. My collection class is named mini_vector_t, so I use the following base classes:

/// iterator and const_iterator differ only in these typedefs.
/// const_iterator_base is the base class of const_iterator, while
/// iterator_base is the base class of iterator; both iterator and
/// const_iterator are typedefs of common_safe_iterator.
struct iterator_base;
struct const_iterator_base
{
    typedef const typename mini_vector_t::value_type& reference;
    typedef const typename mini_vector_t::value_type* pointer;
    typedef const mini_vector_t vector_t;
    typedef common_safe_iterator<const_iterator_base> const_iterator_t;
    typedef common_safe_iterator<iterator_base> iterator_t;
};
struct iterator_base
{
    typedef typename mini_vector_t::value_type& reference;
    typedef typename mini_vector_t::value_type* pointer;
    typedef mini_vector_t vector_t;
    typedef common_safe_iterator<const_iterator_base> const_iterator_t;
    typedef common_safe_iterator<iterator_base> iterator_t;
};

Finally, your collection must contain typedefs for const_iterator and iterator:

typedef common_safe_iterator<const_iterator_base> const_iterator;
typedef common_safe_iterator<iterator_base> iterator;

If your collection wraps an array, then a simpler alternative to all this is to use T* as your iterator type, and const T* as your const_iterator type:

typedef T* iterator;
typedef const T* const_iterator;

Remember, the STL is designed so that pointers themselves are iterators.

I think you're supposed to do something extra to declare that your iterators are "random access", but I don't know what.