title: Memory Allocation in C++, Using a Map of Linked Lists
body: <p>The underlying data structure I am using is:</p>
  
  <pre><code>map&lt;int, Cell&gt;  struct Cell{ char c; Cell*next; };
  </code></pre>
  
  <p>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:</p>
  
  <pre><code> Cell *cellPointer1 = new Cell;
  </code></pre>
  
  <p>//Process cells, build linked list</p>
  
  <p>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.</p>
  
  <pre><code>delete cellPointer1
  </code></pre>
  
  <p>But at the end of my program I have a memory leak!! 
  To test memory leak I use:</p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;crtdbg.h&gt; 
  #define _CRTDBG_MAP_ALLOC
  
  _CrtDumpMemoryLeaks();
  </code></pre>
  
  <p>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?</p>