Patchwork [v3] implement allocator-extended constructors in <tuple>

login
register
mail settings
Submitter Jonathan Wakely
Date May 30, 2011, 4:32 p.m.
Message ID <BANLkTinOKqCk2xKsO_TfQ=Y=m6qW0N8D1Q@mail.gmail.com>
Download mbox | patch
Permalink /patch/97937/
State New
Headers show

Comments

Jonathan Wakely - May 30, 2011, 4:32 p.m.
2011-05-30  Jonathan Wakely  <jwakely.gcc@gmail.com>

        * include/std/tuple: Implement uses-allocator construction.
        * include/bits/allocator.h (uses_allocator): Move to ...
        * include/bits/uses_allocator.h: New file.
        * include/Makefile.am: Add new header.
        * include/Makefile.in: Regenerate.
        * testsuite/20_util/uses_allocator/cons_neg.cc: New.
        * testsuite/20_util/uses_allocator/construction.cc: New.
        * testsuite/20_util/tuple/cons/allocate_noncopyable.cc: New.
        * testsuite/20_util/tuple/cons/allocators.cc: New.

Tested x86_64-linux, committed to trunk.

I move the uses_allocator code to a separate header because <tuple>
only needs that, not the whole of bits/allocator.h, and I defined
three tag types, __uses_alloc0, __uses_alloc1 and __uses_alloc2, which
are used to dispatch to the appropriate constructor. If uses_allocator
is false then alloc0 is used, if uses_allocator<T, Alloc> is true then
alloc1 is used if is_constructible<T, allocator_arg_t, Alloc, Args...>
is true, otherwise alloc2 is used.  The function template
__use_alloc<T, Alloc, Args...>(const Alloc&) returns a type derived
from one of those tags. The tag also holds a pointer to the allocator
if it will be used, to save passing it as a separate argument.

N.B. the code could be made simpler using delegating constructors
because the _Tuple_impl constructors taking allocator_arg_t could just
pass their arguments to _Head_base and then _Head_base could call
__use_alloc and dispatch to the appropriate delegated constructor.
That can be changed later when G++ supports delegating ctors.
H.J. Lu - May 30, 2011, 8:14 p.m.
On Mon, May 30, 2011 at 9:32 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> 2011-05-30  Jonathan Wakely  <jwakely.gcc@gmail.com>
>
>        * include/std/tuple: Implement uses-allocator construction.
>        * include/bits/allocator.h (uses_allocator): Move to ...
>        * include/bits/uses_allocator.h: New file.
>        * include/Makefile.am: Add new header.
>        * include/Makefile.in: Regenerate.
>        * testsuite/20_util/uses_allocator/cons_neg.cc: New.
>        * testsuite/20_util/uses_allocator/construction.cc: New.
>        * testsuite/20_util/tuple/cons/allocate_noncopyable.cc: New.
>        * testsuite/20_util/tuple/cons/allocators.cc: New.
>
> Tested x86_64-linux, committed to trunk.
>
>

This may have caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49236
Jonathan Wakely - May 30, 2011, 10:53 p.m.
On 30 May 2011 21:14, H.J. Lu <hjl.tools@gmail.com> wrote:
> On Mon, May 30, 2011 at 9:32 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>> 2011-05-30  Jonathan Wakely  <jwakely.gcc@gmail.com>
>>
>>        * include/std/tuple: Implement uses-allocator construction.
>>        * include/bits/allocator.h (uses_allocator): Move to ...
>>        * include/bits/uses_allocator.h: New file.
>>        * include/Makefile.am: Add new header.
>>        * include/Makefile.in: Regenerate.
>>        * testsuite/20_util/uses_allocator/cons_neg.cc: New.
>>        * testsuite/20_util/uses_allocator/construction.cc: New.
>>        * testsuite/20_util/tuple/cons/allocate_noncopyable.cc: New.
>>        * testsuite/20_util/tuple/cons/allocators.cc: New.
>>
>> Tested x86_64-linux, committed to trunk.
>>
>>
>
> This may have caused:
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49236


It did, I tweaked the test in my tree but didn't include it in the
commit.  Thanks to Paolo for fixing it.

Patch

Index: include/bits/allocator.h
===================================================================
--- include/bits/allocator.h	(revision 174380)
+++ include/bits/allocator.h	(working copy)
@@ -49,7 +49,7 @@ 
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 #include <bits/ptr_traits.h>
-#include <type_traits> // For _GLIBCXX_HAS_NESTED_TYPE
+#include <bits/uses_allocator.h>
 #include <limits>
 #endif
 
@@ -207,32 +207,6 @@ 
       }
     };
 
-
-  /// [allocator.tag]
-  struct allocator_arg_t { };
-
-  constexpr allocator_arg_t allocator_arg = allocator_arg_t();
-
-_GLIBCXX_HAS_NESTED_TYPE(allocator_type)
-
-  template<typename _Tp, typename _Alloc,
-	   bool = __has_allocator_type<_Tp>::value>
-    struct __uses_allocator_helper
-    : public false_type { };
-
-  template<typename _Tp, typename _Alloc>
-    struct __uses_allocator_helper<_Tp, _Alloc, true>
-    : public integral_constant<bool, is_convertible<_Alloc,
-				     typename _Tp::allocator_type>::value>
-    { };
-
-  /// [allocator.uses.trait]
-  template<typename _Tp, typename _Alloc>
-    struct uses_allocator
-    : public integral_constant<bool,
-			       __uses_allocator_helper<_Tp, _Alloc>::value>
-    { };
-
   template<typename _Alloc, typename _Tp>
     class __alloctr_rebind_helper
     {
Index: include/bits/uses_allocator.h
===================================================================
--- include/bits/uses_allocator.h	(revision 0)
+++ include/bits/uses_allocator.h	(revision 0)
@@ -0,0 +1,109 @@ 
+// Uses-allocator Construction -*- C++ -*-
+
+// Copyright (C) 2010, 2011 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+#ifndef _USES_ALLOCATOR_H
+#define _USES_ALLOCATOR_H 1
+
+#ifndef __GXX_EXPERIMENTAL_CXX0X__
+# include <bits/c++0x_warning.h>
+#else
+
+#include <type_traits>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+  /// [allocator.tag]
+  struct allocator_arg_t { };
+
+  constexpr allocator_arg_t allocator_arg = allocator_arg_t();
+
+_GLIBCXX_HAS_NESTED_TYPE(allocator_type)
+
+  template<typename _Tp, typename _Alloc,
+	   bool = __has_allocator_type<_Tp>::value>
+    struct __uses_allocator_helper
+    : public false_type { };
+
+  template<typename _Tp, typename _Alloc>
+    struct __uses_allocator_helper<_Tp, _Alloc, true>
+    : public integral_constant<bool, is_convertible<_Alloc,
+				     typename _Tp::allocator_type>::value>
+    { };
+
+  /// [allocator.uses.trait]
+  template<typename _Tp, typename _Alloc>
+    struct uses_allocator
+    : public integral_constant<bool,
+			       __uses_allocator_helper<_Tp, _Alloc>::value>
+    { };
+
+  template<typename _Tp, typename _Alloc, typename... _Args>
+    struct __uses_allocator_arg
+    : is_constructible<_Tp, _Alloc, _Args...>
+    { static_assert( uses_allocator<_Tp, _Alloc>::value, "uses allocator" ); };
+
+  struct __uses_alloc_base { };
+  struct __uses_alloc0 : __uses_alloc_base
+  { struct _Anything { _Anything(...) { } } _M_a; };
+  template<typename _Alloc>
+    struct __uses_alloc1 : __uses_alloc_base { const _Alloc* _M_a; };
+  template<typename _Alloc>
+    struct __uses_alloc2 : __uses_alloc_base { const _Alloc* _M_a; };
+
+  template<bool, typename _Alloc, typename... _Args>
+    struct __uses_alloc;
+
+  template<typename _Tp, typename _Alloc, typename... _Args>
+    struct __uses_alloc<true, _Tp, _Alloc, _Args...>
+    : conditional<
+        is_constructible<_Tp, allocator_arg_t, _Alloc, _Args...>::value,
+        __uses_alloc1<_Alloc>,
+       	__uses_alloc2<_Alloc>>::type
+    { };
+
+  template<typename _Tp, typename _Alloc, typename... _Args>
+    struct __uses_alloc<false, _Tp, _Alloc, _Args...>
+    : __uses_alloc0 { };
+
+  template<typename _Tp, typename _Alloc, typename... _Args>
+    struct __uses_alloc_impl
+    : __uses_alloc<uses_allocator<_Tp, _Alloc>::value, _Tp,  _Alloc, _Args...>
+    { };
+
+  template<typename _Tp, typename _Alloc, typename... _Args>
+    __uses_alloc_impl<_Tp, _Alloc, _Args...>
+    __use_alloc(const _Alloc& __a)
+    {
+      __uses_alloc_impl<_Tp, _Alloc, _Args...> __ret;
+      __ret._M_a = &__a;
+      return __ret;
+    }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
+#endif
+#endif
Index: include/std/tuple
===================================================================
--- include/std/tuple	(revision 174358)
+++ include/std/tuple	(working copy)
@@ -36,6 +36,7 @@ 
 #else
 
 #include <utility>
+#include <bits/uses_allocator.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -81,10 +82,35 @@ 
       constexpr _Head_base(const _Head& __h)
       : _Head(__h) { }
 
-      template<typename _UHead>
+      template<typename _UHead, typename = typename
+	       enable_if<!is_convertible<_UHead,
+	                                 __uses_alloc_base>::value>::type>
         _Head_base(_UHead&& __h)
 	: _Head(std::forward<_UHead>(__h)) { }
 
+      _Head_base(__uses_alloc0)
+      : _Head() { }
+
+      template<typename _Alloc>
+	_Head_base(__uses_alloc1<_Alloc> __a)
+	: _Head(allocator_arg, *__a._M_a) { }
+
+      template<typename _Alloc>
+	_Head_base(__uses_alloc2<_Alloc> __a)
+	: _Head(*__a._M_a) { }
+
+      template<typename _UHead>
+	_Head_base(__uses_alloc0, _UHead&& __uhead)
+	: _Head(std::forward<_UHead>(__uhead)) { }
+
+      template<typename _Alloc, typename _UHead>
+	_Head_base(__uses_alloc1<_Alloc> __a, _UHead&& __uhead)
+	: _Head(allocator_arg, *__a._M_a, std::forward<_UHead>(__uhead)) { }
+
+      template<typename _Alloc, typename _UHead>
+	_Head_base(__uses_alloc2<_Alloc> __a, _UHead&& __uhead)
+	: _Head(std::forward<_UHead>(__uhead), *__a._M_a) { }
+
       _Head&       _M_head() noexcept       { return *this; }
       const _Head& _M_head() const noexcept { return *this; }
     };
@@ -98,10 +124,36 @@ 
       constexpr _Head_base(const _Head& __h)
       : _M_head_impl(__h) { }
 
-      template<typename _UHead>
+      template<typename _UHead, typename = typename
+	       enable_if<!is_convertible<_UHead,
+	                                 __uses_alloc_base>::value>::type>
         _Head_base(_UHead&& __h)
 	: _M_head_impl(std::forward<_UHead>(__h)) { }
 
+      _Head_base(__uses_alloc0)
+      : _M_head_impl() { }
+
+      template<typename _Alloc>
+	_Head_base(__uses_alloc1<_Alloc> __a)
+	: _M_head_impl(allocator_arg, *__a._M_a) { }
+
+      template<typename _Alloc>
+	_Head_base(__uses_alloc2<_Alloc> __a)
+	: _M_head_impl(*__a._M_a) { }
+
+      template<typename _UHead>
+	_Head_base(__uses_alloc0, _UHead&& __uhead)
+	: _M_head_impl(std::forward<_UHead>(__uhead)) { }
+
+      template<typename _Alloc, typename _UHead>
+	_Head_base(__uses_alloc1<_Alloc> __a, _UHead&& __uhead)
+	: _M_head_impl(allocator_arg, *__a._M_a, std::forward<_UHead>(__uhead))
+	{ }
+
+      template<typename _Alloc, typename _UHead>
+	_Head_base(__uses_alloc2<_Alloc> __a, _UHead&& __uhead)
+	: _M_head_impl(std::forward<_UHead>(__uhead), *__a._M_a) { }
+
       _Head&       _M_head() noexcept       { return _M_head_impl; }
       const _Head& _M_head() const noexcept { return _M_head_impl; }        
 
@@ -128,6 +180,17 @@ 
     {
       template<std::size_t, typename...> friend class _Tuple_impl;
 
+      _Tuple_impl() = default;
+
+      template<typename _Alloc>
+        _Tuple_impl(allocator_arg_t, const _Alloc&) { }
+
+      template<typename _Alloc>
+        _Tuple_impl(allocator_arg_t, const _Alloc&, const _Tuple_impl&) { }
+
+      template<typename _Alloc>
+        _Tuple_impl(allocator_arg_t, const _Alloc&, _Tuple_impl&&) { }
+
     protected:
       void _M_swap(_Tuple_impl&) noexcept { /* no-op */ }
     };
@@ -160,7 +223,8 @@ 
       constexpr _Tuple_impl(const _Head& __head, const _Tail&... __tail)
       : _Inherited(__tail...), _Base(__head) { }
 
-      template<typename _UHead, typename... _UTail> 
+      template<typename _UHead, typename... _UTail, typename = typename
+               std::enable_if<sizeof...(_Tail)==sizeof...(_UTail)>::type> 
         explicit
         _Tuple_impl(_UHead&& __head, _UTail&&... __tail)
 	: _Inherited(std::forward<_UTail>(__tail)...),
@@ -183,6 +247,54 @@ 
 	: _Inherited(std::move(__in._M_tail())),
 	  _Base(std::forward<_UHead>(__in._M_head())) { }
 
+      template<typename _Alloc>
+	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a)
+	: _Inherited(__tag, __a),
+          _Base(__use_alloc<_Head>(__a)) { }
+
+      template<typename _Alloc>
+	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
+	    const _Head& __head, const _Tail&... __tail)
+	: _Inherited(__tag, __a, __tail...),
+          _Base(__use_alloc<_Head, _Alloc, _Head>(__a), __head) { }
+
+      template<typename _Alloc, typename _UHead, typename... _UTail,
+               typename = typename std::enable_if<sizeof...(_Tail)
+		                                  ==sizeof...(_UTail)>::type>
+	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
+	            _UHead&& __head, _UTail&&... __tail)
+	: _Inherited(__tag, __a, std::forward<_UTail>(__tail)...),
+          _Base(__use_alloc<_Head, _Alloc, _UHead>(__a),
+	        std::forward<_UHead>(__head)) { }
+
+      template<typename _Alloc>
+        _Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
+	            const _Tuple_impl& __in)
+	: _Inherited(__tag, __a, __in._M_tail()), 
+          _Base(__use_alloc<_Head, _Alloc, _Head>(__a), __in._M_head()) { }
+
+      template<typename _Alloc>
+	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
+	            _Tuple_impl&& __in)
+	noexcept(std::is_nothrow_move_constructible<_Head>::value
+		 && std::is_nothrow_move_constructible<_Inherited>::value)
+	: _Inherited(__tag, __a, std::move(__in._M_tail())), 
+	  _Base(__use_alloc<_Head, _Alloc, _Head>(__a),
+	        std::forward<_Head>(__in._M_head())) { }
+
+      template<typename _Alloc, typename... _UElements>
+	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
+	            const _Tuple_impl<_Idx, _UElements...>& __in)
+	: _Inherited(__tag, __a, __in._M_tail()),
+	  _Base(__use_alloc<_Head, _Alloc, _Head>(__a), __in._M_head()) { }
+
+      template<typename _Alloc, typename _UHead, typename... _UTails>
+	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
+	            _Tuple_impl<_Idx, _UHead, _UTails...>&& __in)
+	: _Inherited(__tag, __a, std::move(__in._M_tail())),
+	  _Base(__use_alloc<_Head, _Alloc, _UHead>(__a),
+                std::forward<_UHead>(__in._M_head())) { }
+
       _Tuple_impl&
       operator=(const _Tuple_impl& __in)
       {
@@ -269,6 +381,51 @@ 
         tuple(tuple<_UElements...>&& __in)
         : _Inherited(static_cast<_Tuple_impl<0, _UElements...>&&>(__in)) { }
 
+      // allocator-extended constructors
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a)
+	: _Inherited(__tag, __a) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a,
+	      const _Elements&... __elements)
+	: _Inherited(__tag, __a, __elements...) { }
+
+      template<typename _Alloc, typename... _UElements, typename = typename
+	       std::enable_if<sizeof...(_UElements)
+			      == sizeof...(_Elements)>::type>
+	tuple(allocator_arg_t __tag, const _Alloc& __a,
+	      _UElements&&... __elements)
+	: _Inherited(__tag, __a, std::forward<_UElements>(__elements)...)
+       	{ }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
+	: _Inherited(__tag, __a, static_cast<const _Inherited&>(__in)) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
+	: _Inherited(__tag, __a, static_cast<_Inherited&&>(__in)) { }
+
+      template<typename _Alloc, typename... _UElements, typename = typename
+	       std::enable_if<sizeof...(_UElements)
+			      == sizeof...(_Elements)>::type>
+	tuple(allocator_arg_t __tag, const _Alloc& __a,
+	      const tuple<_UElements...>& __in)
+	: _Inherited(__tag, __a,
+	             static_cast<const _Tuple_impl<0, _UElements...>&>(__in))
+	{ }
+
+      template<typename _Alloc, typename... _UElements, typename = typename
+	       std::enable_if<sizeof...(_UElements)
+			      == sizeof...(_Elements)>::type>
+	tuple(allocator_arg_t __tag, const _Alloc& __a,
+	      tuple<_UElements...>&& __in)
+	: _Inherited(__tag, __a,
+	             static_cast<_Tuple_impl<0, _UElements...>&&>(__in))
+	{ }
+
       tuple&
       operator=(const tuple& __in)
       {
@@ -356,6 +513,52 @@ 
 	: _Inherited(std::forward<_U1>(__in.first),
 		     std::forward<_U2>(__in.second)) { }
 
+      // allocator-extended constructors
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a)
+	: _Inherited(__tag, __a) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a,
+	      const _T1& __a1, const _T2& __a2)
+	: _Inherited(__tag, __a, __a1, __a2) { }
+
+      template<typename _Alloc, typename _U1, typename _U2>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, _U1&& __a1, _U2&& __a2)
+	: _Inherited(__tag, __a, std::forward<_U1>(__a1),
+	             std::forward<_U2>(__a2)) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
+	: _Inherited(__tag, __a, static_cast<const _Inherited&>(__in)) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
+	: _Inherited(__tag, __a, static_cast<_Inherited&&>(__in)) { }
+
+      template<typename _Alloc, typename _U1, typename _U2>
+	tuple(allocator_arg_t __tag, const _Alloc& __a,
+	      const tuple<_U1, _U2>& __in)
+	: _Inherited(__tag, __a,
+	             static_cast<const _Tuple_impl<0, _U1, _U2>&>(__in))
+	{ }
+
+      template<typename _Alloc, typename _U1, typename _U2>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple<_U1, _U2>&& __in)
+	: _Inherited(__tag, __a, static_cast<_Tuple_impl<0, _U1, _U2>&&>(__in))
+	{ }
+
+      template<typename _Alloc, typename _U1, typename _U2>
+        tuple(allocator_arg_t __tag, const _Alloc& __a,
+	      const pair<_U1, _U2>& __in)
+	: _Inherited(__tag, __a, __in.first, __in.second) { }
+
+      template<typename _Alloc, typename _U1, typename _U2>
+        tuple(allocator_arg_t __tag, const _Alloc& __a, pair<_U1, _U2>&& __in)
+	: _Inherited(__tag, __a, std::forward<_U1>(__in.first),
+		     std::forward<_U2>(__in.second)) { }
+
       tuple&
       operator=(const tuple& __in)
       {
@@ -426,7 +629,7 @@ 
       : _Inherited(__a1) { }
 
       template<typename _U1, typename = typename
-	       std::enable_if<std::is_convertible<_U1, _T1>::value>::type>
+	       std::enable_if<std::is_constructible<_T1, _U1&&>::value>::type>
         explicit
         tuple(_U1&& __a1)
 	: _Inherited(std::forward<_U1>(__a1)) { }
@@ -442,6 +645,38 @@ 
         tuple(tuple<_U1>&& __in)
 	: _Inherited(static_cast<_Tuple_impl<0, _U1>&&>(__in)) { }
 
+      // allocator-extended constructors
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a)
+	: _Inherited(__tag, __a) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, const _T1& __a1)
+	: _Inherited(__tag, __a, __a1) { }
+
+      // TODO: constrain for is_uses_allocator_constructible<_T1, _U1&&, _Alloc>
+      template<typename _Alloc, typename _U1>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, _U1&& __a1)
+	: _Inherited(__tag, __a, std::forward<_U1>(__a1)) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
+	: _Inherited(__tag, __a, static_cast<const _Inherited&>(__in)) { }
+
+      template<typename _Alloc>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
+	: _Inherited(__tag, __a, static_cast<_Inherited&&>(__in)) { }
+
+      template<typename _Alloc, typename _U1>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple<_U1>& __in)
+	: _Inherited(__tag, __a, static_cast<const _Tuple_impl<0, _U1>&>(__in))
+       	{ }
+
+      template<typename _Alloc, typename _U1>
+	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple<_U1>&& __in)
+	: _Inherited(__tag, __a, static_cast<_Tuple_impl<0, _U1>&&>(__in)) { }
+
       tuple&
       operator=(const tuple& __in)
       {
@@ -804,6 +1039,10 @@ 
 
   const _Swallow_assign ignore{};
 
+  /// Partial specialization for tuples
+  template<typename... _Types, typename _Alloc>
+    struct uses_allocator<tuple<_Types...>, _Alloc> : true_type { };
+
   /**
    * Stores a tuple of indices. Used by bind() to extract the elements
    * in a tuple. 
Index: include/Makefile.am
===================================================================
--- include/Makefile.am	(revision 174380)
+++ include/Makefile.am	(working copy)
@@ -168,6 +168,7 @@ 
 	${bits_srcdir}/unique_ptr.h \
 	${bits_srcdir}/unordered_map.h \
 	${bits_srcdir}/unordered_set.h \
+	${bits_srcdir}/uses_allocator.h \
 	${bits_srcdir}/valarray_array.h \
 	${bits_srcdir}/valarray_array.tcc \
 	${bits_srcdir}/valarray_before.h \
Index: testsuite/20_util/uses_allocator/cons_neg.cc
===================================================================
--- testsuite/20_util/uses_allocator/cons_neg.cc	(revision 0)
+++ testsuite/20_util/uses_allocator/cons_neg.cc	(revision 0)
@@ -0,0 +1,48 @@ 
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// Copyright (C) 2011 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/>.
+
+// 20.4.2.1 [tuple.cnstr] Allocator-extended constructors
+
+#include <memory>
+#include <tuple>
+
+struct MyAlloc { };
+
+struct Type
+{
+  typedef MyAlloc allocator_type; // uses_allocator<Type, MyAlloc> is true
+
+  explicit Type(int) { }
+
+  Type(std::allocator_arg_t, MyAlloc) { }
+  Type(MyAlloc) { }
+};
+
+void test01()
+{
+  using std::allocator_arg;
+  using std::tuple;
+
+  MyAlloc a;
+
+  tuple<Type> t(allocator_arg, a, 1);
+}
+// { dg-error "no matching function" "" { target *-*-* } 112 }
+// { dg-excess-errors "note" }
Index: testsuite/20_util/uses_allocator/construction.cc
===================================================================
--- testsuite/20_util/uses_allocator/construction.cc	(revision 0)
+++ testsuite/20_util/uses_allocator/construction.cc	(revision 0)
@@ -0,0 +1,108 @@ 
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// 20.6.7.2 uses-allocator construction
+
+#include <memory>
+#include <tuple>
+#include <testsuite_hooks.h>
+
+struct MyAlloc { };
+
+// type that can't be constructed with an allocator
+struct CannotUse
+{
+  CannotUse(int) : ok(true) { }
+
+  bool ok;
+};
+
+// type that can be constructed with an allocator
+// but which has uses_allocator == false
+struct DoesNotUse
+{
+  typedef MyAlloc allocator_type;
+
+  DoesNotUse(int) : ok(true) { }
+  DoesNotUse(std::allocator_arg_t, MyAlloc, int) : ok(false) { }
+  DoesNotUse(int, MyAlloc) : ok(false) { }
+
+  bool ok;
+};
+
+namespace std
+{
+  template<typename A> 
+    struct uses_allocator<DoesNotUse, A> : false_type { };
+}
+
+// type that can be constructed with an allocator as second argument
+struct UsesWithTag
+{
+  typedef MyAlloc allocator_type;
+
+  UsesWithTag(int) : ok(false) { }
+  UsesWithTag(std::allocator_arg_t, MyAlloc, int) : ok(true) { }
+  UsesWithTag(int, MyAlloc) : ok(false) {  }
+
+  bool ok;
+};
+
+// type that can be constructed with an allocator as last argument
+struct UsesWithoutTag
+{
+  typedef MyAlloc allocator_type;
+
+  UsesWithoutTag(int) : ok(false) { }
+  UsesWithoutTag(int, MyAlloc) : ok(true) { }
+
+  bool ok;
+};
+
+
+template<typename TestType, typename... T>
+  bool test2(T... args)
+  {
+    using std::allocator_arg;
+    using std::tuple;
+    using std::get;
+
+    tuple<TestType, T...> t(allocator_arg, MyAlloc(), 1, args...);
+
+    return get<0>(t).ok;
+  }
+
+template<typename... T>
+  void test(T... args)
+  {
+    bool test __attribute__((unused)) = true;
+
+    VERIFY( test2<CannotUse>(args...) );
+    VERIFY( test2<DoesNotUse>(args...) );
+    VERIFY( test2<UsesWithTag>(args...) );
+    VERIFY( test2<UsesWithoutTag>(args...) );
+  }
+
+int main()
+{
+  test();
+  test(1);
+  test(1, 2);
+  return 0;
+}
Index: testsuite/20_util/tuple/cons/allocate_noncopyable.cc
===================================================================
--- testsuite/20_util/tuple/cons/allocate_noncopyable.cc	(revision 0)
+++ testsuite/20_util/tuple/cons/allocate_noncopyable.cc	(revision 0)
@@ -0,0 +1,73 @@ 
+// { dg-options "-std=gnu++0x" }
+// { dg-do compile }
+
+// Copyright (C) 2011 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/>.
+
+// 20.4.2.1 [tuple.cnstr] Allocator-extended constructors
+
+#include <memory>
+#include <tuple>
+
+struct MyAlloc { };
+
+struct Tag0 { };
+struct Tag1 { };
+struct Tag2 { };
+
+// A non-copyable and non-movable type
+struct Type
+{
+  typedef MyAlloc allocator_type;
+
+  explicit Type(Tag0) { }
+  Type(std::allocator_arg_t, MyAlloc, Tag1) { }
+  Type(Tag2, MyAlloc) { }
+
+  Type(const Type&) = delete;
+  Type(Type&&) = delete;
+  Type& operator=(const Type&) = delete;
+  Type& operator=(Type&&) = delete;
+};
+
+void test01()
+{
+  using std::allocator_arg;
+  using std::tuple;
+
+  MyAlloc a;
+  Tag0 tag0;
+  Tag1 tag1;
+  Tag2 tag2;
+
+  // N.B. cannot use Tag0 with uses-allocator construction, because
+  // uses_allocator<Type, MyAlloc> is true but no suitable cosntructor
+  tuple<Type>		  t1(tag0);
+
+  tuple<Type> 		  t2(allocator_arg, a, tag1);
+  tuple<Type> 		  t3(allocator_arg, a, tag2);
+
+  tuple<Type, Type> 	  t4(allocator_arg, a, tag1, tag2);
+
+  tuple<Type, Type, Type> t5(allocator_arg, a, tag2, tag1, tag2);
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/20_util/tuple/cons/allocators.cc
===================================================================
--- testsuite/20_util/tuple/cons/allocators.cc	(revision 0)
+++ testsuite/20_util/tuple/cons/allocators.cc	(revision 0)
@@ -0,0 +1,169 @@ 
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+// 20.4.2.1 [tuple.cnstr] Allocator-extended constructors
+
+#include <memory>
+#include <tuple>
+#include <testsuite_hooks.h>
+
+struct MyAlloc { };
+
+// type that can't be constructed with an allocator
+struct CannotUse
+{
+  CannotUse(int = 0, int = 0) : ok(true) { }
+
+  bool ok;
+};
+
+// type that can be constructed with an allocator
+// but which has uses_allocator == false
+struct DoesNotUse
+{
+  typedef MyAlloc allocator_type;
+
+  DoesNotUse(int = 0) : ok(true) { }
+  DoesNotUse(std::allocator_arg_t, MyAlloc, int = 0) : ok(false) { }
+  DoesNotUse(MyAlloc) : ok(false) { }
+  DoesNotUse(int, MyAlloc) : ok(false) { }
+
+  DoesNotUse(const DoesNotUse&) : ok(true) { }
+  DoesNotUse(std::allocator_arg_t, MyAlloc, const DoesNotUse&) : ok(false) { }
+  DoesNotUse(const DoesNotUse&, MyAlloc) : ok(false) { }
+
+  DoesNotUse(DoesNotUse&&) : ok(true) { }
+  DoesNotUse(std::allocator_arg_t, MyAlloc, DoesNotUse&&) : ok(false) { }
+  DoesNotUse(DoesNotUse&&, MyAlloc) : ok(false) { }
+
+  bool ok;
+};
+
+namespace std
+{
+  template<typename A> 
+    struct uses_allocator<DoesNotUse, A> : false_type { };
+}
+
+// type that can be constructed with an allocator as second argument
+struct UsesWithTag
+{
+  typedef MyAlloc allocator_type;
+
+  UsesWithTag(int = 0) : ok(false) { }
+  UsesWithTag(std::allocator_arg_t, MyAlloc, int = 0) : ok(true) { }
+  UsesWithTag(MyAlloc) : ok(false) {  }
+  UsesWithTag(int, MyAlloc) : ok(false) {  }
+
+  UsesWithTag(const UsesWithTag&) : ok(false) { }
+  UsesWithTag(std::allocator_arg_t, MyAlloc, const UsesWithTag&) : ok(true) { }
+  UsesWithTag(const UsesWithTag&, MyAlloc) : ok(false) {  }
+
+  UsesWithTag(UsesWithTag&&) : ok(false) { }
+  UsesWithTag(std::allocator_arg_t, MyAlloc, UsesWithTag&&) : ok(true) { }
+  UsesWithTag(UsesWithTag&&, MyAlloc) : ok(false) {  }
+
+  bool ok;
+};
+
+// type that can be constructed with an allocator as last argument
+struct UsesWithoutTag
+{
+  typedef MyAlloc allocator_type;
+
+  UsesWithoutTag(int = 0) : ok(false) { }
+  UsesWithoutTag(MyAlloc) : ok(true) { }
+  UsesWithoutTag(int, MyAlloc) : ok(true) { }
+
+  UsesWithoutTag(const UsesWithoutTag&) : ok(false) { }
+  UsesWithoutTag(const UsesWithoutTag&, MyAlloc) : ok(true) { }
+
+  UsesWithoutTag(UsesWithoutTag&&) : ok(false) { }
+  UsesWithoutTag(UsesWithoutTag&&, MyAlloc) : ok(true) { }
+
+  bool ok;
+};
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  using std::allocator_arg;
+  using std::tuple;
+  using std::make_tuple;
+  using std::get;
+
+  typedef CannotUse T1;
+  typedef DoesNotUse T2;
+  typedef UsesWithTag T3;
+  typedef UsesWithoutTag T4;
+  typedef tuple<T1, T2, T3, T4> test_type;
+
+  MyAlloc a;
+
+  // default construction
+  test_type t1(allocator_arg, a);
+  VERIFY( get<0>(t1).ok );
+  VERIFY( get<1>(t1).ok );
+  VERIFY( get<2>(t1).ok );
+  VERIFY( get<3>(t1).ok );
+
+  // copy construction
+  test_type t2(allocator_arg, a, t1);
+  VERIFY( get<0>(t2).ok );
+  VERIFY( get<1>(t2).ok );
+  VERIFY( get<2>(t2).ok );
+  VERIFY( get<3>(t2).ok );
+
+  // move construction
+  test_type t3(allocator_arg, a, std::move(t1));
+  VERIFY( get<0>(t3).ok );
+  VERIFY( get<1>(t3).ok );
+  VERIFY( get<2>(t3).ok );
+  VERIFY( get<3>(t3).ok );
+
+  // construction from int
+  test_type t4(allocator_arg, a, 1, 2, 3, 4);
+  VERIFY( get<0>(t4).ok );
+  VERIFY( get<1>(t4).ok );
+  VERIFY( get<2>(t4).ok );
+  VERIFY( get<3>(t4).ok );
+
+  auto ints = make_tuple(1, 2, 3, 4);
+
+  // construction from lvalue tuple of ints
+  test_type t5(allocator_arg, a, ints);
+  VERIFY( get<0>(t5).ok );
+  VERIFY( get<1>(t5).ok );
+  VERIFY( get<2>(t5).ok );
+  VERIFY( get<3>(t2).ok );
+
+  // construction from rvalue tuple of ints
+  test_type t6(allocator_arg, a, std::move(ints));
+  VERIFY( get<0>(t6).ok );
+  VERIFY( get<1>(t6).ok );
+  VERIFY( get<2>(t6).ok );
+  VERIFY( get<3>(t6).ok );
+
+}
+
+int main()
+{
+  test01();
+  return 0;
+}