Деструктор связанного списка с помощью std::move C++
Я изучаю структуры данных в C++;
Я написал деструктор для связанного списка следующим образом:
~List(){
Node* temporary = new Node;
Node* node = head;
while(node != nullptr){
temporary = node;
node = node->next;
delete temporary;
}
}
Но потом я понял, что я могу сделать:
~List(){
Node* node = head;
while(node != nullptr){
node = std::move(node->next);
}
}
Избегая создания временного объекта, я пробовал и работал нормально, но я не знаю, нормально ли это, я не нашел такого деструктора ни в одном другом месте.
Я думаю, вы неправильно понимаете, как работают объекты в C++. Это не Java, я бы порекомендовал хорошую книгу по C++. std::move не звонит delete.
Если вы изучаете структуры данных, первое, что нужно усвоить (ИМХО), это то, что «связанный список» — это едва ли не худшая структура данных, которую вы можете использовать. Но если вы хотите настаивать на ужасном, то хотя бы не кодируйте сами, используйте std::list.
@François Andrieux Разве std::move не удаляет указатель после вызова?
Вам удалось внедрить - и пропустить - динамическое выделение в деструкторе. Определенно второе предложение прочитать хорошую книгу.
Node* temporary = new Node; Значит, чтобы снести ряд домов, ты сначала идешь и строишь новый дом? Я не думаю, что бизнес по сносу, который занимается этим, долго не протянет.
@EricCardozo Нет, это не так. Указатели являются тривиальным фундаментальным типом, и их перемещение аналогично их копированию. Указатель просто содержит значение, которое говорит «какой объект». Это не тот объект, на который он указывает. Возможно, вы знакомы с языками высокого уровня, такими как Java или C#, где переменные обычно являются ссылками на экземпляр, управляющий временем жизни, но в C++ указатели работают иначе.
"Разве std::move не удаляет указатель после вызова?" - Нет. std::move - это не что иное, как ссылка на rvalue. Он ничего не делает сам по себе.
перемещение может быть разрушительным, но это только в том случае, если вы используете владеющие умными указателями или другими нетривиальными типами (и это происходит, когда вы используете ссылку rvalue в перемещении или присваивании, а не когда вы выполняете приведение)
@Jesper Juhl Итак, все должны бросить свои специальности CS и бросить программирование, потому что все уже выдумано, вместо этого я должен искать работу по продаже автомобилей. Зачем учить С++? Могу ли я сделать это проще на питоне?
@EricCardozo Делай, что хочешь. Но я бы все же посоветовал против связанных списков. Кроме того, университет не выпускает таких замечательных настоящих программистов — их всегда приходится переучивать.
Нет ничего плохого в том, чтобы переписать существующие контейнеры для изучения IMO, но пока урок заключается в том, что вы еще не понимаете указатели.
fwiw с std::unique_ptr<Node> ваш код будет работать.
«Я понял, что могу: [код] Избежать создания временного объекта» — более простой способ избежать создания «временного» объекта — не создавать его. (Если вы удалите = new Node из своего первого блока кода, вы избежите создания ненужного объекта, не влияя ни на что другое.)
Ответы 2
Этот фрагмент кода
~List(){
Node* temporary = new Node;
Node* node = head;
while(node != nullptr){
temporary = node;
node = node->next;
delete temporary;
}
}
производит утечку памяти из-за этого ненужного выделения памяти
Node* temporary = new Node;
В этом фрагменте кода
~List(){
Node* node = head;
while(node != nullptr){
node = std::move(node->next);
}
}
ни одна память не освобождается. Только указатель node переназначается до тех пор, пока он не станет равным нулевому указателю. Итак, снова многочисленные утечки памяти.
Если вы не хотите использовать промежуточную переменную, то деструктор можно написать, например, следующим образом
#include <functional>
//...
~List(){
while ( head ) delete std::exchange( head, head->next );
}
}
Почему ручное управление памятью, а не умные указатели?
@JesperJuhl Где вы нашли умные указатели в исходном вопросе? Очевидно, что автор вопроса учится управлять памятью с помощью new и delete.
И удалить дальше деструктор Node? если вы решили реализовать односвязный список, я не уверен, что рекурсивные деструкторы — это улучшение.
@Useless Нет рекурсивных разрушений. Используется цикл while.
@JesperJuhl есть несколько идей структуры данных хуже, чем у связанного списка. Один из них — связанный список с умными указателями.
Нет рекурсивных уничтожений, потому что вы не используете интеллектуальные указатели, владеющие узлом.
std::move ничего не делает сам по себе, он только приводит что-то к rvalue.
То, как используется rvalue, определяется функцией, которая его принимает, и в этом случае назначение необработанного указателя ничем не отличается от копирования.
Но, например, если вы используете std::unique_ptr, оператор =(unique_ptr&&) удалит исходные данные после присваивания*.
поэтому, если вы используете что-то вроде
#include <memory>
struct Node{
std::unique_ptr<Node> next;
// possibly move List destructor here
// i.e. destruct a Node would safely remove all sub-node non-recursively
};
struct List{
std::unique_ptr<Node> head;
// write destructor to prevent deep recursion
~List(){
while(head) head = std::move(head->next); // current head is deleted after assignment
}
};
тогда это сработает
*btw, self-assignment is safe because it's actually effectively reset(r.release())
std::moveна указателе ни на что не влияет. Ясно, что вы что-то неправильно понимаете в объектной модели C++, но я не уверен, что это за недоразумение. Можете ли вы пояснить, почему вы думаете, что этот ход заменитdelete? Во втором примере происходит утечка узла. Также странноnewобъект в деструкторе.