C++ 动态分配单链表的赋值运算符（MS Visual Studio 2015）

Question

两个类，一个是结点，一个是单链表。

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

现在对于赋值运算符，我已经尝试了两种方法。

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

    return *this;
}

以及使用 std::swap 的变体。两者都编译，但给出运行时间错误。

当我使用 swap 时，我以错误告终我认为说它运行内存不足？

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

如果我使用第一个，没有交换，就会发生奇怪的事情。我通过它调试并观察 'this' 和 'p' 随着它逐步执行该功能，它工作得很好，直到最后，最后一个括号无论暗示什么，突然 'p' 和 'this' 不仅更改为 nullptrs，还更改为 0xdddddd（我猜测 d 的数量）。那么问题就来了。

我想知道为什么会发生这些事情，但如果没有别的，我需要知道我应该做什么！

非常感谢。

编辑：现在函数如下。

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

请注意，back_ 可以说是列表中的 'first' 项（没有指向它），front_ 表示最后一个，它没有指向任何内容。

Answer 1

复制赋值运算符的工作不仅仅是复制指针；默认的编译器生成可以为你做到这一点。

这个运算符的工作是复制另一个对象的内容到一个完全独立的对象中。这意味着将每个 Element<T> 对象从另一个对象复制到这个对象中。这也意味着您必须处理销毁当前对象包含的任何节点。

就像您所做的那样，仅复制指针意味着对一个 PAL<T> 的更改可能会反映在另一个中。如果头部或尾部发生变化，只有一个PAL<T>会有这种变化。

更糟糕的是，如果您将一个 PAL<T> 复制分配给另一个，您现在有两个 PAL<T> 对象认为它们拥有它们包含的 Element<T> 对象。然后，当两者都 destruct 时，它们将各自尝试删除这些对象。这会导致双重释放，从而导致未定义的行为。

首先，更改运算符以引用常量而不是副本。

那么，您要使用的一般模式如下：

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

我猜你的复制构造函数也不做这个复制。如果没有，那么您可以根据此运算符来实现它以最大程度地减少代码重复：

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

C++ 动态分配单链表的赋值运算符（MS Visual Studio 2015）

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

c++

assignment-operator

dynamic-allocation

singly-linked-list