Glorious Crashing while copying lists

Question

So I'm about ready to toss my computer out of a window, and I'm now at the point where I figure I should ask for help before I destroy an expensive piece of equipment.

My program has a list that is filled in automatically (I manually input the items), and it just outputs it. Then, I have another block of code that is to output it again using assignment operators, and then a third copy with a copy constructor.

The assignment operator crashes the program, but if I comment it out to let it get to the copy constructor, the list comes out empty.

Anything that says "TODO" you can ignore, that's noted for me to fix later.

Here is where all the action happens:

List.cpp

(This is not my main function, there's nothing wrong there)

    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;
    }

EDIT: This is where the List class is made, if this needs to be seen as well

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

So here's what's happening:

In your copy constructor, you check whether the list is empty. The result of this check is undefined because m_pFront is uninitialized, but in a debug build, chances are that this check is always true. Either way, since you're not actually copying any nodes, but only _pData, the resulting list will be empty (with the exception of _pData maybe being set).

In your assignment operator, before the line _pData = new char[strlen(str._pData) + 1]; you fail to check if str._pData actually points to anything. If it doesn't and you're essentially doing strlen(0), that is where it crashes and burns.

My advice would be to get a proper implementation of your copy constructor. One that actually does a deep copy, and then implement the copy and swap idiom for your assignment operator.

EDIT: Example

The source code below implements a small subset of the list class from the question to demonstrate a deep copy constructor and an assignment operator using the copy and swap idiom mentioned in the paragraph above.

Before I show the source code, it is important to realize that deep copying a list is not easy. A number of things have to be considered. You have to make copies of the nodes. You probably want to make copies of the data. But maybe not deep copies. Or maybe your specific needs don't require a copy of the data at all.

In your case, the list is doubly linked. If Node had a copy constructor that does a naive deep copy you would probably end up with a stack overflow due to endless chaining of the copy constructor.

Here's an example of such a naive implementation.

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

In my example, I choose to not implement a copy constructor for Node for clarity. I choose to make copies of the data, which is in the form of std::string to match the question.

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;
}

Why the assignment operator and the swap function are the way they are is explained much better than I can in the aforementioned answer that describes the copy and swap idiom. That leaves us with the implementation of the copy constructor. Let's look at it line by line.

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. Our copy constructor takes a reference to a const list. We promise not to change it.
2. We initialize our own members. Since data is not a pointer we might as well copy it in the initializer.
3. Yeah, I have to add this line for proper markdown numbering.
4. If the other list is empty, we're done here. There is no reason to check whether the list we just constructed is empty. It obviously is.
5. For each node in the other list... (sorry, markdown syntax again, doesn't let me combine 5 and 6 nicely).
6. ...we create a new one. As explained above, there's no copy constructor for Node in this example, so we just use our PushBack method.
7. For completeness sake, but this line is totally obvious.

Looping over the nodes in the other list this way is not the nicest. You should prefer using an iterator and calling PushBack(*iter).