std::unordered_map

Explanation

Hash table.

See std::unordered_map.

Memory: array of buckets (each bucket is a linked list of entries). Can use more memory than std::map due to bucket overhead.

Time complexity:

Worst case is O(n) for every operation. It occurs with many hash collisions (all keys hash to same bucket).

Use case

• Fast lookup is priority.
• Do not need sorted iteration.
• Large number of elements.
• std::unordered_map can be slower than std::map for small sizes due to hash function overhead.

Code

#include <print>
#include <string>
#include <unordered_map>

int main() {
  std::unordered_map<std::string, uint64_t> symbolLookup;

  symbolLookup.emplace("_main", 0x10001000);
  symbolLookup.emplace("_helper", 0x10002000);
  symbolLookup.emplace("_init", 0x10003000);

  std::println("_main is at: {:#x}", symbolLookup["_main"]);

  return 0;
}

View on GitHub.

Output

$ ./src/data-structures/build/std-unordered_map
_main is at: 0x10001000