Here is eventually a working proposal.

Compared to the unordered container approach we need to find out what 
type is going to be used to call the comparer. Otherwise we might 
reinstantiate a temporary each time we call the comparer. For example in 
case of const char* insertion with a less<string_view> comparer we would 
create a string_view instance on each comparer call and so each time do 
a strlen.

This code is tricky and do not cover all use cases. For those uncovered 
cases the default behavior is to create a key_type instance which will 
be moved to storage if needed.

Is there any plan to create a builtin function to get help from the 
compiler to find out this type ? Something like std::invoke_result but 
giving also the actual argument types.

     libstdc++: [_Rb_tree] Limit allocations on unique insertions [PR 96088]

     Detect when invoking the comparer requires an allocation using the 
noexcept
     qualification of the functor. In this case guess the type needed to 
invoke
     the comparer and create a temporary instance used for all comparer 
invocations.
     This temporary instance will be eventually moved to storage 
location if it is to
     insert. Avoid to allocate a node and construct the stored value 
otherwise.

     libstdc++-v3/ChangeLog:

             PR libstdc++/96088
             * include/bits/stl_function.h
             (std::less<>::operator()): Add noexcept qualification.
             (std::greater::operator()): Likewise.
(std::_Identity<>::operator<_Tp2>(_Tp2&&)): New perfect forwarding operator.
(std::_Select1st<>::operator<_Pair2>(_Pair2&&)): New move operator.
             * include/bits/stl_tree.h 
(_Rb_tree<>::_ConvertToValueType<>): New helper type.
             (_Rb_tree<>::__has_firstargument): Likewise.
             (_Rb_tree<>::_S_get_key_type_aux): New helper method, use 
latter.
             (_Rb_tree<>::_S_get_key_type): New helper method, use latter.
             (_Rb_tree<>::__key_type_t): New.
             (_Rb_tree<>::__is_comparable_lhs): New.
             (_Rb_tree<>::__is_comparable_rhs): New.
             (_Rb_tree<>::__is_comparable): New, use latters.
             (_Rb_tree<>::__is_nothrow_comparable_lhs): New.
             (_Rb_tree<>::__is_nothrow_comparable_rhs): New.
             (_Rb_tree<>::__is_nothrow_comparable): New, use latters.
             (_Rb_tree<>::_S_forward_key): New.
             (_Rb_tree<>::_M_get_insert_unique_pos_tr): New.
             (_Rb_tree<>::_M_emplace_unique_kv): New.
             (_Rb_tree<>::_M_emplace_unique_aux): New, use latter.
             (_Rb_tree<>::_M_emplace_unique): New, use latter.
             (_Rb_tree<>::_Auto_node::_S_build): New.
             * testsuite/23_containers/map/96088.cc: New test case.
             * testsuite/23_containers/multimap/96088.cc: New test case.
             * testsuite/23_containers/multiset/96088.cc: New test case.
             * testsuite/23_containers/set/96088.cc: New test case.

François