Assignment Operator for singly linked list with dynamic allocation in C++ (MS Visual Studio 2015)

Question

Two classes, one for the nodes, one for the singly linked list.

// node class
template <typename T>
class Element{
private:

  Element *next_ = nullptr;
  string name_ = "";
  T color_ = T();

public:

  Element()=default;
  Element(string name, T d) : next_(nullptr), name_(name), color_(d){};

  friend ostream& operator<<(ostream& out, Element& n){

      out << n.name_ << ":" << n.color_;

      return out;
  }

  friend class PAL<T>;

};

/* "This is a singly linked list of Elements that, taken in order,
constitute the Painter's ALgorithm." */
template<typename T>
class PAL{

private:

  Element<T> *back_ = nullptr;
  Element<T> *front_ = nullptr;

  void print_list(ostream& out); 

public:

  PAL()=default;
  PAL(Element<T> n) : back_(&n), front_(&n) {};
  PAL(string n, T d);
  PAL(const PAL&);
  ~PAL();

  PAL& operator=(PAL);

  void add(Element<T> &n);
  void add(string name, T dat);

  pair<Element<T>*, Element<T>*> find(string name);    
  pair<Element<T>*, Element<T>*> find(Element<T> &n);

  void move_forward1(Element<T> &n);
  void move_to_front(Element<T> &n);  

  void move_back1(Element<T> &n);
  void move_to_back(Element<T> &n);  

  friend ostream& operator<<(ostream& out, PAL<T>& sl){
    sl.print_list(out);
    return out;
  }

Now for the assignment operator, I've tried two things.

template<typename T>
PAL<T> & PAL<T>::operator=(PAL p)
{
    front_ = p.front_;
    back_ = p.back_;

    return *this;
}

As well as variations of using std::swap. Both compile, but give run time errors.

When I use swap, I end up with an error I think says it ran out of memory?

Expression:"(_Ptr_user & (_BIG_ALLOCATION_ALIGNMENT -1)) == 0" && 0

If I use the first one, no swaps, weird shit happens. I went through it debugging and watching 'this' and 'p' as it stepped through the function, and it worked perfectly, until the very end, the last bracket whatever that implies, suddenly 'p' and 'this' are changed not even just to nullptrs, but to 0xdddddd (I'm guessing at the number of d's). So then it has all kinds of issues.

I'd like to know why these things are happening, but if nothing else, I need to know what I'm supposed to do instead!

Many thanks.

Edit: The function is now as follows.

template<typename T>
PAL<T> & PAL<T>::operator=(const PAL &p)
{
    Element<T> *new_front = nullptr, *new_back = nullptr;
    Element<T> *address = p.back_;

    while (address != nullptr) {
        /* the add method in this loop will end up taking
         care of front_ and back_ too */

        add(address->name_, address->color_);
        pair<Element<T>*, Element<T>*> found = find(address->name_);
        if (new_front == nullptr) {
            new_front = found.first;
        }
        new_back = found.first;
        //move_to_front(*found.first);

        address = address->next_;
    }


    Element<T> *old = p.back_;
    while (old) {
        Element<T> *last = old;
        old = old->next_;
        delete last;
    }

    front_ = new_front;
    back_ = new_back;


    return *this;
}

Note that back_ means the 'first' item in the list so to speak (nothing points to it) and front_ means the last, it points to nothing.

Answer 1

The copy-assignment-operator's job is not just to copy pointers; the default compiler-generated can do that for you.

The job of this operator is to duplicate the contents of the other object into a completely independent object. This means duplicating each and every Element<T> object from the other object into this object. That also means that you must handle destroying any nodes that your current object contains.

Just copying the pointers, as you have done, means that changes to one PAL<T> will likely be reflected in the other. If the head or tail changes, only one PAL<T> will have this change.

Even worse, if you copy-assign one PAL<T> over another, you now have two PAL<T> objects that think they own the Element<T> objects they contain. Then, when both destruct, they will each try to delete these objects. This results in a double-free, which causes undefined behavior.

First, change the operator to take a reference to a constant instead of a copy.

Then, the general pattern that you will want to use is something like:

template<typename T>
PAL<T> & PAL<T>::operator=(const PAL &p)
{
    // Store the old list here, which we will deallocate at the end. This
    // step is necessary to do first in case some code copy-assigns an
    // instance to itself; since in that case it is copying its own data,
    // we can't deallocate it yet or we will just lose the data completely.
    Element<T> *old_back = back_;

    // Reset this instance.
    front_ = nullptr;
    back_ = nullptr;

    // Duplicate the elements of p, storing them in this object.
    // You will have to make sure the next_ fields of the new elements point
    // into the duplicated chain, not the original!
    //
    // Left as an exercise for you to implement.

    // Deallocate and free the nodes that were contained in this object.
    while (old_back) {
        Element<T> *last = old_back;
        old_back = old_back->next;
        delete last;
    }

    return *this;
}

I am guessing that your copy constructor does not do this duplication either. If it does not, then you can just implement it in terms of this operator to minimize code duplication:

template<typename T>
PAL<T>::PAL(const PAL &p) : front_(nullptr), back_(nullptr) {
    *this = p;
}