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
73214 次浏览
小开

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.

小开

For set, multiset, map, multimap the time complexity for insertion, deletion and retrieving information is O(logn) as they follow the balance binary tree to structure the data.

For unordered_set and unordered_map, hashing method is utilize to structure the data. So the time complexity for this is O(1). This is perfect way to perform any operation on information in case your prerequisite is not to have data in sorted order.


提交答案