utility revision 360784 
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 T1, class T2>
62struct 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
90template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
91template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
92template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
93template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
94template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
95template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
96
97template <class T1, class T2> pair<V1, V2> make_pair(T1&&, T2&&);   // constexpr in C++14
98template <class T1, class T2>
99void
100swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y)));
101
102struct piecewise_construct_t { explicit piecewise_construct_t() = default; };
103inline constexpr piecewise_construct_t piecewise_construct = piecewise_construct_t();
104
105template <class T> struct tuple_size;
106template <size_t I, class T> struct tuple_element;
107
108template <class T1, class T2> struct tuple_size<pair<T1, T2> >;
109template <class T1, class T2> struct tuple_element<0, pair<T1, T2> >;
110template <class T1, class T2> struct tuple_element<1, pair<T1, T2> >;
111
112template<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
116template<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
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<class T1, class T2>
129    constexpr T1& get(pair<T1, T2>&) noexcept; // C++14
130
131template<class T1, class T2>
132    constexpr const T1& get(const pair<T1, T2>&) noexcept; // C++14
133
134template<class T1, class T2>
135    constexpr T1&& get(pair<T1, T2>&&) noexcept; // C++14
136
137template<class T1, class T2>
138    constexpr const T1&& get(const pair<T1, T2>&&) noexcept; // C++14
139
140template<class T1, class T2>
141    constexpr T1& get(pair<T2, T1>&) noexcept; // C++14
142
143template<class T1, class T2>
144    constexpr const T1& get(const pair<T2, T1>&) noexcept; // C++14
145
146template<class T1, class T2>
147    constexpr T1&& get(pair<T2, T1>&&) noexcept; // C++14
148
149template<class T1, class T2>
150    constexpr const T1&& get(const pair<T2, T1>&&) noexcept; // C++14
151
152// C++14
153
154template<class T, T... I>
155struct integer_sequence
156{
157    typedef T value_type;
158
159    static constexpr size_t size() noexcept;
160};
161
162template<size_t... I>
163  using index_sequence = integer_sequence<size_t, I...>;
164
165template<class T, T N>
166  using make_integer_sequence = integer_sequence<T, 0, 1, ..., N-1>;
167template<size_t N>
168  using make_index_sequence = make_integer_sequence<size_t, N>;
169
170template<class... T>
171  using index_sequence_for = make_index_sequence<sizeof...(T)>;
172
173template<class T, class U=T>
174    T exchange(T& obj, U&& new_value);
175
176// 20.2.7, in-place construction // C++17
177struct in_place_t {
178  explicit in_place_t() = default;
179};
180inline constexpr in_place_t in_place{};
181template <class T>
182  struct in_place_type_t {
183    explicit in_place_type_t() = default;
184  };
185template <class T>
186  inline constexpr in_place_type_t<T> in_place_type{};
187template <size_t I>
188  struct in_place_index_t {
189    explicit in_place_index_t() = default;
190  };
191template <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
214namespace rel_ops
215{
216
217template<class _Tp>
218inline _LIBCPP_INLINE_VISIBILITY
219bool
220operator!=(const _Tp& __x, const _Tp& __y)
221{
222    return !(__x == __y);
223}
224
225template<class _Tp>
226inline _LIBCPP_INLINE_VISIBILITY
227bool
228operator> (const _Tp& __x, const _Tp& __y)
229{
230    return __y < __x;
231}
232
233template<class _Tp>
234inline _LIBCPP_INLINE_VISIBILITY
235bool
236operator<=(const _Tp& __x, const _Tp& __y)
237{
238    return !(__y < __x);
239}
240
241template<class _Tp>
242inline _LIBCPP_INLINE_VISIBILITY
243bool
244operator>=(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
257template <class _Tp>
258inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
259#ifndef _LIBCPP_CXX03_LANG
260typename 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
267const _Tp&
268#endif
269move_if_noexcept(_Tp& __x) _NOEXCEPT
270{
271    return _VSTD::move(__x);
272}
273
274#if _LIBCPP_STD_VER > 14
275template <class _Tp> constexpr add_const_t<_Tp>& as_const(_Tp& __t) noexcept { return __t; }
276template <class _Tp>                        void as_const(const _Tp&&) = delete;
277#endif
278
279struct _LIBCPP_TEMPLATE_VIS piecewise_construct_t { explicit piecewise_construct_t() = default; };
280#if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY)
281extern _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)
287template <class, class>
288struct __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
296template <class _T1, class _T2>
297struct _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    }
557private:
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
569template<class _T1, class _T2>
570pair(_T1, _T2) -> pair<_T1, _T2>;
571#endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES
572
573template <class _T1, class _T2>
574inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
575bool
576operator==(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
577{
578    return __x.first == __y.first && __x.second == __y.second;
579}
580
581template <class _T1, class _T2>
582inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
583bool
584operator!=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
585{
586    return !(__x == __y);
587}
588
589template <class _T1, class _T2>
590inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
591bool
592operator< (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
597template <class _T1, class _T2>
598inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
599bool
600operator> (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
601{
602    return __y < __x;
603}
604
605template <class _T1, class _T2>
606inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
607bool
608operator>=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
609{
610    return !(__x < __y);
611}
612
613template <class _T1, class _T2>
614inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
615bool
616operator<=(const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
617{
618    return !(__y < __x);
619}
620
621template <class _T1, class _T2>
622inline _LIBCPP_INLINE_VISIBILITY
623typename enable_if
624<
625    __is_swappable<_T1>::value &&
626    __is_swappable<_T2>::value,
627    void
628>::type
629swap(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
636template <class _Tp>
637struct __unwrap_reference { typedef _LIBCPP_NODEBUG_TYPE _Tp type; };
638
639template <class _Tp>
640struct __unwrap_reference<reference_wrapper<_Tp> > { typedef _LIBCPP_NODEBUG_TYPE _Tp& type; };
641
642#if _LIBCPP_STD_VER > 17
643template <class _Tp>
644struct unwrap_reference : __unwrap_reference<_Tp> { };
645
646template <class _Tp>
647struct unwrap_ref_decay : unwrap_reference<typename decay<_Tp>::type> { };
648#endif // > C++17
649
650template <class _Tp>
651struct __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
661template <class _T1, class _T2>
662inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
663pair<typename __unwrap_ref_decay<_T1>::type, typename __unwrap_ref_decay<_T2>::type>
664make_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
672template <class _T1, class _T2>
673inline _LIBCPP_INLINE_VISIBILITY
674pair<_T1,_T2>
675make_pair(_T1 __x, _T2 __y)
676{
677    return pair<_T1, _T2>(__x, __y);
678}
679
680#endif  // _LIBCPP_CXX03_LANG
681
682template <class _T1, class _T2>
683  struct _LIBCPP_TEMPLATE_VIS tuple_size<pair<_T1, _T2> >
684    : public integral_constant<size_t, 2> {};
685
686template <size_t _Ip, class _T1, class _T2>
687struct _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
692template <class _T1, class _T2>
693struct _LIBCPP_TEMPLATE_VIS tuple_element<0, pair<_T1, _T2> >
694{
695    typedef _LIBCPP_NODEBUG_TYPE _T1 type;
696};
697
698template <class _T1, class _T2>
699struct _LIBCPP_TEMPLATE_VIS tuple_element<1, pair<_T1, _T2> >
700{
701    typedef _LIBCPP_NODEBUG_TYPE _T2 type;
702};
703
704template <size_t _Ip> struct __get_pair;
705
706template <>
707struct __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
736template <>
737struct __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
766template <size_t _Ip, class _T1, class _T2>
767inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
768typename tuple_element<_Ip, pair<_T1, _T2> >::type&
769get(pair<_T1, _T2>& __p) _NOEXCEPT
770{
771    return __get_pair<_Ip>::get(__p);
772}
773
774template <size_t _Ip, class _T1, class _T2>
775inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
776const typename tuple_element<_Ip, pair<_T1, _T2> >::type&
777get(const pair<_T1, _T2>& __p) _NOEXCEPT
778{
779    return __get_pair<_Ip>::get(__p);
780}
781
782#ifndef _LIBCPP_CXX03_LANG
783template <size_t _Ip, class _T1, class _T2>
784inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
785typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
786get(pair<_T1, _T2>&& __p) _NOEXCEPT
787{
788    return __get_pair<_Ip>::get(_VSTD::move(__p));
789}
790
791template <size_t _Ip, class _T1, class _T2>
792inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
793const typename tuple_element<_Ip, pair<_T1, _T2> >::type&&
794get(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
801template <class _T1, class _T2>
802inline _LIBCPP_INLINE_VISIBILITY
803constexpr _T1 & get(pair<_T1, _T2>& __p) _NOEXCEPT
804{
805    return __get_pair<0>::get(__p);
806}
807
808template <class _T1, class _T2>
809inline _LIBCPP_INLINE_VISIBILITY
810constexpr _T1 const & get(pair<_T1, _T2> const& __p) _NOEXCEPT
811{
812    return __get_pair<0>::get(__p);
813}
814
815template <class _T1, class _T2>
816inline _LIBCPP_INLINE_VISIBILITY
817constexpr _T1 && get(pair<_T1, _T2>&& __p) _NOEXCEPT
818{
819    return __get_pair<0>::get(_VSTD::move(__p));
820}
821
822template <class _T1, class _T2>
823inline _LIBCPP_INLINE_VISIBILITY
824constexpr _T1 const && get(pair<_T1, _T2> const&& __p) _NOEXCEPT
825{
826    return __get_pair<0>::get(_VSTD::move(__p));
827}
828
829template <class _T1, class _T2>
830inline _LIBCPP_INLINE_VISIBILITY
831constexpr _T1 & get(pair<_T2, _T1>& __p) _NOEXCEPT
832{
833    return __get_pair<1>::get(__p);
834}
835
836template <class _T1, class _T2>
837inline _LIBCPP_INLINE_VISIBILITY
838constexpr _T1 const & get(pair<_T2, _T1> const& __p) _NOEXCEPT
839{
840    return __get_pair<1>::get(__p);
841}
842
843template <class _T1, class _T2>
844inline _LIBCPP_INLINE_VISIBILITY
845constexpr _T1 && get(pair<_T2, _T1>&& __p) _NOEXCEPT
846{
847    return __get_pair<1>::get(_VSTD::move(__p));
848}
849
850template <class _T1, class _T2>
851inline _LIBCPP_INLINE_VISIBILITY
852constexpr _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
861template<class _Tp, _Tp... _Ip>
862struct _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
874template<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
879template <class _Tp, _Tp _Ep>
880using __make_integer_sequence _LIBCPP_NODEBUG_TYPE = __make_integer_seq<integer_sequence, _Tp, _Ep>;
881
882#else
883
884template<typename _Tp, _Tp _Np> using __make_integer_sequence_unchecked _LIBCPP_NODEBUG_TYPE  =
885  typename __detail::__make<_Np>::type::template __convert<integer_sequence, _Tp>;
886
887template <class _Tp, _Tp _Ep>
888struct __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
898template <class _Tp, _Tp _Ep>
899using __make_integer_sequence _LIBCPP_NODEBUG_TYPE = typename __make_integer_sequence_checked<_Tp, _Ep>::type;
900
901#endif
902
903template<class _Tp, _Tp _Np>
904    using make_integer_sequence = __make_integer_sequence<_Tp, _Np>;
905
906template<size_t _Np>
907    using make_index_sequence = make_integer_sequence<size_t, _Np>;
908
909template<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
915template<class _T1, class _T2 = _T1>
916inline _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
927struct _LIBCPP_TYPE_VIS in_place_t {
928    explicit in_place_t() = default;
929};
930_LIBCPP_INLINE_VAR constexpr in_place_t in_place{};
931
932template <class _Tp>
933struct _LIBCPP_TEMPLATE_VIS in_place_type_t {
934    explicit in_place_type_t() = default;
935};
936template <class _Tp>
937_LIBCPP_INLINE_VAR constexpr in_place_type_t<_Tp> in_place_type{};
938
939template <size_t _Idx>
940struct _LIBCPP_TYPE_VIS in_place_index_t {
941    explicit in_place_index_t() = default;
942};
943template <size_t _Idx>
944_LIBCPP_INLINE_VAR constexpr in_place_index_t<_Idx> in_place_index{};
945
946template <class _Tp> struct __is_inplace_type_imp : false_type {};
947template <class _Tp> struct __is_inplace_type_imp<in_place_type_t<_Tp>> : true_type {};
948
949template <class _Tp>
950using __is_inplace_type = __is_inplace_type_imp<__uncvref_t<_Tp>>;
951
952template <class _Tp> struct __is_inplace_index_imp : false_type {};
953template <size_t _Idx> struct __is_inplace_index_imp<in_place_index_t<_Idx>> : true_type {};
954
955template <class _Tp>
956using __is_inplace_index = __is_inplace_index_imp<__uncvref_t<_Tp>>;
957
958#endif // _LIBCPP_STD_VER > 14
959
960template <class _Arg, class _Result>
961struct _LIBCPP_TEMPLATE_VIS unary_function
962{
963    typedef _Arg    argument_type;
964    typedef _Result result_type;
965};
966
967template <class _Size>
968inline _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.
980template <class _Size, size_t = sizeof(_Size)*__CHAR_BIT__>
981struct __murmur2_or_cityhash;
982
983template <class _Size>
984struct __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
991template <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
1026template <class _Size>
1027struct __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
1155template <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
1201template <class _Tp, size_t = sizeof(_Tp) / sizeof(size_t)>
1202struct __scalar_hash;
1203
1204template <class _Tp>
1205struct __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
1222template <class _Tp>
1223struct __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
1239template <class _Tp>
1240struct __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
1260template <class _Tp>
1261struct __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
1282template <class _Tp>
1283struct __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
1305struct _PairT {
1306  size_t first;
1307  size_t second;
1308};
1309
1310_LIBCPP_INLINE_VISIBILITY
1311inline 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
1317template<class _Tp>
1318struct _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
1335template <>
1336struct _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
1343template <>
1344struct _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
1351template <>
1352struct _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
1359template <>
1360struct _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
1369template <>
1370struct _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
1377template <>
1378struct _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
1387template <>
1388struct _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
1395template <>
1396struct _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
1403template <>
1404struct _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
1411template <>
1412struct _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
1419template <>
1420struct _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
1427template <>
1428struct _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
1435template <>
1436struct _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
1443template <>
1444struct _LIBCPP_TEMPLATE_VIS hash<long long>
1445    : public __scalar_hash<long long>
1446{
1447};
1448
1449template <>
1450struct _LIBCPP_TEMPLATE_VIS hash<unsigned long long>
1451    : public __scalar_hash<unsigned long long>
1452{
1453};
1454
1455#ifndef _LIBCPP_HAS_NO_INT128
1456
1457template <>
1458struct _LIBCPP_TEMPLATE_VIS hash<__int128_t>
1459    : public __scalar_hash<__int128_t>
1460{
1461};
1462
1463template <>
1464struct _LIBCPP_TEMPLATE_VIS hash<__uint128_t>
1465    : public __scalar_hash<__uint128_t>
1466{
1467};
1468
1469#endif
1470
1471template <>
1472struct _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
1485template <>
1486struct _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
1499template <>
1500struct _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
1551template <class _Tp, bool = is_enum<_Tp>::value>
1552struct _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};
1562template <class _Tp>
1563struct _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
1569template <class _Tp>
1570struct _LIBCPP_TEMPLATE_VIS hash : public __enum_hash<_Tp>
1571{
1572};
1573#endif
1574
1575#if _LIBCPP_STD_VER > 14
1576
1577template <>
1578struct _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
1589template <class _Key, class _Hash>
1590using __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
1596template <class _Key, class _Hash = std::hash<_Key> >
1597using __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
1603template <class _Type, class>
1604using __enable_hash_helper_imp _LIBCPP_NODEBUG_TYPE  = _Type;
1605
1606template <class _Type, class ..._Keys>
1607using __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
1611template <class _Type, class ...>
1612using __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
1620