Let's lay out two things. The first is that it's good to hide implementation details from the user of your code, but it's not necessary to abstract them away entirely. In other words, it's fine to use new in your implementation of your BinaryTree, so long as your user doesn't need to see it.
That being said, it is possible to make things more generic. Below is a very, very generic implementation of a binary tree, complete with Allocators, Deleters, and automatic memory management (there's no need to write a destructor for the tree).
Allocators
Allocators provide a generic way of getting memory. It could be from a memory pool, or it could be from the heap with new, or it could even be something more exotic.
The key idea here is that all your allocators provide a common interface. To keep things simple, we'll use a function called make_new which gets the memory, and constructs the type using the given arguments.
A default allocator and a default deleter would look something like this:
template<class T>
struct DefaultAllocator {
// Get some memory from somewhere
template<class... Args>
T* make_new(Args&&... args) const {
return new T(std::forward<decltype(args)>(args)...);
}
};
struct DefaultDeleter {
//This lets us call Deleter like it's a function
template<class Type>
void operator()(Type* ptr) const {
delete ptr;
}
};
unique_ptr: a class for automatically managing memory
If we want to ensure that there aren't any memory leaks, we should probably use a class like std::unique_ptr. When a class containing unique_ptr is destroyed, whatever unique_ptr points too will automatically be destroyed too.
We can write our own unique_ptr pretty easily. The key is that a unique_ptr should always be unique: we can move it, but we can't make a copy.
template<class T, class Deleter = DefaultDeleter>
class unique_ptr : Deleter {
T* ptr;
public:
Deleter const& get_deleter() const {
return *this;
}
unique_ptr()
: Deleter()
, ptr(nullptr)
{}
unique_ptr(T* ptr)
: Deleter()
, ptr(ptr)
{}
unique_ptr(T* ptr, Deleter const& d)
: Deleter(d),
ptr(ptr)
{}
//It can't be copied, so we're deleting the copy constructor
unique_ptr(unique_ptr const&) = delete;
//It's fine to move a unique_ptr
unique_ptr(unique_ptr && other)
: Deleter(other.get_deleter())
, ptr(other.ptr)
{
//Set other.ptr to null so that it doesn't get deleted twice
other.ptr = nullptr;
}
//Again, no copying allowed
unique_ptr& operator=(unique_ptr const&) = delete;
//But like always, we can move it.
unique_ptr& operator=(unique_ptr&& other) {
//Delete the current pointer
get_deleter()(ptr);
//Assign new ptr:
ptr = other.ptr;
//Set other ptr to null so it doesn't get deleted twice
other.ptr = nullptr;
//Return self
return *this;
}
unique_ptr& operator=(T* new_ptr) {
//Delete current ptr
get_deleter()(ptr);
//Assign new ptr
ptr = new_ptr;
//return self
return *this;
}
~unique_ptr() {
//Call the deleter on the pointer
//if ptr is null, nothing should happen
get_deleter()(ptr);
}
void swap(unique_ptr& other) {
//The standard library provides a swap function
std::swap(ptr, other.ptr);
}
//Overloading -> allows us to use unique_ptr
//as though it were a regular pointer
T* operator->() {
return ptr;
}
T const* operator->() const {
return ptr;
}
//We can also overload the dereference operator
//so that it behaves like a regular pointer
T& operator*() {
return *ptr;
}
T const& operator*() const {
return *ptr;
}
//We can also enable checking if it's null:
bool isNull() const {
return ptr == nullptr;
}
//And we can enable direct comparisons against nullptr
using nullptr_t = decltype(nullptr);
bool operator==(nullptr_t) const {
return ptr == nullptr;
}
//Let's also have a method to get the raw pointer:
T* get() { return ptr; }
T const* get() const { return ptr; }
};
BinaryNode class based on unique_ptr:
Because it's a tree, each node should appear in the tree exactly once. This is a good thing. It means we can use our unique_ptr class, and everything like destruction will get handled automatically: no chance of memory leaks.
template<class T, class Deleter = DefaultDeleter>
class BinaryNode {
T value;
unique_ptr<BinaryNode, Deleter> left;
unique_ptr<BinaryNode, Deleter> right;
public:
BinaryNode(T const& value)
: value(value)
, left()
, right()
{}
BinaryNode(T&& value)
: value(std::move(value))
, left()
, right()
{}
T& get_value() {
return value;
}
T const& get_value() const {
return value;
}
//Let's typedef to give it a shorter name:
using pointer_t = unique_ptr<BinaryNode, Deleter>;
//Because we return a reference, we don't have to
//write a set_left or set_right method
pointer_t& get_left() {
return left;
}
pointer_t& get_right() {
return right;
}
//Writing a const overload is a good idea
pointer_t const& get_left() const {
return left;
}
pointer_t const& get_right() const {
return right;
}
};
BinaryTree class with find and insert
Let's look at the BinaryTree class now. This will actually be one of the most simple to write, because the other classes already take care of stuff like memory management. We've been using Deleters throughout, but now allocators finally come into play.
The interface for insert will be a little different, and the only thing that's changed is that we'll be passing the pointer by reference, instead of value. This allows us to make insert tail-recursive, which makes it more efficient. It also makes insert a little shorter and simpler.
template <class T,
class Deleter = DefaultDeleter,
class Allocator = DefaultAllocator<BinaryNode<T, Deleter>>>
class BinaryTree : Allocator, Deleter {
// Let's declare node_pointer_t
// so that we don't have to type out unique_ptr<...> every time
using node_pointer_t = typename BinaryNode<T, Deleter>::pointer_t;
// If we take the node pointer by reference
// Then we don't have to return anything
// Also our function becomes tail-recursive
// Which means that it won't segfault when called
// no matter how deep the recursion gets
// as long as you have optimization turned on
void insert(node_pointer_t& node, const T& value)
{
if (node == nullptr) {
node = get_allocator().make_new(value);
}
else if (value < node->get_value()) {
insert(node->get_left(), value);
}
else {
insert(node->get_right(), value);
}
}
bool find(node_pointer_t& node, const T& value) {
if (node == nullptr) {
return false;
}
else if(value == node->get_value()) {
return true;
}
else if (value < node->get_value()) {
return find(node->get_left(), value);
}
else {
return find(node->get_right(), value);
}
}
// It'll automatically delete itself
node_pointer_t _root;
public:
BinaryTree()
: Allocator() //Init allocator
, Deleter() //Init deleter
, _root() //Init root
{}
Allocator const& get_allocator() {
return *this;
}
Deleter const& get_deleter() {
return *this;
}
void insert(T const& value) { insert(_root, value); }
bool find(T const& value) { return find(_root, value); }
};
Conclusion
We did it, y'all. HMU if you have any questions.
