c++ nested initialization of template queue class

Question

Hey I have created this templated Queue class that works for all types except for nesting within itself for some reason.

Here is the queue class:

#ifndef QUEUE_H
#define QUEUE_H

//Queue node class.
template <class T>
class QueueNode
{
    public:
        T m_Data;
        QueueNode *m_NextNode;
        QueueNode(const T data_, QueueNode *nextValue_ = NULL)
        {
            m_Data = data_;
            m_NextNode = nextValue_;
        }
        QueueNode(QueueNode *nextValue_ = NULL)
        {
            m_NextNode = nextValue_;
        }
};

//Queue class.
template <class T>
class Queue
{
    public:
        ////////////////////////////////////////////////////////////
        // CONSTRUCTORS AND DESTRUCTORS
        ////////////////////////////////////////////////////////////
        Queue();
        ~Queue();

        ////////////////////////////////////////////////////////////
        // Error Codes
        ////////////////////////////////////////////////////////////
        enum ERC_QUEUE
        {
            ERC_NO_ERROR,
            ERC_QUEUE_EMPTY
        };

        ////////////////////////////////////////////////////////////
        // METHODS
        ////////////////////////////////////////////////////////////
        //Check if queue is empty.
        bool IsEmpty();

        //Check if queue is empty.
        int GetQueueSize();

        //Clear the queue.
        void Clear();

        //Dequeue X nodes and delete them.
        //If there the requested number of nodes to delete exceeds the number of nodes in the actual list,
        //the function will return an empty list.
        void Queue<T>::FlushNodes(unsigned short numNodes);

        //Add an item to the end of the queue.
        void Enqueue(T data_);

        //Get an item from the front of the queue.
        ERC_QUEUE Dequeue(T &data_);

        //Get an item from the front of the queue without removing it.
        ERC_QUEUE Peek(T &data_);

    private:
        QueueNode<T> *m_Head;
        QueueNode<T> *m_Tail;
        int m_Size;
};


//Template implementation

template <class T>
Queue<T>::Queue()
    : m_Size(0)
{
    //Create empty queue with front and rear pointing to NULL.
    m_Head = m_Tail = NULL;
}

template <class T>
Queue<T>::~Queue()
{
    Clear();
}

template <class T>
bool Queue<T>::IsEmpty()
{
    //If front is NULL then the queue is empty.
    return m_Head == NULL;
}

template <class T>
int Queue<T>::GetQueueSize()
{
    return m_Size;
}

template <class T>
void Queue<T>::Clear()
{
    QueueNode<T> *tmp;

    //Go through each node until the end of the queue.
    while (m_Head != NULL)
    {
        //Point tmp to next node.
        tmp = m_Head->m_NextNode;

        //Delete current node.
        delete m_Head;

        //Point front to next node.
        m_Head = tmp;
    }

    m_Size = 0;
}

template <class T>
void Queue<T>::FlushNodes(unsigned short numNodes)
{
    QueueNode<T> *tmp;

    //Go through each node until the end of the queue or the number of requested
    //nodes to be removed have been removed.
    while (m_Head != NULL && numNodes != 0)
    {
        numNodes--;
        m_Size--;

        //Point tmp to next node.
        tmp = m_Head->m_NextNode;

        //Delete current node.
        delete m_Head;

        //Point front to next node.
        m_Head = tmp;
    }
}

template <class T>
void Queue<T>::Enqueue(T data_)
{
    //Create new node.
    QueueNode<T> *node = new QueueNode<T>(data_);
    m_Size++;

    //If queue is empty then point both front and rear to the new node.
    if (IsEmpty())
    {
        m_Head = m_Tail = node;
        return;
    }

    //Add node to the end of the queue and repoint rear to the new node.
    m_Tail->m_NextNode = node;
    m_Tail = node;
}

template <class T>
typename Queue<T>::ERC_QUEUE Queue<T>::Dequeue(T &data_)
{
    //If queue is empty return NULL.
    if (IsEmpty())
    {
        return Queue<T>::ERC_QUEUE_EMPTY;
    }

    //Save value from top node.
    data_ = m_Head->m_Data;

    //Point tmp to front.
    QueueNode<T> *tmp = m_Head;

    //Repoint front to the second node in the queue.
    m_Head = m_Head->m_NextNode;

    //Remove first node.
    delete tmp;

    //Update queue size.
    m_Size--;

    return Queue<T>::ERC_NO_ERROR;
}

template <class T>
typename Queue<T>::ERC_QUEUE Queue<T>::Peek(T &data_)
{
    //If queue is empty return NULL.
    if (IsEmpty())
    {
        return Queue<T>::ERC_QUEUE_EMPTY;
    }

    data_ = m_Head->m_Data;

    return Queue<T>::ERC_NO_ERROR;
}

#endif //QUEUE_H

Here is what I want to do:

Queue<int>          tst;
Queue<Queue<int>>   tst2;

tst.Enqueue(1);
tst.Enqueue(2);
tst.Enqueue(3);

tst2.Enqueue(tst);

Everything compiles, but the program crashes at run-time. what's the deal!?

Answer 1

The one glaring mistake is that you're using a type T that is not safely copyable.

You do this:

void Enqueue(T data_);

But if type T is a Queue<int>, what do you think happens to data_? A copy is made, and your Queue template class doesn't have correct copy semantics. It is missing a user-defined copy constructor and assignment operator.

The crash happens in the destructor of tst2 since this is a Queue<Queue<int>>, and you've hosed the memory way before the destructor call with the call to tst2.Enqueue(tst);. As soon as you called that, you're dead (or will be).

You have the same errors in multiple places, and that is you're copying objects that are not safely copyable.

Example:

//Save value from top node.
data_ = m_Head->m_Data;

If data_ is a Queue<int>, then again, you're dead in the water since assigning a Queue<int> to a Queue<int> is a no-go.

So the way to fix this is to have your Queue class implement the Rule of 3 to ensure that the copies work. You need to implement these functions:

Queue(const Queue& rhs);
Queue& operator=(const Queue& rhs);

Also, test with a case like this:

int main()
{
    Queue<int> q1;
    q1.Enqueue(10);
    Queue<int> q2;
    q2 = q1;
    Queue<int> q3 = q2;
}

A program like that should not crash, show signs of memory leakage, etc. when main exits. If it does, then you haven't implemented the copying correctly.