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:



Output:

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"

No comments: