CODEWITHSUNDEEP
c++c++11stl
Duncan
Duncan

Reputation: 1034

How efficient is iterating through an unordered_set?

Does iterating through an unordered_set require looking through each bucket of the hash table? If so, wouldn't that be very inefficient? If I want to frequently iterate over a set but still need remove in O(1) time is unordered_set still the best data structure to use?

Upvotes: 4

Views: 3858

Answers (3)

Joaquín M López Muñoz
Joaquín M López Muñoz

Reputation: 5658

As it happens, common implementations of std::unordered:set link all elements together much as a std::forward_list does, so traversing the container is basically equivalent to traversing a list (details here). In any case, when in doubt profile your program and see if results meet your needs.

Upvotes: 2

Nicol Bolas
Nicol Bolas

Reputation: 473447

Will iterating through a hash table be slower than iterating through a vector? Yes. A vector will store its elements contiguously; hash tables need some way to identify if a bucket contains data or not. Some hash tables give each bucket a linked list of values that map to the same bucket; others use other methods. Either way, an unordered_set iterator needs to look at each bucket and determine if its empty. That's not as fast as pointer arithmetic.

However, I would not classify the extra time spent looking at empty buckets as "very inefficient". Just because it's not as fast as a sorted vector doesn't mean it's inefficient. You still have cache coherency on your side, since buckets probably don't take up that much memory, and testing for an empty one is just a single cached memory fetch.

In the end, every data structure has tradeoffs. If you want O(1) lookup and removal, a hash table is the only way to get that. That means iteration is going to take longer than it would for a vector. But not as long as it would for a set.

Upvotes: 1

Joan Marcè i Igual
Joan Marcè i Igual

Reputation: 311

Hash tables store data in a vector and everything is indexed by converting the key into a hash number (typically a long) which becomes the index in the vector of the desired element, there are also hash tables using vectors inside vectors to do this. If you iterate through an std::unordered_set it has only cost O(n) because it's like iterating through a std::vector

Upvotes: 0

Related Questions