CODEWITHSUNDEEP
c++stdunordered-map
lancery
lancery

Reputation: 678

Does std::unordered_multimap's bucket only contain elements with equivalent keys

On www.CPlusPlus.com, it states the following for unordered_multimap,

Elements with equivalent keys are grouped together in the same bucket and in such a way that an iterator (see equal_range) can iterate through all of them.

I know we cannot infer this from that statement, but I'd like to know if a given bucket only contains elements with the equivalent keys?

Upvotes: 4

Views: 1346

Answers (2)

Mooing Duck
Mooing Duck

Reputation: 66991

Elements with the same key will end up in the same bucket, but other elements may also end up in the same bucket. You cannot infer that all elements in the same bucket have equivelent keys.

I don't think the spec says this explicitly, but the way the unordered_map works is that it uses the hash of the key to determine which bucket the element goes in. Two keys can hash to the same value, which would mean both keys would be put into the same bucket. However, two elements with the same key will have the same hash, and thus always be in the same bucket. Additionally Since the number of buckets can be set in the constructor, then each bucket must therefore contain a range of keys, though the ranges will change as the number of buckets changes.

You could, have an unordered_multimap that attempted to use one bucket per 100 elements on average, which would be conforming (and rediculously silly), but if you had less than 100 elements it would be putting all of the elements into a single bucket.

Upvotes: 2

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385405

Here are the only pertinent requirements:

[C++11: 23.2.5/5]: Two values k1 and k2 of type Key are considered equivalent if the container’s key_equal function object returns true when passed those values. If k1 and k2 are equivalent, the hash function shall return the same value for both. [..]

[C++11: 23.2.5/8]: The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket. [..]

There is nothing prohibiting all elements with key hash a and all elements with key hash b from being stored in the same bucket. It is up to the standard library implementation that you use as to whether or not this fact is used.

No standard wording exists to make this explicit; it's defined by omission.

Upvotes: 5

Related Questions