我已经用 C++ 实现了二叉搜索树。我没有使用裸指针指向子节点,而是使用了 std::shared_ptr
.树的节点实现如下
struct treeNode;
typedef std::shared_ptr<treeNode> pTreeNode;
struct treeNode {
T key;
pTreeNode left;
pTreeNode right;
treeNode(T key) : key(key), left(nullptr), right(nullptr) {}
};
从 BST 中删除一个节点时,其中一种情况是该节点只有一个 child 。节点简单地被这个 child 替换,如下所示:
| remove node
node ---------> |
\ right
right
在类似的 Java 实现中,这可以编码为:
node = node.getRight();
在我的 C++ 实现中它是:
node = node->right;
节点的类型是 pTreeNode
.
在 pTreeNode
上调用 = 运算符时( std::shared_ptr<TreeNode>
), node
的析构函数将被调用。指向底层的共享指针数量 TreeNode
是 1,因此 TreeNode
被摧毁释放它的内存。当 TreeNode
(默认)析构函数被调用,它的每个成员都被销毁。这肯定会导致 pTreeNode right
成员被销毁。问题是 node->right
是分配给 node
的内容.在测试我的 BST 时,它似乎工作正常,没有错误/内存泄漏。
- 我正在做的事情不安全吗?
- 如果它不安全,我该怎么做才能解决这个问题?
我认为可能有用的“hack”是制作另一个指针以增加其引用计数。这是一个合适的解决方案吗?
//increase reference to node->right by 1 so it doesn't get destroyed
pTreeNode temp(node->right);
node = node->right;
最佳答案
你显然假设,在
node = right;
shared_ptr
的赋值运算符可能会在从right
完成读取之前减少节点的计数(或在增加right
使用的引用计数之前) .但是,根据cppreference,使用
template<typename T>
template<typename U>
std::shared_ptr<T> &std::shared_ptr<T>::operator =(const std::shared_ptr<U> &);
作为
node = right; // std::shared_ptr<treeNode>
相当于
std::shared_ptr<treeNode>(right).swap(node);
这是安全的,因为 right
在 node
的旧值被销毁之前被复制。顺便说一句,我自己实现了一个共享指针,我确保“清理”旧值是我在 operator =
中所做的最后事情,正是为了避免此类问题。
关于c++ - 为 C++ 二叉搜索树使用智能指针,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45651401/