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