3
\$\begingroup\$

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;
}
\$\endgroup\$
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for this, these are all excellent suggestions. Should I simply accept this answer? Or should you and I commence an iterative process, whereby I incorporate your changes and you update your critique? Sorry, I am new here. \$\endgroup\$ – AnotherSmellyGeek Mar 12 '18 at 15:01
  • \$\begingroup\$ There's a good section in the help center entitled What should I do when someone answers my question? - in summary, do not change the code in your question. I'd recommend waiting a few days for answers, as there are certainly review points I've missed, and accepting an answer suggests you don't need any more review. \$\endgroup\$ – Toby Speight Mar 12 '18 at 15:03
  • \$\begingroup\$ Do you have any useful feedback regarding the use of a distinct iterator class, instead of using a primitive type such as a pointer? In this contrived example it's required, but in the "real world" case I intend to work on next, there are multiple subclasses of collection, some which can use primitive iterators and some not. Is it as simple as: use primitive types whenever possible? \$\endgroup\$ – AnotherSmellyGeek Mar 12 '18 at 15:35
  • \$\begingroup\$ Lastly, is there any way to avoid poking things into namespace 'std'? \$\endgroup\$ – AnotherSmellyGeek Mar 12 '18 at 15:36
  • \$\begingroup\$ Last two comments - use a class whenever a primitive type won't do the job (for iterators, that's almost always, except where the storage is an array). And you don't avoid defining things in namespace std when that's the customization point at which you're expected to define it (i.e. defining std::iterator_traits<RingIter> is the correct thing to do). \$\endgroup\$ – Toby Speight Mar 12 '18 at 16:49
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'd just get rid of that checking entirely, and expect the user to check empty() or equivalent, just like the standard containers. Don't pay for something that's not needed! \$\endgroup\$ – Toby Speight Mar 12 '18 at 14:51
  • \$\begingroup\$ @TobySpeight: That, of course, is an entirely valid option as well (but it's not really in keeping with what I'd consider the basic spirit of this site, which at least as I see things is mostly about refactoring while maintaining the same behavior unless that behavior is clearly unintended). With this design, it's also trivial to define assure_non_empty() as a macro that does the check for a debug built, and expands to nothing in a release build. \$\endgroup\$ – Jerry Coffin Mar 12 '18 at 14:54
  • \$\begingroup\$ @Toby Thanks, I now see that there's no good reason why every correct caller, who only asks for the front or back of a non-empty collection, should have to pay for a runtime check. But I also agree that such checking should be centralised if it does continue to be present. Perhaps an assertion would be appropriate in this case? \$\endgroup\$ – AnotherSmellyGeek Mar 12 '18 at 14:58
  • \$\begingroup\$ @Jerry Which is essentially what assert does... so we seem all three of us to be basically in agreement here? \$\endgroup\$ – AnotherSmellyGeek Mar 12 '18 at 14:59
  • \$\begingroup\$ @AnotherSmellyGeek: I dunno. Retrieving iterators is rarely done so often than the cost of doing a validity check first is likely to cost enough to notice. As such, i'd tend toward leaving them in until/unless a profiler really indicates removing them make a big difference. \$\endgroup\$ – Jerry Coffin Mar 12 '18 at 15:03

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.