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