Originally posted as TotW #136 on June 23, 2017
“Sometimes, when the material is really good, you put expectations on yourself to make it the best possible show. You’re not just serving up the regular hash and doing your job and going home.” — Peter Dinklage
TL;DR: See https://abseil.io/docs/cpp/guides/container for official and up-to-date recommendations. This tip introduced the new types, but is not the canonical reference.
There is a new family of associative containers in town. They boast improvements
to efficiency and provide early access to APIs from C++17. They also provide
developers with direct control over their implementation and default hash
functions, which is important for the long term evolution of a code base. New
code should prefer these types over
std::unordered_map . All of the maps and
sets in this family have APIs that are nearly identical to
so transitioning to them is easy.
absl::*_hash_map there is also an
absl::*_hash_set; however, the
diagrams will only depict the
map case and we will often refer to just the
These should be your default choice. They store their
value_type inside the
main array. Because they move data when they rehash, elements don’t get pointer
stability. If you need pointer stability or your values are large, consider
absl::node_hash_map instead, or
Warning: Because of pointer instability after
rehash() code like
map["b"] will access invalidated memory.
These allocate their
value_type in nodes outside of the main array (like
std::unordered_map). Because of the separate allocation, they provide pointer
stability (the address of objects stored in the map does not change) for the
stored data and empty slots only require 8 bytes. Additionally, they can store
things that are neither moveable nor copyable.
We generally recommend that you use
absl::node_hash_map<K, V>, and similarly for