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