Monday 1 August 2011

Removing selected map elements whilst iterating through it

Couple of days ago I wrote about how to remove elements from vector while iterating through it and today I will focus on the same task but performed on STL map data structure.

Let's say we have a dictionary which keys are names of countries and values are names of their capitals. There was an error when capitals were typed so all their names begin with small letters. We want to correct this mistake and make those names to start in capital letters. On the top of this, for some reason, we want to remove those countries which capitals start with a letter 'B'.

Someone might write something like this:



When execution tries to move iterator to the next position after one element has been erased Debugger brings up Debug Assertion window:

MapIteratorNotIncrementable

In aforementioned article we learned that vector::erase invalidates iterators that point at or after element being deleted. Now we know what could have caused this assertion to fail - invalidated iterator. Documentation says that map::erase invalidates only iterator that points to the element being deleted. That was exactly what happened in our case - iterator became invalid after map::erase so it could not have been increased so to point to the next element.

The trick here is to increase iterator BEFORE calling erase:



Output:

Initial map elements:

m["Austria"] = "vienna"
m["Belgium"] = "brussels"
m["Czech Republic"] = "prague"
m["Denmark"] = "copenhagen"
m["Estonia"] = "tallinn"
m["Finland"] = "helsinki"
m["Greece"] = "athens"
m["Hungary"] = "budapest"
m["Iceland"] = "reykjavik"
m["Latvia"] = "riga"
m["Malta"] = "valletta"
m["United Kingdom"] = "london"

Map elements after deletions:

m["Austria"] = "vienna"
m["Czech Republic"] = "prague"
m["Denmark"] = "copenhagen"
m["Estonia"] = "tallinn"
m["Finland"] = "helsinki"
m["Greece"] = "athens"
m["Iceland"] = "reykjavik"
m["Latvia"] = "riga"
m["Malta"] = "valletta"
m["United Kingdom"] = "london"

Nice! No scary assertion dialogs, capitals with 'B' are removed...err...Why do names of capital cities still start with small letters??? We get object for a given dictionary key and we do CHANGE it, right? Do we? Which object is actually changed? In the example above strCapital is string object, initialized with string returned by dereferencing iterator...but strCapital object is totally independent from the object IN the dictionary! It is a COPY! We do change that local variable but that is just wasted effort as we don't change object in the dictionary! We need to access ORIGINAL object and we can do it either by using pointer to it or its reference. This is C++ program and natural choice is to use reference:



Output is now as expected:

Initial map elements:

m["Austria"] = "vienna"
m["Belgium"] = "brussels"
m["Czech Republic"] = "prague"
m["Denmark"] = "copenhagen"
m["Estonia"] = "tallinn"
m["Finland"] = "helsinki"
m["Greece"] = "athens"
m["Hungary"] = "budapest"
m["Iceland"] = "reykjavik"
m["Latvia"] = "riga"
m["Malta"] = "valletta"
m["United Kingdom"] = "london"

Map elements after deletions:

m["Austria"] = "Vienna"
m["Czech Republic"] = "Prague"
m["Denmark"] = "Copenhagen"
m["Estonia"] = "Tallinn"
m["Finland"] = "Helsinki"
m["Greece"] = "Athens"
m["Iceland"] = "Reykjavik"
m["Latvia"] = "Riga"
m["Malta"] = "Valletta"
m["United Kingdom"] = "London"

No comments: