ptr: linked list entry deletion
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:
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)
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.
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.
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.
I think that you're mistaken because when you move the pointer ( std::move ) you're generating a rvalue and leaving ptr->next in a released state so it's not an undefined behaviour.
I mean, prior to reset you're releasing the pointer: reset(r.release())
And then:
HEAD.next = std::move(HEAD.next->next);
Edit after comments (just adding the code I was testing):
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;
}
And results:
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
上一篇: Xg boost用于多标记分类？
下一篇: ptr：链接列表条目删除