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