libstdc++: [_Hashtable] Prefer to insert after last node

     When inserting an element into an empty bucket we currently insert 
the new node
     after the before-begin node so in first position. The drawback of 
doing this is
     that we are forced to update the bucket that was containing this 
before-begin
     node to point to the newly inserted node. To do so we need at best 
to do a modulo
     to find this bucket and at worst, when hash code is not cached, 
also compute it.

     To avoid this side effect it is better to insert after the last 
node. To do so
     we are introducing a helper type _HintPolicy that have 3 
resposibilities.

     1. When the gnu versioned namespace is used we add a _M_last member 
to _Hashtable,
     _HintPolicy is then in charge of maintaining it. For this purpose 
_HintPolicy is
     using the RAII pattern, it resets the _M_last at destruction level. 
It also maintain
     its own _M_last, all mutable operations are updating it when needed.

     2. When the gnu versioned namespace is not used _HintPolicy will 
still maintain its
     _M_last member using initially the user provided hint if any and if 
it is actually
     the container last node that is to say a dereferenceable node with 
its next node being
     null. All mutable operations can also update the contextual 
_HintPolicy instance
     whenever they detect the last node during their process.

     3. As long as we haven't been able to detect the container last 
node _HintPolicy
     is used to keep a cache of the before-begin bucket index so that we 
do not need to
     compute it afterward for example in the context of range insertion.

     libstdc++-v3/ChangeLog:

             * include/bits/hashtable.h
[_GLIBCXX_INLINE_VERSION](_Hashtable<>::_M_last): New, the container 
last node.
             (_Hashtable<>::_HintPolicy): New.
             (_Hashtable<>::_M_get_hint(__node_ptr)): New.
             (_Hashtable<>::_M_get_hint_policy(__node_ptr)): New.
(_Hashtable<>::_M_check_for_last(__node_base_ptr)): New.
             (_Hashtable<>::_M_set_last(__node_ptr)): New.
             (_Hashtable<>::_M_get_last()): New.
             (_Hashtable<>::_M_compute_hash_code(__node_ptr, const 
key_type&)): Remove.
             (_Hashtable<>::_InsertInfo): New struct.
             (_Hashtable<>::_M_get_insert_info): New, return latter.
(_Hashtable<>::operator=(initializer_list<>)): Adapt to instantiate a 
_HintPolicy.
             (_Hashtable<>::_M_insert_bucket_begin): Add _HintPolicy& 
parameter and use it
             to optimize insertion in an empty bucket.
             (_Hashtable<>::_M_insert_unique_node): Add _HintPolicy& 
parameter.
             (_Hashtable<>::_M_insert_multi_node): Likewise and add 
_InsertInfo parameter.
(_Hashtable<>::_M_emplace_unique(_HintPolicy&, _Args&&...)): New.
(_Hashtable<>::_M_emplace_multi(_HintPolicy&, _Args&&...)): New.
             (_Hashtable<>::_M_emplace): Adapt to use latters.
             (_Hashtable<>::_M_insert_unique): Add _HintPolicy& parameter.
             (_Hashtable<>::_M_insert_unique_aux): Add _HintPolicy& 
parameter.
             (_Hashtable<>::_M_insert): Adapt to use latter.
             (_Hashtable<>::emplace_hint(const_iterator, _Args&&...)): 
Adapt.
             (_hashtable<>::rehash(size_type)): Adapt.
             (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):
             Add hint parameter, adapt to use it for _HintPolicy 
instantiation.
             (_Hashtable<>::_M_reinsert_node_multi): Likewise.
             (_Hashtable<>::_M_merge_unique): Adapt.
             (_Hashtable<>::_M_rehash): Add _HintPolicy& parameter.
             (_Hashtable<>::_Hashtable<_InputIte>()): Adapt.
             (_Hashtable<>::_M_assign): Call _M_set_last.
             (_Hashtable<>::_M_reset()): Reset _M_last.
(_Hashtable<>::_M_move_assign(_Hashtable&&, true_type)): Move _M_last.
             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, 
true_type)): Copy _M_last.
             (_Hashtable<>(_Hashtable&&, __node_alloc_type&&, 
false_type)): Copy _M_last.
             (_Hashtable<>::_M_insert_range): Adapt.
             (_Hashtable<>::_M_erase): Call _M_check_for_last.
             (_Hashtable<>::erase): Likewise.
             * include/bits/hashtable_policy.h:
             (_Map_base<>::operator[](const key_type&)): Use hint policy.
             (_Map_base<>::operator[](key_type&&)): Likewise.
             (_Insert_base<>::insert(const_iterator, const 
value_type&)): Likewise using hint.
             (_Insert_base<>::try_emplace): Likewise.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, true_type)): 
Use hint policy.
(_Insert_base<>::_M_insert_range<>(_InputIte, _InputIte, false_type)): 
Use hint policy.
             (_Insert<>::insert(const_iterator, value_type&&)): Likewise.
             * include/bits/unordered_map.h 
(unordered_map<>::insert(node_type&&)): Pass cend as
             hint.
             (unordered_map<>::insert(const_iterator, node_type&&)): 
Adapt to use hint.
             * include/bits/unordered_set.h 
(unordered_set<>::insert(node_type&&)): Pass cend as
             hint.
             (unordered_set<>::insert(const_iterator, node_type&&)): 
Adapt to use hint.
             * 
testsuite/23_containers/unordered_multimap/insert/hint.cc: Adapt 
implementation
             specific tests.

Tested under Linux x64

Ok to commit ?

François