Как использовать 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;
    }
}

И вот что у вас есть: итерационная версия вашей функции, ошибки и все.

Мы можем избавитьсяодного уровня косвенности, используя один из методов 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();
    }
}

Вместо того, чтобы работать поверх оболочек интеллектуальных указателей, мы просто получаем содержимое и используем необработанные базовые указатели.