每周技巧 #144：关联容器中的异构查找

本节阅读量:

本文翻译自 Abseil 官网的 Tip of the Week #144: Heterogeneous Lookup in Associative Containers。

原文最初作为 TotW #144 发布于 2018 年 3 月 23 日。

更新于 2020 年 4 月 6 日。

引言

关联容器会把元素和 key 关联起来。向容器插入元素或从容器查找元素，都需要一个等价 key。一般来说，容器要求 key 具有特定类型，这可能导致调用点低效：调用点需要在近似等价的类型之间转换（例如 std::string 和 absl::string_view）。

为了避免这种不必要的工作，有些容器提供异构查找。这个特性允许调用方传入任意类型的 key（只要用户指定的比较函数对象支持它们）。STL 容器中这个特性的例子见 std::map::find。

透明函数对象

透明函数对象是指接受不止一种特定类型的函数对象。它必须通过提供 is_transparent 内部类型来公开这一点。这个内部类型的实际定义并不重要，因为它只是作为标签使用。常见做法是用 using 声明把 is_transparent 设为 void。

当容器检测到透明函数对象时，其查找函数会原样转发用户指定的值，而不是先把它转换成 key_type（无论是隐式还是显式转换）。

隐式支持异构查找可能很危险，因为值之间的关系在转换后可能无法保持。例如，1.0 < 1.1，但 static_cast<int>(1.0) == static_cast<int>(1.1)。因此，用 double 在 std::set<int> 中查找值可能导致错误结果。这些潜在 bug 正是该特性需要显式选择启用的原因。

为性能使用异构查找

使用异构查找的一个常见原因是性能。我们可以构造 key_type，但这么做需要非平凡工作，而我们更愿意避免。例如：

1
2
3
4
5


std::map<std::string, int> m = ...;
absl::string_view some_key = ...;
// 构造一个临时 `std::string` 来查询。
// 分配 + 复制 + 释放可能主导 find() 调用成本。
auto it = m.find(std::string(some_key));

可以改用如下透明比较器：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


struct StringCmp {
  using is_transparent = void;
  bool operator()(absl::string_view a, absl::string_view b) const {
    return a < b;
  }
};

std::map<std::string, int, StringCmp> m = ...;
absl::string_view some_key = ...;
// 比较器 `StringCmp` 会接受任何可隐式转换为 `absl::string_view`
// 的类型，并通过声明 `is_transparent` 标签说明这一点。
// 我们可以把 `some_key` 传给 `find()`，而不必先转换为 `std::string`。
// 在这个例子里，这避免了构造 `std::string` 实例所需的不必要内存分配。
auto it = m.find(some_key);

它还有什么用？

有些情况下，仅仅为了查找而创建一个有效的 key_type 对象是不可能或不方便的。这时，我们可能想使用另一种更容易产生、但包含查找所需信息的类型。例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


struct ThreadCmp {
  using is_transparent = void;
  // Regular overload.
  bool operator()(const std::thread& a, const std::thread& b) const {
    return a.get_id() < b.get_id();
  }
  // Transparent overloads
  bool operator()(const std::thread& a, std::thread::id b) const {
    return a.get_id() < b;
  }
  bool operator()(std::thread::id a, const std::thread& b) const {
    return a < b.get_id();
  }
  bool operator()(std::thread::id a, std::thread::id b) const {
    return a < b;
  }
};

std::set<std::thread, ThreadCmp> threads = ...;
// 不能只为查找而构造一个拥有相同 id 的 `std::thread` 实例。
// 但可以改用 id 查找。
std::thread::id id = ...;
auto it = threads.find(id);

STL 容器支持和替代方案

标准有序容器（std::{map,set,multimap,multiset}）支持异构查找。标准无序容器（std::unordered_{map,set,multimap,multiset}）直到 C++20 才支持异构查找。

不过，新的 Swiss Tables 家族同时支持类似字符串的类型（std::string、absl::string_view 等）和智能指针（T*、std::shared_ptr、std::unique_ptr）的异构查找。它们要求哈希器和相等函数都标记为透明。所有其他 key 类型都要求用户显式选择启用。

B-Tree 容器（absl::btree_{set,map,multiset,multimap}）也支持异构查找。

Protocol Buffers 的关联 map 实现 google::protobuf::Map 在以 std::string 为 key 时，支持使用类似字符串的 key（任何可转换为 absl::string_view 的类型）进行异构查找。

每周技巧 #143：C++11 删除函数（`= delete`）

每周技巧 #146：默认初始化与值初始化

本节目录