CODEWITHSUNDEEP
c++c++11smart-pointers
bornfree
bornfree

Reputation: 2528

How to use unique_ptr for iteration?

I have a binary search tree implementation where each node of the tree has this structure.

struct node {
        T data;
        std::unique_ptr<node> left, right;
        node(T data): data(data), left(nullptr), right(nullptr) {}
    };

I have implemented a findmin routine that returns the minimum data(left most node's data), given the root of the tree. At present, I have implemented it recursively.

template<typename T>
T Btree<T>::_findmin(std::unique_ptr<node>& curr)
{
    if (curr && curr->left == nullptr)
        return curr->data;
    return _findmin(curr->left);    
}

This works but I would like to implement it iteratively. For a normal pointer, we can assign and then keep traversing the leftmost node curr = curr->left , but such an assignment won't work for unique_ptr.

Is there a way to implement it iteratively?

Upvotes: 1

Views: 996

Answers (1)

melpomene
melpomene

Reputation: 85767

The problem with your current function is that it takes a reference. We can't directly transform it to a loop because you can't reseat a reference (= make it point somewhere else).

However, we can do it with a pointer! We just have to add * every time we use it.

template<typename T>
T Btree<T>::_findmin(std::unique_ptr<node> &root)
{
    std::unique_ptr<node> *curr = &root;
    while (true) {
        if (*curr && (*curr)->left == nullptr)
            return (*curr)->data;
        curr = &(*curr)->left;
    }
}

And there you have it: An iterative version of your function, bugs and all.

We can get rid of one level of indirection by taking advantage of one of unique_ptr's methods, get():

template<typename T>
T Btree<T>::_findmin(std::unique_ptr<node> &root)
{
    node *curr = root.get();
    while (true) {
        if (curr && curr->left == nullptr)
            return curr->data;
        curr = curr->left.get();
    }
}

Instead of operating on top of the smart pointer wrappers, we simply get the contents and use the raw underlying pointers.

Upvotes: 6

Related Questions