Iterator over a container with indexing operation

Question

This is a random access iterator that stores an index and a reference to a container.

It iterates over any container with indexing operation.

It does not have copy assignment / move assignment operations. This is because I cannot re-assign the reference to a container to reference to another container. The iterator stores a reference instead of a pointer to the original container.

If the iterator stores a pointer instead of reference to the container, will that affect performance?

The index_iterator inherits from the const_index_iterator because I want implicit conversion from the non-const to const iterator even during template instantiation.

The code and google tests are also at: https://github.com/rzu512/algorithms

Thanks for reviewing this.

Code:

#ifndef ALGORITHMS_ITERATOR_H
#define ALGORITHMS_ITERATOR_H

#include <iterator>
#include <iostream>

/// \brief Random access const_iterator over a container with index operation
/// \note no copy assignment / move assignment.
template<typename A>
class const_index_iterator {
    typedef const_index_iterator<A> self_type;
public:
    typedef typename A::value_type value_type;
    typedef value_type& reference;
    typedef value_type* pointer;
    typedef typename A::difference_type difference_type;
    typedef std::random_access_iterator_tag iterator_category;

    const_index_iterator(const A& a, const typename A::size_type ix)
            : a_(a), ix_(ix) {
        // + 1 because of end().
        assert(ix_ < a_.size() + 1 && ix_ >= 0 && "Index is out of bounds.");
    }

    // Arithmetic
    self_type operator++() {
        ++ix_;
        check_ix();
        return *this;
    }

    self_type operator++(int dummy) { return operator++(); }

    self_type& operator+=(difference_type n) {
        ix_ += n;
        check_ix();
        return *this;
    }

    self_type operator--() {
        --ix_;
        check_ix();
        return *this;
    }

    self_type operator--(int dummy) { return operator--(); }

    self_type& operator-=(difference_type n) {
        return operator+=(-n);
    }

    friend const_index_iterator<A> operator+(const const_index_iterator<A>& a,
                                             const difference_type n) {
        return const_index_iterator<A>(a.a_, a.ix_ + n);
    }

    friend difference_type operator-(const const_index_iterator<A>& a,
                                     const const_index_iterator<A>& b) {
        return a.ix_ - b.ix_;
    }

    // Dereference
    const value_type& operator[](const difference_type ix) const {
        check_dereference(ix);
        return a_[ix];
    }

    const value_type& operator*() const {
        check_dereference();
        return a_[ix_];
    }

    const value_type* operator->() const {
        check_dereference();
        assert(ix_ < a_.size());
        return &(a_[ix_]);
    }

    // Logical
    bool operator==(const self_type& rhs) const { return ix_ == rhs.ix_; }

    bool operator!=(const self_type& rhs) const { return !operator==(rhs); }

    bool operator>(const self_type& rhs) const { return ix_ > rhs.ix_; }

    bool operator<=(const self_type& rhs) const { return !operator>(rhs); }

    bool operator<(const self_type& rhs) const { return ix_ < rhs.ix_; }

    bool operator>=(const self_type& rhs) const { return !operator<(rhs); }

protected:
    void check_ix() const { check_ix(ix_); }

    void check_ix(const difference_type ix) const {
        assert(ix < a_.size() + 1 && ix >= 0 && "Index is out of bounds.");
    }

    void check_dereference() const { check_dereference(ix_); }

    void check_dereference(const difference_type ix) const {
        assert(ix < a_.size() && ix >= 0
               && "The iterator cannot be dereferenced because it is out of "
                       "bounds");
    }

    const A& a_;
    typename A::size_type ix_;
};


template<typename A>
const_index_iterator<A> operator+(const typename
                                  const_index_iterator<A>::difference_type n,
                                  const const_index_iterator<A>& a) {
    return operator+(a, n);
}

template<typename A>
const_index_iterator<A> operator-(const const_index_iterator<A>& a,
                                  const typename
                                  const_index_iterator<A>::difference_type n) {
    return operator+(a, -n);
}

/// \brief Random access const_iterator over a container with index operation
/// \note no copy assignment / move assignment.
template<typename A>
class index_iterator : public const_index_iterator<A> {
    typedef const_index_iterator<A> Base;
    typedef index_iterator<A> self_type;
public:
    typedef typename A::value_type value_type;
    typedef value_type& reference;
    typedef value_type* pointer;
    typedef typename A::difference_type difference_type;
    typedef std::random_access_iterator_tag iterator_category;

    index_iterator(A& a, const typename A::size_type ix)
            : Base::const_index_iterator(a, ix) {}

    // Arithmetic
    friend index_iterator<A> operator+(const index_iterator<A>& a,
                                       const difference_type n) {
        return index_iterator<A>(a.mutable_a(), a.ix_ + n);
    }

    friend difference_type operator-(const index_iterator<A>& a,
                                     const index_iterator<A>& b) {
        return a.ix_ - b.ix_;
    }

    // Dereference
    using Base::operator*;
    using Base::operator->;

    value_type& operator[](const difference_type ix) const {
        check_dereference(ix);
        return mutable_a()[ix];
    }

    value_type& operator*() const {
        check_dereference();
        return mutable_a()[ix_];
    }

    value_type* operator->() const {
        check_dereference();
        return &(mutable_a()[ix_]);
    }

private:
    A& mutable_a() const { return const_cast<A&>(a_); }
    using Base::a_;
    using Base::ix_;
    using Base::check_dereference;

};

template<typename A>
index_iterator<A> operator+(const typename
                            index_iterator<A>::difference_type n,
                            const index_iterator<A>& a) {
    return operator+(a, n);
}

template<typename A>
index_iterator<A> operator-(const index_iterator<A>& a,
                            const typename
                            index_iterator<A>::difference_type n) {
    return operator+(a, -n);
}

template<typename A>
typename A::difference_type distance(const const_index_iterator<A>& a,
                                     const const_index_iterator<A>& b) {
    return a - b;
}

#endif //ALGORITHMS_ITERATOR_H

Answer 1

Your increment and decrement do not behave the same way as pointers (The classic example of how iterators should work).

// Arithmetic
self_type operator++() {
    ++ix_;
    check_ix();
    return *this;
}

self_type operator++(int dummy) { return operator++(); }

template<typename I>
int code(I x0) {     // assuming you got the copy working.

    I   x1(x0)

    auto value0  = *(++x);  // With your code these two values are
    auto value1  = *(x++);  // the same. I would not expect that.
}

See How to overload the operator++ for the classic implementation.

Normally if operator+=() is a member, then operator+() is a member.

self_type& operator+=(difference_type n) {
    ix_ += n;
    check_ix();
    return *this;
}


friend const_index_iterator<A> operator+(const const_index_iterator<A>& a,
                                         const difference_type n) {
    return const_index_iterator<A>(a.a_, a.ix_ + n);
}

Also normally these two are implemented in terms of each other. That way, by changing one you change both, and have less chance for a bug being introduced during maintenance.

self_type& operator+=(difference_type n) {
    ix_ += n;
    return *this;
}
self_type operator+(const difference_type n) {
    // Again assuming you get copy constructor working.
    return self_type(*this) += n;
}

Do you really need this for an iterator?

const value_type& operator[](const difference_type ix) const {
    check_dereference(ix);
    return a_[ix];
}

I don't like the trailing underscore on member names. It means you have names that are hard to distinguish from variables in the local context and thus need a visual reminder. This is a code smell. Use better names for your member variables so you know that they are members.