On Wed, 22 Feb 2023 at 06:06, François Dumont via Libstdc++ <libstd...@gcc.gnu.org> wrote: > > 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.
That's what std::less<void> is for. I don't think we need to spend time trying to solve the problem against for std::less<T> when std::less<void> already exists. If the concern is strings vs const char*, we could explore your suggestion in https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088#c1 (keeping https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96088#c4 in mind) so that we optimize that specific case. > 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. Yes, it's tricky, and don't handle all cases, but slows down compilation for all cases. Also, I think you'll get ambiguous overloads for a comparison type that has both first_argument_type and is_transparent defined, because it will match two overloads. I don't think we should be recreating the logic of transparent comparison functions, and we shouldn't be reintroducing dependencies on first_argument_type (in C++20 users should be able to use that typedef for anything, e.g. make it a typedef for void, and the library shouldn't care ... I think that would break with your patch). > 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. No, I don't think so. > > 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
