libstdc++
functional
Go to the documentation of this file.
00001 // <functional> -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2018 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  * Copyright (c) 1997
00027  * Silicon Graphics Computer Systems, Inc.
00028  *
00029  * Permission to use, copy, modify, distribute and sell this software
00030  * and its documentation for any purpose is hereby granted without fee,
00031  * provided that the above copyright notice appear in all copies and
00032  * that both that copyright notice and this permission notice appear
00033  * in supporting documentation.  Silicon Graphics makes no
00034  * representations about the suitability of this software for any
00035  * purpose.  It is provided "as is" without express or implied warranty.
00036  *
00037  */
00038 
00039 /** @file include/functional
00040  *  This is a Standard C++ Library header.
00041  */
00042 
00043 #ifndef _GLIBCXX_FUNCTIONAL
00044 #define _GLIBCXX_FUNCTIONAL 1
00045 
00046 #pragma GCC system_header
00047 
00048 #include <bits/c++config.h>
00049 #include <bits/stl_function.h>
00050 
00051 #if __cplusplus >= 201103L
00052 
00053 #include <new>
00054 #include <tuple>
00055 #include <type_traits>
00056 #include <bits/functional_hash.h>
00057 #include <bits/invoke.h>
00058 #include <bits/refwrap.h>       // std::reference_wrapper and _Mem_fn_traits
00059 #include <bits/std_function.h>  // std::function
00060 #if __cplusplus > 201402L
00061 # include <unordered_map>
00062 # include <vector>
00063 # include <array>
00064 # include <utility>
00065 # include <bits/stl_algo.h>
00066 #endif
00067 
00068 namespace std _GLIBCXX_VISIBILITY(default)
00069 {
00070 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00071 
00072 #if __cplusplus > 201402L
00073 # define __cpp_lib_invoke 201411
00074 
00075   /// Invoke a callable object.
00076   template<typename _Callable, typename... _Args>
00077     inline invoke_result_t<_Callable, _Args...>
00078     invoke(_Callable&& __fn, _Args&&... __args)
00079     noexcept(is_nothrow_invocable_v<_Callable, _Args...>)
00080     {
00081       return std::__invoke(std::forward<_Callable>(__fn),
00082                            std::forward<_Args>(__args)...);
00083     }
00084 #endif
00085 
00086   template<typename _MemFunPtr,
00087            bool __is_mem_fn = is_member_function_pointer<_MemFunPtr>::value>
00088     class _Mem_fn_base
00089     : public _Mem_fn_traits<_MemFunPtr>::__maybe_type
00090     {
00091       using _Traits = _Mem_fn_traits<_MemFunPtr>;
00092 
00093       using _Arity = typename _Traits::__arity;
00094       using _Varargs = typename _Traits::__vararg;
00095 
00096       template<typename _Func, typename... _BoundArgs>
00097         friend struct _Bind_check_arity;
00098 
00099       _MemFunPtr _M_pmf;
00100 
00101     public:
00102 
00103       using result_type = typename _Traits::__result_type;
00104 
00105       explicit constexpr
00106       _Mem_fn_base(_MemFunPtr __pmf) noexcept : _M_pmf(__pmf) { }
00107 
00108       template<typename... _Args>
00109         auto
00110         operator()(_Args&&... __args) const
00111         noexcept(noexcept(
00112               std::__invoke(_M_pmf, std::forward<_Args>(__args)...)))
00113         -> decltype(std::__invoke(_M_pmf, std::forward<_Args>(__args)...))
00114         { return std::__invoke(_M_pmf, std::forward<_Args>(__args)...); }
00115     };
00116 
00117   // Partial specialization for member object pointers.
00118   template<typename _MemObjPtr>
00119     class _Mem_fn_base<_MemObjPtr, false>
00120     {
00121       using _Arity = integral_constant<size_t, 0>;
00122       using _Varargs = false_type;
00123 
00124       template<typename _Func, typename... _BoundArgs>
00125         friend struct _Bind_check_arity;
00126 
00127       _MemObjPtr _M_pm;
00128 
00129     public:
00130       explicit constexpr
00131       _Mem_fn_base(_MemObjPtr __pm) noexcept : _M_pm(__pm) { }
00132 
00133       template<typename _Tp>
00134         auto
00135         operator()(_Tp&& __obj) const
00136         noexcept(noexcept(std::__invoke(_M_pm, std::forward<_Tp>(__obj))))
00137         -> decltype(std::__invoke(_M_pm, std::forward<_Tp>(__obj)))
00138         { return std::__invoke(_M_pm, std::forward<_Tp>(__obj)); }
00139     };
00140 
00141   template<typename _MemberPointer>
00142     struct _Mem_fn; // undefined
00143 
00144   template<typename _Res, typename _Class>
00145     struct _Mem_fn<_Res _Class::*>
00146     : _Mem_fn_base<_Res _Class::*>
00147     {
00148       using _Mem_fn_base<_Res _Class::*>::_Mem_fn_base;
00149     };
00150 
00151   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00152   // 2048.  Unnecessary mem_fn overloads
00153   /**
00154    *  @brief Returns a function object that forwards to the member
00155    *  pointer @a pm.
00156    *  @ingroup functors
00157    */
00158   template<typename _Tp, typename _Class>
00159     inline _Mem_fn<_Tp _Class::*>
00160     mem_fn(_Tp _Class::* __pm) noexcept
00161     {
00162       return _Mem_fn<_Tp _Class::*>(__pm);
00163     }
00164 
00165   /**
00166    *  @brief Determines if the given type _Tp is a function object that
00167    *  should be treated as a subexpression when evaluating calls to
00168    *  function objects returned by bind().
00169    *
00170    *  C++11 [func.bind.isbind].
00171    *  @ingroup binders
00172    */
00173   template<typename _Tp>
00174     struct is_bind_expression
00175     : public false_type { };
00176 
00177   /**
00178    *  @brief Determines if the given type _Tp is a placeholder in a
00179    *  bind() expression and, if so, which placeholder it is.
00180    *
00181    *  C++11 [func.bind.isplace].
00182    *  @ingroup binders
00183    */
00184   template<typename _Tp>
00185     struct is_placeholder
00186     : public integral_constant<int, 0>
00187     { };
00188 
00189 #if __cplusplus > 201402L
00190   template <typename _Tp> inline constexpr bool is_bind_expression_v
00191     = is_bind_expression<_Tp>::value;
00192   template <typename _Tp> inline constexpr int is_placeholder_v
00193     = is_placeholder<_Tp>::value;
00194 #endif // C++17
00195 
00196   /** @brief The type of placeholder objects defined by libstdc++.
00197    *  @ingroup binders
00198    */
00199   template<int _Num> struct _Placeholder { };
00200 
00201   /** @namespace std::placeholders
00202    *  @brief ISO C++11 entities sub-namespace for functional.
00203    *  @ingroup binders
00204    */
00205   namespace placeholders
00206   {
00207   /* Define a large number of placeholders. There is no way to
00208    * simplify this with variadic templates, because we're introducing
00209    * unique names for each.
00210    */
00211     extern const _Placeholder<1> _1;
00212     extern const _Placeholder<2> _2;
00213     extern const _Placeholder<3> _3;
00214     extern const _Placeholder<4> _4;
00215     extern const _Placeholder<5> _5;
00216     extern const _Placeholder<6> _6;
00217     extern const _Placeholder<7> _7;
00218     extern const _Placeholder<8> _8;
00219     extern const _Placeholder<9> _9;
00220     extern const _Placeholder<10> _10;
00221     extern const _Placeholder<11> _11;
00222     extern const _Placeholder<12> _12;
00223     extern const _Placeholder<13> _13;
00224     extern const _Placeholder<14> _14;
00225     extern const _Placeholder<15> _15;
00226     extern const _Placeholder<16> _16;
00227     extern const _Placeholder<17> _17;
00228     extern const _Placeholder<18> _18;
00229     extern const _Placeholder<19> _19;
00230     extern const _Placeholder<20> _20;
00231     extern const _Placeholder<21> _21;
00232     extern const _Placeholder<22> _22;
00233     extern const _Placeholder<23> _23;
00234     extern const _Placeholder<24> _24;
00235     extern const _Placeholder<25> _25;
00236     extern const _Placeholder<26> _26;
00237     extern const _Placeholder<27> _27;
00238     extern const _Placeholder<28> _28;
00239     extern const _Placeholder<29> _29;
00240   }
00241 
00242   /**
00243    *  Partial specialization of is_placeholder that provides the placeholder
00244    *  number for the placeholder objects defined by libstdc++.
00245    *  @ingroup binders
00246    */
00247   template<int _Num>
00248     struct is_placeholder<_Placeholder<_Num> >
00249     : public integral_constant<int, _Num>
00250     { };
00251 
00252   template<int _Num>
00253     struct is_placeholder<const _Placeholder<_Num> >
00254     : public integral_constant<int, _Num>
00255     { };
00256 
00257 
00258   // Like tuple_element_t but SFINAE-friendly.
00259   template<std::size_t __i, typename _Tuple>
00260     using _Safe_tuple_element_t
00261       = typename enable_if<(__i < tuple_size<_Tuple>::value),
00262                            tuple_element<__i, _Tuple>>::type::type;
00263 
00264   /**
00265    *  Maps an argument to bind() into an actual argument to the bound
00266    *  function object [func.bind.bind]/10. Only the first parameter should
00267    *  be specified: the rest are used to determine among the various
00268    *  implementations. Note that, although this class is a function
00269    *  object, it isn't entirely normal because it takes only two
00270    *  parameters regardless of the number of parameters passed to the
00271    *  bind expression. The first parameter is the bound argument and
00272    *  the second parameter is a tuple containing references to the
00273    *  rest of the arguments.
00274    */
00275   template<typename _Arg,
00276            bool _IsBindExp = is_bind_expression<_Arg>::value,
00277            bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>
00278     class _Mu;
00279 
00280   /**
00281    *  If the argument is reference_wrapper<_Tp>, returns the
00282    *  underlying reference.
00283    *  C++11 [func.bind.bind] p10 bullet 1.
00284    */
00285   template<typename _Tp>
00286     class _Mu<reference_wrapper<_Tp>, false, false>
00287     {
00288     public:
00289       /* Note: This won't actually work for const volatile
00290        * reference_wrappers, because reference_wrapper::get() is const
00291        * but not volatile-qualified. This might be a defect in the TR.
00292        */
00293       template<typename _CVRef, typename _Tuple>
00294         _Tp&
00295         operator()(_CVRef& __arg, _Tuple&) const volatile
00296         { return __arg.get(); }
00297     };
00298 
00299   /**
00300    *  If the argument is a bind expression, we invoke the underlying
00301    *  function object with the same cv-qualifiers as we are given and
00302    *  pass along all of our arguments (unwrapped).
00303    *  C++11 [func.bind.bind] p10 bullet 2.
00304    */
00305   template<typename _Arg>
00306     class _Mu<_Arg, true, false>
00307     {
00308     public:
00309       template<typename _CVArg, typename... _Args>
00310         auto
00311         operator()(_CVArg& __arg,
00312                    tuple<_Args...>& __tuple) const volatile
00313         -> decltype(__arg(declval<_Args>()...))
00314         {
00315           // Construct an index tuple and forward to __call
00316           typedef typename _Build_index_tuple<sizeof...(_Args)>::__type
00317             _Indexes;
00318           return this->__call(__arg, __tuple, _Indexes());
00319         }
00320 
00321     private:
00322       // Invokes the underlying function object __arg by unpacking all
00323       // of the arguments in the tuple.
00324       template<typename _CVArg, typename... _Args, std::size_t... _Indexes>
00325         auto
00326         __call(_CVArg& __arg, tuple<_Args...>& __tuple,
00327                const _Index_tuple<_Indexes...>&) const volatile
00328         -> decltype(__arg(declval<_Args>()...))
00329         {
00330           return __arg(std::get<_Indexes>(std::move(__tuple))...);
00331         }
00332     };
00333 
00334   /**
00335    *  If the argument is a placeholder for the Nth argument, returns
00336    *  a reference to the Nth argument to the bind function object.
00337    *  C++11 [func.bind.bind] p10 bullet 3.
00338    */
00339   template<typename _Arg>
00340     class _Mu<_Arg, false, true>
00341     {
00342     public:
00343       template<typename _Tuple>
00344         _Safe_tuple_element_t<(is_placeholder<_Arg>::value - 1), _Tuple>&&
00345         operator()(const volatile _Arg&, _Tuple& __tuple) const volatile
00346         {
00347           return
00348             ::std::get<(is_placeholder<_Arg>::value - 1)>(std::move(__tuple));
00349         }
00350     };
00351 
00352   /**
00353    *  If the argument is just a value, returns a reference to that
00354    *  value. The cv-qualifiers on the reference are determined by the caller.
00355    *  C++11 [func.bind.bind] p10 bullet 4.
00356    */
00357   template<typename _Arg>
00358     class _Mu<_Arg, false, false>
00359     {
00360     public:
00361       template<typename _CVArg, typename _Tuple>
00362         _CVArg&&
00363         operator()(_CVArg&& __arg, _Tuple&) const volatile
00364         { return std::forward<_CVArg>(__arg); }
00365     };
00366 
00367   // std::get<I> for volatile-qualified tuples
00368   template<std::size_t _Ind, typename... _Tp>
00369     inline auto
00370     __volget(volatile tuple<_Tp...>& __tuple)
00371     -> __tuple_element_t<_Ind, tuple<_Tp...>> volatile&
00372     { return std::get<_Ind>(const_cast<tuple<_Tp...>&>(__tuple)); }
00373 
00374   // std::get<I> for const-volatile-qualified tuples
00375   template<std::size_t _Ind, typename... _Tp>
00376     inline auto
00377     __volget(const volatile tuple<_Tp...>& __tuple)
00378     -> __tuple_element_t<_Ind, tuple<_Tp...>> const volatile&
00379     { return std::get<_Ind>(const_cast<const tuple<_Tp...>&>(__tuple)); }
00380 
00381   /// Type of the function object returned from bind().
00382   template<typename _Signature>
00383     struct _Bind;
00384 
00385    template<typename _Functor, typename... _Bound_args>
00386     class _Bind<_Functor(_Bound_args...)>
00387     : public _Weak_result_type<_Functor>
00388     {
00389       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
00390         _Bound_indexes;
00391 
00392       _Functor _M_f;
00393       tuple<_Bound_args...> _M_bound_args;
00394 
00395       // Call unqualified
00396       template<typename _Result, typename... _Args, std::size_t... _Indexes>
00397         _Result
00398         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
00399         {
00400           return std::__invoke(_M_f,
00401               _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
00402               );
00403         }
00404 
00405       // Call as const
00406       template<typename _Result, typename... _Args, std::size_t... _Indexes>
00407         _Result
00408         __call_c(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
00409         {
00410           return std::__invoke(_M_f,
00411               _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...
00412               );
00413         }
00414 
00415       // Call as volatile
00416       template<typename _Result, typename... _Args, std::size_t... _Indexes>
00417         _Result
00418         __call_v(tuple<_Args...>&& __args,
00419                  _Index_tuple<_Indexes...>) volatile
00420         {
00421           return std::__invoke(_M_f,
00422               _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
00423               );
00424         }
00425 
00426       // Call as const volatile
00427       template<typename _Result, typename... _Args, std::size_t... _Indexes>
00428         _Result
00429         __call_c_v(tuple<_Args...>&& __args,
00430                    _Index_tuple<_Indexes...>) const volatile
00431         {
00432           return std::__invoke(_M_f,
00433               _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...
00434               );
00435         }
00436 
00437       template<typename _BoundArg, typename _CallArgs>
00438         using _Mu_type = decltype(
00439             _Mu<typename remove_cv<_BoundArg>::type>()(
00440               std::declval<_BoundArg&>(), std::declval<_CallArgs&>()) );
00441 
00442       template<typename _Fn, typename _CallArgs, typename... _BArgs>
00443         using _Res_type_impl
00444           = typename result_of< _Fn&(_Mu_type<_BArgs, _CallArgs>&&...) >::type;
00445 
00446       template<typename _CallArgs>
00447         using _Res_type = _Res_type_impl<_Functor, _CallArgs, _Bound_args...>;
00448 
00449       template<typename _CallArgs>
00450         using __dependent = typename
00451           enable_if<bool(tuple_size<_CallArgs>::value+1), _Functor>::type;
00452 
00453       template<typename _CallArgs, template<class> class __cv_quals>
00454         using _Res_type_cv = _Res_type_impl<
00455           typename __cv_quals<__dependent<_CallArgs>>::type,
00456           _CallArgs,
00457           typename __cv_quals<_Bound_args>::type...>;
00458 
00459      public:
00460       template<typename... _Args>
00461         explicit _Bind(const _Functor& __f, _Args&&... __args)
00462         : _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)
00463         { }
00464 
00465       template<typename... _Args>
00466         explicit _Bind(_Functor&& __f, _Args&&... __args)
00467         : _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)
00468         { }
00469 
00470       _Bind(const _Bind&) = default;
00471 
00472       _Bind(_Bind&& __b)
00473       : _M_f(std::move(__b._M_f)), _M_bound_args(std::move(__b._M_bound_args))
00474       { }
00475 
00476       // Call unqualified
00477       template<typename... _Args,
00478                typename _Result = _Res_type<tuple<_Args...>>>
00479         _Result
00480         operator()(_Args&&... __args)
00481         {
00482           return this->__call<_Result>(
00483               std::forward_as_tuple(std::forward<_Args>(__args)...),
00484               _Bound_indexes());
00485         }
00486 
00487       // Call as const
00488       template<typename... _Args,
00489                typename _Result = _Res_type_cv<tuple<_Args...>, add_const>>
00490         _Result
00491         operator()(_Args&&... __args) const
00492         {
00493           return this->__call_c<_Result>(
00494               std::forward_as_tuple(std::forward<_Args>(__args)...),
00495               _Bound_indexes());
00496         }
00497 
00498 #if __cplusplus > 201402L
00499 # define _GLIBCXX_DEPR_BIND \
00500       [[deprecated("std::bind does not support volatile in C++17")]]
00501 #else
00502 # define _GLIBCXX_DEPR_BIND
00503 #endif
00504       // Call as volatile
00505       template<typename... _Args,
00506                typename _Result = _Res_type_cv<tuple<_Args...>, add_volatile>>
00507         _GLIBCXX_DEPR_BIND
00508         _Result
00509         operator()(_Args&&... __args) volatile
00510         {
00511           return this->__call_v<_Result>(
00512               std::forward_as_tuple(std::forward<_Args>(__args)...),
00513               _Bound_indexes());
00514         }
00515 
00516       // Call as const volatile
00517       template<typename... _Args,
00518                typename _Result = _Res_type_cv<tuple<_Args...>, add_cv>>
00519         _GLIBCXX_DEPR_BIND
00520         _Result
00521         operator()(_Args&&... __args) const volatile
00522         {
00523           return this->__call_c_v<_Result>(
00524               std::forward_as_tuple(std::forward<_Args>(__args)...),
00525               _Bound_indexes());
00526         }
00527     };
00528 
00529   /// Type of the function object returned from bind<R>().
00530   template<typename _Result, typename _Signature>
00531     struct _Bind_result;
00532 
00533   template<typename _Result, typename _Functor, typename... _Bound_args>
00534     class _Bind_result<_Result, _Functor(_Bound_args...)>
00535     {
00536       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type
00537         _Bound_indexes;
00538 
00539       _Functor _M_f;
00540       tuple<_Bound_args...> _M_bound_args;
00541 
00542       // sfinae types
00543       template<typename _Res>
00544         using __enable_if_void
00545           = typename enable_if<is_void<_Res>{}>::type;
00546 
00547       template<typename _Res>
00548         using __disable_if_void
00549           = typename enable_if<!is_void<_Res>{}, _Result>::type;
00550 
00551       // Call unqualified
00552       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00553         __disable_if_void<_Res>
00554         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
00555         {
00556           return std::__invoke(_M_f, _Mu<_Bound_args>()
00557                       (std::get<_Indexes>(_M_bound_args), __args)...);
00558         }
00559 
00560       // Call unqualified, return void
00561       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00562         __enable_if_void<_Res>
00563         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)
00564         {
00565           std::__invoke(_M_f, _Mu<_Bound_args>()
00566                (std::get<_Indexes>(_M_bound_args), __args)...);
00567         }
00568 
00569       // Call as const
00570       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00571         __disable_if_void<_Res>
00572         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
00573         {
00574           return std::__invoke(_M_f, _Mu<_Bound_args>()
00575                       (std::get<_Indexes>(_M_bound_args), __args)...);
00576         }
00577 
00578       // Call as const, return void
00579       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00580         __enable_if_void<_Res>
00581         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const
00582         {
00583           std::__invoke(_M_f, _Mu<_Bound_args>()
00584                (std::get<_Indexes>(_M_bound_args),  __args)...);
00585         }
00586 
00587       // Call as volatile
00588       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00589         __disable_if_void<_Res>
00590         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) volatile
00591         {
00592           return std::__invoke(_M_f, _Mu<_Bound_args>()
00593                       (__volget<_Indexes>(_M_bound_args), __args)...);
00594         }
00595 
00596       // Call as volatile, return void
00597       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00598         __enable_if_void<_Res>
00599         __call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) volatile
00600         {
00601           std::__invoke(_M_f, _Mu<_Bound_args>()
00602                (__volget<_Indexes>(_M_bound_args), __args)...);
00603         }
00604 
00605       // Call as const volatile
00606       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00607         __disable_if_void<_Res>
00608         __call(tuple<_Args...>&& __args,
00609                _Index_tuple<_Indexes...>) const volatile
00610         {
00611           return std::__invoke(_M_f, _Mu<_Bound_args>()
00612                       (__volget<_Indexes>(_M_bound_args), __args)...);
00613         }
00614 
00615       // Call as const volatile, return void
00616       template<typename _Res, typename... _Args, std::size_t... _Indexes>
00617         __enable_if_void<_Res>
00618         __call(tuple<_Args...>&& __args,
00619                _Index_tuple<_Indexes...>) const volatile
00620         {
00621           std::__invoke(_M_f, _Mu<_Bound_args>()
00622                (__volget<_Indexes>(_M_bound_args), __args)...);
00623         }
00624 
00625     public:
00626       typedef _Result result_type;
00627 
00628       template<typename... _Args>
00629         explicit _Bind_result(const _Functor& __f, _Args&&... __args)
00630         : _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)
00631         { }
00632 
00633       template<typename... _Args>
00634         explicit _Bind_result(_Functor&& __f, _Args&&... __args)
00635         : _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)
00636         { }
00637 
00638       _Bind_result(const _Bind_result&) = default;
00639 
00640       _Bind_result(_Bind_result&& __b)
00641       : _M_f(std::move(__b._M_f)), _M_bound_args(std::move(__b._M_bound_args))
00642       { }
00643 
00644       // Call unqualified
00645       template<typename... _Args>
00646         result_type
00647         operator()(_Args&&... __args)
00648         {
00649           return this->__call<_Result>(
00650               std::forward_as_tuple(std::forward<_Args>(__args)...),
00651               _Bound_indexes());
00652         }
00653 
00654       // Call as const
00655       template<typename... _Args>
00656         result_type
00657         operator()(_Args&&... __args) const
00658         {
00659           return this->__call<_Result>(
00660               std::forward_as_tuple(std::forward<_Args>(__args)...),
00661               _Bound_indexes());
00662         }
00663 
00664       // Call as volatile
00665       template<typename... _Args>
00666         _GLIBCXX_DEPR_BIND
00667         result_type
00668         operator()(_Args&&... __args) volatile
00669         {
00670           return this->__call<_Result>(
00671               std::forward_as_tuple(std::forward<_Args>(__args)...),
00672               _Bound_indexes());
00673         }
00674 
00675       // Call as const volatile
00676       template<typename... _Args>
00677         _GLIBCXX_DEPR_BIND
00678         result_type
00679         operator()(_Args&&... __args) const volatile
00680         {
00681           return this->__call<_Result>(
00682               std::forward_as_tuple(std::forward<_Args>(__args)...),
00683               _Bound_indexes());
00684         }
00685     };
00686 #undef _GLIBCXX_DEPR_BIND
00687 
00688   /**
00689    *  @brief Class template _Bind is always a bind expression.
00690    *  @ingroup binders
00691    */
00692   template<typename _Signature>
00693     struct is_bind_expression<_Bind<_Signature> >
00694     : public true_type { };
00695 
00696   /**
00697    *  @brief Class template _Bind is always a bind expression.
00698    *  @ingroup binders
00699    */
00700   template<typename _Signature>
00701     struct is_bind_expression<const _Bind<_Signature> >
00702     : public true_type { };
00703 
00704   /**
00705    *  @brief Class template _Bind is always a bind expression.
00706    *  @ingroup binders
00707    */
00708   template<typename _Signature>
00709     struct is_bind_expression<volatile _Bind<_Signature> >
00710     : public true_type { };
00711 
00712   /**
00713    *  @brief Class template _Bind is always a bind expression.
00714    *  @ingroup binders
00715    */
00716   template<typename _Signature>
00717     struct is_bind_expression<const volatile _Bind<_Signature>>
00718     : public true_type { };
00719 
00720   /**
00721    *  @brief Class template _Bind_result is always a bind expression.
00722    *  @ingroup binders
00723    */
00724   template<typename _Result, typename _Signature>
00725     struct is_bind_expression<_Bind_result<_Result, _Signature>>
00726     : public true_type { };
00727 
00728   /**
00729    *  @brief Class template _Bind_result is always a bind expression.
00730    *  @ingroup binders
00731    */
00732   template<typename _Result, typename _Signature>
00733     struct is_bind_expression<const _Bind_result<_Result, _Signature>>
00734     : public true_type { };
00735 
00736   /**
00737    *  @brief Class template _Bind_result is always a bind expression.
00738    *  @ingroup binders
00739    */
00740   template<typename _Result, typename _Signature>
00741     struct is_bind_expression<volatile _Bind_result<_Result, _Signature>>
00742     : public true_type { };
00743 
00744   /**
00745    *  @brief Class template _Bind_result is always a bind expression.
00746    *  @ingroup binders
00747    */
00748   template<typename _Result, typename _Signature>
00749     struct is_bind_expression<const volatile _Bind_result<_Result, _Signature>>
00750     : public true_type { };
00751 
00752   template<typename _Func, typename... _BoundArgs>
00753     struct _Bind_check_arity { };
00754 
00755   template<typename _Ret, typename... _Args, typename... _BoundArgs>
00756     struct _Bind_check_arity<_Ret (*)(_Args...), _BoundArgs...>
00757     {
00758       static_assert(sizeof...(_BoundArgs) == sizeof...(_Args),
00759                    "Wrong number of arguments for function");
00760     };
00761 
00762   template<typename _Ret, typename... _Args, typename... _BoundArgs>
00763     struct _Bind_check_arity<_Ret (*)(_Args......), _BoundArgs...>
00764     {
00765       static_assert(sizeof...(_BoundArgs) >= sizeof...(_Args),
00766                    "Wrong number of arguments for function");
00767     };
00768 
00769   template<typename _Tp, typename _Class, typename... _BoundArgs>
00770     struct _Bind_check_arity<_Tp _Class::*, _BoundArgs...>
00771     {
00772       using _Arity = typename _Mem_fn<_Tp _Class::*>::_Arity;
00773       using _Varargs = typename _Mem_fn<_Tp _Class::*>::_Varargs;
00774       static_assert(_Varargs::value
00775                     ? sizeof...(_BoundArgs) >= _Arity::value + 1
00776                     : sizeof...(_BoundArgs) == _Arity::value + 1,
00777                     "Wrong number of arguments for pointer-to-member");
00778     };
00779 
00780   // Trait type used to remove std::bind() from overload set via SFINAE
00781   // when first argument has integer type, so that std::bind() will
00782   // not be a better match than ::bind() from the BSD Sockets API.
00783   template<typename _Tp, typename _Tp2 = typename decay<_Tp>::type>
00784     using __is_socketlike = __or_<is_integral<_Tp2>, is_enum<_Tp2>>;
00785 
00786   template<bool _SocketLike, typename _Func, typename... _BoundArgs>
00787     struct _Bind_helper
00788     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>
00789     {
00790       typedef typename decay<_Func>::type __func_type;
00791       typedef _Bind<__func_type(typename decay<_BoundArgs>::type...)> type;
00792     };
00793 
00794   // Partial specialization for is_socketlike == true, does not define
00795   // nested type so std::bind() will not participate in overload resolution
00796   // when the first argument might be a socket file descriptor.
00797   template<typename _Func, typename... _BoundArgs>
00798     struct _Bind_helper<true, _Func, _BoundArgs...>
00799     { };
00800 
00801   /**
00802    *  @brief Function template for std::bind.
00803    *  @ingroup binders
00804    */
00805   template<typename _Func, typename... _BoundArgs>
00806     inline typename
00807     _Bind_helper<__is_socketlike<_Func>::value, _Func, _BoundArgs...>::type
00808     bind(_Func&& __f, _BoundArgs&&... __args)
00809     {
00810       typedef _Bind_helper<false, _Func, _BoundArgs...> __helper_type;
00811       return typename __helper_type::type(std::forward<_Func>(__f),
00812                                           std::forward<_BoundArgs>(__args)...);
00813     }
00814 
00815   template<typename _Result, typename _Func, typename... _BoundArgs>
00816     struct _Bindres_helper
00817     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>
00818     {
00819       typedef typename decay<_Func>::type __functor_type;
00820       typedef _Bind_result<_Result,
00821                            __functor_type(typename decay<_BoundArgs>::type...)>
00822         type;
00823     };
00824 
00825   /**
00826    *  @brief Function template for std::bind<R>.
00827    *  @ingroup binders
00828    */
00829   template<typename _Result, typename _Func, typename... _BoundArgs>
00830     inline
00831     typename _Bindres_helper<_Result, _Func, _BoundArgs...>::type
00832     bind(_Func&& __f, _BoundArgs&&... __args)
00833     {
00834       typedef _Bindres_helper<_Result, _Func, _BoundArgs...> __helper_type;
00835       return typename __helper_type::type(std::forward<_Func>(__f),
00836                                           std::forward<_BoundArgs>(__args)...);
00837     }
00838 
00839 #if __cplusplus >= 201402L
00840   /// Generalized negator.
00841   template<typename _Fn>
00842     class _Not_fn
00843     {
00844       template<typename _Fn2, typename... _Args>
00845         using __inv_res_t = typename __invoke_result<_Fn2, _Args...>::type;
00846 
00847       template<typename _Tp>
00848         static decltype(!std::declval<_Tp>())
00849         _S_not() noexcept(noexcept(!std::declval<_Tp>()));
00850 
00851     public:
00852       template<typename _Fn2>
00853         _Not_fn(_Fn2&& __fn, int)
00854         : _M_fn(std::forward<_Fn2>(__fn)) { }
00855 
00856       _Not_fn(const _Not_fn& __fn) = default;
00857       _Not_fn(_Not_fn&& __fn) = default;
00858       ~_Not_fn() = default;
00859 
00860       // Macro to define operator() with given cv-qualifiers ref-qualifiers,
00861       // forwarding _M_fn and the function arguments with the same qualifiers,
00862       // and deducing the return type and exception-specification.
00863 #define _GLIBCXX_NOT_FN_CALL_OP( _QUALS )                               \
00864       template<typename... _Args>                                       \
00865         decltype(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>())           \
00866         operator()(_Args&&... __args) _QUALS                            \
00867         noexcept(noexcept(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>())) \
00868         {                                                               \
00869           return !std::__invoke(std::forward< _Fn _QUALS >(_M_fn),      \
00870                                 std::forward<_Args>(__args)...);        \
00871         }
00872       _GLIBCXX_NOT_FN_CALL_OP( & )
00873       _GLIBCXX_NOT_FN_CALL_OP( const & )
00874       _GLIBCXX_NOT_FN_CALL_OP( && )
00875       _GLIBCXX_NOT_FN_CALL_OP( const && )
00876 #undef _GLIBCXX_NOT_FN_CALL
00877 
00878     private:
00879       _Fn _M_fn;
00880     };
00881 
00882   template<typename _Tp, typename _Pred>
00883     struct __is_byte_like : false_type { };
00884 
00885   template<typename _Tp>
00886     struct __is_byte_like<_Tp, equal_to<_Tp>>
00887     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
00888 
00889   template<typename _Tp>
00890     struct __is_byte_like<_Tp, equal_to<void>>
00891     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
00892 
00893 #if __cplusplus >= 201703L
00894   // Declare std::byte (full definition is in <cstddef>).
00895   enum class byte : unsigned char;
00896 
00897   template<>
00898     struct __is_byte_like<byte, equal_to<byte>>
00899     : true_type { };
00900 
00901   template<>
00902     struct __is_byte_like<byte, equal_to<void>>
00903     : true_type { };
00904 
00905 #define __cpp_lib_not_fn 201603
00906   /// [func.not_fn] Function template not_fn
00907   template<typename _Fn>
00908     inline auto
00909     not_fn(_Fn&& __fn)
00910     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
00911     {
00912       return _Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
00913     }
00914 
00915   // Searchers
00916 #define __cpp_lib_boyer_moore_searcher 201603
00917 
00918   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
00919     class default_searcher
00920     {
00921     public:
00922       default_searcher(_ForwardIterator1 __pat_first,
00923                        _ForwardIterator1 __pat_last,
00924                        _BinaryPredicate __pred = _BinaryPredicate())
00925       : _M_m(__pat_first, __pat_last, std::move(__pred))
00926       { }
00927 
00928       template<typename _ForwardIterator2>
00929         pair<_ForwardIterator2, _ForwardIterator2>
00930         operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
00931         {
00932           _ForwardIterator2 __first_ret =
00933             std::search(__first, __last, std::get<0>(_M_m), std::get<1>(_M_m),
00934                         std::get<2>(_M_m));
00935           auto __ret = std::make_pair(__first_ret, __first_ret);
00936           if (__ret.first != __last)
00937             std::advance(__ret.second, std::distance(std::get<0>(_M_m),
00938                                                      std::get<1>(_M_m)));
00939           return __ret;
00940         }
00941 
00942     private:
00943       tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
00944     };
00945 
00946   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
00947     struct __boyer_moore_map_base
00948     {
00949       template<typename _RAIter>
00950         __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
00951                                _Hash&& __hf, _Pred&& __pred)
00952         : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
00953         {
00954           if (__patlen > 0)
00955             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
00956               _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
00957         }
00958 
00959       using __diff_type = _Tp;
00960 
00961       __diff_type
00962       _M_lookup(_Key __key, __diff_type __not_found) const
00963       {
00964         auto __iter = _M_bad_char.find(__key);
00965         if (__iter == _M_bad_char.end())
00966           return __not_found;
00967         return __iter->second;
00968       }
00969 
00970       _Pred
00971       _M_pred() const { return _M_bad_char.key_eq(); }
00972 
00973       _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
00974     };
00975 
00976   template<typename _Tp, size_t _Len, typename _Pred>
00977     struct __boyer_moore_array_base
00978     {
00979       template<typename _RAIter, typename _Unused>
00980         __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
00981                                  _Unused&&, _Pred&& __pred)
00982         : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
00983         {
00984           std::get<0>(_M_bad_char).fill(__patlen);
00985           if (__patlen > 0)
00986             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
00987               {
00988                 auto __ch = __pat[__i];
00989                 using _UCh = make_unsigned_t<decltype(__ch)>;
00990                 auto __uch = static_cast<_UCh>(__ch);
00991                 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
00992               }
00993         }
00994 
00995       using __diff_type = _Tp;
00996 
00997       template<typename _Key>
00998         __diff_type
00999         _M_lookup(_Key __key, __diff_type __not_found) const
01000         {
01001           auto __ukey = static_cast<make_unsigned_t<_Key>>(__key);
01002           if (__ukey >= _Len)
01003             return __not_found;
01004           return std::get<0>(_M_bad_char)[__ukey];
01005         }
01006 
01007       const _Pred&
01008       _M_pred() const { return std::get<1>(_M_bad_char); }
01009 
01010       tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;
01011     };
01012 
01013   // Use __boyer_moore_array_base when pattern consists of narrow characters
01014   // (or std::byte) and uses std::equal_to as the predicate.
01015   template<typename _RAIter, typename _Hash, typename _Pred,
01016            typename _Val = typename iterator_traits<_RAIter>::value_type,
01017            typename _Diff = typename iterator_traits<_RAIter>::difference_type>
01018     using __boyer_moore_base_t
01019       = conditional_t<__is_byte_like<_Val, _Pred>::value,
01020                       __boyer_moore_array_base<_Diff, 256, _Pred>,
01021                       __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
01022 
01023   template<typename _RAIter, typename _Hash
01024              = hash<typename iterator_traits<_RAIter>::value_type>,
01025            typename _BinaryPredicate = equal_to<>>
01026     class boyer_moore_searcher
01027     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
01028     {
01029       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
01030       using typename _Base::__diff_type;
01031 
01032     public:
01033       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
01034                            _Hash __hf = _Hash(),
01035                            _BinaryPredicate __pred = _BinaryPredicate());
01036 
01037       template<typename _RandomAccessIterator2>
01038         pair<_RandomAccessIterator2, _RandomAccessIterator2>
01039         operator()(_RandomAccessIterator2 __first,
01040                    _RandomAccessIterator2 __last) const;
01041 
01042     private:
01043       bool
01044       _M_is_prefix(_RAIter __word, __diff_type __len,
01045                    __diff_type __pos)
01046       {
01047         const auto& __pred = this->_M_pred();
01048         __diff_type __suffixlen = __len - __pos;
01049         for (__diff_type __i = 0; __i < __suffixlen; ++__i)
01050           if (!__pred(__word[__i], __word[__pos + __i]))
01051             return false;
01052         return true;
01053       }
01054 
01055       __diff_type
01056       _M_suffix_length(_RAIter __word, __diff_type __len,
01057                        __diff_type __pos)
01058       {
01059         const auto& __pred = this->_M_pred();
01060         __diff_type __i = 0;
01061         while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
01062                && __i < __pos)
01063           {
01064             ++__i;
01065           }
01066         return __i;
01067       }
01068 
01069       template<typename _Tp>
01070         __diff_type
01071         _M_bad_char_shift(_Tp __c) const
01072         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
01073 
01074       _RAIter _M_pat;
01075       _RAIter _M_pat_end;
01076       _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
01077     };
01078 
01079   template<typename _RAIter, typename _Hash
01080              = hash<typename iterator_traits<_RAIter>::value_type>,
01081            typename _BinaryPredicate = equal_to<>>
01082     class boyer_moore_horspool_searcher
01083     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
01084     {
01085       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
01086       using typename _Base::__diff_type;
01087 
01088     public:
01089       boyer_moore_horspool_searcher(_RAIter __pat,
01090                                     _RAIter __pat_end,
01091                                     _Hash __hf = _Hash(),
01092                                     _BinaryPredicate __pred
01093                                     = _BinaryPredicate())
01094       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
01095         _M_pat(__pat), _M_pat_end(__pat_end)
01096       { }
01097 
01098       template<typename _RandomAccessIterator2>
01099         pair<_RandomAccessIterator2, _RandomAccessIterator2>
01100         operator()(_RandomAccessIterator2 __first,
01101                    _RandomAccessIterator2 __last) const
01102         {
01103           const auto& __pred = this->_M_pred();
01104           auto __patlen = _M_pat_end - _M_pat;
01105           if (__patlen == 0)
01106             return std::make_pair(__first, __first);
01107           auto __len = __last - __first;
01108           while (__len >= __patlen)
01109             {
01110               for (auto __scan = __patlen - 1;
01111                    __pred(__first[__scan], _M_pat[__scan]); --__scan)
01112                 if (__scan == 0)
01113                   return std::make_pair(__first, __first + __patlen);
01114               auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
01115               __len -= __shift;
01116               __first += __shift;
01117             }
01118           return std::make_pair(__last, __last);
01119         }
01120 
01121     private:
01122       template<typename _Tp>
01123         __diff_type
01124         _M_bad_char_shift(_Tp __c) const
01125         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
01126 
01127       _RAIter _M_pat;
01128       _RAIter _M_pat_end;
01129     };
01130 
01131   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
01132     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
01133     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
01134                          _Hash __hf, _BinaryPredicate __pred)
01135     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
01136       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
01137     {
01138       auto __patlen = __pat_end - __pat;
01139       if (__patlen == 0)
01140         return;
01141       __diff_type __last_prefix = __patlen - 1;
01142       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
01143         {
01144           if (_M_is_prefix(__pat, __patlen, __p + 1))
01145             __last_prefix = __p + 1;
01146           _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
01147         }
01148       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
01149         {
01150           auto __slen = _M_suffix_length(__pat, __patlen, __p);
01151           auto __pos = __patlen - 1 - __slen;
01152           if (!__pred(__pat[__p - __slen], __pat[__pos]))
01153             _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
01154         }
01155     }
01156 
01157   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
01158   template<typename _RandomAccessIterator2>
01159     pair<_RandomAccessIterator2, _RandomAccessIterator2>
01160     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
01161     operator()(_RandomAccessIterator2 __first,
01162                _RandomAccessIterator2 __last) const
01163     {
01164       auto __patlen = _M_pat_end - _M_pat;
01165       if (__patlen == 0)
01166         return std::make_pair(__first, __first);
01167       const auto& __pred = this->_M_pred();
01168       __diff_type __i = __patlen - 1;
01169       auto __stringlen = __last - __first;
01170       while (__i < __stringlen)
01171         {
01172           __diff_type __j = __patlen - 1;
01173           while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
01174             {
01175               --__i;
01176               --__j;
01177             }
01178           if (__j < 0)
01179             {
01180               const auto __match = __first + __i + 1;
01181               return std::make_pair(__match, __match + __patlen);
01182             }
01183           __i += std::max(_M_bad_char_shift(__first[__i]),
01184                           _M_good_suffix[__j]);
01185         }
01186       return std::make_pair(__last, __last);
01187     }
01188 
01189 #endif // C++17
01190 #endif // C++14
01191 
01192 _GLIBCXX_END_NAMESPACE_VERSION
01193 } // namespace std
01194 
01195 #endif // C++11
01196 
01197 #endif // _GLIBCXX_FUNCTIONAL