Created
January 19, 2022 17:14
-
-
Save alifarazz/c1ccd7b987f18be508f199898c20a9a4 to your computer and use it in GitHub Desktop.
A memory-safe bare-minimum binary tree implementation in c++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <functional> | |
#include <iostream> | |
#include <memory> | |
#include <optional> | |
template <int T> | |
struct S { | |
int _[T]; | |
}; | |
template <typename T> | |
class Node { | |
public: | |
Node() : parent{*this}, data{} {} | |
Node(Node &parent, T &&data) : parent{parent}, data{std::move(data)} {} | |
bool isRoot() const { return this == &parent; } | |
public: | |
std::unique_ptr<Node<T>> left, right; | |
Node &parent; | |
T data; | |
}; | |
void test_data_in_node() { | |
using namespace std::literals; | |
using NodeType = Node<std::optional<std::string>>; | |
NodeType root; | |
root.left = std::make_unique<NodeType>(root, "left data"s); | |
root.right = std::make_unique<NodeType>(root, "right data"s); | |
std::cout << root.isRoot() << std::endl; | |
std::cout << root.data.value_or("nothing") << std::endl; | |
std::cout << root.left->data.value() << std::endl; | |
std::cout << root.right->data.value() << std::endl; | |
std::cout << root.right->parent.isRoot() << std::endl; | |
std::cout << sizeof(NodeType) << std::endl; | |
std::cout << sizeof(Node<std::optional<S<2>>>) << std::endl; | |
std::cout << sizeof(Node<std::optional<S<8>>>) << std::endl; | |
std::cout << sizeof(Node<std::optional<S<64>>>) << std::endl; | |
} | |
void test_data_ptr_in_node() { | |
using namespace std::literals; | |
using NodeType = Node<std::unique_ptr<std::string>>; | |
NodeType root; | |
root.left = std::make_unique<NodeType>(root, std::make_unique<std::string>("left data"s)); | |
root.right = std::make_unique<NodeType>(root, std::make_unique<std::string>("righ data"s)); | |
std::cout << root.isRoot() << std::endl; | |
std::cout << root.data << std::endl; | |
std::cout << *root.left->data << std::endl; | |
std::cout << *root.right->data << std::endl; | |
std::cout << root.right->parent.isRoot() << std::endl; | |
std::cout << sizeof(NodeType) << std::endl; | |
std::cout << sizeof(Node<std::unique_ptr<S<2>>>) << std::endl; | |
std::cout << sizeof(Node<std::unique_ptr<S<8>>>) << std::endl; | |
std::cout << sizeof(Node<std::unique_ptr<S<64>>>) << std::endl; | |
} | |
int main() | |
{ | |
std::cout << std::boolalpha; | |
std::cout << std::string(80, '-') << "\n\tWith std::optional\n"; | |
test_data_in_node(); | |
std::cout << std::string(80, '-') << "\n\tWith std::unique_ptr\n"; | |
test_data_ptr_in_node(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment