C++17 STL Cookbook

Hash tables

When talking about associative containers, search trees are not the only way to implement them. With hash tables, items can be found in O(1) time, but they ignore the natural order of the items, so they can't be easily traversed in a sorted manner. The size of the hash table can be manipulated by the user, and the hash function can also be chosen individually, which is important, because the performance versus space consumption characteristics depend on that.

std::unordered_set and std::unordered_map have so much interface in common with their std::set and std::map pendants, that they can be used almost interchangeably.

Just as for the search tree implementations, both containers have their multipendants: std::unordered_multiset ...