multiset, map and hash map complexity

c++ complexity-theory big-o
Harry picture Harry · Oct 21, 2008 · Viewed 63.1k times · Source

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

Answer

Adam Rosenfield picture Adam Rosenfield · Oct 21, 2008

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.

Related questions

Is list::size() really O(n)?

Recently, I noticed some people mentioning that std::list::size() has a linear complexity. According to some sources, this is in fact implementation dependent as the standard doesn't say what the complexity has to be. The comment in this blog …

Read More
Hashtable in C++?

I usually use C++ stdlib map whenever I need to store some data associated with a specific type of value (a key value - e.g. a string or other object). The stdlib map implementation is based on trees which …

Read More
c++ - unordered_map complexity

I need to create a lookup function where a (X,Y) pair corresponds to a specific Z value. One major requirement for this is that I need to do it in as close to O(1) complexity as I can. My …

Read More