2
\$\begingroup\$

One more BST implementation with iterators added. Did not manage to find another implementation with iterators and it is my first attempt at implementing them so thought to check on your opinion:

template<typename T, typename less_than = std::less<T>>
    class BinaryTree {
    public:
        void insert(T&& value);
        void insert(T const& value);
        template<typename... Args>
        void emplace_insert(Args&&... value);
        bool contains(T const& value) const;
        
        template<bool IsConst>
        class iterator_base;
        class iterator;
        class const_iterator;
        
        iterator begin() { return iterator(min_element(root.get())); }
        iterator end() { return {}; };

        const_iterator begin() const { return const_iterator(min_element(root.get())); }
        const_iterator end() const { return {}; };

        const_iterator cbegin() const { return const_iterator(min_element(root.get())); }
        const_iterator cend() const { return {}; };
        
    private:
        struct Node {
            Node(T&& value): payload(std::move(value)) {}
            Node(T const& value): payload(value) {}
            
            template<typename... Args>
                requires std::constructible_from<T, Args...>
            Node(std::in_place_t, Args&&... args): parent(parent), payload(std::forward<Args>(args)...) {}

            T payload;
            Node* parent{ nullptr };
            std::unique_ptr<Node> left;
            std::unique_ptr<Node> right;
        };

        static Node* min_element(Node* node);
        bool insert_node(std::unique_ptr<Node>&& node);
        std::unique_ptr<Node> root;
        size_t size{ 0 };
        less_than cmp_less;
    };


    template<typename T, typename less_than>
    template<bool IsConst>
    class BinaryTree<T, less_than>::iterator_base {
    public:
        using value_type = std::conditional_t<IsConst, T const, T>;
        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;

        iterator_base() = default;
        iterator_base(Node* node) : node(node) {}
        friend class BinaryTree<T, less_than>;
        iterator_base& operator++();
        iterator_base operator++(int);
        value_type& operator*();
        value_type* operator->();

        bool operator==(iterator_base const& other);
        bool operator!=(iterator_base const& other);

    private:
        Node* node{ nullptr };
    };
template<typename T, typename less_than>
    class BinaryTree;

    template<typename T, typename less_than>
    struct BinaryTree<T, less_than>::const_iterator : BinaryTree<T, less_than>::iterator_base<true> {};

    template<typename T, typename less_than>
    struct BinaryTree<T, less_than>::iterator : BinaryTree<T, less_than>::iterator_base<false> {};

    template<typename T, typename less_than>
    template<bool IsConst>
    bool BinaryTree<T, less_than>::iterator_base<IsConst>::operator==(iterator_base const& other) {
        return node == other.node;
    }

    template<typename T, typename less_than>
    template<bool IsConst>
    bool BinaryTree<T, less_than>::iterator_base<IsConst>::operator!=(iterator_base const& other) {
        return !(*this == other);
    }

    template<typename T, typename less_than>
    template<bool IsConst>
    typename BinaryTree<T, less_than>::iterator_base<IsConst>& BinaryTree<T, less_than>::iterator_base<IsConst>::operator++() {
        if (node == nullptr) {
            return *this;
        }

        if (node->right) {
            node = BinaryTree<T, less_than>::min_element(node->right.get());

        }
        else {

            Node* parent{ node->parent };

            while (parent != nullptr && parent->right.get() == node) {
                node = parent;
                parent = node->parent;
            }
            node = parent;
        }
        return *this;
    }

    template<typename T, typename less_than>
    template<bool IsConst>
    typename BinaryTree<T, less_than>::iterator_base<IsConst>::value_type& BinaryTree<T, less_than>::iterator_base<IsConst>::operator*() {
        return static_cast<BinaryTree<T, less_than>::iterator_base<IsConst>::value_type&>(node->payload);
    }

    template<typename T, typename less_than>
    template<bool IsConst>
    typename  BinaryTree<T, less_than>::iterator_base<IsConst>::value_type* BinaryTree<T, less_than>::iterator_base<IsConst>::operator->()
    {
        return static_cast<BinaryTree<T, less_than>::iterator_base<IsConst>::value_type*>(&node->payload);
    }

    template<typename T, typename less_than>
    template<bool IsConst>
    BinaryTree<T, less_than>::iterator_base<IsConst> BinaryTree<T, less_than>::iterator_base<IsConst>::operator++(int) {
        iterator it{ *this };
        ++(*this);
        return it;
    }

    template<typename T, typename less_than>
    typename BinaryTree<T, less_than>::Node* BinaryTree<T, less_than>::min_element(BinaryTree<T, less_than>::Node* node) {
        if (node == nullptr || node->left == nullptr) {
            return node;
        }
        return BinaryTree<T, less_than>::min_element(node->left.get());
    }

    template<typename T, typename less_than>
    template<typename... Args>
    void BinaryTree<T, less_than>::emplace_insert(Args&&... value)
    {
        BinaryTree<T, less_than>::insert_node(std::make_unique<Node>(std::forward<Args>(value)...));
    }

    template<typename T, typename less_than>
    void BinaryTree<T, less_than>::insert(T const& value)
    {
        BinaryTree<T, less_than>::insert_node(std::make_unique<Node>(value));
    }

    template<typename T, typename less_than>
    void BinaryTree<T, less_than>::insert(T&& value)
    {
        BinaryTree<T, less_than>::insert_node(std::make_unique<Node>(std::move(value)));
    }

    template<typename T, typename less_than>
    bool BinaryTree<T, less_than>::insert_node(std::unique_ptr<Node>&& node)
    {
        if (!root) {
            root = std::move(node);
        }
        else {
            Node* curr = root.get();
            Node* parent = nullptr;
            bool addToLeft{ false };
            while (curr != nullptr)
            {
                if (cmp_less(node->payload, curr->payload)) {
                    parent = curr;
                    curr = curr->left.get();
                    addToLeft = true;
                }
                else if (cmp_less(curr->payload, node->payload)) {
                    parent = curr;
                    curr = curr->right.get();
                    addToLeft = false;
                }
                else {
                    return false;
                }
            }

            node->parent = parent;
            if (addToLeft) {
                parent->left = move(node);
            }
            else {
                parent->right = move(node);
            }

        }

        return false;
    }

    template<typename T, typename less_than>
    bool BinaryTree<T, less_than>::contains(T const& value) const {
        Node* curr{ root.get() };
        while (curr) {
            if (cmp_less(curr->payload, value)) {
                curr = curr->right.get();
            }
            else if (cmp_less(value, curr->payload)) {
                curr = curr->left.get();
            }
            else {
                return true;
            }
        }
        return false;
    }

I am aware that there are lots of features to be added. Just wanted to get an idea whether I am going in the right direction so far.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I think you mean BST (binary search tree), not BFS (breadth first search). \$\endgroup\$
    – vnp
    Aug 15, 2023 at 18:05

2 Answers 2

2
\$\begingroup\$

I am aware that there is lots of features to be added. Just wanted to get an idea if I am going in the right direction so far.

From what I can see it does indeed go in the right direction.

Avoid unnecessarily repeating type names

You have nested templated structs, which require a lot of typing and which make the code less readable. It's therefore helpful to avoid repeating typenames when they are not necessary. The thing to keep in mind is that once the compiler sees which class a function is a member of, you then no longer have to repeat that class's name. By using trailing return types we can make even more use of that. For example:

template<typename T, typename less_than>
template<bool IsConst>
typename BinaryTree<T, less_than>::iterator_base<IsConst>::value_type &BinaryTree<T, less_than>::iterator_base<IsConst>::operator*()
{
    return static_cast<BinaryTree<T, less_than>::iterator_base<IsConst>::value_type &>(node->payload);
}

Can be rewritten to:

template<typename T, typename less_than>
template<bool IsConst>
auto BinaryTree<T, less_than>::iterator_base<IsConst>::operator*() -> value_type&
{
    return static_cast<value_type &>(node->payload);
}

Note that the static_cast<>() wasn't even necesssary, so you can write:

template<typename T, typename less_than>
template<bool IsConst>
auto BinaryTree<T, less_than>::iterator_base<IsConst>::operator*() -> value_type&
{
    return node->payload;
}

You can also use this when declaring a struct that uses inheritance, so instead of:

template<typename T, typename less_than>
struct BinaryTree<T, less_than>::const_iterator : BinaryTree<T, less_than>::iterator_base<true> {};

You can write:

template<typename T, typename less_than>
struct BinaryTree<T, less_than>::const_iterator : iterator_base<true> {};

And you can do this inside function bodies:

template<typename T, typename less_than>
template<bool IsConst>
auto BinaryTree<T, less_than>::iterator_base<IsConst>::operator++() -> iterator_base&
{
    …
    // node = BinaryTree<T, less_than>::min_element(node->right.get());
    node = min_element(node->right.get());
    …
}

Make use of the type names you declared

If you declare a type name with using, make sure you use it yourself consistently. Consider iterator_base. First you declare the value_type:

using value_type = std::conditional_t<IsConst, T const, T>;

That's great, but then you forget about it when creating derived types:

using pointer = T*;
using reference = T&;

Those should be:

using pointer = value_type*;
using reference = value_type&;

Luckily, you forgot about the latter two types as well, because:

value_type &operator*();
value_type *operator->();

Those should be:

reference operator*();
pointer operator->();

But of course only if pointer and reference are correctly const-qualified.

Missing things

You already mentioned it needs more features added, but I just wanted to point out some things:

  • You are not updating size, even though you added that member variable already.
  • You should have a constructor that takes a less_than parameter by const reference, and use that to initialize cmp_less.
  • You might want to add a custom allocator function as well.
  • Use of noexcept and constexpr where appropriate.
  • Ideally you copy all of std::set()'s interface.

Is it going to be useful?

I noticed that the tree isn't balanced. The problem is that it then not going to be very efficient. In fact, in extreme cases it could perform worse than just an unsorted std::vector<T>. Any kind of balancing would make this a much more useful data structure.

Alternatively, it would be nice to let the user build the tree in whatever way they like, inserting new nodes in any place in the tree, and maybe adding functions to do breadth-first search and other tree algorithms and operations. It's no longer just a sorted collection of items then.

\$\endgroup\$
1
\$\begingroup\$

Review by compilation

We're missing necessary headers to be able to compile this:

#include <concepts>    // std::constructible_from
#include <cstddef>     // std::ptrdiff_t, std::size_t
#include <functional>  // std::less
#include <iterator>    // std::forward_iterator_tag
#include <memory>      // std::make_unique, std::unique_ptr
#include <type_traits> // std::conditional_t
#include <utility>     // std::forward, std::in_place_t, std::move

It's always a good idea to present the complete code for review, as this makes it easier for reviewers to build the code and propose tested modifications.

In the same spirit, I recommend including the unit tests as part of the review. If this were a pull request for a larger project, you'd want the unit tests to be part of the same commit, so definitely worth including when posting here.

       size_t size{ 0 };

This type is clearly intended to be std::size_t. The standard C++ headers are permitted to declare global-namespace versions of their identifiers, but it's risky to depend on that. And I certainly don't recommend using the C headers such as <stddef.h> - those are intended for cross-language headers only.

g++ -Weffc++ complains that root is not initialised in the constructor. That's somewhat spurious, as it's a std::unique_ptr and will therefore be default-constructed to a sane state - but it's easy to address that warning (and reassure human readers that a null pointer is expected) by writing = {} as an in-class initializer.

We really do need an initialiser for cmp_less, and a constructor that allows passing in an instance - we can't generally assume that it's default-constructible.

Another warning from -Weffc++ is that Node has pointer members but no copy construct/assign. Even though these are inhibited by having a std::unique_ptr member, it may be worth declaring the copy functions = delete and implementing move functions in terms of swap(). Again this will both silence the warning and inform other readers.


Iterator classes

I like the use of a single templated type to provide both iterator and const_iterator. That's a good practice which avoids doubling up on the implementation. The one thing that's missing is a conversion from iterator to const_iterator. That's quite intrusive to do with the current implementation where both types derive from a base class - I normally find it easier with

    using iterator = iterator_base<false>;
    using const_iterator = iterator_base<true>;

combined with a constrained operator const_iterator().

To ensure we have implemented these conversions, the simplest reasonable test is:

    BinaryTree<int> tree;
    assert(tree.begin() == tree.cbegin());
    assert(tree.cbegin() == tree.begin());

Also, I tend to parametrise on the node type (Node or const Node) rather than using a bool; amongst other benefits, this makes creating the iterator's value_type trivial.


Iterator decrement

It would be nice if the iterators were bidirectional - that would make it easier for us to define rbegin(), crbegin(), rend() and crend() functions (using std::make_reverse_iterator()).


Constructor invocation

Here's a dilemma with no easy fix:

        Node(std::in_place_t, Args&&... args)
            : parent(parent),
              payload(std::forward<Args>(args)...)
       {}

We've had to make a choice whether to construct payload using (…) or {…}. Either form can cause user surprise, but I think you are more consistent with the standard library using this form:

The default construct in allocator will call ​::​new((void*)p) T(args), but specialized allocators can choose a different definition.

Using (…) is therefore least likely to cause any functional change when we move to using an allocator to create our content.


Pass by value

I'm not convinced we get any benefit by using an rvalue-reference here:

    bool insert_node(std::unique_ptr<Node>&& node);

Normally, we just accept by value:

    bool insert_node(std::unique_ptr<Node> node);

This same is true, but less obviously so, for BinaryTree::insert(T&&) and Node::Node(T&&). Although T is a template parameter, these are not forwarding references, because T is a parameter of the BinaryTree type.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.