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