How can I implement various iterator categories in an elegant and efficient way?

Question

I'm implementing STL containers, for example, vector. What confused me is the implementation of iterators.

If I want to implement all iterator categories: input_iterator, output_iterator, forward_iterator, bidirectional_iterator and random_access_iterator.

How do I manage their inheritance relationships? I've read How to implement an STL-style iterator and avoid common pitfalls?-Mooing Duck's Answer

This is his example symbolic:

iterator {
    iterator(const iterator&);
    ~iterator();
    iterator& operator=(const iterator&);
    iterator& operator++(); //prefix increment
    reference operator*() const;
    friend void swap(iterator& lhs, iterator& rhs); //C++11 I think
};
input_iterator : public virtual iterator {
    iterator operator++(int); //postfix increment
    value_type operator*() const;
    pointer operator->() const;
    friend bool operator==(const iterator&, const iterator&);
    friend bool operator!=(const iterator&, const iterator&); 
};
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.
output_iterator : public virtual iterator {
    reference operator*() const;
    iterator operator++(int); //postfix increment
};
//dereferences may only be on the left side of an assignment
//once an input iterator has been dereferenced, it is 
//undefined to dereference one before that.
forward_iterator : input_iterator, output_iterator {
    forward_iterator();
};
//multiple passes allowed
bidirectional_iterator : forward_iterator {
    iterator& operator--(); //prefix increment
    iterator operator--(int); //postfix decrement
};

random_access_iterator : bidirectional_iterator {
    friend bool operator<(const iterator&, const iterator&);
    friend bool operator>(const iterator&, const iterator&);
    friend bool operator<=(const iterator&, const iterator&);
    friend bool operator>=(const iterator&, const iterator&);

    iterator& operator+=(size_type);
    friend iterator operator+(const iterator&, size_type);
    friend iterator operator+(size_type, const iterator&);
    iterator& operator-=(size_type);  
    friend iterator operator-(const iterator&, size_type);
    friend difference_type operator-(iterator, iterator);

    reference operator[](size_type) const;
};

But I found a problem: If I have an instance a from class random_access_iterator, I use the code random_access_iterator b = a + 1. This will cause compile error. Because a + 1's class is base iterator, not random_access_iterator.

So I don't think this is a reasonable solution.

Do I misunderstand it? Or please tell me an elegant and efficient way to implement it.

Thanks

@PaulMcKenzie: I've tried to read GCC's implementation, but it's a bit complex for me, I'm still trying to figure it out. But when I came across the implementation above, I'm impressed but not sure about its correctness. — Kevince Boole, Feb 03 '16 at 10:44

score 2 · Accepted Answer · answered Feb 03 '16 at 12:25

I think you should use CRTP (https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern). Like this:

template <typename T, typename ItT>
struct iiterator_t {
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    virtual iterator_type& operator=(const iterator_type&) = 0;
    virtual iterator_type& operator++() = 0;
    virtual reference operator*() const = 0;
};

template <typename T, typename ItT>
struct iterator_impl_t :  virtual public iiterator_t<T, ItT>{
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    iterator_type& operator=(const iterator_type &rhs)
    {
        p = static_cast<const iterator_impl_t&>(rhs).p;
        return dynamic_cast<iterator_type&>(*this);
    }

    iterator_type& operator++()
    {
        ++p;
        return dynamic_cast<iterator_type&>(*this);
    }

    reference operator*() const
    {
        return *p;
    }

private:
    pointer p;
};

template <typename T, typename ItT>
struct iinput_iterator_t : public virtual iiterator_t<T, ItT> {
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    virtual iterator_type operator++(int) = 0;
};


template <typename T, typename ItT>
struct input_iterator_impl_t :
    public virtual iinput_iterator_t<T, ItT>,
    public virtual iterator_impl_t<T, ItT>
{
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;

    typedef ItT iterator_type;

    iterator_type operator++(int)
    {
        iterator_type result(dynamic_cast<const iterator_type &>(*this));
        ++dynamic_cast<iterator_impl_t<T, ItT> &>(*this);
        return result;
    }
};


template <typename T>
struct iterator :
    public virtual iterator_impl_t<T, iterator<T> >
{
};


template <typename T>
struct input_iterator :
    public virtual input_iterator_impl_t<T, input_iterator<T>>
{
};

int main(int , char** )
{
    iterator<int> i;
    iterator<int> i2 = ++i;
    input_iterator<int> inpi;
    input_iterator<int> inpi2 = inpi++;
    return 0;
 }

Brian Rodriguez · Answer 2 · 2016-02-03T13:00:23.813

Iterator categories are nothing but empty structs that act as tags.

Once finished implementing the features of your iterator class, you add its information (like which category it belongs to) into a std::iterator_traits specialization. Here's an example:

namespace std {

template <typename T>
struct iterator_traits<my_iota_iterator<T>> {
    using value_type = T;
    using difference_type = T;
    using pointer = T const*;
    using reference = T const&;
    using iterator_category = std::random_access_iterator_tag; // !!
} /*struct iterator_traits*/;

} /*namespace std*/;

You can also choose to place these type aliases directly in the iterator class itself. Regardless, algorithms can now specialize upon the type of iterator_category and implement specific versions for specific categories.

How can I implement various iterator categories in an elegant and efficient way?

2 Answers2

Linked