Queue Implementation in C++ [closed]

Question

When reviewing my code, please consider these questions too:

1. Any way to avoid using new/delete? Or are data structures like that normally and can't really use smart pointers? I was thinking of using shared pointers or unique pointers but they seem odd to use in this case.

2. Recursion in a constructor? Good or bad?

3. Copy constructor should be deleted for Node? Because you copy the pointer to next otherwise. Copy of the nodes should be done by Queue instead?

queue.h

#ifndef H_UTILS_QUEUE_H
#define H_UTILS_QUEUE_H

#include <stdexcept>


namespace Utils {

template<class T>
class Queue {

private:

    //  Node
    class Node {
    public:
        explicit Node(const T& data, Node* next);
        explicit Node(T&& data, Node* next);
        Node(const Node& other);
        Node(Node&& other) noexcept;

        Node& operator=(Node other) noexcept;

    private:
        void swap(Node& other) noexcept;

    public:
        T mData;
        Node* mNext;

    };  //  Node

public:
    Queue();
    Queue(const Queue<T>& other);
    Queue(Queue<T>&& other) noexcept;

    Queue<T>& operator=(Queue<T> other) noexcept;

    T& front();
    void pop_front() noexcept;
    void push_front(const T& data);
    void push_back(const T& data);
    void push_back(T&& data);

private:
    void swap(Queue<T>& other) noexcept;
    Node* deepCopy(Node* node);

private:
    Node* mHead;

};  //  Queue


//  Node
template<class T>
Queue<T>::Node::Node(const T& data, typename Queue<T>::Node* next)
    : mData(data)
    , mNext(next)
{

}

template<class T>
Queue<T>::Node::Node(T&& data, typename Queue<T>::Node* next)
    : mData(std::move(data))
    , mNext(next)
{

}

template<class T>
Queue<T>::Node::Node(typename const Queue<T>::Node& other)
    : mData()
    , mNext(nullptr)
{
    mData = other.mData;
    mNext = other.mNext;
}

template<class T>
Queue<T>::Node::Node(typename Queue<T>::Node&& other) noexcept
    : mData()
    , mNext(nullptr)
{
    swap(other);
}

template<class T>
typename Queue<T>::Node& Queue<T>::Node::operator=(typename Queue<T>::Node other) noexcept
{
    if (this != &other) {
        swap(node);
    }

    return *this
}

template<class T>
void Queue<T>::Node::swap(typename Queue<T>::Node& other) noexcept
{
    using std::swap;
    swap(mData, other.mData);
    swap(mNext, other.mNext);
}


//  Queue
template<class T>
Queue<T>::Queue()
    : mHead(nullptr)
{

}

template<class T>
Queue<T>::Queue(const Queue<T>& other)
    : mHead(nullptr)
{
    if (other.mHead) {
        mHead = deepCopy(other.mHead);
    }
}

template<class T>
Queue<T>::Queue(Queue<T>&& other) noexcept
    : mHead(nullptr)
{
    swap(other);
}

template<class T>
Queue<T>& Queue<T>::operator=(Queue<T> other) noexcept
{
    if (this != &other) {
        swap(other);
    }

    return *this;
}

template<class T>
void Queue<T>::swap(Queue<T>& other) noexcept
{
    using std::swap;
    swap(mHead, other.mHead);
}

template<class T>
typename Queue<T>::Node* Queue<T>::deepCopy(typename Queue<T>::Node* node)
{
    if (node->mNext == nullptr) {
        //  at tail

        //  if an exception is thrown here allow it to progate out of this function
        //  to be handled by the calling code
        //  no memory will be leaked
        return new Node(node->mData, nullptr);
    }

    Node* next = deepCopy(node->mNext);
    Node* current = nullptr;

    try {
        current = new Node(node->mData, next);
    } catch (...) {
        //  something went wrong
        //  recursively deallocate any nodes that have been allocated up to this point
        Node* i = next;
        while (i) {
            Node* copy = i->mNext;
            delete i;
            i = copy;
        }
    }

    return current;
}

template<class T>
T& Queue<T>::front()
{
    if (mHead) {
        return mHead->mData;
    } else {
        throw std::logic_error("trying to get front of empty queue");
    }
}

template<class T>
void Queue<T>::pop_front() noexcept
{
    if (mHead) {
        Node* newHead = mHead->mNext;
        Node* oldHead = mHead;
        mHead = newHead;
        delete oldHead;
    } 
}

template<class T>
void Queue<T>::push_front(const T& data)
{   
    try {
        Node* prevHead = mHead;
        Node* newHead = new Node(data, prevHead);
        //  only once we successfully get to this stage do we set the head pointer
        mHead = newHead;
    } catch (...) {
        //  something went wrong
        //  queue still in same state it was before call to push_back

        //  let the caller handle the exception
        throw;
    }
}

template<class T>
void Queue<T>::push_back(const T& data)
{
    //  find the tail
    Node* tail = mHead;
    while (tail) {
        if (tail->mNext == nullptr) break;

        tail = tail->mNext;
    }

    if (tail) {
        Node* newHead = nullptr;

        try {
            newHead = new Node(data, nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        tail->mNext = newHead;
    } else {
        Node* newHead = nullptr;

        try {
            newHead = new Node(data, nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        mHead = newHead;
    }

}

template<class T>
void Queue<T>::push_back(T&& data)
{
    //  find the tail
    Node* tail = mHead;
    while (tail) {
        if (tail->mNext == nullptr) break;

        tail = tail->mNext;
    }

    if (tail) {
        Node* newHead = nullptr;

        try {
            newHead = new Node(std::move(data), nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        tail->mNext = newHead;
    }
    else {
        Node* newHead = nullptr;

        try {
            newHead = new Node(std::move(data), nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        mHead = newHead;
    }

}



}  //  Utils


#endif  //  UTILS_QUEUE

main.cpp

#include <iostream>
#include "queue.h"

using Utils::Queue;

int main()
{
    {
        Queue<char> charQueue;

        charQueue.push_back('a');
        char b = 'b';
        charQueue.push_back(b);
        charQueue.push_back('c');
        charQueue.push_back('d');
        charQueue.push_back('e');
        charQueue.push_back('f');
        charQueue.push_back('g');
        charQueue.push_back('h');
        charQueue.push_back('i');
        charQueue.push_back('j');
        charQueue.push_back('k');
        charQueue.push_back('l');
        charQueue.push_back('m');

        for (std::size_t i = 0; i < 13; ++i) {
            std::cout << charQueue.front() << "\n";
            charQueue.pop_front();
        }
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b(a);
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b(std::move(a));
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b;

        b = a;
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b;

        b = std::move(a);
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        try {
            for (std::size_t i = 0; i < 10; ++i) {
                a.front();
                a.pop_front();
            }       
        } catch (std::exception& e) {
            std::cout << "Caught Exception " << e.what() << "\n";
        }
    }


    std::cin.get();

}

Answer 1

Regarding your explicit questions:

1. Well, you can avoid explicit raw use of memory-allocation by using smart-pointers, or if you bound the size of the queue you can alloate all nodes as part of the queue itself.
   Your choice, but for the first it is fairly common to eschew such comforts in the implementation of basic abstractions to reduce dependencies and allow and for maximal control.
   For the second, that's basically a different data-structure.

2. All else being equal, try to keep the stack small. Recursion can potentially overflow the stack in the absence of tail-call-optimization, so that must be taken into account. If that's not a danger, use the most elegant option which is reasonably efficient (generic library-code should take extra care with efficiency).

3. Generally, I would avoid trying to go all-out OOifying internal helper classes. Remember that doing so restricts using code from doing useful things, makes them unnatural and convoluted, and generally leads to bloat.
   The optimal definition for a node-class is imho:

   struct node { node* next; T data; };
   

   Use aggregate-initialization for creating nodes.

   That way there is no bloated artifical interface between it and the owning parent-class getting in the way of conciseness and efficiency, which provides all the consumer-facing options for manipulation anyway.

   The only thing to consider is whether you want to use a std::unique_ptr<node> for next instead.

And now, reviewing everything not yet mentioned:

4. Generally, you make reasonably sure that a header is self-contained by including it first in the corresponding implementation-file.
   That's the one weak point of having a header-only library, there's no source-file which naturally does that check, so it must be done manually.

5. If you stream a single-character-string, consider streaming a character instead. It might be slightly more efficient.

6. Node should either be an aggregate without any customization, or not support copy-/move- construction, assignment and certainly .swap().
   Anyway you look at it, declaring the operations you did noexcept unconditionally is an error, as not all T's support that guarantee.

7. If you insist on having member-function .swap(other), at least make it public. Though it would be far more useful to simply define friend void swap(a, b) instead, as that will be picked up by generic code.

8. You really only need to do a deep-copy in the copy-ctor, which does only that. As such, extracting that into its own function does not buy you anything. Actually, it means you have to duplicate the cleanup-code already in the dtor.

9. You should define template<class... X> void emplace_back(X&&... x) and define the two push-variants in terms of that, equivalently for emplace_front(). That allows you to remove much code-duplication and gets you a more efficient and versatile interface.

10. Don't guard against self-assignment. Aside from the fact that it is trivial to prove that this and &other are distinct as other was passed by value, a copy-and-swap already works correctly and pessimizing the common case is a bad idea.

11. Don't catch exceptions just to rethrow them. Doing so might look like the compiler should be able to optimize it out, but that's not really always the case.

12. Try to avoid special cases. Double-indirection is not rocket science.
    As an example, inserting a new node at the end:

    auto p = &head;
    while (*p)
        p = &p->next;
    *p = new Node{...};
    

Answer 2

First off all, let's answer your questions:

1. Well, you could make this work using std::unique_ptr. However, since you are implementing a quite low-level memory structure, I'm not sure I would suggest it here. In general, smart pointer usage is preferable to raw pointers; however, in a case like this where you have to manipulate the pointers themselves a lot (as opposed to the data they are pointing to), smart pointers tend to be somewhat clumsy and ill fitted. However, you should definitely make sure that you are doing memory management correctly (using static analysis as well as runtime analyzers such as valgrind, asan, msan etc.).
2. There's nothing inherently bad about using recursion in a constructor.

3. There are two different approaches to the copy problem. One is to treat Node as a dumb, struct-like class that does not much more than combining a piece of data with a pointer to the next node. In that case, it is fine to make copying nodes correctly the responsibility of Queue.

   The other approach is treating Nodes more like "smart" objects which have some ingrained behavior, in which case copying should be defined through the Node class.

   I personally prefer the latter, because it plays well with the C++ approach to OOP, and lifts some responsibility from Queue. However, I would not say that the other approach is wrong, I just don't like it as much because it makes the overall burden on Queue heavier.

You queue is nearly useless

Harsh words. Why do I say something like this?

The answer is: You only offer two methods to access elements. While this is conforming to the most basic definition of a queue, it's not very useful in everyday programming.

At the very least, you should add an iterator interface, which would also allow your queue to interact with most standard algorithms and increase usability by a huge margin.

Also, you should add some type definitions to conform to the standard's container library requirements.

Some other things

1. Fix your includes. Now. You need #include <utility> for both std::move and std::swap, otherwise your code might not compile.
2. Adhere to the rule of five. Queue defines a copy and a move constructor as well as a copy assignment operator, so it should define a move assignment operator and a destructor as well. The same is true for Node, if you want to follow my suggestion for question 3. If not, you should remove the special member functions altogether.
3. Related to point 2: Since you are not defining a destructor, you are leaking memory everywhere. Fix this immediately.
4. Copy assignment operators should take their argument by const reference. If you take the other object by value, you incur an unnecessary copy, which is quite costly for a container class.
5. Instead of manually writing out the default constructor for Queue, you should add a member initializer to mHead (i.e. Node* mHead = nullptr;) and just = default the default constructor.
6. When writing single chars to std::cout, use 'c' instead of "c" (in particular, this applies to your use of "\n"). The latter is likely to cause performance degradation.