contrib/libc++/include/functional

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