C++ High Performance

Unordered sets and maps

The unordered versions of sets and maps offer a hash-based alternative to the tree-based versions. This data structure is in general referred to as hash tables. In theory, hash tables offer constant-time insert, add, and delete operations, which are, of course, better than the tree-based versions that operate in O(log n). However, in practice the difference might not be so obvious, especially if you are not storing a very large amount of elements in your container.

Let's see how a hash table can offer O(1) operations. A hash table keeps its elements in some sort of array. When adding an element to the hash table, an integer is computed for the element using a hash function. The integer is usually called the hash of ...