[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

872

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

874

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

877

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

libcxx/include/unordered_map

1047

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

[itrofimow]

cleanup, + benchmarks

[jloser]

libcxx/include/__hash_table

864

Nit: s/reduntand/redundant

877

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.

2284–2290

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

325

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

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

325

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

863–871

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

2284–2290

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

2284–2290

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

2284–2290

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

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

863–871

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

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

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

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

325

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

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

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

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

libcxx/benchmarks/unordered_set_operations.bench.cpp

113

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

[philnik]

LGTM.

libcxx/benchmarks/ContainerBenchmarks.h

static void BM_FindRehash(benchmark::State& st, Container c, GenInputs gen) {
     while (st.KeepRunning()) {
         for (auto it = in.data(); it != end; ++it) {
             benchmark::DoNotOptimize(&(*c.find(*it)));
         }
         benchmark::ClobberMemory();
     }
 }
 
+template <class Container, class GenInputs>
+static void BM_Rehash(benchmark::State& st, Container c, GenInputs gen) {
+    auto in = gen(st.range(0));
+    c.max_load_factor(3.0);
+    c.insert(in.begin(), in.end());
+    benchmark::DoNotOptimize(c);
+    const auto bucket_count = c.bucket_count();
+    while (st.KeepRunning()) {
+        c.rehash(bucket_count + 1);
+        c.rehash(bucket_count);
+        benchmark::ClobberMemory();
+    }
+}
+
 } // end namespace ContainerBenchmarks
 
 #endif // BENCHMARK_CONTAINER_BENCHMARKS_H

libcxx/benchmarks/unordered_set_operations.bench.cpp

struct UInt64Hash2 {
   std::size_t operator()(uint64_t data) const {
       return hash_len_0_to_8<8>(reinterpret_cast<const char*>(&data));
   }
 };
 
 //----------------------------------------------------------------------------//
 //                               BM_Hash
 // ---------------------------------------------------------------------------//
 
 template <class HashFn, class GenInputs>
 void BM_Hash(benchmark::State& st, HashFn fn, GenInputs gen) {
     auto in = gen(st.range(0));
     const auto end = in.data() + in.size();
     std::size_t last_hash = 0;
     benchmark::DoNotOptimize(&last_hash);
     while (st.KeepRunning()) {
         for (auto it = in.data(); it != end; ++it) {
             benchmark::DoNotOptimize(last_hash += fn(*it));
         }
         benchmark::ClobberMemory();
     }
BENCHMARK_CAPTURE(BM_Find,
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
 
 BENCHMARK_CAPTURE(BM_FindRehash,
     unordered_set_string,
     std::unordered_set<std::string>{},
     getRandomStringInputs)->Arg(TestNumInputs);
 
+//----------------------------------------------------------------------------//
+//                         BM_Rehash
+// ---------------------------------------------------------------------------//
+
+BENCHMARK_CAPTURE(BM_Rehash,
+    unordered_set_string_arg,
+    std::unordered_set<std::string>{},
+    getRandomStringInputs)->Arg(TestNumInputs);
+
+BENCHMARK_CAPTURE(BM_Rehash,
+    unordered_set_int_arg,
+    std::unordered_set<int>{},
+    getRandomIntegerInputs<int>)->Arg(TestNumInputs);
+
 ///////////////////////////////////////////////////////////////////////////////
 BENCHMARK_CAPTURE(BM_InsertDuplicate,
     unordered_set_int,
     std::unordered_set<int>{},
     getRandomIntegerInputs<int>)->Arg(TestNumInputs);
 BENCHMARK_CAPTURE(BM_InsertDuplicate,
     unordered_set_string,
     std::unordered_set<std::string>{},
BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
     std::unordered_set<int>{},
     getRandomIntegerInputs<unsigned>)->Arg(TestNumInputs);
 
 BENCHMARK_CAPTURE(BM_EmplaceDuplicate,
     unordered_set_string_arg,
     std::unordered_set<std::string>{},
     getRandomCStringInputs)->Arg(TestNumInputs);
 
 BENCHMARK_MAIN();

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 _UniqueKeys> 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;
 
private:
     explicit __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
         : __node_(__node)
         {
             (void)__c;
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
             __get_db()->__insert_ic(this, __c);
 #endif
         }
-    template <class, class, class, class> friend class __hash_table;
+    template <class, class, class, class, class> friend class __hash_table;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
     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 _NodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator
private:
     explicit __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
         : __node_(__node)
         {
             (void)__c;
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
             __get_db()->__insert_ic(this, __c);
 #endif
         }
-    template <class, class, class, class> friend class __hash_table;
+    template <class, class, class, class, class> friend class __hash_table;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
     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 _NodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator
 {
explicit __hash_local_iterator(__next_pointer __node, size_t __bucket,
         {
             (void)__c;
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
             __get_db()->__insert_ic(this, __c);
 #endif
             if (__node_ != nullptr)
                 __node_ = __node_->__next_;
         }
-    template <class, class, class, class> friend class __hash_table;
+    template <class, class, class, class, class> friend class __hash_table;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 };
 
 template <class _ConstNodePtr>
 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator
 {
     typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
explicit __hash_const_local_iterator(__next_pointer __node_ptr, size_t __bucket,
         {
             (void)__c;
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
             __get_db()->__insert_ic(this, __c);
 #endif
             if (__node_ != nullptr)
                 __node_ = __node_->__next_;
         }
-    template <class, class, class, class> friend class __hash_table;
+    template <class, class, class, class, class> friend class __hash_table;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 };
 
 template <class _Alloc>
 class __bucket_list_deallocator
 {
     typedef _Alloc                                          allocator_type;
     typedef allocator_traits<allocator_type>                __alloc_traits;

 __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>
+// Since both unordered_set/map and unordered_multiset/multimap 
+// use the same implementation of hash_table we might do reduntant work 
+// for unique keys containers (namely calling key_eq in rehashing).
+// This trait helps to distinguish between unique keys/non-unique keys containers.
+template <bool _UniqueKeys>
+struct __hash_table_unique_keys : std::integral_constant<bool, _UniqueKeys> {};
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 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;
     typedef typename
       __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
                                                                      _NodeTypes;
 public:
 
#if _LIBCPP_STD_VER > 14
     _LIBCPP_INLINE_VISIBILITY
     iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
     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)
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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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,
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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)
 {
 }
 
-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 _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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())
 {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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_)
 {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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_)
 {
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
     }
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
         }
     }
 }
 
-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 _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::~__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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>&
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>&
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__deallocate_node(__next_pointer __np)
     _NOEXCEPT
 {
     __node_allocator& __na = __node_alloc();
     while (__np != nullptr)
     {
         __next_pointer __next = __np->__next_;
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
         __c_node* __c = __get_db()->__find_c_and_lock(this);

 #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
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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());
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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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());
#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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline
-__hash_table<_Tp, _Hash, _Equal, _Alloc>&
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>&
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _InputIterator>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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");
 
     if (bucket_count() != 0)
#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 _UniqueKeys>
 template <class _InputIterator>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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");
#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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::begin() _NOEXCEPT
 {
     return iterator(__p1_.first().__next_, this);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::end() _NOEXCEPT
 {
     return iterator(nullptr, this);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::const_iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::begin() const _NOEXCEPT
 {
     return const_iterator(__p1_.first().__next_, this);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::const_iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::end() const _NOEXCEPT
 {
     return const_iterator(nullptr, this);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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;
     }
 }
 
 
 // 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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 _LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_insert_unique_prepare(
     size_t __hash, value_type& __value)
 {
     size_type __bc = bucket_count();
 
     if (__bc != 0)
     {
         size_t __chash = __constrain_hash(__hash, __bc);
         __next_pointer __ndptr = __bucket_list_[__chash];
__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_insert_unique_prepare(
     }
     return nullptr;
 }
 
 // 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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 _LIBCPP_INLINE_VISIBILITY
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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);
 }
 
 // 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(
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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();
__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_insert_multi_prepare(
     return __pn;
 }
 
 // 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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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_;
else
             if (__nhash != __chash)
                 __bucket_list_[__nhash] = __cp->__ptr();
         }
     }
     ++size();
 }
 
 
-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)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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);
 
     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(
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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_;
if (__p != end() && key_eq()(*__p, __cp->__value_))
         ++size();
         return iterator(static_cast<__next_pointer>(__cp), this);
     }
     return __node_insert_multi(__cp);
 }
 
 
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 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)
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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)
if (__bc != 0)
         // increment size
         ++size();
         __inserted = true;
     }
 __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 _UniqueKeys>
 template <class... _Args>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class... _Args>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__emplace_multi(_Args&&... __args)
 {
     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
     iterator __r = __node_insert_multi(__h.get());
     __h.release();
     return __r;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class... _Args>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
 }
 
 #if _LIBCPP_STD_VER > 14
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _NodeHandle, class _InsertReturnType>
 _LIBCPP_INLINE_VISIBILITY
 _InsertReturnType
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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)};
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _NodeHandle>
 _LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _NodeHandle>
 _LIBCPP_INLINE_VISIBILITY
 _NodeHandle
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_handle_extract(
     key_type const& __key)
 {
     iterator __i = find(__key);
     if (__i == end())
         return _NodeHandle();
     return __node_handle_extract<_NodeHandle>(__i);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _NodeHandle>
 _LIBCPP_INLINE_VISIBILITY
 _NodeHandle
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_handle_extract(
     const_iterator __p)
 {
     allocator_type __alloc(__node_alloc());
     return _NodeHandle(remove(__p).release(), __alloc);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _Table>
 _LIBCPP_INLINE_VISIBILITY
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_handle_merge_unique(
     _Table& __source)
 {
     static_assert(is_same<__node, typename _Table::__node>::value, "");
 
     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);
         }
     }
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _NodeHandle>
 _LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_handle_insert_multi(
     _NodeHandle&& __nh)
 {
     if (__nh.empty())
         return end();
     iterator __result = __node_insert_multi(__nh.__ptr_);
     __nh.__release_ptr();
     return __result;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _NodeHandle>
 _LIBCPP_INLINE_VISIBILITY
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _Table>
 _LIBCPP_INLINE_VISIBILITY
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_handle_merge_multi(
     _Table& __source)
 {
     static_assert(is_same<typename _Table::__node, __node>::value, "");
 
     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);
     }
 }
 #endif // _LIBCPP_STD_VER > 14
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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)
     {
if (__nbc > 0)
                     {
                         __bucket_list_[__chash] = __pp;
                         __pp = __cp;
                         __phash = __chash;
                     }
                     else
                     {
                         __next_pointer __np = __cp;
+                        if _LIBCPP_CONSTEXPR_AFTER_CXX14 (!_UniqueKeys::value) {
                             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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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();
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::const_iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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();
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class ..._Args>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _First, class ..._Rest>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__erase_unique(const _Key& __k)
 {
     iterator __i = find(__k);
     if (__i == end())
         return 0;
     erase(__i);
     return 1;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
 }
 
-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
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__node_holder
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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_)
for (__i_node** __dp = __c->end_; __dp != __c->beg_; )
                 _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 _UniqueKeys>
 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
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__count_unique(const _Key& __k) const
 {
     return static_cast<size_type>(find(__k) != end());
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 template <class _Key>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 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(
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__equal_range_unique(
         const _Key& __k)
 {
     iterator __i = find(__k);
     iterator __j = __i;
     if (__i != end())
         ++__j;
     return pair<iterator, iterator>(__i, __j);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 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(
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::const_iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::const_iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 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(
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 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(
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::const_iterator,
+     typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::const_iterator>
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__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);
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 void
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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)
             )
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
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::size_type
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::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>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 inline _LIBCPP_INLINE_VISIBILITY
 void
-swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
-     __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
+swap(__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>& __x,
+     __hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 {
     __x.swap(__y);
 }
 
 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__dereferenceable(const const_iterator* __i) const
 {
     return __i->__node_ != nullptr;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__decrementable(const const_iterator*) const
 {
     return false;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__addable(const const_iterator*, ptrdiff_t) const
 {
     return false;
 }
 
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Tp, class _Hash, class _Equal, class _Alloc, class _UniqueKeys>
 bool
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
+__hash_table<_Tp, _Hash, _Equal, _Alloc, _UniqueKeys>::__subscriptable(const const_iterator*, ptrdiff_t) const
 {
     return false;
 }
 
 #endif // _LIBCPP_ENABLE_DEBUG_MODE
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___HASH_TABLE

libcxx/include/__node_handle

template <class _NodeType, class _Alloc,
           template <class, class> class _MapOrSetSpecifics>
 class _LIBCPP_TEMPLATE_VIS __basic_node_handle
     : public _MapOrSetSpecifics<
           _NodeType,
           __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>
 {
     template <class _Tp, class _Compare, class _Allocator>
         friend class __tree;
-    template <class _Tp, class _Hash, class _Equal, class _Allocator>
+    template <class _Tp, class _Hash, class _Equal, class _Allocator, class _UniqueKeys>
         friend class __hash_table;
     friend struct _MapOrSetSpecifics<
         _NodeType, __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>;
 
     typedef allocator_traits<_Alloc> __alloc_traits;
     typedef typename __rebind_pointer<typename __alloc_traits::void_pointer,
                                       _NodeType>::type
         __node_pointer_type;

libcxx/include/ext/hash_map

 private:
     typedef std::pair<key_type, mapped_type>                    __value_type;
     typedef __hash_map_hasher<__value_type, hasher>   __hasher;
     typedef __hash_map_equal<__value_type, key_equal> __key_equal;
     typedef typename std::__rebind_alloc_helper<
         std::allocator_traits<allocator_type>, __value_type>::type __allocator_type;
 
     typedef std::__hash_table<__value_type, __hasher,
-                         __key_equal,  __allocator_type>   __table;
+                         __key_equal,  __allocator_type, std::__hash_table_unique_keys<true> >   __table;
 
     __table __table_;
 
     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;
     typedef typename __table::__node                       __node;

 
 private:
     typedef std::pair<key_type, mapped_type>               __value_type;
     typedef __hash_map_hasher<__value_type, hasher>   __hasher;
     typedef __hash_map_equal<__value_type, key_equal> __key_equal;
     typedef typename std::__rebind_alloc_helper<std::allocator_traits<allocator_type>, __value_type>::type __allocator_type;
 
     typedef std::__hash_table<__value_type, __hasher,
-                         __key_equal,  __allocator_type>   __table;
+                         __key_equal,  __allocator_type, std::__hash_table_unique_keys<false> >   __table;
 
     __table __table_;
 
     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;
     typedef std::unique_ptr<__node, _Dp>                         __node_holder;

libcxx/include/ext/hash_set

public:
     typedef key_type                                                   value_type;
     typedef _Hash                                                      hasher;
     typedef _Pred                                                      key_equal;
     typedef _Alloc                                                     allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
 
 private:
-    typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
+    typedef std::__hash_table<value_type, hasher, 
+                key_equal, allocator_type, std::__hash_table_unique_keys<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;
public:
     typedef key_type                                                   value_type;
     typedef _Hash                                                      hasher;
     typedef _Pred                                                      key_equal;
     typedef _Alloc                                                     allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
 
 private:
-    typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
+    typedef std::__hash_table<value_type, hasher, 
+                key_equal, allocator_type, std::__hash_table_unique_keys<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;

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;
+                         __key_equal,  __allocator_type, __hash_table_unique_keys<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;
+                         __key_equal,  __allocator_type, __hash_table_unique_keys<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_unique_keys<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;
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_unique_keys<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;