Форум программистов, компьютерный форум CyberForum.ru

Освобождение памяти от циклического списка - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
08.12.2011, 00:19     Освобождение памяти от циклического списка #1
Каким образом организовать освобождение памяти, если выделяется память для каждого элемента цикл. списка внутри функции, а наружу передается только ее указатель?
C++
1
2
3
4
5
6
7
8
int* func()
{
int* p;
 
// создание циклического списка
 
return p;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2011, 00:19     Освобождение памяти от циклического списка
Посмотрите здесь:

освобождение памяти от элементов списка C++
C++ Освобождение памяти
Освобождение памяти C++
C++ Освобождение памяти в C++
Создание односвязного циклического списка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
08.12.2011, 00:21  [ТС]     Освобождение памяти от циклического списка #2
указатель p - указывает на этот циклический список
boombastik
6 / 6 / 0
Регистрация: 13.02.2007
Сообщений: 1,255
08.12.2011, 03:01     Освобождение памяти от циклического списка #3
Что такое циклический список? связанный список? если да, то как он организован? как происходит выделение памяти?

Обычно освобождение выполняется оператором:
Код
delete p;   // освободится память выделенная для 1 переменной int размером sizeof(int)
delete[] p; // освободится память выделенная для массива, размер зависит от размера массива
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
08.12.2011, 12:48  [ТС]     Освобождение памяти от циклического списка #4
ситуация немного сложнее:

есть некий класс:
C++
1
2
3
4
5
6
7
8
9
10
11
class Item 
{ 
// Переменные
    CItem* p_parentItem;
    CString m_Name;
    CString m_Family;
// Методы
    CItem(void);
    CItem(CString);
    ~CItem(void);
}
есть некий тип данных:
C++
1
typedef std::vector<Item> ItemVector;
есть некий вектор - член класса CTreeDlg:
C++
1
ItemVector v1;
есть некая функция по заполнению этого вектора:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool CTreeDlg::CreateList(CString FilePath, CString FileName)
{
    // формирование родителя
    CItem daddy(FileName);
    //CItem daddy = new CItem(FileName);
 
    v1.push_back(daddy);
 
    FILE *stream;   
    
    CItem current;
    CItem* previous;
    char str_from_file[MAX_PATH];
 
    current.p_parentItem = &daddy;
 
    if( FilePath < "  " ) { 
        return FALSE; // слищком короткая строка, содержащая путь к файлу
    }
    else {       
        stream = fopen(FilePath, "a+"); 
        while( !feof( stream ) ) 
        {   
            fgets(str_from_file, MAX_PATH, stream);
 
            current.m_Name = str_from_file;
            // здесь разбить на лексеммы 
            current.m_Name.OemToAnsi();
            int second_word = current.m_Name.Find('' '', 0);
            current.m_Family = current.m_Name.Mid(second_word + 1, current.m_Name.GetLength());
            current.m_Name = current.m_Name.Left(second_word);
            
            // здесь код формирования списка
            v1.push_back(current);
            previous = &current;
        }
        fclose(stream);
        return TRUE;    // всё тру
    }
}
вопрос: есть ли в вышеприведенном коде утечка памяти?
Если я правильно понимаю, вектор в данном случае - типа контейнера,
в котором находятся связанные между собой экземпляры класса Item?
заранее спасибо
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
08.12.2011, 13:05  [ТС]     Освобождение памяти от циклического списка #5
СОРРИ! Предыдущий пост неправильный, старый код туда засунул Вот правильно:
ситуация немного сложнее:

есть некий класс:
C++
1
2
3
4
5
6
7
8
9
10
11
class Item 
{ 
// Переменные
       CItem* p_parentItem;
       CString m_Name;
       CString m_Family;
// Методы
       CItem(void);
       CItem(CString);
       ~CItem(void);
}
есть некий тип данных:
C++
1
typedef std::vector<Item> ItemVector;
есть некий вектор - член класса CTreeDlg:
C++
1
ItemVector v1;
есть некая функция по заполнению этого вектора:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool CTreeDlg::CreateList(CString FilePath, CString FileName)
{
       // формирование родителя
       CItem daddy(FileName);
       //CItem daddy = new CItem(FileName);
 
       v1.push_back(daddy);
 
       FILE *stream;       
       
       CItem current;
       CItem* previous;
       char str_from_file[MAX_PATH];
 
       current.p_parentItem = &daddy;
 
       if( FilePath < " " ) { 
              return FALSE; // слищком короткая строка, содержащая путь к файлу
       }
       else {               
              stream = fopen(FilePath, "a+");       
              while( !feof( stream ) ) 
              {       
                     fgets(str_from_file, MAX_PATH, stream);
 
                     current.m_Name = str_from_file;
                     // здесь разбить на лексеммы 
                     current.m_Name.OemToAnsi();
                     int second_word = current.m_Name.Find('''' '''', 0);
                     current.m_Family = current.m_Name.Mid(second_word + 1, current.m_Name.GetLength());
                     current.m_Name = current.m_Name.Left(second_word);
                     
                     // здесь код формирования списка
                     v1.push_back(current);
                     previous = ¤t;
              }
              fclose(stream);
              return TRUE;       // всё тру
       }
}
содержимое файла FilePath:
Код
Василий Иванов
Петр Петров
Алексей Сидоров
Апрель Май
вопрос: есть ли в вышеприведенном коде утечка памяти?
Если я правильно понимаю, вектор в данном случае - типа контейнера,
в котором находятся связанные между собой экземпляры класса Item?
заранее спасибо
bazile
55 / 31 / 17
Регистрация: 15.03.2007
Сообщений: 6,912
08.12.2011, 16:01     Освобождение памяти от циклического списка #6
Класс vector<> по своей сути это массив, а не список (имеется в виду не внутрення реализация, а назначение класса). Связывание элементов между собой ты делаешь самостоятельно с помощью поля p_parentItem.

Утечек памяти здесь не видно т.к. непонятно как ты используешь этот vector<CItem> дальше и как очищаешь его. Проблема, как мне кажется, в другом. Ты неправильно используешь класс vector. В vector добавляется [italic]копия[/italic] элемента. В твоем примере это приводит к тому что в поле p_parentItem остается указатель на локальную переменную daddy, которая будет уничтожена сразу после завершения CreateList. Возможно имеет смысл ссылаться на родителя по индексу элемента в vector.

Кроме того код похоже нерабочий, в том смысле что класс у тебя называется то Item, то CItem; переменная previous используется только для присвоения и непонятно зачем она вообще.
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
08.12.2011, 16:51  [ТС]     Освобождение памяти от циклического списка #7
Цитата Сообщение от bazile
Возможно имеет смысл ссылаться на родителя по индексу элемента в vector.
Спасибо, может быть так и сделаю
boombastik
6 / 6 / 0
Регистрация: 13.02.2007
Сообщений: 1,255
09.12.2011, 01:41     Освобождение памяти от циклического списка #8
petrovich1, несколько размышлений по дизайну твоего приложения:

* у тебя уже есть динамический контейнер: vector, если твоя задача - затолкать в контейнер все строки из файла в виде экземпляров класса Item, то зачем тебе организовывать список? просто забивай в вектор и все, элементы в векторе будут располагаться в том порядке в каком ты их туда затолкал если использовался метод push_back.

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

* если у тебя задание организовать свой собственный лист, то ты делай это полностью самостоятельно, твой класс Item уже имеет все необходимое для организации простого одно-направленного листа (точнее стека, потому как элементы ссылаются на родителя, то есть предыдущий элемент). На вскидку класс списка выглядел бы следующим образом (не компилировал, поэтому не гарантирую что будет работать сходу):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class CItem 
{
public:
    // Переменные
    CItem* p_parentItem;
    CString m_Name;
    CString m_Family;
    // Методы
    CItem(void);
    CItem(CString& name, CString& family)
    {
        m_Name = name;
        m_Family = name;
    };
    
    ~CItem(void);
} 
 
class CList
{
protected:
    CItem* m_pLast;
 
public:
    CList()
    {
        m_pLast = NULL
    };
    
    ~CItem()
    {
        // Self cleaning
        CItem* pItem = m_pLast;
        while (pItem != NULL)
        {
            CItem* pParent = pItem->p_parentItem;
            delete pItem;
            pItem = pParent;
        }
    }
    
    void Insert(CItem* pItem)
    {
        pItem->p_parentItem = m_pLast;
        m_pLast = pItem;
    }
    
    void Insert(CString& name, CString& family)
    {
        Insert(new CItem(name, family));
    }
    
    int Size()
    {
        int result = 0;
        CItem* pItem = m_pLast;
        while (pItem != NULL)
        {
            pItem = pItem->p_parentItem;
            result++;
        }
        return result;
    }
    
    CItem* GetLast()
    {
        return m_pLast;
    }
    
    CItem* GetFirst()
    {
        if (m_pLast == NULL)
        {
            return NULL;
        }
        
        CItem* pItem = m_pLast;
        while (pItem->p_parentItem != NULL)
        {
            pItem = pItem->p_parentItem;
        }
        
        return pItem;
    }
    
    CItem* FindByName(CString& name)
    {
        CItem* pItem = m_pLast;
        
        while (pItem != NULL)
        {
            if (pItem->m_Name == name)
            {
                return pItem;
            }
            pItem = pItem->p_parentItem;
        }
        
        return NULL;
    }
    
    // And so so on
}
С уважением,
Владимир
boombastik
6 / 6 / 0
Регистрация: 13.02.2007
Сообщений: 1,255
09.12.2011, 01:45     Освобождение памяти от циклического списка #9
P.S. для простоты все оформил в виде online-функций, вместо того чтобы приводить содержимое *.h и *.cpp файлов, да и привычки из Java дают о себе знать, под "листом" конечно же подразумевал "список"
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
09.12.2011, 11:09  [ТС]     Освобождение памяти от циклического списка #10
Цитата Сообщение от boombastik
у тебя уже есть динамический контейнер: vector, если твоя задача - затолкать в контейнер все строки из файла в виде экземпляров класса Item, то зачем тебе организовывать список? просто забивай в вектор и все, элементы в векторе будут располагаться в том порядке в каком ты их туда затолкал если использовался метод push_back.
Я уже это понял и пришел к этому, внял совету bazile("Возможно имеет смысл ссылаться на родителя по индексу элемента в vector") и теперь функция формирования вектора выглядит так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
bool CTreeDlg::CreateList(CString FilePath)
{
    FILE *stream;   
    
    CItem tmp;
 
    char str_from_file[MAX_PATH];
 
    int i = 0;
    int parents_any_tabs[10];
 
    for(i = 0; i < 10; i++) 
        parents_any_tabs[i] = -1;
 
    i = 0;
 
    stream = fopen(FilePath, "a+"); 
    while( !feof( stream ) ) 
    {   
/*
    Иерархия в текстовом файле задается с помощью табуляции
    например, в следующем примере "Иванов" и "Петров" имеют
    родительский узел "Сотрудники", а "WinХР" имеет родительский 
    узел "Иванов"
 
    Пример: //////////////////
    Сотрудники
            Иванов
                WinХР
            Петров
    //////////////////////////
 
*/
        // здесь код формирования вектора           
        fgets(str_from_file, MAX_PATH, stream);
 
        tmp.m_Data = str_from_file;
        tmp.m_Data.OemToAnsi();
 
        // Здесь ведется подсчет табуляций для определения иерархии
        CString tabs = tmp.m_Data.SpanIncluding("   ");
 
        tmp.m_Data.TrimLeft();
        tmp.m_Data.TrimRight();
 
        // В качестве ссылки на родителя используется порядковый номер элента родителя в массиве.
        // Здесь указывается порядковый номер родителя для текущего элемента вектора.
        if (tabs.GetLength() != 0)
            tmp.Parent = parents_any_tabs[tabs.GetLength() - 1];
        else
            tmp.Parent = -1;
 
        parents_any_tabs[tabs.GetLength()] = i;
 
        mas[i] = tmp;
        v1.push_back(tmp);
        i++;
    }
    fclose(stream);
    return TRUE;    // всё тру
}
По заданию нужно из текстового файла или из sql-базы сформировать такой вектор, а потом на его основе проинициализировать TreeView. Идея с простой адресацией на родителя по его порядковому номеру вначале показалась мне удачной, но потом во время инициализации дерева пришлось "расшифровывать" иерархию. В задании надо реализовать drag&drop для этого дерева.
Какой подход посоветуете?
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
09.12.2011, 11:14  [ТС]     Освобождение памяти от циклического списка #11
З.Ы.
Имеется три различных подхода:
1) адресация на родителя по порядковому номеру в векторе
2) stl list
3) собственная реализация класса списка

boombastik
6 / 6 / 0
Регистрация: 13.02.2007
Сообщений: 1,255
09.12.2011, 13:24     Освобождение памяти от циклического списка #12
Есть еще вот такая вещь (и похожие): http://www.aei.mpg.de/~peekas/tree/. Если работаешь с деревом (TreeView), то и оформлять структуру в памяти лучше в виде дерева.

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

С уважением,
Владимир
boombastik
6 / 6 / 0
Регистрация: 13.02.2007
Сообщений: 1,255
09.12.2011, 13:27     Освобождение памяти от циклического списка #13
А во, точно ведь знал, что на codeproject тоже было: http://www.codeproject.com/vcpp/stl/wrk.asp

Вот еще одно: http://stlplus.sourceforge.net/stlplus/docs/ntree.html
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
10.12.2011, 19:31  [ТС]     Освобождение памяти от циклического списка #14
Первое сложновато.
Второе показалось наиболее доступным, наверное его попытаюсь прикрутить.
Третье тоже занятно, но... я понимаю, что плохо быть чайником, но объясните
плиз, что это такое, я такого никогда в жизни не видел. Это под UNIX???
C++
1
2
3
4
5
#include "os_fixes.hpp"
#include "textio.hpp"
#include "persistent.hpp"
#include "exceptions.hpp"
#include <stdexcept>
boombastik
6 / 6 / 0
Регистрация: 13.02.2007
Сообщений: 1,255
10.12.2011, 20:56     Освобождение памяти от циклического списка #15
Н-да... я особо не разбирался ни с одной из них, просто навскидку нашел при помощи google. Когда-то давно использовал похожую вещь (STL like tree) в своем проекте, поэтому знал о существовании реализаций. Про последнюю ссылку, судя по тому что указано на их сайте http://stlplus.sourceforge.net/:
Цитата Сообщение от The STL+ C++ library
The collection is general-purpose and portable between Windows and Unix platforms.
то это не только для UNIX, а те include-файлы видимо ссылаются на др. части этой библиотеки.

С другой стороны, не стоит заморачиваться, просто воспользуйся наиболее удобной для тебя реализацией дерева. Судя по всему свой выбор ты уже сделал.

С уважением,
Владимир.
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
11.12.2011, 10:51  [ТС]     Освобождение памяти от циклического списка #16
Спасибо большое!
petrovich1
0 / 0 / 0
Регистрация: 22.09.2007
Сообщений: 314
06.01.2012, 17:06  [ТС]     Освобождение памяти от циклического списка #17
Цитата Сообщение от boombastik
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class CList
{
protected:
    CItem* m_pLast;
 
public:
    *
    *
    *
    CItem* GetLast()
    {
        return m_pLast;
    }
    *
    *
    *   // And so so on
}
С уважением,
Владимир
пытаюсь реализовать этот механизм следущим образом:
C++
1
2
3
4
void MyClass::Func(CList *list)
{
    CItem *item = list->GetRootItem;
}
он мне пишет:
error C2440: ''type cast'' : cannot convert from ''CItem *(__thiscall CItemTree::* )(void)'' to ''CItem *''
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2012, 01:57     Освобождение памяти от циклического списка
Еще ссылки по теме:

C++ Освобождение памяти
C++ Удаление из двусвязного циклического списка
Корректное освобождение памяти из-под списка C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
boombastik
6 / 6 / 0
Регистрация: 13.02.2007
Сообщений: 1,255
07.01.2012, 01:57     Освобождение памяти от циклического списка #18
Посмотри описание ошибки http://msdn.microsoft.com/library/en...html/C2440.asp

Там описан твой случай. Правда как-то мудрено.. Не уверен точно, так как нужно смотреть код, но могу попробовать дать один совет, не используй online фунции, как в примере который я тебе привел (просто так запись выглядела компактнее).

Удачи,
Владимир
Yandex
Объявления
07.01.2012, 01:57     Освобождение памяти от циклического списка
Ответ Создать тему
Опции темы

Текущее время: 04:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru