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