contrib/gcc-8.0/libstdc++-v3/include/std/functional

   1 // <functional> -*- C++ -*-
   2
   3 // Copyright (C) 2001-2018 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /*
  26  * Copyright (c) 1997
  27  * Silicon Graphics Computer Systems, Inc.
  28  *
  29  * Permission to use, copy, modify, distribute and sell this software
  30  * and its documentation for any purpose is hereby granted without fee,
  31  * provided that the above copyright notice appear in all copies and
  32  * that both that copyright notice and this permission notice appear
  33  * in supporting documentation.  Silicon Graphics makes no
  34  * representations about the suitability of this software for any
  35  * purpose.  It is provided "as is" without express or implied warranty.
  36  *
  37  */
  38
  39 /** @file include/functional
  40  *  This is a Standard C++ Library header.
  41  */
  42
  43 #ifndef _GLIBCXX_FUNCTIONAL
  44 #define _GLIBCXX_FUNCTIONAL 1
  45
  46 #pragma GCC system_header
  47
  48 #include <bits/c++config.h>
  49 #include <bits/stl_function.h>
  50
  51 #if __cplusplus >= 201103L
  52
  53 #include <new>
  54 #include <tuple>
  55 #include <type_traits>
  56 #include <bits/functional_hash.h>
  57 #include <bits/invoke.h>
  58 #include <bits/refwrap.h>       // std::reference_wrapper and _Mem_fn_traits
  59 #include <bits/std_function.h>  // std::function
  60 #if __cplusplus > 201402L
  61 # include <unordered_map>
  62 # include <vector>
  63 # include <array>
  64 # include <utility>
  65 # include <bits/stl_algo.h>
  66 #endif
  67
  68 namespace std _GLIBCXX_VISIBILITY(default)
  69 {
  70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  71
  72 #if __cplusplus > 201402L
  73 # define __cpp_lib_invoke 201411
  74
  75   /// Invoke a callable object.
  76   template<typename _Callable, typename... _Args>
  77     inline invoke_result_t<_Callable, _Args...>
  78     invoke(_Callable&& __fn, _Args&&... __args)
  79     noexcept(is_nothrow_invocable_v<_Callable, _Args...>)
  80     {
  81       return std::__invoke(std::forward<_Callable>(__fn),
  82                            std::forward<_Args>(__args)...);
  83     }
  84 #endif
  85
  86   template<typename _MemFunPtr,
  87            bool __is_mem_fn = is_member_function_pointer<_MemFunPtr>::value>
  88     class _Mem_fn_base
  89     : public _Mem_fn_traits<_MemFunPtr>::__maybe_type
  90     {
  91       using _Traits = _Mem_fn_traits<_MemFunPtr>;
  92
  93       using _Arity = typename _Traits::__arity;
  94       using _Varargs = typename _Traits::__vararg;
  95
  96       template<typename _Func, typename... _BoundArgs>
  97         friend struct _Bind_check_arity;
  98
  99       _MemFunPtr _M_pmf;
 100
 101     public:
 102
 103       using result_type = typename _Traits::__result_type;
 104
 105       explicit constexpr
 106       _Mem_fn_base(_MemFunPtr __pmf) noexcept : _M_pmf(__pmf) { }
 107
 108       template<typename... _Args>
 109         auto
 110         operator()(_Args&&... __args) const
 111         noexcept(noexcept(
 112               std::__invoke(_M_pmf, std::forward<_Args>(__args)...)))
 113         -> decltype(std::__invoke(_M_pmf, std::forward<_Args>(__args)...))
 114         { return std::__invoke(_M_pmf, std::forward<_Args>(__args)...); }
 115     };
 116
 117   // Partial specialization for member object pointers.
 118   template<typename _MemObjPtr>
 119     class _Mem_fn_base<_MemObjPtr, false>
 120     {
 121       using _Arity = integral_constant<size_t, 0>;
 122       using _Varargs = false_type;
 123
 124       template<typename _Func, typename... _BoundArgs>
 125         friend struct _Bind_check_arity;
 126
 127       _MemObjPtr _M_pm;
 128
 129     public:
 130       explicit constexpr
 131       _Mem_fn_base(_MemObjPtr __pm) noexcept : _M_pm(__pm) { }
 132
 133       template<typename _Tp>
 134         auto
 135         operator()(_Tp&& __obj) const
 136         noexcept(noexcept(std::__invoke(_M_pm, std::forward<_Tp>(__obj))))
 137         -> decltype(std::__invoke(_M_pm, std::forward<_Tp>(__obj)))
 138         { return std::__invoke(_M_pm, std::forward<_Tp>(__obj)); }
 139     };
 140
 141   template<typename _MemberPointer>
 142     struct _Mem_fn; // undefined
 143
 144   template<typename _Res, typename _Class>
 145     struct _Mem_fn<_Res _Class::*>
 146     : _Mem_fn_base<_Res _Class::*>
 147     {
 148       using _Mem_fn_base<_Res _Class::*>::_Mem_fn_base;
 149     };
 150
 151   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 152   // 2048.  Unnecessary mem_fn overloads
 153   /**
 154    *  @brief Returns a function object that forwards to the member
 155    *  pointer @a pm.
 156    *  @ingroup functors
 157    */
 158   template<typename _Tp, typename _Class>
 159     inline _Mem_fn<_Tp _Class::*>
 160     mem_fn(_Tp _Class::* __pm) noexcept
 161     {
 162       return _Mem_fn<_Tp _Class::*>(__pm);
 163     }
 164
 165   /**
 166    *  @brief Determines if the given type _Tp is a function object that
 167    *  should be treated as a subexpression when evaluating calls to
 168    *  function objects returned by bind().
 169    *
 170    *  C++11 [func.bind.isbind].
 171    *  @ingroup binders
 172    */
 173   template<typename _Tp>
 174     struct is_bind_expression
 175     : public false_type { };
 176
 177   /**
 178    *  @brief Determines if the given type _Tp is a placeholder in a
 179    *  bind() expression and, if so, which placeholder it is.
 180    *
 181    *  C++11 [func.bind.isplace].
 182    *  @ingroup binders
 183    */
 184   template<typename _Tp>
 185     struct is_placeholder
 186     : public integral_constant<int, 0>
 187     { };
 188
 189 #if __cplusplus > 201402L
 190   template <typename _Tp> inline constexpr bool is_bind_expression_v
 191     = is_bind_expression<_Tp>::value;
 192   template <typename _Tp> inline constexpr int is_placeholder_v
 193     = is_placeholder<_Tp>::value;
 194 #endif // C++17
 195
 196   /** @brief The type of placeholder objects defined by libstdc++.
 197    *  @ingroup binders
 198    */
 199   template<int _Num> struct _Placeholder { };
 200
 201   /** @namespace std::placeholders
 202    *  @brief ISO C++11 entities sub-namespace for functional.
 203    *  @ingroup binders
 204    */
 205   namespace placeholders
 206   {
 207   /* Define a large number of placeholders. There is no way to
 208    * simplify this with variadic templates, because we're introducing
 209    * unique names for each.
 210    */
 211     extern const _Placeholder<1> _1;
 212     extern const _Placeholder<2> _2;
 213     extern const _Placeholder<3> _3;
 214     extern const _Placeholder<4> _4;
 215     extern const _Placeholder<5> _5;
 216     extern const _Placeholder<6> _6;
 217     extern const _Placeholder<7> _7;
 218     extern const _Placeholder<8> _8;
 219     extern const _Placeholder<9> _9;
 220     extern const _Placeholder<10> _10;
 221     extern const _Placeholder<11> _11;
 222     extern const _Placeholder<12> _12;
 223     extern const _Placeholder<13> _13;
 224     extern const _Placeholder<14> _14;
 225     extern const _Placeholder<15> _15;
 226     extern const _Placeholder<16> _16;
 227     extern const _Placeholder<17> _17;
 228     extern const _Placeholder<18> _18;
 229     extern const _Placeholder<19> _19;
 230     extern const _Placeholder<20> _20;
 231     extern const _Placeholder<21> _21;
 232     extern const _Placeholder<22> _22;
 233     extern const _Placeholder<23> _23;
 234     extern const _Placeholder<24> _24;
 235     extern const _Placeholder<25> _25;
 236     extern const _Placeholder<26> _26;
 237     extern const _Placeholder<27> _27;
 238     extern const _Placeholder<28> _28;
 239     extern const _Placeholder<29> _29;
 240   }
 241
 242   /**
 243    *  Partial specialization of is_placeholder that provides the placeholder
 244    *  number for the placeholder objects defined by libstdc++.
 245    *  @ingroup binders
 246    */
 247   template<int _Num>
 248     struct is_placeholder<_Placeholder<_Num> >
 249     : public integral_constant<int, _Num>
 250     { };
 251
 252   template<int _Num>
 253     struct is_placeholder<const _Placeholder<_Num> >
 254     : public integral_constant<int, _Num>
 255     { };
 256
 257
 258   // Like tuple_element_t but SFINAE-friendly.
 259   template<std::size_t __i, typename _Tuple>
 260     using _Safe_tuple_element_t
 261       = typename enable_if<(__i < tuple_size<_Tuple>::value),
 262                            tuple_element<__i, _Tuple>>::type::type;
 263
 264   /**
 265    *  Maps an argument to bind() into an actual argument to the bound
 266    *  function object [func.bind.bind]/10. Only the first parameter should
 267    *  be specified: the rest are used to determine among the various
 268    *  implementations. Note that, although this class is a function
 269    *  object, it isn't entirely normal because it takes only two
 270    *  parameters regardless of the number of parameters passed to the
 271    *  bind expression. The first parameter is the bound argument and
 272    *  the second parameter is a tuple containing references to the
 273    *  rest of the arguments.
 274    */
 275   template<typename _Arg,
 276            bool _IsBindExp = is_bind_expression<_Arg>::value,
 277            bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>
 278     class _Mu;
 279
 280   /**
 281    *  If the argument is reference_wrapper<_Tp>, returns the
 282    *  underlying reference.
 283    *  C++11 [func.bind.bind] p10 bullet 1.
 284    */
 285   template<typename _Tp>
 286     class _Mu<reference_wrapper<_Tp>, false, false>
 287     {
 288     public:
 289       /* Note: This won't actually work for const volatile
 290        * reference_wrappers, because reference_wrapper::get() is const
 291        * but not volatile-qualified. This might be a defect in the TR.
 292        */
 293       template<typename _CVRef, typename _Tuple>
 294         _Tp&
 295         operator()(_CVRef& __arg, _Tuple&) const volatile
 296         { return __arg.get(); }
 297     };
 298
 299   /**
 300    *  If the argument is a bind expression, we invoke the underlying
 301    *  function object with the same cv-qualifiers as we are given and
 302    *  pass along all of our arguments (unwrapped).
 303    *  C++11 [func.bind.bind] p10 bullet 2.
 304    */
 305   template<typename _Arg>
 306     class _Mu<_Arg, true, false>
 307     {
 308     public:
 309       template<typename _CVArg, typename... _Args>
 310         auto
 311         operator()(_CVArg& __arg,
 312                    tuple<_Args...>& __tuple) const volatile
 313         -> decltype(__arg(declval<_Args>()...))
 314         {
 315           // Construct an index tuple and forward to __call
 316           typedef typename _Build_index_tuple<sizeof...(_Args)>::__type
 317             _Indexes;
 318           return this->__call(__arg, __tuple, _Indexes());
 319         }
 320
 321     private:
 322       // Invokes the underlying function object __arg by unpacking all
 323       // of the arguments in the tuple.
 324       template<typename _CVArg, typename... _Args, std::size_t... _Indexes>
 325         auto
 326         __call(_CVArg& __arg, tuple<_Args...>& __tuple,
 327                const _Index_tuple<_Indexes...>&) const volatile
 328         -> decltype(__arg(declval<_Args>()...))
 329         {
 330           return __arg(std::get<_Indexes>(std::move(__tuple))...);
 331         }
 332     };
 333
 334   /**
 335    *  If the argument is a placeholder for the Nth argument, returns
 336    *  a reference to the Nth argument to the bind function object.
 337    *  C++11 [func.bind.bind] p10 bullet 3.
 338    */
 339   template<typename _Arg>
 340     class _Mu<_Arg, false, true>
 341     {
 342     public:
 343       template<typename _Tuple>
 344         _Safe_tuple_element_t<(is_placeholder<_Arg>::value - 1), _Tuple>&&
 345         operator()(const volatile _Arg&, _Tuple& __tuple) const volatile
 346         {
 347           return
 348             ::std::get<(is_placeholder<_Arg>::value - 1)>(std::move(__tuple));
 349         }
 350     };
 351
 352   /**
 353    *  If the argument is just a value, returns a reference to that
 354    *  value. The cv-qualifiers on the reference are determined by the caller.
 355    *  C++11 [func.bind.bind] p10 bullet 4.
 356    */
 357   template<typename _Arg>
 358     class _Mu<_Arg, false, false>
 359     {
 360     public:
 361       template<typename _CVArg, typename _Tuple>
 362         _CVArg&&
 363         operator()(_CVArg&& __arg, _Tuple&) const volatile
 364         { return std::forward<_CVArg>(__arg); }
 365     };
 366
 367   // std::get<I> for volatile-qualified tuples
 368   template<std::size_t _Ind, typename... _Tp>
 369     inline auto
 370     __volget(volatile tuple<_Tp...>& __tuple)
 371     -> __tuple_element_t<_Ind, tuple<_Tp...>> volatile&
 372     { return std::get<_Ind>(const_cast<tuple<_Tp...>&>(__tuple)); }
 373
 374   // std::get<I> for const-volatile-qualified tuples
 375   template<std::size_t _Ind, typename... _Tp>
 376     inline auto
 377     __volget(const volatile tuple<_Tp...>& __tuple)
 378     -> __tuple_element_t<_Ind, tuple<_Tp...>> const volatile&
 379     { return std::get<_Ind>(const_cast<const tuple<_Tp...>&>(__tuple)); }
 380
 381   /// Type of the function object returned from bind().
 382   template<typename _Signature>
 383     struct _Bind;
 384
 385    template<typename _Functor, typename... _Bound_args>
 386     class _Bind<_Functor(_Bound_args...)>
 387     : public _Weak_result_type<_Functor>
 388     {
 389       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
 390         _Bound_indexes;
 391
 392       _Functor _M_f;
 393       tuple<_Bound_args...> _M_bound_args;
 394
 395       // Call unqualified
 396       template<typename _Result, typename... _Args, std::size_t... _Indexes>
 397         _Result
 398         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
 399         {
 400           return std::__invoke(_M_f,
 401               _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
 402               );
 403         }
 404
 405       // Call as const
 406       template<typename _Result, typename... _Args, std::size_t... _Indexes>
 407         _Result
 408         __call_c(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
 409         {
 410           return std::__invoke(_M_f,
 411               _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
 412               );
 413         }
 414
 415       // Call as volatile
 416       template<typename _Result, typename... _Args, std::size_t... _Indexes>
 417         _Result
 418         __call_v(tuple<_Args...>&& __args,
 419                  _Index_tuple<_Indexes...>) volatile
 420         {
 421           return std::__invoke(_M_f,
 422               _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
 423               );
 424         }
 425
 426       // Call as const volatile
 427       template<typename _Result, typename... _Args, std::size_t... _Indexes>
 428         _Result
 429         __call_c_v(tuple<_Args...>&& __args,
 430                    _Index_tuple<_Indexes...>) const volatile
 431         {
 432           return std::__invoke(_M_f,
 433               _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
 434               );
 435         }
 436
 437       template<typename _BoundArg, typename _CallArgs>
 438         using _Mu_type = decltype(
 439             _Mu<typename remove_cv<_BoundArg>::type>()(
 440               std::declval<_BoundArg&>(), std::declval<_CallArgs&>()) );
 441
 442       template<typename _Fn, typename _CallArgs, typename... _BArgs>
 443         using _Res_type_impl
 444           = typename result_of< _Fn&(_Mu_type<_BArgs, _CallArgs>&&...) >::type;
 445
 446       template<typename _CallArgs>
 447         using _Res_type = _Res_type_impl<_Functor, _CallArgs, _Bound_args...>;
 448
 449       template<typename _CallArgs>
 450         using __dependent = typename
 451           enable_if<bool(tuple_size<_CallArgs>::value+1), _Functor>::type;
 452
 453       template<typename _CallArgs, template<class> class __cv_quals>
 454         using _Res_type_cv = _Res_type_impl<
 455           typename __cv_quals<__dependent<_CallArgs>>::type,
 456           _CallArgs,
 457           typename __cv_quals<_Bound_args>::type...>;
 458
 459      public:
 460       template<typename... _Args>
 461         explicit _Bind(const _Functor& __f, _Args&&... __args)
 462         : _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)
 463         { }
 464
 465       template<typename... _Args>
 466         explicit _Bind(_Functor&& __f, _Args&&... __args)
 467         : _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)
 468         { }
 469
 470       _Bind(const _Bind&) = default;
 471
 472       _Bind(_Bind&& __b)
 473       : _M_f(std::move(__b._M_f)), _M_bound_args(std::move(__b._M_bound_args))
 474       { }
 475
 476       // Call unqualified
 477       template<typename... _Args,
 478                typename _Result = _Res_type<tuple<_Args...>>>
 479         _Result
 480         operator()(_Args&&... __args)
 481         {
 482           return this->__call<_Result>(
 483               std::forward_as_tuple(std::forward<_Args>(__args)...),
 484               _Bound_indexes());
 485         }
 486
 487       // Call as const
 488       template<typename... _Args,
 489                typename _Result = _Res_type_cv<tuple<_Args...>, add_const>>
 490         _Result
 491         operator()(_Args&&... __args) const
 492         {
 493           return this->__call_c<_Result>(
 494               std::forward_as_tuple(std::forward<_Args>(__args)...),
 495               _Bound_indexes());
 496         }
 497
 498 #if __cplusplus > 201402L
 499 # define _GLIBCXX_DEPR_BIND \
 500       [[deprecated("std::bind does not support volatile in C++17")]]
 501 #else
 502 # define _GLIBCXX_DEPR_BIND
 503 #endif
 504       // Call as volatile
 505       template<typename... _Args,
 506                typename _Result = _Res_type_cv<tuple<_Args...>, add_volatile>>
 507         _GLIBCXX_DEPR_BIND
 508         _Result
 509         operator()(_Args&&... __args) volatile
 510         {
 511           return this->__call_v<_Result>(
 512               std::forward_as_tuple(std::forward<_Args>(__args)...),
 513               _Bound_indexes());
 514         }
 515
 516       // Call as const volatile
 517       template<typename... _Args,
 518                typename _Result = _Res_type_cv<tuple<_Args...>, add_cv>>
 519         _GLIBCXX_DEPR_BIND
 520         _Result
 521         operator()(_Args&&... __args) const volatile
 522         {
 523           return this->__call_c_v<_Result>(
 524               std::forward_as_tuple(std::forward<_Args>(__args)...),
 525               _Bound_indexes());
 526         }
 527     };
 528
 529   /// Type of the function object returned from bind<R>().
 530   template<typename _Result, typename _Signature>
 531     struct _Bind_result;
 532
 533   template<typename _Result, typename _Functor, typename... _Bound_args>
 534     class _Bind_result<_Result, _Functor(_Bound_args...)>
 535     {
 536       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
 537         _Bound_indexes;
 538
 539       _Functor _M_f;
 540       tuple<_Bound_args...> _M_bound_args;
 541
 542       // sfinae types
 543       template<typename _Res>
 544         using __enable_if_void
 545           = typename enable_if<is_void<_Res>{}>::type;
 546
 547       template<typename _Res>
 548         using __disable_if_void
 549           = typename enable_if<!is_void<_Res>{}, _Result>::type;
 550
 551       // Call unqualified
 552       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 553         __disable_if_void<_Res>
 554         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
 555         {
 556           return std::__invoke(_M_f, _Mu<_Bound_args>()
 557                       (std::get<_Indexes>(_M_bound_args), __args)...);
 558         }
 559
 560       // Call unqualified, return void
 561       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 562         __enable_if_void<_Res>
 563         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
 564         {
 565           std::__invoke(_M_f, _Mu<_Bound_args>()
 566                (std::get<_Indexes>(_M_bound_args), __args)...);
 567         }
 568
 569       // Call as const
 570       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 571         __disable_if_void<_Res>
 572         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
 573         {
 574           return std::__invoke(_M_f, _Mu<_Bound_args>()
 575                       (std::get<_Indexes>(_M_bound_args), __args)...);
 576         }
 577
 578       // Call as const, return void
 579       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 580         __enable_if_void<_Res>
 581         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
 582         {
 583           std::__invoke(_M_f, _Mu<_Bound_args>()
 584                (std::get<_Indexes>(_M_bound_args),  __args)...);
 585         }
 586
 587       // Call as volatile
 588       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 589         __disable_if_void<_Res>
 590         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) volatile
 591         {
 592           return std::__invoke(_M_f, _Mu<_Bound_args>()
 593                       (__volget<_Indexes>(_M_bound_args), __args)...);
 594         }
 595
 596       // Call as volatile, return void
 597       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 598         __enable_if_void<_Res>
 599         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) volatile
 600         {
 601           std::__invoke(_M_f, _Mu<_Bound_args>()
 602                (__volget<_Indexes>(_M_bound_args), __args)...);
 603         }
 604
 605       // Call as const volatile
 606       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 607         __disable_if_void<_Res>
 608         __call(tuple<_Args...>&& __args,
 609                _Index_tuple<_Indexes...>) const volatile
 610         {
 611           return std::__invoke(_M_f, _Mu<_Bound_args>()
 612                       (__volget<_Indexes>(_M_bound_args), __args)...);
 613         }
 614
 615       // Call as const volatile, return void
 616       template<typename _Res, typename... _Args, std::size_t... _Indexes>
 617         __enable_if_void<_Res>
 618         __call(tuple<_Args...>&& __args,
 619                _Index_tuple<_Indexes...>) const volatile
 620         {
 621           std::__invoke(_M_f, _Mu<_Bound_args>()
 622                (__volget<_Indexes>(_M_bound_args), __args)...);
 623         }
 624
 625     public:
 626       typedef _Result result_type;
 627
 628       template<typename... _Args>
 629         explicit _Bind_result(const _Functor& __f, _Args&&... __args)
 630         : _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)
 631         { }
 632
 633       template<typename... _Args>
 634         explicit _Bind_result(_Functor&& __f, _Args&&... __args)
 635         : _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)
 636         { }
 637
 638       _Bind_result(const _Bind_result&) = default;
 639
 640       _Bind_result(_Bind_result&& __b)
 641       : _M_f(std::move(__b._M_f)), _M_bound_args(std::move(__b._M_bound_args))
 642       { }
 643
 644       // Call unqualified
 645       template<typename... _Args>
 646         result_type
 647         operator()(_Args&&... __args)
 648         {
 649           return this->__call<_Result>(
 650               std::forward_as_tuple(std::forward<_Args>(__args)...),
 651               _Bound_indexes());
 652         }
 653
 654       // Call as const
 655       template<typename... _Args>
 656         result_type
 657         operator()(_Args&&... __args) const
 658         {
 659           return this->__call<_Result>(
 660               std::forward_as_tuple(std::forward<_Args>(__args)...),
 661               _Bound_indexes());
 662         }
 663
 664       // Call as volatile
 665       template<typename... _Args>
 666         _GLIBCXX_DEPR_BIND
 667         result_type
 668         operator()(_Args&&... __args) volatile
 669         {
 670           return this->__call<_Result>(
 671               std::forward_as_tuple(std::forward<_Args>(__args)...),
 672               _Bound_indexes());
 673         }
 674
 675       // Call as const volatile
 676       template<typename... _Args>
 677         _GLIBCXX_DEPR_BIND
 678         result_type
 679         operator()(_Args&&... __args) const volatile
 680         {
 681           return this->__call<_Result>(
 682               std::forward_as_tuple(std::forward<_Args>(__args)...),
 683               _Bound_indexes());
 684         }
 685     };
 686 #undef _GLIBCXX_DEPR_BIND
 687
 688   /**
 689    *  @brief Class template _Bind is always a bind expression.
 690    *  @ingroup binders
 691    */
 692   template<typename _Signature>
 693     struct is_bind_expression<_Bind<_Signature> >
 694     : public true_type { };
 695
 696   /**
 697    *  @brief Class template _Bind is always a bind expression.
 698    *  @ingroup binders
 699    */
 700   template<typename _Signature>
 701     struct is_bind_expression<const _Bind<_Signature> >
 702     : public true_type { };
 703
 704   /**
 705    *  @brief Class template _Bind is always a bind expression.
 706    *  @ingroup binders
 707    */
 708   template<typename _Signature>
 709     struct is_bind_expression<volatile _Bind<_Signature> >
 710     : public true_type { };
 711
 712   /**
 713    *  @brief Class template _Bind is always a bind expression.
 714    *  @ingroup binders
 715    */
 716   template<typename _Signature>
 717     struct is_bind_expression<const volatile _Bind<_Signature>>
 718     : public true_type { };
 719
 720   /**
 721    *  @brief Class template _Bind_result is always a bind expression.
 722    *  @ingroup binders
 723    */
 724   template<typename _Result, typename _Signature>
 725     struct is_bind_expression<_Bind_result<_Result, _Signature>>
 726     : public true_type { };
 727
 728   /**
 729    *  @brief Class template _Bind_result is always a bind expression.
 730    *  @ingroup binders
 731    */
 732   template<typename _Result, typename _Signature>
 733     struct is_bind_expression<const _Bind_result<_Result, _Signature>>
 734     : public true_type { };
 735
 736   /**
 737    *  @brief Class template _Bind_result is always a bind expression.
 738    *  @ingroup binders
 739    */
 740   template<typename _Result, typename _Signature>
 741     struct is_bind_expression<volatile _Bind_result<_Result, _Signature>>
 742     : public true_type { };
 743
 744   /**
 745    *  @brief Class template _Bind_result is always a bind expression.
 746    *  @ingroup binders
 747    */
 748   template<typename _Result, typename _Signature>
 749     struct is_bind_expression<const volatile _Bind_result<_Result, _Signature>>
 750     : public true_type { };
 751
 752   template<typename _Func, typename... _BoundArgs>
 753     struct _Bind_check_arity { };
 754
 755   template<typename _Ret, typename... _Args, typename... _BoundArgs>
 756     struct _Bind_check_arity<_Ret (*)(_Args...), _BoundArgs...>
 757     {
 758       static_assert(sizeof...(_BoundArgs) == sizeof...(_Args),
 759                    "Wrong number of arguments for function");
 760     };
 761
 762   template<typename _Ret, typename... _Args, typename... _BoundArgs>
 763     struct _Bind_check_arity<_Ret (*)(_Args......), _BoundArgs...>
 764     {
 765       static_assert(sizeof...(_BoundArgs) >= sizeof...(_Args),
 766                    "Wrong number of arguments for function");
 767     };
 768
 769   template<typename _Tp, typename _Class, typename... _BoundArgs>
 770     struct _Bind_check_arity<_Tp _Class::*, _BoundArgs...>
 771     {
 772       using _Arity = typename _Mem_fn<_Tp _Class::*>::_Arity;
 773       using _Varargs = typename _Mem_fn<_Tp _Class::*>::_Varargs;
 774       static_assert(_Varargs::value
 775                     ? sizeof...(_BoundArgs) >= _Arity::value + 1
 776                     : sizeof...(_BoundArgs) == _Arity::value + 1,
 777                     "Wrong number of arguments for pointer-to-member");
 778     };
 779
 780   // Trait type used to remove std::bind() from overload set via SFINAE
 781   // when first argument has integer type, so that std::bind() will
 782   // not be a better match than ::bind() from the BSD Sockets API.
 783   template<typename _Tp, typename _Tp2 = typename decay<_Tp>::type>
 784     using __is_socketlike = __or_<is_integral<_Tp2>, is_enum<_Tp2>>;
 785
 786   template<bool _SocketLike, typename _Func, typename... _BoundArgs>
 787     struct _Bind_helper
 788     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>
 789     {
 790       typedef typename decay<_Func>::type __func_type;
 791       typedef _Bind<__func_type(typename decay<_BoundArgs>::type...)> type;
 792     };
 793
 794   // Partial specialization for is_socketlike == true, does not define
 795   // nested type so std::bind() will not participate in overload resolution
 796   // when the first argument might be a socket file descriptor.
 797   template<typename _Func, typename... _BoundArgs>
 798     struct _Bind_helper<true, _Func, _BoundArgs...>
 799     { };
 800
 801   /**
 802    *  @brief Function template for std::bind.
 803    *  @ingroup binders
 804    */
 805   template<typename _Func, typename... _BoundArgs>
 806     inline typename
 807     _Bind_helper<__is_socketlike<_Func>::value, _Func, _BoundArgs...>::type
 808     bind(_Func&& __f, _BoundArgs&&... __args)
 809     {
 810       typedef _Bind_helper<false, _Func, _BoundArgs...> __helper_type;
 811       return typename __helper_type::type(std::forward<_Func>(__f),
 812                                           std::forward<_BoundArgs>(__args)...);
 813     }
 814
 815   template<typename _Result, typename _Func, typename... _BoundArgs>
 816     struct _Bindres_helper
 817     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>
 818     {
 819       typedef typename decay<_Func>::type __functor_type;
 820       typedef _Bind_result<_Result,
 821                            __functor_type(typename decay<_BoundArgs>::type...)>
 822         type;
 823     };
 824
 825   /**
 826    *  @brief Function template for std::bind<R>.
 827    *  @ingroup binders
 828    */
 829   template<typename _Result, typename _Func, typename... _BoundArgs>
 830     inline
 831     typename _Bindres_helper<_Result, _Func, _BoundArgs...>::type
 832     bind(_Func&& __f, _BoundArgs&&... __args)
 833     {
 834       typedef _Bindres_helper<_Result, _Func, _BoundArgs...> __helper_type;
 835       return typename __helper_type::type(std::forward<_Func>(__f),
 836                                           std::forward<_BoundArgs>(__args)...);
 837     }
 838
 839 #if __cplusplus >= 201402L
 840   /// Generalized negator.
 841   template<typename _Fn>
 842     class _Not_fn
 843     {
 844       template<typename _Fn2, typename... _Args>
 845         using __inv_res_t = typename __invoke_result<_Fn2, _Args...>::type;
 846
 847       template<typename _Tp>
 848         static decltype(!std::declval<_Tp>())
 849         _S_not() noexcept(noexcept(!std::declval<_Tp>()));
 850
 851     public:
 852       template<typename _Fn2>
 853         _Not_fn(_Fn2&& __fn, int)
 854         : _M_fn(std::forward<_Fn2>(__fn)) { }
 855
 856       _Not_fn(const _Not_fn& __fn) = default;
 857       _Not_fn(_Not_fn&& __fn) = default;
 858       ~_Not_fn() = default;
 859
 860       // Macro to define operator() with given cv-qualifiers ref-qualifiers,
 861       // forwarding _M_fn and the function arguments with the same qualifiers,
 862       // and deducing the return type and exception-specification.
 863 #define _GLIBCXX_NOT_FN_CALL_OP( _QUALS )                               \
 864       template<typename... _Args>                                       \
 865         decltype(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>())           \
 866         operator()(_Args&&... __args) _QUALS                            \
 867         noexcept(noexcept(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>())) \
 868         {                                                               \
 869           return !std::__invoke(std::forward< _Fn _QUALS >(_M_fn),      \
 870                                 std::forward<_Args>(__args)...);        \
 871         }
 872       _GLIBCXX_NOT_FN_CALL_OP( & )
 873       _GLIBCXX_NOT_FN_CALL_OP( const & )
 874       _GLIBCXX_NOT_FN_CALL_OP( && )
 875       _GLIBCXX_NOT_FN_CALL_OP( const && )
 876 #undef _GLIBCXX_NOT_FN_CALL
 877
 878     private:
 879       _Fn _M_fn;
 880     };
 881
 882   template<typename _Tp, typename _Pred>
 883     struct __is_byte_like : false_type { };
 884
 885   template<typename _Tp>
 886     struct __is_byte_like<_Tp, equal_to<_Tp>>
 887     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
 888
 889   template<typename _Tp>
 890     struct __is_byte_like<_Tp, equal_to<void>>
 891     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
 892
 893 #if __cplusplus >= 201703L
 894   // Declare std::byte (full definition is in <cstddef>).
 895   enum class byte : unsigned char;
 896
 897   template<>
 898     struct __is_byte_like<byte, equal_to<byte>>
 899     : true_type { };
 900
 901   template<>
 902     struct __is_byte_like<byte, equal_to<void>>
 903     : true_type { };
 904
 905 #define __cpp_lib_not_fn 201603
 906   /// [func.not_fn] Function template not_fn
 907   template<typename _Fn>
 908     inline auto
 909     not_fn(_Fn&& __fn)
 910     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
 911     {
 912       return _Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
 913     }
 914
 915   // Searchers
 916 #define __cpp_lib_boyer_moore_searcher 201603
 917
 918   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
 919     class default_searcher
 920     {
 921     public:
 922       default_searcher(_ForwardIterator1 __pat_first,
 923                        _ForwardIterator1 __pat_last,
 924                        _BinaryPredicate __pred = _BinaryPredicate())
 925       : _M_m(__pat_first, __pat_last, std::move(__pred))
 926       { }
 927
 928       template<typename _ForwardIterator2>
 929         pair<_ForwardIterator2, _ForwardIterator2>
 930         operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
 931         {
 932           _ForwardIterator2 __first_ret =
 933             std::search(__first, __last, std::get<0>(_M_m), std::get<1>(_M_m),
 934                         std::get<2>(_M_m));
 935           auto __ret = std::make_pair(__first_ret, __first_ret);
 936           if (__ret.first != __last)
 937             std::advance(__ret.second, std::distance(std::get<0>(_M_m),
 938                                                      std::get<1>(_M_m)));
 939           return __ret;
 940         }
 941
 942     private:
 943       tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
 944     };
 945
 946   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
 947     struct __boyer_moore_map_base
 948     {
 949       template<typename _RAIter>
 950         __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
 951                                _Hash&& __hf, _Pred&& __pred)
 952         : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
 953         {
 954           if (__patlen > 0)
 955             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
 956               _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
 957         }
 958
 959       using __diff_type = _Tp;
 960
 961       __diff_type
 962       _M_lookup(_Key __key, __diff_type __not_found) const
 963       {
 964         auto __iter = _M_bad_char.find(__key);
 965         if (__iter == _M_bad_char.end())
 966           return __not_found;
 967         return __iter->second;
 968       }
 969
 970       _Pred
 971       _M_pred() const { return _M_bad_char.key_eq(); }
 972
 973       _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
 974     };
 975
 976   template<typename _Tp, size_t _Len, typename _Pred>
 977     struct __boyer_moore_array_base
 978     {
 979       template<typename _RAIter, typename _Unused>
 980         __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
 981                                  _Unused&&, _Pred&& __pred)
 982         : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
 983         {
 984           std::get<0>(_M_bad_char).fill(__patlen);
 985           if (__patlen > 0)
 986             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
 987               {
 988                 auto __ch = __pat[__i];
 989                 using _UCh = make_unsigned_t<decltype(__ch)>;
 990                 auto __uch = static_cast<_UCh>(__ch);
 991                 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
 992               }
 993         }
 994
 995       using __diff_type = _Tp;
 996
 997       template<typename _Key>
 998         __diff_type
 999         _M_lookup(_Key __key, __diff_type __not_found) const
1000         {
1001           auto __ukey = static_cast<make_unsigned_t<_Key>>(__key);
1002           if (__ukey >= _Len)
1003             return __not_found;
1004           return std::get<0>(_M_bad_char)[__ukey];
1005         }
1006
1007       const _Pred&
1008       _M_pred() const { return std::get<1>(_M_bad_char); }
1009
1010       tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;
1011     };
1012
1013   // Use __boyer_moore_array_base when pattern consists of narrow characters
1014   // (or std::byte) and uses std::equal_to as the predicate.
1015   template<typename _RAIter, typename _Hash, typename _Pred,
1016            typename _Val = typename iterator_traits<_RAIter>::value_type,
1017            typename _Diff = typename iterator_traits<_RAIter>::difference_type>
1018     using __boyer_moore_base_t
1019       = conditional_t<__is_byte_like<_Val, _Pred>::value,
1020                       __boyer_moore_array_base<_Diff, 256, _Pred>,
1021                       __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
1022
1023   template<typename _RAIter, typename _Hash
1024              = hash<typename iterator_traits<_RAIter>::value_type>,
1025            typename _BinaryPredicate = equal_to<>>
1026     class boyer_moore_searcher
1027     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
1028     {
1029       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
1030       using typename _Base::__diff_type;
1031
1032     public:
1033       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
1034                            _Hash __hf = _Hash(),
1035                            _BinaryPredicate __pred = _BinaryPredicate());
1036
1037       template<typename _RandomAccessIterator2>
1038         pair<_RandomAccessIterator2, _RandomAccessIterator2>
1039         operator()(_RandomAccessIterator2 __first,
1040                    _RandomAccessIterator2 __last) const;
1041
1042     private:
1043       bool
1044       _M_is_prefix(_RAIter __word, __diff_type __len,
1045                    __diff_type __pos)
1046       {
1047         const auto& __pred = this->_M_pred();
1048         __diff_type __suffixlen = __len - __pos;
1049         for (__diff_type __i = 0; __i < __suffixlen; ++__i)
1050           if (!__pred(__word[__i], __word[__pos + __i]))
1051             return false;
1052         return true;
1053       }
1054
1055       __diff_type
1056       _M_suffix_length(_RAIter __word, __diff_type __len,
1057                        __diff_type __pos)
1058       {
1059         const auto& __pred = this->_M_pred();
1060         __diff_type __i = 0;
1061         while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
1062                && __i < __pos)
1063           {
1064             ++__i;
1065           }
1066         return __i;
1067       }
1068
1069       template<typename _Tp>
1070         __diff_type
1071         _M_bad_char_shift(_Tp __c) const
1072         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
1073
1074       _RAIter _M_pat;
1075       _RAIter _M_pat_end;
1076       _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
1077     };
1078
1079   template<typename _RAIter, typename _Hash
1080              = hash<typename iterator_traits<_RAIter>::value_type>,
1081            typename _BinaryPredicate = equal_to<>>
1082     class boyer_moore_horspool_searcher
1083     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
1084     {
1085       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
1086       using typename _Base::__diff_type;
1087
1088     public:
1089       boyer_moore_horspool_searcher(_RAIter __pat,
1090                                     _RAIter __pat_end,
1091                                     _Hash __hf = _Hash(),
1092                                     _BinaryPredicate __pred
1093                                     = _BinaryPredicate())
1094       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
1095         _M_pat(__pat), _M_pat_end(__pat_end)
1096       { }
1097
1098       template<typename _RandomAccessIterator2>
1099         pair<_RandomAccessIterator2, _RandomAccessIterator2>
1100         operator()(_RandomAccessIterator2 __first,
1101                    _RandomAccessIterator2 __last) const
1102         {
1103           const auto& __pred = this->_M_pred();
1104           auto __patlen = _M_pat_end - _M_pat;
1105           if (__patlen == 0)
1106             return std::make_pair(__first, __first);
1107           auto __len = __last - __first;
1108           while (__len >= __patlen)
1109             {
1110               for (auto __scan = __patlen - 1;
1111                    __pred(__first[__scan], _M_pat[__scan]); --__scan)
1112                 if (__scan == 0)
1113                   return std::make_pair(__first, __first + __patlen);
1114               auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
1115               __len -= __shift;
1116               __first += __shift;
1117             }
1118           return std::make_pair(__last, __last);
1119         }
1120
1121     private:
1122       template<typename _Tp>
1123         __diff_type
1124         _M_bad_char_shift(_Tp __c) const
1125         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
1126
1127       _RAIter _M_pat;
1128       _RAIter _M_pat_end;
1129     };
1130
1131   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
1132     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
1133     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
1134                          _Hash __hf, _BinaryPredicate __pred)
1135     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
1136       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
1137     {
1138       auto __patlen = __pat_end - __pat;
1139       if (__patlen == 0)
1140         return;
1141       __diff_type __last_prefix = __patlen - 1;
1142       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
1143         {
1144           if (_M_is_prefix(__pat, __patlen, __p + 1))
1145             __last_prefix = __p + 1;
1146           _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
1147         }
1148       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
1149         {
1150           auto __slen = _M_suffix_length(__pat, __patlen, __p);
1151           auto __pos = __patlen - 1 - __slen;
1152           if (!__pred(__pat[__p - __slen], __pat[__pos]))
1153             _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
1154         }
1155     }
1156
1157   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
1158   template<typename _RandomAccessIterator2>
1159     pair<_RandomAccessIterator2, _RandomAccessIterator2>
1160     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
1161     operator()(_RandomAccessIterator2 __first,
1162                _RandomAccessIterator2 __last) const
1163     {
1164       auto __patlen = _M_pat_end - _M_pat;
1165       if (__patlen == 0)
1166         return std::make_pair(__first, __first);
1167       const auto& __pred = this->_M_pred();
1168       __diff_type __i = __patlen - 1;
1169       auto __stringlen = __last - __first;
1170       while (__i < __stringlen)
1171         {
1172           __diff_type __j = __patlen - 1;
1173           while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
1174             {
1175               --__i;
1176               --__j;
1177             }
1178           if (__j < 0)
1179             {
1180               const auto __match = __first + __i + 1;
1181               return std::make_pair(__match, __match + __patlen);
1182             }
1183           __i += std::max(_M_bad_char_shift(__first[__i]),
1184                           _M_good_suffix[__j]);
1185         }
1186       return std::make_pair(__last, __last);
1187     }
1188
1189 #endif // C++17
1190 #endif // C++14
1191
1192 _GLIBCXX_END_NAMESPACE_VERSION
1193 } // namespace std
1194
1195 #endif // C++11
1196
1197 #endif // _GLIBCXX_FUNCTIONAL