c++ - 复制列表时光荣崩溃

Question

所以我准备好把我的电脑扔出窗外，现在我觉得我应该在毁坏一台昂贵的设备之前寻求帮助。

我的程序有一个自动填写的列表(我手动输入项目)，它只是输出它。然后，我有另一个代码块是使用赋值运算符再次输出它，然后是带有复制构造函数的第三个拷贝。

赋值运算符会使程序崩溃，但如果我将其注释掉以让它到达复制构造函数，列表就会变成空的。

您可以忽略任何显示“TODO”的内容，我会在稍后修复。

这里是所有 Action 发生的地方:

列表.cpp

(这不是我的主要功能，那里没有错)

    List::List() : m_pFront(0), m_pBack(0), _pData(0)
    {}

    List::~List()
    {
        Clear();
    }    

    List::List(const char* p)
    {
        if(!p)
        {
            _pData = 0;
            return;
        }
        if(strlen(p) == 0)
        {
            _pData = 0;
            return;
        }
        _pData = new char[strlen(p) + 1];
        strcpy(_pData, p);
    }

    void List::Clear()
    {
        //delete 
        if(!m_pFront)
        {
            return;
        }
        delete m_pFront;
        Node* p = m_pBack;
        //Walking the list
        while(p)
        {
            //Get a pointer to the next in the list
            Node* pTemp = p -> m_pNext;
            delete p;
            //Move p along the list
            p = pTemp;
        }
        m_pFront = 0;
        m_pBack = 0;
    }

    void List::PushFront(std::string data)
    {
        //create a new node
        Node* p = new Node(data);

        //Empty list    
        if(!m_pFront)
        {
            m_pFront = p;
            m_pBack = p;
        }
        else //Not empty list
        {
            p -> m_pNext = m_pFront;
            m_pFront -> m_pPrev = p;
            m_pFront = p;
        }
    }

    void List::PushBack(std::string data)
    {
        Node* p =  new Node(data);

        if(!m_pBack)
        {
            m_pFront = p;
            m_pBack = p;        
        }
        else
        {
            p -> m_pPrev = m_pBack;
            m_pBack -> m_pNext = p;
            m_pBack = p;
        }       
    }    

    void List::PopFront()
    {
        if(m_pFront == 0)
        {
            //TODO: we need to handle this problem
            return;
        }
        if(m_pBack == m_pFront)
        {
            Clear();
            return;
        }
        Node* p = m_pFront;
        m_pFront = m_pFront -> m_pNext;
        p -> m_pNext = 0;
        m_pFront -> m_pPrev = 0;    
        delete p;
    }

    void List::PopBack()
    {
        if(m_pBack == 0)
        {
            //TODO: we need to handle this problem
            return;
        }
        if(m_pBack == m_pFront)
        {
            Clear();
            return;
        }
        Node* p = m_pBack;
        m_pBack = m_pBack -> m_pPrev;
        p -> m_pPrev = 0;
        m_pBack -> m_pNext = 0;
        delete p;
    }


    ostream& List::OutPut(ostream& os)
    {
        if(Empty() == true)
        {
            os << "<empty>";
        }
        else
        {
            m_pFront -> OutputNode(os);
        }
        return os;    
    }    


    std::string& List::Back() const
    {
        if(m_pBack == 0)
        {
            //TODO: we need to handle this problem
        }
        return m_pBack -> GetData();
    }

    std::string& List::Front() const
    {
        if(m_pFront == 0)
        {
            //TODO: we need to handle this problem
        }
    return m_pFront -> GetData();  
    }

    //Copy Constructor
    List::List(const List& str)
    {
        if(Empty() == true)
        {
            _pData = 0;
            return;
        }
        _pData = new char[strlen(str._pData) + 1];
        strcpy(_pData, str._pData);
    }
    //Deep copy
    List& List::operator=(const List& str)
    {
        if(&str == this)
        {
            return *this;
        }
        delete [] _pData;
        _pData = new char[strlen(str._pData) + 1];
        strcpy(_pData, str._pData);
        return *this;
    }

编辑:如果还需要查看，这是创建 List 类的地方

列表.h

class List
{
    public:
        List();
        List(const char* p);
        //Copy constructor
        List(const List& str);
        //Deep Copy
        List& operator=(const List& str);
        ~List();
        void Clear();
        //Adds to the front 
        void PushFront(std::string data);
        //adds to the back
        void PushBack(std::string data);
        //removes from the front
        void PopFront();
        //removes from the back
        void PopBack();
        //gets the back value
        std::string& Back() const;
        //gets the from value
        std::string& Front() const;

        bool Empty() const {return m_pFront == 0;}

        ostream& OutPut(ostream& os);

    private:    
        Node* m_pFront;
        Node* m_pBack;
        char* _pData;

    };

Answer 1

这就是发生的事情:

在你的复制构造函数中，你检查列表是否为空。此检查的结果未定义，因为 m_pFront 未初始化，但在调试版本中，此检查可能始终为真。无论哪种方式，由于您实际上并没有复制任何节点，而只是复制了 _pData，因此结果列表将为空(可能设置了 _pData 除外)。

在您的赋值运算符中，在行 _pData = new char[strlen(str._pData) + 1]; 之前，您无法检查 str._pData 是否实际指向任何事情。如果它没有，而您实际上是在执行 strlen(0)，那么它就会崩溃和燃烧。

我的建议是正确实现复制构造函数。一个实际上做深拷贝，然后实现 copy and swap idiom为您的赋值运算符。

编辑:示例

下面的源代码实现了问题中列表类的一个小子集，以演示使用上一段中提到的 copy-and-swap 习惯用法的深层复制构造函数和赋值运算符。

在展示源代码之前，重要的是要认识到深度复制列表并不容易。必须考虑很多事情。您必须制作节点的拷贝。您可能想要制作数据的拷贝。但也许不是深拷贝。或者您的特定需求可能根本不需要数据拷贝。

在您的例子中，列表是双向链接的。如果 Node 有一个复制构造函数来执行简单的深度复制，那么由于复制构造函数的无限链接，您可能最终会导致堆栈溢出。

这是一个这种天真的实现的例子。

Node(const Node &other) 
{
    if (other.next) 
        next = new Node(*other.next);
    if (other.prev) 
        prev = new Node(*other.prev);
}

在我的示例中，为了清楚起见，我选择不为 Node 实现复制构造函数。我选择复制数据，其形式为 std::string 以匹配问题。

list.h

#ifndef LIST_EXAMPLE_H_
#define LIST_EXAMPLE_H_

#include <string>

struct Node
{
    std::string data;
    Node *next, *prev;
    Node(const std::string &d) 
        : next(0), prev(0), data(d)
    {
    }
};

class List
{
    Node *front;
    Node *back;
    std::string data;

public:
    List();
    List(const std::string &);
    List(const List &);
    ~List();

    List& operator=(List);

    void Clear();
    void PushBack(const std::string&);

    bool Empty() const { return front == 0; }

    friend void swap(List &, List &);

    void Print();
};

#endif // LIST_EXAMPLE_H_

list.cc

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

List::List()
    : front(0), back(0), data()
{
}

List::List(const std::string &in)
    : front(0), back(0), data(in)
{
}

List::~List()
{
    Clear();
}

List::List(const List &other)
    : front(0), back(0), data(other.data)
{
    if (!other.Empty())
        for (Node *node = other.front; node; node = node->next) 
            PushBack(node->data);
}

List& List::operator=(List other)
{
    swap(*this, other);
    return *this;
}

void List::Clear()
{
    Node *node = front;
    while (node) {
        Node *to_delete = node;
        node = node->next;
        delete to_delete;
    }
    front = back = 0;
}

void List::PushBack(const std::string &data)
{
    Node *node = new Node(data);
    if (Empty()) {
        front = back = node;
    } else {
        back->next = node;
        node->prev = back;
        back = node;
    }
}

void List::Print()
{
    std::cout << data << std::endl;
    for (Node *node = front; node; node = node->next)
        std::cout << node->data << std::endl;
    std::cout << std::endl;
}

void swap(List &first, List &second)
{
    using std::swap;
    swap(first.front, second.front);
    swap(first.back, second.back);
    swap(first.data, second.data);
}

int main()
{
    List a("foo");
    a.PushBack("a");
    a.PushBack("b");
    a.PushBack("c");
    a.Print();

    List b("bar");
    b.PushBack("d");
    b.PushBack("e");
    b.PushBack("f");

    List c(b);
    c.Print();

    c = a;
    c.Print();
    a.Print();

    return 0;
}

为什么赋值运算符和交换函数是这样的，在上述描述 copy and swap idiom 的答案中比我能解释得更好。 .这给我们留下了复制构造函数的实现。让我们逐行查看。

1. List::List(const List &other)
2.     : front(0), back(0), data(other.data)
3. {
4.     if (!other.Empty())
5.         for (Node *node = other.front; node; node = node->next) 
6.             PushBack(node->data);
7. }

1. 我们的复制构造函数引用了一个常量列表。我们保证不会更改它。
2. 我们初始化自己的成员。由于 data 不是指针，我们不妨将其复制到初始化程序中。
3. 是的，我必须添加这一行才能正确标记编号。
4. 如果另一个列表是空的，我们到这里就完成了。没有理由检查我们刚刚构建的列表是否为空。显然是。
5. 对于另一个列表中的每个节点...(抱歉，又是 markdown 语法，不能让我很好地组合 5 和 6)。
6. ...我们创造了一个新的。如上所述，此示例中的 Node 没有复制构造函数，因此我们仅使用我们的 PushBack 方法。
7. 为了完整起见，这条线非常明显。

以这种方式遍历另一个列表中的节点并不是最好的。您应该更喜欢使用迭代器并调用 PushBack(*iter)。