在指针到指针场景中使用std::shared_ptr

Question

我创建了一个Node结构，用于二进制搜索树的实现。它使用共享指针来跟踪其子代：

template <class T> struct Node;
template <class T>
using Node_ptr = std::shared_ptr<Node<T>>;
template <class T>
struct Node {
Node_ptr<T> left;
Node_ptr<T> right;
const T label;
...
};

现在，我想要一个函数，给定一些子树和一个值，它将返回该特定值的节点或该节点将来应该位于的位置-find_node。

这就是目前的情况：

template <class T>
auto* find_node(Node_ptr<T>* node, const T& value) {
for (; *node && (*node)->label != value
; node = value < (*node)->label ? &(*node)->left : &(*node)->right);
return node;
}

相当糟糕。但它有效：

template <class T>
class Binary_search_tree {
public:
// correctly inserts consecutive values
void insert(const T& value) {
if (auto* node = find_node(&root, value); !*node)
*node = std::make_shared<Node<T>>(value);
}
...
private:
Node_ptr<T> root;
...
};

我可以重写find_node以使用std::shared_ptr<Node_ptr<T>>而不是Node_ptr<T>*，但它看起来会更糟。还是会呢？

我应该如何处理这种情况？

编辑：正如已经指出的，函数可以通过引用起始节点并返回对节点的引用来简化一点：

template <class T>
Node_ptr<T>& find_node(Node_ptr<T>& node_ref, const T& value) {
auto* node = &node_ref;
...
return *node;
}

Answer 1

1. 当您必须允许传递空指针时，建议使用原始指针——在您的示例中不是这样；或者当您必须传递非整数值时(在您的情况下为true(。在后一种情况下，仍然应该考虑传递引用而不是原始指针。这是一个通用的建议，因此可能存在例外。

2. 注意到这一点，通过将find_node(…(设为私有函数，同时保持insert(…(为公共函数，您仍然可以在函数中安全地使用原始指针。这是安全的，因为没有机会让指针从插入的内部悬空(…(

本质上，我们需要防范使用原始指针的两种可能性：#1。过早地删除指针指向的内存，#2。永远不要删除指针指向的内存。在insert(…(函数中，这两者都不可能。所以你是安全的。

与此相关的是，您可能会考虑在创建节点时为其设置unique_pointer，然后如果要由多个子节点共享，则将其转换为共享指针：std:：move(…(。