如何使用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;
    }
}

您有：函数，错误和所有功能的迭代版本。

我们可以利用唯一_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();
    }
}

我们只需获取内容并使用原始的基础指针，而不是在智能指针包装纸的顶部操作。