CODEWITHSUNDEEP
c++c++11binary-search-treeshared-ptrsmart-pointers
dayman
dayman

Reputation: 123

Using smart pointers for C++ binary search tree

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.

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;

Upvotes: 12

Views: 2896

Answers (2)

Arne Vogel
Arne Vogel

Reputation: 6716

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.

Upvotes: 2

user0042
user0042

Reputation: 8018

  • 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.

Upvotes: 0

Related Questions