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