Abseil系列七容器库

简介

Abseil提供了许多容器作为STL容器的替代品。这些容器通常遵循STL容器的属性，尽管通常有一些相关的API差异和/或实现细节与标准库不同。

Abseil容器的设计在一般情况下更有效率;然而，在某些情况下，STL容器可能更有效。与Abseil提供的其他一些抽象不同，这些容器不应该被视为它们的STL对应物的临时替代品，因为这两组容器之间存在API和/或契约差异。例如，Abseil容器通常不能保证插入或删除后指针的稳定性。

Abseil容器库定义了以下几组容器：

• 无序Hash Tables
• B-tree 有序容器

库内容

Abseil容器库包含许多有用的哈希表，被设计成std::unordered_map和std::unordered_set的替代品，通常遵循STL容器API约定：

• absl::flat_hash_map
• absl::flat_hash_set
• absl::node_hash_map
• absl::node_hash_set

它们提供了一些优于std::unordered_*容器的优点：

• 提供c 14对c 17机制(如try_emplace())的支持。

• 支持异构查找。

• 允许对emplace({key, value})进行优化，以避免在大多数常见情况下分配一对。

• 支持异构std::initializer_list，以避免构造和插入额外的副本。

• 通过返回void而不是迭代器来保证O(1)擦除方法。

// Examples using node_hash_set and node_hash_map are equivalent

// Default constructor
// No allocation for the table's elements is made.
absl::flat_hash_set<std::string> set1;

absl::flat_hash_map<int, std::string> map1;

// Initializer List constructor
absl::flat_hash_set<std::string> set2 = {{"huey"}, {"dewey"}, {"louie"},};

absl::flat_hash_map<int, std::string> map2 =
    {{1, "huey"}, {2, "dewey"}, {3, "louie"},};

// Copy constructor
absl::flat_hash_set<std::string> set3(set2);

absl::flat_hash_map<int, std::string> map3(map2);

// Copy assignment operator
// Hash functor and Comparator are copied as well
absl::flat_hash_set<std::string> set4;
set4 = set3;

absl::flat_hash_map<int, std::string> map4;
map4 = map3;

// Move constructor
// Move is guaranteed efficient
absl::flat_hash_set<std::string> set5(std::move(set4));

absl::flat_hash_map<int, std::string> map5(std::move(map4));

// Move assignment operator
// May be efficient if allocators are compatible
absl::flat_hash_set<std::string> set6;
set6 = std::move(set5);

absl::flat_hash_map<int, std::string> map6;
map6 = std::move(map5);

// Range constructor
std::vector<std::string> v = {"a", "b"};
absl::flat_hash_set<std::string> set7(v.begin(), v.end());

std::vector<std::pair<int, std::string>> v = {{1, "a"}, {2, "b"}};
absl::flat_hash_map<int, std::string> map7(v.begin(), v.end());

Absl::flat_hash_map和Absl::flat_hash_set

Absl::flat_hash_map和Absl::flat_hash_set是一般情况下推荐使用的无序容器。它们是平面数据结构，直接将它们的value_type存储在槽数组中。

• 注意事项：

  • 键和值内联存储。
  • 迭代器、引用和指向元素的指针在重新哈希时失效。
  • 移动操作不会使迭代器或指针失效。

• 内存使用情况：

  容器使用O((sizeof(std::pair<const K, V>) 1) * bucket_count())字节。最大负载因子为87.5%，之后表的大小会翻倍(使负载因子减小2倍)。因此size()通常在0.4375bucket_count()和0.875bucket_count()之间。对于从未重散列的表，负载因子可能更低，但这些数字足以满足我们的估计。

• 建议：

  如果需要值(而不是键)的指针稳定性，请使用absl::flat_hash_map<Key, std::unique_ptr>。

absl::node_hash_map和absl::node_hash_set

它们几乎直接替换了std::unordered_map和std::unordered_set。对比：

• 当键和值都需要指针稳定性1时。

• 对于从std::unordered_map, std::unordered_set, hash_map或hash_set的自动迁移，很难弄清楚代码是否依赖于指针稳定性。

注意事项

• 节点有稳定的地址。
• 迭代器在重新哈希时失效
• Move操作不会使迭代器失效

建议

使用absl::node_hash_map或absl::node_hash_set当需要键和值的指针稳定性时(很少)，或者从具有此属性的其他容器进行代码迁移时。注意:不要用流行度作为指导。您将看到“节点”容器被大量使用，但这只是因为将代码从其他容器迁移到它们是安全的。

使用：

absl::flat_hash_map<int, string> numbers =
    {{1, "one"}, {2, "two"}, {3, "three"}};
numbers.try_emplace(4, "four");

absl::flat_hash_map<string, std::unique_ptr<string>> strings;
strings.try_emplace("foo", absl::make_unique<string>("bar"));

异构查找

在关联容器中插入或查找元素需要一个键。一般来说，容器要求键是特定类型的，这可能会导致在需要在近乎等效的类型(例如std::string和absl::string_view)之间进行转换的调用站点效率低下。

std::map<std::string, int> m = ...;
absl::string_view some_key = ...;
// Construct a temporary `std::string` to do the query.
// The allocation   copy   deallocation might dominate the find() call.
auto it = m.find(std::string(some_key));

为了避免这种不必要的工作，Swiss表通过absl::Hash散列框架提供了对字符串类型的转换(例如，在查找中允许absl::string_view)和对智能指针类型的转换(std::unique_ptr, std::shared_ptr)的异构查找。(支持的比较器内置于absl::Hash中。)

迭代顺序：

虽然std::unordered_map不保证迭代顺序，但许多实现恰好有一个基于键及其插入顺序的确定顺序。对于absl::flat_hash_map和absl::node_hash_map则不是这样。因此，将std::unordered_map转换为absl::flat_hash_map会暴露出代码错误地依赖于迭代顺序的潜在错误。

一个特殊的情况可能会产生一个微妙的错误是在一个无序容器中对浮点值求和。虽然数学和不依赖于顺序，但浮点和依赖于顺序，并且std::unordered_set中的和是确定的，而absl::flat_hash_set中的和是不确定的。

B-tree Ordered Containers

Abseil容器库包含有序的容器，通常遵循STL容器API契约，但使用(通常更有效)b树而不是二叉树(如在std::map等中使用)实现:

• absl: btree_map

• absl: btree_set

• absl: btree_multimap

• absl: btree_multiset

这些有序容器被设计为在大多数情况下更有效地替代std::map和std::set。具体来说，与有序的std:: containers相比，它们提供了几个优点:

• 在大多数情况下提供比STL更低的内存开销。

• 通常比它们的STL对等体更缓存友好(因此更快)。

• 为c 17机制(如try_emplace())提供c 14支持。

• 支持异构查找。

使用：

// Examples using btree_multimap and btree_multiset are equivalent

// Default constructor
// No allocation for the B-tree's elements is made.
absl::btree_set<std::string> set1;

absl::btree_map<int, std::string> map1;

// Initializer List constructor
absl::btree_set<std::string> set2 = {{"huey"}, {"dewey"}, {"louie"},};

absl::btree_map<int, std::string> map2 =
    {{1, "huey"}, {2, "dewey"}, {3, "louie"},};

// Copy constructor
absl::btree_set<std::string> set3(set2);

absl::btree_map<int, std::string> map3(map2);

// Copy assignment operator
// Hash functor and Comparator are copied as well
absl::btree_set<std::string> set4;
set4 = set3;

absl::btree_map<int, std::string> map4;
map4 = map3;

// Move constructor
// Move is guaranteed efficient
absl::btree_set<std::string> set5(std::move(set4));

absl::btree_map<int, std::string> map5(std::move(map4));

// Move assignment operator
// May be efficient if allocators are compatible
absl::btree_set<std::string> set6;
set6 = std::move(set5);

absl::btree_map<int, std::string> map6;
map6 = std::move(map5);

// Range constructor
std::vector<std::string> v = {"a", "b"};
absl::btree_set<std::string> set7(v.begin(), v.end());

std::vector<std::pair<int, std::string>> v = {{1, "a"}, {2, "b"}};
absl::btree_map<int, std::string> map7(v.begin(), v.end());

这篇好文章是转载于：学新通技术网