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