Использование shared-ptr против unique-ptr для конкретного алгоритма двоичного дерева - PullRequest
Новая
       60

Использование shared-ptr против unique-ptr для конкретного алгоритма двоичного дерева

0 голосов
/ 19 мая 2018

Я работал над реализацией различных алгоритмов двоичного дерева, используя умные указатели вместо необработанных указателей.У меня есть достаточно четкое понимание различий между общими / уникальными указателями и тем, когда их использовать, но этот конкретный алгоритм доставляет мне много хлопот.

Это моя реализация TreeNode с unique_ptr слева и справа.children. 

struct UniqueTreeNode {

    /*Construction via int value*/
    explicit UniqueTreeNode(const int v) : val(v), left(nullptr), right(nullptr), parent(nullptr) {}

    ~UniqueTreeNode() { std::wcout << L"Destroy: " << val << std::endl; }

    /*Printing Utility for unique_ptr to tree node.*/
    friend std::wostream& operator<<(std::wostream& wout, const std::unique_ptr<UniqueTreeNode>& n) {
        std::wstringstream wss;
        print(n.get(), std::wstring(), wss, Child::LEFT);
        return wout << wss.rdbuf();
    }

    /*Printing Utility shared_ptr to tree node.*/
    friend std::wostream& operator<<(std::wostream& wout, const std::shared_ptr<UniqueTreeNode>& n) {
        std::wstringstream wss;
        print(n.get(), std::wstring(), wss, Child::LEFT);
        return wout << wss.rdbuf();
    }

    /*Printing Utility for tree node pointer.*/
    friend std::wostream& operator<<(std::wostream& wout, UniqueTreeNode* n) {
        std::wstringstream wss;
        print(n, std::wstring(), wss, Child::LEFT);
        return wout << wss.rdbuf();
    }

    /*Enum utility to pick child*/
    enum class Child { LEFT, RIGHT };
    static void print(UniqueTreeNode* n, std::wstring ws, std::wstringstream& wss, const Child& c);

    /*Construction level-by-level via vector*/
    static std::unique_ptr<UniqueTreeNode> construct(const std::vector<int>& v);

    int val; // Data element in node.
    std::unique_ptr<UniqueTreeNode> left, right; // left & right child pointers.
    UniqueTreeNode* parent; // parent raw pointer.
};


/**
* \brief Prints the tree level by level.
* \param n current node being processed.
* \param ws wide-string for storing prefix.
* \param wss appends result incrementally.
* \param c child being considered currently.
*/
inline void UniqueTreeNode::print(UniqueTreeNode* n, const std::wstring ws, std::wstringstream& wss, const Child& c) {
    if (!n) wss << L"Empty Tree";
    else {
        if (n->right) print(n->right.get(), ws + (c == Child::LEFT ? L"│   " : L"    "), wss, Child::RIGHT);
        wss << ws << (c == Child::LEFT ? L"└── " : L"┌── ") << std::to_wstring(n->val) << L"\n";
        if (n->left)  print(n->left.get(), ws + (c == Child::LEFT ? L"    " : L"│   "), wss, Child::LEFT);
    }
}

/**
* \brief Construction of tree via vector elements.
* \param v vector of elements to add.
* \return the tree after its constructed.
*/
inline std::unique_ptr<UniqueTreeNode> UniqueTreeNode::construct(const std::vector<int>& v) {
    if (v.empty()) return nullptr;
    auto it = v.cbegin();
    auto n = std::make_unique<UniqueTreeNode>(*it);
    std::queue<UniqueTreeNode*> q({ n.get() });
    while (++it != v.cend()) {
        auto *x = q.front(); q.pop();
        x->left = std::make_unique<UniqueTreeNode>(*it), q.push(x->left.get());
        if (++it == v.cend()) break;
        x->right = std::make_unique<UniqueTreeNode>(*it), q.push(x->right.get());
    }
    return n;
}

Реализация, представленная ниже, является моей попыткой решить проблему Максимальное двоичное дерево с помощью leetcode.Однако, что бы я ни пытался, я не могу найти способ решить эту проблему с помощью unique-ptrs.Это просто из-за того, что мне нужно хранить указатель на мой узел в std :: deque, а также на их последующие дочерние элементы.Конечно, я мог легко сделать это с помощью shared-ptr детей, но мне было интересно, можно ли вообще сделать это с помощью уникальных ptrs.Мне известна возможность конвертировать unique_ptr в shared_ptr, чтобы воспользоваться подсчетом ссылок, но я не могу переместить shared_ptr в правый / левый потомок в моих узлах unique_ptr.Вот код с unique_ptrs. 

uTreeNode ConstructMaxTree(const vector<int>& v) {
    deque<uTreeNode> s;
    for (const auto val : v) {
        auto n = make_unique<UniqueTreeNode>(val);
        while (!s.empty() && s.back()->val < val) {
            n->left = move(s.back());
            s.pop_back();
        }
        if (!s.empty()) {
            s.back()->right = move(n);
        }  
        s.emplace_back(move(n));
    } 
    return move(s.front());
}

Здесь uTreeNode - просто псевдоним для std :: unique_ptr.Я также знаю, что n перемещается дважды, и это не разрешено для unique_ptrs.Мне было интересно, есть ли у кого-нибудь понимание того, какие существуют альтернативы, если есть возможность использовать shared_ptr для решения этой проблемы.

...