1// -*- C++ -*-
2//===------------------------ functional ----------------------------------===//
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_FUNCTIONAL
11#define _LIBCPP_FUNCTIONAL
12
13/*
14    functional synopsis
15
16namespace std
17{
18
19template <class Arg, class Result>
20struct unary_function
21{
22    typedef Arg    argument_type;
23    typedef Result result_type;
24};
25
26template <class Arg1, class Arg2, class Result>
27struct binary_function
28{
29    typedef Arg1   first_argument_type;
30    typedef Arg2   second_argument_type;
31    typedef Result result_type;
32};
33
34template <class T>
35class reference_wrapper
36    : public unary_function<T1, R> // if wrapping a unary functor
37    : public binary_function<T1, T2, R> // if wraping a binary functor
38{
39public:
40    // types
41    typedef T type;
42    typedef see below result_type; // Not always defined
43
44    // construct/copy/destroy
45    template<class U>
46      reference_wrapper(U&&);
47    reference_wrapper(const reference_wrapper<T>& x) noexcept;
48
49    // assignment
50    reference_wrapper& operator=(const reference_wrapper<T>& x) noexcept;
51
52    // access
53    operator T& () const noexcept;
54    T& get() const noexcept;
55
56    // invoke
57    template <class... ArgTypes>
58      typename result_of<T&(ArgTypes&&...)>::type
59          operator() (ArgTypes&&...) const;
60};
61
62template <class T>
63  reference_wrapper(T&) -> reference_wrapper<T>;
64
65template <class T> reference_wrapper<T> ref(T& t) noexcept;
66template <class T> void ref(const T&& t) = delete;
67template <class T> reference_wrapper<T> ref(reference_wrapper<T>t) noexcept;
68
69template <class T> reference_wrapper<const T> cref(const T& t) noexcept;
70template <class T> void cref(const T&& t) = delete;
71template <class T> reference_wrapper<const T> cref(reference_wrapper<T> t) noexcept;
72
73template <class T> struct unwrap_reference;                                       // since C++20
74template <class T> struct unwrap_ref_decay : unwrap_reference<decay_t<T>> { };    // since C++20
75template <class T> using unwrap_reference_t = typename unwrap_reference<T>::type; // since C++20
76template <class T> using unwrap_ref_decay_t = typename unwrap_ref_decay<T>::type; // since C++20
77
78template <class T> // <class T=void> in C++14
79struct plus {
80    T operator()(const T& x, const T& y) const;
81};
82
83template <class T> // <class T=void> in C++14
84struct minus {
85    T operator()(const T& x, const T& y) const;
86};
87
88template <class T> // <class T=void> in C++14
89struct multiplies {
90    T operator()(const T& x, const T& y) const;
91};
92
93template <class T> // <class T=void> in C++14
94struct divides {
95    T operator()(const T& x, const T& y) const;
96};
97
98template <class T> // <class T=void> in C++14
99struct modulus {
100    T operator()(const T& x, const T& y) const;
101};
102
103template <class T> // <class T=void> in C++14
104struct negate {
105    T operator()(const T& x) const;
106};
107
108template <class T> // <class T=void> in C++14
109struct equal_to {
110    bool operator()(const T& x, const T& y) const;
111};
112
113template <class T> // <class T=void> in C++14
114struct not_equal_to {
115    bool operator()(const T& x, const T& y) const;
116};
117
118template <class T> // <class T=void> in C++14
119struct greater {
120    bool operator()(const T& x, const T& y) const;
121};
122
123template <class T> // <class T=void> in C++14
124struct less {
125    bool operator()(const T& x, const T& y) const;
126};
127
128template <class T> // <class T=void> in C++14
129struct greater_equal {
130    bool operator()(const T& x, const T& y) const;
131};
132
133template <class T> // <class T=void> in C++14
134struct less_equal {
135    bool operator()(const T& x, const T& y) const;
136};
137
138template <class T> // <class T=void> in C++14
139struct logical_and {
140    bool operator()(const T& x, const T& y) const;
141};
142
143template <class T> // <class T=void> in C++14
144struct logical_or {
145    bool operator()(const T& x, const T& y) const;
146};
147
148template <class T> // <class T=void> in C++14
149struct logical_not {
150    bool operator()(const T& x) const;
151};
152
153template <class T> // <class T=void> in C++14
154struct bit_and {
155    T operator()(const T& x, const T& y) const;
156};
157
158template <class T> // <class T=void> in C++14
159struct bit_or {
160    T operator()(const T& x, const T& y) const;
161};
162
163template <class T> // <class T=void> in C++14
164struct bit_xor {
165    T operator()(const T& x, const T& y) const;
166};
167
168template <class T=void> // C++14
169struct bit_not {
170    T operator()(const T& x) const;
171};
172
173struct identity; // C++20
174
175template <class Predicate>
176class unary_negate // deprecated in C++17, removed in C++20
177    : public unary_function<typename Predicate::argument_type, bool>
178{
179public:
180    explicit unary_negate(const Predicate& pred);
181    bool operator()(const typename Predicate::argument_type& x) const;
182};
183
184template <class Predicate> // deprecated in C++17, removed in C++20
185unary_negate<Predicate> not1(const Predicate& pred);
186
187template <class Predicate>
188class binary_negate // deprecated in C++17, removed in C++20
189    : public binary_function<typename Predicate::first_argument_type,
190                             typename Predicate::second_argument_type,
191                             bool>
192{
193public:
194    explicit binary_negate(const Predicate& pred);
195    bool operator()(const typename Predicate::first_argument_type& x,
196                    const typename Predicate::second_argument_type& y) const;
197};
198
199template <class Predicate> // deprecated in C++17, removed in C++20
200binary_negate<Predicate> not2(const Predicate& pred);
201
202template <class F>
203constexpr unspecified not_fn(F&& f); // C++17, constexpr in C++20
204
205template<class T> struct is_bind_expression;
206template<class T> struct is_placeholder;
207
208    // See C++14 20.9.9, Function object binders
209template <class T> inline constexpr bool is_bind_expression_v
210  = is_bind_expression<T>::value; // C++17
211template <class T> inline constexpr int is_placeholder_v
212  = is_placeholder<T>::value; // C++17
213
214
215template<class Fn, class... BoundArgs>
216  constexpr unspecified bind(Fn&&, BoundArgs&&...);  // constexpr in C++20
217template<class R, class Fn, class... BoundArgs>
218  constexpr unspecified bind(Fn&&, BoundArgs&&...);  // constexpr in C++20
219
220template<class F, class... Args>
221 constexpr // constexpr in C++20
222 invoke_result_t<F, Args...> invoke(F&& f, Args&&... args) // C++17
223    noexcept(is_nothrow_invocable_v<F, Args...>);
224
225namespace placeholders {
226  // M is the implementation-defined number of placeholders
227  extern unspecified _1;
228  extern unspecified _2;
229  .
230  .
231  .
232  extern unspecified _Mp;
233}
234
235template <class Operation>
236class binder1st     // deprecated in C++11, removed in C++17
237    : public unary_function<typename Operation::second_argument_type,
238                            typename Operation::result_type>
239{
240protected:
241    Operation                               op;
242    typename Operation::first_argument_type value;
243public:
244    binder1st(const Operation& x, const typename Operation::first_argument_type y);
245    typename Operation::result_type operator()(      typename Operation::second_argument_type& x) const;
246    typename Operation::result_type operator()(const typename Operation::second_argument_type& x) const;
247};
248
249template <class Operation, class T>
250binder1st<Operation> bind1st(const Operation& op, const T& x);  // deprecated in C++11, removed in C++17
251
252template <class Operation>
253class binder2nd     // deprecated in C++11, removed in C++17
254    : public unary_function<typename Operation::first_argument_type,
255                            typename Operation::result_type>
256{
257protected:
258    Operation                                op;
259    typename Operation::second_argument_type value;
260public:
261    binder2nd(const Operation& x, const typename Operation::second_argument_type y);
262    typename Operation::result_type operator()(      typename Operation::first_argument_type& x) const;
263    typename Operation::result_type operator()(const typename Operation::first_argument_type& x) const;
264};
265
266template <class Operation, class T>
267binder2nd<Operation> bind2nd(const Operation& op, const T& x);  // deprecated in C++11, removed in C++17
268
269template <class Arg, class Result>      // deprecated in C++11, removed in C++17
270class pointer_to_unary_function : public unary_function<Arg, Result>
271{
272public:
273    explicit pointer_to_unary_function(Result (*f)(Arg));
274    Result operator()(Arg x) const;
275};
276
277template <class Arg, class Result>
278pointer_to_unary_function<Arg,Result> ptr_fun(Result (*f)(Arg));      // deprecated in C++11, removed in C++17
279
280template <class Arg1, class Arg2, class Result>      // deprecated in C++11, removed in C++17
281class pointer_to_binary_function : public binary_function<Arg1, Arg2, Result>
282{
283public:
284    explicit pointer_to_binary_function(Result (*f)(Arg1, Arg2));
285    Result operator()(Arg1 x, Arg2 y) const;
286};
287
288template <class Arg1, class Arg2, class Result>
289pointer_to_binary_function<Arg1,Arg2,Result> ptr_fun(Result (*f)(Arg1,Arg2));      // deprecated in C++11, removed in C++17
290
291template<class S, class T>      // deprecated in C++11, removed in C++17
292class mem_fun_t : public unary_function<T*, S>
293{
294public:
295    explicit mem_fun_t(S (T::*p)());
296    S operator()(T* p) const;
297};
298
299template<class S, class T, class A>
300class mem_fun1_t : public binary_function<T*, A, S>      // deprecated in C++11, removed in C++17
301{
302public:
303    explicit mem_fun1_t(S (T::*p)(A));
304    S operator()(T* p, A x) const;
305};
306
307template<class S, class T>          mem_fun_t<S,T>    mem_fun(S (T::*f)());      // deprecated in C++11, removed in C++17
308template<class S, class T, class A> mem_fun1_t<S,T,A> mem_fun(S (T::*f)(A));     // deprecated in C++11, removed in C++17
309
310template<class S, class T>
311class mem_fun_ref_t : public unary_function<T, S>      // deprecated in C++11, removed in C++17
312{
313public:
314    explicit mem_fun_ref_t(S (T::*p)());
315    S operator()(T& p) const;
316};
317
318template<class S, class T, class A>
319class mem_fun1_ref_t : public binary_function<T, A, S>      // deprecated in C++11, removed in C++17
320{
321public:
322    explicit mem_fun1_ref_t(S (T::*p)(A));
323    S operator()(T& p, A x) const;
324};
325
326template<class S, class T>          mem_fun_ref_t<S,T>    mem_fun_ref(S (T::*f)());      // deprecated in C++11, removed in C++17
327template<class S, class T, class A> mem_fun1_ref_t<S,T,A> mem_fun_ref(S (T::*f)(A));     // deprecated in C++11, removed in C++17
328
329template <class S, class T>
330class const_mem_fun_t : public unary_function<const T*, S>      // deprecated in C++11, removed in C++17
331{
332public:
333    explicit const_mem_fun_t(S (T::*p)() const);
334    S operator()(const T* p) const;
335};
336
337template <class S, class T, class A>
338class const_mem_fun1_t : public binary_function<const T*, A, S>      // deprecated in C++11, removed in C++17
339{
340public:
341    explicit const_mem_fun1_t(S (T::*p)(A) const);
342    S operator()(const T* p, A x) const;
343};
344
345template <class S, class T>          const_mem_fun_t<S,T>    mem_fun(S (T::*f)() const);      // deprecated in C++11, removed in C++17
346template <class S, class T, class A> const_mem_fun1_t<S,T,A> mem_fun(S (T::*f)(A) const);     // deprecated in C++11, removed in C++17
347
348template <class S, class T>
349class const_mem_fun_ref_t : public unary_function<T, S>      // deprecated in C++11, removed in C++17
350{
351public:
352    explicit const_mem_fun_ref_t(S (T::*p)() const);
353    S operator()(const T& p) const;
354};
355
356template <class S, class T, class A>
357class const_mem_fun1_ref_t : public binary_function<T, A, S>      // deprecated in C++11, removed in C++17
358{
359public:
360    explicit const_mem_fun1_ref_t(S (T::*p)(A) const);
361    S operator()(const T& p, A x) const;
362};
363
364template <class S, class T>          const_mem_fun_ref_t<S,T>    mem_fun_ref(S (T::*f)() const);   // deprecated in C++11, removed in C++17
365template <class S, class T, class A> const_mem_fun1_ref_t<S,T,A> mem_fun_ref(S (T::*f)(A) const);  // deprecated in C++11, removed in C++17
366
367template<class R, class T>
368constexpr unspecified mem_fn(R T::*); // constexpr in C++20
369
370class bad_function_call
371    : public exception
372{
373};
374
375template<class> class function; // undefined
376
377template<class R, class... ArgTypes>
378class function<R(ArgTypes...)>
379  : public unary_function<T1, R>      // iff sizeof...(ArgTypes) == 1 and
380                                      // ArgTypes contains T1
381  : public binary_function<T1, T2, R> // iff sizeof...(ArgTypes) == 2 and
382                                      // ArgTypes contains T1 and T2
383{
384public:
385    typedef R result_type;
386
387    // construct/copy/destroy:
388    function() noexcept;
389    function(nullptr_t) noexcept;
390    function(const function&);
391    function(function&&) noexcept;
392    template<class F>
393      function(F);
394    template<Allocator Alloc>
395      function(allocator_arg_t, const Alloc&) noexcept;            // removed in C++17
396    template<Allocator Alloc>
397      function(allocator_arg_t, const Alloc&, nullptr_t) noexcept; // removed in C++17
398    template<Allocator Alloc>
399      function(allocator_arg_t, const Alloc&, const function&);    // removed in C++17
400    template<Allocator Alloc>
401      function(allocator_arg_t, const Alloc&, function&&);         // removed in C++17
402    template<class F, Allocator Alloc>
403      function(allocator_arg_t, const Alloc&, F);                  // removed in C++17
404
405    function& operator=(const function&);
406    function& operator=(function&&) noexcept;
407    function& operator=(nullptr_t) noexcept;
408    template<class F>
409      function& operator=(F&&);
410    template<class F>
411      function& operator=(reference_wrapper<F>) noexcept;
412
413    ~function();
414
415    // function modifiers:
416    void swap(function&) noexcept;
417    template<class F, class Alloc>
418      void assign(F&&, const Alloc&);                 // Removed in C++17
419
420    // function capacity:
421    explicit operator bool() const noexcept;
422
423    // function invocation:
424    R operator()(ArgTypes...) const;
425
426    // function target access:
427    const std::type_info& target_type() const noexcept;
428    template <typename T>       T* target() noexcept;
429    template <typename T> const T* target() const noexcept;
430};
431
432// Deduction guides
433template<class R, class ...Args>
434function(R(*)(Args...)) -> function<R(Args...)>; // since C++17
435
436template<class F>
437function(F) -> function<see-below>; // since C++17
438
439// Null pointer comparisons:
440template <class R, class ... ArgTypes>
441  bool operator==(const function<R(ArgTypes...)>&, nullptr_t) noexcept;
442
443template <class R, class ... ArgTypes>
444  bool operator==(nullptr_t, const function<R(ArgTypes...)>&) noexcept;
445
446template <class R, class ... ArgTypes>
447  bool operator!=(const function<R(ArgTypes...)>&, nullptr_t) noexcept;
448
449template <class  R, class ... ArgTypes>
450  bool operator!=(nullptr_t, const function<R(ArgTypes...)>&) noexcept;
451
452// specialized algorithms:
453template <class  R, class ... ArgTypes>
454  void swap(function<R(ArgTypes...)>&, function<R(ArgTypes...)>&) noexcept;
455
456template <class T> struct hash;
457
458template <> struct hash<bool>;
459template <> struct hash<char>;
460template <> struct hash<signed char>;
461template <> struct hash<unsigned char>;
462template <> struct hash<char8_t>; // since C++20
463template <> struct hash<char16_t>;
464template <> struct hash<char32_t>;
465template <> struct hash<wchar_t>;
466template <> struct hash<short>;
467template <> struct hash<unsigned short>;
468template <> struct hash<int>;
469template <> struct hash<unsigned int>;
470template <> struct hash<long>;
471template <> struct hash<long long>;
472template <> struct hash<unsigned long>;
473template <> struct hash<unsigned long long>;
474
475template <> struct hash<float>;
476template <> struct hash<double>;
477template <> struct hash<long double>;
478
479template<class T> struct hash<T*>;
480template <> struct hash<nullptr_t>;  // C++17
481
482}  // std
483
484POLICY:  For non-variadic implementations, the number of arguments is limited
485         to 3.  It is hoped that the need for non-variadic implementations
486         will be minimal.
487
488*/
489
490#include <__config>
491#include <__debug>
492#include <__functional_base>
493#include <concepts>
494#include <exception>
495#include <memory>
496#include <tuple>
497#include <type_traits>
498#include <typeinfo>
499#include <utility>
500#include <version>
501
502#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
503#pragma GCC system_header
504#endif
505
506_LIBCPP_BEGIN_NAMESPACE_STD
507
508_LIBCPP_SUPPRESS_DEPRECATED_PUSH
509#if _LIBCPP_STD_VER > 11
510template <class _Tp = void>
511#else
512template <class _Tp>
513#endif
514struct _LIBCPP_TEMPLATE_VIS plus
515#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
516    : binary_function<_Tp, _Tp, _Tp>
517#endif
518{
519_LIBCPP_SUPPRESS_DEPRECATED_POP
520    typedef _Tp __result_type;  // used by valarray
521#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
522    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
523    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
524    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
525#endif
526    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
527    _Tp operator()(const _Tp& __x, const _Tp& __y) const
528        {return __x + __y;}
529};
530
531#if _LIBCPP_STD_VER > 11
532template <>
533struct _LIBCPP_TEMPLATE_VIS plus<void>
534{
535    template <class _T1, class _T2>
536    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
537    auto operator()(_T1&& __t, _T2&& __u) const
538    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u)))
539    -> decltype        (_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u))
540        { return        _VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u); }
541    typedef void is_transparent;
542};
543#endif
544
545
546_LIBCPP_SUPPRESS_DEPRECATED_PUSH
547#if _LIBCPP_STD_VER > 11
548template <class _Tp = void>
549#else
550template <class _Tp>
551#endif
552struct _LIBCPP_TEMPLATE_VIS minus
553#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
554    : binary_function<_Tp, _Tp, _Tp>
555#endif
556{
557_LIBCPP_SUPPRESS_DEPRECATED_POP
558    typedef _Tp __result_type;  // used by valarray
559#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
560    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
561    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
562    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
563#endif
564    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
565    _Tp operator()(const _Tp& __x, const _Tp& __y) const
566        {return __x - __y;}
567};
568
569#if _LIBCPP_STD_VER > 11
570template <>
571struct _LIBCPP_TEMPLATE_VIS minus<void>
572{
573    template <class _T1, class _T2>
574    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
575    auto operator()(_T1&& __t, _T2&& __u) const
576    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) - _VSTD::forward<_T2>(__u)))
577    -> decltype        (_VSTD::forward<_T1>(__t) - _VSTD::forward<_T2>(__u))
578        { return        _VSTD::forward<_T1>(__t) - _VSTD::forward<_T2>(__u); }
579    typedef void is_transparent;
580};
581#endif
582
583
584_LIBCPP_SUPPRESS_DEPRECATED_PUSH
585#if _LIBCPP_STD_VER > 11
586template <class _Tp = void>
587#else
588template <class _Tp>
589#endif
590struct _LIBCPP_TEMPLATE_VIS multiplies
591#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
592    : binary_function<_Tp, _Tp, _Tp>
593#endif
594{
595_LIBCPP_SUPPRESS_DEPRECATED_POP
596    typedef _Tp __result_type;  // used by valarray
597#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
598    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
599    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
600    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
601#endif
602    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
603    _Tp operator()(const _Tp& __x, const _Tp& __y) const
604        {return __x * __y;}
605};
606
607#if _LIBCPP_STD_VER > 11
608template <>
609struct _LIBCPP_TEMPLATE_VIS multiplies<void>
610{
611    template <class _T1, class _T2>
612    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
613    auto operator()(_T1&& __t, _T2&& __u) const
614    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) * _VSTD::forward<_T2>(__u)))
615    -> decltype        (_VSTD::forward<_T1>(__t) * _VSTD::forward<_T2>(__u))
616        { return        _VSTD::forward<_T1>(__t) * _VSTD::forward<_T2>(__u); }
617    typedef void is_transparent;
618};
619#endif
620
621
622_LIBCPP_SUPPRESS_DEPRECATED_PUSH
623#if _LIBCPP_STD_VER > 11
624template <class _Tp = void>
625#else
626template <class _Tp>
627#endif
628struct _LIBCPP_TEMPLATE_VIS divides
629#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
630    : binary_function<_Tp, _Tp, _Tp>
631#endif
632{
633_LIBCPP_SUPPRESS_DEPRECATED_POP
634    typedef _Tp __result_type;  // used by valarray
635#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
636    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
637    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
638    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
639#endif
640    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
641    _Tp operator()(const _Tp& __x, const _Tp& __y) const
642        {return __x / __y;}
643};
644
645#if _LIBCPP_STD_VER > 11
646template <>
647struct _LIBCPP_TEMPLATE_VIS divides<void>
648{
649    template <class _T1, class _T2>
650    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
651    auto operator()(_T1&& __t, _T2&& __u) const
652    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) / _VSTD::forward<_T2>(__u)))
653    -> decltype        (_VSTD::forward<_T1>(__t) / _VSTD::forward<_T2>(__u))
654        { return        _VSTD::forward<_T1>(__t) / _VSTD::forward<_T2>(__u); }
655    typedef void is_transparent;
656};
657#endif
658
659
660_LIBCPP_SUPPRESS_DEPRECATED_PUSH
661#if _LIBCPP_STD_VER > 11
662template <class _Tp = void>
663#else
664template <class _Tp>
665#endif
666struct _LIBCPP_TEMPLATE_VIS modulus
667#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
668    : binary_function<_Tp, _Tp, _Tp>
669#endif
670{
671_LIBCPP_SUPPRESS_DEPRECATED_POP
672    typedef _Tp __result_type;  // used by valarray
673#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
674    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
675    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
676    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
677#endif
678    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
679    _Tp operator()(const _Tp& __x, const _Tp& __y) const
680        {return __x % __y;}
681};
682
683#if _LIBCPP_STD_VER > 11
684template <>
685struct _LIBCPP_TEMPLATE_VIS modulus<void>
686{
687    template <class _T1, class _T2>
688    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
689    auto operator()(_T1&& __t, _T2&& __u) const
690    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) % _VSTD::forward<_T2>(__u)))
691    -> decltype        (_VSTD::forward<_T1>(__t) % _VSTD::forward<_T2>(__u))
692        { return        _VSTD::forward<_T1>(__t) % _VSTD::forward<_T2>(__u); }
693    typedef void is_transparent;
694};
695#endif
696
697
698_LIBCPP_SUPPRESS_DEPRECATED_PUSH
699#if _LIBCPP_STD_VER > 11
700template <class _Tp = void>
701#else
702template <class _Tp>
703#endif
704struct _LIBCPP_TEMPLATE_VIS negate
705#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
706    : unary_function<_Tp, _Tp>
707#endif
708{
709_LIBCPP_SUPPRESS_DEPRECATED_POP
710    typedef _Tp __result_type;  // used by valarray
711#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
712    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
713    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
714#endif
715    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
716    _Tp operator()(const _Tp& __x) const
717        {return -__x;}
718};
719
720#if _LIBCPP_STD_VER > 11
721template <>
722struct _LIBCPP_TEMPLATE_VIS negate<void>
723{
724    template <class _Tp>
725    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
726    auto operator()(_Tp&& __x) const
727    _NOEXCEPT_(noexcept(- _VSTD::forward<_Tp>(__x)))
728    -> decltype        (- _VSTD::forward<_Tp>(__x))
729        { return        - _VSTD::forward<_Tp>(__x); }
730    typedef void is_transparent;
731};
732#endif
733
734
735_LIBCPP_SUPPRESS_DEPRECATED_PUSH
736#if _LIBCPP_STD_VER > 11
737template <class _Tp = void>
738#else
739template <class _Tp>
740#endif
741struct _LIBCPP_TEMPLATE_VIS equal_to
742#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
743    : binary_function<_Tp, _Tp, bool>
744#endif
745{
746_LIBCPP_SUPPRESS_DEPRECATED_POP
747    typedef bool __result_type;  // used by valarray
748#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
749    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
750    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
751    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
752#endif
753    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
754    bool operator()(const _Tp& __x, const _Tp& __y) const
755        {return __x == __y;}
756};
757
758#if _LIBCPP_STD_VER > 11
759template <>
760struct _LIBCPP_TEMPLATE_VIS equal_to<void>
761{
762    template <class _T1, class _T2>
763    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
764    auto operator()(_T1&& __t, _T2&& __u) const
765    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) == _VSTD::forward<_T2>(__u)))
766    -> decltype        (_VSTD::forward<_T1>(__t) == _VSTD::forward<_T2>(__u))
767        { return        _VSTD::forward<_T1>(__t) == _VSTD::forward<_T2>(__u); }
768    typedef void is_transparent;
769};
770#endif
771
772
773_LIBCPP_SUPPRESS_DEPRECATED_PUSH
774#if _LIBCPP_STD_VER > 11
775template <class _Tp = void>
776#else
777template <class _Tp>
778#endif
779struct _LIBCPP_TEMPLATE_VIS not_equal_to
780#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
781    : binary_function<_Tp, _Tp, bool>
782#endif
783{
784_LIBCPP_SUPPRESS_DEPRECATED_POP
785    typedef bool __result_type;  // used by valarray
786#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
787    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
788    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
789    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
790#endif
791    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
792    bool operator()(const _Tp& __x, const _Tp& __y) const
793        {return __x != __y;}
794};
795
796#if _LIBCPP_STD_VER > 11
797template <>
798struct _LIBCPP_TEMPLATE_VIS not_equal_to<void>
799{
800    template <class _T1, class _T2>
801    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
802    auto operator()(_T1&& __t, _T2&& __u) const
803    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) != _VSTD::forward<_T2>(__u)))
804    -> decltype        (_VSTD::forward<_T1>(__t) != _VSTD::forward<_T2>(__u))
805        { return        _VSTD::forward<_T1>(__t) != _VSTD::forward<_T2>(__u); }
806    typedef void is_transparent;
807};
808#endif
809
810
811_LIBCPP_SUPPRESS_DEPRECATED_PUSH
812#if _LIBCPP_STD_VER > 11
813template <class _Tp = void>
814#else
815template <class _Tp>
816#endif
817struct _LIBCPP_TEMPLATE_VIS greater
818#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
819    : binary_function<_Tp, _Tp, bool>
820#endif
821{
822_LIBCPP_SUPPRESS_DEPRECATED_POP
823    typedef bool __result_type;  // used by valarray
824#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
825    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
826    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
827    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
828#endif
829    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
830    bool operator()(const _Tp& __x, const _Tp& __y) const
831        {return __x > __y;}
832};
833
834#if _LIBCPP_STD_VER > 11
835template <>
836struct _LIBCPP_TEMPLATE_VIS greater<void>
837{
838    template <class _T1, class _T2>
839    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
840    auto operator()(_T1&& __t, _T2&& __u) const
841    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) > _VSTD::forward<_T2>(__u)))
842    -> decltype        (_VSTD::forward<_T1>(__t) > _VSTD::forward<_T2>(__u))
843        { return        _VSTD::forward<_T1>(__t) > _VSTD::forward<_T2>(__u); }
844    typedef void is_transparent;
845};
846#endif
847
848
849// less in <__functional_base>
850
851
852_LIBCPP_SUPPRESS_DEPRECATED_PUSH
853#if _LIBCPP_STD_VER > 11
854template <class _Tp = void>
855#else
856template <class _Tp>
857#endif
858struct _LIBCPP_TEMPLATE_VIS greater_equal
859#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
860    : binary_function<_Tp, _Tp, bool>
861#endif
862{
863_LIBCPP_SUPPRESS_DEPRECATED_POP
864    typedef bool __result_type;  // used by valarray
865#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
866    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
867    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
868    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
869#endif
870    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
871    bool operator()(const _Tp& __x, const _Tp& __y) const
872        {return __x >= __y;}
873};
874
875#if _LIBCPP_STD_VER > 11
876template <>
877struct _LIBCPP_TEMPLATE_VIS greater_equal<void>
878{
879    template <class _T1, class _T2>
880    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
881    auto operator()(_T1&& __t, _T2&& __u) const
882    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) >= _VSTD::forward<_T2>(__u)))
883    -> decltype        (_VSTD::forward<_T1>(__t) >= _VSTD::forward<_T2>(__u))
884        { return        _VSTD::forward<_T1>(__t) >= _VSTD::forward<_T2>(__u); }
885    typedef void is_transparent;
886};
887#endif
888
889
890_LIBCPP_SUPPRESS_DEPRECATED_PUSH
891#if _LIBCPP_STD_VER > 11
892template <class _Tp = void>
893#else
894template <class _Tp>
895#endif
896struct _LIBCPP_TEMPLATE_VIS less_equal
897#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
898    : binary_function<_Tp, _Tp, bool>
899#endif
900{
901_LIBCPP_SUPPRESS_DEPRECATED_POP
902    typedef bool __result_type;  // used by valarray
903#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
904    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
905    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
906    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
907#endif
908    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
909    bool operator()(const _Tp& __x, const _Tp& __y) const
910        {return __x <= __y;}
911};
912
913#if _LIBCPP_STD_VER > 11
914template <>
915struct _LIBCPP_TEMPLATE_VIS less_equal<void>
916{
917    template <class _T1, class _T2>
918    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
919    auto operator()(_T1&& __t, _T2&& __u) const
920    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) <= _VSTD::forward<_T2>(__u)))
921    -> decltype        (_VSTD::forward<_T1>(__t) <= _VSTD::forward<_T2>(__u))
922        { return        _VSTD::forward<_T1>(__t) <= _VSTD::forward<_T2>(__u); }
923    typedef void is_transparent;
924};
925#endif
926
927
928_LIBCPP_SUPPRESS_DEPRECATED_PUSH
929#if _LIBCPP_STD_VER > 11
930template <class _Tp = void>
931#else
932template <class _Tp>
933#endif
934struct _LIBCPP_TEMPLATE_VIS logical_and
935#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
936    : binary_function<_Tp, _Tp, bool>
937#endif
938{
939_LIBCPP_SUPPRESS_DEPRECATED_POP
940    typedef bool __result_type;  // used by valarray
941#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
942    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
943    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
944    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
945#endif
946    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
947    bool operator()(const _Tp& __x, const _Tp& __y) const
948        {return __x && __y;}
949};
950
951#if _LIBCPP_STD_VER > 11
952template <>
953struct _LIBCPP_TEMPLATE_VIS logical_and<void>
954{
955    template <class _T1, class _T2>
956    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
957    auto operator()(_T1&& __t, _T2&& __u) const
958    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) && _VSTD::forward<_T2>(__u)))
959    -> decltype        (_VSTD::forward<_T1>(__t) && _VSTD::forward<_T2>(__u))
960        { return        _VSTD::forward<_T1>(__t) && _VSTD::forward<_T2>(__u); }
961    typedef void is_transparent;
962};
963#endif
964
965
966_LIBCPP_SUPPRESS_DEPRECATED_PUSH
967#if _LIBCPP_STD_VER > 11
968template <class _Tp = void>
969#else
970template <class _Tp>
971#endif
972struct _LIBCPP_TEMPLATE_VIS logical_or
973#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
974    : binary_function<_Tp, _Tp, bool>
975#endif
976{
977_LIBCPP_SUPPRESS_DEPRECATED_POP
978    typedef bool __result_type;  // used by valarray
979#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
980    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
981    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
982    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
983#endif
984    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
985    bool operator()(const _Tp& __x, const _Tp& __y) const
986        {return __x || __y;}
987};
988
989#if _LIBCPP_STD_VER > 11
990template <>
991struct _LIBCPP_TEMPLATE_VIS logical_or<void>
992{
993    template <class _T1, class _T2>
994    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
995    auto operator()(_T1&& __t, _T2&& __u) const
996    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) || _VSTD::forward<_T2>(__u)))
997    -> decltype        (_VSTD::forward<_T1>(__t) || _VSTD::forward<_T2>(__u))
998        { return        _VSTD::forward<_T1>(__t) || _VSTD::forward<_T2>(__u); }
999    typedef void is_transparent;
1000};
1001#endif
1002
1003
1004_LIBCPP_SUPPRESS_DEPRECATED_PUSH
1005#if _LIBCPP_STD_VER > 11
1006template <class _Tp = void>
1007#else
1008template <class _Tp>
1009#endif
1010struct _LIBCPP_TEMPLATE_VIS logical_not
1011#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
1012    : unary_function<_Tp, bool>
1013#endif
1014{
1015_LIBCPP_SUPPRESS_DEPRECATED_POP
1016    typedef bool __result_type;  // used by valarray
1017#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
1018    _LIBCPP_DEPRECATED_IN_CXX17 typedef bool result_type;
1019    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
1020#endif
1021    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1022    bool operator()(const _Tp& __x) const
1023        {return !__x;}
1024};
1025
1026#if _LIBCPP_STD_VER > 11
1027template <>
1028struct _LIBCPP_TEMPLATE_VIS logical_not<void>
1029{
1030    template <class _Tp>
1031    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1032    auto operator()(_Tp&& __x) const
1033    _NOEXCEPT_(noexcept(!_VSTD::forward<_Tp>(__x)))
1034    -> decltype        (!_VSTD::forward<_Tp>(__x))
1035        { return        !_VSTD::forward<_Tp>(__x); }
1036    typedef void is_transparent;
1037};
1038#endif
1039
1040
1041_LIBCPP_SUPPRESS_DEPRECATED_PUSH
1042#if _LIBCPP_STD_VER > 11
1043template <class _Tp = void>
1044#else
1045template <class _Tp>
1046#endif
1047struct _LIBCPP_TEMPLATE_VIS bit_and
1048#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
1049    : binary_function<_Tp, _Tp, _Tp>
1050#endif
1051{
1052_LIBCPP_SUPPRESS_DEPRECATED_POP
1053    typedef _Tp __result_type;  // used by valarray
1054#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
1055    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
1056    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
1057    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
1058#endif
1059    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1060    _Tp operator()(const _Tp& __x, const _Tp& __y) const
1061        {return __x & __y;}
1062};
1063
1064#if _LIBCPP_STD_VER > 11
1065template <>
1066struct _LIBCPP_TEMPLATE_VIS bit_and<void>
1067{
1068    template <class _T1, class _T2>
1069    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1070    auto operator()(_T1&& __t, _T2&& __u) const
1071    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) & _VSTD::forward<_T2>(__u)))
1072    -> decltype        (_VSTD::forward<_T1>(__t) & _VSTD::forward<_T2>(__u))
1073        { return        _VSTD::forward<_T1>(__t) & _VSTD::forward<_T2>(__u); }
1074    typedef void is_transparent;
1075};
1076#endif
1077
1078
1079_LIBCPP_SUPPRESS_DEPRECATED_PUSH
1080#if _LIBCPP_STD_VER > 11
1081template <class _Tp = void>
1082#else
1083template <class _Tp>
1084#endif
1085struct _LIBCPP_TEMPLATE_VIS bit_or
1086#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
1087    : binary_function<_Tp, _Tp, _Tp>
1088#endif
1089{
1090_LIBCPP_SUPPRESS_DEPRECATED_POP
1091    typedef _Tp __result_type;  // used by valarray
1092#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
1093    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
1094    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
1095    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
1096#endif
1097    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1098    _Tp operator()(const _Tp& __x, const _Tp& __y) const
1099        {return __x | __y;}
1100};
1101
1102#if _LIBCPP_STD_VER > 11
1103template <>
1104struct _LIBCPP_TEMPLATE_VIS bit_or<void>
1105{
1106    template <class _T1, class _T2>
1107    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1108    auto operator()(_T1&& __t, _T2&& __u) const
1109    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) | _VSTD::forward<_T2>(__u)))
1110    -> decltype        (_VSTD::forward<_T1>(__t) | _VSTD::forward<_T2>(__u))
1111        { return        _VSTD::forward<_T1>(__t) | _VSTD::forward<_T2>(__u); }
1112    typedef void is_transparent;
1113};
1114#endif
1115
1116
1117_LIBCPP_SUPPRESS_DEPRECATED_PUSH
1118#if _LIBCPP_STD_VER > 11
1119template <class _Tp = void>
1120#else
1121template <class _Tp>
1122#endif
1123struct _LIBCPP_TEMPLATE_VIS bit_xor
1124#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
1125    : binary_function<_Tp, _Tp, _Tp>
1126#endif
1127{
1128_LIBCPP_SUPPRESS_DEPRECATED_POP
1129    typedef _Tp __result_type;  // used by valarray
1130#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
1131    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
1132    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp first_argument_type;
1133    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp second_argument_type;
1134#endif
1135    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1136    _Tp operator()(const _Tp& __x, const _Tp& __y) const
1137        {return __x ^ __y;}
1138};
1139
1140#if _LIBCPP_STD_VER > 11
1141template <>
1142struct _LIBCPP_TEMPLATE_VIS bit_xor<void>
1143{
1144    template <class _T1, class _T2>
1145    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1146    auto operator()(_T1&& __t, _T2&& __u) const
1147    _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) ^ _VSTD::forward<_T2>(__u)))
1148    -> decltype        (_VSTD::forward<_T1>(__t) ^ _VSTD::forward<_T2>(__u))
1149        { return        _VSTD::forward<_T1>(__t) ^ _VSTD::forward<_T2>(__u); }
1150    typedef void is_transparent;
1151};
1152#endif
1153
1154
1155#if _LIBCPP_STD_VER > 11
1156_LIBCPP_SUPPRESS_DEPRECATED_PUSH
1157template <class _Tp = void>
1158struct _LIBCPP_TEMPLATE_VIS bit_not
1159#if !defined(_LIBCPP_ABI_NO_BINDER_BASES)
1160    : unary_function<_Tp, _Tp>
1161#endif
1162{
1163_LIBCPP_SUPPRESS_DEPRECATED_POP
1164#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_BINDER_TYPEDEFS)
1165    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp result_type;
1166    _LIBCPP_DEPRECATED_IN_CXX17 typedef _Tp argument_type;
1167#endif
1168    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1169    _Tp operator()(const _Tp& __x) const
1170        {return ~__x;}
1171};
1172
1173template <>
1174struct _LIBCPP_TEMPLATE_VIS bit_not<void>
1175{
1176    template <class _Tp>
1177    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1178    auto operator()(_Tp&& __x) const
1179    _NOEXCEPT_(noexcept(~_VSTD::forward<_Tp>(__x)))
1180    -> decltype        (~_VSTD::forward<_Tp>(__x))
1181        { return        ~_VSTD::forward<_Tp>(__x); }
1182    typedef void is_transparent;
1183};
1184#endif
1185
1186#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_NEGATORS)
1187template <class _Predicate>
1188class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX17 unary_negate
1189    : public unary_function<typename _Predicate::argument_type, bool>
1190{
1191    _Predicate __pred_;
1192public:
1193    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1194    explicit unary_negate(const _Predicate& __pred)
1195        : __pred_(__pred) {}
1196    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1197    bool operator()(const typename _Predicate::argument_type& __x) const
1198        {return !__pred_(__x);}
1199};
1200
1201template <class _Predicate>
1202_LIBCPP_DEPRECATED_IN_CXX17 inline _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1203unary_negate<_Predicate>
1204not1(const _Predicate& __pred) {return unary_negate<_Predicate>(__pred);}
1205
1206template <class _Predicate>
1207class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX17 binary_negate
1208    : public binary_function<typename _Predicate::first_argument_type,
1209                             typename _Predicate::second_argument_type,
1210                             bool>
1211{
1212    _Predicate __pred_;
1213public:
1214    _LIBCPP_INLINE_VISIBILITY explicit _LIBCPP_CONSTEXPR_AFTER_CXX11
1215    binary_negate(const _Predicate& __pred) : __pred_(__pred) {}
1216
1217    _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1218    bool operator()(const typename _Predicate::first_argument_type& __x,
1219                    const typename _Predicate::second_argument_type& __y) const
1220        {return !__pred_(__x, __y);}
1221};
1222
1223template <class _Predicate>
1224_LIBCPP_DEPRECATED_IN_CXX17 inline _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1225binary_negate<_Predicate>
1226not2(const _Predicate& __pred) {return binary_negate<_Predicate>(__pred);}
1227#endif // _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_NEGATORS)
1228
1229#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_BINDERS)
1230template <class __Operation>
1231class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 binder1st
1232    : public unary_function<typename __Operation::second_argument_type,
1233                            typename __Operation::result_type>
1234{
1235protected:
1236    __Operation                               op;
1237    typename __Operation::first_argument_type value;
1238public:
1239    _LIBCPP_INLINE_VISIBILITY binder1st(const __Operation& __x,
1240                               const typename __Operation::first_argument_type __y)
1241        : op(__x), value(__y) {}
1242    _LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator()
1243        (typename __Operation::second_argument_type& __x) const
1244            {return op(value, __x);}
1245    _LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator()
1246        (const typename __Operation::second_argument_type& __x) const
1247            {return op(value, __x);}
1248};
1249
1250template <class __Operation, class _Tp>
1251_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1252binder1st<__Operation>
1253bind1st(const __Operation& __op, const _Tp& __x)
1254    {return binder1st<__Operation>(__op, __x);}
1255
1256template <class __Operation>
1257class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 binder2nd
1258    : public unary_function<typename __Operation::first_argument_type,
1259                            typename __Operation::result_type>
1260{
1261protected:
1262    __Operation                                op;
1263    typename __Operation::second_argument_type value;
1264public:
1265    _LIBCPP_INLINE_VISIBILITY
1266    binder2nd(const __Operation& __x, const typename __Operation::second_argument_type __y)
1267        : op(__x), value(__y) {}
1268    _LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator()
1269        (      typename __Operation::first_argument_type& __x) const
1270            {return op(__x, value);}
1271    _LIBCPP_INLINE_VISIBILITY typename __Operation::result_type operator()
1272        (const typename __Operation::first_argument_type& __x) const
1273            {return op(__x, value);}
1274};
1275
1276template <class __Operation, class _Tp>
1277_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1278binder2nd<__Operation>
1279bind2nd(const __Operation& __op, const _Tp& __x)
1280    {return binder2nd<__Operation>(__op, __x);}
1281
1282template <class _Arg, class _Result>
1283class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 pointer_to_unary_function
1284    : public unary_function<_Arg, _Result>
1285{
1286    _Result (*__f_)(_Arg);
1287public:
1288    _LIBCPP_INLINE_VISIBILITY explicit pointer_to_unary_function(_Result (*__f)(_Arg))
1289        : __f_(__f) {}
1290    _LIBCPP_INLINE_VISIBILITY _Result operator()(_Arg __x) const
1291        {return __f_(__x);}
1292};
1293
1294template <class _Arg, class _Result>
1295_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1296pointer_to_unary_function<_Arg,_Result>
1297ptr_fun(_Result (*__f)(_Arg))
1298    {return pointer_to_unary_function<_Arg,_Result>(__f);}
1299
1300template <class _Arg1, class _Arg2, class _Result>
1301class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 pointer_to_binary_function
1302    : public binary_function<_Arg1, _Arg2, _Result>
1303{
1304    _Result (*__f_)(_Arg1, _Arg2);
1305public:
1306    _LIBCPP_INLINE_VISIBILITY explicit pointer_to_binary_function(_Result (*__f)(_Arg1, _Arg2))
1307        : __f_(__f) {}
1308    _LIBCPP_INLINE_VISIBILITY _Result operator()(_Arg1 __x, _Arg2 __y) const
1309        {return __f_(__x, __y);}
1310};
1311
1312template <class _Arg1, class _Arg2, class _Result>
1313_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1314pointer_to_binary_function<_Arg1,_Arg2,_Result>
1315ptr_fun(_Result (*__f)(_Arg1,_Arg2))
1316    {return pointer_to_binary_function<_Arg1,_Arg2,_Result>(__f);}
1317
1318template<class _Sp, class _Tp>
1319class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 mem_fun_t
1320    : public unary_function<_Tp*, _Sp>
1321{
1322    _Sp (_Tp::*__p_)();
1323public:
1324    _LIBCPP_INLINE_VISIBILITY explicit mem_fun_t(_Sp (_Tp::*__p)())
1325        : __p_(__p) {}
1326    _LIBCPP_INLINE_VISIBILITY _Sp operator()(_Tp* __p) const
1327        {return (__p->*__p_)();}
1328};
1329
1330template<class _Sp, class _Tp, class _Ap>
1331class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 mem_fun1_t
1332    : public binary_function<_Tp*, _Ap, _Sp>
1333{
1334    _Sp (_Tp::*__p_)(_Ap);
1335public:
1336    _LIBCPP_INLINE_VISIBILITY explicit mem_fun1_t(_Sp (_Tp::*__p)(_Ap))
1337        : __p_(__p) {}
1338    _LIBCPP_INLINE_VISIBILITY _Sp operator()(_Tp* __p, _Ap __x) const
1339        {return (__p->*__p_)(__x);}
1340};
1341
1342template<class _Sp, class _Tp>
1343_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1344mem_fun_t<_Sp,_Tp>
1345mem_fun(_Sp (_Tp::*__f)())
1346    {return mem_fun_t<_Sp,_Tp>(__f);}
1347
1348template<class _Sp, class _Tp, class _Ap>
1349_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1350mem_fun1_t<_Sp,_Tp,_Ap>
1351mem_fun(_Sp (_Tp::*__f)(_Ap))
1352    {return mem_fun1_t<_Sp,_Tp,_Ap>(__f);}
1353
1354template<class _Sp, class _Tp>
1355class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 mem_fun_ref_t
1356    : public unary_function<_Tp, _Sp>
1357{
1358    _Sp (_Tp::*__p_)();
1359public:
1360    _LIBCPP_INLINE_VISIBILITY explicit mem_fun_ref_t(_Sp (_Tp::*__p)())
1361        : __p_(__p) {}
1362    _LIBCPP_INLINE_VISIBILITY _Sp operator()(_Tp& __p) const
1363        {return (__p.*__p_)();}
1364};
1365
1366template<class _Sp, class _Tp, class _Ap>
1367class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 mem_fun1_ref_t
1368    : public binary_function<_Tp, _Ap, _Sp>
1369{
1370    _Sp (_Tp::*__p_)(_Ap);
1371public:
1372    _LIBCPP_INLINE_VISIBILITY explicit mem_fun1_ref_t(_Sp (_Tp::*__p)(_Ap))
1373        : __p_(__p) {}
1374    _LIBCPP_INLINE_VISIBILITY _Sp operator()(_Tp& __p, _Ap __x) const
1375        {return (__p.*__p_)(__x);}
1376};
1377
1378template<class _Sp, class _Tp>
1379_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1380mem_fun_ref_t<_Sp,_Tp>
1381mem_fun_ref(_Sp (_Tp::*__f)())
1382    {return mem_fun_ref_t<_Sp,_Tp>(__f);}
1383
1384template<class _Sp, class _Tp, class _Ap>
1385_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1386mem_fun1_ref_t<_Sp,_Tp,_Ap>
1387mem_fun_ref(_Sp (_Tp::*__f)(_Ap))
1388    {return mem_fun1_ref_t<_Sp,_Tp,_Ap>(__f);}
1389
1390template <class _Sp, class _Tp>
1391class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 const_mem_fun_t
1392    : public unary_function<const _Tp*, _Sp>
1393{
1394    _Sp (_Tp::*__p_)() const;
1395public:
1396    _LIBCPP_INLINE_VISIBILITY explicit const_mem_fun_t(_Sp (_Tp::*__p)() const)
1397        : __p_(__p) {}
1398    _LIBCPP_INLINE_VISIBILITY _Sp operator()(const _Tp* __p) const
1399        {return (__p->*__p_)();}
1400};
1401
1402template <class _Sp, class _Tp, class _Ap>
1403class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 const_mem_fun1_t
1404    : public binary_function<const _Tp*, _Ap, _Sp>
1405{
1406    _Sp (_Tp::*__p_)(_Ap) const;
1407public:
1408    _LIBCPP_INLINE_VISIBILITY explicit const_mem_fun1_t(_Sp (_Tp::*__p)(_Ap) const)
1409        : __p_(__p) {}
1410    _LIBCPP_INLINE_VISIBILITY _Sp operator()(const _Tp* __p, _Ap __x) const
1411        {return (__p->*__p_)(__x);}
1412};
1413
1414template <class _Sp, class _Tp>
1415_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1416const_mem_fun_t<_Sp,_Tp>
1417mem_fun(_Sp (_Tp::*__f)() const)
1418    {return const_mem_fun_t<_Sp,_Tp>(__f);}
1419
1420template <class _Sp, class _Tp, class _Ap>
1421_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1422const_mem_fun1_t<_Sp,_Tp,_Ap>
1423mem_fun(_Sp (_Tp::*__f)(_Ap) const)
1424    {return const_mem_fun1_t<_Sp,_Tp,_Ap>(__f);}
1425
1426template <class _Sp, class _Tp>
1427class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 const_mem_fun_ref_t
1428    : public unary_function<_Tp, _Sp>
1429{
1430    _Sp (_Tp::*__p_)() const;
1431public:
1432    _LIBCPP_INLINE_VISIBILITY explicit const_mem_fun_ref_t(_Sp (_Tp::*__p)() const)
1433        : __p_(__p) {}
1434    _LIBCPP_INLINE_VISIBILITY _Sp operator()(const _Tp& __p) const
1435        {return (__p.*__p_)();}
1436};
1437
1438template <class _Sp, class _Tp, class _Ap>
1439class _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX11 const_mem_fun1_ref_t
1440    : public binary_function<_Tp, _Ap, _Sp>
1441{
1442    _Sp (_Tp::*__p_)(_Ap) const;
1443public:
1444    _LIBCPP_INLINE_VISIBILITY explicit const_mem_fun1_ref_t(_Sp (_Tp::*__p)(_Ap) const)
1445        : __p_(__p) {}
1446    _LIBCPP_INLINE_VISIBILITY _Sp operator()(const _Tp& __p, _Ap __x) const
1447        {return (__p.*__p_)(__x);}
1448};
1449
1450template <class _Sp, class _Tp>
1451_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1452const_mem_fun_ref_t<_Sp,_Tp>
1453mem_fun_ref(_Sp (_Tp::*__f)() const)
1454    {return const_mem_fun_ref_t<_Sp,_Tp>(__f);}
1455
1456template <class _Sp, class _Tp, class _Ap>
1457_LIBCPP_DEPRECATED_IN_CXX11 inline _LIBCPP_INLINE_VISIBILITY
1458const_mem_fun1_ref_t<_Sp,_Tp,_Ap>
1459mem_fun_ref(_Sp (_Tp::*__f)(_Ap) const)
1460    {return const_mem_fun1_ref_t<_Sp,_Tp,_Ap>(__f);}
1461#endif
1462
1463////////////////////////////////////////////////////////////////////////////////
1464//                                MEMFUN
1465//==============================================================================
1466
1467template <class _Tp>
1468class __mem_fn
1469#if _LIBCPP_STD_VER <= 17 || !defined(_LIBCPP_ABI_NO_BINDER_BASES)
1470    : public __weak_result_type<_Tp>
1471#endif
1472{
1473public:
1474    // types
1475    typedef _Tp type;
1476private:
1477    type __f_;
1478
1479public:
1480    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1481    __mem_fn(type __f) _NOEXCEPT : __f_(__f) {}
1482
1483#ifndef _LIBCPP_CXX03_LANG
1484    // invoke
1485    template <class... _ArgTypes>
1486    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1487    typename __invoke_return<type, _ArgTypes...>::type
1488    operator() (_ArgTypes&&... __args) const {
1489        return _VSTD::__invoke(__f_, _VSTD::forward<_ArgTypes>(__args)...);
1490    }
1491#else
1492
1493    template <class _A0>
1494    _LIBCPP_INLINE_VISIBILITY
1495    typename __invoke_return0<type, _A0>::type
1496    operator() (_A0& __a0) const {
1497        return _VSTD::__invoke(__f_, __a0);
1498    }
1499
1500    template <class _A0>
1501    _LIBCPP_INLINE_VISIBILITY
1502    typename __invoke_return0<type, _A0 const>::type
1503    operator() (_A0 const& __a0) const {
1504        return _VSTD::__invoke(__f_, __a0);
1505    }
1506
1507    template <class _A0, class _A1>
1508    _LIBCPP_INLINE_VISIBILITY
1509    typename __invoke_return1<type, _A0, _A1>::type
1510    operator() (_A0& __a0, _A1& __a1) const {
1511        return _VSTD::__invoke(__f_, __a0, __a1);
1512    }
1513
1514    template <class _A0, class _A1>
1515    _LIBCPP_INLINE_VISIBILITY
1516    typename __invoke_return1<type, _A0 const, _A1>::type
1517    operator() (_A0 const& __a0, _A1& __a1) const {
1518        return _VSTD::__invoke(__f_, __a0, __a1);
1519    }
1520
1521    template <class _A0, class _A1>
1522    _LIBCPP_INLINE_VISIBILITY
1523    typename __invoke_return1<type, _A0, _A1 const>::type
1524    operator() (_A0& __a0, _A1 const& __a1) const {
1525        return _VSTD::__invoke(__f_, __a0, __a1);
1526    }
1527
1528    template <class _A0, class _A1>
1529    _LIBCPP_INLINE_VISIBILITY
1530    typename __invoke_return1<type, _A0 const, _A1 const>::type
1531    operator() (_A0 const& __a0, _A1 const& __a1) const {
1532        return _VSTD::__invoke(__f_, __a0, __a1);
1533    }
1534
1535    template <class _A0, class _A1, class _A2>
1536    _LIBCPP_INLINE_VISIBILITY
1537    typename __invoke_return2<type, _A0, _A1, _A2>::type
1538    operator() (_A0& __a0, _A1& __a1, _A2& __a2) const {
1539        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1540    }
1541
1542    template <class _A0, class _A1, class _A2>
1543    _LIBCPP_INLINE_VISIBILITY
1544    typename __invoke_return2<type, _A0 const, _A1, _A2>::type
1545    operator() (_A0 const& __a0, _A1& __a1, _A2& __a2) const {
1546        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1547    }
1548
1549    template <class _A0, class _A1, class _A2>
1550    _LIBCPP_INLINE_VISIBILITY
1551    typename __invoke_return2<type, _A0, _A1 const, _A2>::type
1552    operator() (_A0& __a0, _A1 const& __a1, _A2& __a2) const {
1553        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1554    }
1555
1556    template <class _A0, class _A1, class _A2>
1557    _LIBCPP_INLINE_VISIBILITY
1558    typename __invoke_return2<type, _A0, _A1, _A2 const>::type
1559    operator() (_A0& __a0, _A1& __a1, _A2 const& __a2) const {
1560        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1561    }
1562
1563    template <class _A0, class _A1, class _A2>
1564    _LIBCPP_INLINE_VISIBILITY
1565    typename __invoke_return2<type, _A0 const, _A1 const, _A2>::type
1566    operator() (_A0 const& __a0, _A1 const& __a1, _A2& __a2) const {
1567        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1568    }
1569
1570    template <class _A0, class _A1, class _A2>
1571    _LIBCPP_INLINE_VISIBILITY
1572    typename __invoke_return2<type, _A0 const, _A1, _A2 const>::type
1573    operator() (_A0 const& __a0, _A1& __a1, _A2 const& __a2) const {
1574        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1575    }
1576
1577    template <class _A0, class _A1, class _A2>
1578    _LIBCPP_INLINE_VISIBILITY
1579    typename __invoke_return2<type, _A0, _A1 const, _A2 const>::type
1580    operator() (_A0& __a0, _A1 const& __a1, _A2 const& __a2) const {
1581        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1582    }
1583
1584    template <class _A0, class _A1, class _A2>
1585    _LIBCPP_INLINE_VISIBILITY
1586    typename __invoke_return2<type, _A0 const, _A1 const, _A2 const>::type
1587    operator() (_A0 const& __a0, _A1 const& __a1, _A2 const& __a2) const {
1588        return _VSTD::__invoke(__f_, __a0, __a1, __a2);
1589    }
1590#endif
1591};
1592
1593template<class _Rp, class _Tp>
1594inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
1595__mem_fn<_Rp _Tp::*>
1596mem_fn(_Rp _Tp::* __pm) _NOEXCEPT
1597{
1598    return __mem_fn<_Rp _Tp::*>(__pm);
1599}
1600
1601////////////////////////////////////////////////////////////////////////////////
1602//                                FUNCTION
1603//==============================================================================
1604
1605// bad_function_call
1606
1607class _LIBCPP_EXCEPTION_ABI bad_function_call
1608    : public exception
1609{
1610#ifdef _LIBCPP_ABI_BAD_FUNCTION_CALL_KEY_FUNCTION
1611public:
1612    virtual ~bad_function_call() _NOEXCEPT;
1613
1614    virtual const char* what() const _NOEXCEPT;
1615#endif
1616};
1617
1618_LIBCPP_NORETURN inline _LIBCPP_INLINE_VISIBILITY
1619void __throw_bad_function_call()
1620{
1621#ifndef _LIBCPP_NO_EXCEPTIONS
1622    throw bad_function_call();
1623#else
1624    _VSTD::abort();
1625#endif
1626}
1627
1628#if defined(_LIBCPP_CXX03_LANG) && !defined(_LIBCPP_DISABLE_DEPRECATION_WARNINGS) && __has_attribute(deprecated)
1629#   define _LIBCPP_DEPRECATED_CXX03_FUNCTION \
1630        __attribute__((deprecated("Using std::function in C++03 is not supported anymore. Please upgrade to C++11 or later, or use a different type")))
1631#else
1632#   define _LIBCPP_DEPRECATED_CXX03_FUNCTION /* nothing */
1633#endif
1634
1635template<class _Fp> class _LIBCPP_DEPRECATED_CXX03_FUNCTION _LIBCPP_TEMPLATE_VIS function; // undefined
1636
1637namespace __function
1638{
1639
1640template<class _Rp>
1641struct __maybe_derive_from_unary_function
1642{
1643};
1644
1645template<class _Rp, class _A1>
1646struct __maybe_derive_from_unary_function<_Rp(_A1)>
1647    : public unary_function<_A1, _Rp>
1648{
1649};
1650
1651template<class _Rp>
1652struct __maybe_derive_from_binary_function
1653{
1654};
1655
1656template<class _Rp, class _A1, class _A2>
1657struct __maybe_derive_from_binary_function<_Rp(_A1, _A2)>
1658    : public binary_function<_A1, _A2, _Rp>
1659{
1660};
1661
1662template <class _Fp>
1663_LIBCPP_INLINE_VISIBILITY
1664bool __not_null(_Fp const&) { return true; }
1665
1666template <class _Fp>
1667_LIBCPP_INLINE_VISIBILITY
1668bool __not_null(_Fp* __ptr) { return __ptr; }
1669
1670template <class _Ret, class _Class>
1671_LIBCPP_INLINE_VISIBILITY
1672bool __not_null(_Ret _Class::*__ptr) { return __ptr; }
1673
1674template <class _Fp>
1675_LIBCPP_INLINE_VISIBILITY
1676bool __not_null(function<_Fp> const& __f) { return !!__f; }
1677
1678#ifdef _LIBCPP_HAS_EXTENSION_BLOCKS
1679template <class _Rp, class ..._Args>
1680_LIBCPP_INLINE_VISIBILITY
1681bool __not_null(_Rp (^__p)(_Args...)) { return __p; }
1682#endif
1683
1684} // namespace __function
1685
1686#ifndef _LIBCPP_CXX03_LANG
1687
1688namespace __function {
1689
1690// __alloc_func holds a functor and an allocator.
1691
1692template <class _Fp, class _Ap, class _FB> class __alloc_func;
1693template <class _Fp, class _FB>
1694class __default_alloc_func;
1695
1696template <class _Fp, class _Ap, class _Rp, class... _ArgTypes>
1697class __alloc_func<_Fp, _Ap, _Rp(_ArgTypes...)>
1698{
1699    __compressed_pair<_Fp, _Ap> __f_;
1700
1701  public:
1702    typedef _LIBCPP_NODEBUG_TYPE _Fp _Target;
1703    typedef _LIBCPP_NODEBUG_TYPE _Ap _Alloc;
1704
1705    _LIBCPP_INLINE_VISIBILITY
1706    const _Target& __target() const { return __f_.first(); }
1707
1708    // WIN32 APIs may define __allocator, so use __get_allocator instead.
1709    _LIBCPP_INLINE_VISIBILITY
1710    const _Alloc& __get_allocator() const { return __f_.second(); }
1711
1712    _LIBCPP_INLINE_VISIBILITY
1713    explicit __alloc_func(_Target&& __f)
1714        : __f_(piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__f)),
1715               _VSTD::forward_as_tuple())
1716    {
1717    }
1718
1719    _LIBCPP_INLINE_VISIBILITY
1720    explicit __alloc_func(const _Target& __f, const _Alloc& __a)
1721        : __f_(piecewise_construct, _VSTD::forward_as_tuple(__f),
1722               _VSTD::forward_as_tuple(__a))
1723    {
1724    }
1725
1726    _LIBCPP_INLINE_VISIBILITY
1727    explicit __alloc_func(const _Target& __f, _Alloc&& __a)
1728        : __f_(piecewise_construct, _VSTD::forward_as_tuple(__f),
1729               _VSTD::forward_as_tuple(_VSTD::move(__a)))
1730    {
1731    }
1732
1733    _LIBCPP_INLINE_VISIBILITY
1734    explicit __alloc_func(_Target&& __f, _Alloc&& __a)
1735        : __f_(piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__f)),
1736               _VSTD::forward_as_tuple(_VSTD::move(__a)))
1737    {
1738    }
1739
1740    _LIBCPP_INLINE_VISIBILITY
1741    _Rp operator()(_ArgTypes&&... __arg)
1742    {
1743        typedef __invoke_void_return_wrapper<_Rp> _Invoker;
1744        return _Invoker::__call(__f_.first(),
1745                                _VSTD::forward<_ArgTypes>(__arg)...);
1746    }
1747
1748    _LIBCPP_INLINE_VISIBILITY
1749    __alloc_func* __clone() const
1750    {
1751        typedef allocator_traits<_Alloc> __alloc_traits;
1752        typedef
1753            typename __rebind_alloc_helper<__alloc_traits, __alloc_func>::type
1754                _AA;
1755        _AA __a(__f_.second());
1756        typedef __allocator_destructor<_AA> _Dp;
1757        unique_ptr<__alloc_func, _Dp> __hold(__a.allocate(1), _Dp(__a, 1));
1758        ::new ((void*)__hold.get()) __alloc_func(__f_.first(), _Alloc(__a));
1759        return __hold.release();
1760    }
1761
1762    _LIBCPP_INLINE_VISIBILITY
1763    void destroy() _NOEXCEPT { __f_.~__compressed_pair<_Target, _Alloc>(); }
1764
1765    static void __destroy_and_delete(__alloc_func* __f) {
1766      typedef allocator_traits<_Alloc> __alloc_traits;
1767      typedef typename __rebind_alloc_helper<__alloc_traits, __alloc_func>::type
1768          _FunAlloc;
1769      _FunAlloc __a(__f->__get_allocator());
1770      __f->destroy();
1771      __a.deallocate(__f, 1);
1772    }
1773};
1774
1775template <class _Fp, class _Rp, class... _ArgTypes>
1776class __default_alloc_func<_Fp, _Rp(_ArgTypes...)> {
1777  _Fp __f_;
1778
1779public:
1780  typedef _LIBCPP_NODEBUG_TYPE _Fp _Target;
1781
1782  _LIBCPP_INLINE_VISIBILITY
1783  const _Target& __target() const { return __f_; }
1784
1785  _LIBCPP_INLINE_VISIBILITY
1786  explicit __default_alloc_func(_Target&& __f) : __f_(_VSTD::move(__f)) {}
1787
1788  _LIBCPP_INLINE_VISIBILITY
1789  explicit __default_alloc_func(const _Target& __f) : __f_(__f) {}
1790
1791  _LIBCPP_INLINE_VISIBILITY
1792  _Rp operator()(_ArgTypes&&... __arg) {
1793    typedef __invoke_void_return_wrapper<_Rp> _Invoker;
1794    return _Invoker::__call(__f_, _VSTD::forward<_ArgTypes>(__arg)...);
1795  }
1796
1797  _LIBCPP_INLINE_VISIBILITY
1798  __default_alloc_func* __clone() const {
1799      __builtin_new_allocator::__holder_t __hold =
1800        __builtin_new_allocator::__allocate_type<__default_alloc_func>(1);
1801    __default_alloc_func* __res =
1802        ::new ((void*)__hold.get()) __default_alloc_func(__f_);
1803    (void)__hold.release();
1804    return __res;
1805  }
1806
1807  _LIBCPP_INLINE_VISIBILITY
1808  void destroy() _NOEXCEPT { __f_.~_Target(); }
1809
1810  static void __destroy_and_delete(__default_alloc_func* __f) {
1811    __f->destroy();
1812      __builtin_new_allocator::__deallocate_type<__default_alloc_func>(__f, 1);
1813  }
1814};
1815
1816// __base provides an abstract interface for copyable functors.
1817
1818template<class _Fp> class _LIBCPP_TEMPLATE_VIS __base;
1819
1820template<class _Rp, class ..._ArgTypes>
1821class __base<_Rp(_ArgTypes...)>
1822{
1823    __base(const __base&);
1824    __base& operator=(const __base&);
1825public:
1826    _LIBCPP_INLINE_VISIBILITY __base() {}
1827    _LIBCPP_INLINE_VISIBILITY virtual ~__base() {}
1828    virtual __base* __clone() const = 0;
1829    virtual void __clone(__base*) const = 0;
1830    virtual void destroy() _NOEXCEPT = 0;
1831    virtual void destroy_deallocate() _NOEXCEPT = 0;
1832    virtual _Rp operator()(_ArgTypes&& ...) = 0;
1833#ifndef _LIBCPP_NO_RTTI
1834    virtual const void* target(const type_info&) const _NOEXCEPT = 0;
1835    virtual const std::type_info& target_type() const _NOEXCEPT = 0;
1836#endif // _LIBCPP_NO_RTTI
1837};
1838
1839// __func implements __base for a given functor type.
1840
1841template<class _FD, class _Alloc, class _FB> class __func;
1842
1843template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1844class __func<_Fp, _Alloc, _Rp(_ArgTypes...)>
1845    : public  __base<_Rp(_ArgTypes...)>
1846{
1847    __alloc_func<_Fp, _Alloc, _Rp(_ArgTypes...)> __f_;
1848public:
1849    _LIBCPP_INLINE_VISIBILITY
1850    explicit __func(_Fp&& __f)
1851        : __f_(_VSTD::move(__f)) {}
1852
1853    _LIBCPP_INLINE_VISIBILITY
1854    explicit __func(const _Fp& __f, const _Alloc& __a)
1855        : __f_(__f, __a) {}
1856
1857    _LIBCPP_INLINE_VISIBILITY
1858    explicit __func(const _Fp& __f, _Alloc&& __a)
1859        : __f_(__f, _VSTD::move(__a)) {}
1860
1861    _LIBCPP_INLINE_VISIBILITY
1862    explicit __func(_Fp&& __f, _Alloc&& __a)
1863        : __f_(_VSTD::move(__f), _VSTD::move(__a)) {}
1864
1865    virtual __base<_Rp(_ArgTypes...)>* __clone() const;
1866    virtual void __clone(__base<_Rp(_ArgTypes...)>*) const;
1867    virtual void destroy() _NOEXCEPT;
1868    virtual void destroy_deallocate() _NOEXCEPT;
1869    virtual _Rp operator()(_ArgTypes&&... __arg);
1870#ifndef _LIBCPP_NO_RTTI
1871    virtual const void* target(const type_info&) const _NOEXCEPT;
1872    virtual const std::type_info& target_type() const _NOEXCEPT;
1873#endif // _LIBCPP_NO_RTTI
1874};
1875
1876template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1877__base<_Rp(_ArgTypes...)>*
1878__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::__clone() const
1879{
1880    typedef allocator_traits<_Alloc> __alloc_traits;
1881    typedef typename __rebind_alloc_helper<__alloc_traits, __func>::type _Ap;
1882    _Ap __a(__f_.__get_allocator());
1883    typedef __allocator_destructor<_Ap> _Dp;
1884    unique_ptr<__func, _Dp> __hold(__a.allocate(1), _Dp(__a, 1));
1885    ::new ((void*)__hold.get()) __func(__f_.__target(), _Alloc(__a));
1886    return __hold.release();
1887}
1888
1889template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1890void
1891__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::__clone(__base<_Rp(_ArgTypes...)>* __p) const
1892{
1893    ::new ((void*)__p) __func(__f_.__target(), __f_.__get_allocator());
1894}
1895
1896template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1897void
1898__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::destroy() _NOEXCEPT
1899{
1900    __f_.destroy();
1901}
1902
1903template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1904void
1905__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::destroy_deallocate() _NOEXCEPT
1906{
1907    typedef allocator_traits<_Alloc> __alloc_traits;
1908    typedef typename __rebind_alloc_helper<__alloc_traits, __func>::type _Ap;
1909    _Ap __a(__f_.__get_allocator());
1910    __f_.destroy();
1911    __a.deallocate(this, 1);
1912}
1913
1914template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1915_Rp
1916__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::operator()(_ArgTypes&& ... __arg)
1917{
1918    return __f_(_VSTD::forward<_ArgTypes>(__arg)...);
1919}
1920
1921#ifndef _LIBCPP_NO_RTTI
1922
1923template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1924const void*
1925__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::target(const type_info& __ti) const _NOEXCEPT
1926{
1927    if (__ti == typeid(_Fp))
1928        return &__f_.__target();
1929    return nullptr;
1930}
1931
1932template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
1933const std::type_info&
1934__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::target_type() const _NOEXCEPT
1935{
1936    return typeid(_Fp);
1937}
1938
1939#endif // _LIBCPP_NO_RTTI
1940
1941// __value_func creates a value-type from a __func.
1942
1943template <class _Fp> class __value_func;
1944
1945template <class _Rp, class... _ArgTypes> class __value_func<_Rp(_ArgTypes...)>
1946{
1947    typename aligned_storage<3 * sizeof(void*)>::type __buf_;
1948
1949    typedef __base<_Rp(_ArgTypes...)> __func;
1950    __func* __f_;
1951
1952    _LIBCPP_NO_CFI static __func* __as_base(void* p)
1953    {
1954        return reinterpret_cast<__func*>(p);
1955    }
1956
1957  public:
1958    _LIBCPP_INLINE_VISIBILITY
1959    __value_func() _NOEXCEPT : __f_(nullptr) {}
1960
1961    template <class _Fp, class _Alloc>
1962    _LIBCPP_INLINE_VISIBILITY __value_func(_Fp&& __f, const _Alloc& __a)
1963        : __f_(nullptr)
1964    {
1965        typedef allocator_traits<_Alloc> __alloc_traits;
1966        typedef __function::__func<_Fp, _Alloc, _Rp(_ArgTypes...)> _Fun;
1967        typedef typename __rebind_alloc_helper<__alloc_traits, _Fun>::type
1968            _FunAlloc;
1969
1970        if (__function::__not_null(__f))
1971        {
1972            _FunAlloc __af(__a);
1973            if (sizeof(_Fun) <= sizeof(__buf_) &&
1974                is_nothrow_copy_constructible<_Fp>::value &&
1975                is_nothrow_copy_constructible<_FunAlloc>::value)
1976            {
1977                __f_ =
1978                    ::new ((void*)&__buf_) _Fun(_VSTD::move(__f), _Alloc(__af));
1979            }
1980            else
1981            {
1982                typedef __allocator_destructor<_FunAlloc> _Dp;
1983                unique_ptr<__func, _Dp> __hold(__af.allocate(1), _Dp(__af, 1));
1984                ::new ((void*)__hold.get()) _Fun(_VSTD::move(__f), _Alloc(__a));
1985                __f_ = __hold.release();
1986            }
1987        }
1988    }
1989
1990    template <class _Fp,
1991        class = typename enable_if<!is_same<typename decay<_Fp>::type, __value_func>::value>::type>
1992    _LIBCPP_INLINE_VISIBILITY explicit __value_func(_Fp&& __f)
1993        : __value_func(_VSTD::forward<_Fp>(__f), allocator<_Fp>()) {}
1994
1995    _LIBCPP_INLINE_VISIBILITY
1996    __value_func(const __value_func& __f)
1997    {
1998        if (__f.__f_ == nullptr)
1999            __f_ = nullptr;
2000        else if ((void*)__f.__f_ == &__f.__buf_)
2001        {
2002            __f_ = __as_base(&__buf_);
2003            __f.__f_->__clone(__f_);
2004        }
2005        else
2006            __f_ = __f.__f_->__clone();
2007    }
2008
2009    _LIBCPP_INLINE_VISIBILITY
2010    __value_func(__value_func&& __f) _NOEXCEPT
2011    {
2012        if (__f.__f_ == nullptr)
2013            __f_ = nullptr;
2014        else if ((void*)__f.__f_ == &__f.__buf_)
2015        {
2016            __f_ = __as_base(&__buf_);
2017            __f.__f_->__clone(__f_);
2018        }
2019        else
2020        {
2021            __f_ = __f.__f_;
2022            __f.__f_ = nullptr;
2023        }
2024    }
2025
2026    _LIBCPP_INLINE_VISIBILITY
2027    ~__value_func()
2028    {
2029        if ((void*)__f_ == &__buf_)
2030            __f_->destroy();
2031        else if (__f_)
2032            __f_->destroy_deallocate();
2033    }
2034
2035    _LIBCPP_INLINE_VISIBILITY
2036    __value_func& operator=(__value_func&& __f)
2037    {
2038        *this = nullptr;
2039        if (__f.__f_ == nullptr)
2040            __f_ = nullptr;
2041        else if ((void*)__f.__f_ == &__f.__buf_)
2042        {
2043            __f_ = __as_base(&__buf_);
2044            __f.__f_->__clone(__f_);
2045        }
2046        else
2047        {
2048            __f_ = __f.__f_;
2049            __f.__f_ = nullptr;
2050        }
2051        return *this;
2052    }
2053
2054    _LIBCPP_INLINE_VISIBILITY
2055    __value_func& operator=(nullptr_t)
2056    {
2057        __func* __f = __f_;
2058        __f_ = nullptr;
2059        if ((void*)__f == &__buf_)
2060            __f->destroy();
2061        else if (__f)
2062            __f->destroy_deallocate();
2063        return *this;
2064    }
2065
2066    _LIBCPP_INLINE_VISIBILITY
2067    _Rp operator()(_ArgTypes&&... __args) const
2068    {
2069        if (__f_ == nullptr)
2070            __throw_bad_function_call();
2071        return (*__f_)(_VSTD::forward<_ArgTypes>(__args)...);
2072    }
2073
2074    _LIBCPP_INLINE_VISIBILITY
2075    void swap(__value_func& __f) _NOEXCEPT
2076    {
2077        if (&__f == this)
2078            return;
2079        if ((void*)__f_ == &__buf_ && (void*)__f.__f_ == &__f.__buf_)
2080        {
2081            typename aligned_storage<sizeof(__buf_)>::type __tempbuf;
2082            __func* __t = __as_base(&__tempbuf);
2083            __f_->__clone(__t);
2084            __f_->destroy();
2085            __f_ = nullptr;
2086            __f.__f_->__clone(__as_base(&__buf_));
2087            __f.__f_->destroy();
2088            __f.__f_ = nullptr;
2089            __f_ = __as_base(&__buf_);
2090            __t->__clone(__as_base(&__f.__buf_));
2091            __t->destroy();
2092            __f.__f_ = __as_base(&__f.__buf_);
2093        }
2094        else if ((void*)__f_ == &__buf_)
2095        {
2096            __f_->__clone(__as_base(&__f.__buf_));
2097            __f_->destroy();
2098            __f_ = __f.__f_;
2099            __f.__f_ = __as_base(&__f.__buf_);
2100        }
2101        else if ((void*)__f.__f_ == &__f.__buf_)
2102        {
2103            __f.__f_->__clone(__as_base(&__buf_));
2104            __f.__f_->destroy();
2105            __f.__f_ = __f_;
2106            __f_ = __as_base(&__buf_);
2107        }
2108        else
2109            _VSTD::swap(__f_, __f.__f_);
2110    }
2111
2112    _LIBCPP_INLINE_VISIBILITY
2113    _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT { return __f_ != nullptr; }
2114
2115#ifndef _LIBCPP_NO_RTTI
2116    _LIBCPP_INLINE_VISIBILITY
2117    const std::type_info& target_type() const _NOEXCEPT
2118    {
2119        if (__f_ == nullptr)
2120            return typeid(void);
2121        return __f_->target_type();
2122    }
2123
2124    template <typename _Tp>
2125    _LIBCPP_INLINE_VISIBILITY const _Tp* target() const _NOEXCEPT
2126    {
2127        if (__f_ == nullptr)
2128            return nullptr;
2129        return (const _Tp*)__f_->target(typeid(_Tp));
2130    }
2131#endif // _LIBCPP_NO_RTTI
2132};
2133
2134// Storage for a functor object, to be used with __policy to manage copy and
2135// destruction.
2136union __policy_storage
2137{
2138    mutable char __small[sizeof(void*) * 2];
2139    void* __large;
2140};
2141
2142// True if _Fun can safely be held in __policy_storage.__small.
2143template <typename _Fun>
2144struct __use_small_storage
2145    : public integral_constant<
2146          bool, sizeof(_Fun) <= sizeof(__policy_storage) &&
2147                    _LIBCPP_ALIGNOF(_Fun) <= _LIBCPP_ALIGNOF(__policy_storage) &&
2148                    is_trivially_copy_constructible<_Fun>::value &&
2149                    is_trivially_destructible<_Fun>::value> {};
2150
2151// Policy contains information about how to copy, destroy, and move the
2152// underlying functor. You can think of it as a vtable of sorts.
2153struct __policy
2154{
2155    // Used to copy or destroy __large values. null for trivial objects.
2156    void* (*const __clone)(const void*);
2157    void (*const __destroy)(void*);
2158
2159    // True if this is the null policy (no value).
2160    const bool __is_null;
2161
2162    // The target type. May be null if RTTI is disabled.
2163    const std::type_info* const __type_info;
2164
2165    // Returns a pointer to a static policy object suitable for the functor
2166    // type.
2167    template <typename _Fun>
2168    _LIBCPP_INLINE_VISIBILITY static const __policy* __create()
2169    {
2170        return __choose_policy<_Fun>(__use_small_storage<_Fun>());
2171    }
2172
2173    _LIBCPP_INLINE_VISIBILITY
2174    static const __policy* __create_empty()
2175    {
2176        static const _LIBCPP_CONSTEXPR __policy __policy_ = {nullptr, nullptr,
2177                                                             true,
2178#ifndef _LIBCPP_NO_RTTI
2179                                                             &typeid(void)
2180#else
2181                                                             nullptr
2182#endif
2183        };
2184        return &__policy_;
2185    }
2186
2187  private:
2188    template <typename _Fun> static void* __large_clone(const void* __s)
2189    {
2190        const _Fun* __f = static_cast<const _Fun*>(__s);
2191        return __f->__clone();
2192    }
2193
2194    template <typename _Fun>
2195    static void __large_destroy(void* __s) {
2196      _Fun::__destroy_and_delete(static_cast<_Fun*>(__s));
2197    }
2198
2199    template <typename _Fun>
2200    _LIBCPP_INLINE_VISIBILITY static const __policy*
2201    __choose_policy(/* is_small = */ false_type) {
2202      static const _LIBCPP_CONSTEXPR __policy __policy_ = {
2203          &__large_clone<_Fun>, &__large_destroy<_Fun>, false,
2204#ifndef _LIBCPP_NO_RTTI
2205          &typeid(typename _Fun::_Target)
2206#else
2207          nullptr
2208#endif
2209      };
2210        return &__policy_;
2211    }
2212
2213    template <typename _Fun>
2214    _LIBCPP_INLINE_VISIBILITY static const __policy*
2215        __choose_policy(/* is_small = */ true_type)
2216    {
2217        static const _LIBCPP_CONSTEXPR __policy __policy_ = {
2218            nullptr, nullptr, false,
2219#ifndef _LIBCPP_NO_RTTI
2220            &typeid(typename _Fun::_Target)
2221#else
2222            nullptr
2223#endif
2224        };
2225        return &__policy_;
2226    }
2227};
2228
2229// Used to choose between perfect forwarding or pass-by-value. Pass-by-value is
2230// faster for types that can be passed in registers.
2231template <typename _Tp>
2232using __fast_forward =
2233    typename conditional<is_scalar<_Tp>::value, _Tp, _Tp&&>::type;
2234
2235// __policy_invoker calls an instance of __alloc_func held in __policy_storage.
2236
2237template <class _Fp> struct __policy_invoker;
2238
2239template <class _Rp, class... _ArgTypes>
2240struct __policy_invoker<_Rp(_ArgTypes...)>
2241{
2242    typedef _Rp (*__Call)(const __policy_storage*,
2243                          __fast_forward<_ArgTypes>...);
2244
2245    __Call __call_;
2246
2247    // Creates an invoker that throws bad_function_call.
2248    _LIBCPP_INLINE_VISIBILITY
2249    __policy_invoker() : __call_(&__call_empty) {}
2250
2251    // Creates an invoker that calls the given instance of __func.
2252    template <typename _Fun>
2253    _LIBCPP_INLINE_VISIBILITY static __policy_invoker __create()
2254    {
2255        return __policy_invoker(&__call_impl<_Fun>);
2256    }
2257
2258  private:
2259    _LIBCPP_INLINE_VISIBILITY
2260    explicit __policy_invoker(__Call __c) : __call_(__c) {}
2261
2262    static _Rp __call_empty(const __policy_storage*,
2263                            __fast_forward<_ArgTypes>...)
2264    {
2265        __throw_bad_function_call();
2266    }
2267
2268    template <typename _Fun>
2269    static _Rp __call_impl(const __policy_storage* __buf,
2270                           __fast_forward<_ArgTypes>... __args)
2271    {
2272        _Fun* __f = reinterpret_cast<_Fun*>(__use_small_storage<_Fun>::value
2273                                                ? &__buf->__small
2274                                                : __buf->__large);
2275        return (*__f)(_VSTD::forward<_ArgTypes>(__args)...);
2276    }
2277};
2278
2279// __policy_func uses a __policy and __policy_invoker to create a type-erased,
2280// copyable functor.
2281
2282template <class _Fp> class __policy_func;
2283
2284template <class _Rp, class... _ArgTypes> class __policy_func<_Rp(_ArgTypes...)>
2285{
2286    // Inline storage for small objects.
2287    __policy_storage __buf_;
2288
2289    // Calls the value stored in __buf_. This could technically be part of
2290    // policy, but storing it here eliminates a level of indirection inside
2291    // operator().
2292    typedef __function::__policy_invoker<_Rp(_ArgTypes...)> __invoker;
2293    __invoker __invoker_;
2294
2295    // The policy that describes how to move / copy / destroy __buf_. Never
2296    // null, even if the function is empty.
2297    const __policy* __policy_;
2298
2299  public:
2300    _LIBCPP_INLINE_VISIBILITY
2301    __policy_func() : __policy_(__policy::__create_empty()) {}
2302
2303    template <class _Fp, class _Alloc>
2304    _LIBCPP_INLINE_VISIBILITY __policy_func(_Fp&& __f, const _Alloc& __a)
2305        : __policy_(__policy::__create_empty())
2306    {
2307        typedef __alloc_func<_Fp, _Alloc, _Rp(_ArgTypes...)> _Fun;
2308        typedef allocator_traits<_Alloc> __alloc_traits;
2309        typedef typename __rebind_alloc_helper<__alloc_traits, _Fun>::type
2310            _FunAlloc;
2311
2312        if (__function::__not_null(__f))
2313        {
2314            __invoker_ = __invoker::template __create<_Fun>();
2315            __policy_ = __policy::__create<_Fun>();
2316
2317            _FunAlloc __af(__a);
2318            if (__use_small_storage<_Fun>())
2319            {
2320                ::new ((void*)&__buf_.__small)
2321                    _Fun(_VSTD::move(__f), _Alloc(__af));
2322            }
2323            else
2324            {
2325                typedef __allocator_destructor<_FunAlloc> _Dp;
2326                unique_ptr<_Fun, _Dp> __hold(__af.allocate(1), _Dp(__af, 1));
2327                ::new ((void*)__hold.get())
2328                    _Fun(_VSTD::move(__f), _Alloc(__af));
2329                __buf_.__large = __hold.release();
2330            }
2331        }
2332    }
2333
2334    template <class _Fp, class = typename enable_if<!is_same<typename decay<_Fp>::type, __policy_func>::value>::type>
2335    _LIBCPP_INLINE_VISIBILITY explicit __policy_func(_Fp&& __f)
2336        : __policy_(__policy::__create_empty()) {
2337      typedef __default_alloc_func<_Fp, _Rp(_ArgTypes...)> _Fun;
2338
2339      if (__function::__not_null(__f)) {
2340        __invoker_ = __invoker::template __create<_Fun>();
2341        __policy_ = __policy::__create<_Fun>();
2342        if (__use_small_storage<_Fun>()) {
2343          ::new ((void*)&__buf_.__small) _Fun(_VSTD::move(__f));
2344        } else {
2345          __builtin_new_allocator::__holder_t __hold =
2346              __builtin_new_allocator::__allocate_type<_Fun>(1);
2347          __buf_.__large = ::new ((void*)__hold.get()) _Fun(_VSTD::move(__f));
2348          (void)__hold.release();
2349        }
2350      }
2351    }
2352
2353    _LIBCPP_INLINE_VISIBILITY
2354    __policy_func(const __policy_func& __f)
2355        : __buf_(__f.__buf_), __invoker_(__f.__invoker_),
2356          __policy_(__f.__policy_)
2357    {
2358        if (__policy_->__clone)
2359            __buf_.__large = __policy_->__clone(__f.__buf_.__large);
2360    }
2361
2362    _LIBCPP_INLINE_VISIBILITY
2363    __policy_func(__policy_func&& __f)
2364        : __buf_(__f.__buf_), __invoker_(__f.__invoker_),
2365          __policy_(__f.__policy_)
2366    {
2367        if (__policy_->__destroy)
2368        {
2369            __f.__policy_ = __policy::__create_empty();
2370            __f.__invoker_ = __invoker();
2371        }
2372    }
2373
2374    _LIBCPP_INLINE_VISIBILITY
2375    ~__policy_func()
2376    {
2377        if (__policy_->__destroy)
2378            __policy_->__destroy(__buf_.__large);
2379    }
2380
2381    _LIBCPP_INLINE_VISIBILITY
2382    __policy_func& operator=(__policy_func&& __f)
2383    {
2384        *this = nullptr;
2385        __buf_ = __f.__buf_;
2386        __invoker_ = __f.__invoker_;
2387        __policy_ = __f.__policy_;
2388        __f.__policy_ = __policy::__create_empty();
2389        __f.__invoker_ = __invoker();
2390        return *this;
2391    }
2392
2393    _LIBCPP_INLINE_VISIBILITY
2394    __policy_func& operator=(nullptr_t)
2395    {
2396        const __policy* __p = __policy_;
2397        __policy_ = __policy::__create_empty();
2398        __invoker_ = __invoker();
2399        if (__p->__destroy)
2400            __p->__destroy(__buf_.__large);
2401        return *this;
2402    }
2403
2404    _LIBCPP_INLINE_VISIBILITY
2405    _Rp operator()(_ArgTypes&&... __args) const
2406    {
2407        return __invoker_.__call_(_VSTD::addressof(__buf_),
2408                                  _VSTD::forward<_ArgTypes>(__args)...);
2409    }
2410
2411    _LIBCPP_INLINE_VISIBILITY
2412    void swap(__policy_func& __f)
2413    {
2414        _VSTD::swap(__invoker_, __f.__invoker_);
2415        _VSTD::swap(__policy_, __f.__policy_);
2416        _VSTD::swap(__buf_, __f.__buf_);
2417    }
2418
2419    _LIBCPP_INLINE_VISIBILITY
2420    explicit operator bool() const _NOEXCEPT
2421    {
2422        return !__policy_->__is_null;
2423    }
2424
2425#ifndef _LIBCPP_NO_RTTI
2426    _LIBCPP_INLINE_VISIBILITY
2427    const std::type_info& target_type() const _NOEXCEPT
2428    {
2429        return *__policy_->__type_info;
2430    }
2431
2432    template <typename _Tp>
2433    _LIBCPP_INLINE_VISIBILITY const _Tp* target() const _NOEXCEPT
2434    {
2435        if (__policy_->__is_null || typeid(_Tp) != *__policy_->__type_info)
2436            return nullptr;
2437        if (__policy_->__clone) // Out of line storage.
2438            return reinterpret_cast<const _Tp*>(__buf_.__large);
2439        else
2440            return reinterpret_cast<const _Tp*>(&__buf_.__small);
2441    }
2442#endif // _LIBCPP_NO_RTTI
2443};
2444
2445#if defined(_LIBCPP_HAS_BLOCKS_RUNTIME) && !defined(_LIBCPP_HAS_OBJC_ARC)
2446
2447extern "C" void *_Block_copy(const void *);
2448extern "C" void _Block_release(const void *);
2449
2450template<class _Rp1, class ..._ArgTypes1, class _Alloc, class _Rp, class ..._ArgTypes>
2451class __func<_Rp1(^)(_ArgTypes1...), _Alloc, _Rp(_ArgTypes...)>
2452    : public  __base<_Rp(_ArgTypes...)>
2453{
2454    typedef _Rp1(^__block_type)(_ArgTypes1...);
2455    __block_type __f_;
2456
2457public:
2458    _LIBCPP_INLINE_VISIBILITY
2459    explicit __func(__block_type const& __f)
2460        : __f_(reinterpret_cast<__block_type>(__f ? _Block_copy(__f) : nullptr))
2461    { }
2462
2463    // [TODO] add && to save on a retain
2464
2465    _LIBCPP_INLINE_VISIBILITY
2466    explicit __func(__block_type __f, const _Alloc& /* unused */)
2467        : __f_(reinterpret_cast<__block_type>(__f ? _Block_copy(__f) : nullptr))
2468    { }
2469
2470    virtual __base<_Rp(_ArgTypes...)>* __clone() const {
2471        _LIBCPP_ASSERT(false,
2472            "Block pointers are just pointers, so they should always fit into "
2473            "std::function's small buffer optimization. This function should "
2474            "never be invoked.");
2475        return nullptr;
2476    }
2477
2478    virtual void __clone(__base<_Rp(_ArgTypes...)>* __p) const {
2479        ::new ((void*)__p) __func(__f_);
2480    }
2481
2482    virtual void destroy() _NOEXCEPT {
2483        if (__f_)
2484            _Block_release(__f_);
2485        __f_ = 0;
2486    }
2487
2488    virtual void destroy_deallocate() _NOEXCEPT {
2489        _LIBCPP_ASSERT(false,
2490            "Block pointers are just pointers, so they should always fit into "
2491            "std::function's small buffer optimization. This function should "
2492            "never be invoked.");
2493    }
2494
2495    virtual _Rp operator()(_ArgTypes&& ... __arg) {
2496        return _VSTD::__invoke(__f_, _VSTD::forward<_ArgTypes>(__arg)...);
2497    }
2498
2499#ifndef _LIBCPP_NO_RTTI
2500    virtual const void* target(type_info const& __ti) const _NOEXCEPT {
2501        if (__ti == typeid(__func::__block_type))
2502            return &__f_;
2503        return (const void*)nullptr;
2504    }
2505
2506    virtual const std::type_info& target_type() const _NOEXCEPT {
2507        return typeid(__func::__block_type);
2508    }
2509#endif // _LIBCPP_NO_RTTI
2510};
2511
2512#endif // _LIBCPP_HAS_EXTENSION_BLOCKS && !_LIBCPP_HAS_OBJC_ARC
2513
2514}  // __function
2515
2516template<class _Rp, class ..._ArgTypes>
2517class _LIBCPP_TEMPLATE_VIS function<_Rp(_ArgTypes...)>
2518#if _LIBCPP_STD_VER <= 17 || !defined(_LIBCPP_ABI_NO_BINDER_BASES)
2519    : public __function::__maybe_derive_from_unary_function<_Rp(_ArgTypes...)>,
2520      public __function::__maybe_derive_from_binary_function<_Rp(_ArgTypes...)>
2521#endif
2522{
2523#ifndef _LIBCPP_ABI_OPTIMIZED_FUNCTION
2524    typedef __function::__value_func<_Rp(_ArgTypes...)> __func;
2525#else
2526    typedef __function::__policy_func<_Rp(_ArgTypes...)> __func;
2527#endif
2528
2529    __func __f_;
2530
2531    template <class _Fp, bool = _And<
2532        _IsNotSame<__uncvref_t<_Fp>, function>,
2533        __invokable<_Fp, _ArgTypes...>
2534    >::value>
2535    struct __callable;
2536    template <class _Fp>
2537        struct __callable<_Fp, true>
2538        {
2539            static const bool value = is_void<_Rp>::value ||
2540                __is_core_convertible<typename __invoke_of<_Fp, _ArgTypes...>::type,
2541                                      _Rp>::value;
2542        };
2543    template <class _Fp>
2544        struct __callable<_Fp, false>
2545        {
2546            static const bool value = false;
2547        };
2548
2549  template <class _Fp>
2550  using _EnableIfLValueCallable = typename enable_if<__callable<_Fp&>::value>::type;
2551public:
2552    typedef _Rp result_type;
2553
2554    // construct/copy/destroy:
2555    _LIBCPP_INLINE_VISIBILITY
2556    function() _NOEXCEPT { }
2557    _LIBCPP_INLINE_VISIBILITY
2558    function(nullptr_t) _NOEXCEPT {}
2559    function(const function&);
2560    function(function&&) _NOEXCEPT;
2561    template<class _Fp, class = _EnableIfLValueCallable<_Fp>>
2562    function(_Fp);
2563
2564#if _LIBCPP_STD_VER <= 14
2565    template<class _Alloc>
2566      _LIBCPP_INLINE_VISIBILITY
2567      function(allocator_arg_t, const _Alloc&) _NOEXCEPT {}
2568    template<class _Alloc>
2569      _LIBCPP_INLINE_VISIBILITY
2570      function(allocator_arg_t, const _Alloc&, nullptr_t) _NOEXCEPT {}
2571    template<class _Alloc>
2572      function(allocator_arg_t, const _Alloc&, const function&);
2573    template<class _Alloc>
2574      function(allocator_arg_t, const _Alloc&, function&&);
2575    template<class _Fp, class _Alloc, class = _EnableIfLValueCallable<_Fp>>
2576      function(allocator_arg_t, const _Alloc& __a, _Fp __f);
2577#endif
2578
2579    function& operator=(const function&);
2580    function& operator=(function&&) _NOEXCEPT;
2581    function& operator=(nullptr_t) _NOEXCEPT;
2582    template<class _Fp, class = _EnableIfLValueCallable<typename decay<_Fp>::type>>
2583    function& operator=(_Fp&&);
2584
2585    ~function();
2586
2587    // function modifiers:
2588    void swap(function&) _NOEXCEPT;
2589
2590#if _LIBCPP_STD_VER <= 14
2591    template<class _Fp, class _Alloc>
2592      _LIBCPP_INLINE_VISIBILITY
2593      void assign(_Fp&& __f, const _Alloc& __a)
2594        {function(allocator_arg, __a, _VSTD::forward<_Fp>(__f)).swap(*this);}
2595#endif
2596
2597    // function capacity:
2598    _LIBCPP_INLINE_VISIBILITY
2599    _LIBCPP_EXPLICIT operator bool() const _NOEXCEPT {
2600      return static_cast<bool>(__f_);
2601    }
2602
2603    // deleted overloads close possible hole in the type system
2604    template<class _R2, class... _ArgTypes2>
2605      bool operator==(const function<_R2(_ArgTypes2...)>&) const = delete;
2606    template<class _R2, class... _ArgTypes2>
2607      bool operator!=(const function<_R2(_ArgTypes2...)>&) const = delete;
2608public:
2609    // function invocation:
2610    _Rp operator()(_ArgTypes...) const;
2611
2612#ifndef _LIBCPP_NO_RTTI
2613    // function target access:
2614    const std::type_info& target_type() const _NOEXCEPT;
2615    template <typename _Tp> _Tp* target() _NOEXCEPT;
2616    template <typename _Tp> const _Tp* target() const _NOEXCEPT;
2617#endif // _LIBCPP_NO_RTTI
2618};
2619
2620#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
2621template<class _Rp, class ..._Ap>
2622function(_Rp(*)(_Ap...)) -> function<_Rp(_Ap...)>;
2623
2624template<class _Fp>
2625struct __strip_signature;
2626
2627template<class _Rp, class _Gp, class ..._Ap>
2628struct __strip_signature<_Rp (_Gp::*) (_Ap...)> { using type = _Rp(_Ap...); };
2629template<class _Rp, class _Gp, class ..._Ap>
2630struct __strip_signature<_Rp (_Gp::*) (_Ap...) const> { using type = _Rp(_Ap...); };
2631template<class _Rp, class _Gp, class ..._Ap>
2632struct __strip_signature<_Rp (_Gp::*) (_Ap...) volatile> { using type = _Rp(_Ap...); };
2633template<class _Rp, class _Gp, class ..._Ap>
2634struct __strip_signature<_Rp (_Gp::*) (_Ap...) const volatile> { using type = _Rp(_Ap...); };
2635
2636template<class _Rp, class _Gp, class ..._Ap>
2637struct __strip_signature<_Rp (_Gp::*) (_Ap...) &> { using type = _Rp(_Ap...); };
2638template<class _Rp, class _Gp, class ..._Ap>
2639struct __strip_signature<_Rp (_Gp::*) (_Ap...) const &> { using type = _Rp(_Ap...); };
2640template<class _Rp, class _Gp, class ..._Ap>
2641struct __strip_signature<_Rp (_Gp::*) (_Ap...) volatile &> { using type = _Rp(_Ap...); };
2642template<class _Rp, class _Gp, class ..._Ap>
2643struct __strip_signature<_Rp (_Gp::*) (_Ap...) const volatile &> { using type = _Rp(_Ap...); };
2644
2645template<class _Rp, class _Gp, class ..._Ap>
2646struct __strip_signature<_Rp (_Gp::*) (_Ap...) noexcept> { using type = _Rp(_Ap...); };
2647template<class _Rp, class _Gp, class ..._Ap>
2648struct __strip_signature<_Rp (_Gp::*) (_Ap...) const noexcept> { using type = _Rp(_Ap...); };
2649template<class _Rp, class _Gp, class ..._Ap>
2650struct __strip_signature<_Rp (_Gp::*) (_Ap...) volatile noexcept> { using type = _Rp(_Ap...); };
2651template<class _Rp, class _Gp, class ..._Ap>
2652struct __strip_signature<_Rp (_Gp::*) (_Ap...) const volatile noexcept> { using type = _Rp(_Ap...); };
2653
2654template<class _Rp, class _Gp, class ..._Ap>
2655struct __strip_signature<_Rp (_Gp::*) (_Ap...) & noexcept> { using type = _Rp(_Ap...); };
2656template<class _Rp, class _Gp, class ..._Ap>
2657struct __strip_signature<_Rp (_Gp::*) (_Ap...) const & noexcept> { using type = _Rp(_Ap...); };
2658template<class _Rp, class _Gp, class ..._Ap>
2659struct __strip_signature<_Rp (_Gp::*) (_Ap...) volatile & noexcept> { using type = _Rp(_Ap...); };
2660template<class _Rp, class _Gp, class ..._Ap>
2661struct __strip_signature<_Rp (_Gp::*) (_Ap...) const volatile & noexcept> { using type = _Rp(_Ap...); };
2662
2663template<class _Fp, class _Stripped = typename __strip_signature<decltype(&_Fp::operator())>::type>
2664function(_Fp) -> function<_Stripped>;
2665#endif // !_LIBCPP_HAS_NO_DEDUCTION_GUIDES
2666
2667template<class _Rp, class ..._ArgTypes>
2668function<_Rp(_ArgTypes...)>::function(const function& __f) : __f_(__f.__f_) {}
2669
2670#if _LIBCPP_STD_VER <= 14
2671template<class _Rp, class ..._ArgTypes>
2672template <class _Alloc>
2673function<_Rp(_ArgTypes...)>::function(allocator_arg_t, const _Alloc&,
2674                                     const function& __f) : __f_(__f.__f_) {}
2675#endif
2676
2677template <class _Rp, class... _ArgTypes>
2678function<_Rp(_ArgTypes...)>::function(function&& __f) _NOEXCEPT
2679    : __f_(_VSTD::move(__f.__f_)) {}
2680
2681#if _LIBCPP_STD_VER <= 14
2682template<class _Rp, class ..._ArgTypes>
2683template <class _Alloc>
2684function<_Rp(_ArgTypes...)>::function(allocator_arg_t, const _Alloc&,
2685                                      function&& __f)
2686    : __f_(_VSTD::move(__f.__f_)) {}
2687#endif
2688
2689template <class _Rp, class... _ArgTypes>
2690template <class _Fp, class>
2691function<_Rp(_ArgTypes...)>::function(_Fp __f) : __f_(_VSTD::move(__f)) {}
2692
2693#if _LIBCPP_STD_VER <= 14
2694template <class _Rp, class... _ArgTypes>
2695template <class _Fp, class _Alloc, class>
2696function<_Rp(_ArgTypes...)>::function(allocator_arg_t, const _Alloc& __a,
2697                                      _Fp __f)
2698    : __f_(_VSTD::move(__f), __a) {}
2699#endif
2700
2701template<class _Rp, class ..._ArgTypes>
2702function<_Rp(_ArgTypes...)>&
2703function<_Rp(_ArgTypes...)>::operator=(const function& __f)
2704{
2705    function(__f).swap(*this);
2706    return *this;
2707}
2708
2709template<class _Rp, class ..._ArgTypes>
2710function<_Rp(_ArgTypes...)>&
2711function<_Rp(_ArgTypes...)>::operator=(function&& __f) _NOEXCEPT
2712{
2713    __f_ = _VSTD::move(__f.__f_);
2714    return *this;
2715}
2716
2717template<class _Rp, class ..._ArgTypes>
2718function<_Rp(_ArgTypes...)>&
2719function<_Rp(_ArgTypes...)>::operator=(nullptr_t) _NOEXCEPT
2720{
2721    __f_ = nullptr;
2722    return *this;
2723}
2724
2725template<class _Rp, class ..._ArgTypes>
2726template <class _Fp, class>
2727function<_Rp(_ArgTypes...)>&
2728function<_Rp(_ArgTypes...)>::operator=(_Fp&& __f)
2729{
2730    function(_VSTD::forward<_Fp>(__f)).swap(*this);
2731    return *this;
2732}
2733
2734template<class _Rp, class ..._ArgTypes>
2735function<_Rp(_ArgTypes...)>::~function() {}
2736
2737template<class _Rp, class ..._ArgTypes>
2738void
2739function<_Rp(_ArgTypes...)>::swap(function& __f) _NOEXCEPT
2740{
2741    __f_.swap(__f.__f_);
2742}
2743
2744template<class _Rp, class ..._ArgTypes>
2745_Rp
2746function<_Rp(_ArgTypes...)>::operator()(_ArgTypes... __arg) const
2747{
2748    return __f_(_VSTD::forward<_ArgTypes>(__arg)...);
2749}
2750
2751#ifndef _LIBCPP_NO_RTTI
2752
2753template<class _Rp, class ..._ArgTypes>
2754const std::type_info&
2755function<_Rp(_ArgTypes...)>::target_type() const _NOEXCEPT
2756{
2757    return __f_.target_type();
2758}
2759
2760template<class _Rp, class ..._ArgTypes>
2761template <typename _Tp>
2762_Tp*
2763function<_Rp(_ArgTypes...)>::target() _NOEXCEPT
2764{
2765    return (_Tp*)(__f_.template target<_Tp>());
2766}
2767
2768template<class _Rp, class ..._ArgTypes>
2769template <typename _Tp>
2770const _Tp*
2771function<_Rp(_ArgTypes...)>::target() const _NOEXCEPT
2772{
2773    return __f_.template target<_Tp>();
2774}
2775
2776#endif // _LIBCPP_NO_RTTI
2777
2778template <class _Rp, class... _ArgTypes>
2779inline _LIBCPP_INLINE_VISIBILITY
2780bool
2781operator==(const function<_Rp(_ArgTypes...)>& __f, nullptr_t) _NOEXCEPT {return !__f;}
2782
2783template <class _Rp, class... _ArgTypes>
2784inline _LIBCPP_INLINE_VISIBILITY
2785bool
2786operator==(nullptr_t, const function<_Rp(_ArgTypes...)>& __f) _NOEXCEPT {return !__f;}
2787
2788template <class _Rp, class... _ArgTypes>
2789inline _LIBCPP_INLINE_VISIBILITY
2790bool
2791operator!=(const function<_Rp(_ArgTypes...)>& __f, nullptr_t) _NOEXCEPT {return (bool)__f;}
2792
2793template <class _Rp, class... _ArgTypes>
2794inline _LIBCPP_INLINE_VISIBILITY
2795bool
2796operator!=(nullptr_t, const function<_Rp(_ArgTypes...)>& __f) _NOEXCEPT {return (bool)__f;}
2797
2798template <class _Rp, class... _ArgTypes>
2799inline _LIBCPP_INLINE_VISIBILITY
2800void
2801swap(function<_Rp(_ArgTypes...)>& __x, function<_Rp(_ArgTypes...)>& __y) _NOEXCEPT
2802{return __x.swap(__y);}
2803
2804#else // _LIBCPP_CXX03_LANG
2805
2806#include <__functional_03>
2807
2808#endif
2809
2810////////////////////////////////////////////////////////////////////////////////
2811//                                  BIND
2812//==============================================================================
2813
2814template<class _Tp> struct __is_bind_expression : public false_type {};
2815template<class _Tp> struct _LIBCPP_TEMPLATE_VIS is_bind_expression
2816    : public __is_bind_expression<typename remove_cv<_Tp>::type> {};
2817
2818#if _LIBCPP_STD_VER > 14
2819template <class _Tp>
2820_LIBCPP_INLINE_VAR constexpr size_t is_bind_expression_v = is_bind_expression<_Tp>::value;
2821#endif
2822
2823template<class _Tp> struct __is_placeholder : public integral_constant<int, 0> {};
2824template<class _Tp> struct _LIBCPP_TEMPLATE_VIS is_placeholder
2825    : public __is_placeholder<typename remove_cv<_Tp>::type> {};
2826
2827#if _LIBCPP_STD_VER > 14
2828template <class _Tp>
2829_LIBCPP_INLINE_VAR constexpr size_t is_placeholder_v = is_placeholder<_Tp>::value;
2830#endif
2831
2832namespace placeholders
2833{
2834
2835template <int _Np> struct __ph {};
2836
2837#if defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY)
2838_LIBCPP_FUNC_VIS extern const __ph<1>   _1;
2839_LIBCPP_FUNC_VIS extern const __ph<2>   _2;
2840_LIBCPP_FUNC_VIS extern const __ph<3>   _3;
2841_LIBCPP_FUNC_VIS extern const __ph<4>   _4;
2842_LIBCPP_FUNC_VIS extern const __ph<5>   _5;
2843_LIBCPP_FUNC_VIS extern const __ph<6>   _6;
2844_LIBCPP_FUNC_VIS extern const __ph<7>   _7;
2845_LIBCPP_FUNC_VIS extern const __ph<8>   _8;
2846_LIBCPP_FUNC_VIS extern const __ph<9>   _9;
2847_LIBCPP_FUNC_VIS extern const __ph<10> _10;
2848#else
2849/* _LIBCPP_INLINE_VAR */ constexpr __ph<1>   _1{};
2850/* _LIBCPP_INLINE_VAR */ constexpr __ph<2>   _2{};
2851/* _LIBCPP_INLINE_VAR */ constexpr __ph<3>   _3{};
2852/* _LIBCPP_INLINE_VAR */ constexpr __ph<4>   _4{};
2853/* _LIBCPP_INLINE_VAR */ constexpr __ph<5>   _5{};
2854/* _LIBCPP_INLINE_VAR */ constexpr __ph<6>   _6{};
2855/* _LIBCPP_INLINE_VAR */ constexpr __ph<7>   _7{};
2856/* _LIBCPP_INLINE_VAR */ constexpr __ph<8>   _8{};
2857/* _LIBCPP_INLINE_VAR */ constexpr __ph<9>   _9{};
2858/* _LIBCPP_INLINE_VAR */ constexpr __ph<10> _10{};
2859#endif // defined(_LIBCPP_CXX03_LANG) || defined(_LIBCPP_BUILDING_LIBRARY)
2860
2861}  // placeholders
2862
2863template<int _Np>
2864struct __is_placeholder<placeholders::__ph<_Np> >
2865    : public integral_constant<int, _Np> {};
2866
2867
2868#ifndef _LIBCPP_CXX03_LANG
2869
2870template <class _Tp, class _Uj>
2871inline _LIBCPP_INLINE_VISIBILITY
2872_Tp&
2873__mu(reference_wrapper<_Tp> __t, _Uj&)
2874{
2875    return __t.get();
2876}
2877
2878template <class _Ti, class ..._Uj, size_t ..._Indx>
2879inline _LIBCPP_INLINE_VISIBILITY
2880typename __invoke_of<_Ti&, _Uj...>::type
2881__mu_expand(_Ti& __ti, tuple<_Uj...>& __uj, __tuple_indices<_Indx...>)
2882{
2883    return __ti(_VSTD::forward<_Uj>(_VSTD::get<_Indx>(__uj))...);
2884}
2885
2886template <class _Ti, class ..._Uj>
2887inline _LIBCPP_INLINE_VISIBILITY
2888typename _EnableIf
2889<
2890    is_bind_expression<_Ti>::value,
2891    __invoke_of<_Ti&, _Uj...>
2892>::type
2893__mu(_Ti& __ti, tuple<_Uj...>& __uj)
2894{
2895    typedef typename __make_tuple_indices<sizeof...(_Uj)>::type __indices;
2896    return _VSTD::__mu_expand(__ti, __uj, __indices());
2897}
2898
2899template <bool IsPh, class _Ti, class _Uj>
2900struct __mu_return2 {};
2901
2902template <class _Ti, class _Uj>
2903struct __mu_return2<true, _Ti, _Uj>
2904{
2905    typedef typename tuple_element<is_placeholder<_Ti>::value - 1, _Uj>::type type;
2906};
2907
2908template <class _Ti, class _Uj>
2909inline _LIBCPP_INLINE_VISIBILITY
2910typename enable_if
2911<
2912    0 < is_placeholder<_Ti>::value,
2913    typename __mu_return2<0 < is_placeholder<_Ti>::value, _Ti, _Uj>::type
2914>::type
2915__mu(_Ti&, _Uj& __uj)
2916{
2917    const size_t _Indx = is_placeholder<_Ti>::value - 1;
2918    return _VSTD::forward<typename tuple_element<_Indx, _Uj>::type>(_VSTD::get<_Indx>(__uj));
2919}
2920
2921template <class _Ti, class _Uj>
2922inline _LIBCPP_INLINE_VISIBILITY
2923typename enable_if
2924<
2925    !is_bind_expression<_Ti>::value &&
2926    is_placeholder<_Ti>::value == 0 &&
2927    !__is_reference_wrapper<_Ti>::value,
2928    _Ti&
2929>::type
2930__mu(_Ti& __ti, _Uj&)
2931{
2932    return __ti;
2933}
2934
2935template <class _Ti, bool IsReferenceWrapper, bool IsBindEx, bool IsPh,
2936          class _TupleUj>
2937struct __mu_return_impl;
2938
2939template <bool _Invokable, class _Ti, class ..._Uj>
2940struct __mu_return_invokable  // false
2941{
2942    typedef __nat type;
2943};
2944
2945template <class _Ti, class ..._Uj>
2946struct __mu_return_invokable<true, _Ti, _Uj...>
2947{
2948    typedef typename __invoke_of<_Ti&, _Uj...>::type type;
2949};
2950
2951template <class _Ti, class ..._Uj>
2952struct __mu_return_impl<_Ti, false, true, false, tuple<_Uj...> >
2953    : public __mu_return_invokable<__invokable<_Ti&, _Uj...>::value, _Ti, _Uj...>
2954{
2955};
2956
2957template <class _Ti, class _TupleUj>
2958struct __mu_return_impl<_Ti, false, false, true, _TupleUj>
2959{
2960    typedef typename tuple_element<is_placeholder<_Ti>::value - 1,
2961                                   _TupleUj>::type&& type;
2962};
2963
2964template <class _Ti, class _TupleUj>
2965struct __mu_return_impl<_Ti, true, false, false, _TupleUj>
2966{
2967    typedef typename _Ti::type& type;
2968};
2969
2970template <class _Ti, class _TupleUj>
2971struct __mu_return_impl<_Ti, false, false, false, _TupleUj>
2972{
2973    typedef _Ti& type;
2974};
2975
2976template <class _Ti, class _TupleUj>
2977struct __mu_return
2978    : public __mu_return_impl<_Ti,
2979                              __is_reference_wrapper<_Ti>::value,
2980                              is_bind_expression<_Ti>::value,
2981                              0 < is_placeholder<_Ti>::value &&
2982                              is_placeholder<_Ti>::value <= tuple_size<_TupleUj>::value,
2983                              _TupleUj>
2984{
2985};
2986
2987template <class _Fp, class _BoundArgs, class _TupleUj>
2988struct __is_valid_bind_return
2989{
2990    static const bool value = false;
2991};
2992
2993template <class _Fp, class ..._BoundArgs, class _TupleUj>
2994struct __is_valid_bind_return<_Fp, tuple<_BoundArgs...>, _TupleUj>
2995{
2996    static const bool value = __invokable<_Fp,
2997                    typename __mu_return<_BoundArgs, _TupleUj>::type...>::value;
2998};
2999
3000template <class _Fp, class ..._BoundArgs, class _TupleUj>
3001struct __is_valid_bind_return<_Fp, const tuple<_BoundArgs...>, _TupleUj>
3002{
3003    static const bool value = __invokable<_Fp,
3004                    typename __mu_return<const _BoundArgs, _TupleUj>::type...>::value;
3005};
3006
3007template <class _Fp, class _BoundArgs, class _TupleUj,
3008          bool = __is_valid_bind_return<_Fp, _BoundArgs, _TupleUj>::value>
3009struct __bind_return;
3010
3011template <class _Fp, class ..._BoundArgs, class _TupleUj>
3012struct __bind_return<_Fp, tuple<_BoundArgs...>, _TupleUj, true>
3013{
3014    typedef typename __invoke_of
3015    <
3016        _Fp&,
3017        typename __mu_return
3018        <
3019            _BoundArgs,
3020            _TupleUj
3021        >::type...
3022    >::type type;
3023};
3024
3025template <class _Fp, class ..._BoundArgs, class _TupleUj>
3026struct __bind_return<_Fp, const tuple<_BoundArgs...>, _TupleUj, true>
3027{
3028    typedef typename __invoke_of
3029    <
3030        _Fp&,
3031        typename __mu_return
3032        <
3033            const _BoundArgs,
3034            _TupleUj
3035        >::type...
3036    >::type type;
3037};
3038
3039template <class _Fp, class _BoundArgs, size_t ..._Indx, class _Args>
3040inline _LIBCPP_INLINE_VISIBILITY
3041typename __bind_return<_Fp, _BoundArgs, _Args>::type
3042__apply_functor(_Fp& __f, _BoundArgs& __bound_args, __tuple_indices<_Indx...>,
3043                _Args&& __args)
3044{
3045    return _VSTD::__invoke(__f, _VSTD::__mu(_VSTD::get<_Indx>(__bound_args), __args)...);
3046}
3047
3048template<class _Fp, class ..._BoundArgs>
3049class __bind
3050#if _LIBCPP_STD_VER <= 17 || !defined(_LIBCPP_ABI_NO_BINDER_BASES)
3051    : public __weak_result_type<typename decay<_Fp>::type>
3052#endif
3053{
3054protected:
3055    typedef typename decay<_Fp>::type _Fd;
3056    typedef tuple<typename decay<_BoundArgs>::type...> _Td;
3057private:
3058    _Fd __f_;
3059    _Td __bound_args_;
3060
3061    typedef typename __make_tuple_indices<sizeof...(_BoundArgs)>::type __indices;
3062public:
3063    template <class _Gp, class ..._BA,
3064              class = typename enable_if
3065                               <
3066                                  is_constructible<_Fd, _Gp>::value &&
3067                                  !is_same<typename remove_reference<_Gp>::type,
3068                                           __bind>::value
3069                               >::type>
3070      _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3071      explicit __bind(_Gp&& __f, _BA&& ...__bound_args)
3072        : __f_(_VSTD::forward<_Gp>(__f)),
3073          __bound_args_(_VSTD::forward<_BA>(__bound_args)...) {}
3074
3075    template <class ..._Args>
3076        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3077        typename __bind_return<_Fd, _Td, tuple<_Args&&...> >::type
3078        operator()(_Args&& ...__args)
3079        {
3080            return _VSTD::__apply_functor(__f_, __bound_args_, __indices(),
3081                                  tuple<_Args&&...>(_VSTD::forward<_Args>(__args)...));
3082        }
3083
3084    template <class ..._Args>
3085        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3086        typename __bind_return<const _Fd, const _Td, tuple<_Args&&...> >::type
3087        operator()(_Args&& ...__args) const
3088        {
3089            return _VSTD::__apply_functor(__f_, __bound_args_, __indices(),
3090                                   tuple<_Args&&...>(_VSTD::forward<_Args>(__args)...));
3091        }
3092};
3093
3094template<class _Fp, class ..._BoundArgs>
3095struct __is_bind_expression<__bind<_Fp, _BoundArgs...> > : public true_type {};
3096
3097template<class _Rp, class _Fp, class ..._BoundArgs>
3098class __bind_r
3099    : public __bind<_Fp, _BoundArgs...>
3100{
3101    typedef __bind<_Fp, _BoundArgs...> base;
3102    typedef typename base::_Fd _Fd;
3103    typedef typename base::_Td _Td;
3104public:
3105    typedef _Rp result_type;
3106
3107
3108    template <class _Gp, class ..._BA,
3109              class = typename enable_if
3110                               <
3111                                  is_constructible<_Fd, _Gp>::value &&
3112                                  !is_same<typename remove_reference<_Gp>::type,
3113                                           __bind_r>::value
3114                               >::type>
3115      _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3116      explicit __bind_r(_Gp&& __f, _BA&& ...__bound_args)
3117        : base(_VSTD::forward<_Gp>(__f),
3118               _VSTD::forward<_BA>(__bound_args)...) {}
3119
3120    template <class ..._Args>
3121        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3122        typename enable_if
3123        <
3124            is_convertible<typename __bind_return<_Fd, _Td, tuple<_Args&&...> >::type,
3125                           result_type>::value || is_void<_Rp>::value,
3126            result_type
3127        >::type
3128        operator()(_Args&& ...__args)
3129        {
3130            typedef __invoke_void_return_wrapper<_Rp> _Invoker;
3131            return _Invoker::__call(static_cast<base&>(*this), _VSTD::forward<_Args>(__args)...);
3132        }
3133
3134    template <class ..._Args>
3135        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3136        typename enable_if
3137        <
3138            is_convertible<typename __bind_return<const _Fd, const _Td, tuple<_Args&&...> >::type,
3139                           result_type>::value || is_void<_Rp>::value,
3140            result_type
3141        >::type
3142        operator()(_Args&& ...__args) const
3143        {
3144            typedef __invoke_void_return_wrapper<_Rp> _Invoker;
3145            return _Invoker::__call(static_cast<base const&>(*this), _VSTD::forward<_Args>(__args)...);
3146        }
3147};
3148
3149template<class _Rp, class _Fp, class ..._BoundArgs>
3150struct __is_bind_expression<__bind_r<_Rp, _Fp, _BoundArgs...> > : public true_type {};
3151
3152template<class _Fp, class ..._BoundArgs>
3153inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3154__bind<_Fp, _BoundArgs...>
3155bind(_Fp&& __f, _BoundArgs&&... __bound_args)
3156{
3157    typedef __bind<_Fp, _BoundArgs...> type;
3158    return type(_VSTD::forward<_Fp>(__f), _VSTD::forward<_BoundArgs>(__bound_args)...);
3159}
3160
3161template<class _Rp, class _Fp, class ..._BoundArgs>
3162inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3163__bind_r<_Rp, _Fp, _BoundArgs...>
3164bind(_Fp&& __f, _BoundArgs&&... __bound_args)
3165{
3166    typedef __bind_r<_Rp, _Fp, _BoundArgs...> type;
3167    return type(_VSTD::forward<_Fp>(__f), _VSTD::forward<_BoundArgs>(__bound_args)...);
3168}
3169
3170#endif // _LIBCPP_CXX03_LANG
3171
3172#if _LIBCPP_STD_VER > 14
3173
3174template<class _Op, class _Tuple,
3175         class _Idxs = typename __make_tuple_indices<tuple_size<_Tuple>::value>::type>
3176struct __perfect_forward_impl;
3177
3178template<class _Op, class... _Bound, size_t... _Idxs>
3179struct __perfect_forward_impl<_Op, __tuple_types<_Bound...>, __tuple_indices<_Idxs...>>
3180{
3181    tuple<_Bound...> __bound_;
3182
3183    template<class... _Args>
3184    _LIBCPP_INLINE_VISIBILITY constexpr auto operator()(_Args&&... __args) &
3185    noexcept(noexcept(_Op::__call(_VSTD::get<_Idxs>(__bound_)..., _VSTD::forward<_Args>(__args)...)))
3186    -> decltype(      _Op::__call(_VSTD::get<_Idxs>(__bound_)..., _VSTD::forward<_Args>(__args)...))
3187    {return           _Op::__call(_VSTD::get<_Idxs>(__bound_)..., _VSTD::forward<_Args>(__args)...);}
3188
3189    template<class... _Args>
3190    _LIBCPP_INLINE_VISIBILITY constexpr auto operator()(_Args&&... __args) const&
3191    noexcept(noexcept(_Op::__call(_VSTD::get<_Idxs>(__bound_)..., _VSTD::forward<_Args>(__args)...)))
3192    -> decltype(      _Op::__call(_VSTD::get<_Idxs>(__bound_)..., _VSTD::forward<_Args>(__args)...))
3193    {return           _Op::__call(_VSTD::get<_Idxs>(__bound_)..., _VSTD::forward<_Args>(__args)...);}
3194
3195    template<class... _Args>
3196    _LIBCPP_INLINE_VISIBILITY constexpr auto operator()(_Args&&... __args) &&
3197    noexcept(noexcept(_Op::__call(_VSTD::get<_Idxs>(_VSTD::move(__bound_))...,
3198                                  _VSTD::forward<_Args>(__args)...)))
3199    -> decltype(      _Op::__call(_VSTD::get<_Idxs>(_VSTD::move(__bound_))...,
3200                                  _VSTD::forward<_Args>(__args)...))
3201    {return           _Op::__call(_VSTD::get<_Idxs>(_VSTD::move(__bound_))...,
3202                                  _VSTD::forward<_Args>(__args)...);}
3203
3204    template<class... _Args>
3205    _LIBCPP_INLINE_VISIBILITY constexpr auto operator()(_Args&&... __args) const&&
3206    noexcept(noexcept(_Op::__call(_VSTD::get<_Idxs>(_VSTD::move(__bound_))...,
3207                                  _VSTD::forward<_Args>(__args)...)))
3208    -> decltype(      _Op::__call(_VSTD::get<_Idxs>(_VSTD::move(__bound_))...,
3209                                  _VSTD::forward<_Args>(__args)...))
3210    {return           _Op::__call(_VSTD::get<_Idxs>(_VSTD::move(__bound_))...,
3211                                  _VSTD::forward<_Args>(__args)...);}
3212
3213    template<class _Fn = typename tuple_element<0, tuple<_Bound...>>::type,
3214             class = _EnableIf<is_copy_constructible_v<_Fn>>>
3215    constexpr __perfect_forward_impl(__perfect_forward_impl const& __other)
3216        : __bound_(__other.__bound_) {}
3217
3218    template<class _Fn = typename tuple_element<0, tuple<_Bound...>>::type,
3219             class = _EnableIf<is_move_constructible_v<_Fn>>>
3220    constexpr __perfect_forward_impl(__perfect_forward_impl && __other)
3221        : __bound_(_VSTD::move(__other.__bound_)) {}
3222
3223    template<class... _BoundArgs>
3224    explicit constexpr __perfect_forward_impl(_BoundArgs&&... __bound) :
3225        __bound_(_VSTD::forward<_BoundArgs>(__bound)...) { }
3226};
3227
3228template<class _Op, class... _Args>
3229using __perfect_forward =
3230    __perfect_forward_impl<_Op, __tuple_types<decay_t<_Args>...>>;
3231
3232struct __not_fn_op
3233{
3234    template<class... _Args>
3235    static _LIBCPP_CONSTEXPR_AFTER_CXX17 auto __call(_Args&&... __args)
3236    noexcept(noexcept(!_VSTD::invoke(_VSTD::forward<_Args>(__args)...)))
3237    -> decltype(      !_VSTD::invoke(_VSTD::forward<_Args>(__args)...))
3238    { return          !_VSTD::invoke(_VSTD::forward<_Args>(__args)...); }
3239};
3240
3241template<class _Fn,
3242         class = _EnableIf<is_constructible_v<decay_t<_Fn>, _Fn> &&
3243                           is_move_constructible_v<_Fn>>>
3244_LIBCPP_CONSTEXPR_AFTER_CXX17 auto not_fn(_Fn&& __f)
3245{
3246    return __perfect_forward<__not_fn_op, _Fn>(_VSTD::forward<_Fn>(__f));
3247}
3248
3249#endif // _LIBCPP_STD_VER > 14
3250
3251#if _LIBCPP_STD_VER > 17
3252
3253struct __bind_front_op
3254{
3255    template<class... _Args>
3256    constexpr static auto __call(_Args&&... __args)
3257    noexcept(noexcept(_VSTD::invoke(_VSTD::forward<_Args>(__args)...)))
3258    -> decltype(      _VSTD::invoke(_VSTD::forward<_Args>(__args)...))
3259    { return          _VSTD::invoke(_VSTD::forward<_Args>(__args)...); }
3260};
3261
3262template<class _Fn, class... _Args,
3263         class = _EnableIf<conjunction<is_constructible<decay_t<_Fn>, _Fn>,
3264                                       is_move_constructible<decay_t<_Fn>>,
3265                                       is_constructible<decay_t<_Args>, _Args>...,
3266                                       is_move_constructible<decay_t<_Args>>...
3267                                       >::value>>
3268constexpr auto bind_front(_Fn&& __f, _Args&&... __args)
3269{
3270    return __perfect_forward<__bind_front_op, _Fn, _Args...>(_VSTD::forward<_Fn>(__f),
3271                                                             _VSTD::forward<_Args>(__args)...);
3272}
3273
3274#endif // _LIBCPP_STD_VER > 17
3275
3276// struct hash<T*> in <memory>
3277
3278template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>
3279pair<_ForwardIterator1, _ForwardIterator1> _LIBCPP_CONSTEXPR_AFTER_CXX11
3280__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3281         _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred,
3282         forward_iterator_tag, forward_iterator_tag)
3283{
3284    if (__first2 == __last2)
3285        return _VSTD::make_pair(__first1, __first1);  // Everything matches an empty sequence
3286    while (true)
3287    {
3288        // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks
3289        while (true)
3290        {
3291            if (__first1 == __last1)  // return __last1 if no element matches *__first2
3292                return _VSTD::make_pair(__last1, __last1);
3293            if (__pred(*__first1, *__first2))
3294                break;
3295            ++__first1;
3296        }
3297        // *__first1 matches *__first2, now match elements after here
3298        _ForwardIterator1 __m1 = __first1;
3299        _ForwardIterator2 __m2 = __first2;
3300        while (true)
3301        {
3302            if (++__m2 == __last2)  // If pattern exhausted, __first1 is the answer (works for 1 element pattern)
3303                return _VSTD::make_pair(__first1, __m1);
3304            if (++__m1 == __last1)  // Otherwise if source exhaused, pattern not found
3305                return _VSTD::make_pair(__last1, __last1);
3306            if (!__pred(*__m1, *__m2))  // if there is a mismatch, restart with a new __first1
3307            {
3308                ++__first1;
3309                break;
3310            }  // else there is a match, check next elements
3311        }
3312    }
3313}
3314
3315template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
3316_LIBCPP_CONSTEXPR_AFTER_CXX11
3317pair<_RandomAccessIterator1, _RandomAccessIterator1>
3318__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
3319         _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred,
3320           random_access_iterator_tag, random_access_iterator_tag)
3321{
3322    typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
3323    typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
3324    // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
3325    const _D2 __len2 = __last2 - __first2;
3326    if (__len2 == 0)
3327        return _VSTD::make_pair(__first1, __first1);
3328    const _D1 __len1 = __last1 - __first1;
3329    if (__len1 < __len2)
3330        return _VSTD::make_pair(__last1, __last1);
3331    const _RandomAccessIterator1 __s = __last1 - (__len2 - 1);  // Start of pattern match can't go beyond here
3332
3333    while (true)
3334    {
3335        while (true)
3336        {
3337            if (__first1 == __s)
3338                return _VSTD::make_pair(__last1, __last1);
3339            if (__pred(*__first1, *__first2))
3340                break;
3341            ++__first1;
3342        }
3343
3344        _RandomAccessIterator1 __m1 = __first1;
3345        _RandomAccessIterator2 __m2 = __first2;
3346         while (true)
3347         {
3348             if (++__m2 == __last2)
3349                 return _VSTD::make_pair(__first1, __first1 + __len2);
3350             ++__m1;          // no need to check range on __m1 because __s guarantees we have enough source
3351             if (!__pred(*__m1, *__m2))
3352             {
3353                 ++__first1;
3354                 break;
3355             }
3356         }
3357    }
3358}
3359
3360#if _LIBCPP_STD_VER > 14
3361
3362// default searcher
3363template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
3364class _LIBCPP_TEMPLATE_VIS default_searcher {
3365public:
3366    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3367    default_searcher(_ForwardIterator __f, _ForwardIterator __l,
3368                       _BinaryPredicate __p = _BinaryPredicate())
3369        : __first_(__f), __last_(__l), __pred_(__p) {}
3370
3371    template <typename _ForwardIterator2>
3372    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
3373    pair<_ForwardIterator2, _ForwardIterator2>
3374    operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const
3375    {
3376        return _VSTD::__search(__f, __l, __first_, __last_, __pred_,
3377            typename iterator_traits<_ForwardIterator>::iterator_category(),
3378            typename iterator_traits<_ForwardIterator2>::iterator_category());
3379    }
3380
3381private:
3382    _ForwardIterator __first_;
3383    _ForwardIterator __last_;
3384    _BinaryPredicate __pred_;
3385    };
3386
3387#endif // _LIBCPP_STD_VER > 14
3388
3389#if _LIBCPP_STD_VER > 17
3390template <class _Tp>
3391using unwrap_reference_t = typename unwrap_reference<_Tp>::type;
3392
3393template <class _Tp>
3394using unwrap_ref_decay_t = typename unwrap_ref_decay<_Tp>::type;
3395#endif // > C++17
3396
3397#if _LIBCPP_STD_VER > 17
3398// [func.identity]
3399struct identity {
3400    template<class _Tp>
3401    _LIBCPP_NODISCARD_EXT constexpr _Tp&& operator()(_Tp&& __t) const noexcept
3402    {
3403        return _VSTD::forward<_Tp>(__t);
3404    }
3405
3406    using is_transparent = void;
3407};
3408#endif // _LIBCPP_STD_VER > 17
3409
3410#if !defined(_LIBCPP_HAS_NO_RANGES)
3411
3412namespace ranges {
3413
3414struct equal_to {
3415  template <class _Tp, class _Up>
3416  requires equality_comparable_with<_Tp, _Up>
3417  [[nodiscard]] constexpr bool operator()(_Tp &&__t, _Up &&__u) const
3418      noexcept(noexcept(bool(_VSTD::forward<_Tp>(__t) == _VSTD::forward<_Up>(__u)))) {
3419    return _VSTD::forward<_Tp>(__t) == _VSTD::forward<_Up>(__u);
3420  }
3421
3422  using is_transparent = void;
3423};
3424
3425struct not_equal_to {
3426  template <class _Tp, class _Up>
3427  requires equality_comparable_with<_Tp, _Up>
3428  [[nodiscard]] constexpr bool operator()(_Tp &&__t, _Up &&__u) const
3429      noexcept(noexcept(bool(!(_VSTD::forward<_Tp>(__t) == _VSTD::forward<_Up>(__u))))) {
3430    return !(_VSTD::forward<_Tp>(__t) == _VSTD::forward<_Up>(__u));
3431  }
3432
3433  using is_transparent = void;
3434};
3435
3436struct greater {
3437  template <class _Tp, class _Up>
3438  requires totally_ordered_with<_Tp, _Up>
3439  [[nodiscard]] constexpr bool operator()(_Tp &&__t, _Up &&__u) const
3440      noexcept(noexcept(bool(_VSTD::forward<_Up>(__u) < _VSTD::forward<_Tp>(__t)))) {
3441    return _VSTD::forward<_Up>(__u) < _VSTD::forward<_Tp>(__t);
3442  }
3443
3444  using is_transparent = void;
3445};
3446
3447struct less {
3448  template <class _Tp, class _Up>
3449  requires totally_ordered_with<_Tp, _Up>
3450  [[nodiscard]] constexpr bool operator()(_Tp &&__t, _Up &&__u) const
3451      noexcept(noexcept(bool(_VSTD::forward<_Tp>(__t) < _VSTD::forward<_Up>(__u)))) {
3452    return _VSTD::forward<_Tp>(__t) < _VSTD::forward<_Up>(__u);
3453  }
3454
3455  using is_transparent = void;
3456};
3457
3458struct greater_equal {
3459  template <class _Tp, class _Up>
3460  requires totally_ordered_with<_Tp, _Up>
3461  [[nodiscard]] constexpr bool operator()(_Tp &&__t, _Up &&__u) const
3462      noexcept(noexcept(bool(!(_VSTD::forward<_Tp>(__t) < _VSTD::forward<_Up>(__u))))) {
3463    return !(_VSTD::forward<_Tp>(__t) < _VSTD::forward<_Up>(__u));
3464  }
3465
3466  using is_transparent = void;
3467};
3468
3469struct less_equal {
3470  template <class _Tp, class _Up>
3471  requires totally_ordered_with<_Tp, _Up>
3472  [[nodiscard]] constexpr bool operator()(_Tp &&__t, _Up &&__u) const
3473      noexcept(noexcept(bool(!(_VSTD::forward<_Up>(__u) < _VSTD::forward<_Tp>(__t))))) {
3474    return !(_VSTD::forward<_Up>(__u) < _VSTD::forward<_Tp>(__t));
3475  }
3476
3477  using is_transparent = void;
3478};
3479
3480} // namespace ranges
3481
3482#endif // !defined(_LIBCPP_HAS_NO_RANGES)
3483
3484_LIBCPP_END_NAMESPACE_STD
3485
3486#endif // _LIBCPP_FUNCTIONAL
3487