在BST中使用unique_ptr而不是shared_ptr [英] Using unique_ptr instead of shared_ptr in BST
本文介绍了在BST中使用unique_ptr而不是shared_ptr的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在尝试使用unique_ptr实施BST.我有一个shared_ptr的工作程序.我该如何使用unique_ptr来代替BinarySearchTree的单一所有权语义?
I am trying to implement BST with unique_ptr. I got a working program for shared_ptr. How do I go about using unique_ptr instead to enforce the single ownership semantics of the BinarySearchTree?
当用unique_ptr替换shared_ptr时，出现了我无法理解的编译错误.
When I replace shared_ptr with unique_ptr, I get compilation errors beyond my understanding.
#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;
}
编译错误，以防有人感兴趣.警告:文字墙.
Compilation errors in case anyone is interested. Warning: Wall of text.
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
^
推荐答案
unique_ptr是不可分配的，但可以移动.我重新制作了您的示例，现在可以与unique_ptr一起使用.请注意，我使用std::move以便将内容从一个unique_ptr移动到另一个.同样由于unique_ptr是不可复制的事实，我在成员函数中通过引用而不是通过值传递unique_ptr s:
unique_ptrs are not assignable but moveable. I reworked your example and now works with unique_ptrs. Notice, that I use std::move in order to move contents from one unique_ptr to another. Also due to the fact that unique_ptr isn't copyable, I pass unique_ptrs in member functions by reference and not by value:
#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;
}
这篇关于在BST中使用unique_ptr而不是shared_ptr的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
