C++: 使用異構(gòu)查找來提高性能

關(guān)聯(lián)容器將元素與鍵相關(guān)聯(lián)。插入或從容器中查找元素需要等效鍵。通常，容器要求鍵是特定類型的，這會導(dǎo)致調(diào)用站點的效率低下，需要在接近等效的類型（如 std::string 和 absl::string_view）之間進行轉(zhuǎn)換。

為了避免這種不必要的工作，一些容器提供了異構(gòu)查找。此功能允許調(diào)用者傳遞任何類型的鍵（只要用戶指定的比較器函子支持它們）。有關(guān) STL 容器中此功能的示例，請參見 std::find。

使用異構(gòu)查找來提高性能

使用異構(gòu)查找的一個常見原因是性能。我們可以構(gòu)造 key_type，但這樣做需要我們寧愿避免的非平凡工作。例如：

std::map 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));

Instead, we can use a transparent comparator like so:

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


std::map m = ...;
absl::string_view some_key = ...;
// The comparator `StringCmp` will accept any type that is implicitly
// convertible to `absl::string_view` and says so by declaring the
// `is_transparent` tag.
// We can pass `some_key` to `find()` without converting it first to
// `std::string`. In this case, that avoids the unnecessary memory allocation
// required to construct the `std::string` instance.
auto?it?=?m.find(some_key);

STL 容器支持和替代方案

有序容器 (std::{map,set,multimap,multiset}) 從 C++14 開始支持異構(gòu)查找。從 C++17 開始，無序容器仍然不支持它。有添加此功能的建議，但尚未被接受。

GTL 容器支持

在 gtl/absl 中支持異構(gòu)查找的容器包括：

go/btree：btree 容器 absl::btree_{set,map,multiset,multimap}。它們隱含地支持對具有常見比較器的類字符串鍵的異構(gòu)查找，例如 std::less 其中 T 是 {std::string, absl::string_view, absl::Cord} 之一（對于 std::greater ）。所有其他密鑰類型都需要用戶明確選擇加入。

go/swisstable：無序容器 absl::{flat,node}_hash_{set,map}。它們要求哈希函數(shù)和相等函數(shù)都被標(biāo)記為透明的。出于性能原因，swisstable 隱式支持字符串鍵表的異構(gòu)查找。所有其他密鑰類型都需要用戶明確選擇加入。

扁平有序容器 gtl::flat_{set,map,multiset,multimap}。

gtl::LockFreeHash{Set,Map}。

本文那個題目的答案是?None of the above: this code is correct and efficient.

編輯：黃飛

?