Wednesday, 3 August 2011

The order of elements in STL map

Have you ever been surprised by the order of elements when traversing the map? We insert elements with random keys but elements appear sorted by their keys when we traverse that map:


Map elements:

m["Austria"] = "Vienna"
m["Belgium"] = "Brussels"
m["Czech Republic"] = "Prague"

Maybe you expected that countries would be listed in the order of insertion, starting with Belgium but no, that wasn't the case. Let's unveil that magic which made our map sorted.

STL map is associative container so it provides an ability for fast retrieval of data based on keys. Fast lookup is provided by the container's implementation. Maps are usually implemented as binary search trees (ordered, sorted binary trees) where position of the new element depends on its key. Elements remain sorted after insertion; they are NOT stored in the order of insertion like those in vector! Insertion order is lost.

When a new element is being added to a map, its key is compared with keys of existing elements in the map. For each key type there must be some function (let's call it is_less) that accepts two objects of that type, compares them and returns true if left one has lower value than the right one. Hey, we used map but we never mentioned is_less in the code! Why? That's because std::map uses its default comparison function, or more precisely, functor.

Map constructor has four parameters of which last two are optional:

Traits argument is (according to this MSDN article) "The type that provides a function object that can compare two element values as sort keys to determine their relative order in the map. This argument is optional and the binary predicate less is the default value".

std::less is default functor used for keys comparison so, in our case, it was std::less⟨std::string⟩ that helped that wizzard to order elements during insertion.

There is NO way of preserving the order of insertion. The only thing we can do is to provide some custom comparison function/functor which will redefine the meaning of the 'is less' relation. It's a bit of cheating but this way we can insert our countries in reverse order. All we need is a functor 'is_less' which returns true when string1 is actually greater than string2:

With the map which uses this custom comparison function the output is:

Map elements:

m["Czech Republic"] = "Prague"
m["Belgium"] = "Brussels"
m["Austria"] = "Vienna"

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