Блог пользователя Qualified

Unordered set and map
Автор Qualified, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить