在指针场景中使用 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;
  ...
};

现在，我想要一个函数，它给定一些子树和一个值 return 该特定值的节点或该节点将来应位于的位置 - 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>* 但它看起来会更糟。还是会？

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

编辑：正如所指出的，可以通过引用起始节点并return引用节点来简化函数：

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

Answer 1

当您必须允许传递空指针时，建议使用原始指针 - 在您的示例中不是这样；或者当您必须传递一个非整数值时（在您的情况下为真）。在后一种情况下，仍应考虑传递引用而不是原始指针。这是一般性建议 - 因此可能存在例外情况。
注意到，通过将 find_node(...) 设为私有函数同时保留 insert(... ) public。这是安全的，因为不可能让指针在 insert(...).

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

在相关说明中，您可能会考虑在创建节点时为节点设置 unique_pointer，然后如果要由多个子节点共享它们，则将它们转换为共享指针：std::move (...).

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

Using std::shared_ptr in pointer to pointer scenario

c++

smart-pointers

shared-ptr

c++17