Circular queue using STL queue?

user_3118602 0
Viewed 5965

I have been searching the internet for a while but can't seem to find an answer on this.

I intend to use stl::queue to conduct some simulation. I am wondering if it is possible to create a circular queue using stl::queue? As far as I know, stl::queue is linear and is not circular by default?

If this is possible, does anyone have any implementation reference that I can refer to?

Thanks.

queue stl c++
2 Answers

std::deque is defined fairly carefully to be a linear queue. Its design isn't really suitable for a circular queue.

In particular, it breaks the queue up into a number of equal-sized blocks, so if the queue is reasonably balanced (i.e., on average, data is being consumed about as fast as it's being produced) you'll normally have blocks being discarded and ready for re-use, so you can use one for a long time with minimal heap fragmentation.

To accomplish that, a deque (at least normally) uses a two-level storage mechanism. That is to say, it has an expandable array of pointers, each pointing to an equal-sized block that contains the actual data.

For a circular buffer, however, that's pointless and unnecessary. With a circular buffer, you normally allocate a block of memory when you create it, and continue to use that same block of memory until you destroy it. In this case, the two-level storage used by a deque simply adds an extra level of indirection to every access without accomplishing anything useful.

For a circular buffer, you might as well using a single, flat chunk of memory to hold your data, and just create/destroy objects in that block of memory. Here's a simple implementation I wrote some time ago:

#ifndef CBUFFER_H_INC
#define CBUFFER_H_INC

template <class T>
class circular_buffer {
    T *data;
    unsigned read_pos;
    unsigned write_pos;
    unsigned in_use;
    const unsigned capacity;
public:
    circular_buffer(unsigned size) :
        data((T *)operator new(size * sizeof(T))),
        read_pos(0),
        write_pos(0),
        in_use(0),
        capacity(size)
    {}

    void push(T const &t) {
        // ensure there's room in buffer:
        if (in_use == capacity) 
            pop();

        // construct copy of object in-place into buffer
        new(&data[write_pos++]) T(t);
        // keep pointer in bounds.
        write_pos %= capacity;
        ++in_use;
    }

    // return oldest object in queue:
    T front() {
        return data[read_pos];
    }

    // remove oldest object from queue:
    void pop() { 
        // destroy the object:
        data[read_pos++].~T();

        // keep pointer in bounds.
        read_pos %= capacity;
        --in_use;
    }
  
~circular_buffer() {
    // first destroy any content
    while (in_use != 0)
        pop();

    // then release the buffer.
    operator delete(data); 
}

};

#endif
user_1799100

If you can use The Boost Libraries, there is already a boost::circular_buffer class template that implements the front(), back(), push_back() and pop_front() member functions and therefore can be used as the underlying container for the std::queue container adapter:

#include <queue>
#include <boost/circular_buffer.hpp>
#include <cassert>

template<typename T>
using Queue = std::queue<T, boost::circular_buffer<T>>;

auto main() -> int {
   Queue<int> q(boost::circular_buffer<int>(3)); // capacity of the queue is 3

   q.push(0);
   q.push(1);
   q.push(2);
   assert(q.front() == 0);
   assert(q.back() == 2);

   q.push(3);
   assert(q.front() == 1);
   assert(q.back() == 3);

   q.pop();
   assert(q.front() == 2); 
   assert(q.back() == 3);
}
user_80126460
Related