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(is_nothrow_swappable_v<T1> &&
  86                                 is_nothrow_swappable_v<T2>);
  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
 175 // 20.2.7, in-place construction // C++17
 176 struct in_place_t {
 177   explicit in_place_t() = default;
 178 };
 179 inline constexpr in_place_t in_place{};
 180 template <class T>
 181   struct in_place_type_t {
 182     explicit in_place_type_t() = default;
 183   };
 184 template <class T>
 185   inline constexpr in_place_type_t<T> in_place_type{};
 186 template <size_t I>
 187   struct in_place_index_t {
 188     explicit in_place_index_t() = default;
 189   };
 190 template <size_t I>
 191   inline constexpr in_place_index_t<I> in_place_index{};
 192
 193 }  // std
 194
 195 */
 196
 197 #include <__config>
 198 #include <__tuple>
 199 #include <type_traits>
 200 #include <initializer_list>
 201 #include <__debug>
 202
 203 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 204 #pragma GCC system_header
 205 #endif
 206
 207 _LIBCPP_BEGIN_NAMESPACE_STD
 208
 209 namespace rel_ops
 210 {
 211
 212 template<class _Tp>
 213 inline _LIBCPP_INLINE_VISIBILITY
 214 bool
 215 operator!=(const _Tp& __x, const _Tp& __y)
 216 {
 217     return !(__x == __y);
 218 }
 219
 220 template<class _Tp>
 221 inline _LIBCPP_INLINE_VISIBILITY
 222 bool
 223 operator> (const _Tp& __x, const _Tp& __y)
 224 {
 225     return __y < __x;
 226 }
 227
 228 template<class _Tp>
 229 inline _LIBCPP_INLINE_VISIBILITY
 230 bool
 231 operator<=(const _Tp& __x, const _Tp& __y)
 232 {
 233     return !(__y < __x);
 234 }
 235
 236 template<class _Tp>
 237 inline _LIBCPP_INLINE_VISIBILITY
 238 bool
 239 operator>=(const _Tp& __x, const _Tp& __y)
 240 {
 241     return !(__x < __y);
 242 }
 243
 244 }  // rel_ops
 245
 246 // swap_ranges
 247
 248
 249 template <class _ForwardIterator1, class _ForwardIterator2>
 250 inline _LIBCPP_INLINE_VISIBILITY
 251 _ForwardIterator2
 252 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
 253 {
 254     for(; __first1 != __last1; ++__first1, (void) ++__first2)
 255         swap(*__first1, *__first2);
 256     return __first2;
 257 }
 258
 259 // forward declared in <type_traits>
 260 template<class _Tp, size_t _Np>
 261 inline _LIBCPP_INLINE_VISIBILITY
 262 typename enable_if<
 263     __is_swappable<_Tp>::value
 264 >::type
 265 swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value)
 266 {
 267     _VSTD::swap_ranges(__a, __a + _Np, __b);
 268 }
 269
 270 template <class _Tp>
 271 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 272 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 273 typename conditional
 274 <
 275     !is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value,
 276     const _Tp&,
 277     _Tp&&
 278 >::type
 279 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 280 const _Tp&
 281 #endif
 282 move_if_noexcept(_Tp& __x) _NOEXCEPT
 283 {
 284     return _VSTD::move(__x);
 285 }
 286
 287 #if _LIBCPP_STD_VER > 14
 288 template <class _Tp> constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; }
 289 template <class _Tp>                        void as_const(const _Tp&&) = delete;
 290 #endif
 291
 292 struct _LIBCPP_TEMPLATE_VIS piecewise_construct_t { };
 293 #if defined(_LIBCPP_HAS_NO_CONSTEXPR) || defined(_LIBCPP_BUILDING_UTILITY)
 294 extern const piecewise_construct_t piecewise_construct;// = piecewise_construct_t();
 295 #else
 296 constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
 297 #endif
 298
 299 #if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR)
 300 struct __non_trivially_copyable_base {
 301   _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
 302   __non_trivially_copyable_base() _NOEXCEPT {}
 303   _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 304   __non_trivially_copyable_base(__non_trivially_copyable_base const&) _NOEXCEPT {}
 305 };
 306 #endif
 307
 308 template <class _T1, class _T2>
 309 struct _LIBCPP_TEMPLATE_VIS pair
 310 #if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR)
 311 : private __non_trivially_copyable_base
 312 #endif
 313 {
 314     typedef _T1 first_type;
 315     typedef _T2 second_type;
 316
 317     _T1 first;
 318     _T2 second;
 319
 320 #if !defined(_LIBCPP_CXX03_LANG)
 321     pair(pair const&) = default;
 322     pair(pair&&) = default;
 323 #else
 324   // Use the implicitly declared copy constructor in C++03
 325 #endif
 326
 327 #ifdef _LIBCPP_CXX03_LANG
 328     _LIBCPP_INLINE_VISIBILITY
 329     pair() : first(), second() {}
 330
 331     _LIBCPP_INLINE_VISIBILITY
 332     pair(_T1 const& __t1, _T2 const& __t2) : first(__t1), second(__t2) {}
 333
 334     template <class _U1, class _U2>
 335     _LIBCPP_INLINE_VISIBILITY
 336     pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
 337
 338     _LIBCPP_INLINE_VISIBILITY
 339     pair& operator=(pair const& __p) {
 340         first = __p.first;
 341         second = __p.second;
 342         return *this;
 343     }
 344 #else
 345     template <bool _Val>
 346     using _EnableB = typename enable_if<_Val, bool>::type;
 347
 348     struct _CheckArgs {
 349       template <class _U1, class _U2>
 350       static constexpr bool __enable_default() {
 351           return is_default_constructible<_U1>::value
 352               && is_default_constructible<_U2>::value;
 353       }
 354
 355       template <class _U1, class _U2>
 356       static constexpr bool __enable_explicit() {
 357           return is_constructible<first_type, _U1>::value
 358               && is_constructible<second_type, _U2>::value
 359               && (!is_convertible<_U1, first_type>::value
 360                   || !is_convertible<_U2, second_type>::value);
 361       }
 362
 363       template <class _U1, class _U2>
 364       static constexpr bool __enable_implicit() {
 365           return is_constructible<first_type, _U1>::value
 366               && is_constructible<second_type, _U2>::value
 367               && is_convertible<_U1, first_type>::value
 368               && is_convertible<_U2, second_type>::value;
 369       }
 370     };
 371
 372     template <bool _MaybeEnable>
 373     using _CheckArgsDep = typename conditional<
 374       _MaybeEnable, _CheckArgs, __check_tuple_constructor_fail>::type;
 375
 376     struct _CheckTupleLikeConstructor {
 377         template <class _Tuple>
 378         static constexpr bool __enable_implicit() {
 379             return __tuple_convertible<_Tuple, pair>::value;
 380         }
 381
 382         template <class _Tuple>
 383         static constexpr bool __enable_explicit() {
 384             return __tuple_constructible<_Tuple, pair>::value
 385                && !__tuple_convertible<_Tuple, pair>::value;
 386         }
 387
 388         template <class _Tuple>
 389         static constexpr bool __enable_assign() {
 390             return __tuple_assignable<_Tuple, pair>::value;
 391         }
 392     };
 393
 394     template <class _Tuple>
 395     using _CheckTLC = typename conditional<
 396         __tuple_like_with_size<_Tuple, 2>::value
 397             && !is_same<typename decay<_Tuple>::type, pair>::value,
 398         _CheckTupleLikeConstructor,
 399         __check_tuple_constructor_fail
 400     >::type;
 401
 402     template<bool _Dummy = true, _EnableB<
 403             _CheckArgsDep<_Dummy>::template __enable_default<_T1, _T2>()
 404     > = false>
 405     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 406     pair() : first(), second() {}
 407
 408     template <bool _Dummy = true, _EnableB<
 409              _CheckArgsDep<_Dummy>::template __enable_explicit<_T1 const&, _T2 const&>()
 410     > = false>
 411     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 412     explicit pair(_T1 const& __t1, _T2 const& __t2)
 413         : first(__t1), second(__t2) {}
 414
 415     template<bool _Dummy = true, _EnableB<
 416             _CheckArgsDep<_Dummy>::template __enable_implicit<_T1 const&, _T2 const&>()
 417     > = false>
 418     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 419     pair(_T1 const& __t1, _T2 const& __t2)
 420         : first(__t1), second(__t2) {}
 421
 422     template<class _U1, class _U2, _EnableB<
 423              _CheckArgs::template __enable_explicit<_U1, _U2>()
 424     > = false>
 425     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 426     explicit pair(_U1&& __u1, _U2&& __u2)
 427         : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {}
 428
 429     template<class _U1, class _U2, _EnableB<
 430             _CheckArgs::template __enable_implicit<_U1, _U2>()
 431     > = false>
 432     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 433     pair(_U1&& __u1, _U2&& __u2)
 434         : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {}
 435
 436     template<class _U1, class _U2, _EnableB<
 437             _CheckArgs::template __enable_explicit<_U1 const&, _U2 const&>()
 438     > = false>
 439     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 440     explicit pair(pair<_U1, _U2> const& __p)
 441         : first(__p.first), second(__p.second) {}
 442
 443     template<class _U1, class _U2, _EnableB<
 444             _CheckArgs::template __enable_implicit<_U1 const&, _U2 const&>()
 445     > = false>
 446     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 447     pair(pair<_U1, _U2> const& __p)
 448         : first(__p.first), second(__p.second) {}
 449
 450     template<class _U1, class _U2, _EnableB<
 451             _CheckArgs::template __enable_explicit<_U1, _U2>()
 452     > = false>
 453     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 454     explicit pair(pair<_U1, _U2>&&__p)
 455         : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {}
 456
 457     template<class _U1, class _U2, _EnableB<
 458             _CheckArgs::template __enable_implicit<_U1, _U2>()
 459     > = false>
 460     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 461     pair(pair<_U1, _U2>&& __p)
 462         : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {}
 463
 464     template<class _Tuple, _EnableB<
 465             _CheckTLC<_Tuple>::template __enable_explicit<_Tuple>()
 466     > = false>
 467     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 468     explicit pair(_Tuple&& __p)
 469         : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))),
 470           second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {}
 471
 472     template<class _Tuple, _EnableB<
 473             _CheckTLC<_Tuple>::template __enable_implicit<_Tuple>()
 474     > = false>
 475     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 476     pair(_Tuple&& __p)
 477         : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))),
 478           second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {}
 479
 480     template <class... _Args1, class... _Args2>
 481     _LIBCPP_INLINE_VISIBILITY
 482     pair(piecewise_construct_t __pc,
 483          tuple<_Args1...> __first_args, tuple<_Args2...> __second_args)
 484         : pair(__pc, __first_args, __second_args,
 485                 typename __make_tuple_indices<sizeof...(_Args1)>::type(),
 486                 typename __make_tuple_indices<sizeof...(_Args2) >::type()) {}
 487
 488     _LIBCPP_INLINE_VISIBILITY
 489     pair& operator=(typename conditional<
 490                         is_copy_assignable<first_type>::value &&
 491                         is_copy_assignable<second_type>::value,
 492                     pair, __nat>::type const& __p)
 493         _NOEXCEPT_(is_nothrow_copy_assignable<first_type>::value &&
 494                    is_nothrow_copy_assignable<second_type>::value)
 495     {
 496         first = __p.first;
 497         second = __p.second;
 498         return *this;
 499     }
 500
 501     _LIBCPP_INLINE_VISIBILITY
 502     pair& operator=(typename conditional<
 503                         is_move_assignable<first_type>::value &&
 504                         is_move_assignable<second_type>::value,
 505                     pair, __nat>::type&& __p)
 506         _NOEXCEPT_(is_nothrow_move_assignable<first_type>::value &&
 507                    is_nothrow_move_assignable<second_type>::value)
 508     {
 509         first = _VSTD::forward<first_type>(__p.first);
 510         second = _VSTD::forward<second_type>(__p.second);
 511         return *this;
 512     }
 513
 514     template <class _Tuple, _EnableB<
 515             _CheckTLC<_Tuple>::template __enable_assign<_Tuple>()
 516      > = false>
 517     _LIBCPP_INLINE_VISIBILITY
 518     pair& operator=(_Tuple&& __p) {
 519         first = _VSTD::get<0>(_VSTD::forward<_Tuple>(__p));
 520         second = _VSTD::get<1>(_VSTD::forward<_Tuple>(__p));
 521         return *this;
 522     }
 523 #endif
 524
 525     _LIBCPP_INLINE_VISIBILITY
 526     void
 527     swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable<first_type>::value &&
 528                                __is_nothrow_swappable<second_type>::value)
 529     {
 530         using _VSTD::swap;
 531         swap(first,  __p.first);
 532         swap(second, __p.second);
 533     }
 534 private:
 535
 536 #ifndef _LIBCPP_CXX03_LANG
 537     template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
 538         _LIBCPP_INLINE_VISIBILITY
 539         pair(piecewise_construct_t,
 540              tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args,
 541              __tuple_indices<_I1...>, __tuple_indices<_I2...>);
 542 #endif
 543 };
 544
 545 template <class _T1, class _T2>
 546 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 547 bool
 548 operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 549 {
 550     return __x.first == __y.first && __x.second == __y.second;
 551 }
 552
 553 template <class _T1, class _T2>
 554 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 555 bool
 556 operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 557 {
 558     return !(__x == __y);
 559 }
 560
 561 template <class _T1, class _T2>
 562 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 563 bool
 564 operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 565 {
 566     return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second);
 567 }
 568
 569 template <class _T1, class _T2>
 570 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 571 bool
 572 operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 573 {
 574     return __y < __x;
 575 }
 576
 577 template <class _T1, class _T2>
 578 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 579 bool
 580 operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 581 {
 582     return !(__x < __y);
 583 }
 584
 585 template <class _T1, class _T2>
 586 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 587 bool
 588 operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 589 {
 590     return !(__y < __x);
 591 }
 592
 593 template <class _T1, class _T2>
 594 inline _LIBCPP_INLINE_VISIBILITY
 595 typename enable_if
 596 <
 597     __is_swappable<_T1>::value &&
 598     __is_swappable<_T2>::value,
 599     void
 600 >::type
 601 swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
 602                      _NOEXCEPT_((__is_nothrow_swappable<_T1>::value &&
 603                                  __is_nothrow_swappable<_T2>::value))
 604 {
 605     __x.swap(__y);
 606 }
 607
 608 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 609
 610
 611 template <class _Tp>
 612 struct __make_pair_return_impl
 613 {
 614     typedef _Tp type;
 615 };
 616
 617 template <class _Tp>
 618 struct __make_pair_return_impl<reference_wrapper<_Tp>>
 619 {
 620     typedef _Tp& type;
 621 };
 622
 623 template <class _Tp>
 624 struct __make_pair_return
 625 {
 626     typedef typename __make_pair_return_impl<typename decay<_Tp>::type>::type type;
 627 };
 628
 629 template <class _T1, class _T2>
 630 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 631 pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
 632 make_pair(_T1&& __t1, _T2&& __t2)
 633 {
 634     return pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
 635                (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2));
 636 }
 637
 638 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 639
 640 template <class _T1, class _T2>
 641 inline _LIBCPP_INLINE_VISIBILITY
 642 pair<_T1,_T2>
 643 make_pair(_T1 __x, _T2 __y)
 644 {
 645     return pair<_T1, _T2>(__x, __y);
 646 }
 647
 648 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 649
 650 template <class _T1, class _T2>
 651   class _LIBCPP_TEMPLATE_VIS tuple_size<pair<_T1, _T2> >
 652     : public integral_constant<size_t, 2> {};
 653
 654 template <class _T1, class _T2>
 655 class _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> >
 656 {
 657 public:
 658     typedef _T1 type;
 659 };
 660
 661 template <class _T1, class _T2>
 662 class _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> >
 663 {
 664 public:
 665     typedef _T2 type;
 666 };
 667
 668 template <size_t _Ip> struct __get_pair;
 669
 670 template <>
 671 struct __get_pair<0>
 672 {
 673     template <class _T1, class _T2>
 674     static
 675     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 676     _T1&
 677     get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
 678
 679     template <class _T1, class _T2>
 680     static
 681     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 682     const _T1&
 683     get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
 684
 685 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 686
 687     template <class _T1, class _T2>
 688     static
 689     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 690     _T1&&
 691     get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);}
 692
 693     template <class _T1, class _T2>
 694     static
 695     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 696     const _T1&&
 697     get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T1>(__p.first);}
 698
 699 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 700 };
 701
 702 template <>
 703 struct __get_pair<1>
 704 {
 705     template <class _T1, class _T2>
 706     static
 707     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 708     _T2&
 709     get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
 710
 711     template <class _T1, class _T2>
 712     static
 713     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 714     const _T2&
 715     get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
 716
 717 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 718
 719     template <class _T1, class _T2>
 720     static
 721     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 722     _T2&&
 723     get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);}
 724
 725     template <class _T1, class _T2>
 726     static
 727     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 728     const _T2&&
 729     get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T2>(__p.second);}
 730
 731 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 732 };
 733
 734 template <size_t _Ip, class _T1, class _T2>
 735 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 736 typename tuple_element<_Ip, pair<_T1, _T2> >::type&
 737 get(pair<_T1, _T2>& __p) _NOEXCEPT
 738 {
 739     return __get_pair<_Ip>::get(__p);
 740 }
 741
 742 template <size_t _Ip, class _T1, class _T2>
 743 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 744 const typename tuple_element<_Ip, pair<_T1, _T2> >::type&
 745 get(const pair<_T1, _T2>& __p) _NOEXCEPT
 746 {
 747     return __get_pair<_Ip>::get(__p);
 748 }
 749
 750 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 751
 752 template <size_t _Ip, class _T1, class _T2>
 753 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 754 typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
 755 get(pair<_T1, _T2>&& __p) _NOEXCEPT
 756 {
 757     return __get_pair<_Ip>::get(_VSTD::move(__p));
 758 }
 759
 760 template <size_t _Ip, class _T1, class _T2>
 761 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 762 const typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
 763 get(const pair<_T1, _T2>&& __p) _NOEXCEPT
 764 {
 765     return __get_pair<_Ip>::get(_VSTD::move(__p));
 766 }
 767
 768 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 769
 770 #if _LIBCPP_STD_VER > 11
 771 template <class _T1, class _T2>
 772 inline _LIBCPP_INLINE_VISIBILITY
 773 constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT
 774 {
 775     return __get_pair<0>::get(__p);
 776 }
 777
 778 template <class _T1, class _T2>
 779 inline _LIBCPP_INLINE_VISIBILITY
 780 constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT
 781 {
 782     return __get_pair<0>::get(__p);
 783 }
 784
 785 template <class _T1, class _T2>
 786 inline _LIBCPP_INLINE_VISIBILITY
 787 constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT
 788 {
 789     return __get_pair<0>::get(_VSTD::move(__p));
 790 }
 791
 792 template <class _T1, class _T2>
 793 inline _LIBCPP_INLINE_VISIBILITY
 794 constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT
 795 {
 796     return __get_pair<0>::get(_VSTD::move(__p));
 797 }
 798
 799 template <class _T1, class _T2>
 800 inline _LIBCPP_INLINE_VISIBILITY
 801 constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT
 802 {
 803     return __get_pair<1>::get(__p);
 804 }
 805
 806 template <class _T1, class _T2>
 807 inline _LIBCPP_INLINE_VISIBILITY
 808 constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT
 809 {
 810     return __get_pair<1>::get(__p);
 811 }
 812
 813 template <class _T1, class _T2>
 814 inline _LIBCPP_INLINE_VISIBILITY
 815 constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT
 816 {
 817     return __get_pair<1>::get(_VSTD::move(__p));
 818 }
 819
 820 template <class _T1, class _T2>
 821 inline _LIBCPP_INLINE_VISIBILITY
 822 constexpr _T1 const && get(pair<_T2, _T1> const&& __p) _NOEXCEPT
 823 {
 824     return __get_pair<1>::get(_VSTD::move(__p));
 825 }
 826
 827 #endif
 828
 829 #if _LIBCPP_STD_VER > 11
 830
 831 template<class _Tp, _Tp... _Ip>
 832 struct _LIBCPP_TEMPLATE_VIS integer_sequence
 833 {
 834     typedef _Tp value_type;
 835     static_assert( is_integral<_Tp>::value,
 836                   "std::integer_sequence can only be instantiated with an integral type" );
 837     static
 838     _LIBCPP_INLINE_VISIBILITY
 839     constexpr
 840     size_t
 841     size() noexcept { return sizeof...(_Ip); }
 842 };
 843
 844 template<size_t... _Ip>
 845     using index_sequence = integer_sequence<size_t, _Ip...>;
 846
 847 #if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE)
 848
 849 template <class _Tp, _Tp _Ep>
 850 using __make_integer_sequence = __make_integer_seq<integer_sequence, _Tp, _Ep>;
 851
 852 #else
 853
 854 template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked =
 855   typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>;
 856
 857 template <class _Tp, _Tp _Ep>
 858 struct __make_integer_sequence_checked
 859 {
 860     static_assert(is_integral<_Tp>::value,
 861                   "std::make_integer_sequence can only be instantiated with an integral type" );
 862     static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length");
 863     // Workaround GCC bug by preventing bad installations when 0 <= _Ep
 864     // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929
 865     typedef __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type;
 866 };
 867
 868 template <class _Tp, _Tp _Ep>
 869 using __make_integer_sequence = typename __make_integer_sequence_checked<_Tp, _Ep>::type;
 870
 871 #endif
 872
 873 template<class _Tp, _Tp _Np>
 874     using make_integer_sequence = __make_integer_sequence<_Tp, _Np>;
 875
 876 template<size_t _Np>
 877     using make_index_sequence = make_integer_sequence<size_t, _Np>;
 878
 879 template<class... _Tp>
 880     using index_sequence_for = make_index_sequence<sizeof...(_Tp)>;
 881
 882 #endif  // _LIBCPP_STD_VER > 11
 883
 884 #if _LIBCPP_STD_VER > 11
 885 template<class _T1, class _T2 = _T1>
 886 inline _LIBCPP_INLINE_VISIBILITY
 887 _T1 exchange(_T1& __obj, _T2 && __new_value)
 888 {
 889     _T1 __old_value = _VSTD::move(__obj);
 890     __obj = _VSTD::forward<_T2>(__new_value);
 891     return __old_value;
 892 }
 893 #endif  // _LIBCPP_STD_VER > 11
 894
 895 #if _LIBCPP_STD_VER > 14
 896
 897 struct _LIBCPP_TYPE_VIS in_place_t {
 898     explicit in_place_t() = default;
 899 };
 900 #ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES
 901 inline
 902 #endif
 903 constexpr in_place_t in_place{};
 904
 905 template <class _Tp>
 906 struct _LIBCPP_TYPE_VIS in_place_type_t {
 907     explicit in_place_type_t() = default;
 908 };
 909 template <class _Tp>
 910 #ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES
 911 inline
 912 #endif
 913 constexpr in_place_type_t<_Tp> in_place_type{};
 914
 915 template <size_t _Idx>
 916 struct _LIBCPP_TYPE_VIS in_place_index_t {
 917     explicit in_place_index_t() = default;
 918 };
 919 template <size_t _Idx>
 920 #ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES
 921 inline
 922 #endif
 923 constexpr in_place_index_t<_Idx> in_place_index{};
 924
 925 template <class _Tp> struct __is_inplace_type_imp : false_type {};
 926 template <class _Tp> struct __is_inplace_type_imp<in_place_type_t<_Tp>> : true_type {};
 927
 928 template <class _Tp>
 929 using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>;
 930
 931 #endif // _LIBCPP_STD_VER > 14
 932
 933 _LIBCPP_END_NAMESPACE_STD
 934
 935 #endif  // _LIBCPP_UTILITY