Implementation of a queue

Question

It's been nearly a year I've been using C++, and I have just implemented this queue. I've tested it in many different scenarios, and it seems to work completely fine. Would you mind telling me what can be improved? What techniques might and might not be used in a professional scenario? In general, could you please give me your opinions so that I can improve my skills?

// --- Implementation of an exception class
class E: public std::exception{

    const char * _msg = "Default Exception.";
    E(){};

public:
    E(const char * message) throw() { this->_msg = message; }
    const char * what() const throw(){ return this->_msg; }
};

// --- Implementation of a queue.
template <typename T> class Queue {

    static const int _defaultSize = 10;
    static const int _maxSize = 1000;
    int _size;
    int _currentSize = 0;

    T * _queuePointer;
    int _firstInQueue = -1;                             // Holds the index of the first item in the queue (the item that should be popped).
    int _lastIndex = -1;                                // Holds the index that we have just pushed a new element to. ("last index to have an element being added to")

public:
    // Constructors and Destructors
    Queue(int sz=_defaultSize);                         // Default/Int Constructor Constructor
    Queue(const Queue & other);                         // Copy Constructor
    ~Queue();                                           // Destructor

    // Overloaded Assignment Operator
    Queue & operator = (const Queue rhs);               // To implement the copy-and-swap idiom

    // Utility Functions
    void swap(Queue & rhs);
    T enqueue(const T & node);
    T dequeue();
    bool isFull() const { return (this->getCurrentSize() == this->getSize()); };
    bool isEmpty() const { return (!this->getCurrentSize()); };

    // Getters/Accessors
    int getCurrentSize() const { return this->_currentSize; }
    int getSize() const { return this->_size; }

};

// Implementation of Constructors and Destructors
template <typename T> Queue<T>::Queue(int sz){

    if (sz < 1 || sz > _maxSize){
        // Invalid 'sz' argument value.
        throw E("Queue Exception: Invalid size argument value.");
    }else {
        std::cout << "Created Object (Default/Int Constructor)" << std::endl;
        this->_size = sz;
        this->_queuePointer = new T[this->_size];
    }
}

template <typename T> Queue<T>::Queue(const Queue<T> & other){
    this->_size = other._size;
    this->_currentSize = other._currentSize;
    this->_lastIndex = other._lastIndex;
    this->_queuePointer = new T[this->_size];

    for(int i=0; i < this->_size; i++){
        this->_queuePointer[i] = other._queuePointer[i];
    }
}

template <typename T> Queue<T>::~Queue(){
    delete [] this->_queuePointer;
}

// Implementation Of The Overloaded Assignment Operator
template <typename T> Queue<T> & Queue<T>::operator = (Queue<T> rhs){ // So that I can use the copy-and-swap idiom.
    this->swap(rhs);
    return *this;
}

// Implementation of Utility Functions
template <typename T> void Queue<T>::swap(Queue<T> & rhs){
    std::swap(this->_size, rhs._size);
    std::swap(this->_currentSize, rhs._currentSize);
    std::swap(this->_lastIndex, rhs._lastIndex);

    /*
     As I am assigning, it means that dynamic memory was
     allocated for the lhs object. So, before copying the
     content of the rhs to the lhs object, let's delete
     the allocated memory from the lhs object and allocate
     again based on the new size.
    */
    delete [] this->_queuePointer;
    this->_queuePointer = new T[this->_size];

    for(int i=0; i < this->_size; i++){
        this->_queuePointer[i] = rhs._queuePointer[i];
    }
}

template <typename T> T Queue<T>::enqueue(const T & node){

    if(this->isFull()){

        // The queue is full.
        throw E("Queue Exception: Your queue is full! You can't push anymore until you pop something.");
    }else {
        // The queue is not full.

        if(this->_firstInQueue == -1){
            // If it is the first item being pushed to the queue.
            this->_firstInQueue++; // The first in queue is now index 0.
        }

        // This if statement will just be executed if I push another node, and the last
        // node I added was at the last position of the queue.
        if(this->_lastIndex == (this->getSize() - 1)){
            // If the last index is at the last position of the queue,
            // set the last index to -1 again.
            this->_lastIndex = -1;
        }

        // Increasing index to the index number that we should add the new element.
        this->_lastIndex++;

        // Pushing element here (with respect to/using lastindex)...
        this->_queuePointer[this->_lastIndex] = node;

        // Increasing the current size of the queue.
        this->_currentSize++;
    }
    return (this->_queuePointer[this->_lastIndex]);
}

template <typename T> T Queue<T>::dequeue(){

    if(this->isEmpty()){
        // The queue is empty.
        throw E("Queue Exception: Your queue is empty. There is nothing to pop!");
    }

    // The queue is not empty.
    T value_to_be_returned = this->_queuePointer[this->_firstInQueue];

    if(this->_currentSize == 1){
        // If the queue has just one element and this element is at index 0.

        // Setting the index of the first in the queue to -1, because I am popping the
        // last element of the queue. Now, if I push a new element after popping this last one,
        // the element being pushed will be first in the queue, and its index will be 0.
        this->_firstInQueue = -1; // The first in queue is now back to index -1.

        // Returning the last index to -1, so that when the new item is pushed, the last index will be 0.
        this->_lastIndex = -1;

        // OBS: fiq and the li must ALWAYS go back to their initial values, -1, if all
        // the values are popped from the queue.
    }else {

        // Increasing index.
        // This if statement will just be executed if the first element in the queue
        // is at the last position of the queue. If so, we need to set the first in queue
        // variable to -1 again, and then increase it to 0, so that the next element first
        // in the queue is at index 0.
        if (this->_firstInQueue == (this->getSize() - 1)){
            this->_firstInQueue = -1;
        }

        this->_firstInQueue++;
    }

    // Decreasing queue's current size.
    this->_currentSize--;

    return value_to_be_returned;
}

Answer 1

I see a number of things that may help you improve your code.

Use the required #includes

The code uses std::exception, std::cout and std::swap but the corresponding headers are not listed. It was not difficult to infer, but it helps reviewers if the code is complete. The code should have these three lines:

#include <exception>
#include <iostream>
#include <utility>

Fix the bugs

There are some problems with the operator = implementation and friends. First, the copy does not initialize the _firstInQueue member. Since its default value is -1, subsequent calls to functions such as dequeue will attempt to access out-of-bounds memory which is undefined behavior. Second, the loop that copies pointers marches through the indices up to this->_size, but fails to account for the possibility that, say, Q1 is larger than Q2.

Don't use this-> everywhere

Within member functions, this-> is implied, so writing it out everywhere just needlessly clutters the code. Every instance of this-> in this code can safely be deleted.

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl. With that said, in this code, I think the entire line of code should be deleted since it appears to simply be debugging help.

return is not a function

Since return is a keyword and not a function, it does not need parentheses for any argument that may follow. So instead of this:

bool isEmpty() const { return (!getCurrentSize()); };

I would write this:

bool isEmpty() const { return !getCurrentSize(); }

Note also that the trailing semicolon is not necessary.

Answer 2

The Exception Class

I won’t repeat what Edward noted, except to add that putting extra parens around the return expression will bite you some day, so there is now (since C++17) a good reason other than style to not do that.

class E: public std::exception{

    const char * _msg = "Default Exception.";
    E(){};

public:
    E(const char * message) throw() { this->_msg = message; }
    const char * what() const throw(){ return this->_msg; }
};

Normal style is to group the pointer (or ref) indicator close to the type:

const char* message

In the constructor, use the initialization list, not assignment in the body!

You are letting _msg default initialize, and then changing it with the assignment.

E(const char* message) noexcept :_msg{message} { }

Hmm, you don’t have a default constructor, so the "Default Exception." will never be used. Make

E() noexcept { }

public (not private) and now the default will serve its purpose.

Meanwhile, throw() exception specifications have gone away! But, throw() with an empty param list will continue to be accepted as a synonym for noexcept for a few years. That is for ease in upgrading the compiler in old codebases, not for writing new code.

Your base class already declares a virtual function for what. You probably mean to override this, and maybe you are. Maybe you’re not, if the signature is not exactly the same! That is an insidious bug to have, so be glad that we now have the override keyword which makes your intention clear. If you botch the signature, the compiler will tell you that it doesn’t match.

const char* what() const noexcept  override  { return msg; }

I appreciate that this is one use where a plain old primitive C-string is just fine, even preferential — you want it to be non-throwing, so don’t want to involve the string class.

Now, back to the const char*. I agree that the “old fashioned” type is fitting and proper here, but you can still express it better using up-to-date idioms. See ⧺F.25 (and look over the Standard Guidelines in general!)

So write

    gsl::zstring _msg = "Default Exception.";

    E (gsl::zstring message) ⋯

Answer 3

The Queue class

static const int _defaultSize = 10;
static const int _maxSize = 1000;

It’s been said that “constexpr is the new static const.” In general, change these where you can.

constexpr int _defaultSize = 10;
constexpr int _maxSize = 1000;

---

Writing identifiers with a leading underscore is a bad idea, and is generally dissuaded as a style. Note that it is legal for member names if (and only if) the next character is not a capital letter or another underscore.

---

T * _queuePointer;

See ⧺R.20.

unique_ptr<T[]> queuePointer;

Then, in the constructor:

template <typename T> 
Queue<T>::Queue(int sz) {
    ⋮
    this->_queuePointer = new T[this->_size];

you should (1) use member initialization list; (2) don’t use naked new (⧺C.149).

template <typename T> 
Queue<T>::Queue(int sz)
    : size{ensure_range(sz, 1,_maxsize)}, 
      queuePointer{make_unique<T[]>(sz)}
    { }

The trouble is that I had to cram the range checking in there before doing the allocation. But, writing a separate ensure_range (value, high, low) function is general purpose and reusable!

---

On to the copy constructor.

for(int i=0; i < this->_size; i++){
    this->_queuePointer[i] = other._queuePointer[i];
}

Use the std::copy algorithm instead. (Note that the supplied collections like vector are even more efficient, and copy-construct the elements that exist rather than default construct and then assign.)

---

Destructor:

By making the pointer a unique_ptr, this now goes away completely. Don’t declare or write it! The auto-generated one is better.

---

The swap member function re-allocates and copies the buffer? It also appears to leave the rhs object’s buffer unchanged, rather than switching it to the other one. That is not right, and the comments “As I am assigning…” makes me think you got your wires crossed.

It is important to have a nothrow swap function. It should just switch the pointers just like it switched the sizes and index.

---

I suppose you are doing this as an exercise for various reasons. But if you really just wanted a queue, just write:

template <typename T, size_t capacity>
using Queue = std::queue<T>;

A pre-allocated fixed capacity can be achieved by using an underlying collection with that behavior.

template <typename T, size_t capacity>
using Queue = std::queue<T, boost::container::static_vector<T,capacity>>;

---

Good show, though! Keep up with your study!

Answer 4

Lack of comments

I find it very helpful for each function to have a comment that specifies exactly what it does, what guarantees it provides, and what kind of input will cause it to fail. Some people like to put this comment just above the implementation of the function (not inside); I prefer it just prior to the function declaration in the header, formatted so that a tool like doxygen can use it to automatically generate documentation. In any case, the comment is a statement of the function's contract.

Destructor

If there is any possibility that someone might try to derive another class from Queue, the destructor should be virtual. I would assume the possibility exists.

Copy constructor

In the copy constructor, you assign _queuePointer without deleting the old array. That's a memory leak.

swap()

It is not clear why you don't just swap the pointers of the two queues in the implementation of swap(). As you have it, you write a lot of extra code, you lose the contents of this, and you leave rhs in a possibly inconsistent state. I realize this has no effect on the the particular use you made of swap() in operator =(), but if anyone tries to use this function for an actual swap it's likely to work very badly for them. Since you implemented this function (and even made it public), you should make it conform to the reasonable expectations people might have, especially since the expected behavior is easier to implement and more efficient.

C-style array

There is no real need to use T*, and it has gotten you in trouble (see the last couple of items). You could at least use an std::array<T>, perhaps even std::vector<T>, and take advantage of convenient features such as their swap() and operator =() functions. This makes your code simpler and lets you worry a lot less about possible memory leaks; the template cleans up after itself.

E

Several useful remarks about Queue::E have already been posted. I will try not to duplicate them.

Using E as the name of an exception class seems a bit obscure. In fact, it is not clear why you create your own subclass of std::exception at all, unless the reason is to avoid having to distinguish between such things as std::logic_error and std::runtime_error, both of which in effect offer the same constructor-with-C-string and what() function that your class has.

If the reason is to practice making exception classes, then you might try to make the exception provide something the standard exception classes don't, such as identifying a specific problem that can occur in a queue.

Dynamic allocation

For certain embedded applications, an explicit (not very large) maximum size may make sense. But in many such applications, dynamic allocation is frowned upon (to put it mildly). So it is not clear why you have such a low upper limit on the queue size (or indeed any limit at all) when you're willing to risk calling new.

It might be interesting to write a queue class that can grow dynamically like std::vector can.