unique_ptr: linked list entry deletion

Question

I am currently considering the implementation of a single linked list with the aid of unique_ptrs. Despite the problem of a possible stack overflow due to the recursive call of the destructors (see Stack overflow with unique_ptr linked list), I came across the following problem: Assume, we have the following implementation of the linked list

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

and we have initialized our list according to

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

Now, I would like to delete the node with the value 1:

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

At first glance, this seems sensible. Still, I am not sure if it might cause undefined behaviour:

According to http://en.cppreference.com/w/cpp/memory/unique_ptr/operator%3D, the operator=

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())

Having a closer look at unique_ptr::reset (http://en.cppreference.com/w/cpp/memory/unique_ptr/reset), it reads

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

1. Saves a copy of the current pointer old_ptr = current_ptr

2. Overwrites the current pointer with the argument current_ptr = ptr

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

This means that in this case the call of r.get_deleter() would reference an object that has already been destroyed, or am I mistaken here?

Thank you very much for your responses.

Answer 1

Your concerns seem valid to me. The ptr->next.get_deleter() no longer exists, because ptr->next is destroyed (although no longer owning anything) along with *ptr when ptr is reset. In most cases it's probably not going to matter, since the deleter is going to be an empty base class, and assignment is going to be a no-op, but still technically undefined behaviour.

I'd go with HEAD.next.reset(ptr->next.release()); explicitly (if you don't care about the deleter), or HEAD.next = std::unique_ptr<node>(std::move(ptr->next)) if you are concerned about preserving the deleter.

Answer 2

I think you are correct.

The only thing preventing the HEAD.next->next unique_ptr being destroyed is that HEAD.next node holds it. The act of assigning to HEAD.next breaks that before trying to get the deleter from HEAD.next->next unique_ptr.

To me, the intuitive way of deleting the node with value 1 would be to detach the tail from the head and then re-attach the tail from the node with value 2:

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

What you are trying to do is like cutting and re-attaching a snake while only holding the snake with one hand, if you are not careful bits of the snake might wriggle away.

Edit: I tried using a stateful deleter like this:

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

Interestingly, in GCC it seems to behave itself but in Visual Studio 2015 it is clearly invoking undefined behaviour. The output is:

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
...

It looks like it is trying to use deleter 1 after it has been destroyed.