libstdc++: [_Hashtable] Make more use of insertion hint Make use of the user provided hint iterator in unordered containers operations. Hint is used: - As a hint for allocation to potentially reduce memory fragmentation. - For unordered_set/unordered_map we check if it does not match the key of the element to insert, before computing the hash code. - For unordered_multiset/unordered_multimap, if equals to the key of the element to insert, the hash code is taken from the hint so that we can take advantage of the potential hash code cache. libstdc++-v3/ChangeLog:     * include/bits/hashtable_policy.h (_NodeBuilder<>::_S_build): Add _NodePtr template     parameter.     (_ReuseOrAllocNode::operator()): Add __node_ptr parameter.     (_AllocNode::operator()): Likewise.     (_Insert_base::try_emplace): Adapt to use hint.     (_Hashtable_alloc<>::_M_allocate_node(__node_ptr, _Args&&...)): Add __node_ptr parameter.     * include/bits/hashtable.h     (_Hashtable<>::_Scope_node<>(__hashtable_alloc*, __node_ptr, _Args&&...)):     Add __node_ptr parameter.     (_Hashtable<>::_M_get_hint(size_type, __node_ptr)): New.     (_Hashtable<>::_M_emplace_unique(const_iterator, _Args&&...)): New.     (_Hashtable<>::_M_emplace_multi(const_iterator, _Args&&...)): New.     (_Hashtable<>::_M_emplace()): Adapt to use latter.     (_Hashtable<>::_M_insert_unique): Add const_iterator parameter.     (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const _NodeGenerator&, true_type)):     Use latter.     (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):     Add const_iterator parameter, adapt to use it.     (_Hashtable<>::_M_reinsert_node_multi): Make more use of hint parameter.     * 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. Tested under Linux x86_64. François