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