Recursive binary search tree

Question

How is my usage of std::unique_ptr() and std::move()? How can I improve this code?

//I don't know what to return when key is not found, so throw std::runtime_error()
//this code does not have handwritten copy/move/destruct because I think unique_ptr already handled the node pointers
template<typename T>
using Ptr = std::unique_ptr<T>;
template<typename K, typename V>
class Bst {
 struct Node {
 K key;
 V val;
 std::size_t n;
 Ptr<Node> left;
 Ptr<Node> right;
 Node(const K& k, const V& v, const std::size_t& s) : key(k), val(v), n(s), left(nullptr), right(nullptr) { }
 };
 Ptr<Node> root;
public:
 Bst() :root{nullptr} { }
 std::size_t size() {
 return size(root);
 }
 std::size_t size(Ptr<Node>& t) {
 return (t == nullptr) ? 0 : t->n;
 }
 void insert(const K& k, const V& v) {
 root = insert(root,k,v);
 }
 Ptr<Node> insert(Ptr<Node>& t, const K& k, const V& v) {
 if (t == nullptr) {
 Ptr<Node> node(new Node(k,v,1));
 return node;
 }
 if (k < t->key) {
 t->left = insert(t->left,k,v);
 } else if (k > t->key) {
 t->right = insert(t->right,k,v);
 } else {
 t->val = v;
 }
 t->n = size(t->left)+size(t->right)+1;
 return std::move(t);
 }
 V& operator[](const K& k) {
 return get(root,k);
 }
 V& get(Ptr<Node>& t, const K& k) {
 if (t == nullptr) {
 t = insert(t,k,{});
 return t->val;
 }
 if (k < t->key) {
 return get(t->left,k);
 } else if (k > t->key) {
 return get(t->right,k);
 } else {
 return t->val;
 }
 }
 K min() {
 check(root);
 return min(root)->key;;
 }
 Ptr<Node>& min(Ptr<Node>& t) {
 if (t->left == nullptr) {
 return t;
 }
 return min(t->left);
 }
 K max() {
 check(root);
 return max(root)->key;
 }
 Ptr<Node>& max(Ptr<Node>& t) {
 if (t->right == nullptr) {
 return t;
 }
 return max(t->right);
 }
 void remove_min() {
 check(root);
 root = remove_min(root);
 }
 Ptr<Node> remove_min(Ptr<Node>& t) {
 if (t->left == nullptr) {
 return std::move(t->right);
 }
 t->left = remove_min(t->left);
 t->n = size(t->left)+size(t->right)+1;
 return std::move(t);
 }
 void remove_max() {
 check(root);
 root = remove_max(root);
 }
 Ptr<Node> remove_max(Ptr<Node>& t) {
 if (t->right == nullptr) {
 return std::move(t->left);
 }
 t->right = remove_max(t->right);
 t->n = size(t->left)+size(t->right)+1;
 return std::move(t);
 }
 void remove(K k) {
 root = remove(root, k);
 }
 Ptr<Node> remove(Ptr<Node>& t, K k) {
 check(t);
 if (k < t->key){
 t->left = remove(t->left, k);
 } else if (k > t->key){
 t->right = remove(t->right, k);
 } else {
 if (t->right == nullptr) {
 return std::move(t->left);
 }
 if (t->left == nullptr) {
 return std::move(t->right);
 }
 Ptr<Node> d = std::move(t);
 t = std::move(min(d->right));
 t->right = remove_min(t);
 t->left = std::move(d->left);
 }
 t->n = size(t->left)+size(t->right)+1;
 return std::move(t);
 }
 void traverse() {
 traverse(root);
 }
 void traverse(Ptr<Node>& t) {
 if (t == nullptr) {
 return;
 }
 traverse(t->left);
 std::cout << t->key << " " << t->val << '\n';
 traverse(t->right);
 }
private:
 void check(Ptr<Node>& t) {
 if (t == nullptr) {
 throw std::runtime_error("No node");
 }
 }
};

Answer 1

How is my usage of std::unique_ptr() and std::move()?

It's actually more common to use raw pointers with data structures, but I don't think it would hurt to use smart pointers instead. It would avoid the need for a destructor, though it's not too difficult to define a proper destructor for a tree.

My understanding of std::move() is that it's not particularly useful to return by that, even when it appears to be viable. This would also prevent the compiler from making its own decisions. A C++11 compliant compiler should be able to utilize move semantics as needed, and this is one of the times where it's better to let the compiler take over. Forcing something on it may cause problems, or it may simply try to ignore what you're telling it to do (this is where the code's behavior should be tested).

---

• There's no need for multiple private sections, especially with them in between one large public section. This can just be combined into one of the existing sections.

• This is greatly lacking const-correctness. Member functions that don't modify data members, such as getters, should be const:

  std::size_t size() const {
   return size(root);
  }
  

  Since there are many other applicable functions here, I'll let you find and change the rest of them. The compiler will correct you if you make a mistake with this.

  This also applies to objects of non-primitive types being passed to any type of function. If they're not being modified, they should be passed by const& (if move semantics are not viable).

• It makes more sense for Bst, not Node, to have a size field. One node won't have a particular size; it'll have value(s) and pointer(s). Having it for Bst will allow you to maintain the number of nodes currently in the structure. It'll also allow you to have just one size() member function that returns the value of this field.

• Since you're defining operator[], you should also have an at(), similar to the standard library. This should do the same thing, but also throw an exception if the index is out of bounds.

• lightning_missile: Thanks. How about my std::unique_ptr() and std::move()s? I think I move nodes a lot here. Is it fine doing that?
• Jamal: @morbidCode: I think your use of smart pointers here is okay. They clean themselves up, which I suppose is why there's no destructor. I'm not entirely sure about std::move, though. But there are more rules pertaining to having one returned, as mentioned here. Perhaps this type of return wouldn't be needed.
• lightning_missile: Um, I can't make it work when I remove std::move() from my returns. I should've experimented with it more before writing this tree. I'll fix it and maybe post a followup :)

Answer 2

Please don't introduce global name aliases in a header file like this:

template<typename T>
using Ptr = std::unique_ptr<T>;

You're setting yourself up for name collisions and other nasties. Just use the god... I mean committee given names.

If you really want a shorthand, then use a type-local alias. Like this:

template<typename K, typename V>
class Bst {
private:
 struct Node;
public:
 typedef std::unique_ptr<Node> NodePtr;

It encapsulates the shorthand with the context in which it is used. As an added benefit you can now change the implementation from unique_ptr to shared_ptr if need be, without affecting the rest of the application.

The C++11 keyword auto will save your clients typing Bst::NodePtr. Also NodePtr is shorter to type than Ptr<Node> ;)

I agree with RubberDuck on the naming. Prefer BinarySearchTree as class name. Also I'm leaving the indepth review for some one with more time on their hands.

• Jamal: I do like the name NodePtr instead of Ptr here. Though, I feel that an alias is not really necessary, and it especially shouldn't need to be public. This is part of the implementation detail that the user doesn't need to see.
• Emily L.: @Jamal Please not the wording "If you really want an alias". Also the public interface returns and uses Ptr<Node> hence I made it public to be compatible as I wasn't reviewing anything else in OP.

Answer 3

Y u shrt yr nms?

Bst is a really bad name. It's completely meaningless. Call your class what it is, a BinarySearchTree. You have a similar issue with your names for Key and Value. Code is read much more often than it's written, so it's important to be crystal clear with our naming. Particularly our public API. What would you think/say if you say this in some code you were unfamiliar with?

Bst * p1 = new Bst;

I'll leave an actual review of your implementation to the c++ experts though.

• lightning_missile: Um, I thought everyone knows what Bst means, just like Ptr for pointers. I'll make better names next time :)
• RubberDuck: @morbidCode imagine it's not your code for a moment. What would you think of Node.K or Node.V?? Do those names tell you anything at all about what they are or do?
• Emily L.: @morbidCode Assumption is the mother of all fk-ups. BST can match many things: BST
• Alnitak: @RubberDuck but he doesn't have Node.K, he has Node.key, with K as a very conventional template identifier for the type of it.
• Thomas: If a programmer can't instantly recognize what the K and V types represent in a key-value datastructure then he should probably put down the keyboard and go to sleep because he's obviously had a bit too much to drink. Being explicit is one thing, being overdescriptive to the point of complete and utter redundancy is quite another.