Alex Rivera | Logout

How expensive is comparing two unordered sets for equality?

Asked 2012-04-12T06:33:00.900
15

Given two std::sets, one can simply iterate through both sets simultaneously and compare the elements, resulting in linear complexity. This doesn't work for std::unordered_sets, because the elements may be stored in any order. So how expensive is a == b for std::unordered_set?

c++ set complexity-theory equality unordered-set
Edit
Report

1 Answer

5

Complexity of operator== and operator!=:

Linear complexity in the average case. N2 in the worst case, where N is the size of the container.

More details in the standard ยง23.2.5, point 11:

For unordered_set and unordered_map, the complexity of operator== (i.e., the number of calls to the == operator of the value_type, to the predicate returned by key_equal(), and to the hasher returned by hash_function()) is proportional to N in the average case and to N2 in the worst case, where N is a.size().

answered 2012-04-12T06:41:41.257

Your Answer