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