以 std::pair 作为键透明搜索 std::map

Question

如果存在

std::map<std::pair<std::string, std::string>, some_type>

，找到其值的最佳方法是什么？

我想最明显的就是做这样的事情：

map.find(std::make_pair(str1, str2));

但这将导致在配对构建过程中对

str1

和

str2

字符串进行复制构建。

我希望也许

map.find(std::make_pair(std::ref(str1), std::ref(str2)));

可以提供帮助，但不幸的是没有，这仍然会产生字符串副本。

map.find(std::make_pair(std::move(str1), std::move(str2))

应该可以工作，但我们假设这些字符串 (

str1

,

str2

) 是 const 或者不应该移动。

所以我问是否有其他方法可以进行地图搜索而不进行多余的字符串副本？

（请注意，使用

std::string_view

代替

std::map key

不是一个选项，因为地图应该拥有其字符串。）

Answer 1

C++14 为

std::map::find

添加了以下重载，允许透明搜索：

template< class K >
const_iterator find( const K& x ) const;

要利用此功能，您仍然需要

std::map

拥有合适的比较器：

struct pair_less {
    // important for transparent comparison, see std::map:find documentation
    using is_transparent = std::true_type;

    template <typename T, typename U>
      requires pair_less_than_comparable<T, U> // C++20, see below
    bool operator()(const T& a, const U& b) const {
        if (a.first < b.first) return true;
        if (b.first < a.first) return false;
        return a.second < b.second;
    }
};

int main() {
    std::map<std::pair<std::string, std::string>, int, pair_less> m { /* ... */ };
    // ...
    std::string a = "a", b = "b";
    // now works and creates no copies
    auto pos = m.find(std::make_pair(std::ref(a), std::ref(b)));
}

这个

pair_less

是完全透明的。 它可以直接比较

std::pair<X, Y>

与

std::pair<const X&, const Y&>

。

注意

std::pair::operator<

自 LWG Defect 3865

 起，C++ 标准要求 

std::pair::operator< 保持透明。 理论上，这将使

std::less<void>

或

std::ranges::less

足以作为透明比较器。

但是，在撰写本文时，libstdc++ 尚未实现透明的

std::pair

比较，因此

std::less<void>

只适用于 GCC 以外的编译器。

正确的 C++20 约束

正确限制

pair_less

的呼叫操作员并不那么容易。 无论如何，这并不是绝对必要的，但会将错误转移到操作员的调用站点，并且可能更适合诊断。

通常的方法类似于

template <typename T, typename U>
concept pair_less_than_comparable
  = requires (const T& t, const U& u) {
      { t.first < u.first } -> /* boolean-testable */;
      { t.second < u.second } -> /* boolean-testable */;
  }

另请参阅

boolean-testable

。

Answer 2

为了避免密钥构造，您可以将

std::map

与透明比较器一起使用。在许多情况下，您不需要实现自己的标准 - 标准提供了

std::less<>

来完成这项工作。

不幸的是，它不适用于

std::pair

键，因为

std::pair

缺乏异构比较：您无法将

std::pair<std::string, std::string>

与

std::pair<const std::string&, const std::string&>

进行比较。

但是如果你可以将

std::pair

更改为

std::tuple

，它就会起作用：

std::map<std::tuple<std::string, std::string>, int, std::less<>> map;
// ...
auto pos = map.find(std::make_tuple(std::cref(str1), std::cref(str2)));