1// -*- C++ -*-
2//===-------------------------- utility -----------------------------------===//
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_UTILITY
12#define _LIBCPP_UTILITY
13
14/*
15    utility synopsis
16
17namespace std
18{
19
20template <class T>
21    void
22    swap(T& a, T& b);
23
24namespace rel_ops
25{
26    template<class T> bool operator!=(const T&, const T&);
27    template<class T> bool operator> (const T&, const T&);
28    template<class T> bool operator<=(const T&, const T&);
29    template<class T> bool operator>=(const T&, const T&);
30}
31
32template<class T>
33void
34swap(T& a, T& b) noexcept(is_nothrow_move_constructible<T>::value &&
35                          is_nothrow_move_assignable<T>::value);
36
37template <class T, size_t N>
38void
39swap(T (&a)[N], T (&b)[N]) noexcept(noexcept(swap(*a, *b)));
40
41template <class T> T&& forward(typename remove_reference<T>::type& t) noexcept;  // constexpr in C++14
42template <class T> T&& forward(typename remove_reference<T>::type&& t) noexcept; // constexpr in C++14
43
44template <class T> typename remove_reference<T>::type&& move(T&&) noexcept;      // constexpr in C++14
45
46template <class T>
47    typename conditional
48    <
49        !is_nothrow_move_constructible<T>::value && is_copy_constructible<T>::value,
50        const T&,
51        T&&
52    >::type
53    move_if_noexcept(T& x) noexcept; // constexpr in C++14
54
55template <class T> constexpr add_const<T>_t& as_const(T& t) noexcept;      // C++17
56template <class T>                      void as_const(const T&&) = delete; // C++17
57
58template <class T> typename add_rvalue_reference<T>::type declval() noexcept;
59
60template <class T1, class T2>
61struct pair
62{
63    typedef T1 first_type;
64    typedef T2 second_type;
65
66    T1 first;
67    T2 second;
68
69    pair(const pair&) = default;
70    pair(pair&&) = default;
71    constexpr pair();
72    pair(const T1& x, const T2& y);                          // constexpr in C++14
73    template <class U, class V> pair(U&& x, V&& y);          // constexpr in C++14
74    template <class U, class V> pair(const pair<U, V>& p);   // constexpr in C++14
75    template <class U, class V> pair(pair<U, V>&& p);        // constexpr in C++14
76    template <class... Args1, class... Args2>
77        pair(piecewise_construct_t, tuple<Args1...> first_args,
78             tuple<Args2...> second_args);
79
80    template <class U, class V> pair& operator=(const pair<U, V>& p);
81    pair& operator=(pair&& p) noexcept(is_nothrow_move_assignable<T1>::value &&
82                                       is_nothrow_move_assignable<T2>::value);
83    template <class U, class V> pair& operator=(pair<U, V>&& p);
84
85    void swap(pair& p) noexcept(noexcept(swap(first, p.first)) &&
86                                noexcept(swap(second, p.second)));
87};
88
89template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
90template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
91template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
92template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
93template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
94template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
95
96template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&);   // constexpr in C++14
97template <class T1, class T2>
98void
99swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y)));
100
101struct piecewise_construct_t { };
102constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
103
104template <class T> class tuple_size;
105template <size_t I, class T> class tuple_element;
106
107template <class T1, class T2> struct tuple_size<pair<T1, T2> >;
108template <class T1, class T2> struct tuple_element<0, pair<T1, T2> >;
109template <class T1, class T2> struct tuple_element<1, pair<T1, T2> >;
110
111template<size_t I, class T1, class T2>
112    typename tuple_element<I, pair<T1, T2> >::type&
113    get(pair<T1, T2>&) noexcept; // constexpr in C++14
114
115template<size_t I, class T1, class T2>
116    const typename tuple_element<I, pair<T1, T2> >::type&
117    get(const pair<T1, T2>&) noexcept; // constexpr in C++14
118
119template<size_t I, class T1, class T2>
120    typename tuple_element<I, pair<T1, T2> >::type&&
121    get(pair<T1, T2>&&) noexcept; // constexpr in C++14
122
123template<class T1, class T2>
124    constexpr T1& get(pair<T1, T2>&) noexcept; // C++14
125
126template<size_t I, class T1, class T2>
127    constexpr const T1& get(const pair<T1, T2>&) noexcept; // C++14
128
129template<size_t I, class T1, class T2>
130    constexpr T1&& get(pair<T1, T2>&&) noexcept; // C++14
131
132// C++14
133
134template<class T, T... I>
135struct integer_sequence
136{
137    typedef T value_type;
138
139    static constexpr size_t size() noexcept;
140};
141
142template<size_t... I>
143  using index_sequence = integer_sequence<size_t, I...>;
144
145template<class T, T N>
146  using make_integer_sequence = integer_sequence<T, 0, 1, ..., N-1>;
147template<size_t N>
148  using make_index_sequence = make_integer_sequence<size_t, N>;
149
150template<class... T>
151  using index_sequence_for = make_index_sequence<sizeof...(T)>;
152
153template<class T, class U=T>
154    T exchange(T& obj, U&& new_value);
155}  // std
156
157*/
158
159#include <__config>
160#include <__tuple>
161#include <type_traits>
162
163#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
164#pragma GCC system_header
165#endif
166
167_LIBCPP_BEGIN_NAMESPACE_STD
168
169namespace rel_ops
170{
171
172template<class _Tp>
173inline _LIBCPP_INLINE_VISIBILITY
174bool
175operator!=(const _Tp& __x, const _Tp& __y)
176{
177    return !(__x == __y);
178}
179
180template<class _Tp>
181inline _LIBCPP_INLINE_VISIBILITY
182bool
183operator> (const _Tp& __x, const _Tp& __y)
184{
185    return __y < __x;
186}
187
188template<class _Tp>
189inline _LIBCPP_INLINE_VISIBILITY
190bool
191operator<=(const _Tp& __x, const _Tp& __y)
192{
193    return !(__y < __x);
194}
195
196template<class _Tp>
197inline _LIBCPP_INLINE_VISIBILITY
198bool
199operator>=(const _Tp& __x, const _Tp& __y)
200{
201    return !(__x < __y);
202}
203
204}  // rel_ops
205
206// swap_ranges
207
208// forward
209template<class _Tp, size_t _Np>
210inline _LIBCPP_INLINE_VISIBILITY
211void swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value);
212
213template <class _ForwardIterator1, class _ForwardIterator2>
214inline _LIBCPP_INLINE_VISIBILITY
215_ForwardIterator2
216swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
217{
218    for(; __first1 != __last1; ++__first1, (void) ++__first2)
219        swap(*__first1, *__first2);
220    return __first2;
221}
222
223template<class _Tp, size_t _Np>
224inline _LIBCPP_INLINE_VISIBILITY
225void
226swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value)
227{
228    _VSTD::swap_ranges(__a, __a + _Np, __b);
229}
230
231template <class _Tp>
232inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
233#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
234typename conditional
235<
236    !is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value,
237    const _Tp&,
238    _Tp&&
239>::type
240#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
241const _Tp&
242#endif
243move_if_noexcept(_Tp& __x) _NOEXCEPT
244{
245    return _VSTD::move(__x);
246}
247
248#if _LIBCPP_STD_VER > 14
249template <class _Tp> constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; }
250template <class _Tp>                        void as_const(const _Tp&&) = delete;
251#endif
252
253struct _LIBCPP_TYPE_VIS_ONLY piecewise_construct_t { };
254#if defined(_LIBCPP_HAS_NO_CONSTEXPR) || defined(_LIBCPP_BUILDING_UTILITY)
255extern const piecewise_construct_t piecewise_construct;// = piecewise_construct_t();
256#else
257constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
258#endif
259
260template <class _T1, class _T2>
261struct _LIBCPP_TYPE_VIS_ONLY pair
262{
263    typedef _T1 first_type;
264    typedef _T2 second_type;
265
266    _T1 first;
267    _T2 second;
268
269    // pair(const pair&) = default;
270    // pair(pair&&) = default;
271
272    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR pair() : first(), second() {}
273
274    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
275    pair(const _T1& __x, const _T2& __y)
276        : first(__x), second(__y) {}
277
278    template<class _U1, class _U2>
279        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
280        pair(const pair<_U1, _U2>& __p
281#ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAE
282                 ,typename enable_if<is_convertible<const _U1&, _T1>::value &&
283                                    is_convertible<const _U2&, _T2>::value>::type* = 0
284#endif
285                                      )
286            : first(__p.first), second(__p.second) {}
287
288#if !defined(_LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS) && _LIBCPP_TRIVIAL_PAIR_COPY_CTOR
289    _LIBCPP_INLINE_VISIBILITY
290    pair(const pair& __p) = default;
291#elif !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) || !_LIBCPP_TRIVIAL_PAIR_COPY_CTOR
292    _LIBCPP_INLINE_VISIBILITY
293    pair(const pair& __p)
294        _NOEXCEPT_(is_nothrow_copy_constructible<first_type>::value &&
295                   is_nothrow_copy_constructible<second_type>::value)
296        : first(__p.first),
297          second(__p.second)
298    {
299    }
300#endif
301
302    _LIBCPP_INLINE_VISIBILITY
303    pair& operator=(const pair& __p)
304        _NOEXCEPT_(is_nothrow_copy_assignable<first_type>::value &&
305                   is_nothrow_copy_assignable<second_type>::value)
306    {
307        first = __p.first;
308        second = __p.second;
309        return *this;
310    }
311
312#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
313
314    template <class _U1, class _U2,
315              class = typename enable_if<is_convertible<_U1, first_type>::value &&
316                                         is_convertible<_U2, second_type>::value>::type>
317        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
318        pair(_U1&& __u1, _U2&& __u2)
319            : first(_VSTD::forward<_U1>(__u1)),
320              second(_VSTD::forward<_U2>(__u2))
321            {}
322
323    template<class _U1, class _U2>
324        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
325        pair(pair<_U1, _U2>&& __p,
326                 typename enable_if<is_convertible<_U1, _T1>::value &&
327                                    is_convertible<_U2, _T2>::value>::type* = 0)
328            : first(_VSTD::forward<_U1>(__p.first)),
329              second(_VSTD::forward<_U2>(__p.second)) {}
330
331#ifndef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS
332    _LIBCPP_INLINE_VISIBILITY
333    pair(pair&& __p) = default;
334#else
335    _LIBCPP_INLINE_VISIBILITY
336    pair(pair&& __p) _NOEXCEPT_(is_nothrow_move_constructible<first_type>::value &&
337                                is_nothrow_move_constructible<second_type>::value)
338        : first(_VSTD::forward<first_type>(__p.first)),
339          second(_VSTD::forward<second_type>(__p.second))
340    {
341    }
342#endif
343
344    _LIBCPP_INLINE_VISIBILITY
345    pair&
346    operator=(pair&& __p) _NOEXCEPT_(is_nothrow_move_assignable<first_type>::value &&
347                                     is_nothrow_move_assignable<second_type>::value)
348    {
349        first = _VSTD::forward<first_type>(__p.first);
350        second = _VSTD::forward<second_type>(__p.second);
351        return *this;
352    }
353
354#ifndef _LIBCPP_HAS_NO_VARIADICS
355
356    template<class _Tuple,
357             class = typename enable_if<__tuple_convertible<_Tuple, pair>::value>::type>
358        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
359        pair(_Tuple&& __p)
360            : first(_VSTD::forward<typename tuple_element<0,
361                                  typename __make_tuple_types<_Tuple>::type>::type>(_VSTD::get<0>(__p))),
362              second(_VSTD::forward<typename tuple_element<1,
363                                   typename __make_tuple_types<_Tuple>::type>::type>(_VSTD::get<1>(__p)))
364            {}
365
366
367
368    template <class... _Args1, class... _Args2>
369        _LIBCPP_INLINE_VISIBILITY
370        pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args,
371                                    tuple<_Args2...> __second_args)
372            : pair(__pc, __first_args, __second_args,
373                   typename __make_tuple_indices<sizeof...(_Args1)>::type(),
374                   typename __make_tuple_indices<sizeof...(_Args2) >::type())
375            {}
376
377    template <class _Tuple,
378              class = typename enable_if<__tuple_assignable<_Tuple, pair>::value>::type>
379        _LIBCPP_INLINE_VISIBILITY
380        pair&
381        operator=(_Tuple&& __p)
382        {
383            typedef typename __make_tuple_types<_Tuple>::type _TupleRef;
384            typedef typename tuple_element<0, _TupleRef>::type _U0;
385            typedef typename tuple_element<1, _TupleRef>::type _U1;
386            first  = _VSTD::forward<_U0>(_VSTD::get<0>(__p));
387            second = _VSTD::forward<_U1>(_VSTD::get<1>(__p));
388            return *this;
389        }
390
391#endif  // _LIBCPP_HAS_NO_VARIADICS
392
393#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
394    _LIBCPP_INLINE_VISIBILITY
395    void
396    swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable<first_type>::value &&
397                               __is_nothrow_swappable<second_type>::value)
398    {
399        using _VSTD::swap;
400        swap(first,  __p.first);
401        swap(second, __p.second);
402    }
403private:
404
405#ifndef _LIBCPP_HAS_NO_VARIADICS
406    template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
407        _LIBCPP_INLINE_VISIBILITY
408        pair(piecewise_construct_t,
409             tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args,
410             __tuple_indices<_I1...>, __tuple_indices<_I2...>);
411#endif  // _LIBCPP_HAS_NO_VARIADICS
412};
413
414template <class _T1, class _T2>
415inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
416bool
417operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
418{
419    return __x.first == __y.first && __x.second == __y.second;
420}
421
422template <class _T1, class _T2>
423inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
424bool
425operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
426{
427    return !(__x == __y);
428}
429
430template <class _T1, class _T2>
431inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
432bool
433operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
434{
435    return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second);
436}
437
438template <class _T1, class _T2>
439inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
440bool
441operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
442{
443    return __y < __x;
444}
445
446template <class _T1, class _T2>
447inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
448bool
449operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
450{
451    return !(__x < __y);
452}
453
454template <class _T1, class _T2>
455inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
456bool
457operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
458{
459    return !(__y < __x);
460}
461
462template <class _T1, class _T2>
463inline _LIBCPP_INLINE_VISIBILITY
464typename enable_if
465<
466    __is_swappable<_T1>::value &&
467    __is_swappable<_T2>::value,
468    void
469>::type
470swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
471                     _NOEXCEPT_((__is_nothrow_swappable<_T1>::value &&
472                                 __is_nothrow_swappable<_T2>::value))
473{
474    __x.swap(__y);
475}
476
477#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
478
479template <class _Tp> class _LIBCPP_TYPE_VIS_ONLY reference_wrapper;
480
481template <class _Tp>
482struct __make_pair_return_impl
483{
484    typedef _Tp type;
485};
486
487template <class _Tp>
488struct __make_pair_return_impl<reference_wrapper<_Tp>>
489{
490    typedef _Tp& type;
491};
492
493template <class _Tp>
494struct __make_pair_return
495{
496    typedef typename __make_pair_return_impl<typename decay<_Tp>::type>::type type;
497};
498
499template <class _T1, class _T2>
500inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
501pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
502make_pair(_T1&& __t1, _T2&& __t2)
503{
504    return pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
505               (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2));
506}
507
508#else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
509
510template <class _T1, class _T2>
511inline _LIBCPP_INLINE_VISIBILITY
512pair<_T1,_T2>
513make_pair(_T1 __x, _T2 __y)
514{
515    return pair<_T1, _T2>(__x, __y);
516}
517
518#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
519
520template <class _T1, class _T2>
521  class _LIBCPP_TYPE_VIS_ONLY tuple_size<pair<_T1, _T2> >
522    : public integral_constant<size_t, 2> {};
523
524template <class _T1, class _T2>
525class _LIBCPP_TYPE_VIS_ONLY tuple_element<0, pair<_T1, _T2> >
526{
527public:
528    typedef _T1 type;
529};
530
531template <class _T1, class _T2>
532class _LIBCPP_TYPE_VIS_ONLY tuple_element<1, pair<_T1, _T2> >
533{
534public:
535    typedef _T2 type;
536};
537
538template <size_t _Ip> struct __get_pair;
539
540template <>
541struct __get_pair<0>
542{
543    template <class _T1, class _T2>
544    static
545    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
546    _T1&
547    get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
548
549    template <class _T1, class _T2>
550    static
551    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
552    const _T1&
553    get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
554
555#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
556
557    template <class _T1, class _T2>
558    static
559    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
560    _T1&&
561    get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);}
562
563#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
564};
565
566template <>
567struct __get_pair<1>
568{
569    template <class _T1, class _T2>
570    static
571    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
572    _T2&
573    get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
574
575    template <class _T1, class _T2>
576    static
577    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
578    const _T2&
579    get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
580
581#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
582
583    template <class _T1, class _T2>
584    static
585    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
586    _T2&&
587    get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);}
588
589#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
590};
591
592template <size_t _Ip, class _T1, class _T2>
593inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
594typename tuple_element<_Ip, pair<_T1, _T2> >::type&
595get(pair<_T1, _T2>& __p) _NOEXCEPT
596{
597    return __get_pair<_Ip>::get(__p);
598}
599
600template <size_t _Ip, class _T1, class _T2>
601inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
602const typename tuple_element<_Ip, pair<_T1, _T2> >::type&
603get(const pair<_T1, _T2>& __p) _NOEXCEPT
604{
605    return __get_pair<_Ip>::get(__p);
606}
607
608#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
609
610template <size_t _Ip, class _T1, class _T2>
611inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
612typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
613get(pair<_T1, _T2>&& __p) _NOEXCEPT
614{
615    return __get_pair<_Ip>::get(_VSTD::move(__p));
616}
617
618#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
619
620#if _LIBCPP_STD_VER > 11
621template <class _T1, class _T2>
622inline _LIBCPP_INLINE_VISIBILITY
623constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT
624{
625    return __get_pair<0>::get(__p);
626}
627
628template <class _T1, class _T2>
629inline _LIBCPP_INLINE_VISIBILITY
630constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT
631{
632    return __get_pair<0>::get(__p);
633}
634
635template <class _T1, class _T2>
636inline _LIBCPP_INLINE_VISIBILITY
637constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT
638{
639    return __get_pair<0>::get(_VSTD::move(__p));
640}
641
642template <class _T1, class _T2>
643inline _LIBCPP_INLINE_VISIBILITY
644constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT
645{
646    return __get_pair<1>::get(__p);
647}
648
649template <class _T1, class _T2>
650inline _LIBCPP_INLINE_VISIBILITY
651constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT
652{
653    return __get_pair<1>::get(__p);
654}
655
656template <class _T1, class _T2>
657inline _LIBCPP_INLINE_VISIBILITY
658constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT
659{
660    return __get_pair<1>::get(_VSTD::move(__p));
661}
662
663#endif
664
665#if _LIBCPP_STD_VER > 11
666
667template<class _Tp, _Tp... _Ip>
668struct _LIBCPP_TYPE_VIS_ONLY integer_sequence
669{
670    typedef _Tp value_type;
671    static_assert( is_integral<_Tp>::value,
672                  "std::integer_sequence can only be instantiated with an integral type" );
673    static
674    _LIBCPP_INLINE_VISIBILITY
675    constexpr
676    size_t
677    size() noexcept { return sizeof...(_Ip); }
678};
679
680template<size_t... _Ip>
681    using index_sequence = integer_sequence<size_t, _Ip...>;
682
683namespace __detail {
684
685template<typename _Tp, size_t ..._Extra> struct __repeat;
686template<typename _Tp, _Tp ..._Np, size_t ..._Extra> struct __repeat<integer_sequence<_Tp, _Np...>, _Extra...> {
687  typedef integer_sequence<_Tp,
688                           _Np...,
689                           sizeof...(_Np) + _Np...,
690                           2 * sizeof...(_Np) + _Np...,
691                           3 * sizeof...(_Np) + _Np...,
692                           4 * sizeof...(_Np) + _Np...,
693                           5 * sizeof...(_Np) + _Np...,
694                           6 * sizeof...(_Np) + _Np...,
695                           7 * sizeof...(_Np) + _Np...,
696                           _Extra...> type;
697};
698
699template<size_t _Np> struct __parity;
700template<size_t _Np> struct __make : __parity<_Np % 8>::template __pmake<_Np> {};
701
702template<> struct __make<0> { typedef integer_sequence<size_t> type; };
703template<> struct __make<1> { typedef integer_sequence<size_t, 0> type; };
704template<> struct __make<2> { typedef integer_sequence<size_t, 0, 1> type; };
705template<> struct __make<3> { typedef integer_sequence<size_t, 0, 1, 2> type; };
706template<> struct __make<4> { typedef integer_sequence<size_t, 0, 1, 2, 3> type; };
707template<> struct __make<5> { typedef integer_sequence<size_t, 0, 1, 2, 3, 4> type; };
708template<> struct __make<6> { typedef integer_sequence<size_t, 0, 1, 2, 3, 4, 5> type; };
709template<> struct __make<7> { typedef integer_sequence<size_t, 0, 1, 2, 3, 4, 5, 6> type; };
710
711template<> struct __parity<0> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type> {}; };
712template<> struct __parity<1> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 1> {}; };
713template<> struct __parity<2> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 2, _Np - 1> {}; };
714template<> struct __parity<3> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 3, _Np - 2, _Np - 1> {}; };
715template<> struct __parity<4> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
716template<> struct __parity<5> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
717template<> struct __parity<6> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 6, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
718template<> struct __parity<7> { template<size_t _Np> struct __pmake : __repeat<typename __make<_Np / 8>::type, _Np - 7, _Np - 6, _Np - 5, _Np - 4, _Np - 3, _Np - 2, _Np - 1> {}; };
719
720template<typename _Tp, typename _Up> struct __convert {
721  template<typename> struct __result;
722  template<_Tp ..._Np> struct __result<integer_sequence<_Tp, _Np...> > { typedef integer_sequence<_Up, _Np...> type; };
723};
724template<typename _Tp> struct __convert<_Tp, _Tp> { template<typename _Up> struct __result { typedef _Up type; }; };
725
726}
727
728template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked =
729  typename __detail::__convert<size_t, _Tp>::template __result<typename __detail::__make<_Np>::type>::type;
730
731template <class _Tp, _Tp _Ep>
732struct __make_integer_sequence
733{
734    static_assert(is_integral<_Tp>::value,
735                  "std::make_integer_sequence can only be instantiated with an integral type" );
736    static_assert(0 <= _Ep, "std::make_integer_sequence input shall not be negative");
737    typedef __make_integer_sequence_unchecked<_Tp, _Ep> type;
738};
739
740template<class _Tp, _Tp _Np>
741    using make_integer_sequence = typename __make_integer_sequence<_Tp, _Np>::type;
742
743template<size_t _Np>
744    using make_index_sequence = make_integer_sequence<size_t, _Np>;
745
746template<class... _Tp>
747    using index_sequence_for = make_index_sequence<sizeof...(_Tp)>;
748
749#endif  // _LIBCPP_STD_VER > 11
750
751#if _LIBCPP_STD_VER > 11
752template<class _T1, class _T2 = _T1>
753inline _LIBCPP_INLINE_VISIBILITY
754_T1 exchange(_T1& __obj, _T2 && __new_value)
755{
756    _T1 __old_value = _VSTD::move(__obj);
757    __obj = _VSTD::forward<_T2>(__new_value);
758    return __old_value;
759}
760#endif  // _LIBCPP_STD_VER > 11
761
762_LIBCPP_END_NAMESPACE_STD
763
764#endif  // _LIBCPP_UTILITY
765