在BST中使用unique_ptr代替shared_ptr

Question

我正在嘗試使用unique_ptr實現BST。我有一個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 
     ^

Answer 1

unique_ptr s爲不可轉讓，但可移動的。我重新修改了您的示例，現在可以與unique_ptr s一起使用。請注意，我使用std::move將內容從一個unique_ptr移動到另一個。另外，由於這樣的事實：unique_ptr是不可拷貝，我通過unique_ptr S IN的成員函數的引用而不是值：

#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

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

你只是想指向指針嗎？對unique_ptr使用const lvalue引用，或者傳遞unique_ptr.get（）中的const raw指針。

// 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)...)); 
}