[libc++] Implement P1425R4 (Iterator pair constructors for std::stack and std::queue)

[philnik]

Summary

Implement P1425R4

[philnik]

Updated synopsis

[philnik]

• renamed shadowing variable

[jloser]

Please consider adding tests for the deduction guides.

[philnik]

• Added deduction guide tests (I think)

[Mordante]

Thanks for your contribution! It still needs some more work.

libcxx/include/queue

77

This deduction guide has also been added. A quick scan it seems there are more deduction guides not added to the synopsis.

261

Can you move the new constructors to this location, that seems more consistent.

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

42

I miss a test to validate the queue has the expected values.

44

The deduction guides should be their own test, queue.cons/deduct.pass.cpp already contains test for the deduction guides, please add them there.

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

29

I think it would be good to test all elements in the queue to have the expected value.

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

42

I miss a test to validate the queue has the expected values.

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

28

I think it would be good to test all elements in the queue to have the expected value.

[philnik]

• Added deduction guides to synopsis
• Moved queue constructors
• Moved deduction guide tests
• Checking elements

[• Quuxplusone]

Thanks, this looks good, except for the style not matching the style of the surrounding code.

libcxx/include/queue

55

Nits: please indent to match the surrounding style, and please last); // since C++23 (although I see you're aligning the comments, I don't think it's beneficial here).

Also, please shuffle the order of these new constructors to match what's in the paper and/or Standard synopsis. The (first, last) one should be circa line 44, and the (first, last, const Alloc&) one down here.

81–83

Here and line 79 also, please indent the second line by 2 spaces to match the surrounding style.
Consider line-breaking before deque just to improve readability.

libcxx/include/stack

188

Ditto below.

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

31–32

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

25

Testing that std::queue{it, it} produces a queue of ints rather than a queue of iterators is a good test, but it belongs in deduct.pass.cpp, not here. In this file, you should focus on the non-CTAD happy path, std::queue<int>(a.begin(), a.end()). Keep it simple:

const int a[] = {4, 3, 2, 1};
std::queue<int> queue(a, a+4);
assert(queue.front() == 4); // etc.

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

159–164 ↗

(On Diff #395297)

Let's use std::list<int> as our type here, since we do that above. Also, let's match the style of surrounding code.

{
    typedef short T;
    typedef test_allocator<T> Alloc;
    std::list<T> source;
    {
    std::queue que(source.begin(), source.end());
    static_assert(std::is_same_v<decltype(que), std::queue<T>>);
    }
    {
    std::queue que(source.begin(), source.end(), Alloc(2));
    static_assert(std::is_same_v<decltype(que), std::queue<T, std::deque<T, Alloc>>>);
    }
}

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

42

I miss variable names that make it clear that the thing under test here is not a queue. ;)
(This test should be refactored simpler along the same lines I suggest for the queue test, above.)

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

163–168 ↗

(On Diff #395297)

Same comments here as on the queue deduct.pass.cpp.

[• Quuxplusone]

libcxx/include/queue

390–397

Yipes, almost missed this, except that the failing CI alerted me. All these deduction guides need to use __enable_if_t to disable themselves when _InputIterator is not an iterator or _Alloc is not an allocator. Look at the guides for deque or priority_queue and do as they do.

Please also add some SFINAES_away tests to deduct.pass.cpp proving that the deduction guides indeed SFINAE away in those cases.

[philnik]

• Updated synopsis
• Added SFINAE stuff
• Style changes

[• Quuxplusone]

libcxx/include/queue

267

Does this overload need , __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0 similar to the below overloads? I suspect it does. (And then please add a regression test. The regression test will use SFINAE but not CTAD.)

390–397

Please follow the pattern on lines 385–397 above (and in e.g. <vector>, which I assume is more or less where you copied these particular constraints from):

template<class _InputIterator,
         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>
>
queue(_InputIterator, _InputIterator)
    -> queue<__iter_value_type<_InputIterator>>;

template<class _InputIterator,
         class _Alloc,
         class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
         class = enable_if_t<__is_allocator<_Alloc>::value>
>
queue(_InputIterator, _InputIterator, _Alloc)
    -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;

Both for consistency, and because _LIBCPP_HAS_NO_CONCEPTS is still a thing.

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

24

iter should now be just const int*, which means you don't need the typedef.

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

28–31

This is okay, but personally I'd rather see lines 25,27,28,29,30 replaced with

assert(stack.top() == 1); stack.pop();
assert(stack.top() == 2); stack.pop();
assert(stack.top() == 3); stack.pop();
assert(stack.top() == 4); stack.pop();
assert(stack.empty());

and then you can remove the include of <ranges>. And similarly in the queue test:

assert(queue.front() == 4); queue.pop();
assert(queue.front() == 3); queue.pop();
assert(queue.front() == 2); queue.pop();
assert(queue.front() == 1); queue.pop();
assert(queue.empty());

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

19 ↗

(On Diff #395315)

This can be removed again now. Ditto in queue.cons/ctor_iterators.pass.cpp.

159 ↗

(On Diff #395315)

Throw in <std::stack, NotIter, Iter> while you're here.
I like the renaming of BadAlloc to NotAlloc. I wouldn't complain if you replaced the uses of AllocAsCont with just Alloc, either (I don't think the AsCont improves my understanding of that case).

[philnik]

• Addressed comments

[• Quuxplusone]

libcxx/include/queue

267

Actually even (hand-rolled) SFINAE is unnecessary. A regression test for this could be as simple as

static_assert(!std::is_constructible_v<std::queue<int>, int, int, std::allocator<int>>);
static_assert(!std::is_constructible_v<std::queue<int>, int*, int*, int>);
static_assert( std::is_constructible_v<std::queue<int, std::deque<int, test_allocator<int>>>, int, int, test_allocator<int>>);
static_assert(!std::is_constructible_v<std::queue<int, std::deque<int, test_allocator<int>>>, int, int, std::allocator<int>>);

and likewise for stack. (Preemptive whitespace advice: These lines are long, but I wouldn't break them.)

[philnik]

• Added regression tests and __enable_ifs to constructors

[philnik]

ping

[• Quuxplusone]

Getting there! Definitely wait for buildkite to be back online and green before landing this, though, because I can totally imagine buildkite not liking it.

libcxx/include/queue

219

Why all of <memory>? (Same question below in stack.)

219

Here and <stack>, <version> should be included now.
(That is, please just make sure the merge-conflict with D116172 doesn't somehow get lost in the shuffle.)

265

Please linebreak before queue, for consistency. (Here and line 283, and presumably also in stack)

393

399–400

libcxx/include/stack

259–268

Please follow the enable_if_t pattern here as well.

[philnik]

• Addessed comments

libcxx/include/queue

219

I'll just wait for D116172 do be landed. It looks like it's just waiting for CI to pass.

[philnik]

Rebased. Any more comments @Quuxplusone?

[jloser]

I haven't finished reviewing this in full yet, but do we need to use enable_if_t instead of concepts/requires since this is C++23 code? I.e. is our requirement of using older AppleClang version in C++23 mode an issue with this (and therefore we must use enable_if_t still)? The consistency argument is fine - I'm asking purely from a technical standpoint.

[philnik]

I think it could also be guarded with _LIBCPP_HAS_NO_CONCEPTS. libc++ still supports compilers where concepts are not working.

[• Quuxplusone]

In D115977#3223823, @jloser wrote:

I haven't finished reviewing this in full yet, but do we need to use enable_if_t instead of concepts/requires since this is C++23 code? I.e. is our requirement of using older AppleClang version in C++23 mode an issue with this (and therefore we must use enable_if_t still)? The consistency argument is fine - I'm asking purely from a technical standpoint.

If you want it to be present in -std=c++2b mode, on old compilers without full concepts support, then it can't depend on full concepts support (although technically maybe those old compilers support enough of concepts that a simple requires-clause would be OK... but let's not go down that rabbit hole, let's just wait a couple more years). If you guard it under _LIBCPP_HAS_NO_CONCEPTS, then it won't be present on old compilers without full concepts support, so I don't think that would be a good idea either. Finally, you could provide two different implementations — one under _LIBCPP_HAS_NO_CONCEPTS and one not — but that would be twice the work, and require going down a rabbit hole involving "twice the tests," so let's not do that either.

libcxx/include/queue

82

219

stack still includes <memory>; it probably shouldn't, right?

271

This line shouldn't be here; and please add a regression test if possible.
An example of a regression test would be

int a[10] = {};
std::pmr::queue<int> q(a, a+10, std::pmr::new_delete_resource());  // should be OK

except that that'll be hard to put in a test since we don't support std::pmr. :P

The deduction guides are appropriately constrained so that (if they don't take a Container parameter) Alloc must be an allocator; but the constructors are not so constrained. https://wg21.link/p1518r1 is related.

libcxx/include/stack

195

and regression-test

[philnik]

• Addressed comments

libcxx/include/queue

219

Yep, forgot that.

[Mordante]

In D115977#3223872, @Quuxplusone wrote:

In D115977#3223823, @jloser wrote:

I haven't finished reviewing this in full yet, but do we need to use enable_if_t instead of concepts/requires since this is C++23 code? I.e. is our requirement of using older AppleClang version in C++23 mode an issue with this (and therefore we must use enable_if_t still)? The consistency argument is fine - I'm asking purely from a technical standpoint.

If you want it to be present in -std=c++2b mode, on old compilers without full concepts support, then it can't depend on full concepts support (although technically maybe those old compilers support enough of concepts that a simple requires-clause would be OK... but let's not go down that rabbit hole, let's just wait a couple more years). If you guard it under _LIBCPP_HAS_NO_CONCEPTS, then it won't be present on old compilers without full concepts support, so I don't think that would be a good idea either. Finally, you could provide two different implementations — one under _LIBCPP_HAS_NO_CONCEPTS and one not — but that would be twice the work, and require going down a rabbit hole involving "twice the tests," so let's not do that either.

IIRC the only compiler using _LIBCPP_HAS_NO_CONCEPTS is AppleClang. Unfortunately our CI isn't running the latest AppleClang yet so we need to support not concept builds.

LGTM, just make sure the Apple build failure isn't due to your changes.

[philnik]

CI failed with the same problems in D116691, so I don't think they are related to this patch.

[• Quuxplusone]

The span.cons/initializer_list.pass.cpp failure is my fault, and I believe I just fixed it in 570ed38b6e387644c38561e0cb019c94d7b5c0bb. Feel free to poke CI again if you want, but I don't think it's necessary — I mean, if CI is "green except for span.cons/initializer_list.pass.cpp" on your most recent diff, then you can feel free to treat that as green.

libcxx/docs/FeatureTestMacroTable.rst

.. table:: Current Status
     ``__cpp_lib_to_address``                          ``201711L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_to_array``                            ``201907L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_unwrap_ref``                          ``201811L``
     ------------------------------------------------- -----------------
     **C++ 2b**
     -------------------------------------------------------------------
+    ``__cpp_lib_adaptor_iterator_pair_constructor``   ``202106L``
+    ------------------------------------------------- -----------------
     ``__cpp_lib_byteswap``                            ``202110L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_is_scoped_enum``                      ``202011L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_stacktrace``                          *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_stdatomic_h``                         *unimplemented*
     ------------------------------------------------- -----------------
     ``__cpp_lib_string_contains``                     ``202011L``
     ------------------------------------------------- -----------------
     ``__cpp_lib_to_underlying``                       ``202102L``
     ================================================= =================
 

libcxx/docs/Status/Cxx2bPapers.csv

 "`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","",""
 "","","","","",""
 "`P0401R6 <https://wg21.link/P0401R6>`__","LWG","Providing size feedback in the Allocator interface","June 2021","",
 "`P0448R4 <https://wg21.link/P0448R4>`__","LWG","A strstream replacement using span<charT> as buffer","June 2021","",""
 "`P1132R8 <https://wg21.link/P1132R8>`__","LWG","out_ptr - a scalable output pointer abstraction","June 2021","",""
 "`P1328R1 <https://wg21.link/P1328R1>`__","LWG","Making std::type_info::operator== constexpr","June 2021","",""
-"`P1425R4 <https://wg21.link/P1425R4>`__","LWG","Iterators pair constructors for stack and queue","June 2021","",""
+"`P1425R4 <https://wg21.link/P1425R4>`__","LWG","Iterators pair constructors for stack and queue","June 2021","|Complete|","14.0"
 "`P1518R2 <https://wg21.link/P1518R2>`__","LWG","Stop overconstraining allocators in container deduction guides","June 2021","|Complete|","13.0"
 "`P1659R3 <https://wg21.link/P1659R3>`__","LWG","starts_with and ends_with","June 2021","",""
 "`P1951R1 <https://wg21.link/P1951R1>`__","LWG","Default Arguments for pair Forwarding Constructor","June 2021","|Complete|","14.0"
 "`P1989R2 <https://wg21.link/P1989R2>`__","LWG","Range constructor for std::string_view","June 2021","|Complete|","14.0"
 "`P2136R3 <https://wg21.link/P2136R3>`__","LWG","invoke_r","June 2021","",""
 "`P2166R1 <https://wg21.link/P2166R1>`__","LWG","A Proposal to Prohibit std::basic_string and std::basic_string_view construction from nullptr","June 2021","|Complete|","13.0"
 "","","","","",""
 "`P0288R9 <https://wg21.link/P0288R9>`__","LWG","``any_invocable``","October 2021","",""

libcxx/include/queue

public:
     template <class Alloc>
         queue(const container_type& c, const Alloc& a);
     template <class Alloc>
         queue(container_type&& c, const Alloc& a);
     template <class Alloc>
         queue(const queue& q, const Alloc& a);
     template <class Alloc>
         queue(queue&& q, const Alloc& a);
+    template <class InputIterator, class Alloc>
+    queue(InputIterator first, InputIterator last, const Alloc&); // since C++23
+    template<class InputIterator>
+    queue(InputIterator first, InputIterator last);               // since C++23
 
     bool      empty() const;
     size_type size() const;
 
     reference       front();
     const_reference front() const;
     reference       back();
     const_reference back() const;
 
     void push(const value_type& v);
     void push(value_type&& v);
     template <class... Args> reference emplace(Args&&... args); // reference in C++17
     void pop();
 
     void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
 };
 
 template<class Container>
   queue(Container) -> queue<typename Container::value_type, Container>; // C++17
 
 template<class Container, class Allocator>
   queue(Container, Allocator) -> queue<typename Container::value_type, Container>; // C++17
 
 template <class T, class Container>
   bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
 
 template <class T, class Container>
   bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
 
 template <class T, class Container>
   bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
 
 template <class T, class Container>
   bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);

 
 #include <__config>
 #include <__memory/uses_allocator.h>
 #include <__utility/forward.h>
 #include <algorithm>
 #include <compare>
 #include <deque>
 #include <functional>
 #include <vector>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Tp, class _Container = deque<_Tp> > class _LIBCPP_TEMPLATE_VIS queue;

 public:
     _LIBCPP_INLINE_VISIBILITY
     queue()
         _NOEXCEPT_(is_nothrow_default_constructible<container_type>::value)
         : c() {}
 
     _LIBCPP_INLINE_VISIBILITY
     queue(const queue& __q) : c(__q.c) {}
 
     _LIBCPP_INLINE_VISIBILITY
     queue& operator=(const queue& __q) {c = __q.c; return *this;}
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     queue(queue&& __q)
         _NOEXCEPT_(is_nothrow_move_constructible<container_type>::value)
         : c(_VSTD::move(__q.c)) {}
 
     _LIBCPP_INLINE_VISIBILITY
     queue& operator=(queue&& __q)
         _NOEXCEPT_(is_nothrow_move_assignable<container_type>::value)
         {c = _VSTD::move(__q.c); return *this;}
 #endif // _LIBCPP_CXX03_LANG
 
+#if _LIBCPP_STD_VER > 20
+    template <class _InputIterator>
+    _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) {}
+
+    template <class _InputIterator, class _Alloc>
+    _LIBCPP_HIDE_FROM_ABI queue(_InputIterator __first, _InputIterator __second, const _Alloc& __alloc)
+        : c(__first, __second, __alloc) {}
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     explicit queue(const container_type& __c)  : c(__c) {}
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     explicit queue(container_type&& __c) : c(_VSTD::move(__c)) {}
 #endif // _LIBCPP_CXX03_LANG
     template <class _Alloc>
         _LIBCPP_INLINE_VISIBILITY
#endif // _LIBCPP_CXX03_LANG
 
     template <class _T1, class _C1>
     friend
     _LIBCPP_INLINE_VISIBILITY
     bool
     operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
 };
 
-#if _LIBCPP_STD_VER >= 17
+#if _LIBCPP_STD_VER > 14
 template<class _Container,
          class = enable_if_t<!__is_allocator<_Container>::value>
 >
 queue(_Container)
     -> queue<typename _Container::value_type, _Container>;
 
 template<class _Container,
          class _Alloc,
          class = enable_if_t<!__is_allocator<_Container>::value>,
          class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
 >
 queue(_Container, _Alloc)
     -> queue<typename _Container::value_type, _Container>;
 #endif
 
+#if _LIBCPP_STD_VER > 20
+template <class _InputIterator>
+queue(_InputIterator, _InputIterator) -> queue<__iter_value_type<_InputIterator>>;
+
+template <class _InputIterator, class _Alloc>
+queue(_InputIterator, _InputIterator, _Alloc)
+  -> queue<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
+#endif
+
 template <class _Tp, class _Container>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 {
     return __x.c == __y.c;
 }
 
 template <class _Tp, class _Container>
 inline _LIBCPP_INLINE_VISIBILITY

libcxx/include/stack

template <class _Alloc>
             : c(_VSTD::move(__c), __a) {}
     template <class _Alloc>
         _LIBCPP_INLINE_VISIBILITY
         stack(stack&& __s, const _Alloc& __a,
               __enable_if_t<uses_allocator<container_type, _Alloc>::value>* = 0)
             : c(_VSTD::move(__s.c), __a) {}
 #endif // _LIBCPP_CXX03_LANG
 
+#if _LIBCPP_STD_VER > 20
+    template <class _InputIterator>
+    _LIBCPP_HIDE_FROM_ABI stack(_InputIterator __first, _InputIterator __last) : c{__first, __last} {}
+
+    template <class _InputIterator, class _Alloc>
+    _LIBCPP_HIDE_FROM_ABI stack(_InputIterator __first, _InputIterator __last, const _Alloc& __alloc)
+        : c{__first, __last, __alloc} {}
+#endif
+
     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
     bool empty()     const      {return c.empty();}
     _LIBCPP_INLINE_VISIBILITY
     size_type size() const      {return c.size();}
     _LIBCPP_INLINE_VISIBILITY
     reference top()             {return c.back();}
     _LIBCPP_INLINE_VISIBILITY
     const_reference top() const {return c.back();}
 
#endif // _LIBCPP_CXX03_LANG
     operator==(const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
 
     template <class T1, class _C1>
     friend
     bool
     operator< (const stack<T1, _C1>& __x, const stack<T1, _C1>& __y);
 };
 
-#if _LIBCPP_STD_VER >= 17
+#if _LIBCPP_STD_VER > 14
 template<class _Container,
          class = enable_if_t<!__is_allocator<_Container>::value>
 >
 stack(_Container)
     -> stack<typename _Container::value_type, _Container>;
 
 template<class _Container,
          class _Alloc,
          class = enable_if_t<!__is_allocator<_Container>::value>,
          class = enable_if_t<uses_allocator<_Container, _Alloc>::value>
          >
 stack(_Container, _Alloc)
     -> stack<typename _Container::value_type, _Container>;
 #endif
 
+#if _LIBCPP_STD_VER > 20
+template<class _InputIterator>
+stack(_InputIterator, _InputIterator) -> stack<__iter_value_type<_InputIterator>>;
+
+template<class _InputIterator, class _Alloc>
+stack(_InputIterator, _InputIterator, _Alloc)
+-> stack<__iter_value_type<_InputIterator>, deque<__iter_value_type<_InputIterator>, _Alloc>>;
+#endif
+
 template <class _Tp, class _Container>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const stack<_Tp, _Container>& __x, const stack<_Tp, _Container>& __y)
 {
     return __x.c == __y.c;
 }
 
 template <class _Tp, class _Container>

libcxx/include/version

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP_VERSIONH
 #define _LIBCPP_VERSIONH
 
 /*
   version synopsis
 
 Macro name                                              Value   Headers
+__cpp_lib_adaptor_iterator_pair_constructor             202106L <queue> <stack>
 __cpp_lib_addressof_constexpr                           201603L <memory>
 __cpp_lib_allocator_traits_is_always_equal              201411L <deque> <forward_list> <list>
                                                                 <map> <memory> <scoped_allocator>
                                                                 <set> <string> <unordered_map>
                                                                 <unordered_set> <vector>
 __cpp_lib_any                                           201606L <any>
 __cpp_lib_apply                                         201603L <tuple>
 __cpp_lib_array_constexpr                               201811L <array> <iterator>

 // # define __cpp_lib_syncbuf                              201803L
 // # define __cpp_lib_three_way_comparison                 201907L
 # define __cpp_lib_to_address                           201711L
 # define __cpp_lib_to_array                             201907L
 # define __cpp_lib_unwrap_ref                           201811L
 #endif
 
 #if _LIBCPP_STD_VER > 20
+# define __cpp_lib_adaptor_iterator_pair_constructor    202106L
 # define __cpp_lib_byteswap                             202110L
 # define __cpp_lib_is_scoped_enum                       202011L
 // # define __cpp_lib_stacktrace                           202011L
 // # define __cpp_lib_stdatomic_h                          202011L
 # define __cpp_lib_string_contains                      202011L
 # define __cpp_lib_to_underlying                        202102L
 #endif
 
 // clang-format on
 
 #endif // _LIBCPP_VERSIONH

libcxx/test/std/containers/container.adaptors/queue/queue.cons.alloc/ctor_iterators.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// <queue>
+
+// template <class InputIterator, class Allocator>
+// queue(InputIterator, InputIterator, const Allocator&);
+
+#include <array>
+#include <cassert>
+#include <queue>
+
+#include "test_allocator.h"
+
+using base_type = std::queue<int, std::deque<int, test_allocator<int>>>;
+using iter = std::array<int, 4>::const_iterator;
+
+class GetAlloc : base_type {
+  test_allocator_statistics* stats;
+
+public:
+  GetAlloc(test_allocator_statistics& stats, iter begin, iter end)
+      : base_type{begin, end, test_allocator<int>{&stats}}, stats{&stats} {}
+  void check() {
+    assert(size() == 4);
+    assert(stats->alloc_count > 0);
+  }
+};
+
+int main(int, char**) {
+
+  const auto a = std::array{4, 3, 2, 1};
+  test_allocator_statistics stats{};
+  const auto queue = GetAlloc{stats, a.begin(), a.end()};
+}

libcxx/test/std/containers/container.adaptors/queue/queue.cons/ctor_iterators.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// <queue>
+
+// template <class InputIterator>
+// queue(InputIterator, InputIterator);
+
+#include <array>
+#include <cassert>
+#include <queue>
+
+int main(int, char**) {
+  const auto a = std::array{4, 3, 2, 1};
+  const auto queue = std::queue{a.begin(), a.end()};
+  assert(queue.front() == 4);
+  assert(queue.back() == 1);
+  assert(queue.size() == 4);
+}

libcxx/test/std/containers/container.adaptors/stack/stack.cons.alloc/ctor_iterators.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// <queue>
+
+// template <class InputIterator, class Allocator>
+// stack(InputIterator, InputIterator, Allocator);
+
+#include <array>
+#include <cassert>
+#include <stack>
+
+#include "test_allocator.h"
+
+using base_type = std::stack<int, std::deque<int, test_allocator<int>>>;
+using iter = std::array<int, 4>::const_iterator;
+
+class GetAlloc : base_type {
+  test_allocator_statistics* stats;
+
+public:
+  GetAlloc(test_allocator_statistics& stats, iter begin, iter end)
+      : base_type{begin, end, test_allocator<int>{&stats}}, stats{&stats} {}
+  void check() {
+    assert(size() == 4);
+    assert(stats->alloc_count > 0);
+  }
+};
+
+int main(int, char**) {
+
+  const auto a = std::array{4, 3, 2, 1};
+  test_allocator_statistics stats{};
+  const auto queue = GetAlloc{stats, a.begin(), a.end()};
+}

libcxx/test/std/containers/container.adaptors/stack/stack.cons/ctor_iterators.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+
+// <queue>
+
+// template <class InputIterator>
+// stack(InputIterator, InputIterator);
+
+#include <array>
+#include <cassert>
+#include <stack>
+
+int main(int, char**) {
+  const auto a = std::array{4, 3, 2, 1};
+  const auto queue = std::stack{a.begin(), a.end()};
+  assert(queue.top() == 1);
+  assert(queue.size() == 4);
+}

libcxx/test/std/language.support/support.limits/support.limits.general/queue.version.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
+//
+//===----------------------------------------------------------------------===//
+//
+// WARNING: This test was generated by generate_feature_test_macro_components.py
+// and should not be edited manually.
+//
+// clang-format off
+
+// <queue>
+
+// Test the feature test macros defined by <queue>
+
+/*  Constant                                       Value
+    __cpp_lib_adaptor_iterator_pair_constructor    202106L [C++2b]
+*/
+
+#include <queue>
+#include "test_macros.h"
+
+#if TEST_STD_VER < 14
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER == 14
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER == 17
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER == 20
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER > 20
+
+# ifndef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should be defined in c++2b"
+# endif
+# if __cpp_lib_adaptor_iterator_pair_constructor != 202106L
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should have the value 202106L in c++2b"
+# endif
+
+#endif // TEST_STD_VER > 20
+
+int main(int, char**) { return 0; }

libcxx/test/std/language.support/support.limits/support.limits.general/stack.version.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
+//
+//===----------------------------------------------------------------------===//
+//
+// WARNING: This test was generated by generate_feature_test_macro_components.py
+// and should not be edited manually.
+//
+// clang-format off
+
+// <stack>
+
+// Test the feature test macros defined by <stack>
+
+/*  Constant                                       Value
+    __cpp_lib_adaptor_iterator_pair_constructor    202106L [C++2b]
+*/
+
+#include <stack>
+#include "test_macros.h"
+
+#if TEST_STD_VER < 14
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER == 14
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER == 17
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER == 20
+
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
+#elif TEST_STD_VER > 20
+
+# ifndef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should be defined in c++2b"
+# endif
+# if __cpp_lib_adaptor_iterator_pair_constructor != 202106L
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should have the value 202106L in c++2b"
+# endif
+
+#endif // TEST_STD_VER > 20
+
+int main(int, char**) { return 0; }

libcxx/test/std/language.support/support.limits/support.limits.general/version.version.pass.cpp

 //
 // clang-format off
 
 // <version>
 
 // Test the feature test macros defined by <version>
 
 /*  Constant                                       Value
+    __cpp_lib_adaptor_iterator_pair_constructor    202106L [C++2b]
     __cpp_lib_addressof_constexpr                  201603L [C++17]
     __cpp_lib_allocator_traits_is_always_equal     201411L [C++17]
     __cpp_lib_any                                  201606L [C++17]
     __cpp_lib_apply                                201603L [C++17]
     __cpp_lib_array_constexpr                      201603L [C++17]
                                                    201811L [C++20]
     __cpp_lib_as_const                             201510L [C++17]
     __cpp_lib_assume_aligned                       201811L [C++20]
/*  Constant                                       Value
     __cpp_lib_void_t                               201411L [C++17]
 */
 
 #include <version>
 #include "test_macros.h"
 
 #if TEST_STD_VER < 14
 
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
 # ifdef __cpp_lib_addressof_constexpr
 #   error "__cpp_lib_addressof_constexpr should not be defined before c++17"
 # endif
 
 # ifdef __cpp_lib_allocator_traits_is_always_equal
 #   error "__cpp_lib_allocator_traits_is_always_equal should not be defined before c++17"
 # endif
 

 # endif
 
 # ifdef __cpp_lib_void_t
 #   error "__cpp_lib_void_t should not be defined before c++17"
 # endif
 
 #elif TEST_STD_VER == 14
 
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
 # ifdef __cpp_lib_addressof_constexpr
 #   error "__cpp_lib_addressof_constexpr should not be defined before c++17"
 # endif
 
 # ifdef __cpp_lib_allocator_traits_is_always_equal
 #   error "__cpp_lib_allocator_traits_is_always_equal should not be defined before c++17"
 # endif
 

 # endif
 
 # ifdef __cpp_lib_void_t
 #   error "__cpp_lib_void_t should not be defined before c++17"
 # endif
 
 #elif TEST_STD_VER == 17
 
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
 # ifndef __cpp_lib_addressof_constexpr
 #   error "__cpp_lib_addressof_constexpr should be defined in c++17"
 # endif
 # if __cpp_lib_addressof_constexpr != 201603L
 #   error "__cpp_lib_addressof_constexpr should have the value 201603L in c++17"
 # endif
 
 # ifndef __cpp_lib_allocator_traits_is_always_equal

 #   error "__cpp_lib_void_t should be defined in c++17"
 # endif
 # if __cpp_lib_void_t != 201411L
 #   error "__cpp_lib_void_t should have the value 201411L in c++17"
 # endif
 
 #elif TEST_STD_VER == 20
 
+# ifdef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should not be defined before c++2b"
+# endif
+
 # ifndef __cpp_lib_addressof_constexpr
 #   error "__cpp_lib_addressof_constexpr should be defined in c++20"
 # endif
 # if __cpp_lib_addressof_constexpr != 201603L
 #   error "__cpp_lib_addressof_constexpr should have the value 201603L in c++20"
 # endif
 
 # ifndef __cpp_lib_allocator_traits_is_always_equal

 #   error "__cpp_lib_void_t should be defined in c++20"
 # endif
 # if __cpp_lib_void_t != 201411L
 #   error "__cpp_lib_void_t should have the value 201411L in c++20"
 # endif
 
 #elif TEST_STD_VER > 20
 
+# ifndef __cpp_lib_adaptor_iterator_pair_constructor
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should be defined in c++2b"
+# endif
+# if __cpp_lib_adaptor_iterator_pair_constructor != 202106L
+#   error "__cpp_lib_adaptor_iterator_pair_constructor should have the value 202106L in c++2b"
+# endif
+
 # ifndef __cpp_lib_addressof_constexpr
 #   error "__cpp_lib_addressof_constexpr should be defined in c++2b"
 # endif
 # if __cpp_lib_addressof_constexpr != 201603L
 #   error "__cpp_lib_addressof_constexpr should have the value 201603L in c++2b"
 # endif
 
 # ifndef __cpp_lib_allocator_traits_is_always_equal

libcxx/utils/generate_feature_test_macro_components.py

 #                   macros defined in <__config>.
 # unimplemented     An optional Boolean field with the value `True`. This field
 #                   is only used when a feature isn't fully implemented. Once
 #                   you've fully implemented the feature, you should remove
 #                   this field.
 # ================  ============================================================
 feature_test_macros = [ add_version_header(x) for x in [
   {
+    "name": "__cpp_lib_adaptor_iterator_pair_constructor",
+    "values": { "c++2b": 202106 },
+    "headers": ["queue", "stack"],
+  }, {
     "name": "__cpp_lib_addressof_constexpr",
     "values": { "c++17": 201603 },
     "headers": ["memory"],
   }, {
     "name": "__cpp_lib_allocator_traits_is_always_equal",
     "values": { "c++17": 201411 },
     "headers": ["deque", "forward_list", "list", "map", "memory", "scoped_allocator", "set", "string", "unordered_map", "unordered_set", "vector"],
   }, {