c++ - C++ 中的内存分配，使用链表映射

Question

我使用的底层数据结构是:

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

实际上，数据结构将 int 映射到链表。 map (在本例中实现为 HashMap )确保在列表中查找值在恒定时间内运行。链表确保插入和删除也在恒定时间内运行。在每次处理迭代中，我都在做类似的事情:

 Cell *cellPointer1 = new Cell;

//处理单元格，构建链表

构建列表后，我将元素 Cell 放入 map 中。该结构工作得很好，在我的程序之后我释放了内存。对于列表中的每个单元格。

delete cellPointer1

但是在我的程序结束时我有内存泄漏!! 为了测试内存泄漏，我使用:

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

_CrtDumpMemoryLeaks();

我在想，我将 Cells 放入 map 中这一事实不允许我正确地释放内存。有没有人对如何解决这个问题有任何想法？

Answer 1

我们需要查看您的插入和删除代码才能确定。

我认为无内存泄漏的插入/删除代码是: (注意:我假设您不存储您在 map 中分配的单元格)

//
// 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++;
}

编辑:有一条评论表明我可能没有完全理解这个问题。如果您在 map 中插入您分配的所有单元格，那么错误的是您的 map 包含 Cell , 不是 Cell* .

如果您将 map 定义为:std::map<int, Cell *> ，您的问题将在 2 个条件下得到解决:

1. 您插入所有您在 map 中分配的单元格
2. 与每个单元格关联的整数(键)是唯一(重要!!)

现在删除只是一个问题:

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