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