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

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)

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.

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow