1// <tuple> -*- C++ -*-
2
3// Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file include/tuple
26 *  This is a Standard C++ Library header.
27 */
28
29#ifndef _GLIBCXX_TUPLE
30#define _GLIBCXX_TUPLE 1
31
32#pragma GCC system_header
33
34#ifndef __GXX_EXPERIMENTAL_CXX0X__
35# include <bits/c++0x_warning.h>
36#else
37
38#include <utility>
39#include <bits/uses_allocator.h>
40
41namespace std _GLIBCXX_VISIBILITY(default)
42{
43_GLIBCXX_BEGIN_NAMESPACE_VERSION
44
45  // Adds a const reference to a non-reference type.
46  template<typename _Tp>
47    struct __add_c_ref
48    { typedef const _Tp& type; };
49
50  template<typename _Tp>
51    struct __add_c_ref<_Tp&>
52    { typedef _Tp& type; };
53
54  // Adds a reference to a non-reference type.
55  template<typename _Tp>
56    struct __add_ref
57    { typedef _Tp& type; };
58
59  template<typename _Tp>
60    struct __add_ref<_Tp&>
61    { typedef _Tp& type; };
62
63  // Adds an rvalue reference to a non-reference type.
64  template<typename _Tp>
65    struct __add_r_ref
66    { typedef _Tp&& type; };
67
68  template<typename _Tp>
69    struct __add_r_ref<_Tp&>
70    { typedef _Tp& type; };
71
72  template<std::size_t _Idx, typename _Head, bool _IsEmptyNotFinal>
73    struct _Head_base;
74
75  template<std::size_t _Idx, typename _Head>
76    struct _Head_base<_Idx, _Head, true>
77    : public _Head
78    {
79      constexpr _Head_base()
80      : _Head() { }
81
82      constexpr _Head_base(const _Head& __h)
83      : _Head(__h) { }
84
85      template<typename _UHead, typename = typename
86	       enable_if<!is_convertible<_UHead,
87	                                 __uses_alloc_base>::value>::type>
88        constexpr _Head_base(_UHead&& __h)
89	: _Head(std::forward<_UHead>(__h)) { }
90
91      _Head_base(__uses_alloc0)
92      : _Head() { }
93
94      template<typename _Alloc>
95	_Head_base(__uses_alloc1<_Alloc> __a)
96	: _Head(allocator_arg, *__a._M_a) { }
97
98      template<typename _Alloc>
99	_Head_base(__uses_alloc2<_Alloc> __a)
100	: _Head(*__a._M_a) { }
101
102      template<typename _UHead>
103	_Head_base(__uses_alloc0, _UHead&& __uhead)
104	: _Head(std::forward<_UHead>(__uhead)) { }
105
106      template<typename _Alloc, typename _UHead>
107	_Head_base(__uses_alloc1<_Alloc> __a, _UHead&& __uhead)
108	: _Head(allocator_arg, *__a._M_a, std::forward<_UHead>(__uhead)) { }
109
110      template<typename _Alloc, typename _UHead>
111	_Head_base(__uses_alloc2<_Alloc> __a, _UHead&& __uhead)
112	: _Head(std::forward<_UHead>(__uhead), *__a._M_a) { }
113
114      static constexpr _Head&
115      _M_head(_Head_base& __b) noexcept { return __b; }
116
117      static constexpr const _Head&
118      _M_head(const _Head_base& __b) noexcept { return __b; }
119    };
120
121  template<std::size_t _Idx, typename _Head>
122    struct _Head_base<_Idx, _Head, false>
123    {
124      constexpr _Head_base()
125      : _M_head_impl() { }
126
127      constexpr _Head_base(const _Head& __h)
128      : _M_head_impl(__h) { }
129
130      template<typename _UHead, typename = typename
131	       enable_if<!is_convertible<_UHead,
132	                                 __uses_alloc_base>::value>::type>
133        constexpr _Head_base(_UHead&& __h)
134	: _M_head_impl(std::forward<_UHead>(__h)) { }
135
136      _Head_base(__uses_alloc0)
137      : _M_head_impl() { }
138
139      template<typename _Alloc>
140	_Head_base(__uses_alloc1<_Alloc> __a)
141	: _M_head_impl(allocator_arg, *__a._M_a) { }
142
143      template<typename _Alloc>
144	_Head_base(__uses_alloc2<_Alloc> __a)
145	: _M_head_impl(*__a._M_a) { }
146
147      template<typename _UHead>
148	_Head_base(__uses_alloc0, _UHead&& __uhead)
149	: _M_head_impl(std::forward<_UHead>(__uhead)) { }
150
151      template<typename _Alloc, typename _UHead>
152	_Head_base(__uses_alloc1<_Alloc> __a, _UHead&& __uhead)
153	: _M_head_impl(allocator_arg, *__a._M_a, std::forward<_UHead>(__uhead))
154	{ }
155
156      template<typename _Alloc, typename _UHead>
157	_Head_base(__uses_alloc2<_Alloc> __a, _UHead&& __uhead)
158	: _M_head_impl(std::forward<_UHead>(__uhead), *__a._M_a) { }
159
160      static constexpr _Head&
161      _M_head(_Head_base& __b) noexcept { return __b._M_head_impl; }
162
163      static constexpr const _Head&
164      _M_head(const _Head_base& __b) noexcept { return __b._M_head_impl; }
165
166      _Head _M_head_impl;
167    };
168
169  /**
170   * Contains the actual implementation of the @c tuple template, stored
171   * as a recursive inheritance hierarchy from the first element (most
172   * derived class) to the last (least derived class). The @c Idx
173   * parameter gives the 0-based index of the element stored at this
174   * point in the hierarchy; we use it to implement a constant-time
175   * get() operation.
176   */
177  template<std::size_t _Idx, typename... _Elements>
178    struct _Tuple_impl;
179
180  /**
181   * Zero-element tuple implementation. This is the basis case for the
182   * inheritance recursion.
183   */
184  template<std::size_t _Idx>
185    struct _Tuple_impl<_Idx>
186    {
187      template<std::size_t, typename...> friend class _Tuple_impl;
188
189      _Tuple_impl() = default;
190
191      template<typename _Alloc>
192        _Tuple_impl(allocator_arg_t, const _Alloc&) { }
193
194      template<typename _Alloc>
195        _Tuple_impl(allocator_arg_t, const _Alloc&, const _Tuple_impl&) { }
196
197      template<typename _Alloc>
198        _Tuple_impl(allocator_arg_t, const _Alloc&, _Tuple_impl&&) { }
199
200    protected:
201      void _M_swap(_Tuple_impl&) noexcept { /* no-op */ }
202    };
203
204  // Use the Empty Base-class Optimization for empty, non-final types.
205  template<typename _Tp>
206    using __empty_not_final
207      = typename conditional<__is_final(_Tp), false_type, is_empty<_Tp>>::type;
208
209  /**
210   * Recursive tuple implementation. Here we store the @c Head element
211   * and derive from a @c Tuple_impl containing the remaining elements
212   * (which contains the @c Tail).
213   */
214  template<std::size_t _Idx, typename _Head, typename... _Tail>
215    struct _Tuple_impl<_Idx, _Head, _Tail...>
216    : public _Tuple_impl<_Idx + 1, _Tail...>,
217      private _Head_base<_Idx, _Head, __empty_not_final<_Head>::value>
218    {
219      template<std::size_t, typename...> friend class _Tuple_impl;
220
221      typedef _Tuple_impl<_Idx + 1, _Tail...> _Inherited;
222      typedef _Head_base<_Idx, _Head, __empty_not_final<_Head>::value> _Base;
223
224      static constexpr _Head&
225      _M_head(_Tuple_impl& __t) noexcept { return _Base::_M_head(__t); }
226
227      static constexpr const _Head&
228      _M_head(const _Tuple_impl& __t) noexcept { return _Base::_M_head(__t); }
229
230      static constexpr _Inherited&
231      _M_tail(_Tuple_impl& __t) noexcept { return __t; }
232
233      static constexpr const _Inherited&
234      _M_tail(const _Tuple_impl& __t) noexcept { return __t; }
235
236      constexpr _Tuple_impl()
237      : _Inherited(), _Base() { }
238
239      explicit
240      constexpr _Tuple_impl(const _Head& __head, const _Tail&... __tail)
241      : _Inherited(__tail...), _Base(__head) { }
242
243      template<typename _UHead, typename... _UTail, typename = typename
244               enable_if<sizeof...(_Tail) == sizeof...(_UTail)>::type>
245        explicit
246        constexpr _Tuple_impl(_UHead&& __head, _UTail&&... __tail)
247	: _Inherited(std::forward<_UTail>(__tail)...),
248	  _Base(std::forward<_UHead>(__head)) { }
249
250      constexpr _Tuple_impl(const _Tuple_impl&) = default;
251
252      constexpr
253      _Tuple_impl(_Tuple_impl&& __in)
254      noexcept(__and_<is_nothrow_move_constructible<_Head>,
255	              is_nothrow_move_constructible<_Inherited>>::value)
256      : _Inherited(std::move(_M_tail(__in))),
257	_Base(std::forward<_Head>(_M_head(__in))) { }
258
259      template<typename... _UElements>
260        constexpr _Tuple_impl(const _Tuple_impl<_Idx, _UElements...>& __in)
261	: _Inherited(_Tuple_impl<_Idx, _UElements...>::_M_tail(__in)),
262	  _Base(_Tuple_impl<_Idx, _UElements...>::_M_head(__in)) { }
263
264      template<typename _UHead, typename... _UTails>
265        constexpr _Tuple_impl(_Tuple_impl<_Idx, _UHead, _UTails...>&& __in)
266	: _Inherited(std::move
267		     (_Tuple_impl<_Idx, _UHead, _UTails...>::_M_tail(__in))),
268	  _Base(std::forward<_UHead>
269		(_Tuple_impl<_Idx, _UHead, _UTails...>::_M_head(__in))) { }
270
271      template<typename _Alloc>
272	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a)
273	: _Inherited(__tag, __a),
274          _Base(__use_alloc<_Head>(__a)) { }
275
276      template<typename _Alloc>
277	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
278		    const _Head& __head, const _Tail&... __tail)
279	: _Inherited(__tag, __a, __tail...),
280          _Base(__use_alloc<_Head, _Alloc, _Head>(__a), __head) { }
281
282      template<typename _Alloc, typename _UHead, typename... _UTail,
283               typename = typename enable_if<sizeof...(_Tail)
284					     == sizeof...(_UTail)>::type>
285	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
286	            _UHead&& __head, _UTail&&... __tail)
287	: _Inherited(__tag, __a, std::forward<_UTail>(__tail)...),
288          _Base(__use_alloc<_Head, _Alloc, _UHead>(__a),
289	        std::forward<_UHead>(__head)) { }
290
291      template<typename _Alloc>
292        _Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
293	            const _Tuple_impl& __in)
294	: _Inherited(__tag, __a, _M_tail(__in)),
295          _Base(__use_alloc<_Head, _Alloc, _Head>(__a), _M_head(__in)) { }
296
297      template<typename _Alloc>
298	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
299	            _Tuple_impl&& __in)
300	: _Inherited(__tag, __a, std::move(_M_tail(__in))),
301	  _Base(__use_alloc<_Head, _Alloc, _Head>(__a),
302	        std::forward<_Head>(_M_head(__in))) { }
303
304      template<typename _Alloc, typename... _UElements>
305	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
306	            const _Tuple_impl<_Idx, _UElements...>& __in)
307	: _Inherited(__tag, __a,
308		     _Tuple_impl<_Idx, _UElements...>::_M_tail(__in)),
309	  _Base(__use_alloc<_Head, _Alloc, _Head>(__a),
310		_Tuple_impl<_Idx, _UElements...>::_M_head(__in)) { }
311
312      template<typename _Alloc, typename _UHead, typename... _UTails>
313	_Tuple_impl(allocator_arg_t __tag, const _Alloc& __a,
314	            _Tuple_impl<_Idx, _UHead, _UTails...>&& __in)
315	: _Inherited(__tag, __a, std::move
316		     (_Tuple_impl<_Idx, _UHead, _UTails...>::_M_tail(__in))),
317	  _Base(__use_alloc<_Head, _Alloc, _UHead>(__a),
318                std::forward<_UHead>
319		(_Tuple_impl<_Idx, _UHead, _UTails...>::_M_head(__in))) { }
320
321      _Tuple_impl&
322      operator=(const _Tuple_impl& __in)
323      {
324	_M_head(*this) = _M_head(__in);
325	_M_tail(*this) = _M_tail(__in);
326	return *this;
327      }
328
329      _Tuple_impl&
330      operator=(_Tuple_impl&& __in)
331      noexcept(__and_<is_nothrow_move_assignable<_Head>,
332	              is_nothrow_move_assignable<_Inherited>>::value)
333      {
334	_M_head(*this) = std::forward<_Head>(_M_head(__in));
335	_M_tail(*this) = std::move(_M_tail(__in));
336	return *this;
337      }
338
339      template<typename... _UElements>
340        _Tuple_impl&
341        operator=(const _Tuple_impl<_Idx, _UElements...>& __in)
342        {
343	  _M_head(*this) = _Tuple_impl<_Idx, _UElements...>::_M_head(__in);
344	  _M_tail(*this) = _Tuple_impl<_Idx, _UElements...>::_M_tail(__in);
345	  return *this;
346	}
347
348      template<typename _UHead, typename... _UTails>
349        _Tuple_impl&
350        operator=(_Tuple_impl<_Idx, _UHead, _UTails...>&& __in)
351        {
352	  _M_head(*this) = std::forward<_UHead>
353	    (_Tuple_impl<_Idx, _UHead, _UTails...>::_M_head(__in));
354	  _M_tail(*this) = std::move
355	    (_Tuple_impl<_Idx, _UHead, _UTails...>::_M_tail(__in));
356	  return *this;
357	}
358
359    protected:
360      void
361      _M_swap(_Tuple_impl& __in)
362      noexcept(noexcept(swap(std::declval<_Head&>(),
363			     std::declval<_Head&>()))
364	       && noexcept(_M_tail(__in)._M_swap(_M_tail(__in))))
365      {
366	using std::swap;
367	swap(_M_head(*this), _M_head(__in));
368	_Inherited::_M_swap(_M_tail(__in));
369      }
370    };
371
372  /// Primary class template, tuple
373  template<typename... _Elements>
374    class tuple : public _Tuple_impl<0, _Elements...>
375    {
376      typedef _Tuple_impl<0, _Elements...> _Inherited;
377
378    public:
379      constexpr tuple()
380      : _Inherited() { }
381
382      explicit
383      constexpr tuple(const _Elements&... __elements)
384      : _Inherited(__elements...) { }
385
386      template<typename... _UElements, typename = typename
387        enable_if<__and_<is_convertible<_UElements,
388					_Elements>...>::value>::type>
389	explicit
390        constexpr tuple(_UElements&&... __elements)
391	: _Inherited(std::forward<_UElements>(__elements)...) {	}
392
393      constexpr tuple(const tuple&) = default;
394
395      constexpr tuple(tuple&&) = default;
396
397      template<typename... _UElements, typename = typename
398        enable_if<__and_<is_convertible<const _UElements&,
399					_Elements>...>::value>::type>
400        constexpr tuple(const tuple<_UElements...>& __in)
401        : _Inherited(static_cast<const _Tuple_impl<0, _UElements...>&>(__in))
402        { }
403
404      template<typename... _UElements, typename = typename
405        enable_if<__and_<is_convertible<_UElements,
406					_Elements>...>::value>::type>
407        constexpr tuple(tuple<_UElements...>&& __in)
408        : _Inherited(static_cast<_Tuple_impl<0, _UElements...>&&>(__in)) { }
409
410      // Allocator-extended constructors.
411
412      template<typename _Alloc>
413	tuple(allocator_arg_t __tag, const _Alloc& __a)
414	: _Inherited(__tag, __a) { }
415
416      template<typename _Alloc>
417	tuple(allocator_arg_t __tag, const _Alloc& __a,
418	      const _Elements&... __elements)
419	: _Inherited(__tag, __a, __elements...) { }
420
421      template<typename _Alloc, typename... _UElements, typename = typename
422	       enable_if<sizeof...(_UElements)
423			 == sizeof...(_Elements)>::type>
424	tuple(allocator_arg_t __tag, const _Alloc& __a,
425	      _UElements&&... __elements)
426	: _Inherited(__tag, __a, std::forward<_UElements>(__elements)...)
427       	{ }
428
429      template<typename _Alloc>
430	tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
431	: _Inherited(__tag, __a, static_cast<const _Inherited&>(__in)) { }
432
433      template<typename _Alloc>
434	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
435	: _Inherited(__tag, __a, static_cast<_Inherited&&>(__in)) { }
436
437      template<typename _Alloc, typename... _UElements, typename = typename
438	       enable_if<sizeof...(_UElements)
439			 == sizeof...(_Elements)>::type>
440	tuple(allocator_arg_t __tag, const _Alloc& __a,
441	      const tuple<_UElements...>& __in)
442	: _Inherited(__tag, __a,
443	             static_cast<const _Tuple_impl<0, _UElements...>&>(__in))
444	{ }
445
446      template<typename _Alloc, typename... _UElements, typename = typename
447	       enable_if<sizeof...(_UElements)
448			 == sizeof...(_Elements)>::type>
449	tuple(allocator_arg_t __tag, const _Alloc& __a,
450	      tuple<_UElements...>&& __in)
451	: _Inherited(__tag, __a,
452	             static_cast<_Tuple_impl<0, _UElements...>&&>(__in))
453	{ }
454
455      tuple&
456      operator=(const tuple& __in)
457      {
458	static_cast<_Inherited&>(*this) = __in;
459	return *this;
460      }
461
462      tuple&
463      operator=(tuple&& __in)
464      noexcept(is_nothrow_move_assignable<_Inherited>::value)
465      {
466	static_cast<_Inherited&>(*this) = std::move(__in);
467	return *this;
468      }
469
470      template<typename... _UElements, typename = typename
471	       enable_if<sizeof...(_UElements)
472			 == sizeof...(_Elements)>::type>
473        tuple&
474        operator=(const tuple<_UElements...>& __in)
475        {
476	  static_cast<_Inherited&>(*this) = __in;
477	  return *this;
478	}
479
480      template<typename... _UElements, typename = typename
481	       enable_if<sizeof...(_UElements)
482			 == sizeof...(_Elements)>::type>
483        tuple&
484        operator=(tuple<_UElements...>&& __in)
485        {
486	  static_cast<_Inherited&>(*this) = std::move(__in);
487	  return *this;
488	}
489
490      void
491      swap(tuple& __in)
492      noexcept(noexcept(__in._M_swap(__in)))
493      { _Inherited::_M_swap(__in); }
494    };
495
496  // Explicit specialization, zero-element tuple.
497  template<>
498    class tuple<>
499    {
500    public:
501      void swap(tuple&) noexcept { /* no-op */ }
502    };
503
504  /// Partial specialization, 2-element tuple.
505  /// Includes construction and assignment from a pair.
506  template<typename _T1, typename _T2>
507    class tuple<_T1, _T2> : public _Tuple_impl<0, _T1, _T2>
508    {
509      typedef _Tuple_impl<0, _T1, _T2> _Inherited;
510
511    public:
512      constexpr tuple()
513      : _Inherited() { }
514
515      explicit
516      constexpr tuple(const _T1& __a1, const _T2& __a2)
517      : _Inherited(__a1, __a2) { }
518
519      template<typename _U1, typename _U2, typename = typename
520	       enable_if<__and_<is_convertible<_U1, _T1>,
521				is_convertible<_U2, _T2>>::value>::type>
522        explicit
523        constexpr tuple(_U1&& __a1, _U2&& __a2)
524	: _Inherited(std::forward<_U1>(__a1), std::forward<_U2>(__a2)) { }
525
526      constexpr tuple(const tuple&) = default;
527
528      constexpr tuple(tuple&&) = default;
529
530      template<typename _U1, typename _U2, typename = typename
531	enable_if<__and_<is_convertible<const _U1&, _T1>,
532			 is_convertible<const _U2&, _T2>>::value>::type>
533        constexpr tuple(const tuple<_U1, _U2>& __in)
534	: _Inherited(static_cast<const _Tuple_impl<0, _U1, _U2>&>(__in)) { }
535
536      template<typename _U1, typename _U2, typename = typename
537	       enable_if<__and_<is_convertible<_U1, _T1>,
538				is_convertible<_U2, _T2>>::value>::type>
539        constexpr tuple(tuple<_U1, _U2>&& __in)
540	: _Inherited(static_cast<_Tuple_impl<0, _U1, _U2>&&>(__in)) { }
541
542      template<typename _U1, typename _U2, typename = typename
543	enable_if<__and_<is_convertible<const _U1&, _T1>,
544			 is_convertible<const _U2&, _T2>>::value>::type>
545        constexpr tuple(const pair<_U1, _U2>& __in)
546	: _Inherited(__in.first, __in.second) { }
547
548      template<typename _U1, typename _U2, typename = typename
549	       enable_if<__and_<is_convertible<_U1, _T1>,
550				is_convertible<_U2, _T2>>::value>::type>
551        constexpr tuple(pair<_U1, _U2>&& __in)
552	: _Inherited(std::forward<_U1>(__in.first),
553		     std::forward<_U2>(__in.second)) { }
554
555      // Allocator-extended constructors.
556
557      template<typename _Alloc>
558	tuple(allocator_arg_t __tag, const _Alloc& __a)
559	: _Inherited(__tag, __a) { }
560
561      template<typename _Alloc>
562	tuple(allocator_arg_t __tag, const _Alloc& __a,
563	      const _T1& __a1, const _T2& __a2)
564	: _Inherited(__tag, __a, __a1, __a2) { }
565
566      template<typename _Alloc, typename _U1, typename _U2>
567	tuple(allocator_arg_t __tag, const _Alloc& __a, _U1&& __a1, _U2&& __a2)
568	: _Inherited(__tag, __a, std::forward<_U1>(__a1),
569	             std::forward<_U2>(__a2)) { }
570
571      template<typename _Alloc>
572	tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
573	: _Inherited(__tag, __a, static_cast<const _Inherited&>(__in)) { }
574
575      template<typename _Alloc>
576	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
577	: _Inherited(__tag, __a, static_cast<_Inherited&&>(__in)) { }
578
579      template<typename _Alloc, typename _U1, typename _U2>
580	tuple(allocator_arg_t __tag, const _Alloc& __a,
581	      const tuple<_U1, _U2>& __in)
582	: _Inherited(__tag, __a,
583	             static_cast<const _Tuple_impl<0, _U1, _U2>&>(__in))
584	{ }
585
586      template<typename _Alloc, typename _U1, typename _U2>
587	tuple(allocator_arg_t __tag, const _Alloc& __a, tuple<_U1, _U2>&& __in)
588	: _Inherited(__tag, __a, static_cast<_Tuple_impl<0, _U1, _U2>&&>(__in))
589	{ }
590
591      template<typename _Alloc, typename _U1, typename _U2>
592        tuple(allocator_arg_t __tag, const _Alloc& __a,
593	      const pair<_U1, _U2>& __in)
594	: _Inherited(__tag, __a, __in.first, __in.second) { }
595
596      template<typename _Alloc, typename _U1, typename _U2>
597        tuple(allocator_arg_t __tag, const _Alloc& __a, pair<_U1, _U2>&& __in)
598	: _Inherited(__tag, __a, std::forward<_U1>(__in.first),
599		     std::forward<_U2>(__in.second)) { }
600
601      tuple&
602      operator=(const tuple& __in)
603      {
604	static_cast<_Inherited&>(*this) = __in;
605	return *this;
606      }
607
608      tuple&
609      operator=(tuple&& __in)
610      noexcept(is_nothrow_move_assignable<_Inherited>::value)
611      {
612	static_cast<_Inherited&>(*this) = std::move(__in);
613	return *this;
614      }
615
616      template<typename _U1, typename _U2>
617        tuple&
618        operator=(const tuple<_U1, _U2>& __in)
619        {
620	  static_cast<_Inherited&>(*this) = __in;
621	  return *this;
622	}
623
624      template<typename _U1, typename _U2>
625        tuple&
626        operator=(tuple<_U1, _U2>&& __in)
627        {
628	  static_cast<_Inherited&>(*this) = std::move(__in);
629	  return *this;
630	}
631
632      template<typename _U1, typename _U2>
633        tuple&
634        operator=(const pair<_U1, _U2>& __in)
635        {
636	  this->_M_head(*this) = __in.first;
637	  this->_M_tail(*this)._M_head(*this) = __in.second;
638	  return *this;
639	}
640
641      template<typename _U1, typename _U2>
642        tuple&
643        operator=(pair<_U1, _U2>&& __in)
644        {
645	  this->_M_head(*this) = std::forward<_U1>(__in.first);
646	  this->_M_tail(*this)._M_head(*this) = std::forward<_U2>(__in.second);
647	  return *this;
648	}
649
650      void
651      swap(tuple& __in)
652      noexcept(noexcept(__in._M_swap(__in)))
653      { _Inherited::_M_swap(__in); }
654    };
655
656
657  /// Gives the type of the ith element of a given tuple type.
658  template<std::size_t __i, typename _Tp>
659    struct tuple_element;
660
661  /**
662   * Recursive case for tuple_element: strip off the first element in
663   * the tuple and retrieve the (i-1)th element of the remaining tuple.
664   */
665  template<std::size_t __i, typename _Head, typename... _Tail>
666    struct tuple_element<__i, tuple<_Head, _Tail...> >
667    : tuple_element<__i - 1, tuple<_Tail...> > { };
668
669  /**
670   * Basis case for tuple_element: The first element is the one we're seeking.
671   */
672  template<typename _Head, typename... _Tail>
673    struct tuple_element<0, tuple<_Head, _Tail...> >
674    {
675      typedef _Head type;
676    };
677
678  template<std::size_t __i, typename _Tp>
679    struct tuple_element<__i, const _Tp>
680    {
681      typedef typename
682      add_const<typename tuple_element<__i, _Tp>::type>::type type;
683    };
684
685  template<std::size_t __i, typename _Tp>
686    struct tuple_element<__i, volatile _Tp>
687    {
688      typedef typename
689      add_volatile<typename tuple_element<__i, _Tp>::type>::type type;
690    };
691
692  template<std::size_t __i, typename _Tp>
693    struct tuple_element<__i, const volatile _Tp>
694    {
695      typedef typename
696      add_cv<typename tuple_element<__i, _Tp>::type>::type type;
697    };
698
699  /// Finds the size of a given tuple type.
700  template<typename _Tp>
701    struct tuple_size;
702
703  template<typename _Tp>
704    struct tuple_size<const _Tp>
705    : public integral_constant<
706             typename remove_cv<decltype(tuple_size<_Tp>::value)>::type,
707             tuple_size<_Tp>::value> { };
708
709  template<typename _Tp>
710    struct tuple_size<volatile _Tp>
711    : public integral_constant<
712             typename remove_cv<decltype(tuple_size<_Tp>::value)>::type,
713             tuple_size<_Tp>::value> { };
714
715  template<typename _Tp>
716    struct tuple_size<const volatile _Tp>
717    : public integral_constant<
718             typename remove_cv<decltype(tuple_size<_Tp>::value)>::type,
719             tuple_size<_Tp>::value> { };
720
721  /// class tuple_size
722  template<typename... _Elements>
723    struct tuple_size<tuple<_Elements...>>
724    : public integral_constant<std::size_t, sizeof...(_Elements)> { };
725
726  template<std::size_t __i, typename _Head, typename... _Tail>
727    constexpr typename __add_ref<_Head>::type
728    __get_helper(_Tuple_impl<__i, _Head, _Tail...>& __t) noexcept
729    { return _Tuple_impl<__i, _Head, _Tail...>::_M_head(__t); }
730
731  template<std::size_t __i, typename _Head, typename... _Tail>
732    constexpr typename __add_c_ref<_Head>::type
733    __get_helper(const _Tuple_impl<__i, _Head, _Tail...>& __t) noexcept
734    { return _Tuple_impl<__i, _Head, _Tail...>::_M_head(__t); }
735
736  // Return a reference (const reference, rvalue reference) to the ith element
737  // of a tuple.  Any const or non-const ref elements are returned with their
738  // original type.
739  template<std::size_t __i, typename... _Elements>
740    constexpr typename __add_ref<
741                      typename tuple_element<__i, tuple<_Elements...>>::type
742                    >::type
743    get(tuple<_Elements...>& __t) noexcept
744    { return __get_helper<__i>(__t); }
745
746  template<std::size_t __i, typename... _Elements>
747    constexpr typename __add_c_ref<
748                      typename tuple_element<__i, tuple<_Elements...>>::type
749                    >::type
750    get(const tuple<_Elements...>& __t) noexcept
751    { return __get_helper<__i>(__t); }
752
753  template<std::size_t __i, typename... _Elements>
754    constexpr typename __add_r_ref<
755                      typename tuple_element<__i, tuple<_Elements...>>::type
756                    >::type
757    get(tuple<_Elements...>&& __t) noexcept
758    { return std::forward<typename tuple_element<__i,
759	tuple<_Elements...>>::type&&>(get<__i>(__t)); }
760
761  // This class helps construct the various comparison operations on tuples
762  template<std::size_t __check_equal_size, std::size_t __i, std::size_t __j,
763	   typename _Tp, typename _Up>
764    struct __tuple_compare;
765
766  template<std::size_t __i, std::size_t __j, typename _Tp, typename _Up>
767    struct __tuple_compare<0, __i, __j, _Tp, _Up>
768    {
769      static bool
770      __eq(const _Tp& __t, const _Up& __u)
771      {
772	return (get<__i>(__t) == get<__i>(__u) &&
773		__tuple_compare<0, __i + 1, __j, _Tp, _Up>::__eq(__t, __u));
774      }
775
776      static bool
777      __less(const _Tp& __t, const _Up& __u)
778      {
779	return ((get<__i>(__t) < get<__i>(__u))
780		|| !(get<__i>(__u) < get<__i>(__t)) &&
781		__tuple_compare<0, __i + 1, __j, _Tp, _Up>::__less(__t, __u));
782      }
783    };
784
785  template<std::size_t __i, typename _Tp, typename _Up>
786    struct __tuple_compare<0, __i, __i, _Tp, _Up>
787    {
788      static bool
789      __eq(const _Tp&, const _Up&) { return true; }
790
791      static bool
792      __less(const _Tp&, const _Up&) { return false; }
793    };
794
795  template<typename... _TElements, typename... _UElements>
796    bool
797    operator==(const tuple<_TElements...>& __t,
798	       const tuple<_UElements...>& __u)
799    {
800      typedef tuple<_TElements...> _Tp;
801      typedef tuple<_UElements...> _Up;
802      return (__tuple_compare<tuple_size<_Tp>::value - tuple_size<_Up>::value,
803	      0, tuple_size<_Tp>::value, _Tp, _Up>::__eq(__t, __u));
804    }
805
806  template<typename... _TElements, typename... _UElements>
807    bool
808    operator<(const tuple<_TElements...>& __t,
809	      const tuple<_UElements...>& __u)
810    {
811      typedef tuple<_TElements...> _Tp;
812      typedef tuple<_UElements...> _Up;
813      return (__tuple_compare<tuple_size<_Tp>::value - tuple_size<_Up>::value,
814	      0, tuple_size<_Tp>::value, _Tp, _Up>::__less(__t, __u));
815    }
816
817  template<typename... _TElements, typename... _UElements>
818    inline bool
819    operator!=(const tuple<_TElements...>& __t,
820	       const tuple<_UElements...>& __u)
821    { return !(__t == __u); }
822
823  template<typename... _TElements, typename... _UElements>
824    inline bool
825    operator>(const tuple<_TElements...>& __t,
826	      const tuple<_UElements...>& __u)
827    { return __u < __t; }
828
829  template<typename... _TElements, typename... _UElements>
830    inline bool
831    operator<=(const tuple<_TElements...>& __t,
832	       const tuple<_UElements...>& __u)
833    { return !(__u < __t); }
834
835  template<typename... _TElements, typename... _UElements>
836    inline bool
837    operator>=(const tuple<_TElements...>& __t,
838	       const tuple<_UElements...>& __u)
839    { return !(__t < __u); }
840
841  // NB: DR 705.
842  template<typename... _Elements>
843    constexpr tuple<typename __decay_and_strip<_Elements>::__type...>
844    make_tuple(_Elements&&... __args)
845    {
846      typedef tuple<typename __decay_and_strip<_Elements>::__type...>
847	__result_type;
848      return __result_type(std::forward<_Elements>(__args)...);
849    }
850
851  template<typename... _Elements>
852    constexpr tuple<_Elements&&...>
853    forward_as_tuple(_Elements&&... __args) noexcept
854    { return tuple<_Elements&&...>(std::forward<_Elements>(__args)...); }
855
856
857  template<typename, std::size_t> struct array;
858
859  template<std::size_t _Int, typename _Tp, std::size_t _Nm>
860    constexpr _Tp& get(array<_Tp, _Nm>&) noexcept;
861
862  template<std::size_t _Int, typename _Tp, std::size_t _Nm>
863    constexpr _Tp&& get(array<_Tp, _Nm>&&) noexcept;
864
865  template<std::size_t _Int, typename _Tp, std::size_t _Nm>
866    constexpr const _Tp& get(const array<_Tp, _Nm>&) noexcept;
867
868  template<typename>
869    struct __is_tuple_like_impl : false_type
870    { };
871
872  template<typename... _Tps>
873    struct __is_tuple_like_impl<tuple<_Tps...>> : true_type
874    { };
875
876  template<typename _T1, typename _T2>
877    struct __is_tuple_like_impl<pair<_T1, _T2>> : true_type
878    { };
879
880  template<typename _Tp, std::size_t _Nm>
881    struct __is_tuple_like_impl<array<_Tp, _Nm>> : true_type
882    { };
883
884  // Internal type trait that allows us to sfinae-protect tuple_cat.
885  template<typename _Tp>
886    struct __is_tuple_like
887    : public __is_tuple_like_impl<typename std::remove_cv
888            <typename std::remove_reference<_Tp>::type>::type>::type
889    { };
890
891  // Stores a tuple of indices.  Also used by bind() to extract the elements
892  // in a tuple.
893  template<std::size_t... _Indexes>
894    struct _Index_tuple
895    {
896      typedef _Index_tuple<_Indexes..., sizeof...(_Indexes)> __next;
897    };
898
899  // Builds an _Index_tuple<0, 1, 2, ..., _Num-1>.
900  template<std::size_t _Num>
901    struct _Build_index_tuple
902    {
903      typedef typename _Build_index_tuple<_Num - 1>::__type::__next __type;
904    };
905
906  template<>
907    struct _Build_index_tuple<0>
908    {
909      typedef _Index_tuple<> __type;
910    };
911
912  template<std::size_t, typename, typename, std::size_t>
913    struct __make_tuple_impl;
914
915  template<std::size_t _Idx, typename _Tuple, typename... _Tp,
916           std::size_t _Nm>
917    struct __make_tuple_impl<_Idx, tuple<_Tp...>, _Tuple, _Nm>
918    {
919      typedef typename __make_tuple_impl<_Idx + 1, tuple<_Tp...,
920	typename std::tuple_element<_Idx, _Tuple>::type>, _Tuple, _Nm>::__type
921      __type;
922    };
923
924  template<std::size_t _Nm, typename _Tuple, typename... _Tp>
925    struct __make_tuple_impl<_Nm, tuple<_Tp...>, _Tuple, _Nm>
926    {
927      typedef tuple<_Tp...> __type;
928    };
929
930  template<typename _Tuple>
931    struct __do_make_tuple
932    : public __make_tuple_impl<0, tuple<>, _Tuple,
933                               std::tuple_size<_Tuple>::value>
934    { };
935
936  // Returns the std::tuple equivalent of a tuple-like type.
937  template<typename _Tuple>
938    struct __make_tuple
939    : public __do_make_tuple<typename std::remove_cv
940            <typename std::remove_reference<_Tuple>::type>::type>
941    { };
942
943  // Combines several std::tuple's into a single one.
944  template<typename...>
945    struct __combine_tuples;
946
947  template<>
948    struct __combine_tuples<>
949    {
950      typedef tuple<> __type;
951    };
952
953  template<typename... _Ts>
954    struct __combine_tuples<tuple<_Ts...>>
955    {
956      typedef tuple<_Ts...> __type;
957    };
958
959  template<typename... _T1s, typename... _T2s, typename... _Rem>
960    struct __combine_tuples<tuple<_T1s...>, tuple<_T2s...>, _Rem...>
961    {
962      typedef typename __combine_tuples<tuple<_T1s..., _T2s...>,
963					_Rem...>::__type __type;
964    };
965
966  // Computes the result type of tuple_cat given a set of tuple-like types.
967  template<typename... _Tpls>
968    struct __tuple_cat_result
969    {
970      typedef typename __combine_tuples
971        <typename __make_tuple<_Tpls>::__type...>::__type __type;
972    };
973
974  // Helper to determine the index set for the first tuple-like
975  // type of a given set.
976  template<typename...>
977    struct __make_1st_indices;
978
979  template<>
980    struct __make_1st_indices<>
981    {
982      typedef std::_Index_tuple<> __type;
983    };
984
985  template<typename _Tp, typename... _Tpls>
986    struct __make_1st_indices<_Tp, _Tpls...>
987    {
988      typedef typename std::_Build_index_tuple<std::tuple_size<
989	typename std::remove_reference<_Tp>::type>::value>::__type __type;
990    };
991
992  // Performs the actual concatenation by step-wise expanding tuple-like
993  // objects into the elements,  which are finally forwarded into the
994  // result tuple.
995  template<typename _Ret, typename _Indices, typename... _Tpls>
996    struct __tuple_concater;
997
998  template<typename _Ret, std::size_t... _Is, typename _Tp, typename... _Tpls>
999    struct __tuple_concater<_Ret, std::_Index_tuple<_Is...>, _Tp, _Tpls...>
1000    {
1001      template<typename... _Us>
1002        static constexpr _Ret
1003        _S_do(_Tp&& __tp, _Tpls&&... __tps, _Us&&... __us)
1004        {
1005	  typedef typename __make_1st_indices<_Tpls...>::__type __idx;
1006	  typedef __tuple_concater<_Ret, __idx, _Tpls...>      __next;
1007	  return __next::_S_do(std::forward<_Tpls>(__tps)...,
1008			       std::forward<_Us>(__us)...,
1009			       std::get<_Is>(std::forward<_Tp>(__tp))...);
1010	}
1011    };
1012
1013  template<typename _Ret>
1014    struct __tuple_concater<_Ret, std::_Index_tuple<>>
1015    {
1016      template<typename... _Us>
1017	static constexpr _Ret
1018	_S_do(_Us&&... __us)
1019        {
1020	  return _Ret(std::forward<_Us>(__us)...);
1021	}
1022    };
1023
1024  template<typename... _Tpls, typename = typename
1025           enable_if<__and_<__is_tuple_like<_Tpls>...>::value>::type>
1026    constexpr auto
1027    tuple_cat(_Tpls&&... __tpls)
1028    -> typename __tuple_cat_result<_Tpls...>::__type
1029    {
1030      typedef typename __tuple_cat_result<_Tpls...>::__type __ret;
1031      typedef typename __make_1st_indices<_Tpls...>::__type __idx;
1032      typedef __tuple_concater<__ret, __idx, _Tpls...> __concater;
1033      return __concater::_S_do(std::forward<_Tpls>(__tpls)...);
1034    }
1035
1036  template<typename... _Elements>
1037    inline tuple<_Elements&...>
1038    tie(_Elements&... __args) noexcept
1039    { return tuple<_Elements&...>(__args...); }
1040
1041  template<typename... _Elements>
1042    inline void
1043    swap(tuple<_Elements...>& __x, tuple<_Elements...>& __y)
1044    noexcept(noexcept(__x.swap(__y)))
1045    { __x.swap(__y); }
1046
1047  // A class (and instance) which can be used in 'tie' when an element
1048  // of a tuple is not required
1049  struct _Swallow_assign
1050  {
1051    template<class _Tp>
1052      const _Swallow_assign&
1053      operator=(const _Tp&) const
1054      { return *this; }
1055  };
1056
1057  const _Swallow_assign ignore{};
1058
1059  /// Partial specialization for tuples
1060  template<typename... _Types, typename _Alloc>
1061    struct uses_allocator<tuple<_Types...>, _Alloc> : true_type { };
1062
1063  // See stl_pair.h...
1064  template<class _T1, class _T2>
1065    template<typename... _Args1, typename... _Args2>
1066      inline
1067      pair<_T1, _T2>::
1068      pair(piecewise_construct_t,
1069	   tuple<_Args1...> __first, tuple<_Args2...> __second)
1070      : pair(__first, __second,
1071	     typename _Build_index_tuple<sizeof...(_Args1)>::__type(),
1072	     typename _Build_index_tuple<sizeof...(_Args2)>::__type())
1073      { }
1074
1075  template<class _T1, class _T2>
1076    template<typename... _Args1, std::size_t... _Indexes1,
1077             typename... _Args2, std::size_t... _Indexes2>
1078      inline
1079      pair<_T1, _T2>::
1080      pair(tuple<_Args1...>& __tuple1, tuple<_Args2...>& __tuple2,
1081	   _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>)
1082      : first(std::forward<_Args1>(std::get<_Indexes1>(__tuple1))...),
1083        second(std::forward<_Args2>(std::get<_Indexes2>(__tuple2))...)
1084      { }
1085
1086_GLIBCXX_END_NAMESPACE_VERSION
1087} // namespace
1088
1089#endif // __GXX_EXPERIMENTAL_CXX0X__
1090
1091#endif // _GLIBCXX_TUPLE
1092