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

[жучара]

Друзья! Вот схематично изображён связный список в виде цепочки:
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]

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

[жучара]

Ужасно. Начать с того, что после этого кода
a.vuzel.push_back (b);
Уже будет один лишний объект b. А у меня таких лишних объектов будет ОЧЕНЬ много. То есть уже тут неправильно, тут утечка.

[Bizdelnick]

То есть уже тут неправильно, тут утечка.

Если b на стеке, как в этом примере, то утечки не будет. Но вообще, конечно, тут надо использовать указатели и писать деструктор для их освобождения.

[жучара]

То есть уже тут неправильно, тут утечка.

Если 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]

То есть один лишний объект b существовал до самого конца программы.

Он существовал до выхода из функции main(). То, что оно в данном случае совпадает с концом программы, — частности.
Об утечках имеет смысл говорить только при выделении памяти в куче, стековые переменные побоку.

[жучара]

То есть один лишний объект b существовал до самого конца программы.

Он существовал до выхода из функции main(). То, что оно в данном случае совпадает с концом программы, — частности.
Об утечках имеет смысл говорить только при выделении памяти в куче, стековые переменные побоку.

ничё не понимаю. Я кладу объект в вектор и начинаю с ним, который в векторе, работать. Тот который не в векторе он лишний и хорошо бы его сразу же удалить, как только я положу его (а точнее, его копию в вектор). Но это, оказывается, частности. А слово "частности" в данном случае обозначает что? Ну то есть это всё фигня и ерунда, смею предположить?

[Bizdelnick]

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

Частности не это, а то, что Вы всё проделываете в функции main. Проделывали бы в другой — объекты жили бы только до её завершения. Вот если бы Вы выделили память в куче, не освободили её из той же функции и не вернули указатель, по которому её можно было бы освободить потом, — это была бы утечка.

[жучара]

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

Частности не это, а то, что Вы всё проделываете в функции 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]

это далеко не по боку, с этим нужно бороться

Я и говорю:

надо использовать указатели

[Акаролибр]

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

[жучара]

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

связный список, написано же. Про размер ничего не сказано. Значит, размер произвольный.

[Акаролибр]

Про размер ничего не сказано. Значит, размер произвольный.

Неверно. Если ничего не сказано, это значит, что у нас нет информации по этому аспекту. И надо задать уточняющий вопрос.

Многие люди совершают такую логическую ошибку. Вот достаточно полный классификатор этой и других логических ошибок: https://www.fallacyfiles.org/taxonnew.htm

[жучара]

Про размер ничего не сказано. Значит, размер произвольный.

Неверно. Если ничего не сказано, это значит, что у нас нет информации по этому аспекту. И надо задать уточняющий вопрос.

Многие люди совершают такую логическую ошибку. Вот достаточно полный классификатор этой и других логических ошибок: https://www.fallacyfiles.org/taxonnew.htm

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

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