RingQueue implementation using std::array

Question

I've recently finished implementing a ring queue based on std::array in C++11. I tried to write the code as if I were going to submit it to the C++ Standard committee to have a RingQueue as part of the standard while keeping the implementation as simple and fast as possible. Please let me know if there are any changes I should make or any bugs you spot. I've tested the ring queue pretty well and I couldn't find anything outstandingly buggy/wrong about it.

#ifndef __RING_QUEUE_H__
#define __RING_QUEUE_H__

#include <array>

template <class T, size_t N>
class RingQueue {
public:
    typedef T                                                     value_type;
    typedef const T                                               const_value_type;
    typedef T&                                                    reference;
    typedef const T&                                              const_reference;
    typedef size_t                                                size_type;
    typedef std::array<T, N>                                      Container;
    typedef typename Container::iterator                          iterator;
    typedef typename Container::const_iterator                    const_iterator;
    typedef typename Container::reverse_iterator                  reverse_iterator;
    typedef typename Container::const_reverse_iterator            const_reverse_iterator;

    RingQueue(): p(0) {}
    ~RingQueue(){}
    RingQueue(const RingQueue&) = default;
    RingQueue& operator=(const RingQueue&) = default;

    inline reference operator[](size_t i) { return arr[i]; }
    inline const_reference operator[](size_t i) const { return arr[i]; }

    inline reference at(size_t i) { return arr.at(i); }
    inline const_reference at(size_t i) const { return arr.at(i); }

    inline reference front() { return arr.front(); }
    inline const_reference front() const { return arr.front(); }

    inline reference back() { return arr.back(); }
    inline const_reference back() const { return arr.back(); }

    inline value_type* data () { return arr.data(); }
    inline const value_type* data() const { return arr.data(); }

    inline bool empty() const { return arr.empty(); }

    inline void fill(const value_type& val) { arr.fill(val); }

    inline void enqueue(const value_type& i) { p %= arr.size(); arr[p] = i; ++p; }
    void dequeue()
    {
        if (empty()) return;
        for (auto i = arr.begin() + 1; i != arr.end(); ++i){ *(i - 1) = *i; }
        --p;
    }
    inline size_type size() const { return arr.size(); }
    inline size_type max_size() const { return arr.max_size(); }

    inline void swap(RingQueue<T, N>& x) { arr.swap(x.arr); }

    inline friend bool operator<(const RingQueue<T, N>& a, const RingQueue<T, N>& b)  { return a.arr < b.arr;  }
    inline friend bool operator==(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr == b.arr; }
    inline friend bool operator!=(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr != b.arr; }
    inline friend bool operator<=(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr <= b.arr; }
    inline friend bool operator>(const RingQueue<T, N>& a, const RingQueue<T, N>& b)  { return a.arr > b.arr;  }
    inline friend bool operator>=(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr >= b.arr; }

    inline iterator begin() { return arr.begin(); }
    inline const_iterator begin() const { return arr.begin(); }
    inline const_iterator cbegin() const { return arr.cbegin(); }

    inline reverse_iterator rbegin() { return arr.rbegin(); }
    inline const_reverse_iterator rbegin() const { return arr.rbegin(); }
    inline const_iterator crbegin() const { return arr.crbegin(); }

    inline iterator end() { return arr.end(); }
    inline const_iterator end() const { return arr.end(); }
    inline const_iterator cend() const { return arr.cend(); }

    inline reverse_iterator rend() { return arr.rend(); }
    inline const_reverse_iterator rend() const { return arr.rend(); }
    inline const_iterator crend() const { return arr.crend(); }

private:
    Container arr;
    size_t p;
};

#endif

I have rolled back the last edit. Please see What to do when someone answers. — Jamal♦, Jul 7 at 19:55
@immibis This is a ring queue in the sense that there will be a maximum number of fixed elements at any moment. Any time the queue is full, it overwrites values at the beginning of the queue. Therefore, a ring queue of K size will hold the last K elements inserted. — TamerCpp, Jul 8 at 14:27

vnp · Answer 1 · 2015-07-07 18:29:10Z

up vote 8 down vote

Most methods/operators completely ignore p, which makes the semantics dubious. For example, shouldn't end() return the end of actually available data instead? Along the same line, after swap() the values of p and x.p become inconsistent.
It is a good practice to use standard library whenever possible: the dequeue loop is literally std::copy.
Implementation of dequeue() defeats the purpose of ring buffer. The goal of ring buffer is to avoid moving data around.

answered Jul 7 at 18:29

vnp
15.3k846

The values of p and x.p don't become inconsistent. The swap function just swaps the values in the arrays but doesn't swap the next insertion point of both instances. That's how I've chosen to implement it. I didn't think it'd make sense to swap the insertion values either. – TamerCpp Jul 7 at 19:30

add a comment |

o11c · Answer 2 · 2015-07-07 18:37:08Z

up vote 10 down vote

Uh, that's not a ring queue. The O(n) implementation of dequeue jumps out immediately.

In an actual circular buffer, you can't use the underlying buffer directly; you have to do math (add and modulus) on all indexing operations (if you even supply them! normally I would expect only a .front() and .back(). Likewise, you can't reuse the underlying contain's iterators because you have to do the modulus there too. But I wouldn't supply iterators at all, std::queue doesn't.

answered Jul 7 at 18:37

o11c
951216

You're right about the implementation of dequeue; I'll be removing it. The reason I provided those iterators was just to allow the queue to be able to be used in an enhanced for loop - in the case the user wants to print out the entire queue for example. I'm also not sure what you mean when you say "can't use underlying buffer directly; you have to do math". I am doing modulus math on insertion. – TamerCpp Jul 7 at 19:07

@TamerCpp s/he means that if you just iterate over the underlying buffer, you'll get things in the wrong order. What you have is a queue, but not a ring queue (aka ring buffer or circular buffer): en.wikipedia.org/wiki/Circular_buffer – immibis Jul 9 at 3:15

add a comment |

glampert · Answer 3 · 2015-07-08 02:48:47Z

A few minor stylistic bits, adding to what other reviews already mentioned:

__RING_QUEUE_H__ include guard uses the double underscore prefix, which is reserved for implementation and Standard Library names. Refer to this SO question for a complete listing of potentially reserved named and prefixes.
Technically, size_t is a member of namespace std in C++, e.g.: std::size_t. It happens to exist in the global scope as well because most implementations use the same header file for both C and C++, so the C header exposes all types globally. This is not a requirement, however, so for better portability your should consider fully qualifying the name.
~RingQueue(){}: The empty destructor is not necessary. You only need to provide one if: the class needs some customized cleanup; if you need a virtual destructor for inheritance; if you need to make the destructor private or protected. Otherwise, omit the declaration and let the compiler supply a default for you.
inline is not necessary when a class method is directly defined inside the class body in the header file. In this case, it serves no purpose but to make your code more verbose.
I would personally use shorter lines. Put the method ret name(parameters) part in its own line, with the { } body on the next following lines.
You might consider declaring functions as noexcept where applicable, if you plan on making this as Standard compliant as possible.
max_size() is a constexpr method in std::array. It just returns some predefined constant. You can apply that to your wrapper method as well.

Thank you, I'll be taking these comments to consideration. Speaking of point 1, I did that on purpose as if my data structure would be included in the standard :) Also, my compiler doesn't seem to support noexcept/constexpr so I omitted those. — TamerCpp, Jul 7 at 19:09

TamerCpp · Answer 4 · 2015-07-07 20:19:47Z

I've revised the code after taking into account all of the recommendations from the above reviewers. I've also added an enqueue that takes an rvalue reference (for move semantics) as well as an initializer list constructor.

The new code:

#ifndef __RING_QUEUE_H__
#define __RING_QUEUE_H__

#include <array>
#include <initializer_list>
#include <algorithm>

template <class T, std::size_t N>
class RingQueue {
public:
    typedef T                                                     value_type;
    typedef const T                                               const_value_type;
    typedef T&                                                    reference;
    typedef const T&                                              const_reference;
    typedef std::size_t                                           size_type;
    typedef std::array<T, N>                                      Container;
    typedef typename Container::iterator                          iterator;
    typedef typename Container::const_iterator                    const_iterator;
    typedef typename Container::reverse_iterator                  reverse_iterator;
    typedef typename Container::const_reverse_iterator            const_reverse_iterator;

    RingQueue(): p(0) {}
    RingQueue(const RingQueue<T, N>&) = default;
    RingQueue& operator=(const RingQueue<T, N>&) = default;
    RingQueue(std::initializer_list<T> i) : RingQueue()
    {
        std::for_each(i.begin(), i.end(), [this](const T& elem){ enqueue(elem); });
    }

    reference operator[](size_t i) { return arr[i]; }
    const_reference operator[](size_t i) const { return arr[i]; }

    reference at(size_t i) { return arr.at(i); }
    const_reference at(size_t i) const { return arr.at(i); }

    reference front() { return arr.front(); }
    const_reference front() const { return arr.front(); }

    reference back() { return arr.back(); }
    const_reference back() const { return arr.back(); }

    value_type* data () { return arr.data(); }
    const value_type* data() const { return arr.data(); }

    bool empty() const { return arr.empty(); }

    void fill(const value_type& val) { arr.fill(val); }

    void enqueue(const value_type& i) { p %= arr.size(); arr[p] = i; ++p; }
    void enqueue(const value_type&& i) { p %= arr.size(); arr[p] = std::move(i); ++p; }

    size_type size() const { return arr.size(); }
    size_type max_size() const { return arr.max_size(); }

    void swap(RingQueue<T, N>& x) { arr.swap(x.arr); }

    friend bool operator<(const RingQueue<T, N>& a, const RingQueue<T, N>& b)  { return a.arr < b.arr;  }
    friend bool operator==(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr == b.arr; }
    friend bool operator!=(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr != b.arr; }
    friend bool operator<=(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr <= b.arr; }
    friend bool operator>(const RingQueue<T, N>& a, const RingQueue<T, N>& b)  { return a.arr > b.arr;  }
    friend bool operator>=(const RingQueue<T, N>& a, const RingQueue<T, N>& b) { return a.arr >= b.arr; }

    iterator begin() { return arr.begin(); }
    const_iterator begin() const { return arr.begin(); }
    const_iterator cbegin() const { return arr.cbegin(); }

    reverse_iterator rbegin() { return arr.rbegin(); }
    const_reverse_iterator rbegin() const { return arr.rbegin(); }
    const_iterator crbegin() const { return arr.crbegin(); }

    iterator end() { return arr.end(); }
    const_iterator end() const { return arr.end(); }
    const_iterator cend() const { return arr.cend(); }

    reverse_iterator rend() { return arr.rend(); }
    const_reverse_iterator rend() const { return arr.rend(); }
    const_iterator crend() const { return arr.crend(); }

private:
    Container arr;
    size_t p;
};

#endif

So instead of fixing the performance problem in your implementation of dequeue(), you just removed that method altogether? — 200_success♦, Jul 8 at 0:29

Pete Becker · Answer 5 · 2015-07-08 03:00:10Z

For the standard, the name should be ring_queue. Your sample implementation should be written as ordinary user-written code, i.e., no reserved names. Leave it to implementors to get those details right: there's a lot more to it than putting underscores around the name of the include guard.

The main thing that's needed for a proposal for standardization is an interface specification. If you look at the standard, there aren't any include guards, no #include directives (except for initializer_list, a weird exception), and no implementation details (well, hardly any; once in a while there are some data members marked exposition only). The idea is to specify what the interface looks like, so that users can write code that calls it, and to specify what those interface functions do. The details of how to implement it don't go in the specification.

asked	2 months ago
viewed	245 times
active	2 months ago

current community

your communities

more stack exchange communities

RingQueue implementation using std::array

5 Answers 5

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ c++11 array queue or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

RingQueue implementation using std::array

5 Answers 5

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ c++11 array queue or ask your own question.

Related

Hot Network Questions