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

也是一樣。