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
unlikely
to change performance. But measure it if you are worried. \$\endgroup\$