Google C++每周贴士 #144: 关联容器的混杂查询

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

每周贴士 #144: 关联容器的混杂查询

• 最初发布于：2018-03-23
• 作者：Samuel Benzaquen
• 更新于：2020-04-06
• 短链接：abseil.io/tips/144

介绍

关联容器为每个元素关联了一个键（key）。在容器中插入或查询元素需要一个等值的键。通常情况下，容器要求键是特定的类型，这可能导致调用处的低效率，因为需要在近似的类型之间做转换（比如

std::string

和

absl::string_view

）。

为避免这个不必要的工作，有些容器提供了 混杂查询。这个特性允许调用者传入任意类型的键（只要用户提供的比较仿函数支持它）。std::map::find提供了一个STL容器上该特性的例子。

透明仿函数

透明仿函数是指接受多于一种特定类型的仿函数。它必须提供一个内嵌类型

is_transparent

，以将该事实公开。这个内嵌类型的实际定义并不重要，因为它基本只被用作一个标记。

is_transparent

常常是以

using

声明的

void

。

当容器检测到一个透明仿函数的时候，其查询函数将会把用户指定的值原封不动地转寄，而不是先将其（隐式或显式地）转换为

key_type

。

隐式地支持混杂查询可能是危险的，因为值之间的关系在换换之后可能不再成立。例如，

1.0 < 1.1

，但是

static_cast<int>(1.0) == static_cast<int>(1.1)

。因此，用

double

在

std::set<int>

中查找一个值可能导致错误的结果。这些潜在的缺陷是导致这个特性是选择性引入（opt-in）的原因。

使用混杂查询以提升效率

效率是一个常见的使用混杂查询的原因。我们可以构造

key_type

，但这样做需要一些本可以避免的开销。例如：

std::map<std::string, int> m = ...;
absl::string_view some_key = ...;
// 构造一个临时的`std::string`以进行查询。
// 这个申请+复制+释放的操作可能会主宰find()调用（译者注：的开销）。
auto it = m.find(std::string(some_key));
           

反之，我们可以用如下的透明仿函数：

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

对象。在这样的情况下，我们可能想改用一个更容易构造但包含了查询所需的必要信息的类型。例如：

struct ThreadCmp {
  using is_transparent = void;
  // 普通重载。
  bool operator()(const std::thread& a, const std::thread& b) const {
    return a.get_id() < b.get_id();
  }
  // 透明重载
  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}

）自

C++14

起支持混杂查询。到

C++17

为止，无序容器尚不支持。有一些添加该特性的提案，但都尚未被接受。

不过，新的Swiss Tables容器族对字符串类型（

std::string

、

absl::string_view

等）和智能指针（

T*

、

std::shared_ptr

、

std::unique_ptr

）支持混杂查询。它们要求哈希子（hasher）和判等函数（equality function）都被标记为透明的。其他任何键类型都要求用户显式地引入（opt-in）。

B树容器（

absl::btree_{set,map,multiset,multimap}

）也支持混杂查询。