contrib/libc++/include/utility

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