如何使用unique_ptr进行迭代？

Question

我有一个二进制搜索树实现，其中树的每个节点都有这样的结构。

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

我已经实现了一个findmin例程，它返回给定树根的最小数据(最左边节点的数据)。目前，我已经递归地实现了它。

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

这是可行的，但我想迭代地实现它。对于普通的指针，我们可以赋值，然后继续遍历最左边的节点curr = curr->left，但是这样的赋值对unique_ptr不起作用。

有没有一种方法可以迭代地实现它？

Answer 1

当前函数的问题是它需要引用。我们不能直接将其转换为循环，因为您不能重新放置引用(=使其指向其他地方)。

但是，我们可以用指针来做！我们只需在每次使用时添加*即可。

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;
    }
}

现在你有了它:你的函数的迭代版本，bug和所有东西。

我们可以通过利用unique_ptr的方法之一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();
    }
}

我们不是在智能指针包装器之上操作，而是简单地获取内容并使用原始的底层指针。