Google C++每周贴士 #136: 无序容器

（原文链接：https://abseil.io/tips/136 译者：[email protected]）

每周贴士 #136: 无序容器

• 最初发布于：2017-06-23
• 作者：Matt Kulukundis
• 更新于：2020-04-06
• 短链接：abseil.io/tips/136

“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

长话短说：查看https://abseil.io/docs/cpp/guides/container以获取官方和最新的建议。本贴士 介绍 了这些新类型，但并不是权威参考。

介绍

absl::*_hash_map

现在有一族新的关联容器到货了。它们自诩有效率提升，还尝鲜了C++17的API。它们还允许开发者直接控制实现细节和默认哈希函数，这些对代码库的长期演进很重要。新的代码应该尽量用这些类型而不是

std::unordered_map

。这一族map和set拥有与

std::unordered_map

几乎相同的API，所以迁移到它们很容易。

每一个

absl::*_hash_map

都有对应的

absl::*_hash_set

；但是，下面只会勾勒出

map

的情况，我们也总是指

map

。

absl::flat_hash_map

和

absl::flat_hash_set

这应该是你的默认选项。它们把

value_type

存储在主数组之内。因为它们在重新计算哈希的时候会移动数据，所以元素指针并不稳定。如果你需要指针稳定性，或者你的数据很大，请考虑改用

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

也是一样。