libstdc++-v3/include/std/functional

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