Qualified's blog

Unordered set and map
By Qualified, history, 4 years ago, In English

I was reading up on STL, and I was reading the unordered_set std::count function. It says that worst case is linear and average is constant. Is there a way to make the worst case be constant instead of it being linear?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From Geeksforgeeks, An unordered_set is implemented using a hash table where keys are hashed into indices of a hash table so that the insertion is always randomized. All operations on the unordered_set takes constant time O(1) on an average which can go up to linear time O(n) in worst case which depends on the internally used hash function, but practically they perform very well and generally provide a constant time lookup operation.

→ Reply