Memory Allocation in C++, Using a Map of Linked Lists

Question

The underlying data structure I am using is:

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

In effect the data structure maps an int to a linked list. The map(in this case implemented as a hashmap) ensures that finding a value in the list runs in constant time. The Linked List ensures that insertion and deletion also run in constant time. At each processing iteration I am doing something like:

 Cell *cellPointer1 = new Cell;

//Process cells, build linked list

Once the list is built I put the elements Cell in map. The structure was working just fine and after my program I deallocate memory. For each Cell in the list.

delete cellPointer1

But at the end of my program I have a memory leak!! To test memory leak I use:

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

_CrtDumpMemoryLeaks();

I'm thinking that somewhere along the way the fact that I am putting the Cells in the map does not allow me to deallocate the memory correctly. Does anyone have any ideas on how to solve this problem?

Answer 1

You need to be very careful with what you are doing, because values in a C++ map need to be copyable and with your structure that has raw pointers, you must handle your copy semantics properly.

You would be far better off using std::list where you won't need to worry about your copy semantics.

If you can't change that then at least std::map<int, Cell*> will be a bit more manageable, although you would have to manage the pointers in your map because std::map will not manage them for you.

You could of course use std::map<int, shared_ptr<Cell> >, probably easiest for you for now.

If you also use shared_ptr within your Cell object itself, you will need to beware of circular references, and as Cell will know it's being shared_ptr'd you could derive it from enable_shared_from_this

My final point will be that list is very rarely the correct collection type to use. It is the correct one to use sometimes, especially when you have an LRU cache situation and you want to move accessed elements to the end of the list fast. However that is the minority case and it probably doesn't apply here. Think of an alternative collection you really want. map< int, set<char> > perhaps? or map< int, vector< char > > ?

Your list has a lot of overheads to store a few chars

Answer 2

I've built almost the exact same hybrid data structure you are after (list/map with the same algorithmic complexity if I were to use unordered_map instead) and have been using it from time to time for almost a decade though it's a kind of bulky structure (something I'd use with convenience in mind more than efficiency).

It's worth noting that this is quite different from just using std::unordered_map directly. For a start, it preserves the original order in which one inserts elements. Insertion, removal, and searches are guaranteed to happen in logarithmic time (or constant time depending on whether key searching is involved and whether you use a hash table or BST), iterators do not get invalidated on insertion/removal (the main requirement I needed which made me favor std::map over std::unordered_map), etc.

The way I did it was like this:

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

If you do it like this, it becomes quite easy. push_back is a matter of pushing back to the list and adding the last iterator to the map, iterator removal is a matter of removing the key pointed to by the iterator from the map before removing the element from the list as the list iterator, finding a key is a matter of searching the map and returning the associated value in the map which happens to be the list iterator, key removal is just finding a key and then doing iterator removal, etc.

If you want to improve all methods to constant time, then you can use std::unordered_map instead of std::map as I did here (though that comes with some caveats).

Taking an approach like this should simplify things considerably over an intrusive list-based solution where you're manually having to free memory.

Answer 3

As others have pointed out, it may be hard to see what you're doing wrong without seeing your code.

Someone should mention, however, that you're not helping yourself by overlaying two container types here. If you're using a hash_map, you already have constant insertion and deletion time, see the related Hash : How does it work internally? post. The only exception to the O(c) lookup time is if your implementation decides to resize the container, in which case you have added overhead regardless of your linked list addition. Having two addressing schemes is only going to make things slower (not to mention buggier).

Sorry if this doesn't point you to the memory leak, but I'm sure a lot of memory leaks / bugs come from not using stl / boost containers to their full potential. Look into that first.

Answer 4

We'll need to see your code for insertion and deletion to be sure about it.

What I'd see as a memleak-free insert / remove code would be: ( NOTE: I'm assuming you don't store the Cells that you allocate in the 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++;
}

Edit: there was a comment indicating that I might not have understood the problem completely. If you insert ALL the cells you allocate in the map, then the faulty thing is that your map contains Cell, not Cell*.

If you define your map as: std::map<int, Cell *>, your problem would be solved at 2 conditions:

1. you insert all the Cells that you allocate in the map
2. the integer (the key) associated to each cell is unique (important!!)

Now the deletion is simply a matter of:

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

Answer 5

You could do this using the STL (remove next from Cell):

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

Or if cell only contains a char

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

If your compiler doesn't support std::unordered_map then try boost::unordered_map.

If you really want to use intrusive data structures, have a look at Boost Intrusive.

Answer 6

Is there a reason why you are not using built-in containers like, say, STL?

Anyhow, you don't show the code where the allocation takes place, nor the map definition (is this coming from a library?).

Are you sure you deallocate all of the previously allocated Cells, starting from the last one and going backwards up to the first?