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