c++ - C++ | BST对节点指针的引用与节点指针

Question

假设我有这个BST模板:

template <typename T> class Node {
private:
public:
  T data;
  Node *left;
  Node *right;

  Node(T dt) : data{dt}, left{nullptr}, right{nullptr} {}
  ~Node() {
    this->data = 0;
    this->left = nullptr;
    this->right = nullptr;
  }
};

template <typename T> class BST {
private:
  Node<T> *_root;

  _insert();
  _add();
  _printOrder_In(Node<T> *parent, std::ostream& os) {
    if (!parent) return;
    _printOrder_In(parent->left, os);
    os << parent->data << ' ';
    _printOrder_In(parent->right, os);
  }

public:
  BST() : _root{nullptr} {}
  ~BST();
  
  insert();
  add();
  std::ostream& print(std::ostream& os = std::cout) {
    _printOder_In(this->_root, os);
    return os;
  }
};

为什么以下代码在我传递对节点指针的引用时有效，而在我传递节点指针时不起作用？

// BST MEMBER FUNCTIONS:
private:
  void _insert(Node<T>* &parent, const T &val) { // works
//void _insert(Node<T>*  parent, const T &val) { // doesn't work, apparently generates nodes indefinitely
    if (!parent)
      parent = new Node<T>{val};
    else {
      if (val < parent->data)
        _insert(parent->left, val);
      else if (val > parent->data)
        _insert(parent->right, val);
      else
        return;
    }
  }

public:
  void insert(const T &val) {
    _insert(this->_root, val);
  }
};

与此替代方法相反，该替代方法仅对传递的指针起作用:

// BST MEMBER FUNCTIONS:
private:
  void _add(Node<T>* parent, T val) {
    if (parent->data > val) {
      if (!parent->left) {
        parent->left = new Node<T>{val};
      } else {
        _add(parent->left, val);
      }
    } else {
      if (!parent->right) {
        parent->right = new Node<T>{val};
      } else {
        _add(parent->right, val);
      }
    }
  }

public:
  void add(T val) {
    if (this->_root) {
      this->_add(this->_root, val);
    } else {
      this->_root = new Node<T>(val);
    }
  }

我知道指向该点将使我可以直接访问传递的指针。但是，我被两种方法的区别所困扰。在第二种方法中，尽管指针本身未作为引用传递，但在控制流中使用的本地副本仍然有效。

Answer 1

OP问题与call-by-value vs. call-by-reference有关。
语言C(C++的“主播”)专门提供按值调用。
可以通过使用变量的地址而不是变量本身来模拟缺少的按引用调用。
(当然，resp。函数的参数必须成为指向类型的指针，而不是类型本身。)
因此，指针是按值传递的，但是它的值可用于访问该函数范围之外的内容，并且修改(在其原始存储中完成)将在该函数的返回中保留下来。
当C++从C演变而来时，这一原理已被接管。
但是，C++像其他可比较的语言(例如Pascal)所知道的那样，添加了按引用调用。
按值调用与按引用调用的简单演示:

#include <iostream>

void callByValue(int a)
{
  std::cout
    << "callByValue():\n"
    << "  a: " << a << '\n'
    << "  a = 123;\n";
  a = 123;
  std::cout
    << "  a: " << a << '\n';
}

void callByRef(int &a)
{
  std::cout
    << "callByRef():\n"
    << "  a: " << a << '\n'
    << "  a = 123;\n";
  a = 123;
  std::cout
    << "  a: " << a << '\n';
}

int main()
{
  int b = 0;
  std::cout << "b: " << b << '\n';
  callByValue(b);
  std::cout << "b: " << b << '\n';
  callByRef(b);
  std::cout << "b: " << b << '\n';
}

输出:

b: 0
callByValue():
  a: 0
  a = 123;
  a: 123
b: 0
callByRef():
  a: 0
  a = 123;
  a: 123
b: 123

说明:

更改a仅在callByValue()中具有局部效果，因为a是按值传递的。 (即，将参数的副本传递给函数。)

更改a会修改callByRef()中传递的参数，因为a是通过引用传递的。

十分简单？当然。但是，如果将 int的参数类型 a替换为其他任何类型，例如，这完全相同。 Node*甚至 Node<T>*。
我从OPs代码中删除了相关行:

  void _insert(Node<T>* &parent, const T &val) { // works
    if (!parent)
      parent = new Node<T>{val};

如果参数 parent的值是 nullptr，则为 parent分配新创建的 Node<T>的地址。从而，修改了引用传递的指针(变量)。因此，修改在离开函数 _insert()后仍然存在。
另一种选择:

  void _insert(Node<T>*  parent, const T &val) { // doesn't work, apparently generates nodes indefinitely
    if (!parent)
      parent = new Node<T>{val};

如果参数 parent的值是 nullptr，则为 parent分配新创建的 Node<T>的地址。从而，指针按值传递。因此，(原始)变量(在调用中使用了)没有改变-离开函数后仍包含 nullptr。
顺便说一句。据此，创建的 Node<T>的地址丢失。
(它不再存储在任何地方。)
但是， Node<T>实例仍驻留在其分配的内存中-直到进程结束才可以访问-降级为一块浪费的内存。
这是 memory-leaks如何发生的示例。
请不要将此事实与指针本身“模仿”传递引用相混淆。
指针指向的对象(类型为 Node<T>)的修改(如果不是 nullptr)将变得持久。
仔细观察 _add()，似乎只修改了指向对象( Node<T>类型)，而没有修改指针本身。
因此，按值传递它完全足够而且很好。
但是，为了正确处理 _insert()，对 parent本身的修改也必须变得持久。
因此，只有第一个替代方案可以正常工作。