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_HAS_NO_RVALUE_REFERENCES
 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_HAS_NO_RVALUE_REFERENCES
 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_HAS_NO_CONSTEXPR) || 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_HAS_NO_RVALUE_REFERENCES
 612
 613
 614 template <class _Tp>
 615 struct __make_pair_return_impl
 616 {
 617     typedef _Tp type;
 618 };
 619
 620 template <class _Tp>
 621 struct __make_pair_return_impl<reference_wrapper<_Tp>>
 622 {
 623     typedef _Tp& type;
 624 };
 625
 626 template <class _Tp>
 627 struct __make_pair_return
 628 {
 629     typedef typename __make_pair_return_impl<typename decay<_Tp>::type>::type type;
 630 };
 631
 632 template <class _T1, class _T2>
 633 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 634 pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
 635 make_pair(_T1&& __t1, _T2&& __t2)
 636 {
 637     return pair<typename __make_pair_return<_T1>::type, typename __make_pair_return<_T2>::type>
 638                (_VSTD::forward<_T1>(__t1), _VSTD::forward<_T2>(__t2));
 639 }
 640
 641 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 642
 643 template <class _T1, class _T2>
 644 inline _LIBCPP_INLINE_VISIBILITY
 645 pair<_T1,_T2>
 646 make_pair(_T1 __x, _T2 __y)
 647 {
 648     return pair<_T1, _T2>(__x, __y);
 649 }
 650
 651 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 652
 653 template <class _T1, class _T2>
 654   class _LIBCPP_TEMPLATE_VIS tuple_size<pair<_T1, _T2> >
 655     : public integral_constant<size_t, 2> {};
 656
 657 template <class _T1, class _T2>
 658 class _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> >
 659 {
 660 public:
 661     typedef _T1 type;
 662 };
 663
 664 template <class _T1, class _T2>
 665 class _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> >
 666 {
 667 public:
 668     typedef _T2 type;
 669 };
 670
 671 template <size_t _Ip> struct __get_pair;
 672
 673 template <>
 674 struct __get_pair<0>
 675 {
 676     template <class _T1, class _T2>
 677     static
 678     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 679     _T1&
 680     get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
 681
 682     template <class _T1, class _T2>
 683     static
 684     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 685     const _T1&
 686     get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.first;}
 687
 688 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 689
 690     template <class _T1, class _T2>
 691     static
 692     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 693     _T1&&
 694     get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T1>(__p.first);}
 695
 696     template <class _T1, class _T2>
 697     static
 698     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 699     const _T1&&
 700     get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T1>(__p.first);}
 701
 702 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 703 };
 704
 705 template <>
 706 struct __get_pair<1>
 707 {
 708     template <class _T1, class _T2>
 709     static
 710     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 711     _T2&
 712     get(pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
 713
 714     template <class _T1, class _T2>
 715     static
 716     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 717     const _T2&
 718     get(const pair<_T1, _T2>& __p) _NOEXCEPT {return __p.second;}
 719
 720 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 721
 722     template <class _T1, class _T2>
 723     static
 724     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 725     _T2&&
 726     get(pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<_T2>(__p.second);}
 727
 728     template <class _T1, class _T2>
 729     static
 730     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 731     const _T2&&
 732     get(const pair<_T1, _T2>&& __p) _NOEXCEPT {return _VSTD::forward<const _T2>(__p.second);}
 733
 734 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 735 };
 736
 737 template <size_t _Ip, class _T1, class _T2>
 738 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 739 typename tuple_element<_Ip, pair<_T1, _T2> >::type&
 740 get(pair<_T1, _T2>& __p) _NOEXCEPT
 741 {
 742     return __get_pair<_Ip>::get(__p);
 743 }
 744
 745 template <size_t _Ip, class _T1, class _T2>
 746 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
 747 const typename tuple_element<_Ip, pair<_T1, _T2> >::type&
 748 get(const pair<_T1, _T2>& __p) _NOEXCEPT
 749 {
 750     return __get_pair<_Ip>::get(__p);
 751 }
 752
 753 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 754
 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
 771 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 772
 773 #if _LIBCPP_STD_VER > 11
 774 template <class _T1, class _T2>
 775 inline _LIBCPP_INLINE_VISIBILITY
 776 constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT
 777 {
 778     return __get_pair<0>::get(__p);
 779 }
 780
 781 template <class _T1, class _T2>
 782 inline _LIBCPP_INLINE_VISIBILITY
 783 constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT
 784 {
 785     return __get_pair<0>::get(__p);
 786 }
 787
 788 template <class _T1, class _T2>
 789 inline _LIBCPP_INLINE_VISIBILITY
 790 constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT
 791 {
 792     return __get_pair<0>::get(_VSTD::move(__p));
 793 }
 794
 795 template <class _T1, class _T2>
 796 inline _LIBCPP_INLINE_VISIBILITY
 797 constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT
 798 {
 799     return __get_pair<0>::get(_VSTD::move(__p));
 800 }
 801
 802 template <class _T1, class _T2>
 803 inline _LIBCPP_INLINE_VISIBILITY
 804 constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT
 805 {
 806     return __get_pair<1>::get(__p);
 807 }
 808
 809 template <class _T1, class _T2>
 810 inline _LIBCPP_INLINE_VISIBILITY
 811 constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT
 812 {
 813     return __get_pair<1>::get(__p);
 814 }
 815
 816 template <class _T1, class _T2>
 817 inline _LIBCPP_INLINE_VISIBILITY
 818 constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT
 819 {
 820     return __get_pair<1>::get(_VSTD::move(__p));
 821 }
 822
 823 template <class _T1, class _T2>
 824 inline _LIBCPP_INLINE_VISIBILITY
 825 constexpr _T1 const && get(pair<_T2, _T1> const&& __p) _NOEXCEPT
 826 {
 827     return __get_pair<1>::get(_VSTD::move(__p));
 828 }
 829
 830 #endif
 831
 832 #if _LIBCPP_STD_VER > 11
 833
 834 template<class _Tp, _Tp... _Ip>
 835 struct _LIBCPP_TEMPLATE_VIS integer_sequence
 836 {
 837     typedef _Tp value_type;
 838     static_assert( is_integral<_Tp>::value,
 839                   "std::integer_sequence can only be instantiated with an integral type" );
 840     static
 841     _LIBCPP_INLINE_VISIBILITY
 842     constexpr
 843     size_t
 844     size() noexcept { return sizeof...(_Ip); }
 845 };
 846
 847 template<size_t... _Ip>
 848     using index_sequence = integer_sequence<size_t, _Ip...>;
 849
 850 #if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE)
 851
 852 template <class _Tp, _Tp _Ep>
 853 using __make_integer_sequence = __make_integer_seq<integer_sequence, _Tp, _Ep>;
 854
 855 #else
 856
 857 template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked =
 858   typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>;
 859
 860 template <class _Tp, _Tp _Ep>
 861 struct __make_integer_sequence_checked
 862 {
 863     static_assert(is_integral<_Tp>::value,
 864                   "std::make_integer_sequence can only be instantiated with an integral type" );
 865     static_assert(0 <= _Ep, "std::make_integer_sequence must have a non-negative sequence length");
 866     // Workaround GCC bug by preventing bad installations when 0 <= _Ep
 867     // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68929
 868     typedef __make_integer_sequence_unchecked<_Tp, 0 <= _Ep ? _Ep : 0> type;
 869 };
 870
 871 template <class _Tp, _Tp _Ep>
 872 using __make_integer_sequence = typename __make_integer_sequence_checked<_Tp, _Ep>::type;
 873
 874 #endif
 875
 876 template<class _Tp, _Tp _Np>
 877     using make_integer_sequence = __make_integer_sequence<_Tp, _Np>;
 878
 879 template<size_t _Np>
 880     using make_index_sequence = make_integer_sequence<size_t, _Np>;
 881
 882 template<class... _Tp>
 883     using index_sequence_for = make_index_sequence<sizeof...(_Tp)>;
 884
 885 #endif  // _LIBCPP_STD_VER > 11
 886
 887 #if _LIBCPP_STD_VER > 11
 888 template<class _T1, class _T2 = _T1>
 889 inline _LIBCPP_INLINE_VISIBILITY
 890 _T1 exchange(_T1& __obj, _T2 && __new_value)
 891 {
 892     _T1 __old_value = _VSTD::move(__obj);
 893     __obj = _VSTD::forward<_T2>(__new_value);
 894     return __old_value;
 895 }
 896 #endif  // _LIBCPP_STD_VER > 11
 897
 898 #if _LIBCPP_STD_VER > 14
 899
 900 struct _LIBCPP_TYPE_VIS in_place_t {
 901     explicit in_place_t() = default;
 902 };
 903 #ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES
 904 inline
 905 #endif
 906 constexpr in_place_t in_place{};
 907
 908 template <class _Tp>
 909 struct _LIBCPP_TYPE_VIS in_place_type_t {
 910     explicit in_place_type_t() = default;
 911 };
 912 template <class _Tp>
 913 #ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES
 914 inline
 915 #endif
 916 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 #ifndef _LIBCPP_HAS_NO_INLINE_VARIABLES
 924 inline
 925 #endif
 926 constexpr in_place_index_t<_Idx> in_place_index{};
 927
 928 template <class _Tp> struct __is_inplace_type_imp : false_type {};
 929 template <class _Tp> struct __is_inplace_type_imp<in_place_type_t<_Tp>> : true_type {};
 930
 931 template <class _Tp>
 932 using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>;
 933
 934 #endif // _LIBCPP_STD_VER > 14
 935
 936 template <class _Arg, class _Result>
 937 struct _LIBCPP_TEMPLATE_VIS unary_function
 938 {
 939     typedef _Arg    argument_type;
 940     typedef _Result result_type;
 941 };
 942
 943 template <class _Size>
 944 inline _LIBCPP_INLINE_VISIBILITY
 945 _Size
 946 __loadword(const void* __p)
 947 {
 948     _Size __r;
 949     std::memcpy(&__r, __p, sizeof(__r));
 950     return __r;
 951 }
 952
 953 // We use murmur2 when size_t is 32 bits, and cityhash64 when size_t
 954 // is 64 bits.  This is because cityhash64 uses 64bit x 64bit
 955 // multiplication, which can be very slow on 32-bit systems.
 956 template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__>
 957 struct __murmur2_or_cityhash;
 958
 959 template <class _Size>
 960 struct __murmur2_or_cityhash<_Size, 32>
 961 {
 962     inline _Size operator()(const void* __key, _Size __len)
 963          _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK;
 964 };
 965
 966 // murmur2
 967 template <class _Size>
 968 _Size
 969 __murmur2_or_cityhash<_Size, 32>::operator()(const void* __key, _Size __len)
 970 {
 971     const _Size __m = 0x5bd1e995;
 972     const _Size __r = 24;
 973     _Size __h = __len;
 974     const unsigned char* __data = static_cast<const unsigned char*>(__key);
 975     for (; __len >= 4; __data += 4, __len -= 4)
 976     {
 977         _Size __k = __loadword<_Size>(__data);
 978         __k *= __m;
 979         __k ^= __k >> __r;
 980         __k *= __m;
 981         __h *= __m;
 982         __h ^= __k;
 983     }
 984     switch (__len)
 985     {
 986     case 3:
 987         __h ^= __data[2] << 16;
 988     case 2:
 989         __h ^= __data[1] << 8;
 990     case 1:
 991         __h ^= __data[0];
 992         __h *= __m;
 993     }
 994     __h ^= __h >> 13;
 995     __h *= __m;
 996     __h ^= __h >> 15;
 997     return __h;
 998 }
 999
1000 template <class _Size>
1001 struct __murmur2_or_cityhash<_Size, 64>
1002 {
1003     inline _Size operator()(const void* __key, _Size __len)  _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK;
1004
1005  private:
1006   // Some primes between 2^63 and 2^64.
1007   static const _Size __k0 = 0xc3a5c85c97cb3127ULL;
1008   static const _Size __k1 = 0xb492b66fbe98f273ULL;
1009   static const _Size __k2 = 0x9ae16a3b2f90404fULL;
1010   static const _Size __k3 = 0xc949d7c7509e6557ULL;
1011
1012   static _Size __rotate(_Size __val, int __shift) {
1013     return __shift == 0 ? __val : ((__val >> __shift) | (__val << (64 - __shift)));
1014   }
1015
1016   static _Size __rotate_by_at_least_1(_Size __val, int __shift) {
1017     return (__val >> __shift) | (__val << (64 - __shift));
1018   }
1019
1020   static _Size __shift_mix(_Size __val) {
1021     return __val ^ (__val >> 47);
1022   }
1023
1024   static _Size __hash_len_16(_Size __u, _Size __v)
1025      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1026   {
1027     const _Size __mul = 0x9ddfea08eb382d69ULL;
1028     _Size __a = (__u ^ __v) * __mul;
1029     __a ^= (__a >> 47);
1030     _Size __b = (__v ^ __a) * __mul;
1031     __b ^= (__b >> 47);
1032     __b *= __mul;
1033     return __b;
1034   }
1035
1036   static _Size __hash_len_0_to_16(const char* __s, _Size __len)
1037      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1038   {
1039     if (__len > 8) {
1040       const _Size __a = __loadword<_Size>(__s);
1041       const _Size __b = __loadword<_Size>(__s + __len - 8);
1042       return __hash_len_16(__a, __rotate_by_at_least_1(__b + __len, __len)) ^ __b;
1043     }
1044     if (__len >= 4) {
1045       const uint32_t __a = __loadword<uint32_t>(__s);
1046       const uint32_t __b = __loadword<uint32_t>(__s + __len - 4);
1047       return __hash_len_16(__len + (__a << 3), __b);
1048     }
1049     if (__len > 0) {
1050       const unsigned char __a = __s[0];
1051       const unsigned char __b = __s[__len >> 1];
1052       const unsigned char __c = __s[__len - 1];
1053       const uint32_t __y = static_cast<uint32_t>(__a) +
1054                            (static_cast<uint32_t>(__b) << 8);
1055       const uint32_t __z = __len + (static_cast<uint32_t>(__c) << 2);
1056       return __shift_mix(__y * __k2 ^ __z * __k3) * __k2;
1057     }
1058     return __k2;
1059   }
1060
1061   static _Size __hash_len_17_to_32(const char *__s, _Size __len)
1062      _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1063   {
1064     const _Size __a = __loadword<_Size>(__s) * __k1;
1065     const _Size __b = __loadword<_Size>(__s + 8);
1066     const _Size __c = __loadword<_Size>(__s + __len - 8) * __k2;
1067     const _Size __d = __loadword<_Size>(__s + __len - 16) * __k0;
1068     return __hash_len_16(__rotate(__a - __b, 43) + __rotate(__c, 30) + __d,
1069                          __a + __rotate(__b ^ __k3, 20) - __c + __len);
1070   }
1071
1072   // Return a 16-byte hash for 48 bytes.  Quick and dirty.
1073   // Callers do best to use "random-looking" values for a and b.
1074   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
1075       _Size __w, _Size __x, _Size __y, _Size __z, _Size __a, _Size __b)
1076         _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1077   {
1078     __a += __w;
1079     __b = __rotate(__b + __a + __z, 21);
1080     const _Size __c = __a;
1081     __a += __x;
1082     __a += __y;
1083     __b += __rotate(__a, 44);
1084     return pair<_Size, _Size>(__a + __z, __b + __c);
1085   }
1086
1087   // Return a 16-byte hash for s[0] ... s[31], a, and b.  Quick and dirty.
1088   static pair<_Size, _Size> __weak_hash_len_32_with_seeds(
1089       const char* __s, _Size __a, _Size __b)
1090     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1091   {
1092     return __weak_hash_len_32_with_seeds(__loadword<_Size>(__s),
1093                                          __loadword<_Size>(__s + 8),
1094                                          __loadword<_Size>(__s + 16),
1095                                          __loadword<_Size>(__s + 24),
1096                                          __a,
1097                                          __b);
1098   }
1099
1100   // Return an 8-byte hash for 33 to 64 bytes.
1101   static _Size __hash_len_33_to_64(const char *__s, size_t __len)
1102     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
1103   {
1104     _Size __z = __loadword<_Size>(__s + 24);
1105     _Size __a = __loadword<_Size>(__s) +
1106                 (__len + __loadword<_Size>(__s + __len - 16)) * __k0;
1107     _Size __b = __rotate(__a + __z, 52);
1108     _Size __c = __rotate(__a, 37);
1109     __a += __loadword<_Size>(__s + 8);
1110     __c += __rotate(__a, 7);
1111     __a += __loadword<_Size>(__s + 16);
1112     _Size __vf = __a + __z;
1113     _Size __vs = __b + __rotate(__a, 31) + __c;
1114     __a = __loadword<_Size>(__s + 16) + __loadword<_Size>(__s + __len - 32);
1115     __z += __loadword<_Size>(__s + __len - 8);
1116     __b = __rotate(__a + __z, 52);
1117     __c = __rotate(__a, 37);
1118     __a += __loadword<_Size>(__s + __len - 24);
1119     __c += __rotate(__a, 7);
1120     __a += __loadword<_Size>(__s + __len - 16);
1121     _Size __wf = __a + __z;
1122     _Size __ws = __b + __rotate(__a, 31) + __c;
1123     _Size __r = __shift_mix((__vf + __ws) * __k2 + (__wf + __vs) * __k0);
1124     return __shift_mix(__r * __k0 + __vs) * __k2;
1125   }
1126 };
1127
1128 // cityhash64
1129 template <class _Size>
1130 _Size
1131 __murmur2_or_cityhash<_Size, 64>::operator()(const void* __key, _Size __len)
1132 {
1133   const char* __s = static_cast<const char*>(__key);
1134   if (__len <= 32) {
1135     if (__len <= 16) {
1136       return __hash_len_0_to_16(__s, __len);
1137     } else {
1138       return __hash_len_17_to_32(__s, __len);
1139     }
1140   } else if (__len <= 64) {
1141     return __hash_len_33_to_64(__s, __len);
1142   }
1143
1144   // For strings over 64 bytes we hash the end first, and then as we
1145   // loop we keep 56 bytes of state: v, w, x, y, and z.
1146   _Size __x = __loadword<_Size>(__s + __len - 40);
1147   _Size __y = __loadword<_Size>(__s + __len - 16) +
1148               __loadword<_Size>(__s + __len - 56);
1149   _Size __z = __hash_len_16(__loadword<_Size>(__s + __len - 48) + __len,
1150                           __loadword<_Size>(__s + __len - 24));
1151   pair<_Size, _Size> __v = __weak_hash_len_32_with_seeds(__s + __len - 64, __len, __z);
1152   pair<_Size, _Size> __w = __weak_hash_len_32_with_seeds(__s + __len - 32, __y + __k1, __x);
1153   __x = __x * __k1 + __loadword<_Size>(__s);
1154
1155   // Decrease len to the nearest multiple of 64, and operate on 64-byte chunks.
1156   __len = (__len - 1) & ~static_cast<_Size>(63);
1157   do {
1158     __x = __rotate(__x + __y + __v.first + __loadword<_Size>(__s + 8), 37) * __k1;
1159     __y = __rotate(__y + __v.second + __loadword<_Size>(__s + 48), 42) * __k1;
1160     __x ^= __w.second;
1161     __y += __v.first + __loadword<_Size>(__s + 40);
1162     __z = __rotate(__z + __w.first, 33) * __k1;
1163     __v = __weak_hash_len_32_with_seeds(__s, __v.second * __k1, __x + __w.first);
1164     __w = __weak_hash_len_32_with_seeds(__s + 32, __z + __w.second,
1165                                         __y + __loadword<_Size>(__s + 16));
1166     std::swap(__z, __x);
1167     __s += 64;
1168     __len -= 64;
1169   } while (__len != 0);
1170   return __hash_len_16(
1171       __hash_len_16(__v.first, __w.first) + __shift_mix(__y) * __k1 + __z,
1172       __hash_len_16(__v.second, __w.second) + __x);
1173 }
1174
1175 template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)>
1176 struct __scalar_hash;
1177
1178 template <class _Tp>
1179 struct __scalar_hash<_Tp, 0>
1180     : public unary_function<_Tp, size_t>
1181 {
1182     _LIBCPP_INLINE_VISIBILITY
1183     size_t operator()(_Tp __v) const _NOEXCEPT
1184     {
1185         union
1186         {
1187             _Tp    __t;
1188             size_t __a;
1189         } __u;
1190         __u.__a = 0;
1191         __u.__t = __v;
1192         return __u.__a;
1193     }
1194 };
1195
1196 template <class _Tp>
1197 struct __scalar_hash<_Tp, 1>
1198     : public unary_function<_Tp, size_t>
1199 {
1200     _LIBCPP_INLINE_VISIBILITY
1201     size_t operator()(_Tp __v) const _NOEXCEPT
1202     {
1203         union
1204         {
1205             _Tp    __t;
1206             size_t __a;
1207         } __u;
1208         __u.__t = __v;
1209         return __u.__a;
1210     }
1211 };
1212
1213 template <class _Tp>
1214 struct __scalar_hash<_Tp, 2>
1215     : public unary_function<_Tp, size_t>
1216 {
1217     _LIBCPP_INLINE_VISIBILITY
1218     size_t operator()(_Tp __v) const _NOEXCEPT
1219     {
1220         union
1221         {
1222             _Tp __t;
1223             struct
1224             {
1225                 size_t __a;
1226                 size_t __b;
1227             } __s;
1228         } __u;
1229         __u.__t = __v;
1230         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1231     }
1232 };
1233
1234 template <class _Tp>
1235 struct __scalar_hash<_Tp, 3>
1236     : public unary_function<_Tp, size_t>
1237 {
1238     _LIBCPP_INLINE_VISIBILITY
1239     size_t operator()(_Tp __v) const _NOEXCEPT
1240     {
1241         union
1242         {
1243             _Tp __t;
1244             struct
1245             {
1246                 size_t __a;
1247                 size_t __b;
1248                 size_t __c;
1249             } __s;
1250         } __u;
1251         __u.__t = __v;
1252         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1253     }
1254 };
1255
1256 template <class _Tp>
1257 struct __scalar_hash<_Tp, 4>
1258     : public unary_function<_Tp, size_t>
1259 {
1260     _LIBCPP_INLINE_VISIBILITY
1261     size_t operator()(_Tp __v) const _NOEXCEPT
1262     {
1263         union
1264         {
1265             _Tp __t;
1266             struct
1267             {
1268                 size_t __a;
1269                 size_t __b;
1270                 size_t __c;
1271                 size_t __d;
1272             } __s;
1273         } __u;
1274         __u.__t = __v;
1275         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1276     }
1277 };
1278
1279 struct _PairT {
1280   size_t first;
1281   size_t second;
1282 };
1283
1284 _LIBCPP_INLINE_VISIBILITY
1285 inline size_t __hash_combine(size_t __lhs, size_t __rhs) _NOEXCEPT {
1286     typedef __scalar_hash<_PairT> _HashT;
1287     const _PairT __p = {__lhs, __rhs};
1288     return _HashT()(__p);
1289 }
1290
1291 template<class _Tp>
1292 struct _LIBCPP_TEMPLATE_VIS hash<_Tp*>
1293     : public unary_function<_Tp*, size_t>
1294 {
1295     _LIBCPP_INLINE_VISIBILITY
1296     size_t operator()(_Tp* __v) const _NOEXCEPT
1297     {
1298         union
1299         {
1300             _Tp* __t;
1301             size_t __a;
1302         } __u;
1303         __u.__t = __v;
1304         return __murmur2_or_cityhash<size_t>()(&__u, sizeof(__u));
1305     }
1306 };
1307
1308
1309 template <>
1310 struct _LIBCPP_TEMPLATE_VIS hash<bool>
1311     : public unary_function<bool, size_t>
1312 {
1313     _LIBCPP_INLINE_VISIBILITY
1314     size_t operator()(bool __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1315 };
1316
1317 template <>
1318 struct _LIBCPP_TEMPLATE_VIS hash<char>
1319     : public unary_function<char, size_t>
1320 {
1321     _LIBCPP_INLINE_VISIBILITY
1322     size_t operator()(char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1323 };
1324
1325 template <>
1326 struct _LIBCPP_TEMPLATE_VIS hash<signed char>
1327     : public unary_function<signed char, size_t>
1328 {
1329     _LIBCPP_INLINE_VISIBILITY
1330     size_t operator()(signed char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1331 };
1332
1333 template <>
1334 struct _LIBCPP_TEMPLATE_VIS hash<unsigned char>
1335     : public unary_function<unsigned char, size_t>
1336 {
1337     _LIBCPP_INLINE_VISIBILITY
1338     size_t operator()(unsigned char __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1339 };
1340
1341 #ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
1342
1343 template <>
1344 struct _LIBCPP_TEMPLATE_VIS hash<char16_t>
1345     : public unary_function<char16_t, size_t>
1346 {
1347     _LIBCPP_INLINE_VISIBILITY
1348     size_t operator()(char16_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1349 };
1350
1351 template <>
1352 struct _LIBCPP_TEMPLATE_VIS hash<char32_t>
1353     : public unary_function<char32_t, size_t>
1354 {
1355     _LIBCPP_INLINE_VISIBILITY
1356     size_t operator()(char32_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1357 };
1358
1359 #endif  // _LIBCPP_HAS_NO_UNICODE_CHARS
1360
1361 template <>
1362 struct _LIBCPP_TEMPLATE_VIS hash<wchar_t>
1363     : public unary_function<wchar_t, size_t>
1364 {
1365     _LIBCPP_INLINE_VISIBILITY
1366     size_t operator()(wchar_t __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1367 };
1368
1369 template <>
1370 struct _LIBCPP_TEMPLATE_VIS hash<short>
1371     : public unary_function<short, size_t>
1372 {
1373     _LIBCPP_INLINE_VISIBILITY
1374     size_t operator()(short __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1375 };
1376
1377 template <>
1378 struct _LIBCPP_TEMPLATE_VIS hash<unsigned short>
1379     : public unary_function<unsigned short, size_t>
1380 {
1381     _LIBCPP_INLINE_VISIBILITY
1382     size_t operator()(unsigned short __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1383 };
1384
1385 template <>
1386 struct _LIBCPP_TEMPLATE_VIS hash<int>
1387     : public unary_function<int, size_t>
1388 {
1389     _LIBCPP_INLINE_VISIBILITY
1390     size_t operator()(int __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1391 };
1392
1393 template <>
1394 struct _LIBCPP_TEMPLATE_VIS hash<unsigned int>
1395     : public unary_function<unsigned int, size_t>
1396 {
1397     _LIBCPP_INLINE_VISIBILITY
1398     size_t operator()(unsigned int __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1399 };
1400
1401 template <>
1402 struct _LIBCPP_TEMPLATE_VIS hash<long>
1403     : public unary_function<long, size_t>
1404 {
1405     _LIBCPP_INLINE_VISIBILITY
1406     size_t operator()(long __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1407 };
1408
1409 template <>
1410 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long>
1411     : public unary_function<unsigned long, size_t>
1412 {
1413     _LIBCPP_INLINE_VISIBILITY
1414     size_t operator()(unsigned long __v) const _NOEXCEPT {return static_cast<size_t>(__v);}
1415 };
1416
1417 template <>
1418 struct _LIBCPP_TEMPLATE_VIS hash<long long>
1419     : public __scalar_hash<long long>
1420 {
1421 };
1422
1423 template <>
1424 struct _LIBCPP_TEMPLATE_VIS hash<unsigned long long>
1425     : public __scalar_hash<unsigned long long>
1426 {
1427 };
1428
1429 #ifndef _LIBCPP_HAS_NO_INT128
1430
1431 template <>
1432 struct _LIBCPP_TEMPLATE_VIS hash<__int128_t>
1433     : public __scalar_hash<__int128_t>
1434 {
1435 };
1436
1437 template <>
1438 struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t>
1439     : public __scalar_hash<__uint128_t>
1440 {
1441 };
1442
1443 #endif
1444
1445 template <>
1446 struct _LIBCPP_TEMPLATE_VIS hash<float>
1447     : public __scalar_hash<float>
1448 {
1449     _LIBCPP_INLINE_VISIBILITY
1450     size_t operator()(float __v) const _NOEXCEPT
1451     {
1452         // -0.0 and 0.0 should return same hash
1453        if (__v == 0)
1454            return 0;
1455         return __scalar_hash<float>::operator()(__v);
1456     }
1457 };
1458
1459 template <>
1460 struct _LIBCPP_TEMPLATE_VIS hash<double>
1461     : public __scalar_hash<double>
1462 {
1463     _LIBCPP_INLINE_VISIBILITY
1464     size_t operator()(double __v) const _NOEXCEPT
1465     {
1466         // -0.0 and 0.0 should return same hash
1467        if (__v == 0)
1468            return 0;
1469         return __scalar_hash<double>::operator()(__v);
1470     }
1471 };
1472
1473 template <>
1474 struct _LIBCPP_TEMPLATE_VIS hash<long double>
1475     : public __scalar_hash<long double>
1476 {
1477     _LIBCPP_INLINE_VISIBILITY
1478     size_t operator()(long double __v) const _NOEXCEPT
1479     {
1480         // -0.0 and 0.0 should return same hash
1481         if (__v == 0)
1482             return 0;
1483 #if defined(__i386__)
1484         // Zero out padding bits
1485         union
1486         {
1487             long double __t;
1488             struct
1489             {
1490                 size_t __a;
1491                 size_t __b;
1492                 size_t __c;
1493                 size_t __d;
1494             } __s;
1495         } __u;
1496         __u.__s.__a = 0;
1497         __u.__s.__b = 0;
1498         __u.__s.__c = 0;
1499         __u.__s.__d = 0;
1500         __u.__t = __v;
1501         return __u.__s.__a ^ __u.__s.__b ^ __u.__s.__c ^ __u.__s.__d;
1502 #elif defined(__x86_64__)
1503         // Zero out padding bits
1504         union
1505         {
1506             long double __t;
1507             struct
1508             {
1509                 size_t __a;
1510                 size_t __b;
1511             } __s;
1512         } __u;
1513         __u.__s.__a = 0;
1514         __u.__s.__b = 0;
1515         __u.__t = __v;
1516         return __u.__s.__a ^ __u.__s.__b;
1517 #else
1518         return __scalar_hash<long double>::operator()(__v);
1519 #endif
1520     }
1521 };
1522
1523 #if _LIBCPP_STD_VER > 11
1524
1525 template <class _Tp, bool = is_enum<_Tp>::value>
1526 struct _LIBCPP_TEMPLATE_VIS __enum_hash
1527     : public unary_function<_Tp, size_t>
1528 {
1529     _LIBCPP_INLINE_VISIBILITY
1530     size_t operator()(_Tp __v) const _NOEXCEPT
1531     {
1532         typedef typename underlying_type<_Tp>::type type;
1533         return hash<type>{}(static_cast<type>(__v));
1534     }
1535 };
1536 template <class _Tp>
1537 struct _LIBCPP_TEMPLATE_VIS __enum_hash<_Tp, false> {
1538     __enum_hash() = delete;
1539     __enum_hash(__enum_hash const&) = delete;
1540     __enum_hash& operator=(__enum_hash const&) = delete;
1541 };
1542
1543 template <class _Tp>
1544 struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp>
1545 {
1546 };
1547 #endif
1548
1549 #if _LIBCPP_STD_VER > 14
1550
1551 template <>
1552 struct _LIBCPP_TEMPLATE_VIS hash<nullptr_t>
1553   : public unary_function<nullptr_t, size_t>
1554 {
1555   _LIBCPP_INLINE_VISIBILITY
1556   size_t operator()(nullptr_t) const _NOEXCEPT {
1557     return 662607004ull;
1558   }
1559 };
1560 #endif
1561
1562 #ifndef _LIBCPP_CXX03_LANG
1563 template <class _Key, class _Hash>
1564 using __check_hash_requirements = integral_constant<bool,
1565     is_copy_constructible<_Hash>::value &&
1566     is_move_constructible<_Hash>::value &&
1567     __invokable_r<size_t, _Hash, _Key const&>::value
1568 >;
1569
1570 template <class _Key, class _Hash = std::hash<_Key> >
1571 using __has_enabled_hash = integral_constant<bool,
1572     __check_hash_requirements<_Key, _Hash>::value &&
1573     is_default_constructible<_Hash>::value
1574 >;
1575
1576 #if _LIBCPP_STD_VER > 14
1577 template <class _Type, class>
1578 using __enable_hash_helper_imp = _Type;
1579
1580 template <class _Type, class ..._Keys>
1581 using __enable_hash_helper = __enable_hash_helper_imp<_Type,
1582   typename enable_if<__all<__has_enabled_hash<_Keys>::value...>::value>::type
1583 >;
1584 #else
1585 template <class _Type, class ...>
1586 using __enable_hash_helper = _Type;
1587 #endif
1588
1589 #endif // !_LIBCPP_CXX03_LANG
1590
1591 _LIBCPP_END_NAMESPACE_STD
1592
1593 #endif  // _LIBCPP_UTILITY