CODEWITHSUNDEEP
c++unordered-map
code707
code707

Reputation: 1701

Why does std::unordered_map provide an equal_range member function?

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?

Upvotes: 10

Views: 2612

Answers (4)

jfMR
jfMR

Reputation: 24748

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?

In general, the order, in which elements stored in a std::unordered_multimap are obtained while traversing it, is actually not defined. However, note that std::unordered_multimaps are usually implemented as hash tables. By analysing such an implementation you will realize that the ordering is not going to be as "undefined" as someone might initially think.

At element insertion (or hash table rehashing), the value resulting of applying the hash function to an element's key is used to select the bucket where that element is going to be stored. Two elements with equal keys will result in the same hash value, therefore they will be stored in the same bucket, so they come togetherX while iterating an std::unordered_multimap.

XNote that even two elements with different keys might also result in the same hash value (i.e., a collision). However, std::unordered_multimap can handle these cases by comparing the keys against equality, and therefore still group elements with equal keys together.

Upvotes: 0

NathanOliver
NathanOliver

Reputation: 180660

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

Upvotes: 11

Caleth
Caleth

Reputation: 62779

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

Upvotes: 4

Detonar
Detonar

Reputation: 1429

cplusplus.com writes about std::unordered_map::equal_range:

Returns the bounds of a range that includes all the elements in the container with a key that compares equal to k. In unordered_map containers, where keys are unique, the range will include one element at most.

Upvotes: 2

Related Questions