Two unordered containers
a and
b compare equal if
a.size() == b.size() and, for every equivalent-key group
[
Ea1, Ea2) obtained from
a.equal_range(Ea1), there exists an
equivalent-key group [
Eb1, Eb2) obtained from
b.equal_range(Ea1),
such that
is_permutation(Ea1, Ea2, Eb1, Eb2) returns
true. 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_eq(),
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(). For
unordered_multiset and
unordered_multimap,
the complexity of
operator== is proportional to
∑E2i
in the average case and to
N2 in the worst case, where
N is
a.size(),
and
Ei is the size of the
ith equivalent-key group in
a. However, if the respective elements of each corresponding pair of
equivalent-key groups
Eai and
Ebi are arranged in the same order
(as is commonly the case, e.g., if
a and
b are unmodified copies
of the same container), then the average-case complexity for
unordered_multiset and
unordered_multimap becomes
proportional to
N (but worst-case complexity remains
O(N2), e.g., for
a pathologically bad hash function)
. The behavior of a program that uses
operator== or
operator!= on unordered containers is undefined
unless the
Pred function object has
the same behavior for both containers and the equality comparison function
for
Key is a refinement
of the partition into equivalent-key groups produced by
Pred.