Iterator Inheritance and inheriting *this

Question

How to write a base class and several derived classes of iterator?

Does the iterator have to return itself (*this)?

So far, I use typename X and static_cast<X&>(*this) to allow the derived class to inherit a function that return itself from the base class.

This looks ugly. Is there a better way?

Simplified Code:

#include <iterator>
#include <iostream>
template <typename T, typename X>
class BaseIterator : public std::iterator<std::input_iterator_tag, T> {
    //Not intended to be used directly.
    private:
        T* p;
    protected:
        virtual void increment(void)=0;
        virtual T* stride_index(int index)=0;
    public:
        virtual ~BaseIterator(){} //virtual destructor.
        X operator++(int) { //takes a dummy int argument
            X tmp(static_cast<X&>(*this) );
            increment();
            return tmp;
        }
        bool operator==(const X & rhs) { return p==rhs.p; }
} ;
template <typename T>
class ContiguousIterator : public BaseIterator<T, ContiguousIterator<T> > {
    private:
        T* p;
    protected:
        inline void increment(void) {++p;}
        inline T* stride_index(int index){return p + index;}
    public:
        virtual ~ContiguousIterator(){} //destructor.
        ContiguousIterator(T* x) :p(x) {}
        ContiguousIterator(const ContiguousIterator<T> & mit) : p(mit.p) {}
} ;

int main(void){
    int i[]={0,1,2,3,4,5};
    ContiguousIterator<int> itbegin(i);
    ContiguousIterator<int> it(i);
    it++;
    std::cout << "result: " << (it == itbegin) << std::endl;
}

The alternative is to forget about using inheritance to write less code. Just copy and paste the function that return *this to the derived classes.

That alternative seems increasingly acceptable to me ...

Answer 1

Generally, virtual is a lot of overhead for something like iterators which ought to be lightweight. The usual way to go is CRTP. Which is a little tricky, but looks like this:

template <typename T, typename X>
class BaseIterator : public std::iterator<std::input_iterator_tag, T> {
    protected:
        T* p;
        X* self() {return static_cast<X*>(this);}
        const X* self() const {return static_cast<const X*>(this);}
        BaseIterator(T* x) :p(x) {}
    public:
        X operator++(int) { //takes a dummy int argument
            X tmp(*self());
            self()->increment();
            return tmp;
        }
        bool operator==(const X & rhs) const { return p==rhs.p; }
} ;

The base usually takes the derived type, plus whatever it needs for function signatures as template parameters. Then you add two self() functions, which give you the derived type, which means you don't actually need virtual. Everything is trivially inlined by the compiler. (Note I've also given it a sane constructor, and made operator== const.

template <typename T>
class ContiguousIterator : public BaseIterator<T, ContiguousIterator<T> > {
    public:
        typedef BaseIterator<T, ContiguousIterator<T> > parent;
        void increment(void) {++(this->p);}
        T* stride_index(int index) const {return this->p + index;}
    public:
        virtual ~ContiguousIterator(){} //destructor.
        ContiguousIterator(T* x) :parent(x) {}
        ContiguousIterator(const ContiguousIterator<T> & mit) : parent(mit.p) {}
} ;

Then the derived type simply inherits as normal, except you have to use this-> to access the member, since the parent is a template. See it working here: http://coliru.stacked-crooked.com/a/81182d994c7edea7

This produces a highly efficient iterator, with no overhead. I believe this technique is used quite heavily in Boost's iterator library: http://www.boost.org/doc/libs/1_59_0/libs/iterator/doc/#new-style-iterators