[Hashtable,0/6] Code review
diff mbox

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. UTC
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

Patch
diff mbox

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>