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}

）也支援混雜查詢。