Learning Boost C++ Libraries

Fast lookups using Boost Unordered containers

The four standard associative containers in C++03: std::set, std::map, std::multiset, and std::multimap are ordered containers and store their keys in some sorted order using balanced binary search trees. They require an ordering relationship to be defined for their keys and provide logarithmic complexity insertions and lookups. Given the ordering relationship and two keys, A and B, we can determine whether A precedes B or B precedes A in the relationship. If neither precedes the other, the keys A and B are said to be equivalent; this does not mean A and B are equal. In fact, the ordered containers are agnostic to equality and there need not be a notion of equality defined at all. This is the reason, ...