[Hashtable,0/6] Code review

Message ID d98f7478-6976-e1f5-758f-dac32a128869@gmail.com
State New
Headers show

Commit Message

François Dumont Nov. 17, 2019, 8:42 p.m.
This is the begining of a patch series for _Hashtable

Initial patch to clarify code. I was tired to see true/false or 
true_type/false_type without knowing what was true/false.

I also made code more consistent by chosing to specialize methods 
through usage of __unique_keys_t/__multi_keys_t rather than calling them 
_M_[multi]_XXX.


     * include/bits/hashtable_policy.h (__detail::__unique_keys_t): New.
     (__detail::__multi_keys_t): New.
     (__detail::__constant_iterators_t): New.
     (__detail::__mutable_iterators_t): New.
     (__detail::__hash_cached_t): New.
     (__detail::__hash_not_cached_t): New.
     (_Hash_node<>): Change _Cache_hash_code template parameter from bool to
     typename. Adapt partial specializations.
     (_Node_iterator_base<>): Likewise.
     (operator==(const _Node_iterator_base<>&,const 
_Node_iterator_base<>&)):
     Adapt.
     (operator!=(const _Node_iterator_base<>&,const 
_Node_iterator_base<>&)):
     Adapt.
     (_Node_iterator<>): Change __constant_iterators and __cache template
     parameters from bool to typename.
     (_Node_const_iterator<>): Likewise.
     (_Map_base<>): Change _Unique_keys template parameter from bool to
     typename. Adapt partial specializations.
     (_Insert<>): Change _Constant_iterators template parameter from bool to
     typename. Adapt partial specializations.
     (_Local_iterator_base<>): Change __cache_hash_code template parameter
     from bool to typename. Adapt partial specialization.
     (_Hash_code_base<>): Likewise.
     (operator==(const _Local_iterator_base<>&,
     const _Local_iterator_base<>&)): Adapt.
     (operator!=(const _Local_iterator_base<>&,
     const _Local_iterator_base<>&)):
     Adapt.
     (_Local_iterator<>): Change __constant_iterators and __cache template
     parameters from bool to typename.
     (_Local_const_iterator<>): Likewise.
     (_Hashtable_base<>): Adapt.
     (_Equal_hash_code<>): Adapt.
     (_Equality<>): Adapt.
     * include/bits/hashtable.h (_Hashtable<>): Replace occurences of
     true_type/false_type by respoectively __unique_type_t/__multi_type_t.
     (_M_insert_unique_node(const key_type&, size_t, __hash_code,
     __node_type*, size_t)): Replace by...
     (_M_insert_node(__unique_keys_t, size_t, __hash_code, __node_type*,
     size_t)): ...this.
     (_M_insert_muti_node(__node_type*, const key_type&, __hash_code,
     __node_type*)): Replace by...
     (_M_insert_node(__multi_keys_t, __node_type*, __hash_code,
     __node_type*)): ...this.
     (_M_reinsert_node(node_type&&)): Replace by...
     (_M_reinsert_node(node_type&&, __unique_keys_t)): ...this.
     (_M_reinsert_node(const_iterator, node_type&&, __unique_keys_t)): New,
     forward to latter.
     (_M_reinsert_node_multi(const_iterator, node_type&&)): Replace by...
     (_M_reinsert_node(const_iterator, node_type&&, __multi_keys_t)):
     ...this.
     (_M_reinsert_node(node_type&&, __multi_keys_t)): New, forward to 
latter.
     (_M_reinsert_node(node_type&&)): New, use latters.
     (_M_reinsert_node(const_iterator, node_type&&)): Likewise.
     (_M_merge_unique(_Compatible_Hashtable&)): Replace by...
     (_M_merge(__unique_keys_t, _Compatible_Hashtable&)): ...this.
     (_M_merge_multi(_Compatible_Hashtable&)): Replace by...
     (_M_merge(__multi_keys_t, _Compatible_Hashtable&)): ...this.
     (_M_merge(_Compatible_Hashtable&)): New, use latters.
     * include/bits/unordered_map.h
     (unordered_map<>::insert(const_iterator, node_type&&)): Adapt.
     (unordered_map<>::merge(unordered_map<>&)): Adapt.
(unordered_map<>::merge(unordered_multimap<>&)): Adapt.
     (unordered_multimap<>::insert(node_type&&)): Adapt.
     (unordered_multimap<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_multimap<>::merge(unordered_multimap<>&)): Adapt.
(unordered_multimap<>::merge(unordered_map<>&)): Adapt.
     * include/bits/unordered_set.h
     (unordered_set<>::insert(const_iterator, node_type&&)): Adapt.
     (unordered_set<>::merge(unordered_set<>&)): Adapt.
(unordered_set<>::merge(unordered_multiset<>&)): Adapt.
     (unordered_multiset<>::insert(node_type&&)): Adapt.
     (unordered_multiset<>::insert(const_iterator, node_type&&)): Adapt.
(unordered_multiset<>::merge(unordered_multiset<>&)): Adapt.
(unordered_multiset<>::merge(unordered_set<>&)): Adapt.

Tested under Linux x86_64.

François

Comments

François Dumont Dec. 9, 2019, 9:15 p.m. | #1
This patch also require an update of the printers.py file.

Here is an updated version.

François

On 11/17/19 9:42 PM, François Dumont wrote:
> This is the begining of a patch series for _Hashtable

>

> Initial patch to clarify code. I was tired to see true/false or 

> true_type/false_type without knowing what was true/false.

>

> I also made code more consistent by chosing to specialize methods 

> through usage of __unique_keys_t/__multi_keys_t rather than calling 

> them _M_[multi]_XXX.

>

>

>     * include/bits/hashtable_policy.h (__detail::__unique_keys_t): New.

>     (__detail::__multi_keys_t): New.

>     (__detail::__constant_iterators_t): New.

>     (__detail::__mutable_iterators_t): New.

>     (__detail::__hash_cached_t): New.

>     (__detail::__hash_not_cached_t): New.

>     (_Hash_node<>): Change _Cache_hash_code template parameter from 

> bool to

>     typename. Adapt partial specializations.

>     (_Node_iterator_base<>): Likewise.

>     (operator==(const _Node_iterator_base<>&,const 

> _Node_iterator_base<>&)):

>     Adapt.

>     (operator!=(const _Node_iterator_base<>&,const 

> _Node_iterator_base<>&)):

>     Adapt.

>     (_Node_iterator<>): Change __constant_iterators and __cache template

>     parameters from bool to typename.

>     (_Node_const_iterator<>): Likewise.

>     (_Map_base<>): Change _Unique_keys template parameter from bool to

>     typename. Adapt partial specializations.

>     (_Insert<>): Change _Constant_iterators template parameter from 

> bool to

>     typename. Adapt partial specializations.

>     (_Local_iterator_base<>): Change __cache_hash_code template parameter

>     from bool to typename. Adapt partial specialization.

>     (_Hash_code_base<>): Likewise.

>     (operator==(const _Local_iterator_base<>&,

>     const _Local_iterator_base<>&)): Adapt.

>     (operator!=(const _Local_iterator_base<>&,

>     const _Local_iterator_base<>&)):

>     Adapt.

>     (_Local_iterator<>): Change __constant_iterators and __cache template

>     parameters from bool to typename.

>     (_Local_const_iterator<>): Likewise.

>     (_Hashtable_base<>): Adapt.

>     (_Equal_hash_code<>): Adapt.

>     (_Equality<>): Adapt.

>     * include/bits/hashtable.h (_Hashtable<>): Replace occurences of

>     true_type/false_type by respoectively __unique_type_t/__multi_type_t.

>     (_M_insert_unique_node(const key_type&, size_t, __hash_code,

>     __node_type*, size_t)): Replace by...

>     (_M_insert_node(__unique_keys_t, size_t, __hash_code, __node_type*,

>     size_t)): ...this.

>     (_M_insert_muti_node(__node_type*, const key_type&, __hash_code,

>     __node_type*)): Replace by...

>     (_M_insert_node(__multi_keys_t, __node_type*, __hash_code,

>     __node_type*)): ...this.

>     (_M_reinsert_node(node_type&&)): Replace by...

>     (_M_reinsert_node(node_type&&, __unique_keys_t)): ...this.

>     (_M_reinsert_node(const_iterator, node_type&&, __unique_keys_t)): 

> New,

>     forward to latter.

>     (_M_reinsert_node_multi(const_iterator, node_type&&)): Replace by...

>     (_M_reinsert_node(const_iterator, node_type&&, __multi_keys_t)):

>     ...this.

>     (_M_reinsert_node(node_type&&, __multi_keys_t)): New, forward to 

> latter.

>     (_M_reinsert_node(node_type&&)): New, use latters.

>     (_M_reinsert_node(const_iterator, node_type&&)): Likewise.

>     (_M_merge_unique(_Compatible_Hashtable&)): Replace by...

>     (_M_merge(__unique_keys_t, _Compatible_Hashtable&)): ...this.

>     (_M_merge_multi(_Compatible_Hashtable&)): Replace by...

>     (_M_merge(__multi_keys_t, _Compatible_Hashtable&)): ...this.

>     (_M_merge(_Compatible_Hashtable&)): New, use latters.

>     * include/bits/unordered_map.h

>     (unordered_map<>::insert(const_iterator, node_type&&)): Adapt.

>     (unordered_map<>::merge(unordered_map<>&)): Adapt.

> (unordered_map<>::merge(unordered_multimap<>&)): Adapt.

>     (unordered_multimap<>::insert(node_type&&)): Adapt.

>     (unordered_multimap<>::insert(const_iterator, node_type&&)): Adapt.

> (unordered_multimap<>::merge(unordered_multimap<>&)): Adapt.

> (unordered_multimap<>::merge(unordered_map<>&)): Adapt.

>     * include/bits/unordered_set.h

>     (unordered_set<>::insert(const_iterator, node_type&&)): Adapt.

>     (unordered_set<>::merge(unordered_set<>&)): Adapt.

> (unordered_set<>::merge(unordered_multiset<>&)): Adapt.

>     (unordered_multiset<>::insert(node_type&&)): Adapt.

>     (unordered_multiset<>::insert(const_iterator, node_type&&)): Adapt.

> (unordered_multiset<>::merge(unordered_multiset<>&)): Adapt.

> (unordered_multiset<>::merge(unordered_set<>&)): Adapt.

>

> Tested under Linux x86_64.

>

> François

>
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index c2b2219d471..ef71c090f3b 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -184,7 +184,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       private __detail::_Hashtable_alloc<
 	__alloc_rebind<_Alloc,
 		       __detail::_Hash_node<_Value,
-					    _Traits::__hash_cached::value>>>
+					    typename _Traits::__hash_cached>>>
     {
       static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
 	  "unordered container must have a non-const, non-volatile value_type");
@@ -195,7 +195,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       using __traits_type = _Traits;
       using __hash_cached = typename __traits_type::__hash_cached;
-      using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
+      using __node_type = __detail::_Hash_node<_Value, __hash_cached>;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
 
       using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
@@ -224,6 +224,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using __rehash_type = _RehashPolicy;
       using __rehash_state = typename __rehash_type::_State;
 
+      using __unique_keys_t = __detail::__unique_keys_t;
+      using __multi_keys_t = __detail::__multi_keys_t;
+
       using __constant_iterators = typename __traits_type::__constant_iterators;
       using __unique_keys = typename __traits_type::__unique_keys;
 
@@ -526,7 +529,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
 	_M_before_begin._M_nxt = nullptr;
 	clear();
-	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
+	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
 	return *this;
       }
 
@@ -709,73 +712,74 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __node_base*
       _M_get_previous_node(size_type __bkt, __node_base* __n);
 
-      // Insert node __n with key __k and hash code __code, in bucket __bkt
-      // if no rehash (assumes no element with same key already present).
+      // Insert node __n with hash code __code, in bucket __bkt if no
+      // rehash (assumes no element with same key already present).
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_unique_node(const key_type& __k, size_type __bkt,
-			    __hash_code __code, __node_type* __n,
-			    size_type __n_elt = 1);
+      _M_insert_node(__unique_keys_t, size_type __bkt, __hash_code,
+		     __node_type* __n, size_type __n_elt = 1);
 
       // Insert node __n with key __k and hash code __code.
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			   __hash_code __code, __node_type* __n);
+      _M_insert_node(__multi_keys_t, __node_type* __hint,
+		     __hash_code __code, __node_type* __n);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
-	_M_emplace(true_type, _Args&&... __args);
+	_M_emplace(__unique_keys_t, _Args&&... __args);
 
       template<typename... _Args>
 	iterator
-	_M_emplace(false_type __uk, _Args&&... __args)
-	{ return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
+	_M_emplace(__multi_keys_t __mks, _Args&&... __args)
+	{
+	  return _M_emplace(cend(), __mks,
+			    std::forward<_Args>(__args)...);
+	}
 
       // Emplace with hint, useless when keys are unique.
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, true_type __uk, _Args&&... __args)
-	{ return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
+	_M_emplace(const_iterator, __unique_keys_t __uks, _Args&&... __args)
+	{ return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
 
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, false_type, _Args&&... __args);
+	_M_emplace(const_iterator, __multi_keys_t, _Args&&... __args);
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
+	_M_insert(_Arg&&, const _NodeGenerator&, __unique_keys_t, size_type = 1);
 
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
-		  false_type __uk)
+		  __multi_keys_t __mks)
 	{
 	  return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
-			   __uk);
+			   __mks);
 	}
 
       // Insert with hint, not used when keys are unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&& __arg,
-		  const _NodeGenerator& __node_gen, true_type __uk)
+		  const _NodeGenerator& __node_gen, __unique_keys_t __uks)
 	{
-	  return
-	    _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
+	  return _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
 	}
 
       // Insert with hint when keys are not unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&&,
-		  const _NodeGenerator&, false_type);
+		  const _NodeGenerator&, __multi_keys_t);
 
       size_type
-      _M_erase(true_type, const key_type&);
+      _M_erase(__unique_keys_t, const key_type&);
 
       size_type
-      _M_erase(false_type, const key_type&);
+      _M_erase(__multi_keys_t, const key_type&);
 
       iterator
       _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
@@ -785,13 +789,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename... _Args>
 	__ireturn_type
 	emplace(_Args&&... __args)
-	{ return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
+	{ return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
 
       template<typename... _Args>
 	iterator
 	emplace_hint(const_iterator __hint, _Args&&... __args)
 	{
-	  return _M_emplace(__hint, __unique_keys(),
+	  return _M_emplace(__hint, __unique_keys{},
 			    std::forward<_Args>(__args)...);
 	}
 
@@ -808,7 +812,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       erase(const key_type& __k)
-      { return _M_erase(__unique_keys(), __k); }
+      { return _M_erase(__unique_keys{}, __k); }
 
       iterator
       erase(const_iterator, const_iterator);
@@ -824,9 +828,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // reserve, if present, comes from _Rehash_base.
 
 #if __cplusplus > 201402L
+    private:
       /// Re-insert an extracted node into a container with unique keys.
       insert_return_type
-      _M_reinsert_node(node_type&& __nh)
+      _M_reinsert_node(node_type&& __nh, __unique_keys_t __uks)
       {
 	insert_return_type __ret;
 	if (__nh.empty())
@@ -847,7 +852,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    else
 	      {
 		__ret.position
-		  = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr);
+		  = _M_insert_node(__uks, __bkt, __code, __nh._M_ptr);
 		__nh._M_ptr = nullptr;
 		__ret.inserted = true;
 	      }
@@ -855,9 +860,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __ret;
       }
 
+      /// Re-insert an extracted node into a container with unique keys.
+      insert_return_type
+      _M_reinsert_node(const_iterator, node_type&& __nh, __unique_keys_t __uks)
+      { return _M_reinsert_node(std::move(__nh), __uks); }
+
       /// Re-insert an extracted node into a container with equivalent keys.
       iterator
-      _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
+      _M_reinsert_node(node_type&& __nh, __multi_keys_t __mks)
+      { return _M_reinsert_node(cend(), std::move(__nh), __mks); }
+
+      iterator
+      _M_reinsert_node(const_iterator __hint, node_type&& __nh,
+		       __multi_keys_t __mks)
       {
 	if (__nh.empty())
 	  return end();
@@ -867,12 +882,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	const key_type& __k = __nh._M_key();
 	auto __code = this->_M_hash_code(__k);
 	auto __ret
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __nh._M_ptr);
 	__nh._M_ptr = nullptr;
 	return __ret;
       }
 
-    private:
       node_type
       _M_extract_node(size_t __bkt, __node_base* __prev_n)
       {
@@ -915,15 +929,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __nh;
       }
 
-      /// Merge from a compatible container into one with unique keys.
+      /// Re-insert an extracted node into a container.
+      auto
+      _M_reinsert_node(node_type&& __nh)
+	-> decltype(_M_reinsert_node(std::move(__nh), __unique_keys{}))
+      { return _M_reinsert_node(std::move(__nh), __unique_keys{}); }
+
+      /// Re-insert an extracted node into a container with hint.
+      auto
+      _M_reinsert_node(const_iterator __hint, node_type&& __nh)
+	-> decltype(_M_reinsert_node(__hint, std::move(__nh), __unique_keys{}))
+      { return _M_reinsert_node(__hint, std::move(__nh), __unique_keys{}); }
+
+      /// Merge from a compatible container.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_unique(_Compatible_Hashtable& __src) noexcept
+	_M_merge(_Compatible_Hashtable& __src) noexcept
 	{
 	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
+	  _M_merge(__unique_keys{}, __src);
+	}
+
+    private:
+      /// Merge from a compatible container into one with unique keys.
+      template<typename _Compatible_Hashtable>
+	void
+	_M_merge(__unique_keys_t __uks, _Compatible_Hashtable& __src) noexcept
+	{
 	  auto __n_elt = __src.size();
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
 	    {
@@ -934,8 +969,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      if (_M_find_node(__bkt, __k, __code) == nullptr)
 		{
 		  auto __nh = __src.extract(__pos);
-		  _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr,
-					__n_elt);
+		  _M_insert_node(__uks, __bkt, __code, __nh._M_ptr, __n_elt);
 		  __nh._M_ptr = nullptr;
 		  __n_elt = 1;
 		}
@@ -947,24 +981,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       /// Merge from a compatible container into one with equivalent keys.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_multi(_Compatible_Hashtable& __src) noexcept
+	_M_merge(__multi_keys_t __mks, _Compatible_Hashtable& __src) noexcept
 	{
-	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
-	      node_type>, "Node types are compatible");
-	  __glibcxx_assert(get_allocator() == __src.get_allocator());
-
 	  this->reserve(size() + __src.size());
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
-	    _M_reinsert_node_multi(cend(), __src.extract(__i++));
+	    _M_reinsert_node(cend(), __src.extract(__i++), __mks);
 	}
 #endif // C++17
 
     private:
       // Helper rehash method used when keys are unique.
-      void _M_rehash_aux(size_type __bkt_count, true_type);
+      void _M_rehash_aux(size_type __bkt_count, __unique_keys_t);
 
       // Helper rehash method used when keys can be non-unique.
-      void _M_rehash_aux(size_type __bkt_count, false_type);
+      void _M_rehash_aux(size_type __bkt_count, __multi_keys_t);
 
       // Unconditionally change size of bucket array to n, restore
       // hash policy state to __state on exception.
@@ -1251,7 +1281,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_move_assign(_Hashtable&& __ht, false_type)
     {
       if (__ht._M_node_allocator() == this->_M_node_allocator())
-	_M_move_assign(std::move(__ht), true_type());
+	_M_move_assign(std::move(__ht), true_type{});
       else
 	{
 	  // Can't move memory, move elements then.
@@ -1664,7 +1694,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_emplace(true_type, _Args&&... __args)
+      _M_emplace(__unique_keys_t __uks, _Args&&... __args)
       -> pair<iterator, bool>
       {
 	// First build the node to get access to the hash code
@@ -1677,7 +1707,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return std::make_pair(iterator(__p), false);
 
 	// Insert the node
-	auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -1690,7 +1720,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_emplace(const_iterator __hint, false_type, _Args&&... __args)
+      _M_emplace(const_iterator __hint, __multi_keys_t __mks, _Args&&... __args)
       -> iterator
       {
 	// First build the node to get its hash code.
@@ -1699,7 +1729,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	__hash_code __code = this->_M_hash_code(__k);
 	auto __pos
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -1711,9 +1741,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_unique_node(const key_type& __k, size_type __bkt,
-			  __hash_code __code, __node_type* __node,
-			  size_type __n_elt)
+    _M_insert_node(__unique_keys_t, size_type __bkt, __hash_code __code,
+		   __node_type* __node, size_type __n_elt)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1724,7 +1753,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__do_rehash.first)
 	{
 	  _M_rehash(__do_rehash.second, __saved_state);
-	  __bkt = _M_bucket_index(__k, __code);
+	  __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
 	}
 
       this->_M_store_code(__node, __code);
@@ -1742,8 +1771,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			 __hash_code __code, __node_type* __node)
+    _M_insert_node(__multi_keys_t, __node_type* __hint,
+		   __hash_code __code, __node_type* __node)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1754,6 +1783,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_rehash(__do_rehash.second, __saved_state);
 
       this->_M_store_code(__node, __code);
+      const key_type& __k = this->_M_extract()(__node->_M_v());
       size_type __bkt = _M_bucket_index(__k, __code);
 
       // Find the node before an equivalent one or use hint if it exists and
@@ -1797,8 +1827,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
-		size_type __n_elt)
+      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen,
+		__unique_keys_t __uks, size_type __n_elt)
       -> pair<iterator, bool>
       {
 	const key_type& __k = this->_M_extract()(__v);
@@ -1810,7 +1840,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
 	auto __pos
-	  = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt);
+	  = _M_insert_node(__uks, __bkt, __code, __node._M_node, __n_elt);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -1825,7 +1855,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(const_iterator __hint, _Arg&& __v,
-		const _NodeGenerator& __node_gen, false_type)
+		const _NodeGenerator& __node_gen, __multi_keys_t __mks)
       -> iterator
       {
 	// First compute the hash code so that we don't do anything if it
@@ -1836,7 +1866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
 	const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
 	auto __pos
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -1896,7 +1926,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_erase(true_type, const key_type& __k)
+    _M_erase(__unique_keys_t, const key_type& __k)
     -> size_type
     {
       __hash_code __code = this->_M_hash_code(__k);
@@ -1920,7 +1950,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_erase(false_type, const key_type& __k)
+    _M_erase(__multi_keys_t, const key_type& __k)
     -> size_type
     {
       __hash_code __code = this->_M_hash_code(__k);
@@ -2065,7 +2095,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __try
 	{
-	  _M_rehash_aux(__bkt_count, __unique_keys());
+	  _M_rehash_aux(__bkt_count, __unique_keys{});
 	}
       __catch(...)
 	{
@@ -2084,7 +2114,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_rehash_aux(size_type __bkt_count, true_type)
+    _M_rehash_aux(size_type __bkt_count, __unique_keys_t)
     {
       __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
       __node_type* __p = _M_begin();
@@ -2126,7 +2156,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_rehash_aux(size_type __bkt_count, false_type)
+    _M_rehash_aux(size_type __bkt_count, __multi_keys_t)
     {
       __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f5809c7443a..b9320506bb2 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -172,6 +172,14 @@ namespace __detail
 
   // Auxiliary types used for all instantiations of _Hashtable nodes
   // and iterators.
+  using __unique_keys_t = true_type;
+  using __multi_keys_t = false_type;
+
+  using __constant_iterators_t = true_type;
+  using __mutable_iterators_t = false_type;
+
+  using __hash_cached_t = true_type;
+  using __hash_not_cached_t = false_type;
 
   /**
    *  struct _Hashtable_traits
@@ -252,7 +260,7 @@ namespace __detail
   /**
    *  Primary template struct _Hash_node.
    */
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     struct _Hash_node;
 
   /**
@@ -261,7 +269,8 @@ namespace __detail
    *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
+    struct _Hash_node<_Value, __hash_cached_t>
+    : _Hash_node_value_base<_Value>
     {
       std::size_t  _M_hash_code;
 
@@ -276,7 +285,8 @@ namespace __detail
    *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
+    struct _Hash_node<_Value, __hash_not_cached_t>
+    : _Hash_node_value_base<_Value>
     {
       _Hash_node*
       _M_next() const noexcept
@@ -284,7 +294,7 @@ namespace __detail
     };
 
   /// Base class for node iterators.
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     struct _Node_iterator_base
     {
       using __node_type = _Hash_node<_Value, _Cache_hash_code>;
@@ -299,14 +309,14 @@ namespace __detail
       { _M_cur = _M_cur->_M_next(); }
     };
 
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     inline bool
     operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 	       const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
     noexcept
     { return __x._M_cur == __y._M_cur; }
 
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     inline bool
     operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 	       const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
@@ -314,12 +324,13 @@ namespace __detail
     { return __x._M_cur != __y._M_cur; }
 
   /// Node iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _Value, typename _Constant_iterators,
+	   typename _Cache_hash_code>
     struct _Node_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_Value, _Cache_hash_code>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_Value, _Cache_hash_code>;
       using __node_type = typename __base_type::__node_type;
 
     public:
@@ -327,10 +338,10 @@ namespace __detail
       typedef std::ptrdiff_t				difference_type;
       typedef std::forward_iterator_tag			iterator_category;
 
-      using pointer = typename std::conditional<__constant_iterators,
+      using pointer = typename std::conditional<_Constant_iterators::value,
 						const _Value*, _Value*>::type;
 
-      using reference = typename std::conditional<__constant_iterators,
+      using reference = typename std::conditional<_Constant_iterators::value,
 						  const _Value&, _Value&>::type;
 
       _Node_iterator() noexcept
@@ -365,12 +376,13 @@ namespace __detail
     };
 
   /// Node const_iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _Value, typename _Constant_iterators,
+	   typename _Cache_hash_code>
     struct _Node_const_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_Value, _Cache_hash_code>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_Value, _Cache_hash_code>;
       using __node_type = typename __base_type::__node_type;
 
     public:
@@ -388,8 +400,8 @@ namespace __detail
       _Node_const_iterator(__node_type* __p) noexcept
       : __base_type(__p) { }
 
-      _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
-			   __cache>& __x) noexcept
+      _Node_const_iterator(const _Node_iterator<_Value, _Constant_iterators,
+						_Cache_hash_code>& __x) noexcept
       : __base_type(__x._M_cur) { }
 
       reference
@@ -641,25 +653,25 @@ namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Unique_keys = _Traits::__unique_keys::value>
+	   typename = typename _Traits::__unique_keys>
     struct _Map_base { };
 
-  /// Partial specialization, __unique_keys set to false.
+  /// Partial specialization, keys are not unique.
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>
     {
       using mapped_type = typename std::tuple_element<1, _Pair>::type;
     };
 
-  /// Partial specialization, __unique_keys set to true.
+  /// Partial specialization, keys are unique.
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>
     {
     private:
       using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
@@ -699,7 +711,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     operator[](const key_type& __k)
     -> mapped_type&
     {
@@ -716,7 +728,7 @@ namespace __detail
 	std::tuple<>()
       };
       auto __pos
-	= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	= __h->_M_insert_node(__unique_keys_t{}, __bkt, __code, __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -726,7 +738,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     operator[](key_type&& __k)
     -> mapped_type&
     {
@@ -743,7 +755,7 @@ namespace __detail
 	std::tuple<>()
       };
       auto __pos
-	= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	= __h->_M_insert_node(__unique_keys_t{}, __bkt, __code, __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -753,7 +765,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     at(const key_type& __k)
     -> mapped_type&
     {
@@ -772,7 +784,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     at(const key_type& __k) const
     -> const mapped_type&
     {
@@ -810,10 +822,12 @@ namespace __detail
       using iterator = typename __hashtable_base::iterator;
       using const_iterator =  typename __hashtable_base::const_iterator;
       using size_type = typename __hashtable_base::size_type;
-
-      using __unique_keys = typename __hashtable_base::__unique_keys;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
-      using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>;
+
+      using __unique_keys = typename _Traits::__unique_keys;
+      using __hash_cached = typename _Traits::__hash_cached;
+
+      using __node_type = _Hash_node<_Value, __hash_cached>;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
       using __node_gen_type = _AllocNode<__node_alloc_type>;
 
@@ -824,12 +838,12 @@ namespace __detail
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, true_type);
+			const _NodeGetter&, __unique_keys_t);
 
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, false_type);
+			const _NodeGetter&, __multi_keys_t);
 
     public:
       __ireturn_type
@@ -837,7 +851,7 @@ namespace __detail
       {
 	__hashtable& __h = _M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(__v, __node_gen, __unique_keys());
+	return __h._M_insert(__v, __node_gen, __unique_keys{});
       }
 
       iterator
@@ -845,7 +859,7 @@ namespace __detail
       {
 	__hashtable& __h = _M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);	
-	return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
+	return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
       }
 
       void
@@ -858,7 +872,7 @@ namespace __detail
 	{
 	  __hashtable& __h = _M_conjure_hashtable();
 	  __node_gen_type __node_gen(__h);
-	  return _M_insert_range(__first, __last, __node_gen, __unique_keys());
+	  return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
 	}
     };
 
@@ -871,7 +885,7 @@ namespace __detail
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, true_type)
+		      const _NodeGetter& __node_gen, __unique_keys_t __uks)
       {
 	size_type __n_elt = __detail::__distance_fw(__first, __last);
 	if (__n_elt == 0)
@@ -880,8 +894,7 @@ namespace __detail
 	__hashtable& __h = _M_conjure_hashtable();
 	for (; __first != __last; ++__first)
 	  {
-	    if (__h._M_insert(*__first, __node_gen, __unique_keys(),
-			      __n_elt).second)
+	    if (__h._M_insert(*__first, __node_gen, __uks, __n_elt).second)
 	      __n_elt = 1;
 	    else if (__n_elt != 1)
 	      --__n_elt;
@@ -897,7 +910,7 @@ namespace __detail
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, false_type)
+		      const _NodeGetter& __node_gen, __multi_keys_t __mks)
       {
 	using __rehash_type = typename __hashtable::__rehash_type;
 	using __rehash_state = typename __hashtable::__rehash_state;
@@ -918,7 +931,7 @@ namespace __detail
 	  __h._M_rehash(__do_rehash.second, __saved_state);
 
 	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __unique_keys());
+	  __h._M_insert(*__first, __node_gen, __mks);
       }
 
   /**
@@ -931,7 +944,7 @@ namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Constant_iterators = _Traits::__constant_iterators::value>
+	   typename = typename _Traits::__constant_iterators>
     struct _Insert;
 
   /// Specialization.
@@ -940,7 +953,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, true>
+		   _RehashPolicy, _Traits, __constant_iterators_t>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
@@ -968,7 +981,7 @@ namespace __detail
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
+	return __h._M_insert(std::move(__v), __node_gen, __unique_keys{});
       }
 
       iterator
@@ -977,7 +990,7 @@ namespace __detail
 	__hashtable& __h = this->_M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
 	return __h._M_insert(__hint, std::move(__v), __node_gen,
-			     __unique_keys());
+			     __unique_keys{});
       }
     };
 
@@ -987,7 +1000,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, false>
+		   _RehashPolicy, _Traits, __mutable_iterators_t>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
@@ -1018,7 +1031,7 @@ namespace __detail
 	insert(_Pair&& __v)
 	{
 	  __hashtable& __h = this->_M_conjure_hashtable();
-	  return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
+	  return __h._M_emplace(__unique_keys{}, std::forward<_Pair>(__v));
 	}
 
       template<typename _Pair, typename = _IFconsp<_Pair>>
@@ -1026,7 +1039,7 @@ namespace __detail
 	insert(const_iterator __hint, _Pair&& __v)
 	{
 	  __hashtable& __h = this->_M_conjure_hashtable();
-	  return __h._M_emplace(__hint, __unique_keys(),
+	  return __h._M_emplace(__hint, __unique_keys{},
 				std::forward<_Pair>(__v));
 	}
    };
@@ -1146,7 +1159,7 @@ namespace __detail
    */
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __cache_hash_code>
+	   typename _Cache_hash_code>
     struct _Local_iterator_base;
 
   /**
@@ -1171,14 +1184,15 @@ namespace __detail
    */
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __cache_hash_code>
+	   typename _Cache_hash_code>
     struct _Hash_code_base;
 
   /// Specialization: ranged hash function, no caching hash codes.  H1
   /// and H2 are provided but ignored.  We define a dummy hash code type.
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			   __hash_not_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _Hash>
     {
@@ -1188,7 +1202,7 @@ namespace __detail
 
     protected:
       typedef void* 					__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<_Value, __hash_not_cached_t>	__node_type;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1244,7 +1258,8 @@ namespace __detail
   /// and no definition.
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			   __hash_cached_t>;
 
   /// Specialization: hash function and range-hashing function, no
   /// caching of hash codes.
@@ -1252,7 +1267,7 @@ namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
-			   _Default_ranged_hash, false>
+			   _Default_ranged_hash, __hash_not_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
       private _Hashtable_ebo_helper<2, _H2>
@@ -1264,7 +1279,8 @@ namespace __detail
 
       // Gives the local iterator implementation access to _M_bucket_index().
       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, false>;
+					 _Default_ranged_hash,
+					 __hash_not_cached_t>;
 
     public:
       typedef _H1 					hasher;
@@ -1275,7 +1291,7 @@ namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<_Value, __hash_not_cached_t>	__node_type;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1339,7 +1355,7 @@ namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
-			   _Default_ranged_hash, true>
+			   _Default_ranged_hash, __hash_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
       private _Hashtable_ebo_helper<2, _H2>
@@ -1347,7 +1363,7 @@ namespace __detail
     private:
       // Gives the local iterator implementation access to _M_h2().
       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, true>;
+					 _Default_ranged_hash, __hash_cached_t>;
 
       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
@@ -1362,7 +1378,7 @@ namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, true>			__node_type;
+      typedef _Hash_node<_Value, __hash_cached_t>	__node_type;
 
       // We need the default constructor for _Hashtable default constructor.
       _Hash_code_base() = default;
@@ -1421,17 +1437,18 @@ namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, true>
+				_H1, _H2, _Hash, __hash_cached_t>
     : private _Hashtable_ebo_helper<0, _H2>
     {
     protected:
       using __base_type = _Hashtable_ebo_helper<0, _H2>;
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, true>;
+					       _H1, _H2, _Hash,
+					       __hash_cached_t>;
 
       _Local_iterator_base() = default;
       _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, true>* __p,
+			   _Hash_node<_Value, __hash_cached_t>* __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base._M_h2()),
 	_M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
@@ -1450,7 +1467,7 @@ namespace __detail
 	  }
       }
 
-      _Hash_node<_Value, true>*  _M_cur;
+      _Hash_node<_Value, __hash_cached_t>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
@@ -1497,23 +1514,25 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash>
     using __hash_code_for_local_iter
       = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
-					   _H1, _H2, _Hash, false>>;
+					   _H1, _H2, _Hash,
+					   __hash_not_cached_t>>;
 
   // Partial specialization used when hash codes are not cached
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, false>
+				_H1, _H2, _Hash, __hash_not_cached_t>
     : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
     {
     protected:
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, false>;
+					       _H1, _H2, _Hash,
+					       __hash_not_cached_t>;
 
       _Local_iterator_base() : _M_bucket_count(-1) { }
 
       _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, false>* __p,
+			   _Hash_node<_Value, __hash_not_cached_t>* __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
       { _M_init(__base); }
@@ -1558,7 +1577,7 @@ namespace __detail
 	  }
       }
 
-      _Hash_node<_Value, false>*  _M_cur;
+      _Hash_node<_Value, __hash_not_cached_t>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
@@ -1578,41 +1597,43 @@ namespace __detail
     };
 
   template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _Cache_hash_code>
     inline bool
     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
+	       _H1, _H2, _Hash, _Cache_hash_code>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
+	       _H1, _H2, _Hash, _Cache_hash_code>& __y)
     { return __x._M_curr() == __y._M_curr(); }
 
   template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _Cache_hash_code>
     inline bool
     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
+	       _H1, _H2, _Hash, _Cache_hash_code>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
+	       _H1, _H2, _Hash, _Cache_hash_code>& __y)
     { return __x._M_curr() != __y._M_curr(); }
 
   /// local iterators
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __constant_iterators, bool __cache>
+	   typename _Constant_iterators, typename _Cache_hash_code>
     struct _Local_iterator
     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+				  _H1, _H2, _Hash, _Cache_hash_code>
     {
     private:
       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+					       _H1, _H2, _Hash, _Cache_hash_code>;
       using __hash_code_base = typename __base_type::__hash_code_base;
     public:
       typedef _Value					value_type;
-      typedef typename std::conditional<__constant_iterators,
+      typedef typename std::conditional<_Constant_iterators::value,
 					const _Value*, _Value*>::type
 						       pointer;
-      typedef typename std::conditional<__constant_iterators,
+      typedef typename std::conditional<_Constant_iterators::value,
 					const _Value&, _Value&>::type
 						       reference;
       typedef std::ptrdiff_t				difference_type;
@@ -1621,7 +1642,7 @@ namespace __detail
       _Local_iterator() = default;
 
       _Local_iterator(const __hash_code_base& __base,
-		      _Hash_node<_Value, __cache>* __n,
+		      _Hash_node<_Value, _Cache_hash_code>* __n,
 		      std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
@@ -1653,14 +1674,15 @@ namespace __detail
   /// local const_iterators
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __constant_iterators, bool __cache>
+	   typename _Constant_iterators, typename _Cache_hash_code>
     struct _Local_const_iterator
     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+				  _H1, _H2, _Hash, _Cache_hash_code>
     {
     private:
       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+					       _H1, _H2, _Hash,
+					       _Cache_hash_code>;
       using __hash_code_base = typename __base_type::__hash_code_base;
 
     public:
@@ -1673,15 +1695,15 @@ namespace __detail
       _Local_const_iterator() = default;
 
       _Local_const_iterator(const __hash_code_base& __base,
-			    _Hash_node<_Value, __cache>* __n,
+			    _Hash_node<_Value, _Cache_hash_code>* __n,
 			    std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
 
       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
 						  _H1, _H2, _Hash,
-						  __constant_iterators,
-						  __cache>& __x)
+						  _Constant_iterators,
+						  _Cache_hash_code>& __x)
       : __base_type(__x)
       { }
 
@@ -1724,7 +1746,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash, typename _Traits>
   struct _Hashtable_base
   : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
-			   _Traits::__hash_cached::value>,
+			   typename _Traits::__hash_cached>,
     private _Hashtable_ebo_helper<0, _Equal>
   {
   public:
@@ -1741,29 +1763,29 @@ namespace __detail
 
     using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
 					     _H1, _H2, _Hash,
-					     __hash_cached::value>;
+					     __hash_cached>;
 
     using __hash_code = typename __hash_code_base::__hash_code;
     using __node_type = typename __hash_code_base::__node_type;
 
     using iterator = __detail::_Node_iterator<value_type,
-					      __constant_iterators::value,
-					      __hash_cached::value>;
+					      __constant_iterators,
+					      __hash_cached>;
 
     using const_iterator = __detail::_Node_const_iterator<value_type,
-						   __constant_iterators::value,
-						   __hash_cached::value>;
+						   __constant_iterators,
+						   __hash_cached>;
 
     using local_iterator = __detail::_Local_iterator<key_type, value_type,
-						  _ExtractKey, _H1, _H2, _Hash,
-						  __constant_iterators::value,
-						     __hash_cached::value>;
+						   _ExtractKey, _H1, _H2, _Hash,
+						     __constant_iterators,
+						     __hash_cached>;
 
     using const_local_iterator = __detail::_Local_const_iterator<key_type,
 								 value_type,
 					_ExtractKey, _H1, _H2, _Hash,
-					__constant_iterators::value,
-					__hash_cached::value>;
+					__constant_iterators,
+					__hash_cached>;
 
     using __ireturn_type = typename std::conditional<__unique_keys::value,
 						     std::pair<iterator, bool>,
@@ -1780,10 +1802,10 @@ namespace __detail
       };
 
     template<typename _Ptr2>
-      struct _Equal_hash_code<_Hash_node<_Ptr2, true>>
+      struct _Equal_hash_code<_Hash_node<_Ptr2, __hash_cached_t>>
       {
        static bool
-       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, true>& __n)
+       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, __hash_cached_t>& __n)
        { return __c == __n._M_hash_code; }
       };
 
@@ -1886,7 +1908,7 @@ namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Unique_keys = _Traits::__unique_keys::value>
+	   typename = typename _Traits::__unique_keys>
     struct _Equality;
 
   /// Specialization.
@@ -1895,7 +1917,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>
     {
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 				     _H1, _H2, _Hash, _RehashPolicy, _Traits>;
@@ -1910,7 +1932,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     bool
     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     _M_equal(const __hashtable& __other) const
     {
       const __hashtable* __this = static_cast<const __hashtable*>(this);
@@ -1933,7 +1955,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>
     : public _Equality_base
     {
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
@@ -1949,7 +1971,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     bool
     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>::
     _M_equal(const __hashtable& __other) const
     {
       const __hashtable* __this = static_cast<const __hashtable*>(this);
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index b8243a73445..49c175a90be 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -439,8 +439,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 
 #define __cpp_lib_unordered_map_try_emplace 201411
       /**
@@ -866,7 +866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -879,7 +879,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1659,12 +1659,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       iterator
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
+      { return _M_h._M_reinsert_node(std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
       insert(const_iterator __hint, node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)); }
 #endif // C++17
 
       //@{
@@ -1760,7 +1760,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1774,7 +1774,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index b138d02bbe8..519a5a1ac0c 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -500,8 +500,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 #endif // C++17
 
       //@{
@@ -595,7 +595,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -608,7 +608,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1288,12 +1288,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       iterator
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
+      { return _M_h._M_reinsert_node(std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
       insert(const_iterator __hint, node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)); }
 #endif // C++17
 
       //@{
@@ -1393,7 +1393,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1407,7 +1407,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py
index 5eab57ea6a7..b2a7757a69f 100644
--- a/libstdc++-v3/python/libstdcxx/v6/printers.py
+++ b/libstdc++-v3/python/libstdcxx/v6/printers.py
@@ -942,9 +942,7 @@ class StdHashtableIterator(Iterator):
     def __init__(self, hashtable):
         self.node = hashtable['_M_before_begin']['_M_nxt']
         valtype = hashtable.type.template_argument(1)
-        cached = hashtable.type.template_argument(9).template_argument(0)
-        node_type = lookup_templ_spec('std::__detail::_Hash_node', str(valtype),
-                                      'true' if cached else 'false')
+        node_type = lookup_templ_spec('std::__detail::_Hash_node_value_base', str(valtype))
         self.node_type = node_type.pointer()
 
     def __iter__(self):
François Dumont Dec. 19, 2019, 7:17 p.m. | #2
After further work on pretty printers I prefer to stay closer to what is 
done currently. It works better with another patch I'll submit one day.

The drawback is that I needed to consider versioned namespace in 
template parameters passed to lookup_templ_spec.

François


On 12/9/19 10:15 PM, François Dumont wrote:
> This patch also require an update of the printers.py file.

>

> Here is an updated version.

>

> François

>

> On 11/17/19 9:42 PM, François Dumont wrote:

>> This is the begining of a patch series for _Hashtable

>>

>> Initial patch to clarify code. I was tired to see true/false or 

>> true_type/false_type without knowing what was true/false.

>>

>> I also made code more consistent by chosing to specialize methods 

>> through usage of __unique_keys_t/__multi_keys_t rather than calling 

>> them _M_[multi]_XXX.

>>

>>

>>     * include/bits/hashtable_policy.h (__detail::__unique_keys_t): New.

>>     (__detail::__multi_keys_t): New.

>>     (__detail::__constant_iterators_t): New.

>>     (__detail::__mutable_iterators_t): New.

>>     (__detail::__hash_cached_t): New.

>>     (__detail::__hash_not_cached_t): New.

>>     (_Hash_node<>): Change _Cache_hash_code template parameter from 

>> bool to

>>     typename. Adapt partial specializations.

>>     (_Node_iterator_base<>): Likewise.

>>     (operator==(const _Node_iterator_base<>&,const 

>> _Node_iterator_base<>&)):

>>     Adapt.

>>     (operator!=(const _Node_iterator_base<>&,const 

>> _Node_iterator_base<>&)):

>>     Adapt.

>>     (_Node_iterator<>): Change __constant_iterators and __cache template

>>     parameters from bool to typename.

>>     (_Node_const_iterator<>): Likewise.

>>     (_Map_base<>): Change _Unique_keys template parameter from bool to

>>     typename. Adapt partial specializations.

>>     (_Insert<>): Change _Constant_iterators template parameter from 

>> bool to

>>     typename. Adapt partial specializations.

>>     (_Local_iterator_base<>): Change __cache_hash_code template 

>> parameter

>>     from bool to typename. Adapt partial specialization.

>>     (_Hash_code_base<>): Likewise.

>>     (operator==(const _Local_iterator_base<>&,

>>     const _Local_iterator_base<>&)): Adapt.

>>     (operator!=(const _Local_iterator_base<>&,

>>     const _Local_iterator_base<>&)):

>>     Adapt.

>>     (_Local_iterator<>): Change __constant_iterators and __cache 

>> template

>>     parameters from bool to typename.

>>     (_Local_const_iterator<>): Likewise.

>>     (_Hashtable_base<>): Adapt.

>>     (_Equal_hash_code<>): Adapt.

>>     (_Equality<>): Adapt.

>>     * include/bits/hashtable.h (_Hashtable<>): Replace occurences of

>>     true_type/false_type by respoectively 

>> __unique_type_t/__multi_type_t.

>>     (_M_insert_unique_node(const key_type&, size_t, __hash_code,

>>     __node_type*, size_t)): Replace by...

>>     (_M_insert_node(__unique_keys_t, size_t, __hash_code, __node_type*,

>>     size_t)): ...this.

>>     (_M_insert_muti_node(__node_type*, const key_type&, __hash_code,

>>     __node_type*)): Replace by...

>>     (_M_insert_node(__multi_keys_t, __node_type*, __hash_code,

>>     __node_type*)): ...this.

>>     (_M_reinsert_node(node_type&&)): Replace by...

>>     (_M_reinsert_node(node_type&&, __unique_keys_t)): ...this.

>>     (_M_reinsert_node(const_iterator, node_type&&, __unique_keys_t)): 

>> New,

>>     forward to latter.

>>     (_M_reinsert_node_multi(const_iterator, node_type&&)): Replace by...

>>     (_M_reinsert_node(const_iterator, node_type&&, __multi_keys_t)):

>>     ...this.

>>     (_M_reinsert_node(node_type&&, __multi_keys_t)): New, forward to 

>> latter.

>>     (_M_reinsert_node(node_type&&)): New, use latters.

>>     (_M_reinsert_node(const_iterator, node_type&&)): Likewise.

>>     (_M_merge_unique(_Compatible_Hashtable&)): Replace by...

>>     (_M_merge(__unique_keys_t, _Compatible_Hashtable&)): ...this.

>>     (_M_merge_multi(_Compatible_Hashtable&)): Replace by...

>>     (_M_merge(__multi_keys_t, _Compatible_Hashtable&)): ...this.

>>     (_M_merge(_Compatible_Hashtable&)): New, use latters.

>>     * include/bits/unordered_map.h

>>     (unordered_map<>::insert(const_iterator, node_type&&)): Adapt.

>>     (unordered_map<>::merge(unordered_map<>&)): Adapt.

>> (unordered_map<>::merge(unordered_multimap<>&)): Adapt.

>>     (unordered_multimap<>::insert(node_type&&)): Adapt.

>>     (unordered_multimap<>::insert(const_iterator, node_type&&)): Adapt.

>> (unordered_multimap<>::merge(unordered_multimap<>&)): Adapt.

>> (unordered_multimap<>::merge(unordered_map<>&)): Adapt.

>>     * include/bits/unordered_set.h

>>     (unordered_set<>::insert(const_iterator, node_type&&)): Adapt.

>>     (unordered_set<>::merge(unordered_set<>&)): Adapt.

>> (unordered_set<>::merge(unordered_multiset<>&)): Adapt.

>>     (unordered_multiset<>::insert(node_type&&)): Adapt.

>>     (unordered_multiset<>::insert(const_iterator, node_type&&)): Adapt.

>> (unordered_multiset<>::merge(unordered_multiset<>&)): Adapt.

>> (unordered_multiset<>::merge(unordered_set<>&)): Adapt.

>>

>> Tested under Linux x86_64.

>>

>> François

>>

>
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index c2b2219d471..f57e9ac0638 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -184,7 +184,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       private __detail::_Hashtable_alloc<
 	__alloc_rebind<_Alloc,
 		       __detail::_Hash_node<_Value,
-					    _Traits::__hash_cached::value>>>
+					    typename _Traits::__hash_cached>>>
     {
       static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
 	  "unordered container must have a non-const, non-volatile value_type");
@@ -195,7 +195,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       using __traits_type = _Traits;
       using __hash_cached = typename __traits_type::__hash_cached;
-      using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
+      using __node_type = __detail::_Hash_node<_Value, __hash_cached>;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
 
       using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
@@ -224,6 +224,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using __rehash_type = _RehashPolicy;
       using __rehash_state = typename __rehash_type::_State;
 
+      using __unique_keys_t = __detail::__unique_keys_t;
+      using __multi_keys_t = __detail::__multi_keys_t;
+
       using __constant_iterators = typename __traits_type::__constant_iterators;
       using __unique_keys = typename __traits_type::__unique_keys;
 
@@ -526,7 +529,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
 	_M_before_begin._M_nxt = nullptr;
 	clear();
-	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
+	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
 	return *this;
       }
 
@@ -709,73 +712,91 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __node_base*
       _M_get_previous_node(size_type __bkt, __node_base* __n);
 
-      // Insert node __n with key __k and hash code __code, in bucket __bkt
-      // if no rehash (assumes no element with same key already present).
+      // Insert node __n with hash code __code, in bucket __bkt if no
+      // rehash (assumes no element with same key already present).
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_unique_node(const key_type& __k, size_type __bkt,
-			    __hash_code __code, __node_type* __n,
-			    size_type __n_elt = 1);
+      _M_insert_node(__unique_keys_t, size_type __bkt, __hash_code,
+		     __node_type* __n, size_type __n_elt = 1);
+
+#if !_GLIBCXX_INLINE_VERSION
+      // Insert node with hash code __code, in bucket bkt if no rehash (assumes
+      // no element with its key already present). Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_unique_node(size_type __bkt, __hash_code __code,
+			    __node_type* __n, size_type __n_elt = 1);
+#endif
 
       // Insert node __n with key __k and hash code __code.
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_multi_node(__node_type* __hint, const key_type& __k,
+      _M_insert_node(__multi_keys_t, __node_type* __hint,
+		     __hash_code __code, __node_type* __n);
+
+#if !_GLIBCXX_INLINE_VERSION
+      // Insert node with hash code __code. Take ownership of the node,
+      // deallocate it on exception.
+      iterator
+      _M_insert_multi_node(__node_type* __hint,
 			   __hash_code __code, __node_type* __n);
+#endif
 
       template<typename... _Args>
 	std::pair<iterator, bool>
-	_M_emplace(true_type, _Args&&... __args);
+	_M_emplace(__unique_keys_t, _Args&&... __args);
 
       template<typename... _Args>
 	iterator
-	_M_emplace(false_type __uk, _Args&&... __args)
-	{ return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
+	_M_emplace(__multi_keys_t __mks, _Args&&... __args)
+	{
+	  return _M_emplace(cend(), __mks,
+			    std::forward<_Args>(__args)...);
+	}
 
       // Emplace with hint, useless when keys are unique.
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, true_type __uk, _Args&&... __args)
-	{ return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
+	_M_emplace(const_iterator, __unique_keys_t __uks, _Args&&... __args)
+	{ return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
 
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, false_type, _Args&&... __args);
+	_M_emplace(const_iterator, __multi_keys_t, _Args&&... __args);
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
+	_M_insert(_Arg&&, const _NodeGenerator&, __unique_keys_t, size_type = 1);
 
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
-		  false_type __uk)
+		  __multi_keys_t __mks)
 	{
 	  return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
-			   __uk);
+			   __mks);
 	}
 
       // Insert with hint, not used when keys are unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&& __arg,
-		  const _NodeGenerator& __node_gen, true_type __uk)
+		  const _NodeGenerator& __node_gen, __unique_keys_t __uks)
 	{
-	  return
-	    _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
+	  return _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
 	}
 
       // Insert with hint when keys are not unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&&,
-		  const _NodeGenerator&, false_type);
+		  const _NodeGenerator&, __multi_keys_t);
 
       size_type
-      _M_erase(true_type, const key_type&);
+      _M_erase(__unique_keys_t, const key_type&);
 
       size_type
-      _M_erase(false_type, const key_type&);
+      _M_erase(__multi_keys_t, const key_type&);
 
       iterator
       _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
@@ -785,13 +806,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename... _Args>
 	__ireturn_type
 	emplace(_Args&&... __args)
-	{ return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
+	{ return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
 
       template<typename... _Args>
 	iterator
 	emplace_hint(const_iterator __hint, _Args&&... __args)
 	{
-	  return _M_emplace(__hint, __unique_keys(),
+	  return _M_emplace(__hint, __unique_keys{},
 			    std::forward<_Args>(__args)...);
 	}
 
@@ -808,7 +829,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       erase(const key_type& __k)
-      { return _M_erase(__unique_keys(), __k); }
+      { return _M_erase(__unique_keys{}, __k); }
 
       iterator
       erase(const_iterator, const_iterator);
@@ -824,9 +845,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // reserve, if present, comes from _Rehash_base.
 
 #if __cplusplus > 201402L
+    private:
       /// Re-insert an extracted node into a container with unique keys.
       insert_return_type
-      _M_reinsert_node(node_type&& __nh)
+      _M_reinsert_node(node_type&& __nh, __unique_keys_t __uks)
       {
 	insert_return_type __ret;
 	if (__nh.empty())
@@ -847,7 +869,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    else
 	      {
 		__ret.position
-		  = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr);
+		  = _M_insert_node(__uks, __bkt, __code, __nh._M_ptr);
 		__nh._M_ptr = nullptr;
 		__ret.inserted = true;
 	      }
@@ -855,9 +877,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __ret;
       }
 
+      /// Re-insert an extracted node into a container with unique keys.
+      insert_return_type
+      _M_reinsert_node(const_iterator, node_type&& __nh, __unique_keys_t __uks)
+      { return _M_reinsert_node(std::move(__nh), __uks); }
+
       /// Re-insert an extracted node into a container with equivalent keys.
       iterator
-      _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
+      _M_reinsert_node(node_type&& __nh, __multi_keys_t __mks)
+      { return _M_reinsert_node(cend(), std::move(__nh), __mks); }
+
+      iterator
+      _M_reinsert_node(const_iterator __hint, node_type&& __nh,
+		       __multi_keys_t __mks)
       {
 	if (__nh.empty())
 	  return end();
@@ -867,12 +899,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	const key_type& __k = __nh._M_key();
 	auto __code = this->_M_hash_code(__k);
 	auto __ret
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __nh._M_ptr);
 	__nh._M_ptr = nullptr;
 	return __ret;
       }
 
-    private:
       node_type
       _M_extract_node(size_t __bkt, __node_base* __prev_n)
       {
@@ -915,15 +946,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __nh;
       }
 
-      /// Merge from a compatible container into one with unique keys.
+      /// Re-insert an extracted node into a container.
+      auto
+      _M_reinsert_node(node_type&& __nh)
+	-> decltype(_M_reinsert_node(std::move(__nh), __unique_keys{}))
+      { return _M_reinsert_node(std::move(__nh), __unique_keys{}); }
+
+      /// Re-insert an extracted node into a container with hint.
+      auto
+      _M_reinsert_node(const_iterator __hint, node_type&& __nh)
+	-> decltype(_M_reinsert_node(__hint, std::move(__nh), __unique_keys{}))
+      { return _M_reinsert_node(__hint, std::move(__nh), __unique_keys{}); }
+
+      /// Merge from a compatible container.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_unique(_Compatible_Hashtable& __src) noexcept
+	_M_merge(_Compatible_Hashtable& __src) noexcept
 	{
 	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
+	  _M_merge(__unique_keys{}, __src);
+	}
+
+    private:
+      /// Merge from a compatible container into one with unique keys.
+      template<typename _Compatible_Hashtable>
+	void
+	_M_merge(__unique_keys_t __uks, _Compatible_Hashtable& __src) noexcept
+	{
 	  auto __n_elt = __src.size();
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
 	    {
@@ -934,8 +986,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      if (_M_find_node(__bkt, __k, __code) == nullptr)
 		{
 		  auto __nh = __src.extract(__pos);
-		  _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr,
-					__n_elt);
+		  _M_insert_node(__uks, __bkt, __code, __nh._M_ptr, __n_elt);
 		  __nh._M_ptr = nullptr;
 		  __n_elt = 1;
 		}
@@ -947,24 +998,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       /// Merge from a compatible container into one with equivalent keys.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_multi(_Compatible_Hashtable& __src) noexcept
+	_M_merge(__multi_keys_t __mks, _Compatible_Hashtable& __src) noexcept
 	{
-	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
-	      node_type>, "Node types are compatible");
-	  __glibcxx_assert(get_allocator() == __src.get_allocator());
-
 	  this->reserve(size() + __src.size());
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
-	    _M_reinsert_node_multi(cend(), __src.extract(__i++));
+	    _M_reinsert_node(cend(), __src.extract(__i++), __mks);
 	}
 #endif // C++17
 
     private:
       // Helper rehash method used when keys are unique.
-      void _M_rehash_aux(size_type __bkt_count, true_type);
+      void _M_rehash_aux(size_type __bkt_count, __unique_keys_t);
 
       // Helper rehash method used when keys can be non-unique.
-      void _M_rehash_aux(size_type __bkt_count, false_type);
+      void _M_rehash_aux(size_type __bkt_count, __multi_keys_t);
 
       // Unconditionally change size of bucket array to n, restore
       // hash policy state to __state on exception.
@@ -1251,7 +1298,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_move_assign(_Hashtable&& __ht, false_type)
     {
       if (__ht._M_node_allocator() == this->_M_node_allocator())
-	_M_move_assign(std::move(__ht), true_type());
+	_M_move_assign(std::move(__ht), true_type{});
       else
 	{
 	  // Can't move memory, move elements then.
@@ -1664,7 +1711,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_emplace(true_type, _Args&&... __args)
+      _M_emplace(__unique_keys_t __uks, _Args&&... __args)
       -> pair<iterator, bool>
       {
 	// First build the node to get access to the hash code
@@ -1677,7 +1724,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return std::make_pair(iterator(__p), false);
 
 	// Insert the node
-	auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -1690,7 +1737,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_emplace(const_iterator __hint, false_type, _Args&&... __args)
+      _M_emplace(const_iterator __hint, __multi_keys_t __mks, _Args&&... __args)
       -> iterator
       {
 	// First build the node to get its hash code.
@@ -1699,7 +1746,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	__hash_code __code = this->_M_hash_code(__k);
 	auto __pos
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -1711,9 +1758,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_unique_node(const key_type& __k, size_type __bkt,
-			  __hash_code __code, __node_type* __node,
-			  size_type __n_elt)
+    _M_insert_node(__unique_keys_t, size_type __bkt, __hash_code __code,
+		   __node_type* __node, size_type __n_elt)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1724,7 +1770,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__do_rehash.first)
 	{
 	  _M_rehash(__do_rehash.second, __saved_state);
-	  __bkt = _M_bucket_index(__k, __code);
+	  __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
 	}
 
       this->_M_store_code(__node, __code);
@@ -1735,6 +1781,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return iterator(__node);
     }
 
+#if !_GLIBCXX_INLINE_VERSION
   template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
@@ -1742,8 +1789,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			 __hash_code __code, __node_type* __node)
+    _M_insert_unique_node(size_type __bkt, __hash_code __code,
+			  __node_type* __node, size_type __n_elt)
+    -> iterator
+    {
+      __try
+	{
+	  return _M_insert_node(__unique_keys{}, __bkt, __code, __node,
+				__n_elt);
+	}
+      __catch(...)
+	{
+	  this->_M_deallocate_node(__node);
+	  __throw_exception_again;
+	}
+    }
+#endif
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    auto
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_insert_node(__multi_keys_t, __node_type* __hint,
+		   __hash_code __code, __node_type* __node)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1754,6 +1825,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_rehash(__do_rehash.second, __saved_state);
 
       this->_M_store_code(__node, __code);
+      const key_type& __k = this->_M_extract()(__node->_M_v());
       size_type __bkt = _M_bucket_index(__k, __code);
 
       // Find the node before an equivalent one or use hint if it exists and
@@ -1788,6 +1860,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       return iterator(__node);
     }
 
+#if !_GLIBCXX_INLINE_VERSION
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    auto
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_insert_multi_node(__node_type* __hint,
+			 __hash_code __code, __node_type* __node)
+    -> iterator
+    {
+      __try
+	{
+	  return _M_insert_node(__unique_keys{}, __hint, __code, __node);
+	}
+      __catch(...)
+	{
+	  this->_M_deallocate_node(__node);
+	  __throw_exception_again;
+	}
+    }
+#endif
+
   // Insert v if no element with its key is already present.
   template<typename _Key, typename _Value,
 	   typename _Alloc, typename _ExtractKey, typename _Equal,
@@ -1797,8 +1893,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
-		size_type __n_elt)
+      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen,
+		__unique_keys_t __uks, size_type __n_elt)
       -> pair<iterator, bool>
       {
 	const key_type& __k = this->_M_extract()(__v);
@@ -1810,7 +1906,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
 	auto __pos
-	  = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt);
+	  = _M_insert_node(__uks, __bkt, __code, __node._M_node, __n_elt);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -1825,7 +1921,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(const_iterator __hint, _Arg&& __v,
-		const _NodeGenerator& __node_gen, false_type)
+		const _NodeGenerator& __node_gen, __multi_keys_t __mks)
       -> iterator
       {
 	// First compute the hash code so that we don't do anything if it
@@ -1836,7 +1932,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
 	const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
 	auto __pos
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -1896,7 +1992,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_erase(true_type, const key_type& __k)
+    _M_erase(__unique_keys_t, const key_type& __k)
     -> size_type
     {
       __hash_code __code = this->_M_hash_code(__k);
@@ -1920,7 +2016,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_erase(false_type, const key_type& __k)
+    _M_erase(__multi_keys_t, const key_type& __k)
     -> size_type
     {
       __hash_code __code = this->_M_hash_code(__k);
@@ -2065,7 +2161,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __try
 	{
-	  _M_rehash_aux(__bkt_count, __unique_keys());
+	  _M_rehash_aux(__bkt_count, __unique_keys{});
 	}
       __catch(...)
 	{
@@ -2084,7 +2180,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_rehash_aux(size_type __bkt_count, true_type)
+    _M_rehash_aux(size_type __bkt_count, __unique_keys_t)
     {
       __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
       __node_type* __p = _M_begin();
@@ -2126,7 +2222,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_rehash_aux(size_type __bkt_count, false_type)
+    _M_rehash_aux(size_type __bkt_count, __multi_keys_t)
     {
       __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f5809c7443a..b9320506bb2 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -172,6 +172,14 @@ namespace __detail
 
   // Auxiliary types used for all instantiations of _Hashtable nodes
   // and iterators.
+  using __unique_keys_t = true_type;
+  using __multi_keys_t = false_type;
+
+  using __constant_iterators_t = true_type;
+  using __mutable_iterators_t = false_type;
+
+  using __hash_cached_t = true_type;
+  using __hash_not_cached_t = false_type;
 
   /**
    *  struct _Hashtable_traits
@@ -252,7 +260,7 @@ namespace __detail
   /**
    *  Primary template struct _Hash_node.
    */
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     struct _Hash_node;
 
   /**
@@ -261,7 +269,8 @@ namespace __detail
    *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
+    struct _Hash_node<_Value, __hash_cached_t>
+    : _Hash_node_value_base<_Value>
     {
       std::size_t  _M_hash_code;
 
@@ -276,7 +285,8 @@ namespace __detail
    *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
+    struct _Hash_node<_Value, __hash_not_cached_t>
+    : _Hash_node_value_base<_Value>
     {
       _Hash_node*
       _M_next() const noexcept
@@ -284,7 +294,7 @@ namespace __detail
     };
 
   /// Base class for node iterators.
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     struct _Node_iterator_base
     {
       using __node_type = _Hash_node<_Value, _Cache_hash_code>;
@@ -299,14 +309,14 @@ namespace __detail
       { _M_cur = _M_cur->_M_next(); }
     };
 
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     inline bool
     operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 	       const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
     noexcept
     { return __x._M_cur == __y._M_cur; }
 
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     inline bool
     operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 	       const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
@@ -314,12 +324,13 @@ namespace __detail
     { return __x._M_cur != __y._M_cur; }
 
   /// Node iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _Value, typename _Constant_iterators,
+	   typename _Cache_hash_code>
     struct _Node_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_Value, _Cache_hash_code>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_Value, _Cache_hash_code>;
       using __node_type = typename __base_type::__node_type;
 
     public:
@@ -327,10 +338,10 @@ namespace __detail
       typedef std::ptrdiff_t				difference_type;
       typedef std::forward_iterator_tag			iterator_category;
 
-      using pointer = typename std::conditional<__constant_iterators,
+      using pointer = typename std::conditional<_Constant_iterators::value,
 						const _Value*, _Value*>::type;
 
-      using reference = typename std::conditional<__constant_iterators,
+      using reference = typename std::conditional<_Constant_iterators::value,
 						  const _Value&, _Value&>::type;
 
       _Node_iterator() noexcept
@@ -365,12 +376,13 @@ namespace __detail
     };
 
   /// Node const_iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _Value, typename _Constant_iterators,
+	   typename _Cache_hash_code>
     struct _Node_const_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_Value, _Cache_hash_code>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_Value, _Cache_hash_code>;
       using __node_type = typename __base_type::__node_type;
 
     public:
@@ -388,8 +400,8 @@ namespace __detail
       _Node_const_iterator(__node_type* __p) noexcept
       : __base_type(__p) { }
 
-      _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
-			   __cache>& __x) noexcept
+      _Node_const_iterator(const _Node_iterator<_Value, _Constant_iterators,
+						_Cache_hash_code>& __x) noexcept
       : __base_type(__x._M_cur) { }
 
       reference
@@ -641,25 +653,25 @@ namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Unique_keys = _Traits::__unique_keys::value>
+	   typename = typename _Traits::__unique_keys>
     struct _Map_base { };
 
-  /// Partial specialization, __unique_keys set to false.
+  /// Partial specialization, keys are not unique.
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>
     {
       using mapped_type = typename std::tuple_element<1, _Pair>::type;
     };
 
-  /// Partial specialization, __unique_keys set to true.
+  /// Partial specialization, keys are unique.
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>
     {
     private:
       using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
@@ -699,7 +711,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     operator[](const key_type& __k)
     -> mapped_type&
     {
@@ -716,7 +728,7 @@ namespace __detail
 	std::tuple<>()
       };
       auto __pos
-	= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	= __h->_M_insert_node(__unique_keys_t{}, __bkt, __code, __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -726,7 +738,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     operator[](key_type&& __k)
     -> mapped_type&
     {
@@ -743,7 +755,7 @@ namespace __detail
 	std::tuple<>()
       };
       auto __pos
-	= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	= __h->_M_insert_node(__unique_keys_t{}, __bkt, __code, __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -753,7 +765,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     at(const key_type& __k)
     -> mapped_type&
     {
@@ -772,7 +784,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     at(const key_type& __k) const
     -> const mapped_type&
     {
@@ -810,10 +822,12 @@ namespace __detail
       using iterator = typename __hashtable_base::iterator;
       using const_iterator =  typename __hashtable_base::const_iterator;
       using size_type = typename __hashtable_base::size_type;
-
-      using __unique_keys = typename __hashtable_base::__unique_keys;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
-      using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>;
+
+      using __unique_keys = typename _Traits::__unique_keys;
+      using __hash_cached = typename _Traits::__hash_cached;
+
+      using __node_type = _Hash_node<_Value, __hash_cached>;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
       using __node_gen_type = _AllocNode<__node_alloc_type>;
 
@@ -824,12 +838,12 @@ namespace __detail
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, true_type);
+			const _NodeGetter&, __unique_keys_t);
 
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, false_type);
+			const _NodeGetter&, __multi_keys_t);
 
     public:
       __ireturn_type
@@ -837,7 +851,7 @@ namespace __detail
       {
 	__hashtable& __h = _M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(__v, __node_gen, __unique_keys());
+	return __h._M_insert(__v, __node_gen, __unique_keys{});
       }
 
       iterator
@@ -845,7 +859,7 @@ namespace __detail
       {
 	__hashtable& __h = _M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);	
-	return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
+	return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
       }
 
       void
@@ -858,7 +872,7 @@ namespace __detail
 	{
 	  __hashtable& __h = _M_conjure_hashtable();
 	  __node_gen_type __node_gen(__h);
-	  return _M_insert_range(__first, __last, __node_gen, __unique_keys());
+	  return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
 	}
     };
 
@@ -871,7 +885,7 @@ namespace __detail
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, true_type)
+		      const _NodeGetter& __node_gen, __unique_keys_t __uks)
       {
 	size_type __n_elt = __detail::__distance_fw(__first, __last);
 	if (__n_elt == 0)
@@ -880,8 +894,7 @@ namespace __detail
 	__hashtable& __h = _M_conjure_hashtable();
 	for (; __first != __last; ++__first)
 	  {
-	    if (__h._M_insert(*__first, __node_gen, __unique_keys(),
-			      __n_elt).second)
+	    if (__h._M_insert(*__first, __node_gen, __uks, __n_elt).second)
 	      __n_elt = 1;
 	    else if (__n_elt != 1)
 	      --__n_elt;
@@ -897,7 +910,7 @@ namespace __detail
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, false_type)
+		      const _NodeGetter& __node_gen, __multi_keys_t __mks)
       {
 	using __rehash_type = typename __hashtable::__rehash_type;
 	using __rehash_state = typename __hashtable::__rehash_state;
@@ -918,7 +931,7 @@ namespace __detail
 	  __h._M_rehash(__do_rehash.second, __saved_state);
 
 	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __unique_keys());
+	  __h._M_insert(*__first, __node_gen, __mks);
       }
 
   /**
@@ -931,7 +944,7 @@ namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Constant_iterators = _Traits::__constant_iterators::value>
+	   typename = typename _Traits::__constant_iterators>
     struct _Insert;
 
   /// Specialization.
@@ -940,7 +953,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, true>
+		   _RehashPolicy, _Traits, __constant_iterators_t>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
@@ -968,7 +981,7 @@ namespace __detail
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
+	return __h._M_insert(std::move(__v), __node_gen, __unique_keys{});
       }
 
       iterator
@@ -977,7 +990,7 @@ namespace __detail
 	__hashtable& __h = this->_M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
 	return __h._M_insert(__hint, std::move(__v), __node_gen,
-			     __unique_keys());
+			     __unique_keys{});
       }
     };
 
@@ -987,7 +1000,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, false>
+		   _RehashPolicy, _Traits, __mutable_iterators_t>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
@@ -1018,7 +1031,7 @@ namespace __detail
 	insert(_Pair&& __v)
 	{
 	  __hashtable& __h = this->_M_conjure_hashtable();
-	  return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
+	  return __h._M_emplace(__unique_keys{}, std::forward<_Pair>(__v));
 	}
 
       template<typename _Pair, typename = _IFconsp<_Pair>>
@@ -1026,7 +1039,7 @@ namespace __detail
 	insert(const_iterator __hint, _Pair&& __v)
 	{
 	  __hashtable& __h = this->_M_conjure_hashtable();
-	  return __h._M_emplace(__hint, __unique_keys(),
+	  return __h._M_emplace(__hint, __unique_keys{},
 				std::forward<_Pair>(__v));
 	}
    };
@@ -1146,7 +1159,7 @@ namespace __detail
    */
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __cache_hash_code>
+	   typename _Cache_hash_code>
     struct _Local_iterator_base;
 
   /**
@@ -1171,14 +1184,15 @@ namespace __detail
    */
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __cache_hash_code>
+	   typename _Cache_hash_code>
     struct _Hash_code_base;
 
   /// Specialization: ranged hash function, no caching hash codes.  H1
   /// and H2 are provided but ignored.  We define a dummy hash code type.
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			   __hash_not_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _Hash>
     {
@@ -1188,7 +1202,7 @@ namespace __detail
 
     protected:
       typedef void* 					__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<_Value, __hash_not_cached_t>	__node_type;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1244,7 +1258,8 @@ namespace __detail
   /// and no definition.
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			   __hash_cached_t>;
 
   /// Specialization: hash function and range-hashing function, no
   /// caching of hash codes.
@@ -1252,7 +1267,7 @@ namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
-			   _Default_ranged_hash, false>
+			   _Default_ranged_hash, __hash_not_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
       private _Hashtable_ebo_helper<2, _H2>
@@ -1264,7 +1279,8 @@ namespace __detail
 
       // Gives the local iterator implementation access to _M_bucket_index().
       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, false>;
+					 _Default_ranged_hash,
+					 __hash_not_cached_t>;
 
     public:
       typedef _H1 					hasher;
@@ -1275,7 +1291,7 @@ namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<_Value, __hash_not_cached_t>	__node_type;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1339,7 +1355,7 @@ namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
-			   _Default_ranged_hash, true>
+			   _Default_ranged_hash, __hash_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
       private _Hashtable_ebo_helper<2, _H2>
@@ -1347,7 +1363,7 @@ namespace __detail
     private:
       // Gives the local iterator implementation access to _M_h2().
       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, true>;
+					 _Default_ranged_hash, __hash_cached_t>;
 
       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
@@ -1362,7 +1378,7 @@ namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, true>			__node_type;
+      typedef _Hash_node<_Value, __hash_cached_t>	__node_type;
 
       // We need the default constructor for _Hashtable default constructor.
       _Hash_code_base() = default;
@@ -1421,17 +1437,18 @@ namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, true>
+				_H1, _H2, _Hash, __hash_cached_t>
     : private _Hashtable_ebo_helper<0, _H2>
     {
     protected:
       using __base_type = _Hashtable_ebo_helper<0, _H2>;
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, true>;
+					       _H1, _H2, _Hash,
+					       __hash_cached_t>;
 
       _Local_iterator_base() = default;
       _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, true>* __p,
+			   _Hash_node<_Value, __hash_cached_t>* __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base._M_h2()),
 	_M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
@@ -1450,7 +1467,7 @@ namespace __detail
 	  }
       }
 
-      _Hash_node<_Value, true>*  _M_cur;
+      _Hash_node<_Value, __hash_cached_t>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
@@ -1497,23 +1514,25 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash>
     using __hash_code_for_local_iter
       = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
-					   _H1, _H2, _Hash, false>>;
+					   _H1, _H2, _Hash,
+					   __hash_not_cached_t>>;
 
   // Partial specialization used when hash codes are not cached
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, false>
+				_H1, _H2, _Hash, __hash_not_cached_t>
     : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
     {
     protected:
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, false>;
+					       _H1, _H2, _Hash,
+					       __hash_not_cached_t>;
 
       _Local_iterator_base() : _M_bucket_count(-1) { }
 
       _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, false>* __p,
+			   _Hash_node<_Value, __hash_not_cached_t>* __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
       { _M_init(__base); }
@@ -1558,7 +1577,7 @@ namespace __detail
 	  }
       }
 
-      _Hash_node<_Value, false>*  _M_cur;
+      _Hash_node<_Value, __hash_not_cached_t>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
@@ -1578,41 +1597,43 @@ namespace __detail
     };
 
   template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _Cache_hash_code>
     inline bool
     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
+	       _H1, _H2, _Hash, _Cache_hash_code>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
+	       _H1, _H2, _Hash, _Cache_hash_code>& __y)
     { return __x._M_curr() == __y._M_curr(); }
 
   template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _Cache_hash_code>
     inline bool
     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
+	       _H1, _H2, _Hash, _Cache_hash_code>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
+	       _H1, _H2, _Hash, _Cache_hash_code>& __y)
     { return __x._M_curr() != __y._M_curr(); }
 
   /// local iterators
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __constant_iterators, bool __cache>
+	   typename _Constant_iterators, typename _Cache_hash_code>
     struct _Local_iterator
     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+				  _H1, _H2, _Hash, _Cache_hash_code>
     {
     private:
       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+					       _H1, _H2, _Hash, _Cache_hash_code>;
       using __hash_code_base = typename __base_type::__hash_code_base;
     public:
       typedef _Value					value_type;
-      typedef typename std::conditional<__constant_iterators,
+      typedef typename std::conditional<_Constant_iterators::value,
 					const _Value*, _Value*>::type
 						       pointer;
-      typedef typename std::conditional<__constant_iterators,
+      typedef typename std::conditional<_Constant_iterators::value,
 					const _Value&, _Value&>::type
 						       reference;
       typedef std::ptrdiff_t				difference_type;
@@ -1621,7 +1642,7 @@ namespace __detail
       _Local_iterator() = default;
 
       _Local_iterator(const __hash_code_base& __base,
-		      _Hash_node<_Value, __cache>* __n,
+		      _Hash_node<_Value, _Cache_hash_code>* __n,
 		      std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
@@ -1653,14 +1674,15 @@ namespace __detail
   /// local const_iterators
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __constant_iterators, bool __cache>
+	   typename _Constant_iterators, typename _Cache_hash_code>
     struct _Local_const_iterator
     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+				  _H1, _H2, _Hash, _Cache_hash_code>
     {
     private:
       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+					       _H1, _H2, _Hash,
+					       _Cache_hash_code>;
       using __hash_code_base = typename __base_type::__hash_code_base;
 
     public:
@@ -1673,15 +1695,15 @@ namespace __detail
       _Local_const_iterator() = default;
 
       _Local_const_iterator(const __hash_code_base& __base,
-			    _Hash_node<_Value, __cache>* __n,
+			    _Hash_node<_Value, _Cache_hash_code>* __n,
 			    std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
 
       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
 						  _H1, _H2, _Hash,
-						  __constant_iterators,
-						  __cache>& __x)
+						  _Constant_iterators,
+						  _Cache_hash_code>& __x)
       : __base_type(__x)
       { }
 
@@ -1724,7 +1746,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash, typename _Traits>
   struct _Hashtable_base
   : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
-			   _Traits::__hash_cached::value>,
+			   typename _Traits::__hash_cached>,
     private _Hashtable_ebo_helper<0, _Equal>
   {
   public:
@@ -1741,29 +1763,29 @@ namespace __detail
 
     using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
 					     _H1, _H2, _Hash,
-					     __hash_cached::value>;
+					     __hash_cached>;
 
     using __hash_code = typename __hash_code_base::__hash_code;
     using __node_type = typename __hash_code_base::__node_type;
 
     using iterator = __detail::_Node_iterator<value_type,
-					      __constant_iterators::value,
-					      __hash_cached::value>;
+					      __constant_iterators,
+					      __hash_cached>;
 
     using const_iterator = __detail::_Node_const_iterator<value_type,
-						   __constant_iterators::value,
-						   __hash_cached::value>;
+						   __constant_iterators,
+						   __hash_cached>;
 
     using local_iterator = __detail::_Local_iterator<key_type, value_type,
-						  _ExtractKey, _H1, _H2, _Hash,
-						  __constant_iterators::value,
-						     __hash_cached::value>;
+						   _ExtractKey, _H1, _H2, _Hash,
+						     __constant_iterators,
+						     __hash_cached>;
 
     using const_local_iterator = __detail::_Local_const_iterator<key_type,
 								 value_type,
 					_ExtractKey, _H1, _H2, _Hash,
-					__constant_iterators::value,
-					__hash_cached::value>;
+					__constant_iterators,
+					__hash_cached>;
 
     using __ireturn_type = typename std::conditional<__unique_keys::value,
 						     std::pair<iterator, bool>,
@@ -1780,10 +1802,10 @@ namespace __detail
       };
 
     template<typename _Ptr2>
-      struct _Equal_hash_code<_Hash_node<_Ptr2, true>>
+      struct _Equal_hash_code<_Hash_node<_Ptr2, __hash_cached_t>>
       {
        static bool
-       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, true>& __n)
+       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, __hash_cached_t>& __n)
        { return __c == __n._M_hash_code; }
       };
 
@@ -1886,7 +1908,7 @@ namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Unique_keys = _Traits::__unique_keys::value>
+	   typename = typename _Traits::__unique_keys>
     struct _Equality;
 
   /// Specialization.
@@ -1895,7 +1917,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>
     {
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 				     _H1, _H2, _Hash, _RehashPolicy, _Traits>;
@@ -1910,7 +1932,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     bool
     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     _M_equal(const __hashtable& __other) const
     {
       const __hashtable* __this = static_cast<const __hashtable*>(this);
@@ -1933,7 +1955,7 @@ namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>
     : public _Equality_base
     {
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
@@ -1949,7 +1971,7 @@ namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     bool
     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>::
     _M_equal(const __hashtable& __other) const
     {
       const __hashtable* __this = static_cast<const __hashtable*>(this);
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index b8243a73445..49c175a90be 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -439,8 +439,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 
 #define __cpp_lib_unordered_map_try_emplace 201411
       /**
@@ -866,7 +866,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -879,7 +879,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1659,12 +1659,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       iterator
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
+      { return _M_h._M_reinsert_node(std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
       insert(const_iterator __hint, node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)); }
 #endif // C++17
 
       //@{
@@ -1760,7 +1760,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1774,7 +1774,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index b138d02bbe8..519a5a1ac0c 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -500,8 +500,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 #endif // C++17
 
       //@{
@@ -595,7 +595,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -608,7 +608,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1288,12 +1288,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       iterator
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
+      { return _M_h._M_reinsert_node(std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
       insert(const_iterator __hint, node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)); }
 #endif // C++17
 
       //@{
@@ -1393,7 +1393,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1407,7 +1407,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
diff --git a/libstdc++-v3/python/libstdcxx/v6/printers.py b/libstdc++-v3/python/libstdcxx/v6/printers.py
index 5eab57ea6a7..66560701fb9 100644
--- a/libstdc++-v3/python/libstdcxx/v6/printers.py
+++ b/libstdc++-v3/python/libstdcxx/v6/printers.py
@@ -113,7 +113,10 @@ def lookup_templ_spec(templ, *args):
         # Type not found, try again in versioned namespace.
         global _versioned_namespace
         if _versioned_namespace and _versioned_namespace not in templ:
-            t = t.replace('::', '::' + _versioned_namespace, 1)
+            t = '{}<{}>'.format(templ.replace('::', '::' + _versioned_namespace, 1),
+                                ', '.join([str(a).replace('::' + _versioned_namespace, '::', 1)
+                                           .replace('::', '::' + _versioned_namespace, 1)
+                                           for a in args]))
             try:
                 return gdb.lookup_type(t)
             except gdb.error:
@@ -944,7 +947,7 @@ class StdHashtableIterator(Iterator):
         valtype = hashtable.type.template_argument(1)
         cached = hashtable.type.template_argument(9).template_argument(0)
         node_type = lookup_templ_spec('std::__detail::_Hash_node', str(valtype),
-                                      'true' if cached else 'false')
+                                      'std::integral_constant<bool, {}>'.format('true' if cached else 'false'))
         self.node_type = node_type.pointer()
 
     def __iter__(self):
H.J. Lu via Gcc-patches July 17, 2020, 10:11 a.m. | #3
N.B. the 0/6 entry of a patch series is supposed to be a cover letter
describing the changes in the series, not one of the patches.

If you have patches 0/6, 1/6, 2/6 ... 6/6 then you actually have seven
patches, not six!

Anyway ...

On 19/12/19 20:17 +0100, François Dumont wrote:
>diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h

>index f5809c7443a..b9320506bb2 100644

>--- a/libstdc++-v3/include/bits/hashtable_policy.h

>+++ b/libstdc++-v3/include/bits/hashtable_policy.h

>@@ -172,6 +172,14 @@ namespace __detail

> 

>   // Auxiliary types used for all instantiations of _Hashtable nodes

>   // and iterators.

>+  using __unique_keys_t = true_type;

>+  using __multi_keys_t = false_type;

>+

>+  using __constant_iterators_t = true_type;

>+  using __mutable_iterators_t = false_type;

>+

>+  using __hash_cached_t = true_type;

>+  using __hash_not_cached_t = false_type;


This is an ABI change, and the benefit doesn't seem large enough to
justify it. It will result in code size increases for anything that
links objects compiled before and after the change.

If we wanted to do this, I think it would be better to use enums, so:

enum _Unique_keys { __unique_keys, __multi_keys };

Otherwise you can use __hash_cached_t where __unique_keys_t is meant
to be used, so all you've done is introduce more names for the same
things.

If you want to replace the 'true' and 'false' literals with something
more descriptive, can't you just use constants?

constexpr bool __hash_cached = true;
constexpr bool __hash_not_cached = false;

Or just use comments:

     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
				_H1, _H2, _Hash, /*cached=*/ false>
H.J. Lu via Gcc-patches July 29, 2020, 9:35 a.m. | #4
On 17/07/20 12:11 pm, Jonathan Wakely wrote:
> N.B. the 0/6 entry of a patch series is supposed to be a cover letter

> describing the changes in the series, not one of the patches.

>

> If you have patches 0/6, 1/6, 2/6 ... 6/6 then you actually have seven

> patches, not six!

>

> Anyway ...

>

> On 19/12/19 20:17 +0100, François Dumont wrote:

>> diff --git a/libstdc++-v3/include/bits/hashtable_policy.h 

>> b/libstdc++-v3/include/bits/hashtable_policy.h

>> index f5809c7443a..b9320506bb2 100644

>> --- a/libstdc++-v3/include/bits/hashtable_policy.h

>> +++ b/libstdc++-v3/include/bits/hashtable_policy.h

>> @@ -172,6 +172,14 @@ namespace __detail

>>

>>   // Auxiliary types used for all instantiations of _Hashtable nodes

>>   // and iterators.

>> +  using __unique_keys_t = true_type;

>> +  using __multi_keys_t = false_type;

>> +

>> +  using __constant_iterators_t = true_type;

>> +  using __mutable_iterators_t = false_type;

>> +

>> +  using __hash_cached_t = true_type;

>> +  using __hash_not_cached_t = false_type;

>

> This is an ABI change, and the benefit doesn't seem large enough to

> justify it. It will result in code size increases for anything that

> links objects compiled before and after the change.

>

> If we wanted to do this, I think it would be better to use enums, so:

>

> enum _Unique_keys { __unique_keys, __multi_keys };

>

> Otherwise you can use __hash_cached_t where __unique_keys_t is meant

> to be used, so all you've done is introduce more names for the same

> things.

>

> If you want to replace the 'true' and 'false' literals with something

> more descriptive, can't you just use constants?

>

> constexpr bool __hash_cached = true;

> constexpr bool __hash_not_cached = false;

>

> Or just use comments:

>

>     struct _Local_iterator_base<_Key, _Value, _ExtractKey,

>                 _H1, _H2, _Hash, /*cached=*/ false>

>

>

Ok, I'll review this patch with this simpler approach.

I even started to add comments in the patch you already approved.

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index c2b2219d471..ef71c090f3b 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -184,7 +184,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       private __detail::_Hashtable_alloc<
 	__alloc_rebind<_Alloc,
 		       __detail::_Hash_node<_Value,
-					    _Traits::__hash_cached::value>>>
+					    typename _Traits::__hash_cached>>>
     {
       static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
 	  "unordered container must have a non-const, non-volatile value_type");
@@ -195,7 +195,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       using __traits_type = _Traits;
       using __hash_cached = typename __traits_type::__hash_cached;
-      using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
+      using __node_type = __detail::_Hash_node<_Value, __hash_cached>;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
 
       using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
@@ -224,6 +224,9 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using __rehash_type = _RehashPolicy;
       using __rehash_state = typename __rehash_type::_State;
 
+      using __unique_keys_t = __detail::__unique_keys_t;
+      using __multi_keys_t = __detail::__multi_keys_t;
+
       using __constant_iterators = typename __traits_type::__constant_iterators;
       using __unique_keys = typename __traits_type::__unique_keys;
 
@@ -526,7 +529,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	__reuse_or_alloc_node_gen_t __roan(_M_begin(), *this);
 	_M_before_begin._M_nxt = nullptr;
 	clear();
-	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
+	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
 	return *this;
       }
 
@@ -709,73 +712,74 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __node_base*
       _M_get_previous_node(size_type __bkt, __node_base* __n);
 
-      // Insert node __n with key __k and hash code __code, in bucket __bkt
-      // if no rehash (assumes no element with same key already present).
+      // Insert node __n with hash code __code, in bucket __bkt if no
+      // rehash (assumes no element with same key already present).
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_unique_node(const key_type& __k, size_type __bkt,
-			    __hash_code __code, __node_type* __n,
-			    size_type __n_elt = 1);
+      _M_insert_node(__unique_keys_t, size_type __bkt, __hash_code,
+		     __node_type* __n, size_type __n_elt = 1);
 
       // Insert node __n with key __k and hash code __code.
       // Takes ownership of __n if insertion succeeds, throws otherwise.
       iterator
-      _M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			   __hash_code __code, __node_type* __n);
+      _M_insert_node(__multi_keys_t, __node_type* __hint,
+		     __hash_code __code, __node_type* __n);
 
       template<typename... _Args>
 	std::pair<iterator, bool>
-	_M_emplace(true_type, _Args&&... __args);
+	_M_emplace(__unique_keys_t, _Args&&... __args);
 
       template<typename... _Args>
 	iterator
-	_M_emplace(false_type __uk, _Args&&... __args)
-	{ return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
+	_M_emplace(__multi_keys_t __mks, _Args&&... __args)
+	{
+	  return _M_emplace(cend(), __mks,
+			    std::forward<_Args>(__args)...);
+	}
 
       // Emplace with hint, useless when keys are unique.
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, true_type __uk, _Args&&... __args)
-	{ return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
+	_M_emplace(const_iterator, __unique_keys_t __uks, _Args&&... __args)
+	{ return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
 
       template<typename... _Args>
 	iterator
-	_M_emplace(const_iterator, false_type, _Args&&... __args);
+	_M_emplace(const_iterator, __multi_keys_t, _Args&&... __args);
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
+	_M_insert(_Arg&&, const _NodeGenerator&, __unique_keys_t, size_type = 1);
 
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
-		  false_type __uk)
+		  __multi_keys_t __mks)
 	{
 	  return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
-			   __uk);
+			   __mks);
 	}
 
       // Insert with hint, not used when keys are unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&& __arg,
-		  const _NodeGenerator& __node_gen, true_type __uk)
+		  const _NodeGenerator& __node_gen, __unique_keys_t __uks)
 	{
-	  return
-	    _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
+	  return _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
 	}
 
       // Insert with hint when keys are not unique.
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(const_iterator, _Arg&&,
-		  const _NodeGenerator&, false_type);
+		  const _NodeGenerator&, __multi_keys_t);
 
       size_type
-      _M_erase(true_type, const key_type&);
+      _M_erase(__unique_keys_t, const key_type&);
 
       size_type
-      _M_erase(false_type, const key_type&);
+      _M_erase(__multi_keys_t, const key_type&);
 
       iterator
       _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
@@ -785,13 +789,13 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename... _Args>
 	__ireturn_type
 	emplace(_Args&&... __args)
-	{ return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
+	{ return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
 
       template<typename... _Args>
 	iterator
 	emplace_hint(const_iterator __hint, _Args&&... __args)
 	{
-	  return _M_emplace(__hint, __unique_keys(),
+	  return _M_emplace(__hint, __unique_keys{},
 			    std::forward<_Args>(__args)...);
 	}
 
@@ -808,7 +812,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       size_type
       erase(const key_type& __k)
-      { return _M_erase(__unique_keys(), __k); }
+      { return _M_erase(__unique_keys{}, __k); }
 
       iterator
       erase(const_iterator, const_iterator);
@@ -824,9 +828,10 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       // reserve, if present, comes from _Rehash_base.
 
 #if __cplusplus > 201402L
+    private:
       /// Re-insert an extracted node into a container with unique keys.
       insert_return_type
-      _M_reinsert_node(node_type&& __nh)
+      _M_reinsert_node(node_type&& __nh, __unique_keys_t __uks)
       {
 	insert_return_type __ret;
 	if (__nh.empty())
@@ -847,7 +852,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    else
 	      {
 		__ret.position
-		  = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr);
+		  = _M_insert_node(__uks, __bkt, __code, __nh._M_ptr);
 		__nh._M_ptr = nullptr;
 		__ret.inserted = true;
 	      }
@@ -855,9 +860,19 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __ret;
       }
 
+      /// Re-insert an extracted node into a container with unique keys.
+      insert_return_type
+      _M_reinsert_node(const_iterator, node_type&& __nh, __unique_keys_t __uks)
+      { return _M_reinsert_node(std::move(__nh), __uks); }
+
       /// Re-insert an extracted node into a container with equivalent keys.
       iterator
-      _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
+      _M_reinsert_node(node_type&& __nh, __multi_keys_t __mks)
+      { return _M_reinsert_node(cend(), std::move(__nh), __mks); }
+
+      iterator
+      _M_reinsert_node(const_iterator __hint, node_type&& __nh,
+		       __multi_keys_t __mks)
       {
 	if (__nh.empty())
 	  return end();
@@ -867,12 +882,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	const key_type& __k = __nh._M_key();
 	auto __code = this->_M_hash_code(__k);
 	auto __ret
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __nh._M_ptr);
 	__nh._M_ptr = nullptr;
 	return __ret;
       }
 
-    private:
       node_type
       _M_extract_node(size_t __bkt, __node_base* __prev_n)
       {
@@ -915,15 +929,36 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __nh;
       }
 
-      /// Merge from a compatible container into one with unique keys.
+      /// Re-insert an extracted node into a container.
+      auto
+      _M_reinsert_node(node_type&& __nh)
+	-> decltype(_M_reinsert_node(std::move(__nh), __unique_keys{}))
+      { return _M_reinsert_node(std::move(__nh), __unique_keys{}); }
+
+      /// Re-insert an extracted node into a container with hint.
+      auto
+      _M_reinsert_node(const_iterator __hint, node_type&& __nh)
+	-> decltype(_M_reinsert_node(__hint, std::move(__nh), __unique_keys{}))
+      { return _M_reinsert_node(__hint, std::move(__nh), __unique_keys{}); }
+
+      /// Merge from a compatible container.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_unique(_Compatible_Hashtable& __src) noexcept
+	_M_merge(_Compatible_Hashtable& __src) noexcept
 	{
 	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
+	  _M_merge(__unique_keys{}, __src);
+	}
+
+    private:
+      /// Merge from a compatible container into one with unique keys.
+      template<typename _Compatible_Hashtable>
+	void
+	_M_merge(__unique_keys_t __uks, _Compatible_Hashtable& __src) noexcept
+	{
 	  auto __n_elt = __src.size();
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
 	    {
@@ -934,8 +969,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	      if (_M_find_node(__bkt, __k, __code) == nullptr)
 		{
 		  auto __nh = __src.extract(__pos);
-		  _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr,
-					__n_elt);
+		  _M_insert_node(__uks, __bkt, __code, __nh._M_ptr, __n_elt);
 		  __nh._M_ptr = nullptr;
 		  __n_elt = 1;
 		}
@@ -947,24 +981,20 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       /// Merge from a compatible container into one with equivalent keys.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_multi(_Compatible_Hashtable& __src) noexcept
+	_M_merge(__multi_keys_t __mks, _Compatible_Hashtable& __src) noexcept
 	{
-	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
-	      node_type>, "Node types are compatible");
-	  __glibcxx_assert(get_allocator() == __src.get_allocator());
-
 	  this->reserve(size() + __src.size());
 	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
-	    _M_reinsert_node_multi(cend(), __src.extract(__i++));
+	    _M_reinsert_node(cend(), __src.extract(__i++), __mks);
 	}
 #endif // C++17
 
     private:
       // Helper rehash method used when keys are unique.
-      void _M_rehash_aux(size_type __bkt_count, true_type);
+      void _M_rehash_aux(size_type __bkt_count, __unique_keys_t);
 
       // Helper rehash method used when keys can be non-unique.
-      void _M_rehash_aux(size_type __bkt_count, false_type);
+      void _M_rehash_aux(size_type __bkt_count, __multi_keys_t);
 
       // Unconditionally change size of bucket array to n, restore
       // hash policy state to __state on exception.
@@ -1251,7 +1281,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _M_move_assign(_Hashtable&& __ht, false_type)
     {
       if (__ht._M_node_allocator() == this->_M_node_allocator())
-	_M_move_assign(std::move(__ht), true_type());
+	_M_move_assign(std::move(__ht), true_type{});
       else
 	{
 	  // Can't move memory, move elements then.
@@ -1664,7 +1694,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_emplace(true_type, _Args&&... __args)
+      _M_emplace(__unique_keys_t __uks, _Args&&... __args)
       -> pair<iterator, bool>
       {
 	// First build the node to get access to the hash code
@@ -1677,7 +1707,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  return std::make_pair(iterator(__p), false);
 
 	// Insert the node
-	auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	auto __pos = _M_insert_node(__uks, __bkt, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -1690,7 +1720,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_emplace(const_iterator __hint, false_type, _Args&&... __args)
+      _M_emplace(const_iterator __hint, __multi_keys_t __mks, _Args&&... __args)
       -> iterator
       {
 	// First build the node to get its hash code.
@@ -1699,7 +1729,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	__hash_code __code = this->_M_hash_code(__k);
 	auto __pos
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -1711,9 +1741,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_unique_node(const key_type& __k, size_type __bkt,
-			  __hash_code __code, __node_type* __node,
-			  size_type __n_elt)
+    _M_insert_node(__unique_keys_t, size_type __bkt, __hash_code __code,
+		   __node_type* __node, size_type __n_elt)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1724,7 +1753,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__do_rehash.first)
 	{
 	  _M_rehash(__do_rehash.second, __saved_state);
-	  __bkt = _M_bucket_index(__k, __code);
+	  __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
 	}
 
       this->_M_store_code(__node, __code);
@@ -1742,8 +1771,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_insert_multi_node(__node_type* __hint, const key_type& __k,
-			 __hash_code __code, __node_type* __node)
+    _M_insert_node(__multi_keys_t, __node_type* __hint,
+		   __hash_code __code, __node_type* __node)
     -> iterator
     {
       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
@@ -1754,6 +1783,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_rehash(__do_rehash.second, __saved_state);
 
       this->_M_store_code(__node, __code);
+      const key_type& __k = this->_M_extract()(__node->_M_v());
       size_type __bkt = _M_bucket_index(__k, __code);
 
       // Find the node before an equivalent one or use hint if it exists and
@@ -1797,8 +1827,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       auto
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
-		size_type __n_elt)
+      _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen,
+		__unique_keys_t __uks, size_type __n_elt)
       -> pair<iterator, bool>
       {
 	const key_type& __k = this->_M_extract()(__v);
@@ -1810,7 +1840,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
 	auto __pos
-	  = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt);
+	  = _M_insert_node(__uks, __bkt, __code, __node._M_node, __n_elt);
 	__node._M_node = nullptr;
 	return { __pos, true };
       }
@@ -1825,7 +1855,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
       _M_insert(const_iterator __hint, _Arg&& __v,
-		const _NodeGenerator& __node_gen, false_type)
+		const _NodeGenerator& __node_gen, __multi_keys_t __mks)
       -> iterator
       {
 	// First compute the hash code so that we don't do anything if it
@@ -1836,7 +1866,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
 	const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
 	auto __pos
-	  = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
+	  = _M_insert_node(__mks, __hint._M_cur, __code, __node._M_node);
 	__node._M_node = nullptr;
 	return __pos;
       }
@@ -1896,7 +1926,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_erase(true_type, const key_type& __k)
+    _M_erase(__unique_keys_t, const key_type& __k)
     -> size_type
     {
       __hash_code __code = this->_M_hash_code(__k);
@@ -1920,7 +1950,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     auto
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_erase(false_type, const key_type& __k)
+    _M_erase(__multi_keys_t, const key_type& __k)
     -> size_type
     {
       __hash_code __code = this->_M_hash_code(__k);
@@ -2065,7 +2095,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     {
       __try
 	{
-	  _M_rehash_aux(__bkt_count, __unique_keys());
+	  _M_rehash_aux(__bkt_count, __unique_keys{});
 	}
       __catch(...)
 	{
@@ -2084,7 +2114,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_rehash_aux(size_type __bkt_count, true_type)
+    _M_rehash_aux(size_type __bkt_count, __unique_keys_t)
     {
       __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
       __node_type* __p = _M_begin();
@@ -2126,7 +2156,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    _M_rehash_aux(size_type __bkt_count, false_type)
+    _M_rehash_aux(size_type __bkt_count, __multi_keys_t)
     {
       __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f5809c7443a..b9320506bb2 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -172,6 +172,14 @@  namespace __detail
 
   // Auxiliary types used for all instantiations of _Hashtable nodes
   // and iterators.
+  using __unique_keys_t = true_type;
+  using __multi_keys_t = false_type;
+
+  using __constant_iterators_t = true_type;
+  using __mutable_iterators_t = false_type;
+
+  using __hash_cached_t = true_type;
+  using __hash_not_cached_t = false_type;
 
   /**
    *  struct _Hashtable_traits
@@ -252,7 +260,7 @@  namespace __detail
   /**
    *  Primary template struct _Hash_node.
    */
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     struct _Hash_node;
 
   /**
@@ -261,7 +269,8 @@  namespace __detail
    *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, true> : _Hash_node_value_base<_Value>
+    struct _Hash_node<_Value, __hash_cached_t>
+    : _Hash_node_value_base<_Value>
     {
       std::size_t  _M_hash_code;
 
@@ -276,7 +285,8 @@  namespace __detail
    *  Base class is __detail::_Hash_node_value_base.
    */
   template<typename _Value>
-    struct _Hash_node<_Value, false> : _Hash_node_value_base<_Value>
+    struct _Hash_node<_Value, __hash_not_cached_t>
+    : _Hash_node_value_base<_Value>
     {
       _Hash_node*
       _M_next() const noexcept
@@ -284,7 +294,7 @@  namespace __detail
     };
 
   /// Base class for node iterators.
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     struct _Node_iterator_base
     {
       using __node_type = _Hash_node<_Value, _Cache_hash_code>;
@@ -299,14 +309,14 @@  namespace __detail
       { _M_cur = _M_cur->_M_next(); }
     };
 
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     inline bool
     operator==(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 	       const _Node_iterator_base<_Value, _Cache_hash_code >& __y)
     noexcept
     { return __x._M_cur == __y._M_cur; }
 
-  template<typename _Value, bool _Cache_hash_code>
+  template<typename _Value, typename _Cache_hash_code>
     inline bool
     operator!=(const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
 	       const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
@@ -314,12 +324,13 @@  namespace __detail
     { return __x._M_cur != __y._M_cur; }
 
   /// Node iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _Value, typename _Constant_iterators,
+	   typename _Cache_hash_code>
     struct _Node_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_Value, _Cache_hash_code>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_Value, _Cache_hash_code>;
       using __node_type = typename __base_type::__node_type;
 
     public:
@@ -327,10 +338,10 @@  namespace __detail
       typedef std::ptrdiff_t				difference_type;
       typedef std::forward_iterator_tag			iterator_category;
 
-      using pointer = typename std::conditional<__constant_iterators,
+      using pointer = typename std::conditional<_Constant_iterators::value,
 						const _Value*, _Value*>::type;
 
-      using reference = typename std::conditional<__constant_iterators,
+      using reference = typename std::conditional<_Constant_iterators::value,
 						  const _Value&, _Value&>::type;
 
       _Node_iterator() noexcept
@@ -365,12 +376,13 @@  namespace __detail
     };
 
   /// Node const_iterators, used to iterate through all the hashtable.
-  template<typename _Value, bool __constant_iterators, bool __cache>
+  template<typename _Value, typename _Constant_iterators,
+	   typename _Cache_hash_code>
     struct _Node_const_iterator
-    : public _Node_iterator_base<_Value, __cache>
+    : public _Node_iterator_base<_Value, _Cache_hash_code>
     {
     private:
-      using __base_type = _Node_iterator_base<_Value, __cache>;
+      using __base_type = _Node_iterator_base<_Value, _Cache_hash_code>;
       using __node_type = typename __base_type::__node_type;
 
     public:
@@ -388,8 +400,8 @@  namespace __detail
       _Node_const_iterator(__node_type* __p) noexcept
       : __base_type(__p) { }
 
-      _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
-			   __cache>& __x) noexcept
+      _Node_const_iterator(const _Node_iterator<_Value, _Constant_iterators,
+						_Cache_hash_code>& __x) noexcept
       : __base_type(__x._M_cur) { }
 
       reference
@@ -641,25 +653,25 @@  namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Unique_keys = _Traits::__unique_keys::value>
+	   typename = typename _Traits::__unique_keys>
     struct _Map_base { };
 
-  /// Partial specialization, __unique_keys set to false.
+  /// Partial specialization, keys are not unique.
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>
     {
       using mapped_type = typename std::tuple_element<1, _Pair>::type;
     };
 
-  /// Partial specialization, __unique_keys set to true.
+  /// Partial specialization, keys are unique.
   template<typename _Key, typename _Pair, typename _Alloc, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>
     {
     private:
       using __hashtable_base = __detail::_Hashtable_base<_Key, _Pair,
@@ -699,7 +711,7 @@  namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     operator[](const key_type& __k)
     -> mapped_type&
     {
@@ -716,7 +728,7 @@  namespace __detail
 	std::tuple<>()
       };
       auto __pos
-	= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	= __h->_M_insert_node(__unique_keys_t{}, __bkt, __code, __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -726,7 +738,7 @@  namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     operator[](key_type&& __k)
     -> mapped_type&
     {
@@ -743,7 +755,7 @@  namespace __detail
 	std::tuple<>()
       };
       auto __pos
-	= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	= __h->_M_insert_node(__unique_keys_t{}, __bkt, __code, __node._M_node);
       __node._M_node = nullptr;
       return __pos->second;
     }
@@ -753,7 +765,7 @@  namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     at(const key_type& __k)
     -> mapped_type&
     {
@@ -772,7 +784,7 @@  namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     auto
     _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     at(const key_type& __k) const
     -> const mapped_type&
     {
@@ -810,10 +822,12 @@  namespace __detail
       using iterator = typename __hashtable_base::iterator;
       using const_iterator =  typename __hashtable_base::const_iterator;
       using size_type = typename __hashtable_base::size_type;
-
-      using __unique_keys = typename __hashtable_base::__unique_keys;
       using __ireturn_type = typename __hashtable_base::__ireturn_type;
-      using __node_type = _Hash_node<_Value, _Traits::__hash_cached::value>;
+
+      using __unique_keys = typename _Traits::__unique_keys;
+      using __hash_cached = typename _Traits::__hash_cached;
+
+      using __node_type = _Hash_node<_Value, __hash_cached>;
       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
       using __node_gen_type = _AllocNode<__node_alloc_type>;
 
@@ -824,12 +838,12 @@  namespace __detail
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, true_type);
+			const _NodeGetter&, __unique_keys_t);
 
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, false_type);
+			const _NodeGetter&, __multi_keys_t);
 
     public:
       __ireturn_type
@@ -837,7 +851,7 @@  namespace __detail
       {
 	__hashtable& __h = _M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(__v, __node_gen, __unique_keys());
+	return __h._M_insert(__v, __node_gen, __unique_keys{});
       }
 
       iterator
@@ -845,7 +859,7 @@  namespace __detail
       {
 	__hashtable& __h = _M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);	
-	return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
+	return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
       }
 
       void
@@ -858,7 +872,7 @@  namespace __detail
 	{
 	  __hashtable& __h = _M_conjure_hashtable();
 	  __node_gen_type __node_gen(__h);
-	  return _M_insert_range(__first, __last, __node_gen, __unique_keys());
+	  return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
 	}
     };
 
@@ -871,7 +885,7 @@  namespace __detail
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, true_type)
+		      const _NodeGetter& __node_gen, __unique_keys_t __uks)
       {
 	size_type __n_elt = __detail::__distance_fw(__first, __last);
 	if (__n_elt == 0)
@@ -880,8 +894,7 @@  namespace __detail
 	__hashtable& __h = _M_conjure_hashtable();
 	for (; __first != __last; ++__first)
 	  {
-	    if (__h._M_insert(*__first, __node_gen, __unique_keys(),
-			      __n_elt).second)
+	    if (__h._M_insert(*__first, __node_gen, __uks, __n_elt).second)
 	      __n_elt = 1;
 	    else if (__n_elt != 1)
 	      --__n_elt;
@@ -897,7 +910,7 @@  namespace __detail
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
 		    _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, false_type)
+		      const _NodeGetter& __node_gen, __multi_keys_t __mks)
       {
 	using __rehash_type = typename __hashtable::__rehash_type;
 	using __rehash_state = typename __hashtable::__rehash_state;
@@ -918,7 +931,7 @@  namespace __detail
 	  __h._M_rehash(__do_rehash.second, __saved_state);
 
 	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __unique_keys());
+	  __h._M_insert(*__first, __node_gen, __mks);
       }
 
   /**
@@ -931,7 +944,7 @@  namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Constant_iterators = _Traits::__constant_iterators::value>
+	   typename = typename _Traits::__constant_iterators>
     struct _Insert;
 
   /// Specialization.
@@ -940,7 +953,7 @@  namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, true>
+		   _RehashPolicy, _Traits, __constant_iterators_t>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
@@ -968,7 +981,7 @@  namespace __detail
       {
 	__hashtable& __h = this->_M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
-	return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
+	return __h._M_insert(std::move(__v), __node_gen, __unique_keys{});
       }
 
       iterator
@@ -977,7 +990,7 @@  namespace __detail
 	__hashtable& __h = this->_M_conjure_hashtable();
 	__node_gen_type __node_gen(__h);
 	return __h._M_insert(__hint, std::move(__v), __node_gen,
-			     __unique_keys());
+			     __unique_keys{});
       }
     };
 
@@ -987,7 +1000,7 @@  namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
-		   _RehashPolicy, _Traits, false>
+		   _RehashPolicy, _Traits, __mutable_iterators_t>
     : public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 			   _H1, _H2, _Hash, _RehashPolicy, _Traits>
     {
@@ -1018,7 +1031,7 @@  namespace __detail
 	insert(_Pair&& __v)
 	{
 	  __hashtable& __h = this->_M_conjure_hashtable();
-	  return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
+	  return __h._M_emplace(__unique_keys{}, std::forward<_Pair>(__v));
 	}
 
       template<typename _Pair, typename = _IFconsp<_Pair>>
@@ -1026,7 +1039,7 @@  namespace __detail
 	insert(const_iterator __hint, _Pair&& __v)
 	{
 	  __hashtable& __h = this->_M_conjure_hashtable();
-	  return __h._M_emplace(__hint, __unique_keys(),
+	  return __h._M_emplace(__hint, __unique_keys{},
 				std::forward<_Pair>(__v));
 	}
    };
@@ -1146,7 +1159,7 @@  namespace __detail
    */
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __cache_hash_code>
+	   typename _Cache_hash_code>
     struct _Local_iterator_base;
 
   /**
@@ -1171,14 +1184,15 @@  namespace __detail
    */
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __cache_hash_code>
+	   typename _Cache_hash_code>
     struct _Hash_code_base;
 
   /// Specialization: ranged hash function, no caching hash codes.  H1
   /// and H2 are provided but ignored.  We define a dummy hash code type.
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			   __hash_not_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _Hash>
     {
@@ -1188,7 +1202,7 @@  namespace __detail
 
     protected:
       typedef void* 					__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<_Value, __hash_not_cached_t>	__node_type;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1244,7 +1258,8 @@  namespace __detail
   /// and no definition.
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
-    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
+    struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
+			   __hash_cached_t>;
 
   /// Specialization: hash function and range-hashing function, no
   /// caching of hash codes.
@@ -1252,7 +1267,7 @@  namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
-			   _Default_ranged_hash, false>
+			   _Default_ranged_hash, __hash_not_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
       private _Hashtable_ebo_helper<2, _H2>
@@ -1264,7 +1279,8 @@  namespace __detail
 
       // Gives the local iterator implementation access to _M_bucket_index().
       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, false>;
+					 _Default_ranged_hash,
+					 __hash_not_cached_t>;
 
     public:
       typedef _H1 					hasher;
@@ -1275,7 +1291,7 @@  namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, false>			__node_type;
+      typedef _Hash_node<_Value, __hash_not_cached_t>	__node_type;
 
       // We need the default constructor for the local iterators and _Hashtable
       // default constructor.
@@ -1339,7 +1355,7 @@  namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2>
     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
-			   _Default_ranged_hash, true>
+			   _Default_ranged_hash, __hash_cached_t>
     : private _Hashtable_ebo_helper<0, _ExtractKey>,
       private _Hashtable_ebo_helper<1, _H1>,
       private _Hashtable_ebo_helper<2, _H2>
@@ -1347,7 +1363,7 @@  namespace __detail
     private:
       // Gives the local iterator implementation access to _M_h2().
       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
-					 _Default_ranged_hash, true>;
+					 _Default_ranged_hash, __hash_cached_t>;
 
       using __ebo_extract_key = _Hashtable_ebo_helper<0, _ExtractKey>;
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
@@ -1362,7 +1378,7 @@  namespace __detail
 
     protected:
       typedef std::size_t 				__hash_code;
-      typedef _Hash_node<_Value, true>			__node_type;
+      typedef _Hash_node<_Value, __hash_cached_t>	__node_type;
 
       // We need the default constructor for _Hashtable default constructor.
       _Hash_code_base() = default;
@@ -1421,17 +1437,18 @@  namespace __detail
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, true>
+				_H1, _H2, _Hash, __hash_cached_t>
     : private _Hashtable_ebo_helper<0, _H2>
     {
     protected:
       using __base_type = _Hashtable_ebo_helper<0, _H2>;
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, true>;
+					       _H1, _H2, _Hash,
+					       __hash_cached_t>;
 
       _Local_iterator_base() = default;
       _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, true>* __p,
+			   _Hash_node<_Value, __hash_cached_t>* __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base._M_h2()),
 	_M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
@@ -1450,7 +1467,7 @@  namespace __detail
 	  }
       }
 
-      _Hash_node<_Value, true>*  _M_cur;
+      _Hash_node<_Value, __hash_cached_t>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
@@ -1497,23 +1514,25 @@  namespace __detail
 	   typename _H1, typename _H2, typename _Hash>
     using __hash_code_for_local_iter
       = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
-					   _H1, _H2, _Hash, false>>;
+					   _H1, _H2, _Hash,
+					   __hash_not_cached_t>>;
 
   // Partial specialization used when hash codes are not cached
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
-				_H1, _H2, _Hash, false>
+				_H1, _H2, _Hash, __hash_not_cached_t>
     : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
     {
     protected:
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, false>;
+					       _H1, _H2, _Hash,
+					       __hash_not_cached_t>;
 
       _Local_iterator_base() : _M_bucket_count(-1) { }
 
       _Local_iterator_base(const __hash_code_base& __base,
-			   _Hash_node<_Value, false>* __p,
+			   _Hash_node<_Value, __hash_not_cached_t>* __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
       { _M_init(__base); }
@@ -1558,7 +1577,7 @@  namespace __detail
 	  }
       }
 
-      _Hash_node<_Value, false>*  _M_cur;
+      _Hash_node<_Value, __hash_not_cached_t>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
 
@@ -1578,41 +1597,43 @@  namespace __detail
     };
 
   template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _Cache_hash_code>
     inline bool
     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
+	       _H1, _H2, _Hash, _Cache_hash_code>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
+	       _H1, _H2, _Hash, _Cache_hash_code>& __y)
     { return __x._M_curr() == __y._M_curr(); }
 
   template<typename _Key, typename _Value, typename _ExtractKey,
-	   typename _H1, typename _H2, typename _Hash, bool __cache>
+	   typename _H1, typename _H2, typename _Hash,
+	   typename _Cache_hash_code>
     inline bool
     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __x,
+	       _H1, _H2, _Hash, _Cache_hash_code>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
-					  _H1, _H2, _Hash, __cache>& __y)
+	       _H1, _H2, _Hash, _Cache_hash_code>& __y)
     { return __x._M_curr() != __y._M_curr(); }
 
   /// local iterators
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __constant_iterators, bool __cache>
+	   typename _Constant_iterators, typename _Cache_hash_code>
     struct _Local_iterator
     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+				  _H1, _H2, _Hash, _Cache_hash_code>
     {
     private:
       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+					       _H1, _H2, _Hash, _Cache_hash_code>;
       using __hash_code_base = typename __base_type::__hash_code_base;
     public:
       typedef _Value					value_type;
-      typedef typename std::conditional<__constant_iterators,
+      typedef typename std::conditional<_Constant_iterators::value,
 					const _Value*, _Value*>::type
 						       pointer;
-      typedef typename std::conditional<__constant_iterators,
+      typedef typename std::conditional<_Constant_iterators::value,
 					const _Value&, _Value&>::type
 						       reference;
       typedef std::ptrdiff_t				difference_type;
@@ -1621,7 +1642,7 @@  namespace __detail
       _Local_iterator() = default;
 
       _Local_iterator(const __hash_code_base& __base,
-		      _Hash_node<_Value, __cache>* __n,
+		      _Hash_node<_Value, _Cache_hash_code>* __n,
 		      std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
@@ -1653,14 +1674,15 @@  namespace __detail
   /// local const_iterators
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash,
-	   bool __constant_iterators, bool __cache>
+	   typename _Constant_iterators, typename _Cache_hash_code>
     struct _Local_const_iterator
     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
-				  _H1, _H2, _Hash, __cache>
+				  _H1, _H2, _Hash, _Cache_hash_code>
     {
     private:
       using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
-					       _H1, _H2, _Hash, __cache>;
+					       _H1, _H2, _Hash,
+					       _Cache_hash_code>;
       using __hash_code_base = typename __base_type::__hash_code_base;
 
     public:
@@ -1673,15 +1695,15 @@  namespace __detail
       _Local_const_iterator() = default;
 
       _Local_const_iterator(const __hash_code_base& __base,
-			    _Hash_node<_Value, __cache>* __n,
+			    _Hash_node<_Value, _Cache_hash_code>* __n,
 			    std::size_t __bkt, std::size_t __bkt_count)
       : __base_type(__base, __n, __bkt, __bkt_count)
       { }
 
       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
 						  _H1, _H2, _Hash,
-						  __constant_iterators,
-						  __cache>& __x)
+						  _Constant_iterators,
+						  _Cache_hash_code>& __x)
       : __base_type(__x)
       { }
 
@@ -1724,7 +1746,7 @@  namespace __detail
 	   typename _H1, typename _H2, typename _Hash, typename _Traits>
   struct _Hashtable_base
   : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
-			   _Traits::__hash_cached::value>,
+			   typename _Traits::__hash_cached>,
     private _Hashtable_ebo_helper<0, _Equal>
   {
   public:
@@ -1741,29 +1763,29 @@  namespace __detail
 
     using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
 					     _H1, _H2, _Hash,
-					     __hash_cached::value>;
+					     __hash_cached>;
 
     using __hash_code = typename __hash_code_base::__hash_code;
     using __node_type = typename __hash_code_base::__node_type;
 
     using iterator = __detail::_Node_iterator<value_type,
-					      __constant_iterators::value,
-					      __hash_cached::value>;
+					      __constant_iterators,
+					      __hash_cached>;
 
     using const_iterator = __detail::_Node_const_iterator<value_type,
-						   __constant_iterators::value,
-						   __hash_cached::value>;
+						   __constant_iterators,
+						   __hash_cached>;
 
     using local_iterator = __detail::_Local_iterator<key_type, value_type,
-						  _ExtractKey, _H1, _H2, _Hash,
-						  __constant_iterators::value,
-						     __hash_cached::value>;
+						   _ExtractKey, _H1, _H2, _Hash,
+						     __constant_iterators,
+						     __hash_cached>;
 
     using const_local_iterator = __detail::_Local_const_iterator<key_type,
 								 value_type,
 					_ExtractKey, _H1, _H2, _Hash,
-					__constant_iterators::value,
-					__hash_cached::value>;
+					__constant_iterators,
+					__hash_cached>;
 
     using __ireturn_type = typename std::conditional<__unique_keys::value,
 						     std::pair<iterator, bool>,
@@ -1780,10 +1802,10 @@  namespace __detail
       };
 
     template<typename _Ptr2>
-      struct _Equal_hash_code<_Hash_node<_Ptr2, true>>
+      struct _Equal_hash_code<_Hash_node<_Ptr2, __hash_cached_t>>
       {
        static bool
-       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, true>& __n)
+       _S_equals(__hash_code __c, const _Hash_node<_Ptr2, __hash_cached_t>& __n)
        { return __c == __n._M_hash_code; }
       };
 
@@ -1886,7 +1908,7 @@  namespace __detail
 	   typename _ExtractKey, typename _Equal,
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits,
-	   bool _Unique_keys = _Traits::__unique_keys::value>
+	   typename = typename _Traits::__unique_keys>
     struct _Equality;
 
   /// Specialization.
@@ -1895,7 +1917,7 @@  namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>
     {
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 				     _H1, _H2, _Hash, _RehashPolicy, _Traits>;
@@ -1910,7 +1932,7 @@  namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     bool
     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __unique_keys_t>::
     _M_equal(const __hashtable& __other) const
     {
       const __hashtable* __this = static_cast<const __hashtable*>(this);
@@ -1933,7 +1955,7 @@  namespace __detail
 	   typename _H1, typename _H2, typename _Hash,
 	   typename _RehashPolicy, typename _Traits>
     struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-		     _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
+		     _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>
     : public _Equality_base
     {
       using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
@@ -1949,7 +1971,7 @@  namespace __detail
 	   typename _RehashPolicy, typename _Traits>
     bool
     _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
-	      _H1, _H2, _Hash, _RehashPolicy, _Traits, false>::
+	      _H1, _H2, _Hash, _RehashPolicy, _Traits, __multi_keys_t>::
     _M_equal(const __hashtable& __other) const
     {
       const __hashtable* __this = static_cast<const __hashtable*>(this);
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index b8243a73445..49c175a90be 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -439,8 +439,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 
 #define __cpp_lib_unordered_map_try_emplace 201411
       /**
@@ -866,7 +866,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -879,7 +879,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1659,12 +1659,12 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       iterator
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
+      { return _M_h._M_reinsert_node(std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
       insert(const_iterator __hint, node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)); }
 #endif // C++17
 
       //@{
@@ -1760,7 +1760,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1774,7 +1774,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index 8ebcaf40263..855579ee623 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -500,8 +500,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /// Re-insert an extracted node.
       iterator
-      insert(const_iterator, node_type&& __nh)
-      { return _M_h._M_reinsert_node(std::move(__nh)).position; }
+      insert(const_iterator __hint, node_type&& __nh)
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; }
 #endif // C++17
 
       //@{
@@ -595,7 +595,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -608,7 +608,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
 	{
 	  using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
-	  _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1288,12 +1288,12 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       /// Re-insert an extracted node.
       iterator
       insert(node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
+      { return _M_h._M_reinsert_node(std::move(__nh)); }
 
       /// Re-insert an extracted node.
       iterator
       insert(const_iterator __hint, node_type&& __nh)
-      { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
+      { return _M_h._M_reinsert_node(__hint, std::move(__nh)); }
 #endif // C++17
 
       //@{
@@ -1393,7 +1393,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>
@@ -1407,7 +1407,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	{
 	  using _Merge_helper
 	    = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
-	  _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+	  _M_h._M_merge(_Merge_helper::_S_get_table(__source));
 	}
 
       template<typename _H2, typename _P2>