Example of adding STL iterator support to custom collection class

Question

I'm trying to create an example of a custom collection with an API meeting the requirements of STL iterator templates, as a learning experience.

The collection used here, a ring buffer, is merely a toy in order to help me learn the concepts involved. Once I have a better understanding of those concepts, I intend to retro-fit a similar API to a series of custom collection classes in an existing large body of code.

/**
 * Name        : RingQueue.cpp
 * Author      : Some Guy
 * Version     :
 * Copyright   : Copyleft 2018 Some Guy. No rights reserved.
 * Description : A ring buffer with STL iterators in C++.
 */

#include <iostream>
#include <sstream>
#include <iterator>
#include <cassert>

template <typename T, int capacity> class RingIter;
template <typename T, int capacity> class RingIterConst;

template <typename T, int capacity> class RingQueue {
    friend class RingIter<T, capacity>;
    friend class RingIterConst<T, capacity>;
    typedef RingIter<T, capacity> iterator;
    typedef RingIterConst<T, capacity> const_iterator;
private:
    T buf[capacity];
    int begin_idx;
    int siz;

    int end_idx() { return (begin_idx + siz) % capacity; }
public:
    RingQueue() : begin_idx(0), siz(0) {}
    ~RingQueue() {}
    int size() const { return siz; }
    T &front() {
        if (siz) {
            return buf[begin_idx];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    const T &front() const {
        if (siz) {
            return buf[begin_idx];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    T &back() {
        if (siz) {
            return buf[end_idx()];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    const T &back() const {
        if (siz) {
            return buf[end_idx()];
        } else {
            throw std::invalid_argument("RingQueue is empty");
        }
    }
    T &pop_front() {
        if (!siz) {
            throw std::invalid_argument("RingQueue is empty");
        }
        T &ret = buf[begin_idx];
        begin_idx++;
        begin_idx %= capacity;
        siz--;
        return ret;
    }
    void push_back(T val) {
        buf[end_idx()] = val;
        if (siz < capacity) {
            siz++;
        } else {
            begin_idx++;
            begin_idx %= capacity;
        }
    }
    iterator begin() { return iterator(*this, 0); }
    iterator end() { return iterator(*this, siz); }
    const_iterator cbegin() const { return const_iterator(*this, 0); }
    const_iterator cend() const { return const_iterator(*this, siz); }
    iterator rbegin() { return iterator(*this, siz - 1, -1); }
    iterator rend() { return iterator(*this, -1, -1); }
    const_iterator crbegin() const { return const_iterator(*this, siz - 1, -1); }
    const_iterator crend() const { return const_iterator(*this, -1, -1); }
};

template <typename T, int capacity> class RingIterConst {
    typedef RingIterConst<T, capacity> thisclass;
protected:
    const RingQueue<T, capacity> &rq;
    int off;
    int inc;
    inline const T& deref() { return rq.buf[(rq.begin_idx + off) % capacity]; }
public:
    RingIterConst(const RingQueue<T, capacity> &iterateOver, int offset, int increment = 1) : rq(iterateOver), off(offset), inc(increment) {}
    ~RingIterConst() {}
    bool operator==(const RingIterConst &i) {
        return &i.rq == &rq && i.off == off;
    }
    bool operator!=(const RingIterConst &i) {
        return !(*this == i);
    }
    thisclass & operator++()    { off += inc; return *this; }
    thisclass & operator++(int) { off += inc; return *this; }
    thisclass & operator--()    { off -= inc; return *this; }
    thisclass & operator--(int) { off -= inc; return *this; }
    typename std::iterator_traits<thisclass>::difference_type operator-(thisclass &sibling) const { return (off - sibling.off) / inc; }
    thisclass & operator+=(int amount) { off += (amount * inc); return *this; }
    thisclass & operator-=(int amount) { off -= (amount * inc); return *this; }
    thisclass & operator-() { return thisclass(rq, off, -inc); }
    bool operator<(thisclass &sibling) const { return (inc < 0) != (off < sibling.off);}
    bool operator<=(thisclass &sibling) const { return (inc < 0) != (off <= sibling.off); }
    bool operator>(thisclass &sibling) const { return (inc < 0) != (off > sibling.off); }
    bool operator>=(thisclass &sibling) const { return (inc < 0) != (off >= sibling.off); }
    const T& operator[](int index) {
        assert(index >= 0);
        assert(index < rq.siz);
        return rq.buf[(rq.begin_idx + off + (index * inc)) % capacity];
    }
    const T& operator*() { return deref(); }
};

template <typename T, int capacity> class RingIter : public RingIterConst<T, capacity> {
public:
    RingIter(RingQueue<T, capacity> &iterateOver, int offset) : RingIterConst<T, capacity>(iterateOver, offset) {}
    ~RingIter() {}
    T& operator[](int index) { return this->rq.buf[(this->rq.begin_idx + this->off + (index * this->inc)) % this->capacity]; }
    T &operator*() { return this->deref(); }
};

// FIXME: Do not pollute namespace 'std'.
namespace std {
template<typename T, int capacity> class iterator_traits<RingIterConst<T, capacity> > {
public:
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef std::random_access_iterator_tag iterator_category;
};
template<typename T, int capacity> class iterator_traits<RingIter<T, capacity> > : public iterator_traits<RingIterConst<T, capacity> > {
    typedef const T value_type;
    typedef const T* pointer;
    typedef const T& reference;
};
}

int main(void) {
    RingQueue<int, 4> rq;
    for (int i = 0; i < 10; i++) {
        rq.push_back(i * i);
    }
    assert(rq.size() == 4);
    std::ostringstream s;
    std::copy(rq.cbegin(), rq.cend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "36 49 64 81 ");
    s.str("");
    std::copy(rq.crbegin(), rq.crend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "81 64 49 36 ");
    return 0;
}

Answer 1

Be consistent with back()

end_idx() should match either the next insertion position, or the last insertion position. A simple test of push_back() and back() shows how these are not consistent.

This can be fixed by making end_idx refer to the last element added, and pre-incrementing before inserting.

Provide begin()/end()/rbegin()/rend() for constant collections.

You want to be able to write a function like

template<typename T, std::size_t Capacity>
std::string to_string(const RingIter<T,Capacity>& ring)
{
    std::ostringstream s;
    std::copy(ring.begin(), ring.end(), std::ostream_iterator<const T>(s, " "));
    return s.str();
}

and you want to be able to write for (auto& element: ring) without jumping through hoops.

Postincrement and postdecrement are wrongly implemented

++ and ++(int) should not be the same here (and g++ -Weffc++ warns about this):

thisclass & operator++()    { off += inc; return *this; }
thisclass & operator++(int) { off += inc; return *this; }
thisclass & operator--()    { off -= inc; return *this; }
thisclass & operator--(int) { off -= inc; return *this; }

I'd expect

thisclass & operator++()    { off += inc; return *this; }
thisclass operator++(int) { auto t = *this; off += inc; return t; }
thisclass & operator--()    { off -= inc; return *this; }
thisclass operator--(int) { auto t = *this; off -= inc; return t; }

Of course, returning by value will involve slicing for the non-const subclass, so it will need (trivially) overloading there.

Relational operators should not take mutable ref arguments

Instead of

bool operator<(thisclass &sibling) const;

I'd expect

bool operator<(thisclass const& sibling) const;

The same goes for the operator-() that takes another thisclass.

Indexing operator

I've not seen an indexing operator on an iterator before, but you could simplify it just by using the programmer's expectation:

const T& operator[](int index) {
    return *(*this + index);
}

Note that the assert() is okay for documenting invariants, but very poor for argument checking.

Use a std::size_t for sizes and indexes

Who wants a collection limited to the range of int?

Iterator direction never changes

We can declare inc to be constant. This doesn't affect our ability to assign values, as we already contain a reference member.

No need to declare destructor

The iterators' destructors do nothing, so just let the compiler default them.

Non-const iterator is completely untested

We never compile any code using the non-const version of the iterator. Even its constructor is broken:

189380.cpp:83:32: error: no matching function for call to ‘RingIter<int, 4>::RingIter(RingQueue<int, 4>&, int, int)’
     iterator rbegin() { return iterator(*this, siz - 1, -1); }
                                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~

We need to add the final argument

RingIter(RingQueue<T, capacity> &iterateOver, int offset, int increment = 1)
    : RingIterConst<T, capacity>(iterateOver, offset, increment)
{}

Its iterator_traits members are all private, so unusable.

A cast is required in operator*:

T &operator*() { return const_cast<T&>(this->deref()); }

---

Alternative implementation

Instead of keeping a reference to the container, we could more simply just keep a pointer/reference to its buffer in the iterator. We need to hold the actual index (mod capacity) rather than the offset from the container's current endpoint, but that's not hard:

template <typename T, int capacity>
class RingIter
{
    T *const buf;
    int off;
    int const inc;

public:
    RingIter(T *buf, int offset, int increment = 1)
        : buf(buf), off(offset), inc(increment)
    {}
//...
};

We can re-use this for both const and non-const iterators like this:

template <typename T, int capacity>
class RingQueue
{
public:
    typedef RingIter<T, capacity> iterator;
    typedef RingIter<const T, capacity> const_iterator;

    iterator begin() { return {buf, begin_idx}; }
    iterator end() { return {buf, begin_idx + siz}; }
    const_iterator cbegin() const { return {buf, begin_idx}; }
    const_iterator cend() const { return {buf, begin_idx + siz}; }
    iterator rbegin() { return {buf, begin_idx + siz - 1, -1}; }
    iterator rend() { return {buf, begin_idx - 1, -1}; }
    const_iterator crbegin() const { return {buf, begin_idx + siz - 1, -1}; }
    const_iterator crend() const { return {buf, begin_idx - 1, -1}; }
};

Now the iterator doesn't need to be a friend (but it does need cooperation from the container, which has to give out a pointer to its internal buffer), and we have to maintain only one iterator template (which can equally well point to const or non-const type T).

Consider std::reverse_iterator

Simplify the iterator by using std::reverse_iterator<RingIter<...>> to adapt your random access iterator for reverse operation, as standard library implementations do. This means that the iterators don't need an inc member to indicate their direction.

---

Full worked example

#include <iterator>

template <typename T, std::size_t Capacity>
class RingIter;

template <typename T, std::size_t Capacity>
class RingQueue
{
private:
    T buf[Capacity];
    std::size_t begin_idx;
    std::size_t siz;

    T& last_val() { return buf[(begin_idx + siz - 1) % Capacity]; }

public:
    using iterator = RingIter<T, Capacity>;
    using const_iterator = RingIter<const T, Capacity>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    RingQueue()
        : begin_idx(0), siz(0)
    {}

    std::size_t size() const { return siz; }
    bool empty() const { return siz; }
    T &front() { return buf[begin_idx]; }
    const T &front() const { return buf[begin_idx]; }
    T &back() { return last_val(); }
    const T &back() const { return last_val(); }

    T &pop_front() {
        T &ret = buf[begin_idx++];
        begin_idx %= Capacity;
        --siz;
        return ret;
    }
    void push_back(const T& val) {
        if (siz < Capacity) {
            ++siz;
        } else {
            ++begin_idx %= Capacity;
        }
        last_val() = val;
    }
    void push_back(T&& val) {
        if (siz < Capacity) {
            ++siz;
        } else {
            ++begin_idx %= Capacity;
        }
        last_val() = std::move(val);
    }

    iterator begin() { return { buf, begin_idx }; }
    iterator end() { return {buf, begin_idx + siz}; }
    const_iterator begin() const { return {buf, begin_idx}; }
    const_iterator end() const { return {buf, begin_idx + siz}; }
    const_iterator cbegin() const { return begin(); }
    const_iterator cend() const { return end(); }

    reverse_iterator rbegin() { return reverse_iterator{end()}; }
    reverse_iterator rend() { return reverse_iterator{begin()}; }
    const_reverse_iterator rbegin() const { return const_reverse_iterator{end()}; }
    const_reverse_iterator rend() const { return const_reverse_iterator{begin()}; }
    const_reverse_iterator crbegin() const { return rbegin(); }
    const_reverse_iterator crend() const { return rend(); }
};

template <typename T, std::size_t Capacity>
class RingIter
{
    T *const buf;
    std::size_t off;
public:
    RingIter(T *buf, std::size_t offset)
        : buf(buf), off(offset)
    {}
    bool operator==(const RingIter &i) {
        return &i.buf == &buf && i.off == off;
    }
    bool operator!=(const RingIter &i) {
        return !(*this == i);
    }
    RingIter & operator++()    { ++off; return *this; }
    RingIter operator++(int) { auto t = *this; ++off; return t; }
    RingIter & operator--()    { --off; return *this; }
    RingIter operator--(int) { auto t = *this; --off; return t; }
    std::ptrdiff_t operator-(RingIter const& sibling) const { return off - sibling.off; }
    RingIter & operator+=(int amount) { off += amount; return *this; }
    RingIter & operator-=(int amount) { off -= amount; return *this; }
    bool operator<(RingIter const&sibling) const { return off < sibling.off;}
    bool operator<=(RingIter const&sibling) const { return off <= sibling.off; }
    bool operator>(RingIter const&sibling) const { return off > sibling.off; }
    bool operator>=(RingIter const&sibling) const { return off >= sibling.off; }
    T& operator[](int index) const { return *(*this + index); }
    T& operator*() const { return buf[off % Capacity]; }
};

namespace std {
    template<typename T, std::size_t Capacity>
    class iterator_traits<RingIter<T,Capacity> >
    {
    public:
        using difference_type = std::ptrdiff_t;
        using size_type = std::size_t;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using iterator_category = std::random_access_iterator_tag;
    };
}

#include <cassert>
#include <iostream>
#include <sstream>
int main(void) {
    RingQueue<int, 4> ring;
    for (int i = 0; i < 10; i++) {
        ring.push_back(i * i);
    }
    assert(ring.size() == 4);
    assert(ring.front() == 36);
    assert(ring.back() == 81);
    std::ostringstream s;
    std::copy(ring.cbegin(), ring.cend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "36 49 64 81 ");
    s.str("");
    std::copy(ring.rbegin(), ring.rend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "81 64 49 36 ");

    auto const& ro_ring = ring;
    s.str("");
    std::copy(ro_ring.cbegin(), ro_ring.cend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "36 49 64 81 ");
    s.str("");
    std::copy(ro_ring.rbegin(), ro_ring.rend(), std::ostream_iterator<const int>(s, " "));
    assert(s.str() == "81 64 49 36 ");
    return 0;
}

Answer 2

Avoid repeating yourself

By my count you have 5 repetitions of code to assure that the collection is non-empty before doing what a function is intended to do.

I'd move that code into a single function, and have the others call it:

void assure_non_empty() const { 
    if (siz == 0)
        throw std::invalid_argument("RingQueue is empty");
}

const T &back() const {
    assure_non_empty();
    return buf[end_idx()];
}

const T &front() const {
    assure_non_empty();
    return buf[begin_idx];
}

// and so on

Exception choice

I'm also a bit less than certain that std::invalid_argument is the right exception to throw under the circumstances. You can argue that what's involved is really an invalid argument (since this is passed as a hidden argument to a member function), but at least to me it "feels" wrong to throw an invalid_argument from a function that doesn't actually take an explicit argument.