Binary tree with C++11 smart pointers

Question

I'm trying to replace the use of raw pointers with smart pointers in my C++ code. The following bit is from my first attempt at a self-balancing binary tree, though there is nothing self-balancing at the moment. I am worried about some fundamental problems regarding the use of unique pointers.

template <typename K, typename D>
class rbtree {
 struct rbnode;
 typedef std::unique_ptr<rbnode> node_ptr;
 node_ptr root_;
 struct rbnode {
 node_ptr left, right;
 rbnode *parent;
 enum { Red, Black } color;
 D data;
 K key;
 rbnode(): 
 left(nullptr), right(nullptr), parent(nullptr), 
 color(Red), data(0), key(0) {}
 rbnode(K k, D d): 
 left(nullptr), right(nullptr), parent(nullptr), 
 color(Red), data(d), key(k) {}
 rbnode(K k, D d, rbnode *p): 
 left(nullptr), right(nullptr), parent(p), 
 color(Red), data(d), key(k) {}
 };
 node_ptr insert_(node_ptr& node, node_ptr& parent, K& key, D& data);
 public:
 bool insert(K& key, D& data);
 void dfs(std::function<void (K& key, D& data)> visitor);
};
template <typename K, typename D>
void rbtree<K, D>::dfs(std::function<void (K& key, D& data)> visitor) {
}
template <typename K, typename D>
typename rbtree<K, D>::node_ptr rbtree<K, D>::insert_(
 node_ptr& node, node_ptr& parent, K& key, D& data) {
 if (node == 0) { node = node_ptr(new rbnode(key, data, parent.get())); }
 if (key == node->key) { throw "Key exists!"; }
 if (key < node->key) {
 node->left = std::move(insert_(node->left, node, key, data));
 } else {
 node->right = std::move(insert_(node->right, node, key, data));
 }
 return std::move(node);
}
template <typename K, typename D>
bool rbtree<K, D>::insert(K& key, D& data) {
 root_ = std::move(insert_(root_, root_, key, data));
 root_->color = rbnode::Black;
 return true;
}

Answer 1

These two constructors are never used:

 rbnode(): 
 left(nullptr), right(nullptr), parent(nullptr), 
 color(Red), data(0), key(0) {}
 rbnode(K k, D d): 
 left(nullptr), right(nullptr), parent(nullptr), 
 color(Red), data(d), key(k) {}

I would remove them.

I don't see a use case for the first one (default constructor). But if you must have it then you probably don't want to use use 0 as the initializer for the key and value.

 // Note: This is one of the constructors I would remove.
 // But I just wanted to comment on the ** => data(0) and key(0) <= **
 // initialization. Because this means that Data and Key types
 // need to be initializable with zero (which is very limiting).
 //
 rbnode() 
 : left(nullptr)
 , right(nullptr)
 , parent(nullptr) 
 , color(Red)
 , data() // Use default constructor for user types.
 , key() // And for POD types this is zero-initialization.
 {}

Don't like the test against '0' here:

if (node == 0)

Prefer testing against nullptr. Not sure I like the implicit conversion to pointer but if it works I am not going to argue against it (personally I would have called get() to get at the underlying pointer for testing).

You probably want to pass by const reference or r-value reference here:

bool rbtree<K, D>::insert(K& key, D& data)

Currently it can not be used by the common case:

rbtree<int, int> x;
x.insert(5,6); // Fails to compile.
 // You can not pass references to tempories.
 // Note: You can pass temporaries by const reference.

You don't need to use std::move here:

 node->left = std::move(insert_(node->left, node, key, data));

The function std::move() converts a named value to an r-value reference. The return value of a function is already an r-value reference (I hope I got that correct).

• ratchet freak: the operator bool is overloaded for smart pointers to allow them to be used in conditionals so you can replace it with if(node) no need to get()
• Loki Astari: @ratchetfreak: That's even better.

Answer 2

Unless I missed something, it appears that bool rbtree<K, D>::insert(K& key, D& data) always returns true. It is quite misleading. If there is no way for this function to ever return anything but true, you could as well get rid of the bool return type.

Also, I propose a different approach than Loki's one for the default constructors of rbnode: you can use in-class members initializers for the default values:

struct rbnode
{
 node_ptr left { nullptr };
 node_ptr right { nullptr };
 rbnode *parent { nullptr };
 enum { Red, Black } color = Red;
 D data;
 K key;
 // Etc...
};

This way, your default constructor can be reduced to its simplest form:

rbnode() = default;

And the "default" values from the in-class member initializers will also be used to automatically initialize non-initialized members in the other constructors:

rbnode(K k, D d):
 data{d},
 key{k}
{}
rbnode(K k, D d, rbnode* p):
 parent{p},
 data{d},
 key{k}
{}

Note that I also used list initialization for some of the in-class members initializers and for the constructor initialization list. List initialization can help to avoid some problems related to implicit narrowing conversions of values.