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

• Incomputable: copy assignment is mandatory, thus as it currently stands, it is not iterator defined by standard library.
• R zu: Thanks. And using pointer to container won't hurt performance?
• Incomputable: Best way to figure out is measure. Also, one can use std::reference_wrapper.
• Loki Astari: Switching to pointer is unlikely to change performance. But measure it if you are worried.
• R zu: I am sorry. pointer and reference, and std::vector's iterators give same performance. It was problem with my cmake file.

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.

• R zu: Thank you very much for telling me the convention and the bug in the increment and decrement operators. I am fixing the code now. I added the indexing operation after reading en.cppreference.com/w/cpp/concept/RandomAccessIterator
• Incomputable: @Rzu, you could also use "operator overloading" page on cppreference.