每周技巧 #136：无序容器
本节阅读量:本文翻译自 Abseil 官网的 Tip of the Week #136: Unordered Containers。
原文最初作为 TotW #136 发布于 2017 年 6 月 23 日。
更新于 2020 年 4 月 6 日。
快捷链接：abseil.io/tips/136
“有时，当材料真的很好时，你会给自己设下期待，想把它做成尽可能好的演出。你不只是端上普通杂烩，完成工作然后回家。” —— Peter Dinklage
TL;DR：官方且最新的建议见 https://abseil.io/docs/cpp/guides/container。本技巧介绍了这些新类型，但不是权威参考。
介绍 absl::*_hash_map
这里来了一组新的关联容器家族。它们提升了效率，并提前提供了 C++17 中的一些 API。它们还让开发者可以直接控制其实现和默认哈希函数，这对代码库的长期演进很重要。新代码应优先使用这些类型，而不是 std::unordered_map。这个家族中的所有 map 和 set API 都与 std::unordered_map 几乎相同，因此迁移到它们很容易。
每个 absl::*_hash_map 也都有对应的 absl::*_hash_set；不过，图示只会展示 map 情况，文中也常常只提 map。
absl::flat_hash_map 和 absl::flat_hash_set
它们应该是你的默认选择。它们把 value_type 存储在主数组内部。由于 rehash 时会移动数据，元素不具备指针稳定性。如果你需要指针稳定性，或者 value 很大，可以考虑改用 absl::node_hash_map，或者也许使用 absl::flat_hash_map<Key, std::unique_ptr<Value>>。
警告：由于 rehash() 后指针不稳定，像 map["a"] = map["b"] 这样的代码会访问已失效内存。
absl::node_hash_map 和 absl::node_hash_set
它们在主数组之外的节点中分配 value_type（类似 std::unordered_map）。由于单独分配，它们为已存储数据提供指针稳定性（map 中对象的地址不会改变），并且空槽只需要 8 字节。此外，它们可以存储既不可移动也不可复制的东西。
我们通常建议使用 absl::flat_hash_map<K, std::unique_ptr<V>>，而不是 absl::node_hash_map<K, V>；对 node_hash_set 也类似。
