Chapter 20 - Notes

The STL map and unordered_map classes supply the programmer with container classes that help with applications that require frequent lookups.

This is very similar to the set and unordered_set classes; the difference is that maps store key-value pairs, while sets only store unique keys.

Like sets, all keys in a map have to be strictly unique, but the values in each key-value pair do not have to have unique.

Visual illustration of the difference between a map and a set

Binary Trees

Much like set, the map container is internally represented by a binary search tree. The difference is that each Node of the binary tree stores:

• A key

• A value

• A pointer to the root of the left subtree (a left child node)

• A pointer to the root of the right subtree (a right child node)

When inserting into a binary search tree of a map, comparisons are performed based on the key of the node, the same is done for lookups.

Hash Sets

Much like unordered_set, the unordered_map container is internally represented by a hash table. It differs slightly to a hash set in sense that a hash table provides key-value lookups.