CODEWITHSUNDEEP
c++stlqueue
user3118602
user3118602

Reputation: 583

Circular queue using STL queue?

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.

Upvotes: 8

Views: 13490

Answers (3)

Gerard Torrent
Gerard Torrent

Reputation: 241

You can found a C++20 implementation of a circular queue at https://github.com/torrentg/cqueue

  • Adheres to STL container standards (allocator, iterators, etc)
  • Don't require a fixed capacity
  • Header-only

Note: I am the project maintainer.

Upvotes: 2

jfMR
jfMR

Reputation: 24738

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);
}

Upvotes: 3

Jerry Coffin
Jerry Coffin

Reputation: 490108

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

Upvotes: 4

Related Questions