复制列表时光荣崩溃

Question

所以我准备把我的电脑从窗户里扔出来,而我现在已经到了我想要在销毁昂贵的设备之前寻求帮助的地步.

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

赋值运算符会使程序崩溃,但如果我将它注释掉以便让它进入复制构造函数,那么列表就会变空.

任何说"TODO"你都可以忽略的东西,我注意到后来要修复.

这是所有动作发生的地方:

List.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类的制作地点,如果需要这样的话

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未初始化,但在调试版本中,此检查可能始终为true.无论哪种方式,因为你实际上并没有复制任何节点,只是_pData,结果列表将是空的(_pData可能被设置除外).

在您的赋值运算符中,在该行之前_pData = new char[strlen(str._pData) + 1];您无法检查str._pData实际是否指向任何内容.如果它没有,你基本上在做strlen(0),那就是它崩溃和烧伤的地方.

我的建议是正确实现你的拷贝构造函数.一个实际上做深拷贝,然后为你的赋值运算符实现复制和交换习惯用法.

编辑:示例

下面的源代码实现了问题中列表类的一个小子集,以演示深度复制构造函数和使用上面段落中提到的复制和交换习惯用法的赋值运算符.

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

在您的情况下,列表是双重链接.如果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;
}

为什么赋值运算符和交换函数是它们的解释方式比上面描述复制和交换习语的答案要好得多.这让我们得到了复制构造函数的实现.我们一行一行地看一下.

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. 我们的拷贝构造函数引用了一个const列表.我们保证不会改变它.
2. 我们初始化自己的成员.既然data不是指针,我们也可以将它复制到初始化程序中.
3. 是的,我必须添加此行以进行正确的降价编号.
4. 如果其他列表为空,我们就在这里完成.没有理由检查我们刚构建的列表是否为空.显然是.
5. 对于另一个列表中的每个节点...(抱歉,再次降价语法,不让我很好地结合5和6).
6. ......我们创造了一个新的.如上所述,Node在这个例子中没有复制构造函数,所以我们只使用我们的PushBack方法.
7. 为了完整起见,但这条线是完全明显的.

以这种方式循环其他列表中的节点并不是最好的.您应该更喜欢使用迭代器和调用PushBack(*iter).