commit b7e8fb5e48279ffa5f424e3dd0bb3dfcbe69f5d5
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu May 13 16:16:26 2021

    libstdc++: Add container adaptor constructors taking iterators (P1425R4)
    
    This adds a feature that was recently added to the C++23 working draft.
    
    Signed-off-by: Jonathan Wakely <jwakely@redhat.com>
    
    libstdc++-v3/ChangeLog:
    
            * include/bits/stl_queue.h
            (__cpp_lib_adaptor_iterator_pair_constructor): Define for C++23, as
            per P1425R4.
            (queue(InputIterator, InputIterator)): Likewise.
            (queue(InputIterator, InputIterator, const Alloc&)): Likewise.
            * include/bits/stl_stack.h
            (__cpp_lib_adaptor_iterator_pair_constructor): Likewise.
            (stack(InputIterator, InputIterator)): Likewise.
            (stack(InputIterator, InputIterator, const Alloc&)): Likewise.
            * include/std/version (__cpp_lib_adaptor_iterator_pair_constructor):
            Define.
            * testsuite/23_containers/queue/cons_from_iters.cc: New test.
            * testsuite/23_containers/stack/cons_from_iters.cc: New test.

diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h
index 4519f9f2fec..ccd1122f848 100644
--- a/libstdc++-v3/include/bits/stl_queue.h
+++ b/libstdc++-v3/include/bits/stl_queue.h
@@ -194,6 +194,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	queue(queue&& __q, const _Alloc& __a)
 	: c(std::move(__q.c), __a) { }
+
+#if __cplusplus > 202002L
+#define __cpp_lib_adaptor_iterator_pair_constructor 202100L
+
+      template<typename _InputIterator,
+	       typename = _RequireInputIter<_InputIterator>>
+	queue(_InputIterator __first, _InputIterator __last)
+	: c(__first, __last) { }
+
+      template<typename _InputIterator, typename _Alloc,
+	       typename = _RequireInputIter<_InputIterator>,
+	       typename = _Uses<_Alloc>>
+	queue(_InputIterator __first, _InputIterator __last, const _Alloc& __a)
+	: c(__first, __last, __a) { }
+#endif
 #endif
 
       /**
@@ -331,6 +346,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename = _RequireAllocator<_Allocator>>
     queue(_Container, _Allocator)
     -> queue<typename _Container::value_type, _Container>;
+
+#ifdef __cpp_lib_adaptor_iterator_pair_constructor
+  template<typename _InputIterator,
+	   typename _ValT
+	     = typename iterator_traits<_InputIterator>::value_type,
+	   typename = _RequireInputIter<_InputIterator>>
+    queue(_InputIterator, _InputIterator) -> queue<_ValT>;
+
+  template<typename _InputIterator, typename _Allocator,
+	   typename _ValT
+	     = typename iterator_traits<_InputIterator>::value_type,
+	   typename = _RequireInputIter<_InputIterator>,
+	   typename = _RequireAllocator<_Allocator>>
+    queue(_InputIterator, _InputIterator, _Allocator)
+    -> queue<_ValT, deque<_ValT, _Allocator>>;
+#endif
 #endif
 
   /**
diff --git a/libstdc++-v3/include/bits/stl_stack.h b/libstdc++-v3/include/bits/stl_stack.h
index 85137b9d428..af234d6899c 100644
--- a/libstdc++-v3/include/bits/stl_stack.h
+++ b/libstdc++-v3/include/bits/stl_stack.h
@@ -170,6 +170,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       stack(_Sequence&& __c)
       : c(std::move(__c)) { }
 
+#if __cplusplus > 202002L
+#define __cpp_lib_adaptor_iterator_pair_constructor 202100L
+
+      template<typename _InputIterator,
+	       typename = _RequireInputIter<_InputIterator>>
+	stack(_InputIterator __first, _InputIterator __last)
+	: c(__first, __last) { }
+#endif
+
+
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	explicit
 	stack(const _Alloc& __a)
@@ -190,6 +200,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	stack(stack&& __q, const _Alloc& __a)
 	: c(std::move(__q.c), __a) { }
+
+#if __cplusplus > 202002L
+      template<typename _InputIterator, typename _Alloc,
+	       typename = _RequireInputIter<_InputIterator>,
+	       typename = _Uses<_Alloc>>
+	stack(_InputIterator __first, _InputIterator __last, const _Alloc& __a)
+	: c(__first, __last, __a) { }
+#endif
 #endif
 
       /**
@@ -303,6 +321,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	   typename = _RequireAllocator<_Allocator>>
     stack(_Container, _Allocator)
     -> stack<typename _Container::value_type, _Container>;
+
+#ifdef __cpp_lib_adaptor_iterator_pair_constructor
+  template<typename _InputIterator, typename _Allocator,
+	   typename _ValT
+	     = typename iterator_traits<_InputIterator>::value_type,
+	   typename = _RequireInputIter<_InputIterator>>
+    stack(_InputIterator, _InputIterator) -> stack<_ValT>;
+
+  template<typename _InputIterator, typename _Allocator,
+	   typename _ValT
+	     = typename iterator_traits<_InputIterator>::value_type,
+	   typename = _RequireInputIter<_InputIterator>,
+	   typename = _RequireAllocator<_Allocator>>
+    stack(_InputIterator, _InputIterator, _Allocator)
+    -> stack<_ValT, deque<_ValT, _Allocator>>;
+#endif
 #endif
 
   /**
diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version
index 42f7dfa62ad..66b3d1704b7 100644
--- a/libstdc++-v3/include/std/version
+++ b/libstdc++-v3/include/std/version
@@ -281,6 +281,7 @@
 
 #if __cplusplus > 202002L
 // c++2b
+#define __cpp_lib_adaptor_iterator_pair_constructor 202100L
 #define __cpp_lib_invoke_r 202106L
 #define __cpp_lib_is_scoped_enum 202011L
 #define __cpp_lib_string_contains 202011L
diff --git a/libstdc++-v3/testsuite/23_containers/queue/cons_from_iters.cc b/libstdc++-v3/testsuite/23_containers/queue/cons_from_iters.cc
new file mode 100644
index 00000000000..de0fc310c24
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/queue/cons_from_iters.cc
@@ -0,0 +1,68 @@
+// Copyright (C) 2021 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <queue>
+
+#ifndef __cpp_lib_adaptor_iterator_pair_constructor
+#error Feature test macro for iterator pair constructors is missing in <queue>
+#elif __cpp_lib_adaptor_iterator_pair_constructor != 202100L
+#error Feature test macro for iterator pair constructors has wrong value in <queue>
+#endif
+
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void
+test_p1425r4()
+{
+  const int vals[] = { 5, 4, 3, 2, 1, 9 };
+
+  std::queue<int> q(std::begin(vals), std::end(vals));
+  VERIFY( q.size() == std::size(vals) );
+  VERIFY( q.front() == 5 );
+  VERIFY( q.back() == 9 );
+
+  using Alloc = __gnu_test::uneq_allocator<int>;
+
+  struct Queue : std::queue<int, std::deque<int, Alloc>>
+  {
+    using queue::queue;
+
+    Alloc get_allocator() const { return c.get_allocator(); }
+  };
+
+  Alloc a0, a1(1);
+  Queue q0(std::next(vals), std::end(vals));
+  VERIFY( q0.size() == std::size(vals) - 1 );
+  VERIFY( q0.front() == 4 );
+  VERIFY( q0.back() == 9 );
+  VERIFY( q0.get_allocator() == a0 );
+
+  Queue q1(std::next(vals, 2), std::end(vals), a1);
+  VERIFY( q1.size() == std::size(vals) - 2 );
+  VERIFY( q1.front() == 3 );
+  VERIFY( q1.back() == 9 );
+  VERIFY( q1.get_allocator() == a1 );
+}
+
+int main()
+{
+  test_p1425r4();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/stack/cons_from_iters.cc b/libstdc++-v3/testsuite/23_containers/stack/cons_from_iters.cc
new file mode 100644
index 00000000000..4c648926d62
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/stack/cons_from_iters.cc
@@ -0,0 +1,65 @@
+// Copyright (C) 2021 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <stack>
+
+#ifndef __cpp_lib_adaptor_iterator_pair_constructor
+#error Feature test macro for iterator pair constructors is missing in <stack>
+#elif __cpp_lib_adaptor_iterator_pair_constructor != 202100L
+#error Feature test macro for iterator pair constructors has wrong value in <stack>
+#endif
+
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void
+test_p1425r4()
+{
+  const int vals[] = { 1, 2, 3, 7, 8, 9, 5, 6, 7 };
+
+  std::stack<int> s(std::begin(vals), std::end(vals));
+  VERIFY( s.size() == std::size(vals) );
+  VERIFY( s.top() == 7 );
+
+  using Alloc = __gnu_test::uneq_allocator<int>;
+
+  struct Stack : std::stack<int, std::deque<int, Alloc>>
+  {
+    using stack::stack;
+
+    Alloc get_allocator() const { return c.get_allocator(); }
+  };
+
+  Alloc a0, a1(1);
+  Stack s0(std::begin(vals), std::end(vals) - 1);
+  VERIFY( s0.size() == std::size(vals) - 1 );
+  VERIFY( s0.top() == 6 );
+  VERIFY( s0.get_allocator() == a0 );
+
+  Stack s1(std::begin(vals), std::end(vals) - 2, a1);
+  VERIFY( s1.size() == std::size(vals) - 2 );
+  VERIFY( s1.top() == 5 );
+  VERIFY( s1.get_allocator() == a1 );
+}
+
+int main()
+{
+  test_p1425r4();
+}