C ++ | การอ้างอิง BST-to-node-pointer เทียบกับ node-pointer

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

ปัญหาตรวจการณ์เป็นเรื่องเกี่ยวกับการเรียกร้องโดยค่าเมื่อเทียบกับการเรียกร้องโดยอ้างอิง

ภาษา C ("anchestor" ของ 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เมื่อฟังก์ชันเหลืออยู่

Btw. ด้วยเหตุนี้ที่อยู่ของผู้สร้างNode<T>จะสูญหายไป (ไม่ได้เก็บไว้ที่ใดอีกต่อไป) อย่างไรก็ตามNode<T>อินสแตนซ์ยังคงอยู่ในหน่วยความจำที่จัดสรรไว้ - ไม่สามารถเข้าถึงได้จนกว่าจะสิ้นสุดกระบวนการ - ถูกย่อยสลายจนกลายเป็นหน่วยความจำที่สูญเปล่า นี่คือตัวอย่างว่าหน่วยความจำรั่วอาจเกิดขึ้นได้อย่างไร

โปรดอย่าสับสนระหว่างข้อเท็จจริงนี้กับอีกข้อหนึ่งที่ว่าตัวชี้นั้น“ mimes” เป็นรหัสผ่านโดยอ้างอิง การแก้ไขวัตถุ (ประเภทNode<T>) ที่ตัวชี้ชี้ไปที่ (ถ้าไม่ใช่nullptr) จะกลายเป็นแบบถาวร

เมื่อมองอย่างใกล้ชิด_add()จะพบว่ามีการNode<T>ปรับเปลี่ยนเฉพาะวัตถุปลายแหลม (ชนิด) เท่านั้น แต่จะไม่มีตัวชี้ ดังนั้นการส่งผ่านมันไปตามมูลค่านั้นเพียงพอและดีอย่างสมบูรณ์

แต่สำหรับการทำงานที่ถูกต้องการ_insert()ปรับเปลี่ยนของparentตัวเองก็ต้องกลายเป็นเรื่องถาวรเช่นกัน ดังนั้นทางเลือกแรกเท่านั้นที่ทำงานได้อย่างถูกต้อง