如果存在
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
不是一个选项,因为地图应该拥有其字符串。)
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<
起,C++ 标准要求
std::pair::operator<
保持透明。
理论上,这将使 std::less<void>
或 std::ranges::less
足以作为透明比较器。
std::pair
比较,因此 std::less<void>
只适用于 GCC 以外的编译器。
正确限制
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
。
为了避免密钥构造,您可以将
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)));