Overview

All eight ordered and unordered containers have in common that they associate a key with a value. You can use the key to get the value. To get a classification of the associative containers, three simple questions need to be answered:

• Are the keys sorted?
• Does the key have an associated value?
• Can a key appear more than once?

The following table with 2^3= 8 rows gives the answers to the three questions. I answer a fourth question in the table. How fast is the access time of a key in the best case?

Characteristics for associative containers

Associative container	Sorted	Associated value	More identical keys	Access time
std::set	yes	no	no	logarithmic
std::unordered_set	no	no	no	constant
std::map	yes	yes	no	logarithmic
std::unordered_map	no	yes	no	constant...