Introduction

This is a follow-up to myprevious question. This code rocks new ground-up implementation of core functionality, which I made from combining @vnp’s and @JDługosz's answers. The core functionality got ~100 LOC decrease and insert gained 15-25% performance gain. It turns out that my remove tests didn't test anything at all in the previous version (now fixed), so I don't know how much performance was gained in remove, but I'm pretty sure the gain is paramount.

Though there are some changes I didn't make. I state the reasons closer to the end of post.

Changes:

• Uniform node location

There is a single function to find the desired node with value or yet to be value. This is achieved through double pointers. Yes, double pointers.

• Using boolean conversion instead of== nullptr

• Using default initialization of members

New functionality:

• SFINAE

try_insert is now uniform for both rvalue and lvalue, and activated only if type is either copyable or moveable. Copy constructor checks for feature too.

• Copy constructor

• emplace

This one was a little bit tricky to pull out. It had some exception issues, but should be okay. The only thing that makes me worried is alignment, though I guess doing SSE or some other hardware trick on BSTs is pretty much useless.

• size

Now the tree knows its size and correctly maintains it.

Code

#ifndef ALGORITHMS_BINARY_SEARCH_TREE_HPP#define ALGORITHMS_BINARY_SEARCH_TREE_HPP#include "binary_tree_iterator.hpp"#include <ostream>#include <utility>#include <type_traits>#include <memory>namespace shino{    template <typename ValueType>    class binary_search_tree    {        constexpr static bool v_copiable = std::is_copy_constructible_v<ValueType>;        constexpr static bool v_moveable = std::is_move_constructible_v<ValueType>;        struct node        { //DO NOT MOVE ELEMENTS AROUND, emplace relies on this order            const ValueType value;            node* left = nullptr;            node* right = nullptr;        };        node* root = nullptr;        std::size_t element_count = 0;    public:        using iterator = binary_tree_iterator<node>;        binary_search_tree(binary_search_tree&& other) noexcept:                root(std::exchange(other.root, nullptr)),                element_count(std::exchange(other.element_count, 0))        {}        binary_search_tree& operator=(binary_search_tree&& other) noexcept        {            std::swap(root, other.root);            std::swap(element_count, other.element_count);            return *this;        }        template <typename = std::enable_if_t<v_copiable>>        explicit binary_search_tree(const binary_search_tree& other)        {            if (other.element_count == 0)                return;            root = new node(other.root->value);            deep_copy(root->left, other.root->left);            deep_copy(root->right, other.root->right);            element_count = other.element_count;        }        template <typename AnotherType,                  typename = std::enable_if_t<std::is_same_v<ValueType, std::decay_t<AnotherType>>                                                     and (v_copiable || v_moveable)>>        bool try_insert(AnotherType&& value)        {            auto insertion_point = find_node(value);            if (*insertion_point)                return false;            *insertion_point = new node{std::forward<AnotherType>(value)};            ++element_count;            return true;        }        template <typename ... Args>        bool emplace(Args&& ... args)        {            std::unique_ptr<char[]> buffer = std::make_unique<char[]>(sizeof(node));            new (buffer.get()) node(std::forward<Args>(args)...);            auto possible_node = reinterpret_cast<node*>(buffer.get());            auto insertion_point = find_node(possible_node->value);            if (*insertion_point)            {                std::destroy_at(possible_node->value);                return false;            }            possible_node->left = nullptr;            possible_node->right = nullptr;            *insertion_point = possible_node;            buffer.release();            ++element_count;            return true;        }        bool exists(const ValueType& value) const        {            return *find_node(value) != nullptr;        }        bool delete_if_exists(const ValueType& value)        {            if (element_count == 0)                return false;            auto child_ptr = find_node(value);            if (!*child_ptr)                return false;            *child_ptr = find_replacement(*child_ptr);            --element_count;            return true;        }        std::size_t size() const {            return element_count;        }        void clear()        {            clear_helper(root);        }        iterator begin()        {            return iterator{root};        }        iterator end()        {            return {};        }        ~binary_search_tree()        {            clear();        }    private:        void deep_copy(node* dest, node* source)        {            if (!source)                return;            if (source->left)            {                dest->left = new node(source->left->value);                deep_copy(dest->left, source->left);            }            if (source->right)            {                dest->right = new node(source->right->value);                deep_copy(dest->right, source->right);            }        }        node* find_replacement(node* start_pos)        {            if (!start_pos->left)            {                auto replacement = start_pos->right;                delete start_pos;                return replacement;            }            auto descendant = start_pos->left;            while (descendant->right)                descendant = descendant->right;            descendant->right = start_pos->right;            delete start_pos;            return start_pos->left;        }        void clear_helper(node* start_position)        {            if (!start_position)                return;            clear_helper(start_position->left);            clear_helper(start_position->right);            delete start_position;        }        node** find_node(const ValueType& value)        {            auto* current = &root;            while (*current and (*current)->value != value)                if (value < (*current)->value)                    current = &(*current)->left;                else                    current = &(*current)->right;            return current;        }    };}#endif //ALGORITHMS_BINARY_SEARCH_TREE_HPP

Tests:

#include "binary_search_tree.hpp"#include <random>#include <unordered_set>#include <algorithm>#include <iostream>std::vector<int> generate_unique_numbers(std::size_t size){    std::vector<int> result;    if (size == 0)        return {};    static std::mt19937_64 twister;    std::uniform_int_distribution<> distribution{0, static_cast<int>(size - 1)};    std::unordered_set<int> numbers;    while (numbers.size() != size)    {        numbers.insert(distribution(twister));    }    return {numbers.begin(), numbers.end()};}void run_randomized_insert_tests(){    for (std::size_t i = 0; i <= 5'000; ++i)    {        std::cout << "running binary_search_tree insert test on size " << i << '\n';        auto numbers = generate_unique_numbers(i);        shino::binary_search_tree<int> tree;        for (auto x: numbers)            tree.try_insert(x);        std::sort(numbers.begin(), numbers.end());        std::size_t numbers_index = 0;        for (auto x: tree)        {            if (x != numbers[numbers_index++])                throw std::logic_error{"tree binary_tree_iterator is broken on size " + std::to_string(i)};        }    }}void remove_value(std::vector<int>& vec, int x){    vec.erase(std::remove(vec.begin(), vec.end(), x), vec.end());}void run_randomized_remove_tests(){    static std::mt19937_64 twister;    for (std::size_t i = 0; i <= 1'000; ++i)    {        shino::binary_search_tree<int> tree;        auto numbers = generate_unique_numbers(i);        for (auto x: numbers)            tree.try_insert(x);        std::sort(numbers.begin(), numbers.end());        std::cout << "running remove test on tree of size " << i << '\n';        for (std::size_t j = 0; j < i; ++j)        {            std::bernoulli_distribution dist;            if (dist(twister))            {                tree.delete_if_exists(static_cast<int>(j));                remove_value(numbers, static_cast<int>(j));            }        }        std::size_t values_index = 0;        for (auto x: tree)        {            if (numbers[values_index] != x)                throw std::logic_error{"remove doesn't work correctly on " + std::to_string(i)};            ++values_index;        }    }}int main(){    std::cout << "running randomized insert tests...\n";    run_randomized_insert_tests();    std::cout << "randomized insert tests passed successfully\n";    std::cout << "running randomized remove tests...\n";    run_randomized_remove_tests();    std::cout << "randomized remove tests passed successfully\n";}

Not applied changes

• Return iterator along with insert

I don't think I have suitable iterator interface to implement at the moment.shino::binary_tree_iterator mentioned inthis post might hinder the performance of those operations.

• Still using!= nullptr inexists

Linter was arguing that implicit conversion in that context is confusing. I gave in.

Concerns

Mostly I'd like to improve simplicity and readability of the code on this iteration, and improve usage of standard library. Though if you see any low hanging performance fruit, please let me know. As always, any other comments are welcome too.

• \$\begingroup\$I'd like this to reach boost level of quality. I wanted to apply for GSoC, but couldn't pass their coding test. I'm starting preparations for the next year already :)\$\endgroup\$

  Incomputable

  – Incomputable

  2018-06-26 23:00:17 +00:00

  CommentedJun 26, 2018 at 23:00

2 Answers2

Start asking to get answers

Find the answer to your question by asking.

Explore related questions

See similar questions with these tags.