Heterogeneous lookup comparator

Question

We have got heterogeneous lookup in C++14. I wonder why was the default comparator for map, set etc. not changed to less<>. Without this change average C++ user misses this feature completely and the performance penalty when looking for const char* in set<string> is still there. I have seen this pattern too many times in my company's codebase. Even MS showed this was a real perf bottleneck in one of its GoingNative videos. I can suspect the breaking of code was the issue but I don't see how it could happen for code which already worked in c++98/11

Answer 1

Consider:

struct Foo { bool operator<(const Foo&) const;};
struct Bar { operator Foo() const; };

std::set<Foo> s;
Bar b;
s.find(b);

By default, s uses std::less<Foo>, and s.find() takes a const Foo &, so the lookup constructs one temporary Foo from the Bar and uses it for all comparisons.

In contrast, if s were changed to the transparent comparison functor std::less<>, then in combination with heterogeneous lookup each comparison in find() will be between a Foo and a Bar, so each comparison will construct a temporary Foo. This is a silent performance degradation.