3
\$\begingroup\$

I am new to C++ and am attempting to write the following binary search tree using the iterator pattern (and std::optional in C++17):

#include <memory>
#include <optional>
#include <stack>

template <typename T>
class BinarySearchTree {
public:
  BinarySearchTree(T key)
  : key_(key),
    left_(nullptr),
    right_(nullptr) {}

  BinarySearchTree(const BinarySearchTree& bst) {
    key_ = bst.key_;
    left_ = std::make_unique<BinarySearchTree>(*bst.left_);
    right_ = std::make_unique<BinarySearchTree>(*bst.right_);
  }

  void insert(T key);

  T key() { return key_; }
  std::unique_ptr<BinarySearchTree> left() { return std::make_unique<BinarySearchTree>(*left_); }
  std::unique_ptr<BinarySearchTree> right() { return std::make_unique<BinarySearchTree>(*right_); }

private:
  T key_;
  std::unique_ptr<BinarySearchTree> left_;
  std::unique_ptr<BinarySearchTree> right_;
};

template <typename T>
void BinarySearchTree<T>::insert(T key) {
  auto insert = [key](auto& node) {
    if (node) {
      node->insert(key);
    } else {
      node = std::make_unique<BinarySearchTree>(key);
    }
  };

  if (key <= key_) {
    insert(left_);
  } else {
    insert(right_);
  }
}

template <typename T>
class BinarySearchTreeIterator {
public:
  BinarySearchTreeIterator(BinarySearchTree<T>& bst, bool forward)
  : bst_(std::make_unique<BinarySearchTree<T>>(bst)),
    forward_(forward) {}

  std::optional<T> operator*() { return current_; }

  void operator++() {
    while (bst_ || !stack_.empty()) {
      if (bst_) {
        stack_.emplace(std::make_unique<BinarySearchTree<T>>(*bst_));
        bst_ = std::make_unique<BinarySearchTree<T>>(*(forward_ ? bst_->left() : bst_->right()));
      } else {
        bst_ = std::make_unique<BinarySearchTree<T>>(*(stack_.top()));
        stack_.pop();
        current_ = bst_->key();
        bst_ = std::make_unique<BinarySearchTree<T>>(*(forward_ ? bst_->right() : bst_->left()));
        break;
      }
    }
  }

private:
  std::unique_ptr<BinarySearchTree<T>> bst_;
  bool forward_;
  std::stack<std::unique_ptr<BinarySearchTree<T>>> stack_;
  std::optional<T> current_;
};

I am not sure if my usage of std::unique_ptr is correct or idiomatic.

\$\endgroup\$
3
\$\begingroup\$

BinarySearchTree

  • Since the tree isn't balanced, worst case insertion complexity is \$\mathcal{O}(n)\$ (and not \$\mathcal{O}(\log n)\$ as likely intended). (Same for lookup, if such a method were to be added).
  • Calling left() or right() will create a copy of the whole left/right subtree. This is very likely not intended.
  • This class could profit a lot from a move constructor and a move assignment operator overload. (And while we're at it, add a copy assignment operator overload and a destructor to complete the rule of five.)
  • Is it really necessary to name the lambda the same as the enclosing function in BinarySearchTree::insert(T key)?
  • Also of note, only types that can be copied can be inserted into the BinarySearchTree. This means it is currently not possibly to store a move-only type (like std::unique_ptr) in the tree. (This capacity could be added with an overload accepting a T&&.
  • BinarySearchTree::insert(T key) creates unnecessary copies of key for each recursive call. Consider taking a const T& instead.`
  • left_ and right_ are often dereferenced without checking them for nullptr beforehand! This results in undefined behavior if they are nullptr!

BinarySearchTreeIterator

  • This iterator doesn't provide any iterator_traits or an end iterator. This means using it with standard library algorithms (or even a range based for loop) is not possible. More info on iterators and iterator_traits.
  • There are lots and lots of unnecessary copies (basically every time std::make_unique or bst_->left() or bst_->right() are called).
  • current_ will always have a value with this implementation, so making it std::optional<T> is misleading. Also, any modifications done to the value returned by operator*() won't be propagated to the original BinarySearchTree entry (as it returns an independent copy and not a reference).
  • This iterator traverses the tree in-order. Since there are also other traversal methods, like pre-order, post-order or level-order, it would be nice to indicate that in the name.

std::unique_ptr usage

Normally, a std::unique_ptr is used to express "I own this". So a signature like std::unique_ptr<BinarySearchTree<T>> BinarySearchTree::left() says "Call me, and you become the new owner of whatever I return".

Is this necessary in this case? No! After all, the caller just wants to access the existing object, and not acquire a new one.

So, how can this be expressed?

There are two variants:

  1. Return a non-owning BinarySearchTree<T>*.

    Pros:

    • Very lightweight.
    • Very simple (can still use std::unique_ptr for internal storage, so resources get cleaned up properly).

    Cons:

    • If the BinarySearchTree<T> gets destroyed, but someone still has the pointer stored, the pointer is dangling.
    • Someone could prematurely call delete on the pointer (so the internal std::unique_ptr would be dangling).
  2. Return a std::shared_ptr<BinarySearchTree<T>>.

    Pros:

    • As long as the std::shared_ptr exists, the object will be valid.

    Cons:

    • Might keep the tree (or subtrees) alive for far longer than intended.
    • Has a slight overhead.
    • Requires using std::shared_ptr for internal storage.
    • Might leak in case of cycles (not a problem here, just for the general case).

    Of course, some of those problems can be avoided by appropriate use of std::weak_ptr.

Some more resources:

\$\endgroup\$
  • 1
    \$\begingroup\$ I would prefer turning a reference from left/right as it makes it clear that it is not a pointer that you should store because it can be destroyed at any point \$\endgroup\$ – Emily L. Nov 19 '17 at 10:53
  • 1
    \$\begingroup\$ @EmilyL.: The node might be nullptr, though, so you'd return a dangling reference in those cases. Sadly, there are no std::optional<T&> :/ \$\endgroup\$ – hoffmale Nov 19 '17 at 11:09
  • 1
    \$\begingroup\$ Now that you mention it yes. But that's also a problem with ops current code that directly dereferences and copy constructs from a possibly null-ptr. \$\endgroup\$ – Emily L. Nov 19 '17 at 20:07
  • \$\begingroup\$ @EmilyL.: Oh, yeah. I was so taken in with all the extra copies that I completely overlooked the nullptr dereferences. \$\endgroup\$ – hoffmale Nov 20 '17 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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