unique_ptr：链表条目删除

Question

目前正在考虑借助unique_ptrs实现单链表。尽管由于析构函数的递归调用（参见）而可能出现堆栈溢出的问题，但我还是遇到了以下问题：假设，我们有以下链表的实现

struct node {
  node (void) : val(0), next(nullptr) {}
  int val;
  std::unique_ptr<node> next;
};

并且我们已经根据

初始化了我们的列表

int main (int argc, char* argv[]) {
  node HEAD;
  HEAD.val = 0;
  auto ptr = &HEAD;
  for (int i = 0; i < 10; ++i) {
    ptr->val = i;
    ptr->next.reset(new node);
    ptr = ptr->next.get();
  }
  ptr->val = 10;
  ...

现在，我想删除值为1的节点：

ptr = &HEAD;
ptr = ptr->next.get();
HEAD.next = std::move(ptr->next);

乍一看，这似乎很合理。不过，我不确定它是否会导致未定义的行为：

根据http://en.cppreference.com/w/cpp/memory/unique_ptr/operator%3D，运算符=

Transfers ownership from r to *this as if by calling reset(r.release()) followed by an assignment of get_deleter() from std::forward (r.get_deleter())

仔细查看 unique_ptr::reset (http://en.cppreference.com/w/cpp/memory/unique_ptr/reset)，它显示为

Given current_ptr, the pointer that was managed by *this, performs the
following actions, in this order:

Saves a copy of the current pointer old_ptr = current_ptr

Overwrites the current pointer with the argument current_ptr = ptr

If the old pointer was non-empty, deletes the previously managed object if(old_ptr != nullptr) get_deleter()(old_ptr)

这意味着在这种情况下 r.get_deleter() 的调用将引用一个已经被销毁的对象，还是我弄错了？

非常感谢您的回复。

Answer 1

你的担忧对我来说似乎是有道理的。 ptr->next.get_deleter() 不再存在，因为当 ptr 被重置时 ptr->next 与 *ptr 一起被销毁（尽管不再拥有任何东西）。在大多数情况下，这可能无关紧要，因为删除器将是一个空基class，并且赋值将是一个空操作，但在技术上仍然是未定义的行为。

我会明确选择 HEAD.next.reset(ptr->next.release());（如果您不关心删除器），或者 HEAD.next = std::unique_ptr<node>(std::move(ptr->next)) 如果您担心保留删除器。

Answer 2

我认为你是对的。

唯一阻止 HEAD.next->next unique_ptr 被摧毁的是 HEAD.next node 持有它。分配给 HEAD.next 的行为打破了 before 试图从 HEAD.next->next unique_ptr.

获取删除器

对我来说，删除值为 1 的节点的直观方法是将尾部从头部分离，然后重新连接值为 2 的节点的尾部：

auto tail = std::move(HEAD.next);
HEAD.next = std::move(tail.next);

你想做的就像切割和重新连接一条蛇，同时只用一只手握住蛇，如果你不小心，蛇的碎片可能会蠕动。

编辑： 我尝试使用这样的有状态删除器：

#include <memory>
#include <iostream>

struct node;

class NodeDeleter {
  int deleterNumber;
public:
  NodeDeleter() : deleterNumber(-1) {}
  NodeDeleter(int deleterNumber) : deleterNumber(deleterNumber) {}
  void operator()(node* n);
};

struct node {
  node() : val(0), next(nullptr) {}
  int val;
  std::unique_ptr<node, NodeDeleter> next;
};

void NodeDeleter::operator()(node* n) {
  std::cout << "Deleting node with value " << n->val << " using deleter " << deleterNumber << "\n";
  delete n;
}

std::unique_ptr<node, NodeDeleter> make_node(int deleterNumber) {
  return std::unique_ptr<node, NodeDeleter>(new node(), NodeDeleter(deleterNumber));
}

int main() {
  node HEAD;
  HEAD.val = 0;
  auto ptr = &HEAD;
  for (int i = 0; i < 10; ++i) {
    ptr->val = i;
    ptr->next = make_node(i);
    ptr = ptr->next.get();
  }
  ptr->val = 10;

  HEAD.next = std::move(HEAD.next->next);
}

有趣的是，在 GCC 中它似乎表现得很好，但在 Visual Studio 2015 年它显然调用了未定义的行为。输出为：

Deleting node with value 1 using deleter 0
Deleting node with value 2 using deleter -572662307
Deleting node with value 3 using deleter 2
Deleting node with value 4 using deleter 3
...

删除器 1 被销毁后，它似乎正在尝试使用它。

Answer 3

我认为你错了，因为当你移动指针 (std::move) 时，你正在生成一个右值并将 ptr->next 留在已发布 状态，因此这不是未定义的行为。

我的意思是，在 reset 之前你要释放指针：reset(r.release())

然后：

HEAD.next = std::move(HEAD.next->next);

评论后编辑（仅添加我正在测试的代码）：

struct custom_deleter {  // a deleter class with state
  custom_deleter() {}
  ~custom_deleter() {
    std::cout << "custom deleter deleted" << std::endl;
 }
  template <class T>
  void operator()(T* p) {
    std::cout << "custom deleter()" << std::endl;
    delete p;
  }
};

struct node {
  node (void) : val(0), next(nullptr) {}
  ~node () {
    std::cout << "~node " << val << std::endl;
  }
  int val;
  std::unique_ptr<node, custom_deleter> next;
};

int main (int argc, char* argv[]) {
  node HEAD;
  HEAD.val = 0;
  auto ptr = &HEAD;
  for (int i = 0; i < 10; ++i) {
    ptr->val = i;
    ptr->next.reset(new node);
    ptr = ptr->next.get();
  }
  ptr->val = 10;

  std::cout << "And now we delete it" << std::endl;
  HEAD.next = std::move(HEAD.next->next);

  std::cout << "Looping" << std::endl;
  ptr = &HEAD;
  for (int i=0; i < 9; ++i) {
      std::cout << ptr->val << std::endl;
      ptr = ptr->next.get();
  }
  std::cout << "End." << std::endl;
}

结果：

custom deleter()
~node 1
custom deleter deleted
Looping
0
2
3
4
5
6
7
8
9
End.
~node 0
custom deleter()
~node 2
custom deleter()
~node 3
custom deleter()
~node 4
custom deleter()
~node 5
custom deleter()
~node 6
custom deleter()
~node 7
custom deleter()
~node 8
custom deleter()
~node 9
custom deleter()
~node 10
custom deleter deleted
custom deleter deleted
custom deleter deleted
custom deleter deleted
custom deleter deleted
custom deleter deleted
custom deleter deleted
custom deleter deleted
custom deleter deleted
custom deleter deleted

unique_ptr：链表条目删除

unique_ptr: linked list entry deletion

c++

linked-list

undefined-behavior

unique-ptr