Book Image

Learning Boost C++ Libraries

By : Arindam Mukherjee
Book Image

Learning Boost C++ Libraries

By: Arindam Mukherjee

Overview of this book

Table of Contents (19 chapters)
Learning Boost C++ Libraries
About the Author
About the Reviewers

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, such a relation is called a strict weak ordering.

Consider the following example:

 1 #include <string>
 2 #include <tuple>
 4 struct Person  {
 5   std::string name;
 6   int age;
 7   std::string profession;
 8   std::string nationality...