multiset, map and hash map complexity


I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:

  • inserting entries
  • accessing entries
  • retrieving entries
  • comparing entries
4/23/2016 5:20:07 PM

map, set, multimap, and multiset

These are implemented using a red-black tree, a type of balanced binary search tree. They have the following asymptotic run times:

Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)

hash_map, hash_set, hash_multimap, and hash_multiset

These are implemented using hash tables. They have the following runtimes:

Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case

If you use a proper hash function, you'll almost never see the worst case behavior, but it is something to keep in mind — see Denial of Service via Algorithmic Complexity Attacks by Crosby and Wallach for an example of that.

11/29/2018 4:24:09 AM

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow