[C++23] [P1518R2] Better CTAD behavior for containers with allocators

[• Quuxplusone]

Summary

P1518 does the following in C++23 but we'll just do it in C++17 as well:

• Stop requiring Alloc to be an allocator on some container-adaptor deduction guides
• Stop deducing from Allocator on some sequence container constructors
• Stop deducing from Allocator on some other container constructors (libc++ already did this)

The affected constructors are the "allocator-extended" versions of constructors where the non-allocator arguments are already sufficient to deduce the allocator type. For example,

std::pmr::vector<int> v1;
std::vector v2(v1, std::pmr::new_delete_resource());
std::stack s2(v1, std::pmr::new_delete_resource());

P1518R2 (which will be in the next mailing) was adopted, or at least resolved-to-be-adopted, by LWG the other day.

I'm proposing that libc++ implement these CTAD improvements not only in C++2b mode, but also in all modes (i.e. C++17 and C++20). Anyone who doesn't notice won't mind, and anyone who does notice will thank us. Plus, libc++ already implements a little more than half of P1518R2 in all modes. This patch is just getting us all the way there.

[zoecarver]

This mostly LGTM but I haven't read it too carefully. Thanks for doing this, Arthur.

libcxx/include/deque

1318

I think all the compilers we that support support templated type aliases. WDYT about making this deque(const deque& __c, const __identity_t<allocator_type>& __a);?

[• Quuxplusone]

libcxx/include/deque

1318

Indeed, I'm 99.9% sure we can use alias templates, because of _EnableIf.
But right now libc++ has no __identity_t alias. If we were going to add one, I think I'd lobby for it to be like _Ident<T>, by analogy with _EnableIf<B>, just to keep the boilerplate as short as possible. (Although _EnableIf has advantages in minimizing helper template instantiations, whereas this thing would not.)

[zoecarver]

libcxx/include/deque

1318

_Ident<T> sounds good to me :)

I know this doesn't have compile-time benefit, but I think it will make the code a bit cleaner. Just a small thing.

[• Quuxplusone]

libcxx/include/deque

1318

Posted D97862. I went with __identity_t after all, because there are some irreducible uses of __identity and I didn't want to have, like, __identity<T> and _Ident<T> with subtly different meanings. (Even if _EnableIf is precedent! ;))

[curdeius]

Please consider upgrading the status page.

[zoecarver]

libcxx/include/deque

1318

And uses fewer characters ;)

[ldionne]

I spoke to Arthur about this offline. We usually don't implement stuff before it gets into the Standard, and I'd like to avoid creating a precedent. Waiting for it to get into the standard also means that we won't be caught off-guard if the paper changes at the last minute (which happens), and it will simplify our book-keeping by not having to remember to go back and update the Status list after the paper lands. So instead, Arthur and I agreed that we could pre-review this and when it's ready, he will just sit on it until the paper is actually voted in plenary, and then he can commit it immediately.

We also normally don't implement extensions (e.g. back-porting a paper to an earlier standard), and there are good reasons for that (it leads to tech debt, bugs down the road and we sometimes even break users in subtle ways). However, in this case, I think it's really reasonable to implement in previous standards:

1. This is basically fixing a defect that we hadn't noticed in previous standards, so it's akin to a LWG issue IMO.
2. The only way this can hurt someone is if they somehow rely on the use cases enabled by the paper not working in a SFINAE context (or at least I can't think of something else). I have little sympathy for these sorts of breakages - otherwise we'd be prevented from making basically any change.
3. Fixing the issue in previous standards increases consistency and reduces code complexity (in the test suite too), so we don't lose anything here.

The change itself looks good to me, but we'll have to edit the Status page upon landing it.

[• Quuxplusone]

Added a "NFCI" commit in front of my feature work here:

[libc++] Use _EnableIf and __iter_value_type consistently. NFCI.

Specifically, use these metafunctions consistently in areas that are
about to be affected by P1518R2's changes.

[• Quuxplusone]

Rebase on main. Add tests for LWG3025 and LWG3531. (We don't need any changes for LWG3531 AFAICT. LWG3531 says to do using value_type = __identity_t<pair<...>>, but that doesn't seem to affect anything in the relevant test cases. Being unable to demonstrate the point of that change, I haven't made it, and have emailed LWG for clarification instead.)

[• Quuxplusone]

Landed the NFCI part; rebased on main. Now this PR shows only the functional change again.

[• Quuxplusone]

Update Cxx2bStatusPaperStatus.csv, and poke buildkite. The paper has been merged
https://github.com/cplusplus/draft/pull/4672
so if buildkite is still happy with this, imma land it.

[Mordante]

Minor nit-pick found while reading e-mail, haven't looked at the rest of the patch.

libcxx/docs/Cxx2bStatusPaperStatus.csv

5

Minor nit-pick the placement seems odd. This should be a new section for the June 2021 accepted papers.
(I'm not sure who adds the papers and issues after a meeting, but it would be nice to have all papers and issues listed.)

[• Quuxplusone]

libcxx/docs/Cxx2bStatusPaperStatus.csv

5

it would be nice to have all papers and issues listed

It sure would. @ldionne? :)

This should be a new section for the June 2021 accepted papers.

Hm, I had blindly figured they were just listed asciibetically by paper number, but yeah, I see Cxx2aStatusPaperStatus.csv is organized in the way you describe. Will fix.

[• Quuxplusone]

Not sure what happened last time to make "patch application failed", but let's just try again.

[• Quuxplusone]

Ah, it was perhaps something to do with the existence of a parent revision (even though the parent revision was already merged and closed out).

libcxx/docs/Cxx2bStatusPaperStatus.csv

 "Paper #","Group","Paper Name","Meeting","Status","First released version"
 "`P0881R7 <https://wg21.link/P0881R7>`__","LWG","A Proposal to add stacktrace library","Autumn 2020","",""
 "`P0943R6 <https://wg21.link/P0943R6>`__","LWG","Support C atomics in C++","Autumn 2020","",""
 "`P1048R1 <https://wg21.link/P1048R1>`__","LWG","A proposal for a type trait to detect scoped enumerations","Autumn 2020","|Complete|","12.0"
 "`P1679R3 <https://wg21.link/P1679R3>`__","LWG","string contains function","Autumn 2020","|Complete|","12.0"
 "","","","","",""
 "`P1682R3 <https://wg21.link/P1682R3>`__","LWG","std::to_underlying for enumerations","February 2021","|Complete|","13.0"
 "`P2017R1 <https://wg21.link/P2017R1>`__","LWG","Conditionally borrowed ranges","February 2021","",""
 "`P2160R1 <https://wg21.link/P2160R1>`__","LWG","Locks lock lockables","February 2021","",""
 "`P2162R2 <https://wg21.link/P2162R2>`__","LWG","Inheriting from std::variant","February 2021","|Complete|","13.0"
 "`P2212R2 <https://wg21.link/P2212R2>`__","LWG","Relax Requirements for time_point::clock","February 2021","",""
 "`P2259R1 <https://wg21.link/P2259R1>`__","LWG","Repairing input range adaptors and counted_iterator","February 2021","",""
 "","","","","",""
+"`P1518R2 <https://wg21.link/P1518R2>`__","LWG","Stop overconstraining allocators in container deduction guides","June 2021","|Complete|","13.0"
+"","","","","",""

libcxx/include/deque

 #endif
     deque(size_type __n, const value_type& __v);
     deque(size_type __n, const value_type& __v, const allocator_type& __a);
     template <class _InputIter>
         deque(_InputIter __f, _InputIter __l,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
     template <class _InputIter>
         deque(_InputIter __f, _InputIter __l, const allocator_type& __a,
               typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0);
     deque(const deque& __c);
-    deque(const deque& __c, const allocator_type& __a);
+    deque(const deque& __c, const __identity_t<allocator_type>& __a);
 
     deque& operator=(const deque& __c);
 
 #ifndef _LIBCPP_CXX03_LANG
     deque(initializer_list<value_type> __il);
     deque(initializer_list<value_type> __il, const allocator_type& __a);
 
     _LIBCPP_INLINE_VISIBILITY
     deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;}
 
     _LIBCPP_INLINE_VISIBILITY
     deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value);
     _LIBCPP_INLINE_VISIBILITY
-    deque(deque&& __c, const allocator_type& __a);
+    deque(deque&& __c, const __identity_t<allocator_type>& __a);
     _LIBCPP_INLINE_VISIBILITY
     deque& operator=(deque&& __c)
         _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
                    is_nothrow_move_assignable<allocator_type>::value);
 
     _LIBCPP_INLINE_VISIBILITY
     void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());}
 #endif // _LIBCPP_CXX03_LANG

 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>::deque(const deque& __c)
     : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))
 {
     __append(__c.begin(), __c.end());
 }
 
 template <class _Tp, class _Allocator>
-deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a)
+deque<_Tp, _Allocator>::deque(const deque& __c, const __identity_t<allocator_type>& __a)
     : __base(__a)
 {
     __append(__c.begin(), __c.end());
 }
 
 template <class _Tp, class _Allocator>
 deque<_Tp, _Allocator>&
 deque<_Tp, _Allocator>::operator=(const deque& __c)

 deque<_Tp, _Allocator>::deque(deque&& __c)
     _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
     : __base(_VSTD::move(__c))
 {
 }
 
 template <class _Tp, class _Allocator>
 inline
-deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a)
+deque<_Tp, _Allocator>::deque(deque&& __c, const __identity_t<allocator_type>& __a)
     : __base(_VSTD::move(__c), __a)
 {
     if (__a != __c.__alloc())
     {
         typedef move_iterator<iterator> _Ip;
         assign(_Ip(__c.begin()), _Ip(__c.end()));
     }
 }

libcxx/include/forward_list

template <class _InputIterator>
                      >::type* = nullptr);
     template <class _InputIterator>
         forward_list(_InputIterator __f, _InputIterator __l,
                      const allocator_type& __a,
                      typename enable_if<
                        __is_cpp17_input_iterator<_InputIterator>::value
                      >::type* = nullptr);
     forward_list(const forward_list& __x);
-    forward_list(const forward_list& __x, const allocator_type& __a);
+    forward_list(const forward_list& __x, const __identity_t<allocator_type>& __a);
 
     forward_list& operator=(const forward_list& __x);
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     forward_list(forward_list&& __x)
         _NOEXCEPT_(is_nothrow_move_constructible<base>::value)
         : base(_VSTD::move(__x)) {}
-    forward_list(forward_list&& __x, const allocator_type& __a);
+    forward_list(forward_list&& __x, const __identity_t<allocator_type>& __a);
 
     forward_list(initializer_list<value_type> __il);
     forward_list(initializer_list<value_type> __il, const allocator_type& __a);
 
     _LIBCPP_INLINE_VISIBILITY
     forward_list& operator=(forward_list&& __x)
         _NOEXCEPT_(
              __node_traits::propagate_on_container_move_assignment::value &&

 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x)
     : base(
           __node_traits::select_on_container_copy_construction(__x.__alloc())) {
   insert_after(cbefore_begin(), __x.begin(), __x.end());
 }
 
 template <class _Tp, class _Alloc>
 forward_list<_Tp, _Alloc>::forward_list(const forward_list& __x,
-                                        const allocator_type& __a)
+                                        const __identity_t<allocator_type>& __a)
     : base(__a)
 {
     insert_after(cbefore_begin(), __x.begin(), __x.end());
 }
 
 template <class _Tp, class _Alloc>
 forward_list<_Tp, _Alloc>&
 forward_list<_Tp, _Alloc>::operator=(const forward_list& __x)
 {
     if (this != &__x)
     {
         base::__copy_assign_alloc(__x);
         assign(__x.begin(), __x.end());
     }
     return *this;
 }
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Tp, class _Alloc>
 forward_list<_Tp, _Alloc>::forward_list(forward_list&& __x,
-                                        const allocator_type& __a)
+                                        const __identity_t<allocator_type>& __a)
     : base(_VSTD::move(__x), __a)
 {
     if (base::__alloc() != __x.__alloc())
     {
         typedef move_iterator<iterator> _Ip;
         insert_after(cbefore_begin(), _Ip(__x.begin()), _Ip(__x.end()));
     }
 }

libcxx/include/list

#endif
     template <class _InpIter>
         list(_InpIter __f, _InpIter __l,
              typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);
     template <class _InpIter>
         list(_InpIter __f, _InpIter __l, const allocator_type& __a,
              typename enable_if<__is_cpp17_input_iterator<_InpIter>::value>::type* = 0);
 
     list(const list& __c);
-    list(const list& __c, const allocator_type& __a);
+    list(const list& __c, const __identity_t<allocator_type>& __a);
     _LIBCPP_INLINE_VISIBILITY
     list& operator=(const list& __c);
 #ifndef _LIBCPP_CXX03_LANG
     list(initializer_list<value_type> __il);
     list(initializer_list<value_type> __il, const allocator_type& __a);
 
     _LIBCPP_INLINE_VISIBILITY
     list(list&& __c)
         _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
     _LIBCPP_INLINE_VISIBILITY
-    list(list&& __c, const allocator_type& __a);
+    list(list&& __c, const __identity_t<allocator_type>& __a);
     _LIBCPP_INLINE_VISIBILITY
     list& operator=(list&& __c)
         _NOEXCEPT_(
             __node_alloc_traits::propagate_on_container_move_assignment::value &&
             is_nothrow_move_assignable<__node_allocator>::value);
 
     _LIBCPP_INLINE_VISIBILITY
     list& operator=(initializer_list<value_type> __il)

 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->__insert_c(this);
 #endif
     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
         push_back(*__i);
 }
 
 template <class _Tp, class _Alloc>
-list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
+list<_Tp, _Alloc>::list(const list& __c, const __identity_t<allocator_type>& __a)
     : base(__a)
 {
 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->__insert_c(this);
 #endif
     for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
         push_back(*__i);
 }

 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->__insert_c(this);
 #endif
     splice(end(), __c);
 }
 
 template <class _Tp, class _Alloc>
 inline
-list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
+list<_Tp, _Alloc>::list(list&& __c, const __identity_t<allocator_type>& __a)
     : base(__a)
 {
 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->__insert_c(this);
 #endif
     if (__a == __c.get_allocator())
         splice(end(), __c);
     else

libcxx/include/queue

template<class _Container,
          class = _EnableIf<!__is_allocator<_Container>::value>
 >
 queue(_Container)
     -> queue<typename _Container::value_type, _Container>;
 
 template<class _Container,
          class _Alloc,
          class = _EnableIf<!__is_allocator<_Container>::value>,
-         class = _EnableIf<__is_allocator<_Alloc>::value>
+         class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
 >
 queue(_Container, _Alloc)
     -> queue<typename _Container::value_type, _Container>;
 #endif
 
 template <class _Tp, class _Container>
 inline _LIBCPP_INLINE_VISIBILITY
 bool

 priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(), _Container = _Container())
     -> priority_queue<__iter_value_type<_InputIterator>, _Container, _Compare>;
 
 template<class _Compare,
          class _Container,
          class _Alloc,
          class = _EnableIf<!__is_allocator<_Compare>::value>,
          class = _EnableIf<!__is_allocator<_Container>::value>,
-         class = _EnableIf<__is_allocator<_Alloc>::value>
+         class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
 >
 priority_queue(_Compare, _Container, _Alloc)
     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 #endif
 
 template <class _Tp, class _Container, class _Compare>
 inline
 priority_queue<_Tp, _Container, _Compare>::priority_queue(const _Compare& __comp,

libcxx/include/stack

template<class _Container,
          class = _EnableIf<!__is_allocator<_Container>::value>
 >
 stack(_Container)
     -> stack<typename _Container::value_type, _Container>;
 
 template<class _Container,
          class _Alloc,
          class = _EnableIf<!__is_allocator<_Container>::value>,
-         class = _EnableIf<__is_allocator<_Alloc>::value>
+         class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
          >
 stack(_Container, _Alloc)
     -> stack<typename _Container::value_type, _Container>;
 #endif
 
 template <class _Tp, class _Container>
 inline _LIBCPP_INLINE_VISIBILITY
 bool

libcxx/include/vector

#endif
     {
         __annotate_delete();
 #if _LIBCPP_DEBUG_LEVEL == 2
         __get_db()->__erase_c(this);
 #endif
     }
 
     vector(const vector& __x);
-    vector(const vector& __x, const allocator_type& __a);
+    vector(const vector& __x, const __identity_t<allocator_type>& __a);
     _LIBCPP_INLINE_VISIBILITY
     vector& operator=(const vector& __x);
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     vector(initializer_list<value_type> __il);
 
     _LIBCPP_INLINE_VISIBILITY
     vector(initializer_list<value_type> __il, const allocator_type& __a);
 
     _LIBCPP_INLINE_VISIBILITY
     vector(vector&& __x)
 #if _LIBCPP_STD_VER > 14
         _NOEXCEPT;
 #else
         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
-    vector(vector&& __x, const allocator_type& __a);
+    vector(vector&& __x, const __identity_t<allocator_type>& __a);
     _LIBCPP_INLINE_VISIBILITY
     vector& operator=(vector&& __x)
         _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
 
     _LIBCPP_INLINE_VISIBILITY
     vector& operator=(initializer_list<value_type> __il)
         {assign(__il.begin(), __il.end()); return *this;}
 
#endif
     if (__n > 0)
     {
         __vallocate(__n);
         __construct_at_end(__x.__begin_, __x.__end_, __n);
     }
 }
 
 template <class _Tp, class _Allocator>
-vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
+vector<_Tp, _Allocator>::vector(const vector& __x, const __identity_t<allocator_type>& __a)
     : __base(__a)
 {
 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->__insert_c(this);
 #endif
     size_type __n = __x.size();
     if (__n > 0)
     {
#endif
     this->__begin_ = __x.__begin_;
     this->__end_ = __x.__end_;
     this->__end_cap() = __x.__end_cap();
     __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
 }
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
-vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
+vector<_Tp, _Allocator>::vector(vector&& __x, const __identity_t<allocator_type>& __a)
     : __base(__a)
 {
 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->__insert_c(this);
 #endif
     if (__a == __x.__alloc())
     {
         this->__begin_ = __x.__begin_;
#ifndef _LIBCPP_CXX03_LANG
 
     _LIBCPP_INLINE_VISIBILITY
     vector(vector&& __v)
 #if _LIBCPP_STD_VER > 14
         _NOEXCEPT;
 #else
         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
 #endif
-    vector(vector&& __v, const allocator_type& __a);
+    vector(vector&& __v, const __identity_t<allocator_type>& __a);
     _LIBCPP_INLINE_VISIBILITY
     vector& operator=(vector&& __v)
         _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
 
     _LIBCPP_INLINE_VISIBILITY
     vector& operator=(initializer_list<value_type> __il)
         {assign(__il.begin(), __il.end()); return *this;}
 
: __begin_(__v.__begin_),
       __size_(__v.__size_),
       __cap_alloc_(_VSTD::move(__v.__cap_alloc_)) {
     __v.__begin_ = nullptr;
     __v.__size_ = 0;
     __v.__cap() = 0;
 }
 
 template <class _Allocator>
-vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
+vector<bool, _Allocator>::vector(vector&& __v, const __identity_t<allocator_type>& __a)
     : __begin_(nullptr),
       __size_(0),
       __cap_alloc_(0, __a)
 {
     if (__a == allocator_type(__v.__alloc()))
     {
         this->__begin_ = __v.__begin_;
         this->__size_ = __v.__size_;

libcxx/test/std/containers/associative/map/map.cons/deduct.pass.cpp

int main(int, char**)
     std::map m({ P{1,1L}, P{2,2L}, P{1,1L}, P{INT_MAX,1L}, P{3,1L} }, test_allocator<PC>(0, 45));
 
     ASSERT_SAME_TYPE(decltype(m), std::map<int, long, std::less<int>, test_allocator<PC>>);
     const PC expected_m[] = { {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
     assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
     assert(m.get_allocator().get_id() == 45);
     }
 
+    {
+    // Examples from LWG3025
+    std::map m{std::pair{1, 1}, {2, 2}, {3, 3}};
+    ASSERT_SAME_TYPE(decltype(m), std::map<int, int>);
+
+    std::map m2{m.begin(), m.end()};
+    ASSERT_SAME_TYPE(decltype(m2), std::map<int, int>);
+    }
+
+    {
+    // Examples from LWG3531
+    std::map m1{{std::pair{1, 2}, {3, 4}}, std::less<int>()};
+    ASSERT_SAME_TYPE(decltype(m1), std::map<int, int>);
+
+    using value_type = std::pair<const int, int>;
+    std::map m2{{value_type{1, 2}, {3, 4}}, std::less<int>()};
+    ASSERT_SAME_TYPE(decltype(m2), std::map<int, int>);
+    }
+
     return 0;
 }

libcxx/test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp

int main(int, char**)
     std::multimap m({ P{1,1L}, P{2,2L}, P{1,1L}, P{INT_MAX,1L}, P{3,1L} }, test_allocator<PC>(0, 45));
 
     ASSERT_SAME_TYPE(decltype(m), std::multimap<int, long, std::less<int>, test_allocator<PC>>);
     const PC expected_m[] = { {1,1L}, {1,1L}, {2,2L}, {3,1L}, {INT_MAX,1L} };
     assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
     assert(m.get_allocator().get_id() == 45);
     }
 
+    {
+    // Examples from LWG3025
+    std::multimap m{std::pair{1, 1}, {2, 2}, {3, 3}};
+    ASSERT_SAME_TYPE(decltype(m), std::multimap<int, int>);
+
+    std::multimap m2{m.begin(), m.end()};
+    ASSERT_SAME_TYPE(decltype(m2), std::multimap<int, int>);
+    }
+
+    {
+    // Examples from LWG3531
+    std::multimap m1{{std::pair{1, 2}, {3, 4}}, std::less<int>()};
+    ASSERT_SAME_TYPE(decltype(m1), std::multimap<int, int>);
+
+    using value_type = std::pair<const int, int>;
+    std::multimap m2{{value_type{1, 2}, {3, 4}}, std::less<int>()};
+    ASSERT_SAME_TYPE(decltype(m2), std::multimap<int, int>);
+    }
+
     return 0;
 }

libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp

//  std::priority_queue pri(std::allocator<int>()); // queue (allocator &)
     std::priority_queue<float> source;
     std::priority_queue pri(source); // priority_queue(priority_queue &)
     static_assert(std::is_same_v<decltype(pri)::value_type, float>, "");
     static_assert(std::is_same_v<decltype(pri)::container_type, std::vector<float>>, "");
     assert(pri.size() == 0);
     }
 
     {
-//  This one is odd - you can pass an allocator in to use, but the allocator
-//  has to match the type of the one used by the underlying container
-    typedef long double T;
+        typedef short T;
         typedef std::greater<T> Comp;
         typedef test_allocator<T> Alloc;
         typedef std::deque<T, Alloc> Cont;
+        typedef test_allocator<int> ConvertibleToAlloc;
+        static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
+                      !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
 
-    Cont c{2,3,0,1};
-    std::priority_queue<T, Cont, Comp> source(Comp(), c);
-    std::priority_queue pri(source, Alloc(2)); // queue(queue &, allocator)
-    static_assert(std::is_same_v<decltype(pri)::value_type, T>, "");
-    static_assert(std::is_same_v<decltype(pri)::container_type, Cont>, "");
-    assert(pri.size() == 4);
-    assert(pri.top() == 0);
+        {
+        Comp comp;
+        Cont cont;
+        std::priority_queue pri(comp, cont, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Comp comp;
+        Cont cont;
+        std::priority_queue pri(comp, cont, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Comp comp;
+        Cont cont;
+        std::priority_queue pri(comp, std::move(cont), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Comp comp;
+        Cont cont;
+        std::priority_queue pri(comp, std::move(cont), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+    }
+
+    {
+        typedef short T;
+        typedef std::greater<T> Comp;
+        typedef test_allocator<T> Alloc;
+        typedef std::deque<T, Alloc> Cont;
+        typedef test_allocator<int> ConvertibleToAlloc;
+        static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
+                      !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
+
+        {
+        std::priority_queue<T, Cont, Comp> source;
+        std::priority_queue pri(source, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        std::priority_queue<T, Cont, Comp> source;
+        std::priority_queue pri(source, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        std::priority_queue<T, Cont, Comp> source;
+        std::priority_queue pri(std::move(source), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        std::priority_queue<T, Cont, Comp> source;
+        std::priority_queue pri(std::move(source), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
     }
 
     return 0;
 }

libcxx/test/std/containers/container.adaptors/queue/queue.cons/deduct.pass.cpp

//  std::queue que(std::allocator<int>()); // queue (allocator &)
     std::queue<A> source;
     std::queue que(source); // queue(queue &)
     static_assert(std::is_same_v<decltype(que)::value_type, A>, "");
     static_assert(std::is_same_v<decltype(que)::container_type, std::deque<A>>, "");
     assert(que.size() == 0);
     }
 
     {
-//  This one is odd - you can pass an allocator in to use, but the allocator
-//  has to match the type of the one used by the underlying container
         typedef short T;
         typedef test_allocator<T> Alloc;
-    typedef std::deque<T, Alloc> Container;
+        typedef std::list<T, Alloc> Cont;
+        typedef test_allocator<int> ConvertibleToAlloc;
+        static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
+                      !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
 
-    Container c{0,1,2,3};
-    std::queue<T, Container> source(c);
-    std::queue que(source, Alloc(2)); // queue(queue &, allocator)
-    static_assert(std::is_same_v<decltype(que)::value_type, T>, "");
-    static_assert(std::is_same_v<decltype(que)::container_type, Container>, "");
-    assert(que.size() == 4);
-    assert(que.back() == 3);
+        {
+        Cont cont;
+        std::queue que(cont, Alloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
+        }
+
+        {
+        Cont cont;
+        std::queue que(cont, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
+        }
+
+        {
+        Cont cont;
+        std::queue que(std::move(cont), Alloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
         }
 
+        {
+        Cont cont;
+        std::queue que(std::move(cont), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
+        }
+    }
+
+    {
+        typedef short T;
+        typedef test_allocator<T> Alloc;
+        typedef std::list<T, Alloc> Cont;
+        typedef test_allocator<int> ConvertibleToAlloc;
+        static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
+                      !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
+
+        {
+        std::queue<T, Cont> source;
+        std::queue que(source, Alloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
+        }
+
+        {
+        std::queue<T, Cont> source;
+        std::queue que(source, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
+        }
+
+        {
+        std::queue<T, Cont> source;
+        std::queue que(std::move(source), Alloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
+        }
+
+        {
+        std::queue<T, Cont> source;
+        std::queue que(std::move(source), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(que), std::queue<T, Cont>>);
+        }
+    }
 
     return 0;
 }

libcxx/test/std/containers/container.adaptors/stack/stack.cons/deduct.pass.cpp

 // template<class Container>
 //   stack(Container) -> stack<typename Container::value_type, Container>;
 //
 // template<class Container, class Allocator>
 //   stack(Container, Allocator) -> stack<typename Container::value_type, Container>;
 
 
 #include <stack>
+#include <deque>
 #include <vector>
 #include <list>
 #include <iterator>
 #include <cassert>
 #include <cstddef>
 #include <climits> // INT_MAX
 
 #include "test_macros.h"
//  std::stack stk(std::allocator<int>()); // stack (allocator &)
     std::stack<A> source;
     std::stack stk(source); // stack(stack &)
     static_assert(std::is_same_v<decltype(stk)::value_type, A>, "");
     static_assert(std::is_same_v<decltype(stk)::container_type, std::deque<A>>, "");
     assert(stk.size() == 0);
     }
 
     {
-//  This one is odd - you can pass an allocator in to use, but the allocator
-//  has to match the type of the one used by the underlying container
         typedef short T;
         typedef test_allocator<T> Alloc;
-    typedef std::deque<T, Alloc> Container;
+        typedef std::list<T, Alloc> Cont;
+        typedef test_allocator<int> ConvertibleToAlloc;
+        static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
+                      !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
 
-    Container c{0,1,2,3};
-    std::stack<T, Container> source(c);
-    std::stack stk(source, Alloc(2)); // stack(stack &, allocator)
-    static_assert(std::is_same_v<decltype(stk)::value_type, T>, "");
-    static_assert(std::is_same_v<decltype(stk)::container_type, Container>, "");
-    assert(stk.size() == 4);
-    assert(stk.top() == 3);
+        {
+        Cont cont;
+        std::stack stk(cont, Alloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
+        }
+
+        {
+        Cont cont;
+        std::stack stk(cont, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
+        }
+
+        {
+        Cont cont;
+        std::stack stk(std::move(cont), Alloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
         }
 
+        {
+        Cont cont;
+        std::stack stk(std::move(cont), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
+        }
+    }
+
+    {
+        typedef short T;
+        typedef test_allocator<T> Alloc;
+        typedef std::list<T, Alloc> Cont;
+        typedef test_allocator<int> ConvertibleToAlloc;
+        static_assert(std::uses_allocator_v<Cont, ConvertibleToAlloc> &&
+                      !std::is_same_v<typename Cont::allocator_type, ConvertibleToAlloc>);
+
+        {
+        std::stack<T, Cont> source;
+        std::stack stk(source, Alloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
+        }
+
+        {
+        std::stack<T, Cont> source;
+        std::stack stk(source, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
+        }
+
+        {
+        std::stack<T, Cont> source;
+        std::stack stk(std::move(source), Alloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
+        }
+
+        {
+        std::stack<T, Cont> source;
+        std::stack stk(std::move(source), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(stk), std::stack<T, Cont>>);
+        }
+    }
 
     return 0;
 }

libcxx/test/std/containers/sequences/deque/deque.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
 //
 //===----------------------------------------------------------------------===//
 
-// <array>
+// <deque>
 // UNSUPPORTED: c++03, c++11, c++14
 // UNSUPPORTED: libcpp-no-deduction-guides
 
 
 // template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
 //    deque(InputIterator, InputIterator, Allocator = Allocator())
 //    -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
 //
//  std::deque deq(std::allocator<int>()); // deque (allocator &)
     {
     std::deque<long double> source;
     std::deque deq(source); // deque(deque &)
     static_assert(std::is_same_v<decltype(deq)::value_type, long double>, "");
     static_assert(std::is_same_v<decltype(deq)::allocator_type, std::allocator<long double>>, "");
     assert(deq.size() == 0);
     }
 
+    {
+        typedef test_allocator<short> Alloc;
+        typedef test_allocator<int> ConvertibleToAlloc;
+
+        {
+        std::deque<short, Alloc> source;
+        std::deque deq(source, Alloc(2));
+        static_assert(std::is_same_v<decltype(deq), decltype(source)>);
+        }
+
+        {
+        std::deque<short, Alloc> source;
+        std::deque deq(source, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(deq), decltype(source)>);
+        }
+
+        {
+        std::deque<short, Alloc> source;
+        std::deque deq(std::move(source), Alloc(2));
+        static_assert(std::is_same_v<decltype(deq), decltype(source)>);
+        }
+
+        {
+        std::deque<short, Alloc> source;
+        std::deque deq(std::move(source), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(deq), decltype(source)>);
+        }
+    }
+
     return 0;
 }

libcxx/test/std/containers/sequences/forwardlist/forwardlist.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
 //
 //===----------------------------------------------------------------------===//
 
 // <forward_list>
 // UNSUPPORTED: c++03, c++11, c++14
 // UNSUPPORTED: libcpp-no-deduction-guides
 
 
 // template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
-//    deque(InputIterator, InputIterator, Allocator = Allocator())
-//    -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
+//    forward_list(InputIterator, InputIterator, Allocator = Allocator())
+//    -> forward_list<typename iterator_traits<InputIterator>::value_type, Allocator>;
 //
 
 
 #include <forward_list>
 #include <iterator>
 #include <cassert>
 #include <cstddef>
 #include <climits> // INT_MAX
//  std::forward_list fwl(std::allocator<int>()); // deque (allocator &)
     {
     std::forward_list<long double> source;
     std::forward_list fwl(source); // deque(deque &)
     static_assert(std::is_same_v<decltype(fwl)::value_type, long double>, "");
     static_assert(std::is_same_v<decltype(fwl)::allocator_type, std::allocator<long double>>, "");
     assert(std::distance(fwl.begin(), fwl.end()) == 0); // no size for forward_list
     }
 
+    {
+        typedef test_allocator<short> Alloc;
+        typedef test_allocator<int> ConvertibleToAlloc;
+
+        {
+        std::forward_list<short, Alloc> source;
+        std::forward_list fwl(source, Alloc(2));
+        static_assert(std::is_same_v<decltype(fwl), decltype(source)>);
+        }
+
+        {
+        std::forward_list<short, Alloc> source;
+        std::forward_list fwl(source, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(fwl), decltype(source)>);
+        }
+
+        {
+        std::forward_list<short, Alloc> source;
+        std::forward_list fwl(std::move(source), Alloc(2));
+        static_assert(std::is_same_v<decltype(fwl), decltype(source)>);
+        }
+
+        {
+        std::forward_list<short, Alloc> source;
+        std::forward_list fwl(std::move(source), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(fwl), decltype(source)>);
+        }
+    }
+
     return 0;
 }

libcxx/test/std/containers/sequences/list/list.cons/deduct.pass.cpp

//  std::list lst(std::allocator<int>()); // list (allocator &)
     {
     std::list<long double> source;
     std::list lst(source); // list(list &)
     static_assert(std::is_same_v<decltype(lst)::value_type, long double>, "");
     static_assert(std::is_same_v<decltype(lst)::allocator_type, std::allocator<long double>>, "");
     assert(lst.size() == 0);
     }
 
+    {
+        typedef test_allocator<short> Alloc;
+        typedef test_allocator<int> ConvertibleToAlloc;
+
+        {
+        std::list<short, Alloc> source;
+        std::list lst(source, Alloc(2));
+        static_assert(std::is_same_v<decltype(lst), decltype(source)>);
+        }
+
+        {
+        std::list<short, Alloc> source;
+        std::list lst(source, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(lst), decltype(source)>);
+        }
+
+        {
+        std::list<short, Alloc> source;
+        std::list lst(std::move(source), Alloc(2));
+        static_assert(std::is_same_v<decltype(lst), decltype(source)>);
+        }
+
+        {
+        std::list<short, Alloc> source;
+        std::list lst(std::move(source), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(lst), decltype(source)>);
+        }
+    }
+
     return 0;
 }

libcxx/test/std/containers/sequences/vector/vector.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
 //
 //===----------------------------------------------------------------------===//
 
 // <vector>
 // UNSUPPORTED: c++03, c++11, c++14
 // UNSUPPORTED: libcpp-no-deduction-guides
 
 
 // template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
-//    deque(InputIterator, InputIterator, Allocator = Allocator())
-//    -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;
+//    vector(InputIterator, InputIterator, Allocator = Allocator())
+//    -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>;
 //
 
 
 #include <vector>
 #include <iterator>
 #include <cassert>
 #include <cstddef>
 #include <climits> // INT_MAX
//  A couple of vector<bool> tests, too!
     {
     std::vector<bool> source;
     std::vector vec(source); // vector(vector &)
     static_assert(std::is_same_v<decltype(vec)::value_type, bool>, "");
     static_assert(std::is_same_v<decltype(vec)::allocator_type, std::allocator<bool>>, "");
     assert(vec.size() == 0);
     }
 
+    {
+        typedef test_allocator<short> Alloc;
+        typedef test_allocator<int> ConvertibleToAlloc;
+
+        {
+        std::vector<short, Alloc> source;
+        std::vector vec(source, Alloc(2));
+        static_assert(std::is_same_v<decltype(vec), decltype(source)>);
+        }
+
+        {
+        std::vector<short, Alloc> source;
+        std::vector vec(source, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(vec), decltype(source)>);
+        }
+
+        {
+        std::vector<short, Alloc> source;
+        std::vector vec(std::move(source), Alloc(2));
+        static_assert(std::is_same_v<decltype(vec), decltype(source)>);
+        }
+
+        {
+        std::vector<short, Alloc> source;
+        std::vector vec(std::move(source), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(vec), decltype(source)>);
+        }
+    }
+
     return 0;
 }

libcxx/test/std/containers/unord/unord.map/unord.map.cnstr/deduct.pass.cpp

int main(int, char**)
 
     {
     std::unordered_map m({ P{1,1L}, P{2,2L}, P{1,1L}, P{INT_MAX,1L}, P{3,1L} }, 42, std::hash<long long>(), test_allocator<PC>(0, 48));
     ASSERT_SAME_TYPE(decltype(m), std::unordered_map<int, long, std::hash<long long>, std::equal_to<int>, test_allocator<PC>>);
     assert(std::is_permutation(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
     assert(m.get_allocator().get_id() == 48);
     }
 
+    {
+    // Examples from LWG3025
+    std::unordered_map m{std::pair{1, 1}, {2, 2}, {3, 3}};
+    ASSERT_SAME_TYPE(decltype(m), std::unordered_map<int, int>);
+
+    std::unordered_map m2{m.begin(), m.end()};
+    ASSERT_SAME_TYPE(decltype(m2), std::unordered_map<int, int>);
+    }
+
+    {
+    // Examples from LWG3531
+    std::unordered_map m1{{std::pair{1, 2}, {3, 4}}, 0};
+    ASSERT_SAME_TYPE(decltype(m1), std::unordered_map<int, int>);
+
+    using value_type = std::pair<const int, int>;
+    std::unordered_map m2{{value_type{1, 2}, {3, 4}}, 0};
+    ASSERT_SAME_TYPE(decltype(m2), std::unordered_map<int, int>);
+    }
+
     return 0;
 }

libcxx/test/std/containers/unord/unord.multimap/unord.multimap.cnstr/deduct.pass.cpp

int main(int, char**)
 
     {
     std::unordered_multimap m({ P{1,1L}, P{2,2L}, P{1,1L}, P{INT_MAX,1L}, P{3,1L} }, 42, std::hash<short>(), test_allocator<PC>(0, 48));
     ASSERT_SAME_TYPE(decltype(m), std::unordered_multimap<int, long, std::hash<short>, std::equal_to<int>, test_allocator<PC>>);
     assert(std::is_permutation(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m)));
     assert(m.get_allocator().get_id() == 48);
     }
 
+    {
+    // Examples from LWG3025
+    std::unordered_multimap m{std::pair{1, 1}, {2, 2}, {3, 3}};
+    ASSERT_SAME_TYPE(decltype(m), std::unordered_multimap<int, int>);
+
+    std::unordered_multimap m2{m.begin(), m.end()};
+    ASSERT_SAME_TYPE(decltype(m2), std::unordered_multimap<int, int>);
+    }
+
+    {
+    // Examples from LWG3531
+    std::unordered_multimap m1{{std::pair{1, 2}, {3, 4}}, 0};
+    ASSERT_SAME_TYPE(decltype(m1), std::unordered_multimap<int, int>);
+
+    using value_type = std::pair<const int, int>;
+    std::unordered_multimap m2{{value_type{1, 2}, {3, 4}}, 0};
+    ASSERT_SAME_TYPE(decltype(m2), std::unordered_multimap<int, int>);
+    }
+
     return 0;
 }