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 #include <initializer_list>
  18
  19 namespace std
  20 {
  21
  22 template <class T>
  23     void
  24     swap(T& a, T& b);
  25
  26 namespace rel_ops
  27 {
  28     template<class T> bool operator!=(const T&, const T&);
  29     template<class T> bool operator> (const T&, const T&);
  30     template<class T> bool operator<=(const T&, const T&);
  31     template<class T> bool operator>=(const T&, const T&);
  32 }
  33
  34 template<class T>
  35 void
  36 swap(T& a, T& b) noexcept(is_nothrow_move_constructible<T>::value &&
  37                           is_nothrow_move_assignable<T>::value);
  38
  39 template <class T, size_t N>
  40 void
  41 swap(T (&a)[N], T (&b)[N]) noexcept(noexcept(swap(*a, *b)));
  42
  43 template <class T> T&& forward(typename remove_reference<T>::type& t) noexcept;  // constexpr in C++14
  44 template <class T> T&& forward(typename remove_reference<T>::type&& t) noexcept; // constexpr in C++14
  45
  46 template <class T> typename remove_reference<T>::type&& move(T&&) noexcept;      // constexpr in C++14
  47
  48 template <class T>
  49     typename conditional
  50     <
  51         !is_nothrow_move_constructible<T>::value && is_copy_constructible<T>::value,
  52         const T&,
  53         T&&
  54     >::type
  55     move_if_noexcept(T& x) noexcept; // constexpr in C++14
  56
  57 template <class T> constexpr add_const_t<T>& as_const(T& t) noexcept;      // C++17
  58 template <class T>                      void as_const(const T&&) = delete; // C++17
  59
  60 template <class T> typename add_rvalue_reference<T>::type declval() noexcept;
  61
  62 template <class T1, class T2>
  63 struct pair
  64 {
  65     typedef T1 first_type;
  66     typedef T2 second_type;
  67
  68     T1 first;
  69     T2 second;
  70
  71     pair(const pair&) = default;
  72     pair(pair&&) = default;
  73     constexpr pair();
  74     pair(const T1& x, const T2& y);                          // constexpr in C++14
  75     template <class U, class V> pair(U&& x, V&& y);          // constexpr in C++14
  76     template <class U, class V> pair(const pair<U, V>& p);   // constexpr in C++14
  77     template <class U, class V> pair(pair<U, V>&& p);        // constexpr in C++14
  78     template <class... Args1, class... Args2>
  79         pair(piecewise_construct_t, tuple<Args1...> first_args,
  80              tuple<Args2...> second_args);
  81
  82     template <class U, class V> pair& operator=(const pair<U, V>& p);
  83     pair& operator=(pair&& p) noexcept(is_nothrow_move_assignable<T1>::value &&
  84                                        is_nothrow_move_assignable<T2>::value);
  85     template <class U, class V> pair& operator=(pair<U, V>&& p);
  86
  87     void swap(pair& p) noexcept(is_nothrow_swappable_v<T1> &&
  88                                 is_nothrow_swappable_v<T2>);
  89 };
  90
  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 template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
  96 template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
  97
  98 template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&);   // constexpr in C++14
  99 template <class T1, class T2>
 100 void
 101 swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y)));
 102
 103 struct piecewise_construct_t { };
 104 inline constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
 105
 106 template <class T> struct tuple_size;
 107 template <size_t I, class T> class tuple_element;
 108
 109 template <class T1, class T2> struct tuple_size<pair<T1, T2> >;
 110 template <class T1, class T2> struct tuple_element<0, pair<T1, T2> >;
 111 template <class T1, class T2> struct tuple_element<1, pair<T1, T2> >;
 112
 113 template<size_t I, class T1, class T2>
 114     typename tuple_element<I, pair<T1, T2> >::type&
 115     get(pair<T1, T2>&) noexcept; // constexpr in C++14
 116
 117 template<size_t I, class T1, class T2>
 118     const typename tuple_element<I, pair<T1, T2> >::type&
 119     get(const pair<T1, T2>&) noexcept; // constexpr in C++14
 120
 121 template<size_t I, class T1, class T2>
 122     typename tuple_element<I, pair<T1, T2> >::type&&
 123     get(pair<T1, T2>&&) noexcept; // constexpr in C++14
 124
 125 template<size_t I, class T1, class T2>
 126     const typename tuple_element<I, pair<T1, T2> >::type&&
 127     get(const pair<T1, T2>&&) noexcept; // constexpr in C++14
 128
 129 template<class T1, class T2>
 130     constexpr T1& get(pair<T1, T2>&) noexcept; // C++14
 131
 132 template<class T1, class T2>
 133     constexpr const T1& get(const pair<T1, T2>&) noexcept; // C++14
 134
 135 template<class T1, class T2>
 136     constexpr T1&& get(pair<T1, T2>&&) noexcept; // C++14
 137
 138 template<class T1, class T2>
 139     constexpr const T1&& get(const pair<T1, T2>&&) noexcept; // C++14
 140
 141 template<class T1, class T2>
 142     constexpr T1& get(pair<T2, T1>&) noexcept; // C++14
 143
 144 template<class T1, class T2>
 145     constexpr const T1& get(const pair<T2, T1>&) noexcept; // C++14
 146
 147 template<class T1, class T2>
 148     constexpr T1&& get(pair<T2, T1>&&) noexcept; // C++14
 149
 150 template<class T1, class T2>
 151     constexpr const T1&& get(const pair<T2, T1>&&) noexcept; // C++14
 152
 153 // C++14
 154
 155 template<class T, T... I>
 156 struct integer_sequence
 157 {
 158     typedef T value_type;
 159
 160     static constexpr size_t size() noexcept;
 161 };
 162
 163 template<size_t... I>
 164   using index_sequence = integer_sequence<size_t, I...>;
 165
 166 template<class T, T N>
 167   using make_integer_sequence = integer_sequence<T, 0, 1, ..., N-1>;
 168 template<size_t N>
 169   using make_index_sequence = make_integer_sequence<size_t, N>;
 170
 171 template<class... T>
 172   using index_sequence_for = make_index_sequence<sizeof...(T)>;
 173
 174 template<class T, class U=T>
 175     T exchange(T& obj, U&& new_value);
 176
 177 // 20.2.7, in-place construction // C++17
 178 struct in_place_t {
 179   explicit in_place_t() = default;
 180 };
 181 inline constexpr in_place_t in_place{};
 182 template <class T>
 183   struct in_place_type_t {
 184     explicit in_place_type_t() = default;
 185   };
 186 template <class T>
 187   inline constexpr in_place_type_t<T> in_place_type{};
 188 template <size_t I>
 189   struct in_place_index_t {
 190     explicit in_place_index_t() = default;
 191   };
 192 template <size_t I>
 193   inline constexpr in_place_index_t<I> in_place_index{};
 194
 195 }  // std
 196
 197 */
 198
 199 #include <__config>
 200 #include <__tuple>
 201 #include <type_traits>
 202 #include <initializer_list>
 203 #include <cstddef>
 204 #include <cstring>
 205 #include <cstdint>
 206 #include <version>
 207 #include <__debug>
 208
 209 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 210 #pragma GCC system_header
 211 #endif
 212
 213 _LIBCPP_BEGIN_NAMESPACE_STD
 214
 215 namespace rel_ops
 216 {
 217
 218 template<class _Tp>
 219 inline _LIBCPP_INLINE_VISIBILITY
 220 bool
 221 operator!=(const _Tp& __x, const _Tp& __y)
 222 {
 223     return !(__x == __y);
 224 }
 225
 226 template<class _Tp>
 227 inline _LIBCPP_INLINE_VISIBILITY
 228 bool
 229 operator> (const _Tp& __x, const _Tp& __y)
 230 {
 231     return __y < __x;
 232 }
 233
 234 template<class _Tp>
 235 inline _LIBCPP_INLINE_VISIBILITY
 236 bool
 237 operator<=(const _Tp& __x, const _Tp& __y)
 238 {
 239     return !(__y < __x);
 240 }
 241
 242 template<class _Tp>
 243 inline _LIBCPP_INLINE_VISIBILITY
 244 bool
 245 operator>=(const _Tp& __x, const _Tp& __y)
 246 {
 247     return !(__x < __y);
 248 }
 249
 250 }  // rel_ops
 251
 252 // swap_ranges
 253
 254
 255 template <class _ForwardIterator1, class _ForwardIterator2>
 256 inline _LIBCPP_INLINE_VISIBILITY
 257 _ForwardIterator2
 258 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
 259 {
 260     for(; __first1 != __last1; ++__first1, (void) ++__first2)
 261         swap(*__first1, *__first2);
 262     return __first2;
 263 }
 264
 265 // forward declared in <type_traits>
 266 template<class _Tp, size_t _Np>
 267 inline _LIBCPP_INLINE_VISIBILITY
 268 typename enable_if<
 269     __is_swappable<_Tp>::value
 270 >::type
 271 swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value)
 272 {
 273     _VSTD::swap_ranges(__a, __a + _Np, __b);
 274 }
 275
 276 template <class _Tp>
 277 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 278 #ifndef _LIBCPP_CXX03_LANG
 279 typename conditional
 280 <
 281     !is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value,
 282     const _Tp&,
 283     _Tp&&
 284 >::type
 285 #else  // _LIBCPP_CXX03_LANG
 286 const _Tp&
 287 #endif
 288 move_if_noexcept(_Tp& __x) _NOEXCEPT
 289 {
 290     return _VSTD::move(__x);
 291 }
 292
 293 #if _LIBCPP_STD_VER > 14
 294 template <class _Tp> constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; }
 295 template <class _Tp>                        void as_const(const _Tp&&) = delete;
 296 #endif
 297
 298 struct _LIBCPP_TEMPLATE_VIS piecewise_construct_t { };
 299 #if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY)
 300 extern _LIBCPP_EXPORTED_FROM_ABI const piecewise_construct_t piecewise_construct;// = piecewise_construct_t();
 301 #else
 302 /* _LIBCPP_INLINE_VAR */ constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
 303 #endif
 304
 305 #if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR)
 306 template <class, class>
 307 struct __non_trivially_copyable_base {
 308   _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
 309   __non_trivially_copyable_base() _NOEXCEPT {}
 310   _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
 311   __non_trivially_copyable_base(__non_trivially_copyable_base const&) _NOEXCEPT {}
 312 };
 313 #endif
 314
 315 template <class _T1, class _T2>
 316 struct _LIBCPP_TEMPLATE_VIS pair
 317 #if defined(_LIBCPP_DEPRECATED_ABI_DISABLE_PAIR_TRIVIAL_COPY_CTOR)
 318 : private __non_trivially_copyable_base<_T1, _T2>
 319 #endif
 320 {
 321     typedef _T1 first_type;
 322     typedef _T2 second_type;
 323
 324     _T1 first;
 325     _T2 second;
 326
 327 #if !defined(_LIBCPP_CXX03_LANG)
 328     pair(pair const&) = default;
 329     pair(pair&&) = default;
 330 #else
 331   // Use the implicitly declared copy constructor in C++03
 332 #endif
 333
 334 #ifdef _LIBCPP_CXX03_LANG
 335     _LIBCPP_INLINE_VISIBILITY
 336     pair() : first(), second() {}
 337
 338     _LIBCPP_INLINE_VISIBILITY
 339     pair(_T1 const& __t1, _T2 const& __t2) : first(__t1), second(__t2) {}
 340
 341     template <class _U1, class _U2>
 342     _LIBCPP_INLINE_VISIBILITY
 343     pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
 344
 345     _LIBCPP_INLINE_VISIBILITY
 346     pair& operator=(pair const& __p) {
 347         first = __p.first;
 348         second = __p.second;
 349         return *this;
 350     }
 351 #else
 352     template <bool _Val>
 353     using _EnableB = typename enable_if<_Val, bool>::type;
 354
 355     struct _CheckArgs {
 356       template <class _U1, class _U2>
 357       static constexpr bool __enable_default() {
 358           return is_default_constructible<_U1>::value
 359               && is_default_constructible<_U2>::value;
 360       }
 361
 362       template <class _U1, class _U2>
 363       static constexpr bool __enable_explicit() {
 364           return is_constructible<first_type, _U1>::value
 365               && is_constructible<second_type, _U2>::value
 366               && (!is_convertible<_U1, first_type>::value
 367                   || !is_convertible<_U2, second_type>::value);
 368       }
 369
 370       template <class _U1, class _U2>
 371       static constexpr bool __enable_implicit() {
 372           return is_constructible<first_type, _U1>::value
 373               && is_constructible<second_type, _U2>::value
 374               && is_convertible<_U1, first_type>::value
 375               && is_convertible<_U2, second_type>::value;
 376       }
 377     };
 378
 379     template <bool _MaybeEnable>
 380     using _CheckArgsDep = typename conditional<
 381       _MaybeEnable, _CheckArgs, __check_tuple_constructor_fail>::type;
 382
 383     struct _CheckTupleLikeConstructor {
 384         template <class _Tuple>
 385         static constexpr bool __enable_implicit() {
 386             return __tuple_convertible<_Tuple, pair>::value;
 387         }
 388
 389         template <class _Tuple>
 390         static constexpr bool __enable_explicit() {
 391             return __tuple_constructible<_Tuple, pair>::value
 392                && !__tuple_convertible<_Tuple, pair>::value;
 393         }
 394
 395         template <class _Tuple>
 396         static constexpr bool __enable_assign() {
 397             return __tuple_assignable<_Tuple, pair>::value;
 398         }
 399     };
 400
 401     template <class _Tuple>
 402     using _CheckTLC = typename conditional<
 403         __tuple_like_with_size<_Tuple, 2>::value
 404             && !is_same<typename decay<_Tuple>::type, pair>::value,
 405         _CheckTupleLikeConstructor,
 406         __check_tuple_constructor_fail
 407     >::type;
 408
 409     template<bool _Dummy = true, _EnableB<
 410             _CheckArgsDep<_Dummy>::template __enable_default<_T1, _T2>()
 411     > = false>
 412     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
 413     pair() _NOEXCEPT_(is_nothrow_default_constructible<first_type>::value &&
 414                       is_nothrow_default_constructible<second_type>::value)
 415         : first(), second() {}
 416
 417     template <bool _Dummy = true, _EnableB<
 418              _CheckArgsDep<_Dummy>::template __enable_explicit<_T1 const&, _T2 const&>()
 419     > = false>
 420     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 421     explicit pair(_T1 const& __t1, _T2 const& __t2)
 422         _NOEXCEPT_(is_nothrow_copy_constructible<first_type>::value &&
 423                    is_nothrow_copy_constructible<second_type>::value)
 424         : first(__t1), second(__t2) {}
 425
 426     template<bool _Dummy = true, _EnableB<
 427             _CheckArgsDep<_Dummy>::template __enable_implicit<_T1 const&, _T2 const&>()
 428     > = false>
 429     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 430     pair(_T1 const& __t1, _T2 const& __t2)
 431         _NOEXCEPT_(is_nothrow_copy_constructible<first_type>::value &&
 432                    is_nothrow_copy_constructible<second_type>::value)
 433         : first(__t1), second(__t2) {}
 434
 435     template<class _U1, class _U2, _EnableB<
 436              _CheckArgs::template __enable_explicit<_U1, _U2>()
 437     > = false>
 438     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 439     explicit pair(_U1&& __u1, _U2&& __u2)
 440         _NOEXCEPT_((is_nothrow_constructible<first_type, _U1>::value &&
 441                     is_nothrow_constructible<second_type, _U2>::value))
 442         : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {}
 443
 444     template<class _U1, class _U2, _EnableB<
 445             _CheckArgs::template __enable_implicit<_U1, _U2>()
 446     > = false>
 447     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 448     pair(_U1&& __u1, _U2&& __u2)
 449         _NOEXCEPT_((is_nothrow_constructible<first_type, _U1>::value &&
 450                     is_nothrow_constructible<second_type, _U2>::value))
 451         : first(_VSTD::forward<_U1>(__u1)), second(_VSTD::forward<_U2>(__u2)) {}
 452
 453     template<class _U1, class _U2, _EnableB<
 454             _CheckArgs::template __enable_explicit<_U1 const&, _U2 const&>()
 455     > = false>
 456     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 457     explicit pair(pair<_U1, _U2> const& __p)
 458         _NOEXCEPT_((is_nothrow_constructible<first_type, _U1 const&>::value &&
 459                     is_nothrow_constructible<second_type, _U2 const&>::value))
 460         : first(__p.first), second(__p.second) {}
 461
 462     template<class _U1, class _U2, _EnableB<
 463             _CheckArgs::template __enable_implicit<_U1 const&, _U2 const&>()
 464     > = false>
 465     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 466     pair(pair<_U1, _U2> const& __p)
 467         _NOEXCEPT_((is_nothrow_constructible<first_type, _U1 const&>::value &&
 468                     is_nothrow_constructible<second_type, _U2 const&>::value))
 469         : first(__p.first), second(__p.second) {}
 470
 471     template<class _U1, class _U2, _EnableB<
 472             _CheckArgs::template __enable_explicit<_U1, _U2>()
 473     > = false>
 474     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 475     explicit pair(pair<_U1, _U2>&&__p)
 476         _NOEXCEPT_((is_nothrow_constructible<first_type, _U1&&>::value &&
 477                     is_nothrow_constructible<second_type, _U2&&>::value))
 478         : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {}
 479
 480     template<class _U1, class _U2, _EnableB<
 481             _CheckArgs::template __enable_implicit<_U1, _U2>()
 482     > = false>
 483     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 484     pair(pair<_U1, _U2>&& __p)
 485         _NOEXCEPT_((is_nothrow_constructible<first_type, _U1&&>::value &&
 486                     is_nothrow_constructible<second_type, _U2&&>::value))
 487         : first(_VSTD::forward<_U1>(__p.first)), second(_VSTD::forward<_U2>(__p.second)) {}
 488
 489     template<class _Tuple, _EnableB<
 490             _CheckTLC<_Tuple>::template __enable_explicit<_Tuple>()
 491     > = false>
 492     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 493     explicit pair(_Tuple&& __p)
 494         : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))),
 495           second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {}
 496
 497     template<class _Tuple, _EnableB<
 498             _CheckTLC<_Tuple>::template __enable_implicit<_Tuple>()
 499     > = false>
 500     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 501     pair(_Tuple&& __p)
 502         : first(_VSTD::get<0>(_VSTD::forward<_Tuple>(__p))),
 503           second(_VSTD::get<1>(_VSTD::forward<_Tuple>(__p))) {}
 504
 505     template <class... _Args1, class... _Args2>
 506     _LIBCPP_INLINE_VISIBILITY
 507     pair(piecewise_construct_t __pc,
 508          tuple<_Args1...> __first_args, tuple<_Args2...> __second_args)
 509         _NOEXCEPT_((is_nothrow_constructible<first_type, _Args1...>::value &&
 510                     is_nothrow_constructible<second_type, _Args2...>::value))
 511         : pair(__pc, __first_args, __second_args,
 512                 typename __make_tuple_indices<sizeof...(_Args1)>::type(),
 513                 typename __make_tuple_indices<sizeof...(_Args2) >::type()) {}
 514
 515     _LIBCPP_INLINE_VISIBILITY
 516     pair& operator=(typename conditional<
 517                         is_copy_assignable<first_type>::value &&
 518                         is_copy_assignable<second_type>::value,
 519                     pair, __nat>::type const& __p)
 520         _NOEXCEPT_(is_nothrow_copy_assignable<first_type>::value &&
 521                    is_nothrow_copy_assignable<second_type>::value)
 522     {
 523         first = __p.first;
 524         second = __p.second;
 525         return *this;
 526     }
 527
 528     _LIBCPP_INLINE_VISIBILITY
 529     pair& operator=(typename conditional<
 530                         is_move_assignable<first_type>::value &&
 531                         is_move_assignable<second_type>::value,
 532                     pair, __nat>::type&& __p)
 533         _NOEXCEPT_(is_nothrow_move_assignable<first_type>::value &&
 534                    is_nothrow_move_assignable<second_type>::value)
 535     {
 536         first = _VSTD::forward<first_type>(__p.first);
 537         second = _VSTD::forward<second_type>(__p.second);
 538         return *this;
 539     }
 540
 541     template <class _Tuple, _EnableB<
 542             _CheckTLC<_Tuple>::template __enable_assign<_Tuple>()
 543      > = false>
 544     _LIBCPP_INLINE_VISIBILITY
 545     pair& operator=(_Tuple&& __p) {
 546         first = _VSTD::get<0>(_VSTD::forward<_Tuple>(__p));
 547         second = _VSTD::get<1>(_VSTD::forward<_Tuple>(__p));
 548         return *this;
 549     }
 550 #endif
 551
 552     _LIBCPP_INLINE_VISIBILITY
 553     void
 554     swap(pair& __p) _NOEXCEPT_(__is_nothrow_swappable<first_type>::value &&
 555                                __is_nothrow_swappable<second_type>::value)
 556     {
 557         using _VSTD::swap;
 558         swap(first,  __p.first);
 559         swap(second, __p.second);
 560     }
 561 private:
 562
 563 #ifndef _LIBCPP_CXX03_LANG
 564     template <class... _Args1, class... _Args2, size_t... _I1, size_t... _I2>
 565         _LIBCPP_INLINE_VISIBILITY
 566         pair(piecewise_construct_t,
 567              tuple<_Args1...>& __first_args, tuple<_Args2...>& __second_args,
 568              __tuple_indices<_I1...>, __tuple_indices<_I2...>);
 569 #endif
 570 };
 571
 572 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
 573 template<class _T1, class _T2>
 574 pair(_T1, _T2) -> pair<_T1, _T2>;
 575 #endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES
 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.first == __y.first && __x.second == __y.second;
 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 !(__x == __y);
 591 }
 592
 593 template <class _T1, class _T2>
 594 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 595 bool
 596 operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 597 {
 598     return __x.first < __y.first || (!(__y.first < __x.first) && __x.second < __y.second);
 599 }
 600
 601 template <class _T1, class _T2>
 602 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 603 bool
 604 operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 605 {
 606     return __y < __x;
 607 }
 608
 609 template <class _T1, class _T2>
 610 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 611 bool
 612 operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 613 {
 614     return !(__x < __y);
 615 }
 616
 617 template <class _T1, class _T2>
 618 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 619 bool
 620 operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
 621 {
 622     return !(__y < __x);
 623 }
 624
 625 template <class _T1, class _T2>
 626 inline _LIBCPP_INLINE_VISIBILITY
 627 typename enable_if
 628 <
 629     __is_swappable<_T1>::value &&
 630     __is_swappable<_T2>::value,
 631     void
 632 >::type
 633 swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y)
 634                      _NOEXCEPT_((__is_nothrow_swappable<_T1>::value &&
 635                                  __is_nothrow_swappable<_T2>::value))
 636 {
 637     __x.swap(__y);
 638 }
 639
 640 template <class _Tp>
 641 struct __unwrap_reference { typedef _Tp type; };
 642
 643 template <class _Tp>
 644 struct __unwrap_reference<reference_wrapper<_Tp> > { typedef _Tp& type; };
 645
 646 #if _LIBCPP_STD_VER > 17
 647 template <class _Tp>
 648 struct unwrap_reference : __unwrap_reference<_Tp> { };
 649
 650 template <class _Tp>
 651 struct unwrap_ref_decay : unwrap_reference<typename decay<_Tp>::type> { };
 652 #endif // > C++17
 653
 654 template <class _Tp>
 655 struct __unwrap_ref_decay
 656 #if _LIBCPP_STD_VER > 17
 657     : unwrap_ref_decay<_Tp>
 658 #else
 659     : __unwrap_reference<typename decay<_Tp>::type>
 660 #endif
 661 { };
 662
 663 #ifndef _LIBCPP_CXX03_LANG
 664
 665 template <class _T1, class _T2>
 666 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 667 pair<typename __unwrap_ref_decay<_T1>::type, typename __unwrap_ref_decay<_T2>::type>
 668 make_pair(_T1&& __t1, _T2&& __t2)
 669 {
 670     return pair<typename __unwrap_ref_decay<_T1>::type, typename __unwrap_ref_decay<_T2>::type>
 671                (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2));
 672 }
 673
 674 #else  // _LIBCPP_CXX03_LANG
 675
 676 template <class _T1, class _T2>
 677 inline _LIBCPP_INLINE_VISIBILITY
 678 pair<_T1,_T2>
 679 make_pair(_T1 __x, _T2 __y)
 680 {
 681     return pair<_T1, _T2>(__x, __y);
 682 }
 683
 684 #endif  // _LIBCPP_CXX03_LANG
 685
 686 template <class _T1, class _T2>
 687   struct _LIBCPP_TEMPLATE_VIS tuple_size<pair<_T1, _T2> >
 688     : public integral_constant<size_t, 2> {};
 689
 690 template <size_t _Ip, class _T1, class _T2>
 691 class _LIBCPP_TEMPLATE_VIS tuple_element<_Ip, pair<_T1, _T2> >
 692 {
 693     static_assert(_Ip < 2, "Index out of bounds in std::tuple_element<std::pair<T1, T2>>");
 694 };
 695
 696 template <class _T1, class _T2>
 697 class _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> >
 698 {
 699 public:
 700     typedef _T1 type;
 701 };
 702
 703 template <class _T1, class _T2>
 704 class _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> >
 705 {
 706 public:
 707     typedef _T2 type;
 708 };
 709
 710 template <size_t _Ip> struct __get_pair;
 711
 712 template <>
 713 struct __get_pair<0>
 714 {
 715     template <class _T1, class _T2>
 716     static
 717     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 718     _T1&
 719     get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
 720
 721     template <class _T1, class _T2>
 722     static
 723     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 724     const _T1&
 725     get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
 726
 727 #ifndef _LIBCPP_CXX03_LANG
 728     template <class _T1, class _T2>
 729     static
 730     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 731     _T1&&
 732     get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);}
 733
 734     template <class _T1, class _T2>
 735     static
 736     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 737     const _T1&&
 738     get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T1>(__p.first);}
 739 #endif  // _LIBCPP_CXX03_LANG
 740 };
 741
 742 template <>
 743 struct __get_pair<1>
 744 {
 745     template <class _T1, class _T2>
 746     static
 747     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 748     _T2&
 749     get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
 750
 751     template <class _T1, class _T2>
 752     static
 753     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 754     const _T2&
 755     get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
 756
 757 #ifndef _LIBCPP_CXX03_LANG
 758     template <class _T1, class _T2>
 759     static
 760     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 761     _T2&&
 762     get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);}
 763
 764     template <class _T1, class _T2>
 765     static
 766     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 767     const _T2&&
 768     get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T2>(__p.second);}
 769 #endif  // _LIBCPP_CXX03_LANG
 770 };
 771
 772 template <size_t _Ip, class _T1, class _T2>
 773 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 774 typename tuple_element<_Ip, pair<_T1, _T2> >::type&
 775 get(pair<_T1, _T2>& __p) _NOEXCEPT
 776 {
 777     return __get_pair<_Ip>::get(__p);
 778 }
 779
 780 template <size_t _Ip, class _T1, class _T2>
 781 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 782 const typename tuple_element<_Ip, pair<_T1, _T2> >::type&
 783 get(const pair<_T1, _T2>& __p) _NOEXCEPT
 784 {
 785     return __get_pair<_Ip>::get(__p);
 786 }
 787
 788 #ifndef _LIBCPP_CXX03_LANG
 789 template <size_t _Ip, class _T1, class _T2>
 790 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 791 typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
 792 get(pair<_T1, _T2>&& __p) _NOEXCEPT
 793 {
 794     return __get_pair<_Ip>::get(_VSTD::move(__p));
 795 }
 796
 797 template <size_t _Ip, class _T1, class _T2>
 798 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 799 const typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
 800 get(const pair<_T1, _T2>&& __p) _NOEXCEPT
 801 {
 802     return __get_pair<_Ip>::get(_VSTD::move(__p));
 803 }
 804 #endif  // _LIBCPP_CXX03_LANG
 805
 806 #if _LIBCPP_STD_VER > 11
 807 template <class _T1, class _T2>
 808 inline _LIBCPP_INLINE_VISIBILITY
 809 constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT
 810 {
 811     return __get_pair<0>::get(__p);
 812 }
 813
 814 template <class _T1, class _T2>
 815 inline _LIBCPP_INLINE_VISIBILITY
 816 constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT
 817 {
 818     return __get_pair<0>::get(__p);
 819 }
 820
 821 template <class _T1, class _T2>
 822 inline _LIBCPP_INLINE_VISIBILITY
 823 constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT
 824 {
 825     return __get_pair<0>::get(_VSTD::move(__p));
 826 }
 827
 828 template <class _T1, class _T2>
 829 inline _LIBCPP_INLINE_VISIBILITY
 830 constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT
 831 {
 832     return __get_pair<0>::get(_VSTD::move(__p));
 833 }
 834
 835 template <class _T1, class _T2>
 836 inline _LIBCPP_INLINE_VISIBILITY
 837 constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT
 838 {
 839     return __get_pair<1>::get(__p);
 840 }
 841
 842 template <class _T1, class _T2>
 843 inline _LIBCPP_INLINE_VISIBILITY
 844 constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT
 845 {
 846     return __get_pair<1>::get(__p);
 847 }
 848
 849 template <class _T1, class _T2>
 850 inline _LIBCPP_INLINE_VISIBILITY
 851 constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT
 852 {
 853     return __get_pair<1>::get(_VSTD::move(__p));
 854 }
 855
 856 template <class _T1, class _T2>
 857 inline _LIBCPP_INLINE_VISIBILITY
 858 constexpr _T1 const && get(pair<_T2, _T1> const&& __p) _NOEXCEPT
 859 {
 860     return __get_pair<1>::get(_VSTD::move(__p));
 861 }
 862
 863 #endif
 864
 865 #if _LIBCPP_STD_VER > 11
 866
 867 template<class _Tp, _Tp... _Ip>
 868 struct _LIBCPP_TEMPLATE_VIS integer_sequence
 869 {
 870     typedef _Tp value_type;
 871     static_assert( is_integral<_Tp>::value,
 872                   "std::integer_sequence can only be instantiated with an integral type" );
 873     static
 874     _LIBCPP_INLINE_VISIBILITY
 875     constexpr
 876     size_t
 877     size() noexcept { return sizeof...(_Ip); }
 878 };
 879
 880 template<size_t... _Ip>
 881     using index_sequence = integer_sequence<size_t, _Ip...>;
 882
 883 #if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE)
 884
 885 template <class _Tp, _Tp _Ep>
 886 using __make_integer_sequence = __make_integer_seq<integer_sequence, _Tp, _Ep>;
 887
 888 #else
 889
 890 template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked =
 891   typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>;
 892
 893 template <class _Tp, _Tp _Ep>
 894 struct __make_integer_sequence_checked
 895 {
 896     static_assert(is_integral<_Tp>::value,
 897                   "std::make_integer_sequence can only be instantiated with an integral type" );
 898     static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length");
 899     // Workaround GCC bug by preventing bad installations when 0 <= _Ep
 900     // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929
 901     typedef __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type;
 902 };
 903
 904 template <class _Tp, _Tp _Ep>
 905 using __make_integer_sequence = typename __make_integer_sequence_checked<_Tp, _Ep>::type;
 906
 907 #endif
 908
 909 template<class _Tp, _Tp _Np>
 910     using make_integer_sequence = __make_integer_sequence<_Tp, _Np>;
 911
 912 template<size_t _Np>
 913     using make_index_sequence = make_integer_sequence<size_t, _Np>;
 914
 915 template<class... _Tp>
 916     using index_sequence_for = make_index_sequence<sizeof...(_Tp)>;
 917
 918 #endif  // _LIBCPP_STD_VER > 11
 919
 920 #if _LIBCPP_STD_VER > 11
 921 template<class _T1, class _T2 = _T1>
 922 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 923 _T1 exchange(_T1& __obj, _T2 && __new_value)
 924 {
 925     _T1 __old_value = _VSTD::move(__obj);
 926     __obj = _VSTD::forward<_T2>(__new_value);
 927     return __old_value;
 928 }
 929 #endif  // _LIBCPP_STD_VER > 11
 930
 931 #if _LIBCPP_STD_VER > 14
 932
 933 struct _LIBCPP_TYPE_VIS in_place_t {
 934     explicit in_place_t() = default;
 935 };
 936 _LIBCPP_INLINE_VAR constexpr in_place_t in_place{};
 937
 938 template <class _Tp>
 939 struct _LIBCPP_TEMPLATE_VIS in_place_type_t {
 940     explicit in_place_type_t() = default;
 941 };
 942 template <class _Tp>
 943 _LIBCPP_INLINE_VAR constexpr in_place_type_t<_Tp> in_place_type{};
 944
 945 template <size_t _Idx>
 946 struct _LIBCPP_TYPE_VIS in_place_index_t {
 947     explicit in_place_index_t() = default;
 948 };
 949 template <size_t _Idx>
 950 _LIBCPP_INLINE_VAR constexpr in_place_index_t<_Idx> in_place_index{};
 951
 952 template <class _Tp> struct __is_inplace_type_imp : false_type {};
 953 template <class _Tp> struct __is_inplace_type_imp<in_place_type_t<_Tp>> : true_type {};
 954
 955 template <class _Tp>
 956 using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>;
 957
 958 template <class _Tp> struct __is_inplace_index_imp : false_type {};
 959 template <size_t _Idx> struct __is_inplace_index_imp<in_place_index_t<_Idx>> : true_type {};
 960
 961 template <class _Tp>
 962 using __is_inplace_index = __is_inplace_index_imp<__uncvref_t<_Tp>>;
 963
 964 #endif // _LIBCPP_STD_VER > 14
 965
 966 template <class _Arg, class _Result>
 967 struct _LIBCPP_TEMPLATE_VIS unary_function
 968 {
 969     typedef _Arg    argument_type;
 970     typedef _Result result_type;
 971 };
 972
 973 template <class _Size>
 974 inline _LIBCPP_INLINE_VISIBILITY
 975 _Size
 976 __loadword(const void* __p)
 977 {
 978     _Size __r;
 979     std::memcpy(&__r, __p, sizeof(__r));
 980     return __r;
 981 }
 982
 983 // We use murmur2 when size_t is 32 bits, and cityhash64 when size_t
 984 // is 64 bits.  This is because cityhash64 uses 64bit x 64bit
 985 // multiplication, which can be very slow on 32-bit systems.
 986 template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__>
 987 struct __murmur2_or_cityhash;
 988
 989 template <class _Size>
 990 struct __murmur2_or_cityhash<_Size, 32>
 991 {
 992     inline _Size operator()(const void* __key, _Size __len)
 993          _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK;
 994 };
 995
 996 // murmur2
 997 template <class _Size>
 998 _Size
 999 __murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len)
1000 {
1001     const _Size __m = 0x5bd1e995;
1002     const _Size __r = 24;
1003     _Size __h = __len;
1004     const unsigned char* __data = static_cast<const unsigned char*>(__key);
1005     for (; __len >= 4; __data += 4, __len -= 4)
1006     {
1007         _Size __k = __loadword<_Size>(__data);
1008         __k *= __m;
1009         __k ^= __k >> __r;
1010         __k *= __m;
1011         __h *= __m;
1012         __h ^= __k;
1013     }
1014     switch (__len)
1015     {
1016     case 3:
1017         __h ^= __data[2] << 16;
1018         _LIBCPP_FALLTHROUGH();
1019     case 2:
1020         __h ^= __data[1] << 8;
1021         _LIBCPP_FALLTHROUGH();
1022     case 1:
1023         __h ^= __data[0];
1024         __h *= __m;
1025     }
1026     __h ^= __h >> 13;
1027     __h *= __m;
1028     __h ^= __h >> 15;
1029     return __h;
1030 }
1031
1032 template <class _Size>
1033 struct __murmur2_or_cityhash<_Size, 64>
1034 {
1035     inline _Size operator()(const void* __key, _Size __len)  _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK;
1036
1037  private:
1038   // Some primes between 2^63 and 2^64.
1039   static const _Size __k0 = 0xc3a5c85c97cb3127ULL;
1040   static const _Size __k1 = 0xb492b66fbe98f273ULL;
1041   static const _Size __k2 = 0x9ae16a3b2f90404fULL;
1042   static const _Size __k3 = 0xc949d7c7509e6557ULL;
1043
1044   static _Size __rotate(_Size __val, int __shift) {
1045     return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift)));
1046   }
1047
1048   static _Size __rotate_by_at_least_1(_Size __val, int __shift) {
1049     return (__val >> __shift) | (__val << (64 - __shift));
1050   }
1051
1052   static _Size __shift_mix(_Size __val) {
1053     return __val ^ (__val >> 47);
1054   }
1055
1056   static _Size __hash_len_16(_Size __u, _Size __v)
1057      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1058   {
1059     const _Size __mul = 0x9ddfea08eb382d69ULL;
1060     _Size __a = (__u ^ __v) * __mul;
1061     __a ^= (__a >> 47);
1062     _Size __b = (__v ^ __a) * __mul;
1063     __b ^= (__b >> 47);
1064     __b *= __mul;
1065     return __b;
1066   }
1067
1068   static _Size __hash_len_0_to_16(const char* __s, _Size __len)
1069      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1070   {
1071     if (__len > 8) {
1072       const _Size __a = __loadword<_Size>(__s);
1073       const _Size __b = __loadword<_Size>(__s + __len - 8);
1074       return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b;
1075     }
1076     if (__len >= 4) {
1077       const uint32_t __a = __loadword<uint32_t>(__s);
1078       const uint32_t __b = __loadword<uint32_t>(__s + __len - 4);
1079       return __hash_len_16(__len + (__a << 3), __b);
1080     }
1081     if (__len > 0) {
1082       const unsigned char __a = __s[0];
1083       const unsigned char __b = __s[__len >> 1];
1084       const unsigned char __c = __s[__len - 1];
1085       const uint32_t __y = static_cast<uint32_t>(__a) +
1086                            (static_cast<uint32_t>(__b) << 8);
1087       const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2);
1088       return __shift_mix(__y * __k2 ^ __z * __k3) * __k2;
1089     }
1090     return __k2;
1091   }
1092
1093   static _Size __hash_len_17_to_32(const char *__s, _Size __len)
1094      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1095   {
1096     const _Size __a = __loadword<_Size>(__s) * __k1;
1097     const _Size __b = __loadword<_Size>(__s + 8);
1098     const _Size __c = __loadword<_Size>(__s + __len - 8) * __k2;
1099     const _Size __d = __loadword<_Size>(__s + __len - 16) * __k0;
1100     return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d,
1101                          __a + __rotate(__b ^ __k3, 20) - __c + __len);
1102   }
1103
1104   // Return a 16-byte hash for 48 bytes.  Quick and dirty.
1105   // Callers do best to use "random-looking" values for a and b.
1106   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
1107       _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b)
1108         _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1109   {
1110     __a += __w;
1111     __b = __rotate(__b + __a + __z, 21);
1112     const _Size __c = __a;
1113     __a += __x;
1114     __a += __y;
1115     __b += __rotate(__a, 44);
1116     return pair<_Size, _Size>(__a + __z, __b + __c);
1117   }
1118
1119   // Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
1120   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
1121       const char* __s, _Size __a, _Size __b)
1122     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1123   {
1124     return __weak_hash_len_32_with_seeds(__loadword<_Size>(__s),
1125                                          __loadword<_Size>(__s + 8),
1126                                          __loadword<_Size>(__s + 16),
1127                                          __loadword<_Size>(__s + 24),
1128                                          __a,
1129                                          __b);
1130   }
1131
1132   // Return an 8-byte hash for 33 to 64 bytes.
1133   static _Size __hash_len_33_to_64(const char *__s, size_t __len)
1134     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1135   {
1136     _Size __z = __loadword<_Size>(__s + 24);
1137     _Size __a = __loadword<_Size>(__s) +
1138                 (__len + __loadword<_Size>(__s + __len - 16)) * __k0;
1139     _Size __b = __rotate(__a + __z, 52);
1140     _Size __c = __rotate(__a, 37);
1141     __a += __loadword<_Size>(__s + 8);
1142     __c += __rotate(__a, 7);
1143     __a += __loadword<_Size>(__s + 16);
1144     _Size __vf = __a + __z;
1145     _Size __vs = __b + __rotate(__a, 31) + __c;
1146     __a = __loadword<_Size>(__s + 16) + __loadword<_Size>(__s + __len - 32);
1147     __z += __loadword<_Size>(__s + __len - 8);
1148     __b = __rotate(__a + __z, 52);
1149     __c = __rotate(__a, 37);
1150     __a += __loadword<_Size>(__s + __len - 24);
1151     __c += __rotate(__a, 7);
1152     __a += __loadword<_Size>(__s + __len - 16);
1153     _Size __wf = __a + __z;
1154     _Size __ws = __b + __rotate(__a, 31) + __c;
1155     _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0);
1156     return __shift_mix(__r * __k0 + __vs) * __k2;
1157   }
1158 };
1159
1160 // cityhash64
1161 template <class _Size>
1162 _Size
1163 __murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len)
1164 {
1165   const char* __s = static_cast<const char*>(__key);
1166   if (__len <= 32) {
1167     if (__len <= 16) {
1168       return __hash_len_0_to_16(__s, __len);
1169     } else {
1170       return __hash_len_17_to_32(__s, __len);
1171     }
1172   } else if (__len <= 64) {
1173     return __hash_len_33_to_64(__s, __len);
1174   }
1175
1176   // For strings over 64 bytes we hash the end first, and then as we
1177   // loop we keep 56 bytes of state: v, w, x, y, and z.
1178   _Size __x = __loadword<_Size>(__s + __len - 40);
1179   _Size __y = __loadword<_Size>(__s + __len - 16) +
1180               __loadword<_Size>(__s + __len - 56);
1181   _Size __z = __hash_len_16(__loadword<_Size>(__s + __len - 48) + __len,
1182                           __loadword<_Size>(__s + __len - 24));
1183   pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z);
1184   pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x);
1185   __x = __x * __k1 + __loadword<_Size>(__s);
1186
1187   // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
1188   __len = (__len - 1) & ~static_cast<_Size>(63);
1189   do {
1190     __x = __rotate(__x + __y + __v.first + __loadword<_Size>(__s + 8), 37) * __k1;
1191     __y = __rotate(__y + __v.second + __loadword<_Size>(__s + 48), 42) * __k1;
1192     __x ^= __w.second;
1193     __y += __v.first + __loadword<_Size>(__s + 40);
1194     __z = __rotate(__z + __w.first, 33) * __k1;
1195     __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first);
1196     __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second,
1197                                         __y + __loadword<_Size>(__s + 16));
1198     std::swap(__z, __x);
1199     __s += 64;
1200     __len -= 64;
1201   } while (__len != 0);
1202   return __hash_len_16(
1203       __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z,
1204       __hash_len_16(__v.second, __w.second) + __x);
1205 }
1206
1207 template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)>
1208 struct __scalar_hash;
1209
1210 template <class _Tp>
1211 struct __scalar_hash<_Tp, 0>
1212     : public unary_function<_Tp, size_t>
1213 {
1214     _LIBCPP_INLINE_VISIBILITY
1215     size_t operator()(_Tp __v) const _NOEXCEPT
1216     {
1217         union
1218         {
1219             _Tp    __t;
1220             size_t __a;
1221         } __u;
1222         __u.__a = 0;
1223         __u.__t = __v;
1224         return __u.__a;
1225     }
1226 };
1227
1228 template <class _Tp>
1229 struct __scalar_hash<_Tp, 1>
1230     : public unary_function<_Tp, size_t>
1231 {
1232     _LIBCPP_INLINE_VISIBILITY
1233     size_t operator()(_Tp __v) const _NOEXCEPT
1234     {
1235         union
1236         {
1237             _Tp    __t;
1238             size_t __a;
1239         } __u;
1240         __u.__t = __v;
1241         return __u.__a;
1242     }
1243 };
1244
1245 template <class _Tp>
1246 struct __scalar_hash<_Tp, 2>
1247     : public unary_function<_Tp, size_t>
1248 {
1249     _LIBCPP_INLINE_VISIBILITY
1250     size_t operator()(_Tp __v) const _NOEXCEPT
1251     {
1252         union
1253         {
1254             _Tp __t;
1255             struct
1256             {
1257                 size_t __a;
1258                 size_t __b;
1259             } __s;
1260         } __u;
1261         __u.__t = __v;
1262         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1263     }
1264 };
1265
1266 template <class _Tp>
1267 struct __scalar_hash<_Tp, 3>
1268     : public unary_function<_Tp, size_t>
1269 {
1270     _LIBCPP_INLINE_VISIBILITY
1271     size_t operator()(_Tp __v) const _NOEXCEPT
1272     {
1273         union
1274         {
1275             _Tp __t;
1276             struct
1277             {
1278                 size_t __a;
1279                 size_t __b;
1280                 size_t __c;
1281             } __s;
1282         } __u;
1283         __u.__t = __v;
1284         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1285     }
1286 };
1287
1288 template <class _Tp>
1289 struct __scalar_hash<_Tp, 4>
1290     : public unary_function<_Tp, size_t>
1291 {
1292     _LIBCPP_INLINE_VISIBILITY
1293     size_t operator()(_Tp __v) const _NOEXCEPT
1294     {
1295         union
1296         {
1297             _Tp __t;
1298             struct
1299             {
1300                 size_t __a;
1301                 size_t __b;
1302                 size_t __c;
1303                 size_t __d;
1304             } __s;
1305         } __u;
1306         __u.__t = __v;
1307         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1308     }
1309 };
1310
1311 struct _PairT {
1312   size_t first;
1313   size_t second;
1314 };
1315
1316 _LIBCPP_INLINE_VISIBILITY
1317 inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT {
1318     typedef __scalar_hash<_PairT> _HashT;
1319     const _PairT __p = {__lhs, __rhs};
1320     return _HashT()(__p);
1321 }
1322
1323 template<class _Tp>
1324 struct _LIBCPP_TEMPLATE_VIS hash<_Tp*>
1325     : public unary_function<_Tp*, size_t>
1326 {
1327     _LIBCPP_INLINE_VISIBILITY
1328     size_t operator()(_Tp* __v) const _NOEXCEPT
1329     {
1330         union
1331         {
1332             _Tp* __t;
1333             size_t __a;
1334         } __u;
1335         __u.__t = __v;
1336         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1337     }
1338 };
1339
1340
1341 template <>
1342 struct _LIBCPP_TEMPLATE_VIS hash<bool>
1343     : public unary_function<bool, size_t>
1344 {
1345     _LIBCPP_INLINE_VISIBILITY
1346     size_t operator()(bool __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1347 };
1348
1349 template <>
1350 struct _LIBCPP_TEMPLATE_VIS hash<char>
1351     : public unary_function<char, size_t>
1352 {
1353     _LIBCPP_INLINE_VISIBILITY
1354     size_t operator()(char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1355 };
1356
1357 template <>
1358 struct _LIBCPP_TEMPLATE_VIS hash<signed char>
1359     : public unary_function<signed char, size_t>
1360 {
1361     _LIBCPP_INLINE_VISIBILITY
1362     size_t operator()(signed char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1363 };
1364
1365 template <>
1366 struct _LIBCPP_TEMPLATE_VIS hash<unsigned char>
1367     : public unary_function<unsigned char, size_t>
1368 {
1369     _LIBCPP_INLINE_VISIBILITY
1370     size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1371 };
1372
1373 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
1374
1375 template <>
1376 struct _LIBCPP_TEMPLATE_VIS hash<char16_t>
1377     : public unary_function<char16_t, size_t>
1378 {
1379     _LIBCPP_INLINE_VISIBILITY
1380     size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1381 };
1382
1383 template <>
1384 struct _LIBCPP_TEMPLATE_VIS hash<char32_t>
1385     : public unary_function<char32_t, size_t>
1386 {
1387     _LIBCPP_INLINE_VISIBILITY
1388     size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1389 };
1390
1391 #endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
1392
1393 template <>
1394 struct _LIBCPP_TEMPLATE_VIS hash<wchar_t>
1395     : public unary_function<wchar_t, size_t>
1396 {
1397     _LIBCPP_INLINE_VISIBILITY
1398     size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1399 };
1400
1401 template <>
1402 struct _LIBCPP_TEMPLATE_VIS hash<short>
1403     : public unary_function<short, size_t>
1404 {
1405     _LIBCPP_INLINE_VISIBILITY
1406     size_t operator()(short __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1407 };
1408
1409 template <>
1410 struct _LIBCPP_TEMPLATE_VIS hash<unsigned short>
1411     : public unary_function<unsigned short, size_t>
1412 {
1413     _LIBCPP_INLINE_VISIBILITY
1414     size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1415 };
1416
1417 template <>
1418 struct _LIBCPP_TEMPLATE_VIS hash<int>
1419     : public unary_function<int, size_t>
1420 {
1421     _LIBCPP_INLINE_VISIBILITY
1422     size_t operator()(int __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1423 };
1424
1425 template <>
1426 struct _LIBCPP_TEMPLATE_VIS hash<unsigned int>
1427     : public unary_function<unsigned int, size_t>
1428 {
1429     _LIBCPP_INLINE_VISIBILITY
1430     size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1431 };
1432
1433 template <>
1434 struct _LIBCPP_TEMPLATE_VIS hash<long>
1435     : public unary_function<long, size_t>
1436 {
1437     _LIBCPP_INLINE_VISIBILITY
1438     size_t operator()(long __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1439 };
1440
1441 template <>
1442 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long>
1443     : public unary_function<unsigned long, size_t>
1444 {
1445     _LIBCPP_INLINE_VISIBILITY
1446     size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1447 };
1448
1449 template <>
1450 struct _LIBCPP_TEMPLATE_VIS hash<long long>
1451     : public __scalar_hash<long long>
1452 {
1453 };
1454
1455 template <>
1456 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long long>
1457     : public __scalar_hash<unsigned long long>
1458 {
1459 };
1460
1461 #ifndef _LIBCPP_HAS_NO_INT128
1462
1463 template <>
1464 struct _LIBCPP_TEMPLATE_VIS hash<__int128_t>
1465     : public __scalar_hash<__int128_t>
1466 {
1467 };
1468
1469 template <>
1470 struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t>
1471     : public __scalar_hash<__uint128_t>
1472 {
1473 };
1474
1475 #endif
1476
1477 template <>
1478 struct _LIBCPP_TEMPLATE_VIS hash<float>
1479     : public __scalar_hash<float>
1480 {
1481     _LIBCPP_INLINE_VISIBILITY
1482     size_t operator()(float __v) const _NOEXCEPT
1483     {
1484         // -0.0 and 0.0 should return same hash
1485        if (__v == 0.0)
1486            return 0;
1487         return __scalar_hash<float>::operator()(__v);
1488     }
1489 };
1490
1491 template <>
1492 struct _LIBCPP_TEMPLATE_VIS hash<double>
1493     : public __scalar_hash<double>
1494 {
1495     _LIBCPP_INLINE_VISIBILITY
1496     size_t operator()(double __v) const _NOEXCEPT
1497     {
1498         // -0.0 and 0.0 should return same hash
1499        if (__v == 0.0)
1500            return 0;
1501         return __scalar_hash<double>::operator()(__v);
1502     }
1503 };
1504
1505 template <>
1506 struct _LIBCPP_TEMPLATE_VIS hash<long double>
1507     : public __scalar_hash<long double>
1508 {
1509     _LIBCPP_INLINE_VISIBILITY
1510     size_t operator()(long double __v) const _NOEXCEPT
1511     {
1512         // -0.0 and 0.0 should return same hash
1513         if (__v == 0.0)
1514             return 0;
1515 #if defined(__i386__)
1516         // Zero out padding bits
1517         union
1518         {
1519             long double __t;
1520             struct
1521             {
1522                 size_t __a;
1523                 size_t __b;
1524                 size_t __c;
1525                 size_t __d;
1526             } __s;
1527         } __u;
1528         __u.__s.__a = 0;
1529         __u.__s.__b = 0;
1530         __u.__s.__c = 0;
1531         __u.__s.__d = 0;
1532         __u.__t = __v;
1533         return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d;
1534 #elif defined(__x86_64__)
1535         // Zero out padding bits
1536         union
1537         {
1538             long double __t;
1539             struct
1540             {
1541                 size_t __a;
1542                 size_t __b;
1543             } __s;
1544         } __u;
1545         __u.__s.__a = 0;
1546         __u.__s.__b = 0;
1547         __u.__t = __v;
1548         return __u.__s.__a ^ __u.__s.__b;
1549 #else
1550         return __scalar_hash<long double>::operator()(__v);
1551 #endif
1552     }
1553 };
1554
1555 #if _LIBCPP_STD_VER > 11
1556
1557 template <class _Tp, bool = is_enum<_Tp>::value>
1558 struct _LIBCPP_TEMPLATE_VIS __enum_hash
1559     : public unary_function<_Tp, size_t>
1560 {
1561     _LIBCPP_INLINE_VISIBILITY
1562     size_t operator()(_Tp __v) const _NOEXCEPT
1563     {
1564         typedef typename underlying_type<_Tp>::type type;
1565         return hash<type>{}(static_cast<type>(__v));
1566     }
1567 };
1568 template <class _Tp>
1569 struct _LIBCPP_TEMPLATE_VIS __enum_hash<_Tp, false> {
1570     __enum_hash() = delete;
1571     __enum_hash(__enum_hash const&) = delete;
1572     __enum_hash& operator=(__enum_hash const&) = delete;
1573 };
1574
1575 template <class _Tp>
1576 struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp>
1577 {
1578 };
1579 #endif
1580
1581 #if _LIBCPP_STD_VER > 14
1582
1583 template <>
1584 struct _LIBCPP_TEMPLATE_VIS hash<nullptr_t>
1585   : public unary_function<nullptr_t, size_t>
1586 {
1587   _LIBCPP_INLINE_VISIBILITY
1588   size_t operator()(nullptr_t) const _NOEXCEPT {
1589     return 662607004ull;
1590   }
1591 };
1592 #endif
1593
1594 #ifndef _LIBCPP_CXX03_LANG
1595 template <class _Key, class _Hash>
1596 using __check_hash_requirements = integral_constant<bool,
1597     is_copy_constructible<_Hash>::value &&
1598     is_move_constructible<_Hash>::value &&
1599     __invokable_r<size_t, _Hash, _Key const&>::value
1600 >;
1601
1602 template <class _Key, class _Hash = std::hash<_Key> >
1603 using __has_enabled_hash = integral_constant<bool,
1604     __check_hash_requirements<_Key, _Hash>::value &&
1605     is_default_constructible<_Hash>::value
1606 >;
1607
1608 #if _LIBCPP_STD_VER > 14
1609 template <class _Type, class>
1610 using __enable_hash_helper_imp = _Type;
1611
1612 template <class _Type, class ..._Keys>
1613 using __enable_hash_helper = __enable_hash_helper_imp<_Type,
1614   typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type
1615 >;
1616 #else
1617 template <class _Type, class ...>
1618 using __enable_hash_helper = _Type;
1619 #endif
1620
1621 #endif // !_LIBCPP_CXX03_LANG
1622
1623 _LIBCPP_END_NAMESPACE_STD
1624
1625 #endif  // _LIBCPP_UTILITY