5 ms·

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 refere

by swapna_1956 10y ago

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 ?

debh 10y ago
I think for self referencial data structures, passing them by a const& unique_ptr is a reasonable way to do it. Thanks, Deb.
- solipsism 10y ago
  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.
n00b101 10y ago
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.
leni536 10y ago
shared_ptr forward, weak_ptr back.
zvrba 10y ago
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.
- jupp0r 10y ago
  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.
  - zvrba 10y ago
    Which part of "recursion", "stack overflow" and "crash" did you not understand? Do you think std::list uses smart pointers?
    - gpderetta 10y ago
      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.
      - lorenzhs 10y ago
        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.
        zvrba 10y ago
        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.
        10y ago

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 ?

debh 10y ago

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

solipsism 10y ago
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.

n00b101 10y ago

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.

leni536 10y ago

shared_ptr forward, weak_ptr back.

zvrba 10y ago

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.

jupp0r 10y ago
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.
- zvrba 10y ago
  Which part of "recursion", "stack overflow" and "crash" did you not understand? Do you think std::list uses smart pointers?
  - gpderetta 10y ago
    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.
    - lorenzhs 10y ago
      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.
      - zvrba 10y ago
        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.
        10y ago