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