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