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