主页 / coding / 问题 / 77813605
Accepted
Voivoid
Asked: 2024-01-14 08:48:39 +0800 CST

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

  • 772

如果存在std::map<std::pair<std::string, std::string>, some_type>找到其值的最佳方法是什么？

我想最明显的一个是做这样的事情： 但这将导致在对构造期间对和字符串map.find(std::make_pair(str1, str2)); 进行复制构造。str1str2

我希望也许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_viewforstd::map key不是一个选项，因为地图应该拥有其字符串。）

c++

3 个回答

  1. Best Answer

    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

    std::pair然而，在撰写本文时，libstdc++ 尚未实现透明比较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。

    • 12

  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)));
    • 7

  3. 即使您没有std::string_view密钥，您仍然可以用于std::string_view比较器（因为您可以轻松转换std::string-> std::string_view）：

    struct string_pair_comparator {
    constexpr bool operator()(std::tuple<std::string_view, std::string_view> l, std::tuple<std::string_view, std::string_view> r) const noexcept {
#ifdef __cpp_lib_three_way_comparison
        auto cmp = l <=> r;
#else
        auto cmp = std::get<0>(l).compare(std::get<0>(r));
        if (cmp == 0) cmp = std::get<1>(l).compare(std::get<1>(r));
#endif
        return cmp < 0;
    }

    using is_transparent = void;
};

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

    std::tuple使用而不是std::pair因为您可以转换pair-> tuple，但反之则不行。这意味着您也可以使用元组键，它具有方便的工厂功能：

    map.find(std::tie(str1, str2))
map.find(std::forward_as_tuple(str1, str2))
// pairs also still work
map.find(std::make_pair(std::ref(str1), std::ref(str2)))

    compare使用两个而不是l < r因为 C++20 之前的元组operator<将导致三个memcmp而不是两个（l[0] < r[0]; r[0] < l[0]; l[1] < r[1]。这些似乎没有被优化）。

    • 0

相关问题