在BST中使用unique_ptr代替shared_ptr

Question

我正在尝试使用unique_ptr实现二叉搜索树。 我已经用shared_ptr编写了一个工作程序。 如果我想使用unique_ptr来强制执行BinarySearchTree的单一所有权语义，该怎么办？

当我将shared_ptr替换为unique_ptr时，我遇到了超出我的理解范围的编译错误。

#include <iostream>
#include <memory>

template<class T>
class BinarySearchTree{
    struct TreeNode;
    typedef std::shared_ptr<TreeNode> spTreeNode;
    struct TreeNode{
        T data;
        spTreeNode  left;
        spTreeNode  right;
        TreeNode(const T & value):data(value),left(nullptr),right(nullptr){}
    };



    spTreeNode root;
    bool insert(spTreeNode node);
    void print(const spTreeNode) const ;
public:
    BinarySearchTree();
    void insert( const T & node);
    void print()const;
};

template<class T>
BinarySearchTree<T>::BinarySearchTree():root(nullptr){}

template<class T>
void BinarySearchTree<T>::insert(const T & ref)
{
    TreeNode *node = new TreeNode(ref);
    if (root==nullptr)
    {
        root.reset(node);
    }
    else
    {
        spTreeNode temp = root;
        spTreeNode prev = root;
        while (temp)
        {
            prev = temp;
            if (temp->data < ref)
                temp = temp->right;
            else
                temp = temp->left;
        }
        if (prev->data  < ref)
            prev->right.reset(node);
        else
            prev->left.reset(node);
    }
}

template<class T>
void BinarySearchTree<T>::print()const
{
    print(root);
}

template<class T>
void BinarySearchTree<T>::print(const spTreeNode node)const
{
    if (node==nullptr)
        return;
    print(node->left);
    std::cout << node->data<< std::endl;
    print(node->right);
}

int main()
{
    BinarySearchTree<int> bst;
    bst.insert(13);
    bst.insert(3);
    bst.insert(5);
    bst.insert(31);
    bst.print();
    return 0;
}

编辑：如果有人感兴趣，这里提供编译错误信息。警告：文本堆积如山。

    prog.cpp: In instantiation of ‘void BinarySearchTree<T>::insert(const T&) [with T = int]’:
prog.cpp:75:18:   required from here
prog.cpp:39:27: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’
         spTreeNode temp = root;
                           ^
In file included from /usr/include/c++/4.8/memory:81:0,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here
       unique_ptr(const unique_ptr&) = delete;
       ^
prog.cpp:40:27: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’
         spTreeNode prev = root;
                           ^
In file included from /usr/include/c++/4.8/memory:81:0,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here
       unique_ptr(const unique_ptr&) = delete;
       ^
prog.cpp:43:18: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>& std::unique_ptr<_Tp, _Dp>::operator=(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’
             prev = temp;
                  ^
In file included from /usr/include/c++/4.8/memory:81:0,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/unique_ptr.h:274:19: error: declared here
       unique_ptr& operator=(const unique_ptr&) = delete;
                   ^
prog.cpp:45:22: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>& std::unique_ptr<_Tp, _Dp>::operator=(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’
                 temp = temp->right;
                      ^
In file included from /usr/include/c++/4.8/memory:81:0,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/unique_ptr.h:274:19: error: declared here
       unique_ptr& operator=(const unique_ptr&) = delete;
                   ^
prog.cpp:47:22: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>& std::unique_ptr<_Tp, _Dp>::operator=(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’
                 temp = temp->left;
                      ^
In file included from /usr/include/c++/4.8/memory:81:0,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/unique_ptr.h:274:19: error: declared here
       unique_ptr& operator=(const unique_ptr&) = delete;
                   ^
prog.cpp: In instantiation of ‘void BinarySearchTree<T>::print() const [with T = int]’:
prog.cpp:79:15:   required from here
prog.cpp:59:15: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’
     print(root);
               ^
In file included from /usr/include/c++/4.8/memory:81:0,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here
       unique_ptr(const unique_ptr&) = delete;
       ^
prog.cpp:63:6: error:   initializing argument 1 of ‘void BinarySearchTree<T>::print(BinarySearchTree<T>::spTreeNode) const [with T = int; BinarySearchTree<T>::spTreeNode = std::unique_ptr<BinarySearchTree<int>::TreeNode, std::default_delete<BinarySearchTree<int>::TreeNode> >]’
 void BinarySearchTree<T>::print(const spTreeNode node)const
          ^

- Ian McGrath

---

也许发布这些编译错误会帮助我们理解。编辑：但是你的其中一个函数通过值（即复制）获取指针。但是 unique_ptr 只能被移动。 - Quentin

@Quentin，我可以，但它们非常长。无论如何，我会发布它们。 - Ian McGrath

在遍历树时，请使用TreeNode*（无所有权），而不是unique_ptr<TreeNode>（独占所有权）。树拥有所有权，而非遍历它的代码。 - Ben Voigt

Answer 1

unique_ptr 不可赋值但可移动。我重构了你的示例，现在可以使用 unique_ptr 了。请注意，我使用 std::move 来将内容从一个 unique_ptr 移动到另一个。另外由于 unique_ptr 不可复制，所以我通过引用而不是值来传递成员函数中的 unique_ptr：

#include <iostream>
#include <memory>

template<class T>
class BinarySearchTree{
    struct TreeNode;
    typedef std::unique_ptr<TreeNode> spTreeNode;
    struct TreeNode{
        T data;
        spTreeNode  left;
        spTreeNode  right;
        TreeNode(const T & value):data(value),left(nullptr),right(nullptr){}
    };



    spTreeNode root;
    bool insert(spTreeNode &node);
    void print(const spTreeNode&) const ;
public:
    BinarySearchTree();
    void insert( const T & node);
    void print()const;
};

template<class T>
BinarySearchTree<T>::BinarySearchTree():root(nullptr){}

template<class T>
void BinarySearchTree<T>::insert(const T & ref)
{
    std::unique_ptr<TreeNode> node(new TreeNode(ref));
    if (root == nullptr) {
        root = std::move(node);
    } else {
        TreeNode* temp = root.get();
        TreeNode* prev = root.get();
        while (temp != nullptr) {
            prev = temp;
            if (temp->data < ref)
                temp = temp->right.get();
            else
                temp = temp->left.get();
        }
        if (prev->data < ref)
            prev->right = std::move(node);
        else
            prev->left = std::move(node);
    }
}

template<class T>
void BinarySearchTree<T>::print()const
{
    print(root);
}

template<class T>
void BinarySearchTree<T>::print(const std::unique_ptr<TreeNode> &node) const
{
    if(node == nullptr) return;
    print(node->left);
    std::cout << node->data<< std::endl;
    print(node->right);
}

int main()
{
    BinarySearchTree<int> bst;
    bst.insert(13);
    bst.insert(3);
    bst.insert(5);
    bst.insert(31);
    bst.print();
    return 0;
}

LIVE DEMO

- 101010

---

所以基本上，当您需要"分配"时--使用std::move，而当您只需遍历时，则使用get()？ - Ian McGrath

@IanMcGrath 基本上是的，但请注意 unique_ptr 不能被复制。因此，您无法将其作为值传递给函数作为输入参数，而应该通过引用传递。还要注意，使用 get 访问 unique_ptr 的内容时，请确保不要将此内容分配给另一个智能指针。 - 101010

谢谢。最后一个问题。如果我必须从某个函数返回一个节点，比如说getMaxValueNode()，我应该如何返回？ - Ian McGrath

@IanMcGrath 我个人认为你应该返回节点本身而不是 unique_ptr，因为你需要访问这个节点。正如之前提到的，unique_ptr 不可复制，因此你无法返回已经存在的 unique_ptr。但请注意，如果你在函数体内构造了一个 unique_ptr，并且在同一函数中返回它，编译器足够聪明，能够将这个 unique_ptr 移动，所以在这种情况下返回 unique_ptr 是可行的。 - 101010

有没有不使用 get() 的方法来实现这个？我们通过使用 unique_ptr 来遍历树，但是在遍历时切换到原始指针会很麻烦。我知道你这样做的原因，但我不知道如何避免它。有些东西告诉我 Scott Meyers 不会赞成这种做法。 - wcochran

Answer 2

模板化错误通常会很可怕，但是不要惊慌！所有这些“使用已删除的函数”的问题都是因为你尝试复制一个unique_ptr，而它的超能力来自于只能移动。跳转到每个出现这种错误的行，并分析情况：

您是否希望转移指针的所有权？那么请通过右值引用传递独占指针，并将其移动到新的持有者中。

// Take unique_ptr by rvalue reference
void TreeNode::setLeft(std::unique_ptr<TreeNode> &&node) {
    // Move it in a member variable
    left = std::move(node);
    // Now it's ours !
}

你只是想引用指针吗？使用const左值引用来引用unique_ptr，或者从unique_ptr.get()传递一个const原始指针。

// Take raw const pointer
bool isNodeLeft(TreeNode const *node) const {
    // Look at it but don't disturb it
    return node->value <= value;
}

当所有这些都处理完之后，你将得到一个编译码，或者其他错误，你将解决它们，或者我会更新这个答案。

注意： TreeNode *node = new TreeNode(ref); 在异常安全方面存在问题。你应该使用make_unique（来自C++1y）或自己编写。

代码如下：

template <class T, class... Args>
std::unique_ptr<T> make_unique(Args&&... args) {
    return unique_ptr<T>(new T(std::forward<Args>(args)...));
}

- Quentin

---

非常抱歉，我不明白。对于C++11智能指针还很陌生。您可以发一两行代码吗？非常感谢。 - Ian McGrath

搞定了。感谢你的指点（双关语）。现在，我唯一不明白的是make_unique这个东西，你能否发一行代码让我理解你的意思？ - Ian McGrath

@IanMcGrath，这是它们！ - Quentin

@IanMcGrath 哦，好吧。谢谢，很高兴我能帮到你 :) - Quentin