Following submission of the heterogeneous lookup in unordered containers I rebased this patch on top of it. Appart from reducing its size because of some code reuse the heterogeneous lookup had no impact on this one. This is because when I cannot find out if conversion from inserted element type to hash functor can throw then I pass the element as-is, like if hash functor was transparent.     libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088]     Detect Hash functor argument type to find out if it is different to the     container key_type and if a temporary instance needs to be generated to invoke     the functor from the iterator value_type key part. If this temporary generation     can throw a key_type instance is generated at Hashtable level and used to call     the functors and, if necessary, moved to the storage.     libstdc++-v3/ChangeLog:             PR libstdc++/96088             * include/bits/hashtable_policy.h (_Select2nd): New.             (_NodeBuilder<>): New.             (_ReuseOrAllocNode<>::operator()): Use variadic template args.             (_AllocNode<>::operator()): Likewise.             (_Hash_code_base<>::_M_hash_code): Add _Kt template parameter.             (_Hashtable_base<>::_M_equals): Add _Kt template parameter.             * include/bits/hashtable.h             (_Hashtable<>::__node_builder_t): New.             (_Hashtable<>::_M_find_before_node): Add _Kt template parameter.             (_Hashtable<>::_M_find_node): Likewise.             (_Hashtable<>::_Hash_arg_t): New.             (_Hashtable<>::_S_forward_key): New. (_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)):              New.             (_Hashtable<>::_M_insert): Use latter.             * testsuite/23_containers/unordered_map/96088.cc: New test.             * testsuite/23_containers/unordered_multimap/96088.cc: New test.             * testsuite/23_containers/unordered_multiset/96088.cc: New test.             * testsuite/23_containers/unordered_set/96088.cc: New test.             * testsuite/util/replacement_memory_operators.h             (counter::_M_increment): New.             (counter::_M_decrement): New.             (counter::reset()): New. Note that I plan to change counter type name to something more meaningful but only when back to stage 1. François On 24/10/20 4:25 pm, François Dumont wrote: > Hi > >     Just a rebase of this patch. > > François > > On 17/10/20 6:21 pm, François Dumont wrote: >> I eventually would like to propose the following resolution. >> >> For multi-key containers I kept the same resolution build the node >> first and compute has code from the node key. >> >> For unique-key ones I change behavior when I can't find out hash >> functor argument type. I am rather using the iterator key type and >> just hope that the user's functors are prepared for it. >> >> For now I am using functor argument_type which is deprecated. I just >> hope that the day we remove it we will have a compiler built-in to >> get any functor argument type given an input type. >> >>     libstdc++: Limit allocation on iterator insertion in Hashtable >> [PR 96088] >> >>     Detect Hash functor argument type to find out if it is different >> to the >>     container key_type and if a temporary instance needs to be >> generated to invoke >>     the functor from the iterator value_type key part. If this >> temporary generation >>     can throw a key_type instance is generated at Hashtable level and >> use to call >>     the functors and, if needed, move it to the storage. >> >>     libstdc++-v3/ChangeLog: >> >>             PR libstdc++/96088 >>             * include/bits/hashtable_policy.h (_Select2nd): New. >>             (_NodeBuilder<>): New. >>             (_ReuseOrAllocNode<>::operator()): Use varriadic template >> args. >>             (_AllocNode<>::operator()): Likewise. >>             (_Hash_code_base<>::_M_hash_code): Add _KType template >> parameter. >>             (_Hashtable_base<>::_M_equals): Add _KType template >> parameter. >>             * include/bits/hashtable.h >>             (_Hashtable<>::__node_builder_t): New. >>             (_Hashtable<>::_M_find_before_node): Add _KType template >> parameter. >>             (_Hashtable<>::_M_find_node): Likewise. >>             (_Hashtable<>::_Hash_arg_t): New. >>             (_Hashtable<>::_S_forward_key): New. >> (_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const >> _NodeGenerator&)): >>              New. >>             (_Hashtable<>::_M_insert): Use latter. >>             * testsuite/23_containers/unordered_map/96088.cc: New test. >>             * testsuite/23_containers/unordered_multimap/96088.cc: >> New test. >>             * testsuite/23_containers/unordered_multiset/96088.cc: >> New test. >>             * testsuite/23_containers/unordered_set/96088.cc: New test. >>             * testsuite/util/replacement_memory_operators.h >>             (counter::_M_increment): New. >>             (counter::_M_decrement): New. >>             (counter::reset()): New. >> >> Tested under Linux x86_64. >> >> Ok to commit ? >> >> François >> >> On 01/09/20 2:36 pm, François Dumont wrote: >>> Hi >>> >>>     I started working on PR96088 problem in Hashtable implementation. >>> >>>     In the case of multi-key containers the problem is easy to >>> manage. Now that we have _Scoped_node we can easily allocate the >>> node first and then extract the key from it to compute hash code. It >>> is quite safe as computating a hash code is rarely going to throw >>> especially if there is no allocation anymore to invoke the hasher. >>> >>>     In the unique-key case it is more tricky. First I only consider >>> the hasher invocation, the equal_to shall be consistent with it. My >>> approach is to consider that if the operation needed transform the >>> inserted element key part into the hasher argument can throw then I >>> better generate a key_type instance myself and move it to the node >>> if it is eventually to be inserted. Note that any allocation needed >>> to call the hasher from the key_type is user fault. >>> >>>     Of course the tricky part here is to find out what is the hasher >>> argument_type. For the moment I support hasher with a nested >>> argument_type typedef and function pointer. But, as pointed out by >>> the tests which are failing for the moment I am missing the support >>> for a classic functor. I am pretty sure that if I support it I will >>> still be missing some use cases (like std::function). So I am >>> looking for help on how to determine it. Or maybe the whole approach >>> it wrong ? >>> >>> For now I am still working on it, thanks, >>> >>> François >>> >> >