C ++ | BST 참조-노드 포인터 대 노드 포인터
이 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);
}
}
지점에 대한 참조가 전달 된 포인터에 직접 액세스 할 수 있음을 이해합니다. 그러나 나는 두 가지 방법의 차이에 갇혀 있습니다. 두 번째 방법에서는 포인터 자체가 참조로 전달되지 않더라도 제어 흐름에 사용 된 로컬 복사본이 계속 작동합니다.
답변
OP 문제는 call-by-value와 call-by-reference에 관한 것 입니다.
언어 C (C ++의 "anchestor")는 독점적으로 값별 호출을 제공합니다. 누락 된 참조 별 호출은 변수 자체 대신 변수의 주소를 사용하여 흉내낼 수 있습니다. (물론 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이 a 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이 a nullptr이면 parent에 새로 생성 된 주소가 할당됩니다 Node<T>. 따라서 포인터가 값으로 전달됩니다. 따라서 (호출에 사용 된) (원래) 변수는 변경되지 않고 nullptr함수가 남아 있는 시기를 여전히 포함합니다 .
Btw. 이에 따르면 생성 된 주소 Node<T>가 손실됩니다. (더 이상 어디에도 저장되지 않습니다.) 그러나 Node<T>인스턴스는 여전히 할당 된 메모리에 상주하며 프로세스가 끝날 때까지 액세스 할 수 없으며 낭비되는 메모리로 저하됩니다. 이것은 메모리 누수 가 발생 하는 방법의 예 입니다.
포인터 자체가 참조에 의한 전달을 "모방"한다는 사실을 다른 사실과 혼동하지 마십시오. Node<T>포인터가 가리키는 객체 (유형 )의 수정 (그렇지 않은 경우 nullptr)은 영구적입니다.
자세히 살펴보면 _add()뾰족한 개체 (유형 Node<T>) 만 수정되지만 포인터 자체는 수정되지 않는 것으로 보입니다 . 따라서 값으로 전달하는 것만으로도 충분하고 괜찮습니다.
그러나의 올바른 작동을 위해서는 자체 _insert()수정도 parent지속적이어야합니다. 따라서 첫 번째 대안 만 올바르게 작동합니다.