contrib/llvm-project/libcxx/include/functional

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