Распределение памяти в C ++, используя карту связанных списков

Question

Базовая структура данных, которую я использую:

map<int, Cell>  struct Cell{ char c; Cell*next; };

Фактически структура данных отображает int в связанный список.Карта (в данном случае реализованная в виде хэш-карты) гарантирует, что поиск значения в списке выполняется за постоянное время.Связанный список гарантирует, что вставка и удаление также выполняются в постоянное время.На каждой итерации обработки я делаю что-то вроде:

 Cell *cellPointer1 = new Cell;

// Обработка ячеек, построение связанного списка

Как только список построен, я помещаю элементы Cell в карту.Структура работала очень хорошо, и после моей программы я освобождаю память.Для каждой ячейки в списке.

delete cellPointer1

Но в конце моей программы у меня утечка памяти !!Чтобы проверить утечку памяти, я использую:

#include <stdlib.h>
#include <crtdbg.h> 
#define _CRTDBG_MAP_ALLOC

_CrtDumpMemoryLeaks();

Я думаю, что где-то по пути факт размещения ячеек на карте не позволяет мне правильно освободить память.У кого-нибудь есть идеи как решить эту проблему?

Answer 1

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

Стоит отметить, что это сильно отличается от простого использования std::unordered_map напрямую.Для начала он сохраняет исходный порядок, в котором вставляются элементы.Вставка, удаление и поиск гарантированно происходят в логарифмическом времени (или постоянном времени, в зависимости от того, включен ли поиск ключа и используется ли хеш-таблица или BST), итераторы не становятся недействительными при вставке / удалении (основное требование, которое мне было нужночто заставило меня отдать предпочтение std :: map вместо std :: unordered_map) и т. д.

То, как я это сделал, выглядело так:

// I use this as the iterator for my container with
// the list being the main 'focal point' while I
// treat the map as a secondary structure to accelerate
// key searches.
typedef typename std::list<Value>::iterator iterator;

// Values are stored in the list.
std::list<Value> data;

// Keys and iterators into the list are stored in a map.
std::map<Key, iterator> accelerator;

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

Если вы хотите улучшитьвсе методы с постоянным временем, тогда вы можете использовать std :: unordered_map вместо std :: map, как я делал здесь (хотя это сопровождается некоторыми оговорками).

Использование такого подхода должно значительно упростить ситуациюнавязчивое решение на основе списков, где вам нужно вручную освободить память.

Answer 2

Нам нужно будет увидеть ваш код для вставки и удаления, чтобы быть уверенным в этом.

То, что я увидел бы как код для вставки / удаления без учета утечек, будет: (ПРИМЕЧАНИЕ: япри условии, что вы не сохраняете ячейки, которые вы размещаете на карте)

//
// insert
//
std::map<int, Cell> _map;
Cell a; // no new here!

Cell *iter = &a;
while( condition ) 
{
   Cell *b = new Cell();
   iter->next = b;
   iter = b;
}
_map[id] = a; // will 'copy' a into the container slot of the map

//
// cleanup:
//
std::map<int,Cell>::iterator i = _map.begin();
while( i != _map.end() )
{
  Cell &a = i->second;

  Cell *iter = a.next; // list of cells associated to 'a'.
  while( iter != NULL )
  {
     Cell *to_delete = iter;
     iter = iter->next;
     delete to_delete;
  }
  _map.erase(i); // will remove the Cell from the map. No need to 'delete'
  i++;
}

Редактировать : был комментарий, указывающий, что я, возможно, не полностью понял проблему.Если вы вставите ВСЕ ячейки, которые вы выделяете на карте, то ошибочным будет то, что ваша карта содержит Cell, а не Cell*.

Если вы определите свою карту как: std::map<int, Cell *>, ваша проблема будет решена в 2 условиях:

1. вы вставите все ячейки, которые вы выделите вкарта
2. целое число (ключ), связанное с каждой ячейкой: уникальное (важно !!)

Теперь удаление - это просто вопрос:

std::map<int, Cell*>::iterator i = _map.begin();
while( i != _map.end() )
{
   Cell *c = i->second;
   if ( c != NULL ) delete c;
}
_map.clear();

Answer 3

Вы должны быть очень осторожны с тем, что делаете, потому что значения в карте C ++ должны быть копируемыми, а ваша структура с необработанными указателями должна правильно обрабатывать семантику копирования.

Вы былучше использовать std :: list, где вам не нужно беспокоиться о семантике копирования.

Если вы не можете это изменить, то по крайней мере std::map<int, Cell*> будет немного более управляемым, хотя вывам придется управлять указателями на вашей карте, потому что std :: map не будет управлять ими для вас.

Вы, конечно, можете использовать std::map<int, shared_ptr<Cell> >, вероятно, самый простой для вас сейчас.

Есливы также используете shared_ptr в самом объекте Cell, вам нужно остерегаться циклических ссылок, и, поскольку Cell будет знать, что это shared_ptr, вы можете извлечь его из enable_shared_from_this

Мой последний пункт будет в этом спискеочень редко правильный тип коллекции для использования.Это правильный вариант для использования иногда, особенно когда у вас есть ситуация с кэшем LRU, и вы хотите быстро переместить доступные элементы в конец списка.Однако это дело меньшинства, и оно, вероятно, здесь не применимо.Подумайте об альтернативной коллекции, которую вы действительно хотите.map< int, set<char> > возможно?или map< int, vector< char > >?

В вашем списке много накладных расходов для хранения нескольких символов

Answer 4

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

Кто-то должен упомянуть, однако, что вы не помогаете себе, накладывая здесь два типа контейнеров.Если вы используете hash_map, у вас уже есть постоянное время вставки и удаления, см. Связанный Hash: Как это работает внутри? post.Единственное исключение из времени поиска O (c) - это если ваша реализация решает изменить размер контейнера, и в этом случае вы добавили накладные расходы независимо от добавления в связанный список.Наличие двух схем адресации только приведет к замедлению работы (не говоря уже о баггировании).

Извините, если это не указывает на утечку памяти, но я уверен, что много утечек / ошибок памяти происходитот неиспользования контейнеров stl / boost до их полного потенциала.Сначала посмотри на это.

Answer 5

Вы можете сделать это, используя STL (удалить next из ячейки):

std::unordered_map<int,std::list<Cell>>

Или, если ячейка содержит только char

std::unordered_map<int,std::string>

Если ваш компилятор нене поддерживает std::unordered_map, попробуйте boost::unordered_map.

Если вы действительно хотите использовать навязчивые структуры данных, взгляните на Boost Intrusive .

Answer 6

Есть ли причина, по которой вы не используете встроенные контейнеры, например, STL?

Во всяком случае, вы не показываете код, где происходит распределение, ни определение карты (это из библиотеки?).

Вы уверены, что освободили все ранее выделенные Cell с, начиная с последнего и возвращаясь к первому?