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