contrib/llvm-project/libcxx/include/utility

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