Use of equal_range for unordered_map

Question

As it makes sense, lower_bound and upper_bound are absent for std::unordered_map because there is no order for elements.

However std::unordered_map has method equal_range. it return iterators for range corresponding to a key.

How does it make sense? Since there can be only one element with a key in std::unordered_map. It is just find method.

Also, in std::unordered_multimap, does it presence means all elements with same key will always come together while iterating unordered_multimap with a iterator?

Answer 1

How does it make sense?

It kind of does. The standard requires all associative container to offer equal_range so the non multi containers need to provide it. It does make writing generic code easier so I suspect that is the reason why all of the containers are required to use it.

Does it presence means all elements with same key will always come together while iterating unordered_map with a iterator?

Actually, yes. Since the all of the keys will have the same value they will hash to the same value which means they all get stored in the same bucket and will be grouped together since the keys compare equally. From [unord.req]/6

An unordered associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. unordered_­set and unordered_­map support unique keys. unordered_­multiset and unordered_­multimap support equivalent keys. In containers that support equivalent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container. Thus, although the absolute order of elements in an unordered container is not specified, its elements are grouped into equivalent-key groups such that all elements of each group have equivalent keys. Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified.

^{emphasis mine}

Answer 2

It's for consistency with the other containers.

It makes more sense in the _multi variants, but is present in all the associative (and unordered associative) containers in the standard library.

It allows you to write code like

template <typename MapLike, typename KeyLike>
void do_stuff(const MapLike & map, const KeyLike & key)
{
    auto range = map.equal_range(key);
    for (auto it = range.first; it != range.second; ++it)
         // blah
}

Which does not care about what specific container it is dealing with