PR libstdc++/89128 add deduction guides for container adaptors

diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h
index aa8dd02ed6e..6d092c9bbfe 100644
--- a/libstdc++-v3/include/bits/stl_queue.h
+++ b/libstdc++-v3/include/bits/stl_queue.h
@@ -302,6 +302,18 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif // __cplusplus >= 201103L
     };
 
+#if __cpp_deduction_guides >= 201606
+  template<typename _Container,
+	   typename = enable_if_t<!__is_allocator<_Container>::value>>
+    queue(_Container) -> queue<typename _Container::value_type, _Container>;
+
+  template<typename _Container, typename _Allocator,
+	   typename = enable_if_t<!__is_allocator<_Container>::value>,
+	   typename = enable_if_t<__is_allocator<_Allocator>::value>>
+    queue(_Container, _Allocator)
+    -> queue<typename _Container::value_type, _Container>;
+#endif
+
   /**
    *  @brief  Queue equality comparison.
    *  @param  __x  A %queue.
@@ -653,6 +665,32 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif // __cplusplus >= 201103L
     };
 
+#if __cpp_deduction_guides >= 201606
+  template<typename _Compare, typename _Container,
+	   typename = enable_if_t<!__is_allocator<_Compare>::value>,
+	   typename = enable_if_t<!__is_allocator<_Container>::value>>
+    priority_queue(_Compare, _Container)
+    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
+
+  template<typename _InputIterator, typename _ValT
+	   = typename iterator_traits<_InputIterator>::value_type,
+	   typename _Compare = less<_ValT>,
+	   typename _Container = vector<_ValT>,
+	   typename = _RequireInputIter<_InputIterator>,
+	   typename = enable_if_t<!__is_allocator<_Compare>::value>,
+	   typename = enable_if_t<!__is_allocator<_Container>::value>>
+    priority_queue(_InputIterator, _InputIterator, _Compare = _Compare(),
+		   _Container = _Container())
+    -> priority_queue<_ValT, _Container, _Compare>;
+
+  template<typename _Compare, typename _Container, typename _Allocator,
+	   typename = enable_if_t<!__is_allocator<_Compare>::value>,
+	   typename = enable_if_t<!__is_allocator<_Container>::value>,
+	   typename = enable_if_t<__is_allocator<_Allocator>::value>>
+    priority_queue(_Compare, _Container, _Allocator)
+    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
+#endif
+
   // No equality/comparison operators are provided for priority_queue.
 
 #if __cplusplus >= 201103L
diff --git a/libstdc++-v3/include/bits/stl_stack.h b/libstdc++-v3/include/bits/stl_stack.h
index 8581dce210c..e8443a78a05 100644
--- a/libstdc++-v3/include/bits/stl_stack.h
+++ b/libstdc++-v3/include/bits/stl_stack.h
@@ -276,6 +276,18 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif // __cplusplus >= 201103L
     };
 
+#if __cpp_deduction_guides >= 201606
+  template<typename _Container,
+	   typename = enable_if_t<!__is_allocator<_Container>::value>>
+    stack(_Container) -> stack<typename _Container::value_type, _Container>;
+
+  template<typename _Container, typename _Allocator,
+	   typename = enable_if_t<!__is_allocator<_Container>::value>,
+	   typename = enable_if_t<__is_allocator<_Allocator>::value>>
+    stack(_Container, _Allocator)
+    -> stack<typename _Container::value_type, _Container>;
+#endif
+
   /**
    *  @brief  Stack equality comparison.
    *  @param  __x  A %stack.
diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/deduction.cc b/libstdc++-v3/testsuite/23_containers/priority_queue/deduction.cc
new file mode 100644
index 00000000000..4630cbb101c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/priority_queue/deduction.cc
@@ -0,0 +1,119 @@ 
+// Copyright (C) 2019 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++17" }
+// { dg-do compile { target c++17 } }
+
+#include <queue>
+#include <deque>
+#include <vector>
+#include <testsuite_iterators.h>
+
+template<typename T, typename U> struct require_same;
+template<typename T> struct require_same<T, T> { using type = void; };
+
+template<typename T, typename U>
+  typename require_same<T, U>::type
+  check_type(U&) { }
+
+void
+test01()
+{
+  std::priority_queue<unsigned> s0;
+
+  std::priority_queue s1 = s0;
+  check_type<std::priority_queue<unsigned>>(s1);
+
+  std::priority_queue s2 = std::move(s0);
+  check_type<std::priority_queue<unsigned>>(s2);
+
+  const std::priority_queue s3 = s0;
+  check_type<const std::priority_queue<unsigned>>(s3);
+
+  const std::priority_queue s4 = s3;
+  check_type<const std::priority_queue<unsigned>>(s4);
+
+  std::allocator<unsigned> a;
+  std::priority_queue s5(s0, a);
+  check_type<std::priority_queue<unsigned>>(s5);
+
+  std::priority_queue s6(std::move(s0), a);
+  check_type<std::priority_queue<unsigned>>(s6);
+
+  const std::priority_queue s7(s3, a);
+  check_type<const std::priority_queue<unsigned>>(s7);
+}
+
+template<typename T>
+  using input_iterator_seq
+    = __gnu_test::test_container<T, __gnu_test::input_iterator_wrapper>;
+
+void
+test02()
+{
+  using Deque = std::deque<int>;
+  Deque d;
+  using Vector = std::vector<short>;
+  Vector v;
+  using Cmp = std::greater<long>;
+  Cmp cmp;
+
+  std::priority_queue s1(cmp, d);
+  check_type<std::priority_queue<int, Deque, Cmp>>(s1);
+
+  std::priority_queue s2(cmp, d, d.get_allocator());
+  check_type<std::priority_queue<int, Deque, Cmp>>(s2);
+
+  std::priority_queue s3(cmp, std::move(d));
+  check_type<std::priority_queue<int, Deque, Cmp>>(s3);
+
+  std::priority_queue s4(cmp, std::move(d), d.get_allocator());
+  check_type<std::priority_queue<int, Deque, Cmp>>(s4);
+
+  std::priority_queue s5(cmp, v);
+  check_type<std::priority_queue<short, Vector, Cmp>>(s5);
+
+  std::priority_queue s6(cmp, v, v.get_allocator());
+  check_type<std::priority_queue<short, Vector, Cmp>>(s6);
+
+  std::priority_queue s7(cmp, std::move(v));
+  check_type<std::priority_queue<short, Vector, Cmp>>(s7);
+
+  std::priority_queue s8(cmp, std::move(v), v.get_allocator());
+  check_type<std::priority_queue<short, Vector, Cmp>>(s8);
+
+  short a[1] = {};
+  input_iterator_seq<short> seq(a);
+
+  std::priority_queue s9(seq.begin(), seq.end());
+  check_type<std::priority_queue<short>>(s9);
+
+  std::priority_queue s10(seq.begin(), seq.end(), {});
+  check_type<std::priority_queue<short>>(s10);
+
+  std::priority_queue s11(seq.begin(), seq.end(), {}, {});
+  check_type<std::priority_queue<short>>(s11);
+
+  std::priority_queue s12(seq.begin(), seq.end(), cmp);
+  check_type<std::priority_queue<short, Vector, Cmp>>(s12);
+
+  std::priority_queue s13(seq.begin(), seq.end(), cmp, {});
+  check_type<std::priority_queue<short, Vector, Cmp>>(s13);
+
+  std::priority_queue s14(seq.begin(), seq.end(), cmp, std::deque<short>{});
+  check_type<std::priority_queue<short, std::deque<short>, Cmp>>(s14);
+}
diff --git a/libstdc++-v3/testsuite/23_containers/queue/deduction.cc b/libstdc++-v3/testsuite/23_containers/queue/deduction.cc
new file mode 100644
index 00000000000..c8f6aeebecd
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/queue/deduction.cc
@@ -0,0 +1,89 @@ 
+// Copyright (C) 2019 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++17" }
+// { dg-do compile { target c++17 } }
+
+#include <queue>
+#include <deque>
+#include <list>
+
+template<typename T, typename U> struct require_same;
+template<typename T> struct require_same<T, T> { using type = void; };
+
+template<typename T, typename U>
+  typename require_same<T, U>::type
+  check_type(U&) { }
+
+void
+test01()
+{
+  std::queue<unsigned> s0;
+
+  std::queue s1 = s0;
+  check_type<std::queue<unsigned>>(s1);
+
+  std::queue s2 = std::move(s0);
+  check_type<std::queue<unsigned>>(s2);
+
+  const std::queue s3 = s0;
+  check_type<const std::queue<unsigned>>(s3);
+
+  const std::queue s4 = s3;
+  check_type<const std::queue<unsigned>>(s4);
+
+  std::allocator<unsigned> a;
+  std::queue s5(s0, a);
+  check_type<std::queue<unsigned>>(s5);
+
+  std::queue s6(std::move(s0), a);
+  check_type<std::queue<unsigned>>(s6);
+
+  const std::queue s7(s3, a);
+  check_type<const std::queue<unsigned>>(s7);
+}
+
+void
+test02()
+{
+  std::deque<unsigned> d;
+  std::list<long> l;
+
+  std::queue s1(d);
+  check_type<std::queue<unsigned>>(s1);
+
+  std::queue s2(d, d.get_allocator());
+  check_type<std::queue<unsigned>>(s2);
+
+  std::queue s3(std::move(d));
+  check_type<std::queue<unsigned>>(s3);
+
+  std::queue s4(std::move(d), d.get_allocator());
+  check_type<std::queue<unsigned>>(s4);
+
+  std::queue s5(l);
+  check_type<std::queue<long, std::list<long>>>(s5);
+
+  std::queue s6(l, l.get_allocator());
+  check_type<std::queue<long, std::list<long>>>(s6);
+
+  std::queue s7(std::move(l));
+  check_type<std::queue<long, std::list<long>>>(s7);
+
+  std::queue s8(std::move(l), l.get_allocator());
+  check_type<std::queue<long, std::list<long>>>(s8);
+}
diff --git a/libstdc++-v3/testsuite/23_containers/stack/deduction.cc b/libstdc++-v3/testsuite/23_containers/stack/deduction.cc
new file mode 100644
index 00000000000..3be443e1e8b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/stack/deduction.cc
@@ -0,0 +1,89 @@ 
+// Copyright (C) 2019 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++17" }
+// { dg-do compile { target c++17 } }
+
+#include <stack>
+#include <deque>
+#include <list>
+
+template<typename T, typename U> struct require_same;
+template<typename T> struct require_same<T, T> { using type = void; };
+
+template<typename T, typename U>
+  typename require_same<T, U>::type
+  check_type(U&) { }
+
+void
+test01()
+{
+  std::stack<unsigned> s0;
+
+  std::stack s1 = s0;
+  check_type<std::stack<unsigned>>(s1);
+
+  std::stack s2 = std::move(s0);
+  check_type<std::stack<unsigned>>(s2);
+
+  const std::stack s3 = s0;
+  check_type<const std::stack<unsigned>>(s3);
+
+  const std::stack s4 = s3;
+  check_type<const std::stack<unsigned>>(s4);
+
+  std::allocator<unsigned> a;
+  std::stack s5(s0, a);
+  check_type<std::stack<unsigned>>(s5);
+
+  std::stack s6(std::move(s0), a);
+  check_type<std::stack<unsigned>>(s6);
+
+  const std::stack s7(s3, a);
+  check_type<const std::stack<unsigned>>(s7);
+}
+
+void
+test02()
+  {
+  std::deque<unsigned> d;
+  std::list<long> l;
+
+  std::stack s1(d);
+  check_type<std::stack<unsigned>>(s1);
+
+  std::stack s2(d, d.get_allocator());
+  check_type<std::stack<unsigned>>(s2);
+
+  std::stack s3(std::move(d));
+  check_type<std::stack<unsigned>>(s3);
+
+  std::stack s4(std::move(d), d.get_allocator());
+  check_type<std::stack<unsigned>>(s4);
+
+  std::stack s5(l);
+  check_type<std::stack<long, std::list<long>>>(s5);
+
+  std::stack s6(l, l.get_allocator());
+  check_type<std::stack<long, std::list<long>>>(s6);
+
+  std::stack s7(std::move(l));
+  check_type<std::stack<long, std::list<long>>>(s7);
+
+  std::stack s8(std::move(l), l.get_allocator());
+  check_type<std::stack<long, std::list<long>>>(s8);
+}