Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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).

share|improve this answer
3  
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() –  ratchet freak May 19 at 9:35
    
@ratchetfreak: That's even better. –  Loki Astari May 19 at 16:15
add comment

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 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 dafult 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, you 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 theo ther 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 fot constructor initialization list. List initialization can help to avoid some problems related to implicit narrowing conversions of values.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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