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{}
}
```

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.