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