libstdc++
functional
Go to the documentation of this file.
00001 // <functional> -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2019 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 > 201703L
00840 #define __cpp_lib_bind_front 201902L
00841 
00842   template<typename _Fd, typename... _BoundArgs>
00843     struct _Bind_front
00844     {
00845       static_assert(is_move_constructible_v<_Fd>);
00846       static_assert((is_move_constructible_v<_BoundArgs> && ...));
00847 
00848       // First parameter is to ensure this constructor is never used
00849       // instead of the copy/move constructor.
00850       template<typename _Fn, typename... _Args>
00851         explicit constexpr
00852         _Bind_front(int, _Fn&& __fn, _Args&&... __args)
00853         noexcept(__and_<is_nothrow_constructible<_Fd, _Fn>,
00854                         is_nothrow_constructible<_BoundArgs, _Args>...>::value)
00855         : _M_fd(std::forward<_Fn>(__fn)),
00856           _M_bound_args(std::forward<_Args>(__args)...)
00857         { static_assert(sizeof...(_Args) == sizeof...(_BoundArgs)); }
00858 
00859       _Bind_front(const _Bind_front&) = default;
00860       _Bind_front(_Bind_front&&) = default;
00861       _Bind_front& operator=(const _Bind_front&) = default;
00862       _Bind_front& operator=(_Bind_front&&) = default;
00863       ~_Bind_front() = default;
00864 
00865       template<typename... _CallArgs>
00866         constexpr
00867         invoke_result_t<_Fd&, _BoundArgs&..., _CallArgs...>
00868         operator()(_CallArgs&&... __call_args) &
00869         noexcept(is_nothrow_invocable_v<_Fd&, _BoundArgs&..., _CallArgs...>)
00870         {
00871           return _S_call(*this, _BoundIndices(),
00872               std::forward<_CallArgs>(__call_args)...);
00873         }
00874 
00875       template<typename... _CallArgs>
00876         constexpr
00877         invoke_result_t<const _Fd&, const _BoundArgs&..., _CallArgs...>
00878         operator()(_CallArgs&&... __call_args) const &
00879         noexcept(is_nothrow_invocable_v<const _Fd&, const _BoundArgs&...,
00880                                         _CallArgs...>)
00881         {
00882           return _S_call(*this, _BoundIndices(),
00883               std::forward<_CallArgs>(__call_args)...);
00884         }
00885 
00886       template<typename... _CallArgs>
00887         constexpr
00888         invoke_result_t<_Fd, _BoundArgs..., _CallArgs...>
00889         operator()(_CallArgs&&... __call_args) &&
00890         noexcept(is_nothrow_invocable_v<_Fd, _BoundArgs..., _CallArgs...>)
00891         {
00892           return _S_call(std::move(*this), _BoundIndices(),
00893               std::forward<_CallArgs>(__call_args)...);
00894         }
00895 
00896       template<typename... _CallArgs>
00897         constexpr
00898         invoke_result_t<const _Fd, const _BoundArgs..., _CallArgs...>
00899         operator()(_CallArgs&&... __call_args) const &&
00900         noexcept(is_nothrow_invocable_v<const _Fd, const _BoundArgs...,
00901                                         _CallArgs...>)
00902         {
00903           return _S_call(std::move(*this), _BoundIndices(),
00904               std::forward<_CallArgs>(__call_args)...);
00905         }
00906 
00907     private:
00908       using _BoundIndices = index_sequence_for<_BoundArgs...>;
00909 
00910       template<typename _Tp, size_t... _Ind, typename... _CallArgs>
00911         static constexpr
00912         decltype(auto)
00913         _S_call(_Tp&& __g, index_sequence<_Ind...>, _CallArgs&&... __call_args)
00914         {
00915           return std::invoke(std::forward<_Tp>(__g)._M_fd,
00916               std::get<_Ind>(std::forward<_Tp>(__g)._M_bound_args)...,
00917               std::forward<_CallArgs>(__call_args)...);
00918         }
00919 
00920       _Fd _M_fd;
00921       std::tuple<_BoundArgs...> _M_bound_args;
00922     };
00923 
00924   template<typename _Fn, typename... _Args>
00925     using _Bind_front_t
00926       = _Bind_front<decay_t<_Fn>, unwrap_ref_decay_t<_Args>...>;
00927 
00928   template<typename _Fn, typename... _Args>
00929     _Bind_front_t<_Fn, _Args...>
00930     bind_front(_Fn&& __fn, _Args&&... __args)
00931     noexcept(is_nothrow_constructible_v<int, _Bind_front_t<_Fn, _Args...>,
00932                                         _Fn, _Args...>)
00933     {
00934       return _Bind_front_t<_Fn, _Args...>(0, std::forward<_Fn>(__fn),
00935                                           std::forward<_Args>(__args)...);
00936     }
00937 #endif
00938 
00939 #if __cplusplus >= 201402L
00940   /// Generalized negator.
00941   template<typename _Fn>
00942     class _Not_fn
00943     {
00944       template<typename _Fn2, typename... _Args>
00945         using __inv_res_t = typename __invoke_result<_Fn2, _Args...>::type;
00946 
00947       template<typename _Tp>
00948         static decltype(!std::declval<_Tp>())
00949         _S_not() noexcept(noexcept(!std::declval<_Tp>()));
00950 
00951     public:
00952       template<typename _Fn2>
00953         _Not_fn(_Fn2&& __fn, int)
00954         : _M_fn(std::forward<_Fn2>(__fn)) { }
00955 
00956       _Not_fn(const _Not_fn& __fn) = default;
00957       _Not_fn(_Not_fn&& __fn) = default;
00958       ~_Not_fn() = default;
00959 
00960       // Macro to define operator() with given cv-qualifiers ref-qualifiers,
00961       // forwarding _M_fn and the function arguments with the same qualifiers,
00962       // and deducing the return type and exception-specification.
00963 #define _GLIBCXX_NOT_FN_CALL_OP( _QUALS )                               \
00964       template<typename... _Args>                                       \
00965         decltype(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>())           \
00966         operator()(_Args&&... __args) _QUALS                            \
00967         noexcept(__is_nothrow_invocable<_Fn _QUALS, _Args...>::value    \
00968             && noexcept(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>()))   \
00969         {                                                               \
00970           return !std::__invoke(std::forward< _Fn _QUALS >(_M_fn),      \
00971                                 std::forward<_Args>(__args)...);        \
00972         }
00973       _GLIBCXX_NOT_FN_CALL_OP( & )
00974       _GLIBCXX_NOT_FN_CALL_OP( const & )
00975       _GLIBCXX_NOT_FN_CALL_OP( && )
00976       _GLIBCXX_NOT_FN_CALL_OP( const && )
00977 #undef _GLIBCXX_NOT_FN_CALL
00978 
00979     private:
00980       _Fn _M_fn;
00981     };
00982 
00983   template<typename _Tp, typename _Pred>
00984     struct __is_byte_like : false_type { };
00985 
00986   template<typename _Tp>
00987     struct __is_byte_like<_Tp, equal_to<_Tp>>
00988     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
00989 
00990   template<typename _Tp>
00991     struct __is_byte_like<_Tp, equal_to<void>>
00992     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };
00993 
00994 #if __cplusplus >= 201703L
00995   // Declare std::byte (full definition is in <cstddef>).
00996   enum class byte : unsigned char;
00997 
00998   template<>
00999     struct __is_byte_like<byte, equal_to<byte>>
01000     : true_type { };
01001 
01002   template<>
01003     struct __is_byte_like<byte, equal_to<void>>
01004     : true_type { };
01005 
01006 #define __cpp_lib_not_fn 201603
01007   /// [func.not_fn] Function template not_fn
01008   template<typename _Fn>
01009     inline auto
01010     not_fn(_Fn&& __fn)
01011     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
01012     {
01013       return _Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
01014     }
01015 
01016   // Searchers
01017 #define __cpp_lib_boyer_moore_searcher 201603
01018 
01019   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
01020     class default_searcher
01021     {
01022     public:
01023       default_searcher(_ForwardIterator1 __pat_first,
01024                        _ForwardIterator1 __pat_last,
01025                        _BinaryPredicate __pred = _BinaryPredicate())
01026       : _M_m(__pat_first, __pat_last, std::move(__pred))
01027       { }
01028 
01029       template<typename _ForwardIterator2>
01030         pair<_ForwardIterator2, _ForwardIterator2>
01031         operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
01032         {
01033           _ForwardIterator2 __first_ret =
01034             std::search(__first, __last, std::get<0>(_M_m), std::get<1>(_M_m),
01035                         std::get<2>(_M_m));
01036           auto __ret = std::make_pair(__first_ret, __first_ret);
01037           if (__ret.first != __last)
01038             std::advance(__ret.second, std::distance(std::get<0>(_M_m),
01039                                                      std::get<1>(_M_m)));
01040           return __ret;
01041         }
01042 
01043     private:
01044       tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
01045     };
01046 
01047   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
01048     struct __boyer_moore_map_base
01049     {
01050       template<typename _RAIter>
01051         __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
01052                                _Hash&& __hf, _Pred&& __pred)
01053         : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
01054         {
01055           if (__patlen > 0)
01056             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
01057               _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
01058         }
01059 
01060       using __diff_type = _Tp;
01061 
01062       __diff_type
01063       _M_lookup(_Key __key, __diff_type __not_found) const
01064       {
01065         auto __iter = _M_bad_char.find(__key);
01066         if (__iter == _M_bad_char.end())
01067           return __not_found;
01068         return __iter->second;
01069       }
01070 
01071       _Pred
01072       _M_pred() const { return _M_bad_char.key_eq(); }
01073 
01074       _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
01075     };
01076 
01077   template<typename _Tp, size_t _Len, typename _Pred>
01078     struct __boyer_moore_array_base
01079     {
01080       template<typename _RAIter, typename _Unused>
01081         __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
01082                                  _Unused&&, _Pred&& __pred)
01083         : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
01084         {
01085           std::get<0>(_M_bad_char).fill(__patlen);
01086           if (__patlen > 0)
01087             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
01088               {
01089                 auto __ch = __pat[__i];
01090                 using _UCh = make_unsigned_t<decltype(__ch)>;
01091                 auto __uch = static_cast<_UCh>(__ch);
01092                 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
01093               }
01094         }
01095 
01096       using __diff_type = _Tp;
01097 
01098       template<typename _Key>
01099         __diff_type
01100         _M_lookup(_Key __key, __diff_type __not_found) const
01101         {
01102           auto __ukey = static_cast<make_unsigned_t<_Key>>(__key);
01103           if (__ukey >= _Len)
01104             return __not_found;
01105           return std::get<0>(_M_bad_char)[__ukey];
01106         }
01107 
01108       const _Pred&
01109       _M_pred() const { return std::get<1>(_M_bad_char); }
01110 
01111       tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;
01112     };
01113 
01114   // Use __boyer_moore_array_base when pattern consists of narrow characters
01115   // (or std::byte) and uses std::equal_to as the predicate.
01116   template<typename _RAIter, typename _Hash, typename _Pred,
01117            typename _Val = typename iterator_traits<_RAIter>::value_type,
01118            typename _Diff = typename iterator_traits<_RAIter>::difference_type>
01119     using __boyer_moore_base_t
01120       = conditional_t<__is_byte_like<_Val, _Pred>::value,
01121                       __boyer_moore_array_base<_Diff, 256, _Pred>,
01122                       __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
01123 
01124   template<typename _RAIter, typename _Hash
01125              = hash<typename iterator_traits<_RAIter>::value_type>,
01126            typename _BinaryPredicate = equal_to<>>
01127     class boyer_moore_searcher
01128     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
01129     {
01130       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
01131       using typename _Base::__diff_type;
01132 
01133     public:
01134       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
01135                            _Hash __hf = _Hash(),
01136                            _BinaryPredicate __pred = _BinaryPredicate());
01137 
01138       template<typename _RandomAccessIterator2>
01139         pair<_RandomAccessIterator2, _RandomAccessIterator2>
01140         operator()(_RandomAccessIterator2 __first,
01141                    _RandomAccessIterator2 __last) const;
01142 
01143     private:
01144       bool
01145       _M_is_prefix(_RAIter __word, __diff_type __len,
01146                    __diff_type __pos)
01147       {
01148         const auto& __pred = this->_M_pred();
01149         __diff_type __suffixlen = __len - __pos;
01150         for (__diff_type __i = 0; __i < __suffixlen; ++__i)
01151           if (!__pred(__word[__i], __word[__pos + __i]))
01152             return false;
01153         return true;
01154       }
01155 
01156       __diff_type
01157       _M_suffix_length(_RAIter __word, __diff_type __len,
01158                        __diff_type __pos)
01159       {
01160         const auto& __pred = this->_M_pred();
01161         __diff_type __i = 0;
01162         while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
01163                && __i < __pos)
01164           {
01165             ++__i;
01166           }
01167         return __i;
01168       }
01169 
01170       template<typename _Tp>
01171         __diff_type
01172         _M_bad_char_shift(_Tp __c) const
01173         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
01174 
01175       _RAIter _M_pat;
01176       _RAIter _M_pat_end;
01177       _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
01178     };
01179 
01180   template<typename _RAIter, typename _Hash
01181              = hash<typename iterator_traits<_RAIter>::value_type>,
01182            typename _BinaryPredicate = equal_to<>>
01183     class boyer_moore_horspool_searcher
01184     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
01185     {
01186       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
01187       using typename _Base::__diff_type;
01188 
01189     public:
01190       boyer_moore_horspool_searcher(_RAIter __pat,
01191                                     _RAIter __pat_end,
01192                                     _Hash __hf = _Hash(),
01193                                     _BinaryPredicate __pred
01194                                     = _BinaryPredicate())
01195       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
01196         _M_pat(__pat), _M_pat_end(__pat_end)
01197       { }
01198 
01199       template<typename _RandomAccessIterator2>
01200         pair<_RandomAccessIterator2, _RandomAccessIterator2>
01201         operator()(_RandomAccessIterator2 __first,
01202                    _RandomAccessIterator2 __last) const
01203         {
01204           const auto& __pred = this->_M_pred();
01205           auto __patlen = _M_pat_end - _M_pat;
01206           if (__patlen == 0)
01207             return std::make_pair(__first, __first);
01208           auto __len = __last - __first;
01209           while (__len >= __patlen)
01210             {
01211               for (auto __scan = __patlen - 1;
01212                    __pred(__first[__scan], _M_pat[__scan]); --__scan)
01213                 if (__scan == 0)
01214                   return std::make_pair(__first, __first + __patlen);
01215               auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
01216               __len -= __shift;
01217               __first += __shift;
01218             }
01219           return std::make_pair(__last, __last);
01220         }
01221 
01222     private:
01223       template<typename _Tp>
01224         __diff_type
01225         _M_bad_char_shift(_Tp __c) const
01226         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
01227 
01228       _RAIter _M_pat;
01229       _RAIter _M_pat_end;
01230     };
01231 
01232   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
01233     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
01234     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
01235                          _Hash __hf, _BinaryPredicate __pred)
01236     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
01237       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
01238     {
01239       auto __patlen = __pat_end - __pat;
01240       if (__patlen == 0)
01241         return;
01242       __diff_type __last_prefix = __patlen - 1;
01243       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
01244         {
01245           if (_M_is_prefix(__pat, __patlen, __p + 1))
01246             __last_prefix = __p + 1;
01247           _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
01248         }
01249       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
01250         {
01251           auto __slen = _M_suffix_length(__pat, __patlen, __p);
01252           auto __pos = __patlen - 1 - __slen;
01253           if (!__pred(__pat[__p - __slen], __pat[__pos]))
01254             _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
01255         }
01256     }
01257 
01258   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
01259   template<typename _RandomAccessIterator2>
01260     pair<_RandomAccessIterator2, _RandomAccessIterator2>
01261     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
01262     operator()(_RandomAccessIterator2 __first,
01263                _RandomAccessIterator2 __last) const
01264     {
01265       auto __patlen = _M_pat_end - _M_pat;
01266       if (__patlen == 0)
01267         return std::make_pair(__first, __first);
01268       const auto& __pred = this->_M_pred();
01269       __diff_type __i = __patlen - 1;
01270       auto __stringlen = __last - __first;
01271       while (__i < __stringlen)
01272         {
01273           __diff_type __j = __patlen - 1;
01274           while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
01275             {
01276               --__i;
01277               --__j;
01278             }
01279           if (__j < 0)
01280             {
01281               const auto __match = __first + __i + 1;
01282               return std::make_pair(__match, __match + __patlen);
01283             }
01284           __i += std::max(_M_bad_char_shift(__first[__i]),
01285                           _M_good_suffix[__j]);
01286         }
01287       return std::make_pair(__last, __last);
01288     }
01289 
01290 #endif // C++17
01291 #endif // C++14
01292 
01293 _GLIBCXX_END_NAMESPACE_VERSION
01294 } // namespace std
01295 
01296 #endif // C++11
01297 
01298 #endif // _GLIBCXX_FUNCTIONAL