0

I'm building a tree with Node class having unique_ptr on the left and right child and Node* pointer to parent. When I'm deleting nodes, I take node and the I have to check if the node i'm deleting is right of left child and then reset the unique_ptr in the parent. Is there any way to take the pointer and ask if there is any unique_ptr wrapper around it and possibly return it?

ValentaTomas
  • 260
  • 3
  • 11
  • You can for some `std::shared_ptr` using [`std::/enable_shared_from_this`](http://en.cppreference.com/w/cpp/memory/enable_shared_from_this/shared_from_this). – François Andrieux Dec 18 '17 at 19:28
  • 2
    It's not really clear to me what you're asking. If you delete a node in a tree, you have to get a pointer/reference to its parent, so that you can adjust the parent's pointers. This has nothing to do with unique vs raw vs shared pointer. Usually when you implement e.g. an RB tree, you would include a parent pointer with each node (https://stackoverflow.com/questions/46119328/c-running-time-of-next-and-prev-in-a-multiset-iterator/46119946#46119946). So you can do something like: `if (this->parent->left.get() == this) { // current node is left child } else { // is right }`. – Nir Friedman Dec 18 '17 at 19:32
  • @NirFriedman If I was manipulating with nodes as unique_ptr references I would just have to call reset on the node, but now i have to go one level up and check if it's left or right child even though I already have the pointer I want to delete. I understand that I have to adjust parent pointers, but wouldn't it be solved with just reset on unique_ptr reference, if I could get it? – ValentaTomas Dec 18 '17 at 19:38
  • @Davar It's just still a bit hard to answer your question because it's too broad and short on details. The practical answer to your question is that you need a parent pointer anyhow for various things in a binary tree implementation (read my linked answer). The other possibility is that you can make your `iterator` type contain a pointer to the `unique_ptr` to the Node in question, rather than directly to the node. Either way you'll need to access the parent held pointer and there's no magic way to do that. Note that Francois' suggestion of enable_shared_from_this doesn't help you either. – Nir Friedman Dec 18 '17 at 20:06
  • @NirFriedman Yeah, you are right. – ValentaTomas Dec 18 '17 at 20:16

2 Answers2

5

Is there any way to take the pointer and ask if there is any unique_ptr wrapper around it and possibly return it?

There's no generic way to find the unique_ptr, but you can for example store a reference.

Assuming your tree is binary, you can find the unique_ptr in parent like this:

(parent->left == this ? parent->left : parent->right).release();

If the tree isn't binary, you can iterate over all children.

eerorika
  • 232,697
  • 12
  • 197
  • 326
0

In C++, pointers are uni-directional; and unique_ptr, being simply a wrapper class around a pointer, doesn't change that. There is no way to get the unique_ptr from the raw pointer it is pointing to.

A few alternative solutions to your particular issue are possible:

  1. Add a parent pointer to the child object, then you can navigate to the parent to delete the child from there. This may be inefficient if you have a lot of nodes.
  2. Implement the concept of an iterator - an abstraction of a context that carries sufficient information to be able to modify the tree (e.g. delete a node). For example, a tree iterator could contain a pointer to the current node, a pointer to its parent and the flag indicating if it's a left or right child. The downside is that you can't modify a tree simply by having a pointer to its node, you need to have an instance of an iterator.
rustyx
  • 80,671
  • 25
  • 200
  • 267