0

I have written a code for solving the following problem: We have a map<double,double> 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.

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:

struct myPair {
    map<double,double>::iterator curr, next;
    double loss;
    myPair(map<double,double>::iterator c, map<double,double>::iterator n, 
        double l):  curr(c), next(n), loss(l) {}
};

). This is done as follows:

for (map<double,double>::iterator it1 = myMap.begin(); it1 != --(myMap.end()); 
    it1++) {
    map<double,double>::iterator it2 = it1; it2++;
    double l = computeLoss(it1,it2); 
    List.push(myPair(it1,it2,l));
}

Then, I find the list element corresponding to the lowest loss factor, erase the corresponding elements from the map and insert a new element (result of merging curr and next) in the map. Since this also changes the list elements corresponding to the element after next or before curr I update the corresponding entries and also the associated loss factor.

(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).

While the erase operations should not invalidate the remaining iterators for some specific input instances of the program I get the double free or corruption error exactly at the point where I attempt to erase the elements from the map.

I tried to track this and it seems this happens when both first and second entries of the two map elements are very close (more precisely when the firsts of curr and next are very close).

A strange thing is that I put an assert while populating the list to ensure that in all entries curr and next are different and the same assert in the loop of removing elements. The second one fails!

I would appreciate if anyone can help me.

P.S. I am sorry for not being very precise but I wanted to keep the details as low as possible.

UPDATE: This is (a very simplified version of) how I erase the elements from the map:

while (myMap.size() > 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<double,double>(a,b));

    /* update the adjacent entries */
}
Deduplicator
  • 44,692
  • 7
  • 66
  • 118
MikeL
  • 2,369
  • 2
  • 24
  • 38
  • Please show the code where you erase the elements. – flyx Sep 09 '13 at 13:00
  • I will add the code right now. – MikeL Sep 09 '13 at 13:02
  • By the way, in the shown example, `a >= t.curr->first` and `a <= t.next->first`, hence the new element would be replaced at the same place than the two erased elements. – MikeL Sep 09 '13 at 13:09
  • It looks like you want something similar to a heap or tree instead of a list, so that you don't have to search for the smallest loss factor. In this case, the update of costs ln(N). – Walter Sep 09 '13 at 13:13
  • Thanks @Walter. Yes, as I mentioned, indeed the `list` I am talking of is a combination of a heap and a doubly linked list so that updates are logarithmic. – MikeL Sep 09 '13 at 13:15
  • what's your "comparer" function, since using a double as a key will probably lead to not expected behaviours. – João Augusto Sep 09 '13 at 13:21
  • I am not using a specific compare function. Is the built-in `<` associated with doubles problematic? – MikeL Sep 09 '13 at 13:24
  • Check this answer http://stackoverflow.com/questions/6684573/floating-point-keys-in-stdmap – João Augusto Sep 09 '13 at 13:24
  • 2
    Side note: using a `double` as a map key may produce rather surprising results. If you obtain the key values by a computation, you may get distnict keys where you'd expect indetity, simply due to precision errors. – Angew is no longer proud of SO Sep 09 '13 at 13:46
  • Well, now I see where the problem is coming from: I first have to mention that the merging operation is a linear interpolation: `a = (curr->first * curr->second + next->first * next-second) / (curr->second + next->second);` and `b = curr->second + next->second`. Now, if `curr` and `next` are close in key, `a` would also be close to that key. Theoretically its value should be bigger than `curr->first` and insertion should create a new element. In practice, however, the insertion replaces the next or previous items which causes problems in the next stages. – MikeL Sep 09 '13 at 14:16

2 Answers2

0

Stored iterators in myPair stay invalid after container modification. You should avoid such technique. Probably when you look into header file you will find some ready drafts for your task?

vasylz
  • 177
  • 1
  • 4
  • 1
    Are you sure? Because for example in http://www.cplusplus.com/reference/map/map/erase/ it has been mentioned that the erased iterators are invalidated but the rest of iterators remain valid (in the above code, `t` is removed from the `list`). – MikeL Sep 10 '13 at 07:17
  • Yes, you are correct. Map iterators stay valid after container modification. But what happen when after erase myMap.erase(t.next) in our next iteration we do myMap.erase(t.curr) is it possible when t.next for first iteration is equal to t.curr in the next iteration? – vasylz Sep 10 '13 at 12:12
  • You are absolutely right. I have omitted a large part of the code to avoid complications. But in reality the iterators stored in `list` are updated after the `erase` operations. In particular, the `next` element of the entry which were pointing to `t.curr` (and is invalid now) will be replaced by the new inserted element (`map::insert` would return an iterator pointing to that). Likewise the `curr` element of the entry which were pointing to `t.next` will be replaced by the iterator pointing to the newly inserted element. – MikeL Sep 10 '13 at 15:46
0

As mentioned already by the other people, it turns out that using double as the key of the map is problematic. In particular when the values are computed.

Hence, my solution was to use std::multimap instead of map (and then merge the elements with the same key just after populating the map). With this, for example even if a is very close to both keys of t.curr and t.next or any other element, for sure the insert operation creates a new element such that no existing iterator in the list would point to that.

MikeL
  • 2,369
  • 2
  • 24
  • 38