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"

1 comment:

micheal pan said...

BE SMART AND BECOME RICH IN LESS THAN 3DAYS....It all depends on how fast 
you can be to get the new PROGRAMMED blank ATM card that is capable of
hacking into any ATM machine,anywhere in the world. I got to know about 
this BLANK ATM CARD when I was searching for job online about a month 
ago..It has really changed my life for good and now I can say I'm rich and 
I can never be poor again. The least money I get in a day with it is about 
$50,000.(fifty thousand USD) Every now and then I keeping pumping money 
into my account. Though is illegal,there is no risk of being caught 
,because it has been programmed in such a way that it is not traceable,it 
also has a technique that makes it impossible for the CCTVs to detect 
you..For details on how to get yours today, email the hackers on : (
atmmachinehackers1@gmail.com ). Tell your 
loved once too, and start to live large. That's the simple testimony of how 
my life changed for good...Love you all ...the email address again is ;
atmmachinehackers1@gmail.com