Cannot use user-provided comparison function for std::set>

Question

I stumbled upon very strange compile error for std::set using transparent comparators with help of std::less. Consider this simple program:

using Key = std::string;

bool operator<(const Key&, int) { return true; }
bool operator<(int, const Key&) { return true; }

int main()
{
  std::set<Key, std::less<>> s;
  int x;
  auto it = s.find(x);
}

It gives me compile error:

error: no matching function for call to object of type 'const std::less<void>'
      if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
                          ^~~~~~~~~~~~~~~~~~~~~~

If I use my own class instead of std::string as a key, it works fine:

struct My {};
bool operator<(const My&, const My&) { return true; }

using Key = My;

Why it does not work for std::string?

See the demo here: https://gcc.godbolt.org/z/MY-Y2s

UPD

What I really wanted to do, is to declare comparison operators between std::unique_ptr<T> and T*. But I thought it would be clearer with std::string.

Answer 1

Argument-dependent lookup's a funny old thing, isn't it?

There already exists a operator< relating to std::string in the namespace std, and this is found when looking for a < that fits your arguments. Perhaps counter-intuitively (but not without good reason), no further lookup is attempted after that! Other namespaces are not searched. That's even though only your overload actually matches both arguments. Your global operator< is effectively hidden in this context, as shown in the following horrendous example:

namespace N
{
    struct Foo {};

    bool operator<(Foo, Foo) { return false; }
}

bool operator<(N::Foo, int) { return false; }

namespace N
{
    template <typename T1, typename T2>
    bool less(T1 lhs, T2 rhs)
    {
        return lhs < rhs;
    }
}

int main()
{
    N::Foo f;
    N::less(f, 3);
}

/*
main.cpp: In instantiation of 'bool N::less(T1, T2) [with T1 = N::Foo; T2 = int]':
main.cpp:22:17:   required from here
main.cpp:15:20: error: no match for 'operator<' (operand types are 'N::Foo' and 'int')
         return lhs < rhs;
                ~~~~^~~~~
*/

(live demo)

Now, you can't add things to the namespace std, but that's fine because it would be vastly better if you didn't overload operators relating to other peoples' types anyway. That is the quickest way to hidden ODR bugs when some other library does the same thing.

Similarly, creating something called Key that is actually just std::string in disguise is a recipe for unintended conflicts and unexpected behaviours.

Overall I would strongly suggest making your Key at least a "strong alias" for std::string; that is, its own type rather than simply an alias. As you've found out, that also solves your problem because now the operator< and the operand type are in the same namespace.

More generally, if you are not really using an alias here but do indeed want to operate on standard types, you are back to writing a named custom comparator, which isolates the new logic very nicely and is also pretty much trivial to use. The downside of course is that you have to "opt-in" to it every time, but I think it's way worth it overall.