# 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**.&#x20;

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**.&#x20;

![Visual illustration of the difference between a map and a set](https://4122513583-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MSrqC8yBLK9rXNyJ6ol%2F-MdkTP_p6ZYrweBxjOG4%2F-MdkWEYVXKOd_poUtKxD%2FBlank%20diagram%20-%20Page%204.png?alt=media\&token=7764b8c0-47cc-4f50-8a79-e2d8b9d1587d)

## 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&#x20;
* A value&#x20;
* 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.&#x20;

## Hash Sets &#x20;

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.&#x20;
