C ++ | BST referensi-ke-node-pointer vs. node-pointer

Question

Misalkan saya memiliki template BST ini:

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;
  }
};

Mengapa kode berikut berfungsi ketika saya meneruskan referensi-ke-node-pointer, tidak berfungsi ketika saya melewati-node-pointer?

// 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);
  }
};

Juga sebagai lawan dari metode alternatif ini, yang hanya bekerja dengan penunjuk yang diteruskan:

// 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);
    }
  }

---

Saya memahami bahwa referensi-ke-titik-akan memberi saya akses langsung ke penunjuk yang dilewati. Namun, saya terjebak pada perbedaan antara kedua metode tersebut. Dalam metode kedua, salinan lokal yang digunakan dalam alur kontrol masih berfungsi meskipun penunjuk itu sendiri tidak diteruskan sebagai referensi.

Answer 1

Masalah OP adalah tentang call-by-value vs. call-by-reference .

Bahasa C ("anchestor" dari C ++) menyediakan nilai panggilan-demi-secara eksklusif. Panggilan dengan referensi yang hilang dapat ditiru dengan menggunakan alamat variabel, bukan variabel itu sendiri. (Tentu saja, parameter fungsi resp. Harus menjadi penunjuk-ke-tipe alih-alih tipe itu sendiri.)

Jadi, pointer dilewatkan-oleh-nilai tetapi nilainya dapat digunakan untuk mengakses sesuatu di luar ruang lingkup fungsi, dan modifikasi (dilakukan pada penyimpanan aslinya) akan bertahan kembali dari fungsi itu.

Ketika C ++ berevolusi dari C, prinsip ini telah diambil alih. Namun, C ++ menambahkan panggilan-oleh-referensi seperti yang diketahui dari bahasa lain yang sebanding (misalnya Pascal).

Demonstrasi sederhana dari panggilan-dengan-nilai vs. panggilan-dengan-referensi:

#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';
}

Keluaran:

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

Penjelasan:

• Perubahan amemiliki efek lokal hanya callByValue()karena aditeruskan oleh nilai. (Yaitu salinan argumen diteruskan ke fungsi.)
• Perubahan dari amengubah argumen yang diteruskan callByRef()karena aditeruskan oleh referensi.

Gampang sekali? Tentu saja. Tapi itu persis sama jika jenis parameter intdari adigantikan oleh jenis lainnya - misalnya Node*atau bahkan Node<T>*.

Saya mengeluarkan baris yang relevan dari kode OP:

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

Jika nilai argumen parentadalah a nullptrmaka parentdiberikan alamat yang baru dibuat Node<T>. Dengan demikian, pointer (variabel) yang dikirimkan oleh referensi akan dimodifikasi. Oleh karena itu, modifikasi tetap ada setelah keluar dari fungsi _insert().

Alternatif lainnya:

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

Jika nilai argumen parentadalah a nullptrmaka parentdiberikan alamat yang baru dibuat Node<T>. Dengan demikian, penunjuk dilewatkan oleh nilai. Jadi, variabel (asli) (yang digunakan dalam panggilan) tidak diubah - dan masih berisi nullptrsaat fungsi dibiarkan.

Btw. Menurut ini, alamat yang dibuat Node<T>akan hilang. (Ini tidak disimpan lagi di mana pun.) Namun, Node<T>instance masih berada dalam memori yang dialokasikan - tidak dapat diakses hingga akhir proses - diturunkan ke bagian memori yang terbuang. Ini adalah contoh bagaimana kebocoran memori dapat terjadi.

Tolong, jangan bingung dengan fakta ini dengan yang lain bahwa penunjuk itu sendiri "meniru" sebuah referensi lewat. Modifikasi objek (tipe Node<T>) yang ditunjuk penunjuk (jika tidak nullptr) akan menjadi persisten.

Setelah melihat lebih dekat _add()tampaknya hanya objek runcing (tipe Node<T>) yang dimodifikasi tetapi tidak pernah penunjuk itu sendiri. Jadi, melewatkannya dengan nilai sudah cukup dan bagus.

Tetapi untuk pekerjaan yang benar _insert(), modifikasi parentitu sendiri harus menjadi gigih juga. Jadi, hanya alternatif pertama yang bekerja dengan benar.