Internal storage requirements of C++ UnorderedAssociativeContainer

user_2962393 0
Viewed 64

I've been reading about C++ containers and iterators. For my question, I think the following observations are relevant:

  1. UnorderedAssociativeContainer is a Container.
  2. value_type is std::pair<const Key, T>.
  3. iterator is LegacyForwardIterator and dereferencing it returns container's value_type.

Does this imply that any UnorderedAssociativeContainer must internally store items as value_type?

My curiosity stems from a considering the memory footprint of containers. If I have std::unordered_map<int32_t, int64_t>, then on 64-bit systems std::pair<int32_t, int64_t> will have 32 unused bits due to alignment. I think we should be able to store things more compactly, but I don't see how to satisfy the requirements if the storage is organized in any other way than value_type.

How could iterator return a reference to value_type if the internal storage were organized differently?

c++
1 Answers

Technically, no. The implementation of the standard library is not constrained by the language standard (in fact, it is impossible to implement the full standard library without relying on compiler extensions). An implementation could rely on some exceedingly unusual processor functionality to tightly pack the elements while still exposing them (including their user-visible memory layout) as pairs.

With that said, all standard library implementations I’m aware of do use pair for storage.

user_7874800
Related