contrib/libc++/include/utility

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