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