unique_ptr in class how to work with them

Question

I am implementing AVL tree in C++ and using unique_ptr for children.

struct Node 
{
    const int key;
    std::unique_ptr<Node> left, right;
    Node* parent;
    std::size_t height; ///< for avl tree.
    Node(const int key) : key(key), height(0) {}
};

class AVL
{
    std::unique_ptr<Node> root;
public:
    AVL(int rootKey) : root(std::unique_ptr<Node>(new Node(rootKey))) {
    }

    void insert(std::unique_ptr<Node> newNode) {
        std::unique_ptr<Node> & node = root;
        Node* parentWeak;
        while(node.get()) {
            parentWeak = node->parent;
            if (node->key == newNode->key)
                throw std::runtime_error("Key already present");
            if (node->key < newNode->key) 
                node = node->right;
            else
                node = node->left;
        }

        auto parent = parentWeak;
        const int key = newNode->key;

        if (parent == nullptr) {
            // there is no root
            root = std::move(newNode);
        } else {
            if (parent->key < newNode->key) {
                assert(NULL == parent->right.get());
                parent->right = std::move(newNode);
            } else {
                assert(NULL == parent->left.get());
                parent->left = std::move(newNode);
            }
        }

        // Now increment the height upto down.
        incrementHeight(key);
        // balance starting from parent upwards untill we find some dislanace in height 
        balance(parent, key); 
    }
};

I am getting compiler errors on line node = node->right;. Which is right because it can be possible with only std::move semantics. but that would be wrong because i want to just iterate over the tree, otherwise it would just remove them from the child-list.

However, i need the unique_ptr also, as it would passed in function balance as it would modify the pointers and re-balance the tree.

If i use shared_ptr it would all work. However, i do not need to share the ownership with others. Or am i misunderstanding ownership ?

Answer 1

Your problem seems to be caused by a lack of understanding how to use unique_ptr in real programs, which is related to the concept of ownership. If a something owns an object, it means, this something is responsible for keeping the object alive as long as this something keeps owning the object, and is responsible to destroy the object as soon as nothing owns the object anymore.

Both unique_ptr and shared_ptr can be used to own objects. The difference, you seem to be aware of, is that an object pointed to by unique_ptr can only have a single owner, while there might be multiple shared_ptr objects sharing ownership of a specific object. If a unique_ptr is destroyed or assigned a different value, by definition it can destroy the object it previously pointed to, as a unique_ptr is the single (unique) owner of an object.

Now you have to think about your tree: You can use shared_ptr for everything, which will likely (seems to) work, as objects are kept alive as long as there are references to them. If there really is the parent member in node which you use in your method but did not declare in the node structuer, you would be likely to create reference cycles, though, creating the danger of keeping objects around way too long (or even forever, this is called a memory leak), as shared_ptr in C++ is purely reference-counted. Two objects containing shared_ptrs pointing to each other keep themselves alive forever, even if no other pointer points to them. It seems like in your shared_ptr solution, the parent member was a weak_ptr which is a sensible way to work around this problem, although possibly not the most efficient one.

You seem to want to improve performance and strictness of your code by using unique_ptr instead of shared_ptr which is commonly accepted as a very good idea, as it forces you to deal with ownership in much greater detail. Your choice that the tree owns the root node, and each node owns the children is a sound design. You seem to have removed the parent pointer, because it can not be a unique_ptr, as in that case, a node would be owned by its parents and any childrens it might have, violating the constraint that an object pointed to by unique_ptr may only have one owner. Also, the parent member can not be a weak_ptr, as weak_ptr can only be used with objects managed by shared_ptr. If you want to translate a design from shared_ptr to unique_ptr, you should consider changing weak_ptrs into raw pointers. A non-owning pointer to an object managed by unique_ptr that detects expiration of that object does not exist (it would not be effienctly implementable with the typical C++ memory management). If you need the property of being able to detect a non-owning pointer to be stale, keep using shared_ptr. The overhead for tracking non-owning pointers is almost as big as full shared-ownership semantics, so there is no middle ground in the standard library.

Finally, let's discuss the insert method. The node variable quite surely is not what you want. You correctly found out (possibly by a compiler error message) that node can not be a unique_ptr, as that would take away ownership from the tree object. In fact, having this variable refer to the root pointer in the tree is the right solution, as you don't want to mess around with ownership at this point, but just want to be able to get a grip on some node. But declaring it as a reference does not fit to the way you want to use it, because in C++ you can't re-seat a reference. What you do is you declare node to be just another name for this->root, so if you assign to node, you are overwriting your root node pointer. I am sure this is not what you intended. Instead, you want node to refer to a different object than it referred to before, so it needs to be something that references the root node and can be made to refer to something else. In C++, this means you want a pointer (as Jarod42 said in the comment). You have two choices at hand for the loop scanning the position where to insert:

• Use a raw pointer to node instead of a unique_ptr to node. As you don't need ownership, a raw pointer to node is good enough: You can be sure the owning pointer (this->root) keeps alive as long a you need it, so there is no danger of the object disappearing.
• Use a raw pointer to unique_ptr to node. This is essentially your approach, fixed to use a pointer instead of a reference.

As you say, you later need the unique_ptr to pass it to the balance function. If the balance function works out as it is now, and needs a unique_ptr argument, the decision is made: Having a copy of the raw pointer in node just doesn't do what you want, so you need the pointer-to-unique_ptr.