[libc++] Don't call key_eq in unordered_map/set rehashing routine

[itrofimow]

Summary

As of now containers key_eq might get called when rehashing happens, which is redundant for unique keys containers.

[itrofimow]

+ clang-format

[jloser]

I recommend against clang-format everywhere here. When uploading the patch, you can specify --nolint to arc so it won't complain about the lack of clang-formatting a particular changeset. The noise ratio compared with the actual content change here is high in my opinion.

[itrofimow]

In D128021#3591054, @jloser wrote:

I recommend against clang-format everywhere here. When uploading the patch, you can specify --nolint to arc so it won't complain about the lack of clang-formatting a particular changeset. The noise ratio compared with the actual content change here is high in my opinion.

Thanks for the suggestion, i definitely will follow - clang-format goes crazy with these files

[philnik]

I agree with @jloser that this is a lot of noise. Please either ignore clang-format for now or provide a patch to only reformat the parts you change here and rebase this patch. More important for now: Please provide appropriate benchmarks in libcxx/benchmarks for this if we don't have any and provide the benchmark results.

[Mordante]

Thanks for your contribution! I'll have another look after all comment have been addressed.

libcxx/include/__hash_table

863–869

Can you add some comment why these traits are needed? The reason is in the commit message, but not in the code.

865

Nowadays we tend to use using instead of typedef. This works for all supported compilers in C++98/C++03 mode.

868

I'm not fond of name _Traits it very generic. How about _UniqueKeys?

libcxx/include/unordered_map

1034

As an extension we add unordered_map to C++03.

[itrofimow]

cleanup, + benchmarks

[jloser]

libcxx/include/__hash_table

863

Nit: s/reduntand/redundant

868

FWIW, I personally preferred the traits class name holding a (member or type) to denote the one trait of interest: unique_keys. I don't feel too strongly, but I feel it leads to a more open design generally.

2099–2100

Question: what's the libc++ stance for something like this which could be if constexpr in C++17 or later? Is it worth writing

#if _LIBCPP_STD_VER >= 17
if constexpr
#else
if
#endif
(!UniqueKeys::Value) {

I suspect the answer is just writing if for all standards modes and just letting the compiler realize it's always a constant value now up-front.

[itrofimow]

libcxx/benchmarks/unordered_set_operations.bench.cpp

311 ↗

(On Diff #438077)

This is with the patch:
BM_Rehash/unordered_set_string_arg/1024 44848 ns 44846 ns 96172

This is on trunk:
BM_Rehash/unordered_set_string_arg/1024 55711 ns 55706 ns 74198

full output: https://pastebin.com/7DMcNTna

This benchmark doesn't mean there is an immense speedup in rehashing, it just shows that there is a speedup - max_load_factor(3) was used to be sure that there will be collisions and key_eq branch in rehashing would be hit. So this just measures how long it takes to compare long random strings, but with the patch we don't compare them at all.

[itrofimow]

Can some please help me with clang-format builds failing?
This is what i used to update the patch arc diff HEAD~ --update D128021 --nolint, but format build are still failing.
What should i do to fix that?

[philnik]

This looks pretty good so far, but I'd like to see a full set of benchmarks before approving. BTW it's really stupid that we have all the member function definitions out of line. It makes this diff so much larger than it needs to be.

In D128021#3593737, @itrofimow wrote:

Can some please help me with clang-format builds failing?
This is what i used to update the patch arc diff HEAD~ --update D128021 --nolint, but format build are still failing.
What should i do to fix that?

You can ignore the clang-format runner. It's just soft-failing. Your problem with the CI currently is that you've got some non-ASCII symbols in your patch. That's why Generated output fails.

libcxx/benchmarks/ContainerBenchmarks.h

143 ↗

(On Diff #438077)

benchmark::DoNotOptimize(c) should be more than enough. This doesn't allow the compiler to optimize anything from the container.

libcxx/benchmarks/unordered_set_operations.bench.cpp

311 ↗

(On Diff #438077)

Could you provide the results of a full set of input data (i.e. elements other than string and other sizes)? I don't think you cherry-picked, but having only a single data point smells like it. Since this patch also affects unordered_map, unordered_multimap and unordered_multiset I'd also like to see benchmarks for those (the multi-version are optional, but a nice to have).

libcxx/include/__hash_table

862–863

I don't think this is necessary. Just use integral_constant<bool, {true, false}> where __hash_table is used or use a NTTP instead.

2099–2100

It's definitely not worth it. This makes the code a lot less readable for a minor to non-existent improvement in compile times.

2099–2100

Could you indent this properly?

[Mordante]

One request, when you address a review comment, can you check the "done" button this makes reviewing easier.

I had a look at the changes and I'm wondering about the impact on the size of the binary. You add one template argument to "only" adjust the __rehash function. This means the __hash_table for unordered_map<K, V> and unordered_multimap<K, V> will be different after this change. Could you provide some numbers regarding how much the binary will grow when an applications uses both unordered_map<K, V> and unordered_multimap<K, V>`?

libcxx/include/__hash_table

2099–2100

Question: what's the libc++ stance for something like this which could be if constexpr in C++17 or later? Is it worth writing

#if _LIBCPP_STD_VER >= 17
if constexpr
#else
if
#endif
(!UniqueKeys::Value) {

I suspect the answer is just writing if for all standards modes and just letting the compiler realize it's always a constant value now up-front.

There's no need for the #if LIBCPP_STD_VER >= 17, if _LIBCPP_CONSTEXPR_AFTER_CXX14 (!UniqueKeys::Value) { should work.

libcxx/include/ext/hash_map

490 ↗

(On Diff #438077)

There's no need for std:: here.

[itrofimow]

Thank you guys for the valuable feedback. I'll get back to this near the end of the upcoming week

[itrofimow]

code review fixes

[itrofimow]

So i got some benchmarks: unordered_set_benches

And they didn't make any sense for BM_FindRehash: how could my changes affect it that much, when they don't even touch ::find?
After some profiling i found out that branch misprediction in std::equal_to increases up to x2 from ~11% to 23%, with overall mispediction being close to 4%.

Changing initial rehash in BM_FindRehash from 8 to 7 leads to this: unordered_set_benches, which is what i expected to be,
but i still have no idea what happens in original version.

libcxx/include/__hash_table

862–863

I feel like that would make __hash_table usage way less readable: is true self explanatory enough in __hash_table<Key, Hash, Eq, Alloc, true>?

libcxx/include/ext/hash_map

490 ↗

(On Diff #438077)

doesn't compile without it

[itrofimow]

In D128021#3593922, @Mordante wrote:

One request, when you address a review comment, can you check the "done" button this makes reviewing easier.

I had a look at the changes and I'm wondering about the impact on the size of the binary. You add one template argument to "only" adjust the __rehash function. This means the __hash_table for unordered_map<K, V> and unordered_multimap<K, V> will be different after this change. Could you provide some numbers regarding how much the binary will grow when an applications uses both unordered_map<K, V> and unordered_multimap<K, V>`?

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

[Mordante]

In D128021#3603708, @itrofimow wrote:

In D128021#3593922, @Mordante wrote:

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

Thanks! Can you provide the output of the size command instead of the ls command for both binaries?

[itrofimow]

In D128021#3603897, @Mordante wrote:

In D128021#3603708, @itrofimow wrote:

In D128021#3593922, @Mordante wrote:

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

Thanks! Can you provide the output of the size command instead of the ls command for both binaries?

root@adelaide:~/tmp# size binary_size_*

 text	   data	    bss	    dec	    hex	filename
10109	    744	      8	  10861	   2a6d	binary_size_main
11334	    744	      8	  12086	   2f36	binary_size_patch

[itrofimow]

Gently pinging this

[Mordante]

In D128021#3604428, @itrofimow wrote:

In D128021#3603897, @Mordante wrote:

In D128021#3603708, @itrofimow wrote:

In D128021#3593922, @Mordante wrote:

Would this example be enough?
I could've messed up compile flags, and guidance would be appreciated if i did so

Thanks! Can you provide the output of the size command instead of the ls command for both binaries?

root@adelaide:~/tmp# size binary_size_*

 text	   data	    bss	    dec	    hex	filename
10109	    744	      8	  10861	   2a6d	binary_size_main
11334	    744	      8	  12086	   2f36	binary_size_patch

Thanks. This gives more insight. For the ls the patched version is smaller, but here patched version is bigger; which matches my expectations. I'm not happy with the 1 KB increment of the text size. This price will be paid for every type.

I want to have a closer look at this myself and see whether there's a better solution that gives the performance improvement with a smaller text size overhead.

libcxx/benchmarks/ContainerBenchmarks.h

140 ↗

(On Diff #439213)

Please don't use auto when the type isn't clear, same for the bucket_count.

[Mordante]

I had a look at the code and I wonder whether a different approach might be better. Instead of adding a template argument we change __rehash to two function __rehash_unique and __rehash_multi. This seems the approach already taken for other functions in the __hash_table class.

This means the public functions rehash and resize also need two versions. The other functions calling rehash are already specific for unique and multi. I think we can keep the unique key argument on these rehash functions. So I would suggest something along the lines of.

// These were rehash, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __rehash_unique(size_type __n) { __rehash<true>(__n); }
_LIBCPP_INLINE_VISIBILITY void __rehash_multi(size_type __n) { __rehash<false>(__n); }

// These were reserve, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __reserve_unique(size_type __n)
      {__rehash_unique(static_cast<size_type>(ceil(__n / max_load_factor())));}                                              
_LIBCPP_INLINE_VISIBILITY void __reserve_multi(size_type __n)
      {__rehash_multi(static_cast<size_type>(ceil(__n / max_load_factor())));}


// rename __rehash to __do_rehash and make it templated
template<class _UniqueKeys>
void __do_rehash(size_type __n);

// rename rehash to __rehash, make it private and make it templated
template<class _UniqueKeys>
void __rehash(size_type __n);

Then we can keep the templated rehashing you added but only have the template arguments on these two function instead of the entire class.

WDYT?

[itrofimow]

In D128021#3613221, @Mordante wrote:

I had a look at the code and I wonder whether a different approach might be better. Instead of adding a template argument we change __rehash to two function __rehash_unique and __rehash_multi. This seems the approach already taken for other functions in the __hash_table class.

This means the public functions rehash and resize also need two versions. The other functions calling rehash are already specific for unique and multi. I think we can keep the unique key argument on these rehash functions. So I would suggest something along the lines of.

// These were rehash, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __rehash_unique(size_type __n) { __rehash<true>(__n); }
_LIBCPP_INLINE_VISIBILITY void __rehash_multi(size_type __n) { __rehash<false>(__n); }

// These were reserve, keep them public and adjust the callers
_LIBCPP_INLINE_VISIBILITY void __reserve_unique(size_type __n)
      {__rehash_unique(static_cast<size_type>(ceil(__n / max_load_factor())));}                                              
_LIBCPP_INLINE_VISIBILITY void __reserve_multi(size_type __n)
      {__rehash_multi(static_cast<size_type>(ceil(__n / max_load_factor())));}


// rename __rehash to __do_rehash and make it templated
template<class _UniqueKeys>
void __do_rehash(size_type __n);

// rename rehash to __rehash, make it private and make it templated
template<class _UniqueKeys>
void __rehash(size_type __n);

Then we can keep the templated rehashing you added but only have the template arguments on these two function instead of the entire class.

WDYT?

If binary size is a concern i definitely like this approach more

[itrofimow]

review fixes, updated benchmarks (https://pastebin.com/raw/AF0fa9VJ)

[itrofimow]

libcxx/benchmarks/ContainerBenchmarks.h

140 ↗

(On Diff #439213)

Type here differs for different benchmark registrations, so it would be some decltype otherwise.

I could change bucket_count to be a size_t if you insist, but i feel like it's not only clearly size_t, but also the same type rehash takes anyway

libcxx/benchmarks/unordered_set_operations.bench.cpp

311 ↗

(On Diff #438077)

Strangely enough i couldn't find any unordered_map/multimap/multiset benchmarks, and i'm not sure i am familiar enough with this codebase to write a comprehensive ones from scratch

[itrofimow]

Trying to force a rebuild

[Mordante]

I think this patch is getting close to be done!

I see some small issues.
Can you provide the new binary sizes, I would like to see the overhead of this new approach.
Can you upload the patch with the complete context? Without context it's hard to validate whether the changes to unordered_set and unordered_map are correct. (I assume they are, but I want to validate.)

libcxx/benchmarks/unordered_set_operations.bench.cpp

110 ↗

(On Diff #441901)

This function is confusion. It's called slow, but when the sizes don't match they function bails out quickly. Else it compares all elements. Some comment would be helpful.

114 ↗

(On Diff #441901)

please put eq &= lhs[i] == rhs[i]; on its own line.

libcxx/include/__hash_table

1155

please us __ugly function names.

[itrofimow]

binary size after changes: https://pastebin.com/raw/z23mLN93

[Mordante]

In D128021#3627047, @itrofimow wrote:

binary size after changes: https://pastebin.com/raw/z23mLN93

 text	   data	    bss	    dec	    hex	filename
10323	    744	      8	  11075	   2b43	binary_size_main
10996	    744	      8	  11748	   2de4	binary_size_patch

Thanks! I like these numbers better! This about half of the size overhead of the previous version.
I assume the main values have changed due to rebasing, right?

[itrofimow]

In D128021#3627048, @Mordante wrote:

In D128021#3627047, @itrofimow wrote:

binary size after changes: https://pastebin.com/raw/z23mLN93

 text	   data	    bss	    dec	    hex	filename
10323	    744	      8	  11075	   2b43	binary_size_main
10996	    744	      8	  11748	   2de4	binary_size_patch

Thanks! I like these numbers better! This about half of the size overhead of the previous version.
I assume the main values have changed due to rebasing, right?

I did rebase, however i think main values changed due to me compiling on a different machine.
Not sure if i understand the size command output completely, but this time binary takes only ~150 bytes more on disk versus ~4.5Kb in the previous version

Smh about losing context - updated the patch via web interface, will fix remaining issues and upload the patch via arc this time

[itrofimow]

cr fixes

[itrofimow]

rebase on main

[Mordante]

In D128021#3627069, @itrofimow wrote:

In D128021#3627048, @Mordante wrote:

In D128021#3627047, @itrofimow wrote:

binary size after changes: https://pastebin.com/raw/z23mLN93

 text	   data	    bss	    dec	    hex	filename
10323	    744	      8	  11075	   2b43	binary_size_main
10996	    744	      8	  11748	   2de4	binary_size_patch

Thanks! I like these numbers better! This about half of the size overhead of the previous version.
I assume the main values have changed due to rebasing, right?

I did rebase, however i think main values changed due to me compiling on a different machine.
Not sure if i understand the size command output completely, but this time binary takes only ~150 bytes more on disk versus ~4.5Kb in the previous version

The size command gives more insight in the real binary size. The file on disk contains a lot of additional information, like debug information, information needed for the dynamic linker, etc.

LGTM modulo some small nits. I'll leave the final approval to @philnik.

libcxx/benchmarks/ContainerBenchmarks.h

140 ↗

(On Diff #439213)

I think it's good to use real types when possible.

libcxx/benchmarks/unordered_set_operations.bench.cpp

113 ↗

(On Diff #442518)

Thanks this clarifies it!
You could consider adding an assert that the sizes are equal.

[philnik]

LGTM.

libcxx/include/__hash_table

 
 inline _LIBCPP_INLINE_VISIBILITY
 size_t
 __next_hash_pow2(size_t __n)
 {
     return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n-1)));
 }
 
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+class __hash_table;
 
 template <class _NodePtr>      class _LIBCPP_TEMPLATE_VIS __hash_iterator;
 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 template <class _NodePtr>      class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 

 typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
 __diagnose_unordered_container_requirements(int);
 
 // This dummy overload is used so that the compiler won't emit a spurious
 // "no matching function for call to __diagnose_unordered_xxx" diagnostic
 // when the overload above causes a hard error.
 template <class _Key, class _Hash, class _Equal>
 int __diagnose_unordered_container_requirements(void*);
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-class __hash_table
-{
+template <bool _Unique_Keys>
+struct __hash_table_traits {
+  typedef integral_constant<bool, _Unique_Keys> __unique_keys;
+};
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+class __hash_table {
 public:
     typedef _Tp    value_type;
     typedef _Hash  hasher;
     typedef _Equal key_equal;
     typedef _Alloc allocator_type;
 
 private:
     typedef allocator_traits<allocator_type> __alloc_traits;

 
 private:
 
     typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;
     typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
     typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
     typedef allocator_traits<__pointer_allocator>          __pointer_alloc_traits;
     typedef typename __bucket_list_deleter::pointer       __node_pointer_pointer;
+    typedef typename _Traits::__unique_keys __unique_keys;
 
     // --- Member data begin ---
     __bucket_list                                         __bucket_list_;
     __compressed_pair<__first_node, __node_allocator>     __p1_;
     __compressed_pair<size_type, hasher>                  __p2_;
     __compressed_pair<float, key_equal>                   __p3_;
     // --- Member data end ---
 
#if _LIBCPP_STD_VER > 14
     template <class _Table>
     _LIBCPP_INLINE_VISIBILITY
     void __node_handle_merge_multi(_Table& __source);
 
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(key_type const& __key);
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(const_iterator __it);
 #endif
 
     void clear() _NOEXCEPT;
     void rehash(size_type __n);
     _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
         {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
 
private:
 
     void __deallocate_node(__next_pointer __np) _NOEXCEPT;
     __next_pointer __detach() _NOEXCEPT;
 
     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 };
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
-    _NOEXCEPT_(
-        is_nothrow_default_constructible<__bucket_list>::value &&
-        is_nothrow_default_constructible<__first_node>::value &&
-        is_nothrow_default_constructible<__node_allocator>::value &&
-        is_nothrow_default_constructible<hasher>::value &&
-        is_nothrow_default_constructible<key_equal>::value)
-    : __p2_(0, __default_init_tag()),
-      __p3_(1.0f, __default_init_tag())
-{
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
-                                                       const key_equal& __eql)
-    : __bucket_list_(nullptr, __bucket_list_deleter()),
-      __p1_(),
-      __p2_(0, __hf),
-      __p3_(1.0f, __eql)
-{
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
-                                                       const key_equal& __eql,
-                                                       const allocator_type& __a)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table() _NOEXCEPT_(
+    is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<
+        __first_node>::value&& is_nothrow_default_constructible<__node_allocator>::value&&
+        is_nothrow_default_constructible<hasher>::value&& is_nothrow_default_constructible<key_equal>::value)
+    : __p2_(0, __default_init_tag()), __p3_(1.0f, __default_init_tag()) {}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table(const hasher& __hf, const key_equal& __eql)
+    : __bucket_list_(nullptr, __bucket_list_deleter()), __p1_(), __p2_(0, __hf), __p3_(1.0f, __eql) {}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table(
+    const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, __hf),
-      __p3_(1.0f, __eql)
-{
-}
+      __p3_(1.0f, __eql) {}
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table(const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, __default_init_tag()),
-      __p3_(1.0f, __default_init_tag())
-{
-}
+      __p3_(1.0f, __default_init_tag()) {}
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
-    : __bucket_list_(nullptr,
-          __bucket_list_deleter(allocator_traits<__pointer_allocator>::
-              select_on_container_copy_construction(
-                  __u.__bucket_list_.get_deleter().__alloc()), 0)),
-      __p1_(__default_init_tag(), allocator_traits<__node_allocator>::
-          select_on_container_copy_construction(__u.__node_alloc())),
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table(const __hash_table& __u)
+    : __bucket_list_(
+          nullptr,
+          __bucket_list_deleter(
+              allocator_traits<__pointer_allocator>::select_on_container_copy_construction(
+                  __u.__bucket_list_.get_deleter().__alloc()),
+              0)),
+      __p1_(__default_init_tag(),
+            allocator_traits<__node_allocator>::select_on_container_copy_construction(__u.__node_alloc())),
       __p2_(0, __u.hash_function()),
-      __p3_(__u.__p3_)
-{
-}
+      __p3_(__u.__p3_) {}
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
-                                                       const allocator_type& __a)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table(const __hash_table& __u, const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, __u.hash_function()),
-      __p3_(__u.__p3_)
-{
-}
+      __p3_(__u.__p3_) {}
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
-        _NOEXCEPT_(
-            is_nothrow_move_constructible<__bucket_list>::value &&
-            is_nothrow_move_constructible<__first_node>::value &&
-            is_nothrow_move_constructible<__node_allocator>::value &&
-            is_nothrow_move_constructible<hasher>::value &&
-            is_nothrow_move_constructible<key_equal>::value)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table(__hash_table&& __u) _NOEXCEPT_(
+    is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<
+        __first_node>::value&& is_nothrow_move_constructible<__node_allocator>::value&&
+        is_nothrow_move_constructible<hasher>::value&& is_nothrow_move_constructible<key_equal>::value)
     : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
       __p1_(_VSTD::move(__u.__p1_)),
       __p2_(_VSTD::move(__u.__p2_)),
-      __p3_(_VSTD::move(__u.__p3_))
-{
-    if (size() > 0)
-    {
-        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
-            __p1_.first().__ptr();
-        __u.__p1_.first().__next_ = nullptr;
-        __u.size() = 0;
-    }
+      __p3_(_VSTD::move(__u.__p3_)) {
+  if (size() > 0) {
+    __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
+    __u.__p1_.first().__next_                                                         = nullptr;
+    __u.size()                                                                        = 0;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
-                                                       const allocator_type& __a)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__hash_table(__hash_table&& __u, const allocator_type& __a)
     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
       __p1_(__default_init_tag(), __node_allocator(__a)),
       __p2_(0, _VSTD::move(__u.hash_function())),
-      __p3_(_VSTD::move(__u.__p3_))
-{
-    if (__a == allocator_type(__u.__node_alloc()))
-    {
-        __bucket_list_.reset(__u.__bucket_list_.release());
-        __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
-        __u.__bucket_list_.get_deleter().size() = 0;
-        if (__u.size() > 0)
-        {
-            __p1_.first().__next_ = __u.__p1_.first().__next_;
-            __u.__p1_.first().__next_ = nullptr;
-            __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
-                __p1_.first().__ptr();
-            size() = __u.size();
-            __u.size() = 0;
-        }
-    }
+      __p3_(_VSTD::move(__u.__p3_)) {
+  if (__a == allocator_type(__u.__node_alloc())) {
+    __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
+    if (__u.size() > 0) {
+      __p1_.first().__next_                                                             = __u.__p1_.first().__next_;
+      __u.__p1_.first().__next_                                                         = nullptr;
+      __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
+      size()                                                                            = __u.size();
+      __u.size()                                                                        = 0;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
-{
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::~__hash_table() {
 #if defined(_LIBCPP_CXX03_LANG)
     static_assert((is_copy_constructible<key_equal>::value),
                  "Predicate must be copy-constructible.");
     static_assert((is_copy_constructible<hasher>::value),
                  "Hasher must be copy-constructible.");
 #endif
 
     __deallocate_node(__p1_.first().__next_);
     std::__debug_db_erase_c(this);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
-        const __hash_table& __u, true_type)
-{
-    if (__node_alloc() != __u.__node_alloc())
-    {
-        clear();
-        __bucket_list_.reset();
-        __bucket_list_.get_deleter().size() = 0;
-    }
-    __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
-    __node_alloc() = __u.__node_alloc();
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__copy_assign_alloc(const __hash_table& __u, true_type) {
+  if (__node_alloc() != __u.__node_alloc()) {
+  __node_alloc()                         = __u.__node_alloc();
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>&
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
-{
-    if (this != _VSTD::addressof(__u))
-    {
-        __copy_assign_alloc(__u);
-        hash_function() = __u.hash_function();
-        key_eq() = __u.key_eq();
-        max_load_factor() = __u.max_load_factor();
-        __assign_multi(__u.begin(), __u.end());
-    }
-    return *this;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>&
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::operator=(const __hash_table& __u) {
+  if (this != _VSTD::addressof(__u)) {
+    hash_function()   = __u.hash_function();
+    key_eq()          = __u.key_eq();
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
-    _NOEXCEPT
-{
-    __node_allocator& __na = __node_alloc();
-    while (__np != nullptr)
-    {
-        __next_pointer __next = __np->__next_;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__deallocate_node(__next_pointer __np) _NOEXCEPT {
+  while (__np != nullptr) {
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
         __c_node* __c = __get_db()->__find_c_and_lock(this);
         for (__i_node** __p = __c->end_; __p != __c->beg_; )
         {
             --__p;
             iterator* __i = static_cast<iterator*>((*__p)->__i_);
             if (__i->__node_ == __np)
             {
                 (*__p)->__c_ = nullptr;
                 if (--__c->end_ != __p)
                     _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
             }
         }
         __get_db()->unlock();
 #endif
         __node_pointer __real_np = __np->__upcast();
         __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_));
         __node_traits::deallocate(__na, __real_np, 1);
         __np = __next;
     }
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
-{
-    size_type __bc = bucket_count();
-    for (size_type __i = 0; __i < __bc; ++__i)
-        __bucket_list_[__i] = nullptr;
-    size() = 0;
-    __next_pointer __cache = __p1_.first().__next_;
-    __p1_.first().__next_ = nullptr;
-    return __cache;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__detach() _NOEXCEPT {
+  size()                 = 0;
+  __p1_.first().__next_  = nullptr;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
-        __hash_table& __u, true_type)
-    _NOEXCEPT_(
-        is_nothrow_move_assignable<__node_allocator>::value &&
-        is_nothrow_move_assignable<hasher>::value &&
-        is_nothrow_move_assignable<key_equal>::value)
-{
-    clear();
-    __bucket_list_.reset(__u.__bucket_list_.release());
-    __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
-    __u.__bucket_list_.get_deleter().size() = 0;
-    __move_assign_alloc(__u);
-    size() = __u.size();
-    hash_function() = _VSTD::move(__u.hash_function());
-    max_load_factor() = __u.max_load_factor();
-    key_eq() = _VSTD::move(__u.key_eq());
-    __p1_.first().__next_ = __u.__p1_.first().__next_;
-    if (size() > 0)
-    {
-        __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
-            __p1_.first().__ptr();
-        __u.__p1_.first().__next_ = nullptr;
-        __u.size() = 0;
-    }
-    std::__debug_db_swap(this, std::addressof(__u));
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__move_assign(__hash_table& __u, true_type) _NOEXCEPT_(
+    is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
+        is_nothrow_move_assignable<key_equal>::value) {
+  __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
+  size()                = __u.size();
+  hash_function()       = _VSTD::move(__u.hash_function());
+  max_load_factor()     = __u.max_load_factor();
+  key_eq()              = _VSTD::move(__u.key_eq());
+  if (size() > 0) {
+    __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
+    __u.__p1_.first().__next_                                                         = nullptr;
+    __u.size()                                                                        = 0;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
-        __hash_table& __u, false_type)
-{
-    if (__node_alloc() == __u.__node_alloc())
-        __move_assign(__u, true_type());
-    else
-    {
-        hash_function() = _VSTD::move(__u.hash_function());
-        key_eq() = _VSTD::move(__u.key_eq());
-        max_load_factor() = __u.max_load_factor();
-        if (bucket_count() != 0)
-        {
-            __next_pointer __cache = __detach();
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__move_assign(__hash_table& __u, false_type) {
+  else {
+    hash_function()   = _VSTD::move(__u.hash_function());
+    key_eq()          = _VSTD::move(__u.key_eq());
+    if (bucket_count() != 0) {
 #ifndef _LIBCPP_NO_EXCEPTIONS
             try
             {
 #endif // _LIBCPP_NO_EXCEPTIONS
                 const_iterator __i = __u.begin();
                 while (__cache != nullptr && __u.size() != 0)
                 {
                     __cache->__upcast()->__value_ =
#endif // _LIBCPP_NO_EXCEPTIONS
         {
             __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_));
             __node_insert_multi(__h.get());
             __h.release();
         }
     }
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline
-__hash_table<_Tp, _Hash, _Equal, _Alloc>&
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
-    _NOEXCEPT_(
-        __node_traits::propagate_on_container_move_assignment::value &&
-        is_nothrow_move_assignable<__node_allocator>::value &&
-        is_nothrow_move_assignable<hasher>::value &&
-        is_nothrow_move_assignable<key_equal>::value)
-{
-    __move_assign(__u, integral_constant<bool,
-                  __node_traits::propagate_on_container_move_assignment::value>());
-    return *this;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>&
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::operator=(__hash_table&& __u) _NOEXCEPT_(
+    __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<__node_allocator>::value&&
+        is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value) {
+  __move_assign(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _InputIterator>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
-                                                          _InputIterator __last)
-{
-    typedef iterator_traits<_InputIterator> _ITraits;
-    typedef typename _ITraits::value_type _ItValueType;
-    static_assert((is_same<_ItValueType, __container_value_type>::value),
-                  "__assign_unique may only be called with the containers value type");
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__assign_unique(_InputIterator __first, _InputIterator __last) {
+  static_assert(
+      (is_same<_ItValueType, __container_value_type>::value),
 
-    if (bucket_count() != 0)
-    {
-        __next_pointer __cache = __detach();
+  if (bucket_count() != 0) {
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif // _LIBCPP_NO_EXCEPTIONS
             for (; __cache != nullptr && __first != __last; ++__first)
             {
                 __cache->__upcast()->__value_ = *__first;
                 __next_pointer __next = __cache->__next_;
#ifndef _LIBCPP_NO_EXCEPTIONS
         }
 #endif // _LIBCPP_NO_EXCEPTIONS
         __deallocate_node(__cache);
     }
     for (; __first != __last; ++__first)
         __insert_unique(*__first);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _InputIterator>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
-                                                         _InputIterator __last)
-{
-    typedef iterator_traits<_InputIterator> _ITraits;
-    typedef typename _ITraits::value_type _ItValueType;
-    static_assert((is_same<_ItValueType, __container_value_type>::value ||
-                  is_same<_ItValueType, __node_value_type>::value),
-                  "__assign_multi may only be called with the containers value type"
-                  " or the nodes value type");
-    if (bucket_count() != 0)
-    {
-        __next_pointer __cache = __detach();
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__assign_multi(_InputIterator __first, _InputIterator __last) {
+  static_assert(
+      (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value),
+  if (bucket_count() != 0) {
 #ifndef _LIBCPP_NO_EXCEPTIONS
         try
         {
 #endif // _LIBCPP_NO_EXCEPTIONS
             for (; __cache != nullptr && __first != __last; ++__first)
             {
                 __cache->__upcast()->__value_ = *__first;
                 __next_pointer __next = __cache->__next_;
#ifndef _LIBCPP_NO_EXCEPTIONS
         }
 #endif // _LIBCPP_NO_EXCEPTIONS
         __deallocate_node(__cache);
     }
     for (; __first != __last; ++__first)
         __insert_multi(_NodeTypes::__get_value(*__first));
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
-{
-    return iterator(__p1_.first().__next_, this);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::begin() _NOEXCEPT {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
-{
-    return iterator(nullptr, this);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::end() _NOEXCEPT {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
-{
-    return const_iterator(__p1_.first().__next_, this);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::const_iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::begin() const _NOEXCEPT {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
-{
-    return const_iterator(nullptr, this);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::const_iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::end() const _NOEXCEPT {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
-{
-    if (size() > 0)
-    {
-        __deallocate_node(__p1_.first().__next_);
-        __p1_.first().__next_ = nullptr;
-        size_type __bc = bucket_count();
-        for (size_type __i = 0; __i < __bc; ++__i)
-            __bucket_list_[__i] = nullptr;
-        size() = 0;
-    }
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::clear() _NOEXCEPT {
+  if (size() > 0) {
+    size_type __bc        = bucket_count();
 }
 
-
 // Prepare the container for an insertion of the value __value with the hash
 // __hash. This does a lookup into the container to see if __value is already
 // present, and performs a rehash if necessary. Returns a pointer to the
 // existing element if it exists, otherwise nullptr.
 //
 // Note that this function does forward exceptions if key_eq() throws, and never
 // mutates __value or actually inserts into the map.
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-_LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
-    size_t __hash, value_type& __value)
-{
-    size_type __bc = bucket_count();
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+_LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_insert_unique_prepare(size_t __hash, value_type& __value) {
 
-    if (__bc != 0)
-    {
-        size_t __chash = __constrain_hash(__hash, __bc);
-        __next_pointer __ndptr = __bucket_list_[__chash];
-        if (__ndptr != nullptr)
-        {
-            for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
-                                             __constrain_hash(__ndptr->__hash(), __bc) == __chash;
-                                                     __ndptr = __ndptr->__next_)
-            {
-                if (key_eq()(__ndptr->__upcast()->__value_, __value))
-                    return __ndptr;
-            }
-        }
-    }
-    if (size()+1 > __bc * max_load_factor() || __bc == 0)
-    {
-        rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
-                                     size_type(ceil(float(size() + 1) / max_load_factor()))));
-    }
-    return nullptr;
+  if (__bc != 0) {
+    size_t __chash         = __constrain_hash(__hash, __bc);
+    if (__ndptr != nullptr) {
+      for (__ndptr = __ndptr->__next_; __ndptr != nullptr && __constrain_hash(__ndptr->__hash(), __bc) == __chash;
+           __ndptr = __ndptr->__next_) {
+  if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
+    rehash(_VSTD::max<size_type>(
+        2 * __bc + !__is_hash_power2(__bc), size_type(ceil(float(size() + 1) / max_load_factor()))));
 }
 
 // Insert the node __nd into the container by pushing it into the right bucket,
 // and updating size(). Assumes that __nd->__hash is up-to-date, and that
 // rehashing has already occurred and that no element with the same key exists
 // in the map.
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-_LIBCPP_INLINE_VISIBILITY
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
-    __node_pointer __nd) _NOEXCEPT
-{
-    size_type __bc = bucket_count();
-    size_t __chash = __constrain_hash(__nd->__hash(), __bc);
-    // insert_after __bucket_list_[__chash], or __first_node if bucket is null
-    __next_pointer __pn = __bucket_list_[__chash];
-    if (__pn == nullptr)
-    {
-        __pn =__p1_.first().__ptr();
-        __nd->__next_ = __pn->__next_;
-        __pn->__next_ = __nd->__ptr();
-        // fix up __bucket_list_
-        __bucket_list_[__chash] = __pn;
-        if (__nd->__next_ != nullptr)
-            __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
-    }
-    else
-    {
-        __nd->__next_ = __pn->__next_;
-        __pn->__next_ = __nd->__ptr();
-    }
-    ++size();
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+_LIBCPP_INLINE_VISIBILITY void
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_insert_unique_perform(__node_pointer __nd) _NOEXCEPT {
+  if (__pn == nullptr) {
+    __pn          = __p1_.first().__ptr();
+  } else {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
-{
-    __nd->__hash_ = hash_function()(__nd->__value_);
-    __next_pointer __existing_node =
-        __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_insert_unique(__node_pointer __nd) {
+  __nd->__hash_                  = hash_function()(__nd->__value_);
+  __next_pointer __existing_node = __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
 
-    // Insert the node, unless it already exists in the container.
-    bool __inserted = false;
-    if (__existing_node == nullptr)
-    {
-        __node_insert_unique_perform(__nd);
-        __existing_node = __nd->__ptr();
-        __inserted = true;
-    }
-    return pair<iterator, bool>(iterator(__existing_node, this), __inserted);
+  if (__existing_node == nullptr) {
+    __inserted      = true;
 }
 
 // Prepare the container for an insertion of the value __cp_val with the hash
 // __cp_hash. This does a lookup into the container to see if __cp_value is
 // already present, and performs a rehash if necessary. Returns a pointer to the
 // last occurrence of __cp_val in the map.
 //
 // Note that this function does forward exceptions if key_eq() throws, and never
 // mutates __value or actually inserts into the map.
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
-    size_t __cp_hash, value_type& __cp_val)
-{
-    size_type __bc = bucket_count();
-    if (size()+1 > __bc * max_load_factor() || __bc == 0)
-    {
-        rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
-                       size_type(ceil(float(size() + 1) / max_load_factor()))));
-        __bc = bucket_count();
-    }
-    size_t __chash = __constrain_hash(__cp_hash, __bc);
-    __next_pointer __pn = __bucket_list_[__chash];
-    if (__pn != nullptr)
-    {
-        for (bool __found = false; __pn->__next_ != nullptr &&
-                                   __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
-                                                           __pn = __pn->__next_)
-        {
-            //      __found    key_eq()     action
-            //      false       false       loop
-            //      true        true        loop
-            //      false       true        set __found to true
-            //      true        false       break
-            if (__found != (__pn->__next_->__hash() == __cp_hash &&
-                            key_eq()(__pn->__next_->__upcast()->__value_, __cp_val)))
-            {
-                if (!__found)
-                    __found = true;
-                else
-                    break;
-            }
-        }
-    }
-    return __pn;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val) {
+  if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
+    rehash(_VSTD::max<size_type>(
+        2 * __bc + !__is_hash_power2(__bc), size_type(ceil(float(size() + 1) / max_load_factor()))));
+  size_t __chash      = __constrain_hash(__cp_hash, __bc);
+  if (__pn != nullptr) {
+    for (bool __found = false; __pn->__next_ != nullptr && __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
+         __pn         = __pn->__next_) {
+      if (__found !=
+          (__pn->__next_->__hash() == __cp_hash && key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) {
 }
 
 // Insert the node __cp into the container after __pn (which is the last node in
 // the bucket that compares equal to __cp). Rehashing, and checking for
 // uniqueness has already been performed (in __node_insert_multi_prepare), so
 // all we need to do is update the bucket and size(). Assumes that __cp->__hash
 // is up-to-date.
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
-    __node_pointer __cp, __next_pointer __pn) _NOEXCEPT
-{
-    size_type __bc = bucket_count();
-    size_t __chash = __constrain_hash(__cp->__hash_, __bc);
-    if (__pn == nullptr)
-    {
-        __pn =__p1_.first().__ptr();
-        __cp->__next_ = __pn->__next_;
-        __pn->__next_ = __cp->__ptr();
-        // fix up __bucket_list_
-        __bucket_list_[__chash] = __pn;
-        if (__cp->__next_ != nullptr)
-            __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
-                = __cp->__ptr();
-    }
-    else
-    {
-        __cp->__next_ = __pn->__next_;
-        __pn->__next_ = __cp->__ptr();
-        if (__cp->__next_ != nullptr)
-        {
-            size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc);
-            if (__nhash != __chash)
-                __bucket_list_[__nhash] = __cp->__ptr();
-        }
-    }
-    ++size();
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_insert_multi_perform(
+    __node_pointer __cp, __next_pointer __pn) _NOEXCEPT {
+  if (__pn == nullptr) {
+    __pn          = __p1_.first().__ptr();
+      __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] = __cp->__ptr();
+  } else {
+    if (__cp->__next_ != nullptr) {
 }
 
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
-{
-    __cp->__hash_ = hash_function()(__cp->__value_);
-    __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_);
-    __node_insert_multi_perform(__cp, __pn);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_insert_multi(__node_pointer __cp) {
+  __cp->__hash_       = hash_function()(__cp->__value_);
 
-    return iterator(__cp->__ptr(), this);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
-        const_iterator __p, __node_pointer __cp)
-{
-    _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
-                         "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
-                         " referring to this unordered container");
-    if (__p != end() && key_eq()(*__p, __cp->__value_))
-    {
-        __next_pointer __np = __p.__node_;
-        __cp->__hash_ = __np->__hash();
-        size_type __bc = bucket_count();
-        if (size()+1 > __bc * max_load_factor() || __bc == 0)
-        {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
-                           size_type(ceil(float(size() + 1) / max_load_factor()))));
-            __bc = bucket_count();
-        }
-        size_t __chash = __constrain_hash(__cp->__hash_, __bc);
-        __next_pointer __pp = __bucket_list_[__chash];
-        while (__pp->__next_ != __np)
-            __pp = __pp->__next_;
-        __cp->__next_ = __np;
-        __pp->__next_ = static_cast<__next_pointer>(__cp);
-        ++size();
-        return iterator(static_cast<__next_pointer>(__cp), this);
-    }
-    return __node_insert_multi(__cp);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_insert_multi(const_iterator __p, __node_pointer __cp) {
+  _LIBCPP_DEBUG_ASSERT(
+      __get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
+  if (__p != end() && key_eq()(*__p, __cp->__value_)) {
+    __cp->__hash_       = __np->__hash();
+    size_type __bc      = bucket_count();
+    if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
+      rehash(_VSTD::max<size_type>(
+          2 * __bc + !__is_hash_power2(__bc), size_type(ceil(float(size() + 1) / max_load_factor()))));
+    size_t __chash      = __constrain_hash(__cp->__hash_, __bc);
 }
 
-
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _Key, class ..._Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
-{
-
-    size_t __hash = hash_function()(__k);
-    size_type __bc = bucket_count();
-    bool __inserted = false;
-    __next_pointer __nd;
-    size_t __chash;
-    if (__bc != 0)
-    {
-        __chash = __constrain_hash(__hash, __bc);
-        __nd = __bucket_list_[__chash];
-        if (__nd != nullptr)
-        {
-            for (__nd = __nd->__next_; __nd != nullptr &&
-                (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
-                                                           __nd = __nd->__next_)
-            {
-                if (key_eq()(__nd->__upcast()->__value_, __k))
-                    goto __done;
-            }
-        }
-    }
-    {
-        __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
-        if (size()+1 > __bc * max_load_factor() || __bc == 0)
-        {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
-                           size_type(ceil(float(size() + 1) / max_load_factor()))));
-            __bc = bucket_count();
-            __chash = __constrain_hash(__hash, __bc);
-        }
-        // insert_after __bucket_list_[__chash], or __first_node if bucket is null
-        __next_pointer __pn = __bucket_list_[__chash];
-        if (__pn == nullptr)
-        {
-            __pn = __p1_.first().__ptr();
-            __h->__next_ = __pn->__next_;
-            __pn->__next_ = __h.get()->__ptr();
-            // fix up __bucket_list_
-            __bucket_list_[__chash] = __pn;
-            if (__h->__next_ != nullptr)
-                __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)]
-                    = __h.get()->__ptr();
-        }
-        else
-        {
-            __h->__next_ = __pn->__next_;
-            __pn->__next_ = static_cast<__next_pointer>(__h.get());
-        }
-        __nd = static_cast<__next_pointer>(__h.release());
-        // increment size
-        ++size();
-        __inserted = true;
-    }
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+template <class _Key, class... _Args>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
+  size_t __hash   = hash_function()(__k);
+  size_type __bc  = bucket_count();
+  if (__bc != 0) {
+    __nd    = __bucket_list_[__chash];
+    if (__nd != nullptr) {
+      for (__nd = __nd->__next_;
+           __nd != nullptr && (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
+           __nd = __nd->__next_) {
+    if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
+      rehash(_VSTD::max<size_type>(
+          2 * __bc + !__is_hash_power2(__bc), size_type(ceil(float(size() + 1) / max_load_factor()))));
+      __bc    = bucket_count();
+    if (__pn == nullptr) {
+      __pn          = __p1_.first().__ptr();
+      __h->__next_  = __pn->__next_;
+        __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
+    } else {
+      __h->__next_  = __pn->__next_;
 __done:
     return pair<iterator, bool>(iterator(__nd, this), __inserted);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
-{
-    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
-    pair<iterator, bool> __r = __node_insert_unique(__h.get());
-    if (__r.second)
-        __h.release();
-    return __r;
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__emplace_unique_impl(_Args&&... __args) {
+  __node_holder __h        = __construct_node(_VSTD::forward<_Args>(__args)...);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class... _Args>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
-{
-    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
-    iterator __r = __node_insert_multi(__h.get());
-    __h.release();
-    return __r;
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__emplace_multi(_Args&&... __args) {
+  iterator __r      = __node_insert_multi(__h.get());
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class... _Args>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
-        const_iterator __p, _Args&&... __args)
-{
-    _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
-                         "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
-                         " referring to this unordered container");
-    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
-    iterator __r = __node_insert_multi(__p, __h.get());
-    __h.release();
-    return __r;
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {
+  _LIBCPP_DEBUG_ASSERT(
+      __get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
+  iterator __r      = __node_insert_multi(__p, __h.get());
 }
 
 #if _LIBCPP_STD_VER > 14
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _NodeHandle, class _InsertReturnType>
-_LIBCPP_INLINE_VISIBILITY
-_InsertReturnType
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
-    _NodeHandle&& __nh)
-{
-    if (__nh.empty())
-        return _InsertReturnType{end(), false, _NodeHandle()};
-    pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
-    if (__result.second)
-        __nh.__release_ptr();
-    return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)};
+_LIBCPP_INLINE_VISIBILITY _InsertReturnType
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_insert_unique(_NodeHandle&& __nh) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _NodeHandle>
-_LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
-    const_iterator, _NodeHandle&& __nh)
-{
-    if (__nh.empty())
-        return end();
-    pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
-    if (__result.second)
-        __nh.__release_ptr();
-    return __result.first;
+_LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_insert_unique(const_iterator, _NodeHandle&& __nh) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _NodeHandle>
-_LIBCPP_INLINE_VISIBILITY
-_NodeHandle
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
-    key_type const& __key)
-{
-    iterator __i = find(__key);
-    if (__i == end())
-        return _NodeHandle();
-    return __node_handle_extract<_NodeHandle>(__i);
+_LIBCPP_INLINE_VISIBILITY _NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_extract(key_type const& __key) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _NodeHandle>
-_LIBCPP_INLINE_VISIBILITY
-_NodeHandle
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
-    const_iterator __p)
-{
-    allocator_type __alloc(__node_alloc());
-    return _NodeHandle(remove(__p).release(), __alloc);
+_LIBCPP_INLINE_VISIBILITY _NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_extract(const_iterator __p) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Table>
-_LIBCPP_INLINE_VISIBILITY
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
-    _Table& __source)
-{
-    static_assert(is_same<__node, typename _Table::__node>::value, "");
+_LIBCPP_INLINE_VISIBILITY void
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_merge_unique(_Table& __source) {
 
-    for (typename _Table::iterator __it = __source.begin();
-         __it != __source.end();)
-    {
-        __node_pointer __src_ptr = __it.__node_->__upcast();
-        size_t __hash = hash_function()(__src_ptr->__value_);
-        __next_pointer __existing_node =
-            __node_insert_unique_prepare(__hash, __src_ptr->__value_);
-        auto __prev_iter = __it++;
-        if (__existing_node == nullptr)
-        {
-            (void)__source.remove(__prev_iter).release();
-            __src_ptr->__hash_ = __hash;
-            __node_insert_unique_perform(__src_ptr);
-        }
-    }
+  for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
+    __node_pointer __src_ptr       = __it.__node_->__upcast();
+    size_t __hash                  = hash_function()(__src_ptr->__value_);
+    __next_pointer __existing_node = __node_insert_unique_prepare(__hash, __src_ptr->__value_);
+    auto __prev_iter               = __it++;
+    if (__existing_node == nullptr) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _NodeHandle>
-_LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
-    _NodeHandle&& __nh)
-{
-    if (__nh.empty())
-        return end();
-    iterator __result = __node_insert_multi(__nh.__ptr_);
-    __nh.__release_ptr();
-    return __result;
+_LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_insert_multi(_NodeHandle&& __nh) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _NodeHandle>
-_LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
-    const_iterator __hint, _NodeHandle&& __nh)
-{
-    if (__nh.empty())
-        return end();
-    iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
-    __nh.__release_ptr();
-    return __result;
+_LIBCPP_INLINE_VISIBILITY typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_insert_multi(
+    const_iterator __hint, _NodeHandle&& __nh) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Table>
-_LIBCPP_INLINE_VISIBILITY
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
-    _Table& __source)
-{
-    static_assert(is_same<typename _Table::__node, __node>::value, "");
+_LIBCPP_INLINE_VISIBILITY void
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_handle_merge_multi(_Table& __source) {
 
-    for (typename _Table::iterator __it = __source.begin();
-         __it != __source.end();)
-    {
-        __node_pointer __src_ptr = __it.__node_->__upcast();
-        size_t __src_hash = hash_function()(__src_ptr->__value_);
-        __next_pointer __pn =
-            __node_insert_multi_prepare(__src_hash, __src_ptr->__value_);
-        (void)__source.remove(__it++).release();
-        __src_ptr->__hash_ = __src_hash;
-        __node_insert_multi_perform(__src_ptr, __pn);
-    }
+  for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
+    size_t __src_hash        = hash_function()(__src_ptr->__value_);
+    __next_pointer __pn      = __node_insert_multi_prepare(__src_hash, __src_ptr->__value_);
 }
 #endif // _LIBCPP_STD_VER > 14
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
-_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
-{
-    if (__n == 1)
-        __n = 2;
-    else if (__n & (__n - 1))
-        __n = __next_prime(__n);
-    size_type __bc = bucket_count();
-    if (__n > __bc)
-        __rehash(__n);
-    else if (__n < __bc)
-    {
-        __n = _VSTD::max<size_type>
-              (
-                  __n,
-                  __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
-                                           __next_prime(size_t(ceil(float(size()) / max_load_factor())))
-              );
-        if (__n < __bc)
-            __rehash(__n);
-    }
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::rehash(size_type __n)
+    _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
+  else if (__n < __bc) {
+    __n = _VSTD::max<size_type>(
+        __is_hash_power2(__bc)
+            ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor())))
+            : __next_prime(size_t(ceil(float(size()) / max_load_factor()))));
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
-{
-    std::__debug_db_invalidate_all(this);
-    __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
-    __bucket_list_.reset(__nbc > 0 ?
-                      __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
-    __bucket_list_.get_deleter().size() = __nbc;
-    if (__nbc > 0)
-    {
-        for (size_type __i = 0; __i < __nbc; ++__i)
-            __bucket_list_[__i] = nullptr;
-        __next_pointer __pp = __p1_.first().__ptr();
-        __next_pointer __cp = __pp->__next_;
-        if (__cp != nullptr)
-        {
-            size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
-            __bucket_list_[__chash] = __pp;
-            size_type __phash = __chash;
-            for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr;
-                                                           __cp = __pp->__next_)
-            {
-                __chash = __constrain_hash(__cp->__hash(), __nbc);
-                if (__chash == __phash)
-                    __pp = __cp;
-                else
-                {
-                    if (__bucket_list_[__chash] == nullptr)
-                    {
-                        __bucket_list_[__chash] = __pp;
-                        __pp = __cp;
-                        __phash = __chash;
-                    }
-                    else
-                    {
-                        __next_pointer __np = __cp;
-                        for (; __np->__next_ != nullptr &&
-                               key_eq()(__cp->__upcast()->__value_,
-                                        __np->__next_->__upcast()->__value_);
-                                                           __np = __np->__next_)
-                            ;
-                        __pp->__next_ = __np->__next_;
-                        __np->__next_ = __bucket_list_[__chash]->__next_;
-                        __bucket_list_[__chash]->__next_ = __cp;
-
-                    }
-                }
-            }
-        }
-    }
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__rehash(size_type __nbc) {
+  __bucket_list_.reset(__nbc > 0 ? __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
+  if (__nbc > 0) {
+    if (__cp != nullptr) {
+      size_type __chash       = __constrain_hash(__cp->__hash(), __nbc);
+      size_type __phash       = __chash;
+      for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) {
+        else {
+          if (__bucket_list_[__chash] == nullptr) {
+            __pp                    = __cp;
+            __phash                 = __chash;
+          } else {
+            if (!__unique_keys{}) {
+                     key_eq()(__cp->__upcast()->__value_, __np->__next_->__upcast()->__value_);
+            }
+            __pp->__next_                    = __np->__next_;
+            __np->__next_                    = __bucket_list_[__chash]->__next_;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
-{
-    size_t __hash = hash_function()(__k);
-    size_type __bc = bucket_count();
-    if (__bc != 0)
-    {
-        size_t __chash = __constrain_hash(__hash, __bc);
-        __next_pointer __nd = __bucket_list_[__chash];
-        if (__nd != nullptr)
-        {
-            for (__nd = __nd->__next_; __nd != nullptr &&
-                (__nd->__hash() == __hash
-                  || __constrain_hash(__nd->__hash(), __bc) == __chash);
-                                                           __nd = __nd->__next_)
-            {
-                if ((__nd->__hash() == __hash)
-                    && key_eq()(__nd->__upcast()->__value_, __k))
-                    return iterator(__nd, this);
-            }
-        }
-    }
-    return end();
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::find(const _Key& __k) {
+  size_t __hash  = hash_function()(__k);
+  if (__bc != 0) {
+    size_t __chash      = __constrain_hash(__hash, __bc);
+    if (__nd != nullptr) {
+      for (__nd = __nd->__next_;
+           __nd != nullptr && (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
+           __nd = __nd->__next_) {
+        if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__value_, __k))
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
-{
-    size_t __hash = hash_function()(__k);
-    size_type __bc = bucket_count();
-    if (__bc != 0)
-    {
-        size_t __chash = __constrain_hash(__hash, __bc);
-        __next_pointer __nd = __bucket_list_[__chash];
-        if (__nd != nullptr)
-        {
-            for (__nd = __nd->__next_; __nd != nullptr &&
-                (__hash == __nd->__hash()
-                    || __constrain_hash(__nd->__hash(), __bc) == __chash);
-                                                           __nd = __nd->__next_)
-            {
-                if ((__nd->__hash() == __hash)
-                    && key_eq()(__nd->__upcast()->__value_, __k))
-                    return const_iterator(__nd, this);
-            }
-        }
-
-    }
-    return end();
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::const_iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::find(const _Key& __k) const {
+  size_t __hash  = hash_function()(__k);
+  if (__bc != 0) {
+    size_t __chash      = __constrain_hash(__hash, __bc);
+    if (__nd != nullptr) {
+      for (__nd = __nd->__next_;
+           __nd != nullptr && (__hash == __nd->__hash() || __constrain_hash(__nd->__hash(), __bc) == __chash);
+           __nd = __nd->__next_) {
+        if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__value_, __k))
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class ..._Args>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
-{
-    static_assert(!__is_hash_value_type<_Args...>::value,
-                  "Construct cannot be called with a hash value type");
-    __node_allocator& __na = __node_alloc();
-    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
-    __h.get_deleter().__value_constructed = true;
-    __h->__hash_ = hash_function()(__h->__value_);
-    __h->__next_ = nullptr;
-    return __h;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+template <class... _Args>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__construct_node(_Args&&... __args) {
+  static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
+  __h->__hash_                          = hash_function()(__h->__value_);
+  __h->__next_                          = nullptr;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-template <class _First, class ..._Rest>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
-    size_t __hash, _First&& __f, _Rest&& ...__rest)
-{
-    static_assert(!__is_hash_value_type<_First, _Rest...>::value,
-                  "Construct cannot be called with a hash value type");
-    __node_allocator& __na = __node_alloc();
-    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
-    __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_),
-                             _VSTD::forward<_First>(__f),
-                             _VSTD::forward<_Rest>(__rest)...);
-    __h.get_deleter().__value_constructed = true;
-    __h->__hash_ = __hash;
-    __h->__next_ = nullptr;
-    return __h;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+template <class _First, class... _Rest>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__construct_node_hash(
+    size_t __hash, _First&& __f, _Rest&&... __rest) {
+  static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
+  __node_traits::construct(
+      __na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_First>(__f), _VSTD::forward<_Rest>(__rest)...);
+  __h->__hash_                          = __hash;
+  __h->__next_                          = nullptr;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
-{
-    __next_pointer __np = __p.__node_;
-    _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
-                         "unordered container erase(iterator) called with an iterator not"
-                         " referring to this container");
-    _LIBCPP_ASSERT(__p != end(),
-                   "unordered container erase(iterator) called with a non-dereferenceable iterator");
-    iterator __r(__np, this);
-    ++__r;
-    remove(__p);
-    return __r;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::erase(const_iterator __p) {
+  _LIBCPP_DEBUG_ASSERT(
+      __get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
+  _LIBCPP_ASSERT(__p != end(), "unordered container erase(iterator) called with a non-dereferenceable iterator");
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
-                                                const_iterator __last)
-{
-    _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__first)) == this,
-                         "unordered container::erase(iterator, iterator) called with an iterator not"
-                         " referring to this container");
-    _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__last)) == this,
-                         "unordered container::erase(iterator, iterator) called with an iterator not"
-                         " referring to this container");
-    for (const_iterator __p = __first; __first != __last; __p = __first)
-    {
-        ++__first;
-        erase(__p);
-    }
-    __next_pointer __np = __last.__node_;
-    return iterator (__np, this);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::erase(const_iterator __first, const_iterator __last) {
+  _LIBCPP_DEBUG_ASSERT(
+      __get_const_db()->__find_c_from_i(_VSTD::addressof(__first)) == this,
+  _LIBCPP_DEBUG_ASSERT(
+      __get_const_db()->__find_c_from_i(_VSTD::addressof(__last)) == this,
+  for (const_iterator __p = __first; __first != __last; __p = __first) {
+  return iterator(__np, this);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
-{
-    iterator __i = find(__k);
-    if (__i == end())
-        return 0;
-    erase(__i);
-    return 1;
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__erase_unique(const _Key& __k) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
-{
-    size_type __r = 0;
-    iterator __i = find(__k);
-    if (__i != end())
-    {
-        iterator __e = end();
-        do
-        {
-            erase(__i++);
-            ++__r;
-        } while (__i != __e && key_eq()(*__i, __k));
-    }
-    return __r;
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__erase_multi(const _Key& __k) {
+  iterator __i  = find(__k);
+  if (__i != end()) {
+    do {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
-{
-    // current node
-    __next_pointer __cn = __p.__node_;
-    size_type __bc = bucket_count();
-    size_t __chash = __constrain_hash(__cn->__hash(), __bc);
-    // find previous node
-    __next_pointer __pn = __bucket_list_[__chash];
-    for (; __pn->__next_ != __cn; __pn = __pn->__next_)
-        ;
-    // Fix up __bucket_list_
-        // if __pn is not in same bucket (before begin is not in same bucket) &&
-        //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
-    if (__pn == __p1_.first().__ptr()
-            || __constrain_hash(__pn->__hash(), __bc) != __chash)
-    {
-        if (__cn->__next_ == nullptr
-            || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
-            __bucket_list_[__chash] = nullptr;
-    }
-        // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
-    if (__cn->__next_ != nullptr)
-    {
-        size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc);
-        if (__nhash != __chash)
-            __bucket_list_[__nhash] = __pn;
-    }
-    // remove __cn
-    __pn->__next_ = __cn->__next_;
-    __cn->__next_ = nullptr;
-    --size();
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::remove(const_iterator __p) _NOEXCEPT {
+  size_type __bc      = bucket_count();
+  size_t __chash      = __constrain_hash(__cn->__hash(), __bc);
+  if (__pn == __p1_.first().__ptr() || __constrain_hash(__pn->__hash(), __bc) != __chash) {
+    if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
+  if (__cn->__next_ != nullptr) {
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
     __c_node* __c = __get_db()->__find_c_and_lock(this);
     for (__i_node** __dp = __c->end_; __dp != __c->beg_; )
     {
         --__dp;
         iterator* __i = static_cast<iterator*>((*__dp)->__i_);
         if (__i->__node_ == __cn)
         {
             (*__dp)->__c_ = nullptr;
             if (--__c->end_ != __dp)
                 _VSTD::memmove(__dp, __dp+1, (__c->end_ - __dp)*sizeof(__i_node*));
         }
     }
     __get_db()->unlock();
 #endif
     return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
-{
-    return static_cast<size_type>(find(__k) != end());
+inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__count_unique(const _Key& __k) const {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
-{
-    size_type __r = 0;
-    const_iterator __i = find(__k);
-    if (__i != end())
-    {
-        const_iterator __e = end();
-        do
-        {
-            ++__i;
-            ++__r;
-        } while (__i != __e && key_eq()(*__i, __k));
-    }
-    return __r;
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__count_multi(const _Key& __k) const {
+  size_type __r      = 0;
+  if (__i != end()) {
+    do {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
-     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
-        const _Key& __k)
-{
-    iterator __i = find(__k);
-    iterator __j = __i;
-    if (__i != end())
-        ++__j;
-    return pair<iterator, iterator>(__i, __j);
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__equal_range_unique(const _Key& __k) {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
-     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
-        const _Key& __k) const
-{
-    const_iterator __i = find(__k);
-    const_iterator __j = __i;
-    if (__i != end())
-        ++__j;
-    return pair<const_iterator, const_iterator>(__i, __j);
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::const_iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::const_iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__equal_range_unique(const _Key& __k) const {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
-     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
-        const _Key& __k)
-{
-    iterator __i = find(__k);
-    iterator __j = __i;
-    if (__i != end())
-    {
-        iterator __e = end();
-        do
-        {
-            ++__j;
-        } while (__j != __e && key_eq()(*__j, __k));
-    }
-    return pair<iterator, iterator>(__i, __j);
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__equal_range_multi(const _Key& __k) {
+  if (__i != end()) {
+    do {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
 template <class _Key>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
-     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
-        const _Key& __k) const
-{
-    const_iterator __i = find(__k);
-    const_iterator __j = __i;
-    if (__i != end())
-    {
-        const_iterator __e = end();
-        do
-        {
-            ++__j;
-        } while (__j != __e && key_eq()(*__j, __k));
-    }
-    return pair<const_iterator, const_iterator>(__i, __j);
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::const_iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::const_iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__equal_range_multi(const _Key& __k) const {
+  if (__i != end()) {
+    do {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+void __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::swap(__hash_table& __u)
 #if _LIBCPP_STD_VER <= 11
     _NOEXCEPT_(
-        __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
-        && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
-              || __is_nothrow_swappable<__pointer_allocator>::value)
-        && (!__node_traits::propagate_on_container_swap::value
-              || __is_nothrow_swappable<__node_allocator>::value)
-            )
+        __is_nothrow_swappable<hasher>::value&& __is_nothrow_swappable<key_equal>::value &&
+        (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
+         __is_nothrow_swappable<__pointer_allocator>::value) &&
+        (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable<__node_allocator>::value))
 #else
-  _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value)
+    _NOEXCEPT_(__is_nothrow_swappable<hasher>::value&& __is_nothrow_swappable<key_equal>::value)
 #endif
 {
     _LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value ||
                    this->__node_alloc() == __u.__node_alloc(),
                    "list::swap: Either propagate_on_container_swap must be true"
                    " or the allocators must compare equal");
     {
     __node_pointer_pointer __npp = __bucket_list_.release();
if (size() > 0)
         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
             __p1_.first().__ptr();
     if (__u.size() > 0)
         __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
             __u.__p1_.first().__ptr();
     std::__debug_db_swap(this, std::addressof(__u));
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
-{
-    _LIBCPP_ASSERT(__n < bucket_count(),
-        "unordered container::bucket_size(n) called with n >= bucket_count()");
-    __next_pointer __np = __bucket_list_[__n];
-    size_type __bc = bucket_count();
-    size_type __r = 0;
-    if (__np != nullptr)
-    {
-        for (__np = __np->__next_; __np != nullptr &&
-                                   __constrain_hash(__np->__hash(), __bc) == __n;
-                                                    __np = __np->__next_, (void) ++__r)
-            ;
-    }
-    return __r;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::bucket_size(size_type __n) const {
+  _LIBCPP_ASSERT(__n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()");
+  size_type __bc      = bucket_count();
+  size_type __r       = 0;
+  if (__np != nullptr) {
+    for (__np = __np->__next_; __np != nullptr && __constrain_hash(__np->__hash(), __bc) == __n; __np = __np->__next_,
+        (void)++__r)
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-inline _LIBCPP_INLINE_VISIBILITY
-void
-swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
-     __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
-    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
-{
-    __x.swap(__y);
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+inline _LIBCPP_INLINE_VISIBILITY void
+swap(__hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>& __y)
+    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
 }
 
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
-{
-    return __i->__node_ != nullptr;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+bool __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__dereferenceable(const const_iterator* __i) const {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
-{
-    return false;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+bool __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__decrementable(const const_iterator*) const {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
-{
-    return false;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+bool __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__addable(const const_iterator*, ptrdiff_t) const {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
-{
-    return false;
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _Traits>
+bool __hash_table<_Tp, _Hash, _Equal, _Alloc, _Traits>::__subscriptable(const const_iterator*, ptrdiff_t) const {
 }
 
 #endif // _LIBCPP_ENABLE_DEBUG_MODE
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___HASH_TABLE

libcxx/include/unordered_map

 
 private:
     typedef __hash_value_type<key_type, mapped_type>                          __value_type;
     typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
     typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher>  __key_equal;
     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
                                                  __value_type>::type          __allocator_type;
 
-    typedef __hash_table<__value_type, __hasher,
-                         __key_equal,  __allocator_type>   __table;
+    typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type, __hash_table_traits<true >> __table;
 
     __table __table_;
 
     typedef typename __table::_NodeTypes                   _NodeTypes;
     typedef typename __table::__node_pointer               __node_pointer;
     typedef typename __table::__node_const_pointer         __node_const_pointer;
     typedef typename __table::__node_traits                __node_traits;
     typedef typename __table::__node_allocator             __node_allocator;

 
 private:
     typedef __hash_value_type<key_type, mapped_type>                          __value_type;
     typedef __unordered_map_hasher<key_type, __value_type, hasher, key_equal> __hasher;
     typedef __unordered_map_equal<key_type, __value_type, key_equal, hasher>  __key_equal;
     typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
                                                  __value_type>::type          __allocator_type;
 
-    typedef __hash_table<__value_type, __hasher,
-                         __key_equal,  __allocator_type>   __table;
+    typedef __hash_table<__value_type, __hasher, __key_equal, __allocator_type, __hash_table_traits<false>> __table;
 
     __table __table_;
 
     typedef typename __table::_NodeTypes                   _NodeTypes;
     typedef typename __table::__node_traits                __node_traits;
     typedef typename __table::__node_allocator             __node_allocator;
     typedef typename __table::__node                       __node;
     typedef __hash_map_node_destructor<__node_allocator>   _Dp;

libcxx/include/unordered_set

public:
     typedef __type_identity_t<_Pred>                                   key_equal;
     typedef __type_identity_t<_Alloc>                                  allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
 
 private:
-    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
+  typedef __hash_table<value_type, hasher, key_equal, allocator_type, __hash_table_traits<true >> __table;
 
-    __table __table_;
 
 public:
     typedef typename __table::pointer         pointer;
     typedef typename __table::const_pointer   const_pointer;
     typedef typename __table::size_type       size_type;
     typedef typename __table::difference_type difference_type;
 
     typedef typename __table::const_iterator       iterator;
public:
     typedef __type_identity_t<_Pred>                                   key_equal;
     typedef __type_identity_t<_Alloc>                                  allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
     static_assert((is_same<value_type, typename allocator_type::value_type>::value),
                   "Invalid allocator::value_type");
 
 private:
-    typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
+  typedef __hash_table<value_type, hasher, key_equal, allocator_type, __hash_table_traits<false>> __table;
 
-    __table __table_;
 
 public:
     typedef typename __table::pointer         pointer;
     typedef typename __table::const_pointer   const_pointer;
     typedef typename __table::size_type       size_type;
     typedef typename __table::difference_type difference_type;
 
     typedef typename __table::const_iterator       iterator;