Using smart pointers for C++ binary search tree

Question

I have implemented a binary search tree in c++. Instead of using bare pointers to point to a nodes children I used the std::shared_ptr. The nodes of the tree are implemented as follows

struct treeNode;
typedef std::shared_ptr<treeNode> pTreeNode;

struct treeNode {
    T key;
    pTreeNode left;
    pTreeNode right;
    treeNode(T key) : key(key), left(nullptr), right(nullptr) {}
};

When removing a node from the BST, one of the cases is when the node has only one child. The node is simply replaced by this child as shown below:

             |        remove node                  
            node      --------->     |
               \                    right 
              right                

In an similar Java implementation this can be coded as:

node = node.getRight();

In my C++ implementation it is:

node = node->right;

where node is of type pTreeNode.

When calling the = operator on an pTreeNode (std::shared_ptr<TreeNode>), node's destructor will be called. The number of shared pointers pointing to the underlying TreeNode is 1, hence the TreeNode is destroyed freeing its memory. When the TreeNode (default) destructor is called, each of its members are destroyed. This surely would result in the pTreeNode right member being destroyed. The problem is that node->right is what is being assigned to node. When testing my BST, it appears to work fine with no errors/memory leaks.

• Is what I am doing unsafe?
• If it is unsafe, what could I do to get around this problem?

A 'hack' that i figured may work would be to make another pointer to increase its reference count. Would this be an adequate solution?

//increase reference to node->right by 1 so it doesn't get destroyed
pTreeNode temp(node->right);
node = node->right;

Scoundrel

I am unfamiliar with shared pointers. My suggestion is to see if the destructor is called before or after the assignment. My guess is that it is called afterwards which means that there is a pointer pointing to the former node->right which already increases the reference count. Therefore, the child node will not be destructed. – Baptistery

Relevant Herb Sutter youtu.be/JfmTagWcqoE?t=887 – Ricardoricca

@CaptainGiraffe Wow I didn't knew there something like shared_ptr alias ..using that will prevent workaround – Damara

shared_ptr are safe to use... Copy and move operations are properly implemented to works as expected. So as long as you d'ont do weird things with the raw underlying pointer, code should works just fine. – Meekins

Why do you use shared_ptr when there's nothing to share? Use unique_ptr. – Schramm

At first I thought pTreeNode::operator = would keep alive its argument, as any other function, but then I realized that the shared ptr is being passed by reference (of course!), and a reference to a shared ptr won't increase the refcount. If that operator took its argument by value this would surely work. But, being by reference, I am now unsure: we need that the refcount of the argument to be incremented before node is destroyed. I have no idea about what the standard says about this. – Manstopper

@Manstopper the standard says, essentially, that shared_ptr works. Otherwise what would be the point of providing it? – Synopsis

Answer 1

You are apparently assuming that, in

node = right;

shared_ptr's assignment operator may decrement node's count before having finished reading from right (or before incrementing the ref count used by right). However, according to cppreference, using

template<typename T>
template<typename U>
std::shared_ptr<T> &std::shared_ptr<T>::operator =(const std::shared_ptr<U> &);

as

node = right; // std::shared_ptr<treeNode>

is equivalent to

std::shared_ptr<treeNode>(right).swap(node);

which is safe because right is copied before the old value of node is destroyed. As an aside, I have implemented a shared pointer myself and I saw to it that "cleaning up" the old value is the last thing I do inside of operator = precisely to avoid such problems.

Donavon

Answer 2

• Is what I am doing unsafe?

No, it's safe as far I can see. The left or right node instances will be kept alive until their ref count falls to zero.

• If it is unsafe, what could I do to get around this problem?

The only relevant thing you should be aware of is not to hand out any nodes as shared_ptr's outside of the tree implementation. These should be std::weak_ptr's or raw pointers.

Estellestella

There is nothing wrong with giving std::shared_ptr outside if you want external code to be able to use that node data independently of the fact that the node is still inside the search tree. For example, if you want to remove a node before processing it. – Meekins

Exposing node pointers to outside clients is the only reason to use shared_ptr in the first place. Otherwise one could have used much cheaper unique_ptr. – Synopsis