Hacker News Reader

Comment by swapna_1956 | Hacker News Reader

swapna_1956

So if I'm coding up a LinkedList or a Binary Tree today, instead of using a raw pointer or shared_ptr, should i be using a unique_ptr to prevent circular references ?

View on HN

You should be using a raw pointer, period. The list/tree destructor must be responsible for traversing and deleting the whole structure.

If you have a linked list of, say, 10M elements linked by unique_ptr, deleting the head of the list would cause recursive [1] destruction of all elements in the list. Stack overflow, CRASH, BOOM, BANG!

[1] Take a simple example of list A ->a B ->b C ->c 0 where arrows are unique_ptrs owned by the nodes. Deleting A must invoke the destructor for ->a , which will delete B, invoking the destructor for ->b, which will delete C invoking the destructor for ->c which is null, thus finishing the recursion.

EDITS: added labels to pointers for clarity.

You could (and imho should) use RAII semantics using unique_prts for this. Writing custom destructors will introduce unnecessary code that you'll have to maintain and unnecessary bugs that will creep in eventually.

This wreaks havoc on the ownership semantics. Smart pointers are not a good fit for pointer-based data structures. Just have the list destructor clean it up.

Which part of "recursion", "stack overflow" and "crash" did you not understand? Do you think std::list uses smart pointers?

You are getting downvoted, but you are completely right. When implementing node based containers it is perfectly alright to use raw pointers as the nodes in no way own their children or siblings but they are all collectively owned by the datastructure.

You should of course use smart pointers for the automatic pointers that temporarily hold node references in functions that manipulate the datastructure.

The downvotes are for snark, not incorrectness the of content, I'm fairly certain. Such aggressive replies are not appreciated on HN. I find that this makes HN a much more pleasant community than some others.

The reply is that way because the OP didn't seem to acknowledge that using unique_ptr in this case has serious problems. He still insists on using unique_ptr, reasoning boiling down to "you should avoid writing code because you may create bugs". As if slowness or lurking crash caused by not writing code were not a bug in itself.

Oh I know, using unique_ptr to implement linked list is a terrible idea. Having an element be owned by its predecessor is a very weird idea, not to mention that it wouldn't work at all for a doubly linked list.... I'm just saying that your comment could have been written in a nicer way.

For a doubly linked list, I think the right approach is to store a unique_ptr pointing in one direction and a raw pointer pointing in the other direction. It is then understood by convention that raw pointers should never be deleted.

I think for self referencial data structures, passing them by a const& unique_ptr is a reasonable way to do it.

Thanks, Deb.

I think this is not right -- since references aren't reseatable, this would effectively make the data structure (but not necessarily its contents) immutable.

Shared pointers or raw pointers are the options that make most sense, in my opinion.

Edit: forgot to say, if you use shared_ptr beware circular references. e.g. in the case of a doubly linked list. weak_ptr could be used to break the cycle, but I'd probably use raw pointers here.

shared_ptr forward, weak_ptr back.

Reply on news.ycombinator.com