utility revision 249998
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; 42template <class T> T&& forward(typename remove_reference<T>::type&& t) noexcept; 43 44template <class T> typename remove_reference<T>::type&& move(T&&) noexcept; 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; 54 55template <class T> typename add_rvalue_reference<T>::type declval() noexcept; 56 57template <class T1, class T2> 58struct pair 59{ 60 typedef T1 first_type; 61 typedef T2 second_type; 62 63 T1 first; 64 T2 second; 65 66 pair(const pair&) = default; 67 pair(pair&&) = default; 68 constexpr pair(); 69 pair(const T1& x, const T2& y); 70 template <class U, class V> pair(U&& x, V&& y); 71 template <class U, class V> pair(const pair<U, V>& p); 72 template <class U, class V> pair(pair<U, V>&& p); 73 template <class... Args1, class... Args2> 74 pair(piecewise_construct_t, tuple<Args1...> first_args, 75 tuple<Args2...> second_args); 76 77 template <class U, class V> pair& operator=(const pair<U, V>& p); 78 pair& operator=(pair&& p) noexcept(is_nothrow_move_assignable<T1>::value && 79 is_nothrow_move_assignable<T2>::value); 80 template <class U, class V> pair& operator=(pair<U, V>&& p); 81 82 void swap(pair& p) noexcept(noexcept(swap(first, p.first)) && 83 noexcept(swap(second, p.second))); 84}; 85 86template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&); 87template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&); 88template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&); 89template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&); 90template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); 91template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); 92 93template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&); 94template <class T1, class T2> 95void 96swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y))); 97 98struct piecewise_construct_t { }; 99constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); 100 101template <class T> class tuple_size; 102template <size_t I, class T> class tuple_element; 103 104template <class T1, class T2> struct tuple_size<std::pair<T1, T2> >; 105template <class T1, class T2> struct tuple_element<0, std::pair<T1, T2> >; 106template <class T1, class T2> struct tuple_element<1, std::pair<T1, T2> >; 107 108template<size_t I, class T1, class T2> 109 typename tuple_element<I, std::pair<T1, T2> >::type& 110 get(std::pair<T1, T2>&) noexcept; 111 112template<size_t I, class T1, class T2> 113 const typename const tuple_element<I, std::pair<T1, T2> >::type& 114 get(const std::pair<T1, T2>&) noexcept; 115 116template<size_t I, class T1, class T2> 117 typename tuple_element<I, std::pair<T1, T2> >::type&& 118 get(std::pair<T1, T2>&&) noexcept; 119 120} // std 121 122*/ 123 124#include <__config> 125#include <__tuple> 126#include <type_traits> 127 128#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 129#pragma GCC system_header 130#endif 131 132_LIBCPP_BEGIN_NAMESPACE_STD 133 134namespace rel_ops 135{ 136 137template<class _Tp> 138inline _LIBCPP_INLINE_VISIBILITY 139bool 140operator!=(const _Tp& __x, const _Tp& __y) 141{ 142 return !(__x == __y); 143} 144 145template<class _Tp> 146inline _LIBCPP_INLINE_VISIBILITY 147bool 148operator> (const _Tp& __x, const _Tp& __y) 149{ 150 return __y < __x; 151} 152 153template<class _Tp> 154inline _LIBCPP_INLINE_VISIBILITY 155bool 156operator<=(const _Tp& __x, const _Tp& __y) 157{ 158 return !(__y < __x); 159} 160 161template<class _Tp> 162inline _LIBCPP_INLINE_VISIBILITY 163bool 164operator>=(const _Tp& __x, const _Tp& __y) 165{ 166 return !(__x < __y); 167} 168 169} // rel_ops 170 171// swap_ranges 172 173template <class _ForwardIterator1, class _ForwardIterator2> 174inline _LIBCPP_INLINE_VISIBILITY 175_ForwardIterator2 176swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2) 177{ 178 for(; __first1 != __last1; ++__first1, ++__first2) 179 swap(*__first1, *__first2); 180 return __first2; 181} 182 183template<class _Tp, size_t _Np> 184inline _LIBCPP_INLINE_VISIBILITY 185void 186swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value) 187{ 188 _VSTD::swap_ranges(__a, __a + _Np, __b); 189} 190 191template <class _Tp> 192inline _LIBCPP_INLINE_VISIBILITY 193#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 194typename conditional 195< 196 !is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value, 197 const _Tp&, 198 _Tp&& 199>::type 200#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 201const _Tp& 202#endif 203move_if_noexcept(_Tp& __x) _NOEXCEPT 204{ 205 return _VSTD::move(__x); 206} 207 208struct _LIBCPP_TYPE_VIS piecewise_construct_t { }; 209#if defined(_LIBCPP_HAS_NO_CONSTEXPR) || defined(_LIBCPP_BUILDING_UTILITY) 210extern const piecewise_construct_t piecewise_construct;// = piecewise_construct_t(); 211#else 212constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t(); 213#endif 214 215template <class _T1, class _T2> 216struct _LIBCPP_TYPE_VIS pair 217{ 218 typedef _T1 first_type; 219 typedef _T2 second_type; 220 221 _T1 first; 222 _T2 second; 223 224 // pair(const pair&) = default; 225 // pair(pair&&) = default; 226 227 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR pair() : first(), second() {} 228 229 _LIBCPP_INLINE_VISIBILITY pair(const _T1& __x, const _T2& __y) 230 : first(__x), second(__y) {} 231 232 template<class _U1, class _U2> 233 _LIBCPP_INLINE_VISIBILITY 234 pair(const pair<_U1, _U2>& __p 235#ifndef _LIBCPP_HAS_NO_ADVANCED_SFINAE 236 ,typename enable_if<is_convertible<const _U1&, _T1>::value && 237 is_convertible<const _U2&, _T2>::value>::type* = 0 238#endif 239 ) 240 : first(__p.first), second(__p.second) {} 241 242 _LIBCPP_INLINE_VISIBILITY 243 pair(const pair& __p) 244 _NOEXCEPT_(is_nothrow_copy_constructible<first_type>::value && 245 is_nothrow_copy_constructible<second_type>::value) 246 : first(__p.first), 247 second(__p.second) 248 { 249 } 250 251 _LIBCPP_INLINE_VISIBILITY 252 pair& operator=(const pair& __p) 253 _NOEXCEPT_(is_nothrow_copy_assignable<first_type>::value && 254 is_nothrow_copy_assignable<second_type>::value) 255 { 256 first = __p.first; 257 second = __p.second; 258 return *this; 259 } 260 261#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 262 263 template <class _U1, class _U2, 264 class = typename enable_if<is_convertible<_U1, first_type>::value && 265 is_convertible<_U2, second_type>::value>::type> 266 _LIBCPP_INLINE_VISIBILITY 267 pair(_U1&& __u1, _U2&& __u2) 268 : first(_VSTD::forward<_U1>(__u1)), 269 second(_VSTD::forward<_U2>(__u2)) 270 {} 271 272 template<class _U1, class _U2> 273 _LIBCPP_INLINE_VISIBILITY 274 pair(pair<_U1, _U2>&& __p, 275 typename enable_if<is_convertible<_U1, _T1>::value && 276 is_convertible<_U2, _T2>::value>::type* = 0) 277 : first(_VSTD::forward<_U1>(__p.first)), 278 second(_VSTD::forward<_U2>(__p.second)) {} 279 280 _LIBCPP_INLINE_VISIBILITY 281 pair(pair&& __p) _NOEXCEPT_(is_nothrow_move_constructible<first_type>::value && 282 is_nothrow_move_constructible<second_type>::value) 283 : first(_VSTD::forward<first_type>(__p.first)), 284 second(_VSTD::forward<second_type>(__p.second)) 285 { 286 } 287 288 _LIBCPP_INLINE_VISIBILITY 289 pair& 290 operator=(pair&& __p) _NOEXCEPT_(is_nothrow_move_assignable<first_type>::value && 291 is_nothrow_move_assignable<second_type>::value) 292 { 293 first = _VSTD::forward<first_type>(__p.first); 294 second = _VSTD::forward<second_type>(__p.second); 295 return *this; 296 } 297 298#ifndef _LIBCPP_HAS_NO_VARIADICS 299 300 template<class _Tuple, 301 class = typename enable_if<__tuple_convertible<_Tuple, pair>::value>::type> 302 _LIBCPP_INLINE_VISIBILITY 303 pair(_Tuple&& __p) 304 : first(_VSTD::forward<typename tuple_element<0, 305 typename __make_tuple_types<_Tuple>::type>::type>(get<0>(__p))), 306 second(_VSTD::forward<typename tuple_element<1, 307 typename __make_tuple_types<_Tuple>::type>::type>(get<1>(__p))) 308 {} 309 310 311 312 template <class... _Args1, class... _Args2> 313 _LIBCPP_INLINE_VISIBILITY 314 pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args, 315 tuple<_Args2...> __second_args) 316 : pair(__pc, __first_args, __second_args, 317 typename __make_tuple_indices<sizeof...(_Args1)>::type(), 318 typename __make_tuple_indices<sizeof...(_Args2) >::type()) 319 {} 320 321 template <class _Tuple, 322 class = typename enable_if<__tuple_assignable<_Tuple, pair>::value>::type> 323 _LIBCPP_INLINE_VISIBILITY 324 pair& 325 operator=(_Tuple&& __p) 326 { 327 typedef typename __make_tuple_types<_Tuple>::type _TupleRef; 328 typedef typename tuple_element<0, _TupleRef>::type _U0; 329 typedef typename tuple_element<1, _TupleRef>::type _U1; 330 first = _VSTD::forward<_U0>(_VSTD::get<0>(__p)); 331 second = _VSTD::forward<_U1>(_VSTD::get<1>(__p)); 332 return *this; 333 } 334 335#endif // _LIBCPP_HAS_NO_VARIADICS 336 337#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 338 _LIBCPP_INLINE_VISIBILITY 339 void 340 swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable<first_type>::value && 341 __is_nothrow_swappable<second_type>::value) 342 { 343 _VSTD::iter_swap(&first, &__p.first); 344 _VSTD::iter_swap(&second, &__p.second); 345 } 346private: 347 348#ifndef _LIBCPP_HAS_NO_VARIADICS 349 template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2> 350 _LIBCPP_INLINE_VISIBILITY 351 pair(piecewise_construct_t, 352 tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args, 353 __tuple_indices<_I1...>, __tuple_indices<_I2...>); 354#endif // _LIBCPP_HAS_NO_VARIADICS 355}; 356 357template <class _T1, class _T2> 358inline _LIBCPP_INLINE_VISIBILITY 359bool 360operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 361{ 362 return __x.first == __y.first && __x.second == __y.second; 363} 364 365template <class _T1, class _T2> 366inline _LIBCPP_INLINE_VISIBILITY 367bool 368operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 369{ 370 return !(__x == __y); 371} 372 373template <class _T1, class _T2> 374inline _LIBCPP_INLINE_VISIBILITY 375bool 376operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 377{ 378 return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second); 379} 380 381template <class _T1, class _T2> 382inline _LIBCPP_INLINE_VISIBILITY 383bool 384operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 385{ 386 return __y < __x; 387} 388 389template <class _T1, class _T2> 390inline _LIBCPP_INLINE_VISIBILITY 391bool 392operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 393{ 394 return !(__x < __y); 395} 396 397template <class _T1, class _T2> 398inline _LIBCPP_INLINE_VISIBILITY 399bool 400operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y) 401{ 402 return !(__y < __x); 403} 404 405template <class _T1, class _T2> 406inline _LIBCPP_INLINE_VISIBILITY 407typename enable_if 408< 409 __is_swappable<_T1>::value && 410 __is_swappable<_T2>::value, 411 void 412>::type 413swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y) 414 _NOEXCEPT_((__is_nothrow_swappable<_T1>::value && 415 __is_nothrow_swappable<_T2>::value)) 416{ 417 __x.swap(__y); 418} 419 420#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 421 422template <class _Tp> class _LIBCPP_TYPE_VIS reference_wrapper; 423 424template <class _Tp> 425struct ___make_pair_return 426{ 427 typedef _Tp type; 428}; 429 430template <class _Tp> 431struct ___make_pair_return<reference_wrapper<_Tp>> 432{ 433 typedef _Tp& type; 434}; 435 436template <class _Tp> 437struct __make_pair_return 438{ 439 typedef typename ___make_pair_return<typename decay<_Tp>::type>::type type; 440}; 441 442template <class _T1, class _T2> 443inline _LIBCPP_INLINE_VISIBILITY 444pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type> 445make_pair(_T1&& __t1, _T2&& __t2) 446{ 447 return pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type> 448 (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2)); 449} 450 451#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 452 453template <class _T1, class _T2> 454inline _LIBCPP_INLINE_VISIBILITY 455pair<_T1,_T2> 456make_pair(_T1 __x, _T2 __y) 457{ 458 return pair<_T1, _T2>(__x, __y); 459} 460 461#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 462 463template <class _T1, class _T2> 464 class _LIBCPP_TYPE_VIS tuple_size<pair<_T1, _T2> > 465 : public integral_constant<size_t, 2> {}; 466 467template <class _T1, class _T2> 468 class _LIBCPP_TYPE_VIS tuple_size<const pair<_T1, _T2> > 469 : public integral_constant<size_t, 2> {}; 470 471template <class _T1, class _T2> 472class _LIBCPP_TYPE_VIS tuple_element<0, pair<_T1, _T2> > 473{ 474public: 475 typedef _T1 type; 476}; 477 478template <class _T1, class _T2> 479class _LIBCPP_TYPE_VIS tuple_element<1, pair<_T1, _T2> > 480{ 481public: 482 typedef _T2 type; 483}; 484 485template <class _T1, class _T2> 486class _LIBCPP_TYPE_VIS tuple_element<0, const pair<_T1, _T2> > 487{ 488public: 489 typedef const _T1 type; 490}; 491 492template <class _T1, class _T2> 493class _LIBCPP_TYPE_VIS tuple_element<1, const pair<_T1, _T2> > 494{ 495public: 496 typedef const _T2 type; 497}; 498 499template <size_t _Ip> struct __get_pair; 500 501template <> 502struct __get_pair<0> 503{ 504 template <class _T1, class _T2> 505 static 506 _LIBCPP_INLINE_VISIBILITY 507 _T1& 508 get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} 509 510 template <class _T1, class _T2> 511 static 512 _LIBCPP_INLINE_VISIBILITY 513 const _T1& 514 get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;} 515 516#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 517 518 template <class _T1, class _T2> 519 static 520 _LIBCPP_INLINE_VISIBILITY 521 _T1&& 522 get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);} 523 524#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 525}; 526 527template <> 528struct __get_pair<1> 529{ 530 template <class _T1, class _T2> 531 static 532 _LIBCPP_INLINE_VISIBILITY 533 _T2& 534 get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} 535 536 template <class _T1, class _T2> 537 static 538 _LIBCPP_INLINE_VISIBILITY 539 const _T2& 540 get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;} 541 542#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 543 544 template <class _T1, class _T2> 545 static 546 _LIBCPP_INLINE_VISIBILITY 547 _T2&& 548 get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);} 549 550#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 551}; 552 553template <size_t _Ip, class _T1, class _T2> 554_LIBCPP_INLINE_VISIBILITY inline 555typename tuple_element<_Ip, pair<_T1, _T2> >::type& 556get(pair<_T1, _T2>& __p) _NOEXCEPT 557{ 558 return __get_pair<_Ip>::get(__p); 559} 560 561template <size_t _Ip, class _T1, class _T2> 562_LIBCPP_INLINE_VISIBILITY inline 563const typename tuple_element<_Ip, pair<_T1, _T2> >::type& 564get(const pair<_T1, _T2>& __p) _NOEXCEPT 565{ 566 return __get_pair<_Ip>::get(__p); 567} 568 569#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 570 571template <size_t _Ip, class _T1, class _T2> 572_LIBCPP_INLINE_VISIBILITY inline 573typename tuple_element<_Ip, pair<_T1, _T2> >::type&& 574get(pair<_T1, _T2>&& __p) _NOEXCEPT 575{ 576 return __get_pair<_Ip>::get(_VSTD::move(__p)); 577} 578 579#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 580 581_LIBCPP_END_NAMESPACE_STD 582 583#endif // _LIBCPP_UTILITY 584