Transparent search for a std::map with a std::pair as a key

Question

If there is a std::map<std::pair<std::string, std::string>, some_type> what is the best way to find its values?

I guess the most obvious one is to do something like this: map.find(std::make_pair(str1, str2)); but this will lead to a copy-construction of the str1 and str2 strings during the pair construction.

I hoped that maybe map.find(std::make_pair(std::ref(str1), std::ref(str2))); could help, but unfortunately no, this still produces string copies.

map.find(std::make_pair(std::move(str1), std::move(str2)) should work but let's assume that these strings (str1, str2) are const or should not be moved.

So I'm asking whether there is any other way to do a the map search without making redundant string copies?

(Note that using std::string_view for the std::map key is NOT an option since the map should own its strings.)

Answer 1

C++14 added the following overload for std::map::find which allows transparent search:

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

To make use of this, you still need the std::map to have a suitable comparator:

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

This pair_less is totally transparent. It can directly compare std::pair<X, Y> to std::pair<const X&, const Y&>.

Note on std::pair::operator<

The C++ standard requires std::pair::operator< to be transparent since LWG Defect 3865. Theoretically, this would make std::less<void> or std::ranges::less sufficient as a transparent comparator.

However, libstdc++ does not yet implement transparent std::pair comparisons at the time of writing, so std::less<void> would only work for compilers other than GCC.

Proper C++20 constraints

Properly constraining the call operator of pair_less is not so easy. It's not strictly necessary anyway, but moves the error to the call site of the operator and may be better for diagnostics.

The usual approach would be something along the lines of

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 */;
  }

See also boolean-testable.

Answer 2

To avoid key construction, you can use std::map with a transparent comparator. In many cases you don't need to implement your own one - the standard provides std::less<> that does the job.

Unfortunately, it won't work with std::pair keys because std::pair lacks heterogeneous comparisons: you can't compare std::pair<std::string, std::string> to std::pair<const std::string&, const std::string&>.

But if you could change std::pair to std::tuple, it will work:

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

Answer 3

Even though you can't have std::string_view keys, you can still use std::string_view for your comparator (since you can easily convert a 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 was used instead of std::pair because you can convert pair -> tuple, but not the reverse. This means you can use tuple keys as well, which have handy factory functions:

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

Two compares were used instead of l < r because the pre-C++20 tuple's operator< would result in three memcmps instead of two (l[0] < r[0]; r[0] < l[0]; l[1] < r[1]. These do not seem to be optimized out).