Binary Trees: using unique_ptr

published at 20.11.2025 22:38 by Jens Weller
Save to Instapaper Pocket

Recently I've looked at binary trees, comparing a bare pointer version with new/delete against a binary tree that stores its nodes into a vector and uses indexes instead of pointers.

The result of that experiment was that the vector approach was way faster. Though I also feel the comparison wasn't so fair, as the single allocations do of course cost a lot more then what a vector pays for allocation. I do have a unique_ptr pool I've remembered, and while I could get the example running with this, it turned out to not be build for this use case.

The pool was and is meant for actually allocating large and very expensive objects, and then holding on to them. Its only handing out unique_ptr<Obj,del>, which then points to an internally created object. Its goal is to avoid the allocation if one can, and share these objects for reuse in an multithreaded environment like a threadpool. Its been used back then for providing image detection objects to processing threads. And the current tests do mostly measure adding things to the tree, searching and then destroying the whole thing. Elements are not removed, and the tree nodes are fairly small.

But this made me curious what the simple addition of using unique_ptrs would yield as a result. The initial example is just what you find on the web, raw pointers with new/delete. In modern C++ one would prefer to use unique_ptr. But this by itself is just adding a wrapper to new/delete, in order to make the code safer.

Not much has changed in the code, mostly its replacing TreeNode* with std::unique_ptr<TreeNode>:

using rt_ptr = std::unique_ptr;
int data;               // The value stored in the node
rt_ptr left;         // Pointer to the left child
rt_ptr right;        // Pointer to the right child

The function to add a node recursive now needs to handle a reference to a unique_ptr:

rt_ptr insertRecursive(rt_ptr& node, int value)
{
    if (node == nullptr) 
        return std::make_unique(value);
    // Simple insertion logic (e.g., for a Binary Search Tree)
    if (value < node->data)
            node->left = insertRecursive(node->left, value);
    else if (value > node->data)
            node->right = insertRecursive(node->right, value);
    return std::move(node);
}

The new code at quick-bench now shows that there is a bit of an overhead when using unique_ptr: unique_ptr is 1.7/2.2 (O2/O3) slower than the vector approach, while in the old example using new/delete was 1.7/1.4 (O2/O3) slower than the vector version:

I've been thinking if there is a way to improve this again, but at best one could get close to the performance of the index based example. A pointer based approach will always have to employ some mechanisms to hold the connection between pointer and object valid. Using a vector would not work due to iterator invalidation/reallocation due to growth. I do have some classes which can get around this, adopted to this that would mean a wrapper thats then monitoring the moves/relocation of the object to update the address. I doubt its going to get closer to the approach of what the index based code achieves. It also would be much more complicated.

And thats one of the downsites of quick-bench, debugging is not possible. I'd have to try to get this running locally and once things work copy it back to quick-bench.

Join the Meeting C++ patreon community!
This and other posts on Meeting C++ are enabled by my supporters on patreon!