C++14 Tree Data Structures
Smart Pointer Implementation
Moving Beyond Raw Pointers
If you've built trees with raw pointers, you know the drill. You new up a node, wire it into the tree, and then you have to remember to delete it later. Forgetting to do so leads to memory leaks. Deleting it too early creates dangling pointers. It’s a manual, error-prone process that complicates otherwise clean logic.
Modern C++ offers a better way. Instead of juggling raw pointers and manual memory calls, we can express ownership directly in the type system using smart pointers. For the strict, one-to-one ownership a parent has over its children in a tree, std::unique_ptr is the perfect tool.
Whenever possible, use smart pointers such as std::unique_ptr and std::shared_ptr to manage memory allocation automatically and reduce manual overhead.
A std::unique_ptr is a lightweight wrapper around a raw pointer that owns the object it points to. When the unique_ptr goes out of scope, it automatically deletes the object. This simple behavior, rooted in a principle called , eliminates the need for manual delete calls and prevents entire classes of memory bugs.
Let's redefine our binary tree node to use it. Notice how the left and right members are no longer raw pointers. They are smart pointers that own their respective child nodes.
#include <memory>
template <typename T>
struct BinaryNode {
T data;
std::unique_ptr<BinaryNode<T>> left;
std::unique_ptr<BinaryNode<T>> right;
// Constructor for convenience
BinaryNode(const T& val) : data(val), left(nullptr), right(nullptr) {}
};
Building with Ownership
Since std::unique_ptr enforces unique ownership, you can't simply copy one pointer to another. If you could, you'd have two unique_ptrs thinking they both owned the same memory, which would lead to a double-delete error. Instead, we must explicitly transfer ownership.
This is done using std::move. When we create a new node and want to attach it as a child to a parent, we move the new node into the parent's left or right unique_ptr. This action transfers ownership from our temporary variable to the parent node, leaving the original unique_ptr empty (null).
// Create the root node
auto root = std::make_unique<BinaryNode<int>>(10);
// Create a left child
auto left_child = std::make_unique<BinaryNode<int>>(5);
// Transfer ownership of the new node to the root's left pointer.
// After this line, `left_child` is nullptr.
root->left = std::move(left_child);
// We can also create and move in one step
root->right = std::make_unique<BinaryNode<int>>(15);
This pattern is incredibly powerful. The code now clearly states its intent: the root node owns its children. Operations like tree rotations or re-parenting nodes become explicit transfers of this ownership, managed safely by the type system.
Automatic Cleanup
The most significant benefit of this approach is effortless and safe memory deallocation. When a std::unique_ptr is destroyed, its destructor is called. This destructor checks if it owns a pointer, and if it does, it deletes that pointer.
Now, consider our tree. When the root pointer goes out of scope, its destructor is called. This destructor deletes the BinaryNode it points to. But before that BinaryNode is fully destroyed, its own members must be destroyed first. This triggers the destructors for its left and right unique_ptrs.
This chain reaction continues down the entire tree. The destruction of a parent triggers the destruction of its children, which triggers the destruction of their children, and so on. This recursive destruction ensures the entire tree is deallocated correctly with no extra code. Deleting the root is all it takes to clean up everything.
By adopting std::unique_ptr, we elevate memory management from a manual chore to a declarative statement of ownership, letting the compiler and the type system enforce safety for us.
What is the primary mechanism that allows a std::unique_ptr to automatically manage the memory of the object it points to?
When building a binary tree with std::unique_ptr, how is ownership of a new node transferred to a parent node's left or right child pointer?