c++ 模板队列的嵌套初始化 class

Question

嘿，我创建了这个模板化队列 class，它适用于所有类型，除了出于某种原因嵌套在自身中。

这是队列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

这是我想要做的：

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

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

tst2.Enqueue(tst);

一切都可以编译，但程序在运行时崩溃。怎么回事！？

Answer 1

一个明显的错误是您使用的类型 T 无法安全复制。

你这样做：

void Enqueue(T data_);

但是如果类型 T 是 Queue<int>，您认为 data_ 会发生什么？制作了副本，但您的 Queue 模板 class 没有正确的副本语义。它缺少 user-defined 复制构造函数和赋值运算符。

崩溃发生在 tst2 的析构函数中，因为这是一个 Queue<Queue<int>>，并且在析构函数调用 tst2.Enqueue(tst); 之前，您已经清理了内存。一旦你调用它，你就死了（或将死）。

你在多个地方有相同的错误，那就是你正在复制不可安全复制的对象。

示例：

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

如果 data_ 是 Queue<int>，那么你又一次陷入困境，因为将 Queue<int> 分配给 Queue<int> 是 no-go.

因此解决此问题的方法是让您的 Queue class 实施 Rule of 3 以确保副本有效。您需要实现这些功能：

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

另外，用这样的案例进行测试：

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

当 main 退出时，这样的程序不应该崩溃、显示内存泄漏等迹象。如果是，那么你没有正确实现复制。

c++ 模板队列的嵌套初始化 class

c++ nested initialization of template queue class

c++

queue

templates

nested

multidimensional-array