C++ Iterators and inheritance

Question

Have a quick question about what would be the best way to implement iterators in the following:

Say I have a templated base class 'List' and two subclasses "ListImpl1" and "ListImpl2". The basic requirement of the base class is to be iterable i.e. I can do:

for(List<T>::iterator it = list->begin(); it != list->end(); it++){
   ...
}

I also want to allow iterator addition e.g.:

for(List<T>::iterator it = list->begin()+5; it != list->end(); it++){
   ...
}

So the problem is that the implementation of the iterator for ListImpl1 will be different to that for ListImpl2. I got around this by using a wrapper ListIterator containing a pointer to a ListIteratorImpl with subclasses ListIteratorImpl2 and ListIteratorImpl2, but it's all getting pretty messy, especially when you need to implement operator+ in the ListIterator.

Any thoughts on a better design to get around these issues?

Answer 1

So the problem is that the implementation of the iterator for ListImpl1 will be different to that for ListImpl2. I got around this by using a wrapper ListIterator containing a pointer to a ListIteratorImpl with subclasses ListIteratorImpl2 and ListIteratorImpl2, but it's all getting pretty messy, especially when you need to implement operator+ in the ListIterator.

This design is fine IMHO, I can't see anything messy about it. Except for equality and subtraction, operations of the iterator can be implemented by virtual function pretty easily, so you'll have something like

class ListIteratorInterface // abstract
{
protected:
  virtual Data& operator*()=0;
  // and other operations
};
class ListIteratorA;
class ListIteratorB; // implementation of the above
class ListIterator
{
  ListIteratorInterface* impl_;
public:
  // when you create this, allocate impl_ on the heap
  // operations, forward anything to impl_
};

Answer 2

You could store operator+ as a private virtual method in the base class, and have the iterator call that.

Alternatively, you could consider statically polymorphic list classes, rather than runtime polymorphism.

Answer 3

If you can get away with making List<T>::iterator non-virtual, then delegating the virtualness off add to List makes things simple:

template<typename T>
class List
{
    virtual void add_assign(iterator& left, int right) = 0;

public:
    class iterator
    {
        const List* list;
        const T* item;
    public:
        iterator(const List* list, const T* item) : list(list), item(item) {}

        iterator& operator +=(int right)
        {
            list->add_assign(*this, right);
            return *this;
        }
        static iterator operator +(iterator const& left, int right)
        {
            iterator result = left;
            result += right;
            return result;
        }
    };

    virtual iterator begin() const = 0;
    virtual iterator end() const = 0;
};

Otherwise (if the iterators need to store significantly different data, for example), then you have to do the regular, boring pointer-to-implementation to get your virtualness:

template<typename T>
class List
{
    class ItImpl
    {
        virtual ItImpl* clone() = 0;
        virtual void increment() = 0;
        virtual void add(int right) = 0;
    };
public:
    class iterator
    {
        ItImpl* impl;
    public:
        // Boring memory management stuff.
        iterator() : impl() {}
        iterator(ItImpl* impl) : impl(impl) {}
        iterator(iterator const& right) : impl(right.impl->clone()) {}
        ~iterator() { delete impl; }
        iterator& operator=(iterator const& right)
        {
            delete impl;
            impl = right.impl->clone();
            return *this;
        }

        // forward operators to virtual calls through impl.
        iterator& operator+=(int right)
        {
            impl->add(right);
            return *this;
        }
        iterator& operator++()
        {
            impl->increment();
            return *this;
        }
    };
};

template<typename T>
static List<T>::iterator operator+(List<T>::iterator const& left, int right)
{
    List<T>::iterator result = left;
    result += right;
    return result;
}

template<typename T>
class MagicList : public List<T>
{
    class MagicItImpl : public ItImpl
    {
        const MagicList* list;
        const magic* the_magic;
        // implement ...
    };
public:
    iterator begin() const { return iterator(new MagicItImpl(this, begin_magic)); }
    iterator end() const { return iterator(new MagicItImpl(this, end_magic)); }
};

Answer 4

Say I have a templated base class 'List' and two subclasses "ListImpl1" and "ListImpl2"

What exactly do you gain by using inheritance here?

Answer 5

There is something very important among iterators, called Iterator Category:

• InputIterator
• OutputIterator
• ForwardIterator
• BidirectionalIterator
• RandomAccessIterator

Each category define an exact set of operations that are supported, efficiently, by the iterator.

Here, it seems you wish to turn down that powerful identification mechanism to create some kind of bastard category in which the operations are all present, but no guarantee is made on their efficiency.

I think your design smells.