C++ STL Map and Set

02 Jun 2013

Some note to myself:

In C++ STL, the elements of std::map are ALWAYS sorted by its key, following a specific strict weak ordering indicated by its internal comparison object (of type Compare).

This is because maps are typically implemented as binary search tree. If you need a real ‘hash table’ structure, use std::unordered_map. The same concept applies to std::set and std::unordered_set.

Therefore, if you care the efficiency of accessing elements by their key, then using std::unordered_map would be a better choice.

However, sometimes a bit of ordering in a container could be quite useful. For example, if you want to find the largest member (according to key value) in a map, all you need to do is mymap.rbegin().