Implement deduction guides for <unordered_set>

[• Quuxplusone]

Summary

In this case (alone) I needed to make allocator_type, hasher, and key_equal opaque to deduction using the __identity metafunction. With the original non-opaque aliases, some of the implicit deduction guides from unordered_set's constructors were interfering with deduction from the explicit deduction guides.

Specifically, if you leave typedef _Hash hasher alone:

test/std/containers/unord/unord.set/unord.set.cnstr/deduct.pass.cpp:180:24: note: in instantiation of member function 'std::__1::unordered_set<int, test_allocator<int>, std::__1::equal_to<int>, std::__1::allocator<int> >::unordered_set' requested here
    std::unordered_set s({ 1, 2, 1, INT_MAX, 3 }, 42, test_allocator<int>(0, 43));
                       ^

(Here we want to pick up the deduction guide for unordered_set(initializer_list, Size, Allocator) but it looks like overload resolution is preferring the guide implicitly generated from the constructor unordered_set(initializer_list, Size, Hash) instead. I think this might even be correct behavior according to the paper standard. I'll have to check with e.g. Mike Spertus about what's the intent of http://eel.is/c++draft/unord.req#18 "A deduction guide for an unordered associative container shall not participate in overload resolution if ... it has a Hash template parameter and an integral type or a type that qualifies as an allocator is deduced for that parameter." Namely, is this supposed to apply to just the explicit deduction guides, or the implicit ones as well?)

[• Quuxplusone]

Use ASSERT_SAME_TYPE. Add comments in deduct.fail.cpp. Rebase.

[• Quuxplusone]

Use __iter_value_type<_InputIterator> instead of iterator_traits<_InputIterator>::value_type. @mclow.lists, I think this one is ready to land now, too.

[• Quuxplusone]

Updated to use _EnableIf per EricWF's refactoring of June 23.

@mclow.lists ping! I still think this is ready to land.

[• Quuxplusone]

@mclow.lists ping!

[ostannard]

Two of the new tests are failing on the Arm and AArch64 buildbots - see for example http://lab.llvm.org:8011/builders/libcxx-libcxxabi-libunwind-armv7-linux/builds/946/steps/test.libcxx/logs/FAIL%3A%20libc%2B%2B%3A%3Adeduct.fail.cpp

[ldionne]

In D58617#1582299, @ostannard wrote:

Two of the new tests are failing on the Arm and AArch64 buildbots - see for example http://lab.llvm.org:8011/builders/libcxx-libcxxabi-libunwind-armv7-linux/builds/946/steps/test.libcxx/logs/FAIL%3A%20libc%2B%2B%3A%3Adeduct.fail.cpp

That bot is using Clang 6. r365923 adds an XFAIL for that compiler.

libcxx/trunk/include/unordered_set

 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
           class _Alloc = allocator<_Value> >
 class _LIBCPP_TEMPLATE_VIS unordered_set
 {
 public:
     // types
     typedef _Value                                                     key_type;
     typedef key_type                                                   value_type;
-    typedef _Hash                                                      hasher;
-    typedef _Pred                                                      key_equal;
-    typedef _Alloc                                                     allocator_type;
+    typedef typename __identity<_Hash>::type                           hasher;
+    typedef typename __identity<_Pred>::type                           key_equal;
+    typedef typename __identity<_Alloc>::type                          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;
 
bool __addable(const const_iterator* __i, ptrdiff_t __n) const
         {return __table_.__addable(__i, __n);}
     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
         {return __table_.__addable(__i, __n);}
 
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
 };
 
+#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
+template<class _InputIterator,
+         class _Hash = hash<__iter_value_type<_InputIterator>>,
+         class _Pred = equal_to<__iter_value_type<_InputIterator>>,
+         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<!__is_allocator<_Pred>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
+              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
+  -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
+
+template<class _Tp, class _Hash = hash<_Tp>,
+         class _Pred = equal_to<_Tp>,
+         class _Allocator = allocator<_Tp>,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<!__is_allocator<_Pred>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0,
+              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
+  -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
+
+template<class _InputIterator, class _Allocator,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_set(_InputIterator, _InputIterator,
+              typename allocator_traits<_Allocator>::size_type, _Allocator)
+  -> unordered_set<__iter_value_type<_InputIterator>,
+                   hash<__iter_value_type<_InputIterator>>,
+                   equal_to<__iter_value_type<_InputIterator>>,
+                   _Allocator>;
+
+template<class _InputIterator, class _Hash, class _Allocator,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_set(_InputIterator, _InputIterator,
+              typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
+  -> unordered_set<__iter_value_type<_InputIterator>, _Hash,
+                   equal_to<__iter_value_type<_InputIterator>>,
+                   _Allocator>;
+
+template<class _Tp, class _Allocator,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
+  -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
+
+template<class _Tp, class _Hash, class _Allocator,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
+  -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
+#endif
+
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif

 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
           class _Alloc = allocator<_Value> >
 class _LIBCPP_TEMPLATE_VIS unordered_multiset
 {
 public:
     // types
     typedef _Value                                                     key_type;
     typedef key_type                                                   value_type;
-    typedef _Hash                                                      hasher;
-    typedef _Pred                                                      key_equal;
-    typedef _Alloc                                                     allocator_type;
+    typedef typename __identity<_Hash>::type                           hasher;
+    typedef typename __identity<_Pred>::type                           key_equal;
+    typedef typename __identity<_Alloc>::type                          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;
 
bool __addable(const const_iterator* __i, ptrdiff_t __n) const
         {return __table_.__addable(__i, __n);}
     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
         {return __table_.__addable(__i, __n);}
 
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
 };
 
+#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
+template<class _InputIterator,
+         class _Hash = hash<__iter_value_type<_InputIterator>>,
+         class _Pred = equal_to<__iter_value_type<_InputIterator>>,
+         class _Allocator = allocator<__iter_value_type<_InputIterator>>,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<!__is_allocator<_Pred>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0,
+              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
+  -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>;
+
+template<class _Tp, class _Hash = hash<_Tp>,
+         class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<!__is_allocator<_Pred>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0,
+              _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
+  -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
+
+template<class _InputIterator, class _Allocator,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator)
+  -> unordered_multiset<__iter_value_type<_InputIterator>,
+                   hash<__iter_value_type<_InputIterator>>,
+                   equal_to<__iter_value_type<_InputIterator>>,
+                   _Allocator>;
+
+template<class _InputIterator, class _Hash, class _Allocator,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type,
+              _Hash, _Allocator)
+  -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash,
+                   equal_to<__iter_value_type<_InputIterator>>,
+                   _Allocator>;
+
+template<class _Tp, class _Allocator,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator)
+  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
+
+template<class _Tp, class _Hash, class _Allocator,
+         class = _EnableIf<!__is_allocator<_Hash>::value>,
+         class = _EnableIf<!is_integral<_Hash>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>>
+unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator)
+  -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
+#endif
+
 template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
 #if _LIBCPP_DEBUG_LEVEL >= 2
     __get_db()->__insert_c(this);
 #endif

libcxx/trunk/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/deduct.fail.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//        class Hash = hash<iter-value-type<InputIterator>>,
+//        class Pred = equal_to<iter-value-type<InputIterator>>,
+//        class Allocator = allocator<iter-value-type<InputIterator>>>
+// unordered_multiset(InputIterator, InputIterator, typename see below::size_type = see below,
+//                    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_multiset<iter-value-type<InputIterator>,
+//                         Hash, Pred, Allocator>;
+//
+// template<class T, class Hash = hash<T>,
+//        class Pred = equal_to<T>, class Allocator = allocator<T>>
+// unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
+//                    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_multiset<T, Hash, Pred, Allocator>;
+//
+// template<class InputIterator, class Allocator>
+// unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
+//   -> unordered_multiset<iter-value-type<InputIterator>,
+//                         hash<iter-value-type<InputIterator>>,
+//                         equal_to<iter-value-type<InputIterator>>,
+//                         Allocator>;
+//
+// template<class InputIterator, class Hash, class Allocator>
+// unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
+//                    Hash, Allocator)
+//   -> unordered_multiset<iter-value-type<InputIterator>, Hash,
+//                         equal_to<iter-value-type<InputIterator>>,
+//                         Allocator>;
+//
+// template<class T, class Allocator>
+// unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
+//   -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>;
+//
+// template<class T, class Hash, class Allocator>
+// unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
+//   -> unordered_multiset<T, Hash, equal_to<T>, Allocator>;
+
+#include <functional>
+#include <unordered_set>
+
+int main(int, char**)
+{
+    {
+        // cannot deduce Key from nothing
+        std::unordered_multiset s;
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Size)
+        std::unordered_multiset s(42);
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash)
+        std::unordered_multiset s(42, std::hash<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash, Pred)
+        std::unordered_multiset s(42, std::hash<int>(), std::equal_to<>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash, Pred, Allocator)
+        std::unordered_multiset s(42, std::hash<int>(), std::equal_to<>(), std::allocator<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Allocator)
+        std::unordered_multiset s(std::allocator<int>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Allocator)
+        std::unordered_multiset s(42, std::allocator<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash, Allocator)
+        std::unordered_multiset s(42, std::hash<short>(), std::allocator<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_multiset'}}
+    }
+
+    return 0;
+}

libcxx/trunk/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/deduct.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//        class Hash = hash<iter-value-type<InputIterator>>,
+//        class Pred = equal_to<iter-value-type<InputIterator>>,
+//        class Allocator = allocator<iter-value-type<InputIterator>>>
+// unordered_multiset(InputIterator, InputIterator, typename see below::size_type = see below,
+//                    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_multiset<iter-value-type<InputIterator>,
+//                         Hash, Pred, Allocator>;
+//
+// template<class T, class Hash = hash<T>,
+//        class Pred = equal_to<T>, class Allocator = allocator<T>>
+// unordered_multiset(initializer_list<T>, typename see below::size_type = see below,
+//                    Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_multiset<T, Hash, Pred, Allocator>;
+//
+// template<class InputIterator, class Allocator>
+// unordered_multiset(InputIterator, InputIterator, typename see below::size_type, Allocator)
+//   -> unordered_multiset<iter-value-type<InputIterator>,
+//                         hash<iter-value-type<InputIterator>>,
+//                         equal_to<iter-value-type<InputIterator>>,
+//                         Allocator>;
+//
+// template<class InputIterator, class Hash, class Allocator>
+// unordered_multiset(InputIterator, InputIterator, typename see below::size_type,
+//                    Hash, Allocator)
+//   -> unordered_multiset<iter-value-type<InputIterator>, Hash,
+//                         equal_to<iter-value-type<InputIterator>>,
+//                         Allocator>;
+//
+// template<class T, class Allocator>
+// unordered_multiset(initializer_list<T>, typename see below::size_type, Allocator)
+//   -> unordered_multiset<T, hash<T>, equal_to<T>, Allocator>;
+//
+// template<class T, class Hash, class Allocator>
+// unordered_multiset(initializer_list<T>, typename see below::size_type, Hash, Allocator)
+//   -> unordered_multiset<T, Hash, equal_to<T>, Allocator>;
+
+#include <algorithm> // is_permutation
+#include <cassert>
+#include <climits> // INT_MAX
+#include <type_traits>
+#include <unordered_set>
+
+#include "test_allocator.h"
+
+int main(int, char**)
+{
+    const int expected_s[] = {1, 1, 2, 3, INT_MAX};
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_multiset s(std::begin(arr), std::end(arr));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_multiset s(std::begin(arr), std::end(arr), 42);
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_multiset s(std::begin(arr), std::end(arr), 42, std::hash<short>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<short>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_multiset s(std::begin(arr), std::end(arr), 42, std::hash<short>(), test_allocator<int>(0, 40));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<short>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 40);
+    }
+
+    {
+    std::unordered_multiset<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_multiset s(source);
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    }
+
+    {
+    std::unordered_multiset<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_multiset s{source};  // braces instead of parens
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    }
+
+    {
+    std::unordered_multiset<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_multiset s(source, test_allocator<int>(0, 41));
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    assert(s.get_allocator().get_id() == 41);
+    }
+
+    {
+    std::unordered_multiset<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_multiset s{source, test_allocator<int>(0, 42)};  // braces instead of parens
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    assert(s.get_allocator().get_id() == 42);
+    }
+
+    {
+    std::unordered_multiset s{ 1, 2, 1, INT_MAX, 3 };
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_multiset s({ 1, 2, 1, INT_MAX, 3 }, 42);
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_multiset s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<short>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_multiset s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>(), std::equal_to<>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<short>, std::equal_to<>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_multiset s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>(), std::equal_to<>(), test_allocator<int>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<short>, std::equal_to<>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 43);
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_multiset s(std::begin(arr), std::end(arr), 42, test_allocator<int>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 44);
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_multiset s(std::begin(arr), std::end(arr), 42, std::hash<short>(), test_allocator<int>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<short>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 44);
+    }
+
+    {
+    std::unordered_multiset s({ 1, 2, 1, INT_MAX, 3 }, 42, test_allocator<int>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 43);
+    }
+
+    {
+    std::unordered_multiset s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>(), test_allocator<int>(0, 42));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_multiset<int, std::hash<short>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 42);
+    }
+
+    return 0;
+}

libcxx/trunk/test/std/containers/unord/unord.set/unord.set.cnstr/deduct.fail.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//        class Hash = hash<iter-value-type<InputIterator>>,
+//        class Pred = equal_to<iter-value-type<InputIterator>>,
+//        class Allocator = allocator<iter-value-type<InputIterator>>>
+// unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
+//               Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_set<iter-value-type<InputIterator>,
+//                    Hash, Pred, Allocator>;
+//
+// template<class T, class Hash = hash<T>,
+//        class Pred = equal_to<T>, class Allocator = allocator<T>>
+// unordered_set(initializer_list<T>, typename see below::size_type = see below,
+//               Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_set<T, Hash, Pred, Allocator>;
+//
+// template<class InputIterator, class Allocator>
+// unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
+//   -> unordered_set<iter-value-type<InputIterator>,
+//                    hash<iter-value-type<InputIterator>>,
+//                    equal_to<iter-value-type<InputIterator>>,
+//                    Allocator>;
+//
+// template<class InputIterator, class Hash, class Allocator>
+// unordered_set(InputIterator, InputIterator, typename see below::size_type,
+//               Hash, Allocator)
+//   -> unordered_set<iter-value-type<InputIterator>, Hash,
+//                    equal_to<iter-value-type<InputIterator>>,
+//                    Allocator>;
+//
+// template<class T, class Allocator>
+// unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
+//   -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
+//
+// template<class T, class Hash, class Allocator>
+// unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
+//   -> unordered_set<T, Hash, equal_to<T>, Allocator>;
+
+#include <functional>
+#include <unordered_set>
+
+int main(int, char**)
+{
+    {
+        // cannot deduce Key from nothing
+        std::unordered_set s;
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+    {
+        // cannot deduce Key from just (Size)
+        std::unordered_set s(42);
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash)
+        std::unordered_set s(42, std::hash<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash, Pred)
+        std::unordered_set s(42, std::hash<int>(), std::equal_to<>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash, Pred, Allocator)
+        std::unordered_set s(42, std::hash<int>(), std::equal_to<>(), std::allocator<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+    {
+        // cannot deduce Key from just (Allocator)
+        std::unordered_set s(std::allocator<int>{});
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Allocator)
+        std::unordered_set s(42, std::allocator<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+    {
+        // cannot deduce Key from just (Size, Hash, Allocator)
+        std::unordered_set s(42, std::hash<short>(), std::allocator<int>());
+            // expected-error@-1{{no viable constructor or deduction guide for deduction of template arguments of 'unordered_set'}}
+    }
+
+    return 0;
+}

libcxx/trunk/test/std/containers/unord/unord.set/unord.set.cnstr/deduct.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <unordered_set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//        class Hash = hash<iter-value-type<InputIterator>>,
+//        class Pred = equal_to<iter-value-type<InputIterator>>,
+//        class Allocator = allocator<iter-value-type<InputIterator>>>
+// unordered_set(InputIterator, InputIterator, typename see below::size_type = see below,
+//               Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_set<iter-value-type<InputIterator>,
+//                    Hash, Pred, Allocator>;
+//
+// template<class T, class Hash = hash<T>,
+//        class Pred = equal_to<T>, class Allocator = allocator<T>>
+// unordered_set(initializer_list<T>, typename see below::size_type = see below,
+//               Hash = Hash(), Pred = Pred(), Allocator = Allocator())
+//   -> unordered_set<T, Hash, Pred, Allocator>;
+//
+// template<class InputIterator, class Allocator>
+// unordered_set(InputIterator, InputIterator, typename see below::size_type, Allocator)
+//   -> unordered_set<iter-value-type<InputIterator>,
+//                    hash<iter-value-type<InputIterator>>,
+//                    equal_to<iter-value-type<InputIterator>>,
+//                    Allocator>;
+//
+// template<class InputIterator, class Hash, class Allocator>
+// unordered_set(InputIterator, InputIterator, typename see below::size_type,
+//               Hash, Allocator)
+//   -> unordered_set<iter-value-type<InputIterator>, Hash,
+//                    equal_to<iter-value-type<InputIterator>>,
+//                    Allocator>;
+//
+// template<class T, class Allocator>
+// unordered_set(initializer_list<T>, typename see below::size_type, Allocator)
+//   -> unordered_set<T, hash<T>, equal_to<T>, Allocator>;
+//
+// template<class T, class Hash, class Allocator>
+// unordered_set(initializer_list<T>, typename see below::size_type, Hash, Allocator)
+//   -> unordered_set<T, Hash, equal_to<T>, Allocator>;
+
+#include <algorithm> // is_permutation
+#include <cassert>
+#include <climits> // INT_MAX
+#include <type_traits>
+#include <unordered_set>
+
+#include "test_allocator.h"
+
+int main(int, char**)
+{
+    const int expected_s[] = {1, 2, 3, INT_MAX};
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_set s(std::begin(arr), std::end(arr));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_set s(std::begin(arr), std::end(arr), 42);
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_set s(std::begin(arr), std::end(arr), 42, std::hash<short>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<short>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_set s(std::begin(arr), std::end(arr), 42, std::hash<short>(), test_allocator<int>(0, 40));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<short>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 40);
+    }
+
+    {
+    std::unordered_set<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_set s(source);
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    }
+
+    {
+    std::unordered_set<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_set s{source};  // braces instead of parens
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    }
+
+    {
+    std::unordered_set<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_set s(source, test_allocator<int>(0, 41));
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    assert(s.get_allocator().get_id() == 41);
+    }
+
+    {
+    std::unordered_set<int, std::hash<short>, std::equal_to<>, test_allocator<int>> source;
+    std::unordered_set s{source, test_allocator<int>(0, 42)};  // braces instead of parens
+    ASSERT_SAME_TYPE(decltype(s), decltype(source));
+    assert(s.size() == 0);
+    assert(s.get_allocator().get_id() == 42);
+    }
+
+    {
+    std::unordered_set s{ 1, 2, 1, INT_MAX, 3 };
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_set s({ 1, 2, 1, INT_MAX, 3 }, 42);
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_set s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<short>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_set s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>(), std::equal_to<>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<short>, std::equal_to<>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::unordered_set s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>(), std::equal_to<>(), test_allocator<int>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<short>, std::equal_to<>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 43);
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_set s(std::begin(arr), std::end(arr), 42, test_allocator<int>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<int>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 44);
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::unordered_set s(std::begin(arr), std::end(arr), 42, std::hash<short>(), test_allocator<int>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<short>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 44);
+    }
+
+    {
+    std::unordered_set s({ 1, 2, 1, INT_MAX, 3 }, 42, test_allocator<int>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<int>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 43);
+    }
+
+    {
+    std::unordered_set s({ 1, 2, 1, INT_MAX, 3 }, 42, std::hash<short>(), test_allocator<int>(0, 42));
+
+    ASSERT_SAME_TYPE(decltype(s), std::unordered_set<int, std::hash<short>, std::equal_to<int>, test_allocator<int>>);
+    assert(std::is_permutation(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 42);
+    }
+
+    return 0;
+}