Implement P0433: deduction guides for <set>

[• Quuxplusone]

Summary

(AFAIK, P0433 was adopted into C++17 at Kona 2017.)

Modeled on D46975, D46964, etc.
See also D58587, D58590, D58617.

[• Quuxplusone]

Oops, fix a cut-and-paste thinko in the test for multiset.

[• Quuxplusone]

Use ASSERT_SAME_TYPE. Better comments in the .fail.cpp file.

[EricWF]

Could you please specify what paper you're implementing in the description?

test/std/containers/associative/set/set.cons/deduct.pass.cpp

43

clang-format any new files please.

[• Quuxplusone]

clang-format'ed.

[• Quuxplusone]

Rebased on master.

@EricWF ping?

(Is "CTAD for container types" similar to "polymorphic memory resources" in the bucket of "things libc++ doesn't want to implement for engineering reasons," and if so, could you guys go on record with that? It would be less dysfunctional than the current model.)

[EricWF]

In D58582#1473518, @Quuxplusone wrote:

Rebased on master.

@EricWF ping?

(Is "CTAD for container types" similar to "polymorphic memory resources" in the bucket of "things libc++ doesn't want to implement for engineering reasons," and if so, could you guys go on record with that? It would be less dysfunctional than the current model.)

No, it is not like that.

I've just been quite busy. Please ping this weekly to help it gain attention. I'll try to take a look at it this week.

[mclow.lists]

A couple of minor nits.
Same comment about __identify as in the other review. You need answer it in one place, only.

test/std/containers/associative/multiset/multiset.cons/deduct.pass.cpp

89

A comment here "braces instead of paren" would be nice.

105

These should all be const

[mclow.lists]

Almost there. A couple nits, a few consts, and landing D58587, and we're done.

include/set

858

Any reason that you're not using __iter_value_type here? (Besides that it is declared in D58587)

1357

same comment re: __iter_value_type

test/std/containers/associative/set/set.cons/deduct.pass.cpp

95

Please change to std::allocator<long> When we tighten up the constraints on set, it won't break this test.

[• Quuxplusone]

include/set

858

No, I think just that it's declared in D58587. I was thinking of <set> as the first thing to land and then <map> after that, but I see how it might make more sense to land <map> first, with all the helper aliases, and then rebase <set> on top of it.

[• Quuxplusone]

Review comments. (Add "braces instead of parens" comment; add const to int expected_s[] throughout)

[• Quuxplusone]

Update the tests to no longer test P1518R0 (although it is still supported by the code); this is the same thing I did in my last edit to D58587.

@mclow.lists ping! I think this one is now ready to land, unless I missed something.

include/set

 class _LIBCPP_TEMPLATE_VIS set
 {
 public:
     // types:
     typedef _Key                                     key_type;
     typedef key_type                                 value_type;
     typedef _Compare                                 key_compare;
     typedef key_compare                              value_compare;
-    typedef _Allocator                               allocator_type;
+    typedef typename __identity<_Allocator>::type    allocator_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
 
     static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                   "Allocator::value_type must be same type as value_type");
 
 private:
#if _LIBCPP_STD_VER > 11
     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
     template <typename _K2>
     _LIBCPP_INLINE_VISIBILITY
     typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
 #endif
 };
 
+#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
+template<class _InputIterator,
+         class _Compare = less<typename iterator_traits<_InputIterator>::value_type>,
+         class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type>
+set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
+  -> set<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>;
+
+template<class _Key, class _Compare = less<_Key>,
+         class _Allocator = allocator<_Key>,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type>
+set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
+  -> set<_Key, _Compare, _Allocator>;
+
+template<class _InputIterator, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+set(_InputIterator, _InputIterator, _Allocator)
+  -> set<typename iterator_traits<_InputIterator>::value_type,
+         less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>;
+
+template<class _Key, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+set(initializer_list<_Key>, _Allocator)
+  -> set<_Key, less<_Key>, _Allocator>;
+#endif
+
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Compare, class _Allocator>
 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
     : __tree_(_VSTD::move(__s.__tree_), __a)
 {
     if (__a != __s.get_allocator())
     {

 class _LIBCPP_TEMPLATE_VIS multiset
 {
 public:
     // types:
     typedef _Key                                      key_type;
     typedef key_type                                 value_type;
     typedef _Compare                                  key_compare;
     typedef key_compare                              value_compare;
-    typedef _Allocator                                allocator_type;
+    typedef typename __identity<_Allocator>::type    allocator_type;
     typedef value_type&                              reference;
     typedef const value_type&                        const_reference;
 
     static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
     static_assert((is_same<typename allocator_type::value_type, value_type>::value),
                   "Allocator::value_type must be same type as value_type");
 
 private:
#if _LIBCPP_STD_VER > 11
     equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
     template <typename _K2>
     _LIBCPP_INLINE_VISIBILITY
     typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
     equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
 #endif
 };
 
+#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
+template<class _InputIterator,
+         class _Compare = less<typename iterator_traits<_InputIterator>::value_type>,
+         class _Allocator = allocator<typename iterator_traits<_InputIterator>::value_type>,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type>
+multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
+  -> multiset<typename iterator_traits<_InputIterator>::value_type, _Compare, _Allocator>;
+
+template<class _Key, class _Compare = less<_Key>,
+         class _Allocator = allocator<_Key>,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type,
+         class = typename enable_if<!__is_allocator<_Compare>::value, void>::type>
+multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())
+  -> multiset<_Key, _Compare, _Allocator>;
+
+template<class _InputIterator, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+multiset(_InputIterator, _InputIterator, _Allocator)
+  -> multiset<typename iterator_traits<_InputIterator>::value_type,
+         less<typename iterator_traits<_InputIterator>::value_type>, _Allocator>;
+
+template<class _Key, class _Allocator,
+         class = typename enable_if<__is_allocator<_Allocator>::value, void>::type>
+multiset(initializer_list<_Key>, _Allocator)
+  -> multiset<_Key, less<_Key>, _Allocator>;
+#endif
+
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Compare, class _Allocator>
 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
     : __tree_(_VSTD::move(__s.__tree_), __a)
 {
     if (__a != __s.get_allocator())
     {

test/std/containers/associative/multiset/multiset.cons/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
+//
+//===----------------------------------------------------------------------===//
+
+// <set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// multiset(InputIterator, InputIterator,
+//          Compare = Compare(), Allocator = Allocator())
+//   -> multiset<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> multiset<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// multiset(InputIterator, InputIterator, Allocator)
+//   -> multiset<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// multiset(initializer_list<Key>, Allocator)
+//   -> multiset<Key, less<Key>, Allocator>;
+
+#include <functional>
+#include <set>
+#include <type_traits>
+
+struct NotAnAllocator {
+    friend bool operator<(NotAnAllocator, NotAnAllocator) { return false; }
+};
+
+int main(int, char**)
+{
+    {
+        // cannot deduce Key from nothing
+        std::multiset s; // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Compare)
+        std::multiset s(std::less<int>{}); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'multiset'}}
+    }
+    {
+        // cannot deduce Key from just (Compare, Allocator)
+        std::multiset s(std::less<int>{}, std::allocator<int>{}); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'multiset'}}
+    }
+    {
+        // cannot deduce Key from multiset(Allocator)
+        std::multiset s(std::allocator<int>{}); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'multiset'}}
+    }
+    {
+        // since we have parens, not braces, this deliberately does not find the initializer_list constructor
+        NotAnAllocator a;
+        std::multiset s(a); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'multiset'}}
+    }
+
+  return 0;
+}

test/std/containers/associative/multiset/multiset.cons/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
+//
+//===----------------------------------------------------------------------===//
+
+// <set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// multiset(InputIterator, InputIterator,
+//          Compare = Compare(), Allocator = Allocator())
+//   -> multiset<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> multiset<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// multiset(InputIterator, InputIterator, Allocator)
+//   -> multiset<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// multiset(initializer_list<Key>, Allocator)
+//   -> multiset<Key, less<Key>, Allocator>;
+
+#include <algorithm> // std::equal
+#include <cassert>
+#include <climits> // INT_MAX
+#include <functional>
+#include <set>
+#include <type_traits>
+
+#include "test_allocator.h"
+
+struct NotAnAllocator {
+    friend bool operator<(NotAnAllocator, NotAnAllocator) { return false; }
+};
+
+int main(int, char**)
+{
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::multiset s(std::begin(arr), std::end(arr));
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int>);
+    int expected_s[] = {1, 1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::multiset s(std::begin(arr), std::end(arr), std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int, std::greater<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1, 1};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::multiset s(std::begin(arr), std::end(arr), std::greater<int>(), test_allocator<int>(0, 42));
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int, std::greater<int>, test_allocator<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1, 1};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 42);
+    }
+
+    {
+    std::multiset<long> source;
+    std::multiset s(source);
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<long>);
+    assert(s.size() == 0);
+    }
+
+    {
+    std::multiset<long> source;
+    std::multiset s{source};
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<long>);
+    assert(s.size() == 0);
+    }
+
+    {
+    std::multiset<long> source;
+    std::multiset s(source, std::allocator<int>());
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<long>);
+    assert(s.size() == 0);
+    }
+
+    {
+    std::multiset s{ 1, 2, 1, INT_MAX, 3 };
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int>);
+    int expected_s[] = {1, 1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::multiset s({ 1, 2, 1, INT_MAX, 3 }, std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int, std::greater<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1, 1};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::multiset s({ 1, 2, 1, INT_MAX, 3 }, std::greater<int>(), test_allocator<int>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int, std::greater<int>, test_allocator<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1, 1};
+    assert(std::equal(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::multiset s(std::begin(arr), std::end(arr), test_allocator<int>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int, std::less<int>, test_allocator<int>>);
+    int expected_s[] = {1, 1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 44);
+    }
+
+    {
+    std::multiset s({ 1, 2, 1, INT_MAX, 3 }, test_allocator<int>(0, 45));
+
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int, std::less<int>, test_allocator<int>>);
+    int expected_s[] = {1, 1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 45);
+    }
+
+    {
+    NotAnAllocator a;
+    std::multiset s{a}; // multiset(initializer_list<NotAnAllocator>)
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<NotAnAllocator>);
+    assert(s.size() == 1);
+    }
+
+    {
+    std::multiset<long> source;
+    std::multiset s{source, source}; // multiset(initializer_list<multiset<long>>)
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<std::multiset<long>>);
+    assert(s.size() == 2);
+    }
+
+    {
+    NotAnAllocator a;
+    std::multiset s{a, a}; // multiset(initializer_list<NotAnAllocator>)
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<NotAnAllocator>);
+    assert(s.size() == 2);
+    }
+
+    {
+    int source[3] = {3, 4, 5};
+    std::multiset s(source, source + 3); // multiset(InputIterator, InputIterator)
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int>);
+    assert(s.size() == 3);
+    }
+
+    {
+    int source[3] = {3, 4, 5};
+    std::multiset s{source, source + 3}; // multiset(initializer_list<int*>)
+    ASSERT_SAME_TYPE(decltype(s), std::multiset<int*>);
+    assert(s.size() == 2);
+    }
+
+  return 0;
+}

test/std/containers/associative/set/set.cons/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
+//
+//===----------------------------------------------------------------------===//
+
+// <set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// set(InputIterator, InputIterator,
+//     Compare = Compare(), Allocator = Allocator())
+//   -> set<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> set<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// set(InputIterator, InputIterator, Allocator)
+//   -> set<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// set(initializer_list<Key>, Allocator)
+//   -> set<Key, less<Key>, Allocator>;
+
+#include <functional>
+#include <set>
+#include <type_traits>
+
+struct NotAnAllocator {
+    friend bool operator<(NotAnAllocator, NotAnAllocator) { return false; }
+};
+
+int main(int, char**)
+{
+    {
+        // cannot deduce Key from nothing
+        std::set s; // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'set'}}
+    }
+    {
+        // cannot deduce Key from just (Compare)
+        std::set s(std::less<int>{}); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'set'}}
+    }
+    {
+        // cannot deduce Key from just (Compare, Allocator)
+        std::set s(std::less<int>{}, std::allocator<int>{}); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'set'}}
+    }
+    {
+        // cannot deduce Key from just (Allocator)
+        std::set s(std::allocator<int>{}); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'set'}}
+    }
+    {
+        // since we have parens, not braces, this deliberately does not find the initializer_list constructor
+        NotAnAllocator a;
+        std::set s(a); // expected-error{{no viable constructor or deduction guide for deduction of template arguments of 'set'}}
+    }
+
+  return 0;
+}

test/std/containers/associative/set/set.cons/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
+//
+//===----------------------------------------------------------------------===//
+
+// <set>
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+// UNSUPPORTED: libcpp-no-deduction-guides
+
+// template<class InputIterator,
+//          class Compare = less<iter-value-type<InputIterator>>,
+//          class Allocator = allocator<iter-value-type<InputIterator>>>
+// set(InputIterator, InputIterator,
+//     Compare = Compare(), Allocator = Allocator())
+//   -> set<iter-value-type<InputIterator>, Compare, Allocator>;
+// template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
+// set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
+//   -> set<Key, Compare, Allocator>;
+// template<class InputIterator, class Allocator>
+// set(InputIterator, InputIterator, Allocator)
+//   -> set<iter-value-type<InputIterator>, less<iter-value-type<InputIterator>>, Allocator>;
+// template<class Key, class Allocator>
+// set(initializer_list<Key>, Allocator)
+//   -> set<Key, less<Key>, Allocator>;
+
+#include <algorithm> // std::equal
+#include <cassert>
+#include <climits> // INT_MAX
+#include <functional>
+#include <set>
+#include <type_traits>
+
+#include "test_allocator.h"
+
+struct NotAnAllocator {
+    friend bool operator<(NotAnAllocator, NotAnAllocator) { return false; }
+};
+
+int main(int, char**)
+{
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::set s(std::begin(arr), std::end(arr));
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int>);
+    int expected_s[] = {1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::set s(std::begin(arr), std::end(arr), std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int, std::greater<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    const int arr[] = { 1, 2, 1, INT_MAX, 3 };
+    std::set s(std::begin(arr), std::end(arr), std::greater<int>(), test_allocator<int>(0, 42));
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int, std::greater<int>, test_allocator<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 42);
+    }
+
+    {
+    std::set<long> source;
+    std::set s(source);
+    ASSERT_SAME_TYPE(decltype(s), std::set<long>);
+    assert(s.size() == 0);
+    }
+
+    {
+    std::set<long> source;
+    std::set s{source};
+    ASSERT_SAME_TYPE(decltype(s), std::set<long>);
+    assert(s.size() == 0);
+    }
+
+    {
+    std::set<long> source;
+    std::set s(source, std::allocator<int>());
+    ASSERT_SAME_TYPE(decltype(s), std::set<long>);
+    assert(s.size() == 0);
+    }
+
+    {
+    std::set s{ 1, 2, 1, INT_MAX, 3 };
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int>);
+    int expected_s[] = {1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::set s({ 1, 2, 1, INT_MAX, 3 }, std::greater<int>());
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int, std::greater<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    }
+
+    {
+    std::set s({ 1, 2, 1, INT_MAX, 3 }, std::greater<int>(), test_allocator<int>(0, 43));
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int, std::greater<int>, test_allocator<int>>);
+    int expected_s[] = {INT_MAX, 3, 2, 1};
+    assert(std::equal(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::set s(std::begin(arr), std::end(arr), test_allocator<int>(0, 44));
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int, std::less<int>, test_allocator<int>>);
+    int expected_s[] = {1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 44);
+    }
+
+    {
+    std::set s({ 1, 2, 1, INT_MAX, 3 }, test_allocator<int>(0, 45));
+
+    ASSERT_SAME_TYPE(decltype(s), std::set<int, std::less<int>, test_allocator<int>>);
+    int expected_s[] = {1, 2, 3, INT_MAX};
+    assert(std::equal(s.begin(), s.end(), std::begin(expected_s), std::end(expected_s)));
+    assert(s.get_allocator().get_id() == 45);
+    }
+
+    {
+    NotAnAllocator a;
+    std::set s{a}; // set(initializer_list<NotAnAllocator>)
+    ASSERT_SAME_TYPE(decltype(s), std::set<NotAnAllocator>);
+    assert(s.size() == 1);
+    }
+
+    {
+    std::set<long> source;
+    std::set s{source, source}; // set(initializer_list<set<long>>)
+    ASSERT_SAME_TYPE(decltype(s), std::set<std::set<long>>);
+    assert(s.size() == 1);
+    }
+
+    {
+    NotAnAllocator a;
+    std::set s{a, a}; // set(initializer_list<NotAnAllocator>)
+    ASSERT_SAME_TYPE(decltype(s), std::set<NotAnAllocator>);
+    assert(s.size() == 1);
+    }
+
+    {
+    int source[3] = {3, 4, 5};
+    std::set s(source, source + 3); // set(InputIterator, InputIterator)
+    ASSERT_SAME_TYPE(decltype(s), std::set<int>);
+    assert(s.size() == 3);
+    }
+
+    {
+    int source[3] = {3, 4, 5};
+    std::set s{source, source + 3}; // set(initializer_list<int*>)
+    ASSERT_SAME_TYPE(decltype(s), std::set<int*>);
+    assert(s.size() == 2);
+    }
+
+  return 0;
+}