title: Validity of std::map::iterator after erasing elements
body: <p>I have written a code for solving the following problem: We have a <code>map&lt;double,double&gt;</code> with (relatively) huge number of items. We want to merge the adjacent items in order to reduce the size of the map keeping a certain "loss factor" as low as possible.</p>
  
  <p>To do so, I first populate a list containing adjacent iterators and the associated loss factor (let's say each list element has the following type:</p>
  
  <pre><code>struct myPair {
      map&lt;double,double&gt;::iterator curr, next;
      double loss;
      myPair(map&lt;double,double&gt;::iterator c, map&lt;double,double&gt;::iterator n, 
          double l):  curr(c), next(n), loss(l) {}
  };
  </code></pre>
  
  <p>).  This is done as follows:</p>
  
  <pre><code>for (map&lt;double,double&gt;::iterator it1 = myMap.begin(); it1 != --(myMap.end()); 
      it1++) {
      map&lt;double,double&gt;::iterator it2 = it1; it2++;
      double l = computeLoss(it1,it2); 
      List.push(myPair(it1,it2,l));
  }
  </code></pre>
  
  <p>Then, I find the list element corresponding to the lowest loss factor, <code>erase</code> the corresponding elements from the <code>map</code> and <code>insert</code> a new element (result of merging <code>curr</code> and <code>next</code>) in the <code>map</code>. Since this also changes the list elements corresponding to the element after <code>next</code> or before <code>curr</code> I update the corresponding entries and also the associated loss factor.</p>
  
  <p>(I don't get into the details of how to implement the above efficiently but basically I am combining a double linked list and a heap).</p>
  
  <p>While the <code>erase</code> operations should not invalidate the remaining iterators for some specific input instances of the program I get the <code>double free or corruption</code> error exactly at the point where I attempt to erase the elements from the <code>map</code>.</p>
  
  <p>I tried to track this and it seems this happens when both <code>first</code> and <code>second</code> entries of the two map elements are very close (more precisely when the <code>first</code>s of <code>curr</code> and <code>next</code> are very close). </p>
  
  <p>A strange thing is that I put an <code>assert</code> while populating the list to ensure that in all entries <code>curr</code> and <code>next</code> are different and the same <code>assert</code> in the loop of removing elements. The second one fails!</p>
  
  <p>I would appreciate if anyone can help me.</p>
  
  <p>P.S. I am sorry for not being very precise but I wanted to keep the details as low as possible.</p>
  
  <p>UPDATE: This is (a very simplified version of) how I erase the elements from the map:</p>
  
  <pre><code>while (myMap.size() &gt; MAX_SIZE) {
      t = list.getMin();
      /* compute the merged version ... let's call the result as (a,b) */
      myMap.erase(t.curr);
      myMap.erase(t.next);
      myMap.insert(pair&lt;double,double&gt;(a,b));
  
      /* update the adjacent entries */
  }
  </code></pre>