Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Модератор: Модераторы разделов

Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение жучара »

Друзья! Вот схематично изображён связный список в виде цепочки:
a -> b -> c -> d -> e -> f -> g

У меня в каждом узле вместо адреса следующего узла- вектор узлов с одним элементом. То есть сам узел вот такая структура:

Код: Выделить всё

struct uzel
{
	string date;
	vector <uzel> vuzel;
};
Теперь мы создадим, допустим 7 узлов, инициализируем поле "date" каждого и один в другой вложим. Вот создание узлов:

Код: Выделить всё

	struct uzel a;
	a.date = "aa";
	struct uzel b;
	b.date = "bb";
	struct uzel c;
	c.date = "cc";
	struct uzel d;
	d.date = "dd";
	struct uzel e;
	e.date = "ee";
	struct uzel f;
	f.date = "ff";
	struct uzel g;
	g.date = "gg";
А вот собсно делаем вышеупомянутую цепочку.

Код: Выделить всё

	f.vuzel.push_back (g);  
	e.vuzel.push_back (f);  
	d.vuzel.push_back (e);  
	c.vuzel.push_back (d);  
	b.vuzel.push_back (c);  
	a.vuzel.push_back (b);  
Получили что хотели.
Offtopic
В этом месте меня могут спросить- зачем я связываюсь с векторами, если у меня в каждом векторе всего один элемент. Дело в том, что это упрощённая задача. А в неупрощённой (оригинальной) задаче в каждом векторе не один, а n (1, 2, 3 и так далее) узлов (дерево, короче). Да плюс ещё в векторах, которые в чётных узлах (a, c, e, g) по одному элементу, а в векторах, которые в нечётных узлах (b, d, f)- произвольное количество элементов. Это я просто пытаюсь объяснить, насколько оригинальная задача сложна, поэтому не нужно сюда писать её условие, что мне многие ставят в вину- почему я не привожу начальные условия, а упрощённые. Да вот поэтому и не привожу.
Так, дальше. Задача- удалить из этой вот цепочки
a -> b -> c -> d -> e -> f -> g

Узлы, начиная, c узла d включительно. То есть чтобы этого остатка d -> e -> f -> g больше не было (и он не занимал память!) а осталось только a -> b -> c. Коль скоро имеем дело с векторами, то правильно будет нужные вектора обнулить. Ниже объяснение.

Код: Выделить всё

//если сделать так, то в цепочке останется останется только a
	//a.vuzel.resize(0);

	//если сделать так, то в цепочке останется останется только ab
	//a.vuzel[0].vuzel.resize(0);

	//если сделать так, то в цепочке останется останется только abc
	a.vuzel[0].vuzel[0].vuzel.resize(0);
То есть в последней, нужной нам операции я добрался до вектора, который хранил всего один узел d и удалил узел d. А узлы e, f, g удалились или нет? Понятно дело, если бы память под эти элементы выделялась по-другому (оператор new, например), то мне нужно было бы каждый узел удалять вручную (оператор delete), то есть рекурсивно пробегаться по ним. Если бы каждому узлу соответстовало несколько дочерних узлов, это бы ещё добавило хлопот (цикл). А тут, быть может, достаточно удалить один узел, а всего его дочерние и прадочерние удалятся автоматом и не буду занимать больше память?

Вот полностью код, компилить g++ foo.cpp

Код: Выделить всё

/*foo.cpp*/
#include <string>
#include <vector>
using namespace std;

struct uzel
{
	string date;
	vector <uzel> vuzel;
};

int main ()
{
	struct uzel a;
	a.date = "aa";
	struct uzel b;
	b.date = "bb";
	struct uzel c;
	c.date = "cc";
	struct uzel d;
	d.date = "dd";
	struct uzel e;
	e.date = "ee";
	struct uzel f;
	f.date = "ff";
	struct uzel g;
	g.date = "gg";

	////////////////////////////////////////////////////////////////////
	
	f.vuzel.push_back (g);  
	e.vuzel.push_back (f);  
	d.vuzel.push_back (e);  
	c.vuzel.push_back (d);  
	b.vuzel.push_back (c);  
	a.vuzel.push_back (b);  

	//останется только abc
	a.vuzel[0].vuzel[0].vuzel.resize(0);
	
	return 0;
}
Спасибо, кто откликнется. Debian 10.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Zer0
Сообщения: 479
ОС: Void, Slackware

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение Zer0 »

Попробуйте поискать потенциальные утечки памяти с помощью Valgrind. Небольшой пример на русском. В книге Камрана Амини Экстремальный Cи. Параллелизм, ООП и продвинутые возможности на стр. 190 и далее, тоже довольно приличный пример работы с Valgrind.
Memento mori ... сделай бэкап.
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение жучара »

Ужасно. Начать с того, что после этого кода
a.vuzel.push_back (b);
Уже будет один лишний объект b. А у меня таких лишних объектов будет ОЧЕНЬ много. То есть уже тут неправильно, тут утечка.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 20971
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение Bizdelnick »

жучара писал(а):
11.02.2023 15:54
То есть уже тут неправильно, тут утечка.
Если b на стеке, как в этом примере, то утечки не будет. Но вообще, конечно, тут надо использовать указатели и писать деструктор для их освобождения.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение жучара »

Bizdelnick писал:
11.02.2023 16:03
жучара писал(а):
11.02.2023 15:54
То есть уже тут неправильно, тут утечка.
Если b на стеке, как в этом примере, то утечки не будет. Но вообще, конечно, тут надо использовать указатели и писать деструктор для их освобождения.
почему не будет? вот:

Код: Выделить всё

/*foo.cpp*/
#include <string>
#include <vector>
#include <iostream>

using namespace std;

struct uzel
{
	string date;
	vector <uzel> vuzel;
	~uzel() {cout << date << endl;};
};

int main ()
{
	struct uzel a;
	a.date = "aa";
	struct uzel b;
	b.date = "bb";

	////////////////////////////////////////////////////////////////////
	
	a.vuzel.push_back (b);  
	getchar ();
	
	return 0;
}
после срабатывание getchar (); (ну то есть нажатия на клавишу) вот такая картина:

Shell

$ ./a.out

bb
aa
bb
$
То есть один лишний объект b существовал до самого конца программы.
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 20971
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение Bizdelnick »

жучара писал(а):
11.02.2023 16:11
То есть один лишний объект b существовал до самого конца программы.
Он существовал до выхода из функции main(). То, что оно в данном случае совпадает с концом программы, — частности.
Об утечках имеет смысл говорить только при выделении памяти в куче, стековые переменные побоку.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение жучара »

Bizdelnick писал:
11.02.2023 16:23
жучара писал(а):
11.02.2023 16:11
То есть один лишний объект b существовал до самого конца программы.
Он существовал до выхода из функции main(). То, что оно в данном случае совпадает с концом программы, — частности.
Об утечках имеет смысл говорить только при выделении памяти в куче, стековые переменные побоку.
ничё не понимаю. Я кладу объект в вектор и начинаю с ним, который в векторе, работать. Тот который не в векторе он лишний и хорошо бы его сразу же удалить, как только я положу его (а точнее, его копию в вектор). Но это, оказывается, частности. А слово "частности" в данном случае обозначает что? Ну то есть это всё фигня и ерунда, смею предположить?
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 20971
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение Bizdelnick »

жучара писал(а):
11.02.2023 16:44
Я кладу объект в вектор и начинаю с ним, который в векторе, работать. Тот который не в векторе он лишний и хорошо бы его сразу же удалить, как только я положу его (а точнее, его копию в вектор). Но это, оказывается, частности.
Частности не это, а то, что Вы всё проделываете в функции main. Проделывали бы в другой — объекты жили бы только до её завершения. Вот если бы Вы выделили память в куче, не освободили её из той же функции и не вернули указатель, по которому её можно было бы освободить потом, — это была бы утечка.
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение жучара »

Bizdelnick писал:
11.02.2023 17:02
жучара писал(а):
11.02.2023 16:44
Я кладу объект в вектор и начинаю с ним, который в векторе, работать. Тот который не в векторе он лишний и хорошо бы его сразу же удалить, как только я положу его (а точнее, его копию в вектор). Но это, оказывается, частности.
Частности не это, а то, что Вы всё проделываете в функции main. Проделывали бы в другой — объекты жили бы только до её завершения. Вот если бы Вы выделили память в куче, не освободили её из той же функции и не вернули указатель, по которому её можно было бы освободить потом, — это была бы утечка.
понял. В первом коде у меня задумывается что будет создано 7 объектов, а создаётся 28. Это память + излишняя работа конструкторов копирования. Пусть это не называется утечкой памяти, но и частностью я бы это не назвал. Серьёзная вообще-то утечка памяти штука. И это далеко не по боку, с этим нужно бороться.

Код: Выделить всё

/*foo.cpp*/
#include <string>
#include <vector>
#include <iostream>
using namespace std;

struct uzel
{
	string date;
	vector <uzel> vuzel;
	uzel () {cout << "конструктор" << endl;};
	uzel (uzel const& src) {date =  src.date; vuzel = src.vuzel; cout << "конструктор копирования" << endl;};
	~uzel () {cout << "деструктор" << endl;};
};

int main ()
{
	struct uzel a;
	a.date = "aa";
	struct uzel b;
	b.date = "bb";
	struct uzel c;
	c.date = "cc";
	struct uzel d;
	d.date = "dd";
	struct uzel e;
	e.date = "ee";
	struct uzel f;
	f.date = "ff";
	struct uzel g;
	g.date = "gg";
	

	////////////////////////////////////////////////////////////////////
	
 	f.vuzel.push_back (g);  
 	e.vuzel.push_back (f);  
 	d.vuzel.push_back (e);  
 	c.vuzel.push_back (d);  
 	b.vuzel.push_back (c);  
 	a.vuzel.push_back (b);  

	getchar ();
	
	return 0;
}
Я просто читаю маны.
Спасибо сказали:
Аватара пользователя
Bizdelnick
Модератор
Сообщения: 20971
Статус: nulla salus bello
ОС: Debian GNU/Linux

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение Bizdelnick »

жучара писал(а):
11.02.2023 17:39
это далеко не по боку, с этим нужно бороться
Я и говорю:
Bizdelnick писал:
11.02.2023 16:03
надо использовать указатели
Пишите правильно:
в консоли
вку́пе (с чем-либо)
в общем
вообще
в течение (часа)
новичок
нюанс
по умолчанию
приемлемо
проблема
пробовать
трафик
Спасибо сказали:
Акаролибр
Сообщения: 104

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение Акаролибр »

Почему сразу указатели. От задачи зависит. Если размер этого дерева ограничен сверху, то можно реализовать его при помощи массива фиксированного размера...
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение жучара »

Акаролибр писал:
12.02.2023 02:07
Почему сразу указатели. От задачи зависит. Если размер этого дерева ограничен сверху, то можно реализовать его при помощи массива фиксированного размера...
связный список, написано же. Про размер ничего не сказано. Значит, размер произвольный.
Я просто читаю маны.
Спасибо сказали:
Акаролибр
Сообщения: 104

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение Акаролибр »

жучара писал(а):
12.02.2023 11:29
Про размер ничего не сказано. Значит, размер произвольный.
Неверно. Если ничего не сказано, это значит, что у нас нет информации по этому аспекту. И надо задать уточняющий вопрос.

Многие люди совершают такую логическую ошибку. Вот достаточно полный классификатор этой и других логических ошибок: https://www.fallacyfiles.org/taxonnew.htm
Спасибо сказали:
Аватара пользователя
жучара
Сообщения: 1024
ОС: астралинукс

Re: Реализую связный список, только вместо адресов- вектора элементов. Проблема утечки памяти.

Сообщение жучара »

Акаролибр писал:
12.02.2023 11:33
жучара писал(а):
12.02.2023 11:29
Про размер ничего не сказано. Значит, размер произвольный.
Неверно. Если ничего не сказано, это значит, что у нас нет информации по этому аспекту. И надо задать уточняющий вопрос.

Многие люди совершают такую логическую ошибку. Вот достаточно полный классификатор этой и других логических ошибок: https://www.fallacyfiles.org/taxonnew.htm
если ничего не сказано, то либо у меня нет информации по данному аспекту, либо информация очевидна. Если речь идёт о связном списке, то она очевидна более чем. А так-то уточнять можно много. Всю жизнь можно уточнять. Ну вот, например: "А не из двух ли элементов дружок, состоит у тебя связный список?" Ну и так далее.

...то, что вы задали уточняющий вопрос, это хорошо, это значит вас заинтересовало. Но из сути вопроса следовало, что я дурак, а это не так. Извините.
Я просто читаю маны.
Спасибо сказали: