COMS W4995 C++ Deep Dive for C Programmers

Associative Containers

Lecture outline

1. std::map

   • std::map is a sorted associative container
   • contains key-value pairs with unique keys
   • requires “less-than” for key
   • balanced binary tree (usually Red–black tree) of pair<key,value>

2. Code walk-through

   • m[s]
   • iterating through a map using map::iterator

3. More convenient loops: range-for and structured binding

4. Looking up an entry with find()

5. std::unordered_map

   • Hash table instead of binary tree
   • Requires key equality and hashing

   • Replacing map with unordered_map works without any other change:

     unordered_map<string,int> m;
     

6. std::multimap

   • Same as map, except you can have multiple entries with the same key
   • std::distance()

7. unordered_multimap

   • Same as multimap, except it’s a hash table instead of a binary tree
   • Replacing multimap with unordered_multimap requires no other change

8. Sets