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

Skip to content
# C++ – multiset, map and hash map complexity

###### Related Question

big-oc++complexity-theory

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

- C++ – When should static_cast, dynamic_cast, const_cast and reinterpret_cast be used
- Computational complexity of Fibonacci Sequence
- C++ – The Definitive C++ Book Guide and List
- What does O(log n) mean exactly
- C++ – Why do we need virtual functions in C++
- How to building a heap be O(n) time complexity
- How to find time complexity of an algorithm
- Determining complexity for recursive functions (Big O notation)

## Best Solution

## 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.