CODEWITHSUNDEEP
c++c++11language-lawyerunordered-map
Praxeolitic
Praxeolitic

Reputation: 24039

Does the standard mandate that std::unordered_map place key value pairs together in memory?

Does the C++ standard in effect mandate that a conforming implementation of std::unordered_map place each key and value together in memory?

I think the answer is yes since much of std::unordered_map is specified in terms of std::pair and I don't think the maneuvers necessary to hide the details of key value pairs that are disjoint in memory could be completely hidden but I'm not sure.

Upvotes: 2

Views: 247

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490008

The standard requires that the value_type for std::map::iterator be std::pair<const key, T>, so (for example) as you walk through the map with an iterator, each time you dereference the iterator, you get a pair<const key, T>.

The standard also mandates that (for example) that emplace returns an iterator "to the newly inserted element". At least by my reading, that means you can't have it store the key and value separately from each other, and just (for example) copy a key/value into a temporary location, so it can return a pointer/reference to that location on demand.

The latter would (for example) violate exception safety requirements. It would have to do copying just to make elements in the collection visible, in cases where that's not allowed because such copying could throw an exception, but the function in question isn't allowed to do so (in fact, it's possible to emplace types that can't be copied at all).

Upvotes: 8

Revolver_Ocelot
Revolver_Ocelot

Reputation: 8785

Requirement for map iterator to point to std::pair<const Key, T> and reqirement that object to which iterator refers does not change its address over time, makes it impossible to implement in other way. Said pair should exist and be persistent.

Potentially map can hold both key-value pairs for exposition and maintain internal copies of keys to search by them, but it is unefficient both for space and perfomance.

Upvotes: 2

Related Questions