Двоичные деревья в C ++ с использованием ссылок

Question

Я хочу реализовать бинарное дерево, используя ссылки вместо указателей (это, как правило, то, что вы обычно найдете в каждой книге и на каждом веб-сайте в Интернете).Я попробовал следующий код:

class tree_node {
private:
    tree_node& left;
    tree_node& right;
    data_type data;
public:
    void set_left(tree_node&);
    // ... other functions here
};

void tree_node::set_left(tree_node& new_left) {
    this.left = new_left;
}

Я получаю следующую ошибку: ошибка C2582: функция 'operator =' недоступна в 'tree_node'.

Я знаю, что могу легко реализовать ее, используяуказатели, но я хотел бы сохранить мое решение элегантным и свободным от указателей.Можете ли вы сказать мне, где я иду не так?

Answer 1

Вы не можете изменить объект, на который ссылается ссылка ¹ ; как только вы инициализируете ссылку, она всегда ссылается на объект, с которым она была инициализирована.

Вы должны использовать указатели. В этом нет ничего плохого в использовании указателей (это тоже чисто, если использовать указатели, потому что родительские узлы владеют своими дочерними элементами, поэтому очистка и уничтожение просты!)

^{(1) Ну, вы могли бы явно вызвать деструктор объекта и затем использовать размещение new в реализации оператора присваивания, но это просто беспорядок!}

Answer 2

Ссылки - это не просто указатели с более коротким синтаксисом.Это другое имя для фактического объекта, к которому они относятся, даже когда они используются в качестве lhs присвоения.

int i = 3;
int j = 4;
int &ref = i;
ref = j;
std::cout << i << "\n"; // prints 4: i itself has been modified, 
                        // because semantically ref *is* i

То есть ref = j имеет тот же эффект, что и i = j, или такой жеэффект как *ptr = j, если вы сначала сделали int *ptr = &i;.Это означает «скопировать содержимое объекта j в любой объект, на который ссылается ref».

Для полного времени жизни ref он всегда будет ссылаться на i.Он не может быть использован для ссылки на любой другой тип int, то есть он не может быть «повторно установлен».

То же самое относится и к элементам ссылочных данных, просто их время жизни отличается от автоматических переменных.

Итак, когда вы пишете this.left = new_left, что означает , что означает , «скопируйте содержимое объекта new_left в любой объект, на который ссылается this.left».Что (а) не то, что вы имеете в виду, так как вы надеялись пересаживать this.left, и (б), даже если это было то, что вы имели в виду, это невозможно, поскольку this.left имеет ссылочные элементы, которые сами не могут быть повторно установлены.

Это (b) вызывает ошибку компилятора, которую вы видите, хотя (a) именно поэтому вы должны использовать указатели для этого.

Answer 3

Вы не можете назначить ссылки.То, что вы пытаетесь сделать, не может быть сделано ... без огромного количества изгибов ... (вы по сути уничтожите узел и создадите новый каждый раз, когда захотите его изменить.)

Есть веская причина, почему все эти люди используют указатели.

Answer 4

Моя рекомендация - использовать класс boost shared_ptr вместо ссылки. Это избавит вас от необходимости управлять освобождением указателя. Вас также может заинтересовать библиотека графов Boost .

Answer 5

Ссылки в C ++ не работают так же, как ссылки на других языках.После задания ссылки во время создания ее нельзя изменить на что-либо еще.