commit c53655d1663e0c7edfffaae14bc47a04cbc2da0f
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Wed Jun 7 13:18:42 2017 +0100

    Add C++17 deduction guide for std::basic_string (P0433R2, partial)
    
    	* include/bits/alloc_traits.h (__is_allocator, _RequireAllocator):
    	New trait and alias for detecting Allocator-like types.
    	* include/bits/basic_string.h (basic_string): Add deduction guide
    	from P0433.
    	* include/ext/alloc_traits.h (__gnu_cxx::__alloc_traits): Add template
    	parameter with default template argument that causes substitution
    	failures for types that cannot be allocators.
    	* testsuite/21_strings/basic_string/cons/char/deduction.cc: New.
    	* testsuite/21_strings/basic_string/cons/wchar_t/deduction.cc: New.

diff --git a/libstdc++-v3/include/bits/alloc_traits.h b/libstdc++-v3/include/bits/alloc_traits.h
index 4d1e489..86a4859 100644
--- a/libstdc++-v3/include/bits/alloc_traits.h
+++ b/libstdc++-v3/include/bits/alloc_traits.h
@@ -598,6 +598,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     : is_copy_constructible<_Tp>
     { };
 
+#if __cplusplus >= 201103L
+  // Trait to detect Allocator-like types.
+  template<typename _Alloc, typename = void>
+    struct __is_allocator : false_type { };
+
+  template<typename _Alloc>
+    struct __is_allocator<_Alloc,
+      __void_t<typename _Alloc::value_type,
+	       decltype(std::declval<_Alloc&>().allocate(size_t{}))>>
+    : true_type { };
+
+  template<typename _Alloc>
+    using _RequireAllocator
+      = typename enable_if<__is_allocator<_Alloc>::value, _Alloc>::type;
+#endif
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index b6693c4..519d686 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -5674,6 +5674,18 @@ _GLIBCXX_END_NAMESPACE_CXX11
   };
 #endif  // !_GLIBCXX_USE_CXX11_ABI
 
+#if __cpp_deduction_guides >= 201606
+_GLIBCXX_BEGIN_NAMESPACE_CXX11
+  template<typename _InputIterator, typename _CharT
+	     = typename iterator_traits<_InputIterator>::value_type,
+	   typename _Allocator = allocator<_CharT>,
+	   typename = _RequireInputIter<_InputIterator>,
+	   typename = _RequireAllocator<_Allocator>>
+    basic_string(_InputIterator, _InputIterator, _Allocator = _Allocator())
+      -> basic_string<_CharT, char_traits<_CharT>, _Allocator>;
+_GLIBCXX_END_NAMESPACE_CXX11
+#endif
+
   // operator+
   /**
    *  @brief  Concatenate two strings.
diff --git a/libstdc++-v3/include/ext/alloc_traits.h b/libstdc++-v3/include/ext/alloc_traits.h
index f4435ce..fe56551 100644
--- a/libstdc++-v3/include/ext/alloc_traits.h
+++ b/libstdc++-v3/include/ext/alloc_traits.h
@@ -46,7 +46,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
  * @brief  Uniform interface to C++98 and C++11 allocators.
  * @ingroup allocators
 */
-template<typename _Alloc>
+template<typename _Alloc, typename = typename _Alloc::value_type>
   struct __alloc_traits
 #if __cplusplus >= 201103L
   : std::allocator_traits<_Alloc>
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/deduction.cc b/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/deduction.cc
new file mode 100644
index 0000000..c9af333
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/cons/char/deduction.cc
@@ -0,0 +1,118 @@
+// Copyright (C) 2017 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++1z } }
+
+#include <string>
+#include <testsuite_iterators.h>
+
+template<typename C>
+  using input_iterator_seq
+    = __gnu_test::test_container<C, __gnu_test::input_iterator_wrapper>;
+
+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::string s0;
+  std::allocator<char> a;
+
+  std::basic_string s1 = s0;
+  check_type<std::string>(s1);
+
+  std::basic_string s2 = std::move(s0);
+  check_type<std::string>(s2);
+
+  const std::basic_string s3 = s0;
+  check_type<const std::string>(s3);
+
+  const std::basic_string s4 = s3;
+  check_type<const std::string>(s4);
+
+  std::basic_string s5(s0, a);
+  check_type<std::string>(s5);
+
+  std::basic_string s6(std::move(s0), a);
+  check_type<std::string>(s6);
+
+  std::basic_string s7(s0, 0, 0);
+  check_type<std::string>(s7);
+}
+
+void
+test02()
+{
+  char a[1] = {};
+  input_iterator_seq<char> seq(a);
+
+  std::basic_string s1(seq.begin(), seq.end());
+  check_type<std::string>(s1);
+
+  std::basic_string s2(seq.begin(), seq.end(), std::allocator<char>());
+  check_type<std::string>(s2);
+
+  std::basic_string s3((char)1, 'a');
+  check_type<std::string>(s3);
+
+  std::basic_string s4((char)1, 'a', std::allocator<char>());
+  check_type<std::string>(s4);
+}
+
+void
+test03()
+{
+  char16_t a[1] = {};
+  input_iterator_seq<char16_t> seq(a);
+
+  std::basic_string s1(seq.begin(), seq.end());
+  check_type<std::u16string>(s1);
+
+  std::basic_string s2(seq.begin(), seq.end(), std::allocator<char16_t>());
+  check_type<std::u16string>(s2);
+
+  std::basic_string s3((char16_t)1, u'a');
+  check_type<std::u16string>(s3);
+
+  std::basic_string s4((char16_t)1, u'a', std::allocator<char16_t>());
+  check_type<std::u16string>(s4);
+}
+
+void
+test04()
+{
+  char32_t a[1] = {};
+  input_iterator_seq<char32_t> seq(a);
+
+  std::basic_string s1(seq.begin(), seq.end());
+  check_type<std::u32string>(s1);
+
+  std::basic_string s2(seq.begin(), seq.end(), std::allocator<char32_t>());
+  check_type<std::u32string>(s2);
+
+  std::basic_string s3((char32_t)1, U'a');
+  check_type<std::u32string>(s3);
+
+  std::basic_string s4((char32_t)1, U'a', std::allocator<char32_t>());
+  check_type<std::u32string>(s4);
+}
diff --git a/libstdc++-v3/testsuite/21_strings/basic_string/cons/wchar_t/deduction.cc b/libstdc++-v3/testsuite/21_strings/basic_string/cons/wchar_t/deduction.cc
new file mode 100644
index 0000000..1f8eadb
--- /dev/null
+++ b/libstdc++-v3/testsuite/21_strings/basic_string/cons/wchar_t/deduction.cc
@@ -0,0 +1,77 @@
+// Copyright (C) 2017 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++1z } }
+
+#include <string>
+#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::wstring s0;
+  std::allocator<wchar_t> a;
+
+  std::basic_string s1 = s0;
+  check_type<std::wstring>(s1);
+
+  std::basic_string s2 = std::move(s0);
+  check_type<std::wstring>(s2);
+
+  const std::basic_string s3 = s0;
+  check_type<const std::wstring>(s3);
+
+  const std::basic_string s4 = s2;
+  check_type<const std::wstring>(s4);
+
+  std::basic_string s5(s0, a);
+  check_type<std::wstring>(s5);
+
+  std::basic_string s6(std::move(s0), a);
+  check_type<std::wstring>(s6);
+
+  std::basic_string s7(s0, 0, 0);
+  check_type<std::wstring>(s7);
+}
+
+void
+test02()
+{
+  using namespace __gnu_test;
+  wchar_t a[1] = {};
+  test_container<wchar_t, input_iterator_wrapper> seq(a);
+
+  std::basic_string s1(seq.begin(), seq.end());
+  check_type<std::wstring>(s1);
+
+  std::basic_string s2(seq.begin(), seq.end(), std::allocator<wchar_t>());
+  check_type<std::wstring>(s2);
+
+  std::basic_string s3((wchar_t)1, L'a');
+  check_type<std::wstring>(s3);
+
+  std::basic_string s4((wchar_t)1, L'a', std::allocator<wchar_t>());
+  check_type<std::wstring>(s4);
+}