Map (associative array, dictionary)

Structure:

- a collection of (key, value) pairs such that each possible key appears at most once in the collection

Operations:

- add (insert): addition of pairs to the collection
- remove (delete): removal of pairs from the collection
- reassign: modification of the values of existing pairs; binding an old key to a new value
- lookup of the value associated with a particular key

Implementations:

- Association list (linked list in which each list element (or node) comprises a key and a value)
- direct addressing into an array (efficient only when the keys are restricted to a narrow range of integers)
- Hash table
- binary search tree

C++:

std::map: Internally, the elements in the map are sorted from lower to higher (or vice versa) key value following a specific strict weak ordering criterion set on construction.

Associative array