C++ Queue Circular Array Implementation

Question

I'm trying to implement a queue data structure in C++ using a circular array.

Please give recommendations on how I can improve this code. Also, is my array growth strategy good? I'm doubling the array when the buffer is full. (Try to remain in C++ 11 because, well that's a restriction I have to follow atm).

Sorry for the lack of comments in advance LoL (this is a rushed implementation).

#include <iostream>
#include <utility>
template <typename T>
class Queue {
public:
 Queue() : data(nullptr), len(0), front(0), cap(0)
 {
 }
 ~Queue()
 {
 this->Clear();
 }
 Queue(const Queue& rhs) : Queue()
 {
 if (rhs.data) {
 this->data = new T[rhs.cap];
 this->cap = rhs.cap;
 this->len = rhs.len;
 this->front = rhs.front;
 for (size_t i = 0; i < len; ++i) {
 this->data[i] = rhs.data[i];
 }
 }
 }
 Queue(Queue&& rhs) : data(rhs.data), cap(rhs.cap), len(rhs.len), front(rhs.front)
 {
 rhs.data = nullptr;
 }
 Queue& operator=(Queue rhs)
 {
 swap(*this, rhs);
 return *this;
 }
 size_t GetLength() const { return len; }
 const T& GetFront() const { return data[front]; }
 void Enqueue(const T& val)
 {
 if (len == cap) {
 size_t oldCap = cap;
 if (cap == 0) cap = 1;
 cap *= 2;
 T* newBuff = new T[cap];
 for (size_t i = 0; i < len; ++i) {
 size_t idx = (front + i) % oldCap;
 newBuff[i] = data[idx];
 }
 front = 0;
 data = newBuff;
 }
 data[(front + len) % cap] = val;
 ++len;
 }
 T Dequeue()
 {
 T val = std::move(data[front]);
 front = (front + 1) % cap;
 --len;
 return val;
 }
 void Clear()
 {
 delete[] data;
 data = nullptr;
 this->cap = this->len = this->front = 0;
 }
 friend
 std::ostream& operator<< (std::ostream& out, const Queue& q)
 {
 out << "Queue{";
 for (size_t i = 0; i < q.len; ++i) {
 size_t idx = (q.front + i) % q.cap;
 out << q.data[idx];
 if (i < q.len - 1) out << ", ";
 }
 out << "}";
 return out;
 }
 friend
 void swap(Queue& lhs, Queue& rhs)
 {
 std::swap(lhs.data, rhs.data);
 std::swap(lhs.len, rhs.len);
 std::swap(lhs.cap, rhs.cap);
 std::swap(lhs.front, rhs.front);
 }
private:
 T* data;
 size_t len;
 size_t cap;
 size_t front;
};
int main()
{
 Queue < int > a;
 a.Enqueue( 5 ); // add 5 
 a.Enqueue ( 6 ); // add 6
 std::cout << a; // prints Queue{5, 6}
 
 a.Clear(); // empties the Queue
 std::cout << a; // prints Queue{}
}
```

• user228914: Can you give a basic example of how this class can be used?
• Guy on the Internet: @Aryan Parekh this is a Queue (First-In First-Out) data structure. I'm a CS student so I'm just learning about Data structures so I don't know about many applications of the Queue. However it is used for simulating a real-life Queue in programming.
• user228914: You misunderstood me :), I added a main() function in your code showing how this class can be used. You can edit it further to show the use of the rest of the functions
• Guy on the Internet: @Aryan Parekh ok
• Zachary Vance: A circular array is rough to resize correctly. Can you avoid doing that, and instead throw an error, ha? Doubling is fine, yes. Definitely pull it out of Enqueue. It can be made much more efficient--should just be 'memcpy' twice. Also, you have a memory leak there now. I would allow setting capacity on create (either empty or from another queue) if you want to be extra professional.

Answer 1

This is quite a decent implementation of a C++ container! Some minor improvements are possible though:

Prefer using default member initialization

Especially when you have multiple constructors, default member initialization saves typing and reduces the chance of accidentily not initializing a variable. So:

class Queue {
public:
 Queue() = default;
 Queue(const Queue &rhs)
 {
 ...
 }
 ...
private:
 T* data = nullptr; // or {} works as well
 size_t len = 0;
 size_t cap = 0;
 size_t front = 0;
};

Use bitwise AND instead of modulo operations

Calculating the modulus of an integer is very slow compared to doing a bitwise AND (tens of CPU cycles vs. a fraction of a cycle). Since your capacity is always a power of two, you can use bitwise AND, like so:

data[(front + len) & (cap - 1)] = val;

You can get rid of the - 1 if you really want, that means storing the capacity minus one in cap. This will speed up the common case where you don't need to reallocate a tiny bit.

Note that the compiler probably won't be able to optimize the modulo to a bitwise AND by itself, because cap is not a constant.

Consider following the naming conventions of the standard library

It would be nice if your container has the same interface as other STL containers. That makes it easier for a programmer to remember the names of the member functions, but also makes it more likely that your container can be used as a drop-in replacement for other STL containers, and that algorithms that work with a std::queue can also work with your container. So consider renaming these member functions:

• GetLength() -> size()
• GetFront() -> front()
• Enqueue() -> push()
• Dequeue() -> pop() (althought the STL's pop() doesn't return any value)
• Clear() -> clear()

The reason the STL doesn't return a value for pop() is so that it doesn't require T to be movable, instead you use front() to read the value, then pop() to discard it.

Unnecessary use of this->

There are a few places where you use this-> where it isn't necessary. In the copy constructor it makes a bit of sense since this emphasizes the contrast with rhs., but in ~Queue() and Clear() you don't need it.

• Guy on the Internet: Thanks for the detailed answer 👍. Can you tell me how that bitwise trick works, I can't quite wrap my head around it.
• user228914: @GuyontheInternet You can read this, it will help :)