4

I am having a problem while looping thru a map (std::map).

Inside my loop, there is a call to a function which sometimes (not always) erases elements of this same map. After this function is used, there is some code which is using some of this map information as input.

I am having no problems after this function erases any elements, except on the unique case that the last element of the map is erased.

My loop semms not to understand that the last element of the map is not the same as when it started to operate, and will try to operate on elements which doesnt exist, creating a crash.

It seems to me that the myMap.end() call on the loop description is not able to update itself with the new end() of the map.

The relevant part of the code is listed below:

for(std::map<int, ConnectionInfo>::iterator kv = myMap.begin(); kv != myMap.end(); ++kv) {
        int thisConnectionID=kv->first; //This is where I get garbage when the loop enters when it shouldnt;
        ConnectionInfo currentConnectionInfo=kv->second; //This is where I get garbage when the loop enters when it shouldnt;
        status=eraseSomeMapElementsIfNecessary(thisConnectionID,currentConnectionInfo.DownPacket); //this function might erase elements on myMap. This generates no problems afterwards, except when the end element of myMap is erased
        ... //Next parts of the code make no further usage of myMaps, so I just hid it not to pollute the code
}

Is my interpretation that the kv != myMap.end() is not being able to understand that the inner loop is changing (erasing) the last element (end) of myMap?

In this case, how can I fix this issue?

Or is my interpretation wrong and the solution has nothing to do with what I stated before?

Thanks for your help!

user5193682
  • 260
  • 1
  • 11

4 Answers4

6

The usual idiom when iterating a map with possibly deleting element is:

for(auto it = map.begin(); it != map.end(); ) {
   if ( *it == /*is to delete*/ ) {
     it = map.erase(it);
   }
   else
     ++it;
}

if your eraseSomeMapElementsIfNecessary might erase some random values in map being iterated then this will for sure cause problems. If element to which it is referencing was erased, it becomes invalid, then incrementing it with ++it is also invalid.

The problem is actually only with the it iterator, if eraseSomeMapElementsIfNecessary erases it and then you use it - you have Undefined Behaviour (UB). So the solution is to pass current iterator to eraseSomeMapElementsIfNecessary, and return from it the next one to iterate:

it = eraseSomeMapElementsIfNecessary(it);

the body of the for loop from my example should be inside your eraseSomeMapElementsIfNecessary function. At least this is one solution.

marcinj
  • 48,511
  • 9
  • 79
  • 100
  • 1) How can I coordinate the eraseSomeMapElementsIfNecessary function with the loop so that this problem stops? 2) What does "UB" mean? – user5193682 Apr 22 '16 at 09:47
  • @user9589 Undefined Behaviour - it means application might crash or might work as expected, anything – marcinj Apr 22 '16 at 09:48
  • 2
    ad1) you have to put the above map with erase iterating idiom into your eraseSomeMapElementsIfNecessary function. I have given above a hint how to do it. – marcinj Apr 22 '16 at 09:50
  • I knew that the iterator erased by eraseSomeMapElementsIfNecessary would be invalid, but I thought that the next run of my loop would use the correct one (because it updates with ++it). Its really surprising for me that this is not the case and I dont quite get it. – user5193682 Apr 22 '16 at 10:01
  • 1
    @user9589 the problem is that if `it` is invalid then `++it` is also invalid. I wrote a suggestion that you could start iterating your map from begining if your function erased some elements (if it did then after its execution map size will shirnk), but this is a work around the real problem and might be inefficent. – marcinj Apr 22 '16 at 10:04
  • 1) This comment (about it being invalid makes ++it also invalid) is really inspiring! 2) I will try having forming a clearer idea of how to implement your solution properly during the day and later test it. 3) It would be nice if you put your comment (about it being invalid makes ++it also invalid) on the answer so that other people having the same cognitive difficulty also gets it – user5193682 Apr 22 '16 at 10:12
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/109893/discussion-between-user9589-and-marcin-jedrzejewski). – user5193682 Apr 22 '16 at 11:01
4

I am having no problems after this function erases any elements, except on the unique case that the last element of the map is erased.

Erasing an element in any container invalidates the iterator to it. After that you increment the invalidated iterator.

You should increment the iterator before you delete the element pointed by it.

If you do not know what elements that function inside the loop erases assume that all iterators are invalidated.

Maxim Egorushkin
  • 131,725
  • 17
  • 180
  • 271
  • The problem is that OP-s function does this: `//this function might erase elements on myMap`, so since it might erase any element in map - incrementing iterator before erase will not help. – marcinj Apr 22 '16 at 10:06
  • @MarcinJędrzejewski True, i documented the root cause. – Maxim Egorushkin Apr 22 '16 at 10:14
2

Maybe these 2 links will help:

Basically, what it all boils down to, is that you must update the iterator before it becomes invalid.

Community
  • 1
  • 1
Fara Importanta
  • 161
  • 1
  • 2
  • 10
0

You have to preserve the next iterator before erasing the current one; since the current one will be invalid after deleting the element.

auto nextit = it+1;
map.erase(it);
it = nextit;
Mohan Kumar P
  • 3,122
  • 1
  • 14
  • 17