6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ copy assignment is mandatory, thus as it currently stands, it is not iterator defined by standard library. \$\endgroup\$ – Incomputable Apr 24 '18 at 18:37
  • \$\begingroup\$ Thanks. And using pointer to container won't hurt performance? \$\endgroup\$ – R zu Apr 24 '18 at 18:42
  • \$\begingroup\$ Best way to figure out is measure. Also, one can use std::reference_wrapper. \$\endgroup\$ – Incomputable Apr 24 '18 at 18:43
  • \$\begingroup\$ Switching to pointer is unlikely to change performance. But measure it if you are worried. \$\endgroup\$ – Martin York Apr 24 '18 at 19:53
  • \$\begingroup\$ I am sorry. pointer and reference, and std::vector's iterators give same performance. It was problem with my cmake file. \$\endgroup\$ – R zu Apr 24 '18 at 22:44
7
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.