visus
/
toolchain-gcc-arm-embedded
Watch 1
Star 0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commits
1 Branch
Branch: main
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'main'
${ noResults }
toolchain-gcc-arm-embedded/arm-none-eabi/include/c++/10.2.1/functional

1281 lines
39KB
Raw Permalink Blame History 

  1. // <functional> -*- C++ -*-

  2. 

  3. // Copyright (C) 2001-2020 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 <utility>

  65. # include <bits/stl_algo.h>

  66. #endif

  67. #if __cplusplus > 201703L

  68. # include <bits/range_cmp.h>

  69. # include <compare>

  70. #endif

  71. 

  72. namespace std _GLIBCXX_VISIBILITY(default)

  73. {

  74. _GLIBCXX_BEGIN_NAMESPACE_VERSION

  75. 

  76. #if __cplusplus >= 201703L

  77. # define __cpp_lib_invoke 201411L

  78. # if __cplusplus > 201703L

  79. #  define __cpp_lib_constexpr_functional 201907L

  80. # endif

  81. 

  82.   /// Invoke a callable object.

  83.   template<typename _Callable, typename... _Args>

  84.     inline _GLIBCXX20_CONSTEXPR invoke_result_t<_Callable, _Args...>

  85.     invoke(_Callable&& __fn, _Args&&... __args)

  86.     noexcept(is_nothrow_invocable_v<_Callable, _Args...>)

  87.     {

  88.       return std::__invoke(std::forward<_Callable>(__fn),

  89. 			   std::forward<_Args>(__args)...);

  90.     }

  91. #endif // C++17

  92. 

  93.   template<typename _MemFunPtr,

  94. 	   bool __is_mem_fn = is_member_function_pointer<_MemFunPtr>::value>

  95.     class _Mem_fn_base

  96.     : public _Mem_fn_traits<_MemFunPtr>::__maybe_type

  97.     {

  98.       using _Traits = _Mem_fn_traits<_MemFunPtr>;

  99. 

  100.       using _Arity = typename _Traits::__arity;

  101.       using _Varargs = typename _Traits::__vararg;

  102. 

  103.       template<typename _Func, typename... _BoundArgs>

  104. 	friend struct _Bind_check_arity;

  105. 

  106.       _MemFunPtr _M_pmf;

  107. 

  108.     public:

  109. 

  110.       using result_type = typename _Traits::__result_type;

  111. 

  112.       explicit constexpr

  113.       _Mem_fn_base(_MemFunPtr __pmf) noexcept : _M_pmf(__pmf) { }

  114. 

  115.       template<typename... _Args>

  116. 	_GLIBCXX20_CONSTEXPR

  117. 	auto

  118. 	operator()(_Args&&... __args) const

  119. 	noexcept(noexcept(

  120. 	      std::__invoke(_M_pmf, std::forward<_Args>(__args)...)))

  121. 	-> decltype(std::__invoke(_M_pmf, std::forward<_Args>(__args)...))

  122. 	{ return std::__invoke(_M_pmf, std::forward<_Args>(__args)...); }

  123.     };

  124. 

  125.   // Partial specialization for member object pointers.

  126.   template<typename _MemObjPtr>

  127.     class _Mem_fn_base<_MemObjPtr, false>

  128.     {

  129.       using _Arity = integral_constant<size_t, 0>;

  130.       using _Varargs = false_type;

  131. 

  132.       template<typename _Func, typename... _BoundArgs>

  133. 	friend struct _Bind_check_arity;

  134. 

  135.       _MemObjPtr _M_pm;

  136. 

  137.     public:

  138.       explicit constexpr

  139.       _Mem_fn_base(_MemObjPtr __pm) noexcept : _M_pm(__pm) { }

  140. 

  141.       template<typename _Tp>

  142. 	_GLIBCXX20_CONSTEXPR

  143. 	auto

  144. 	operator()(_Tp&& __obj) const

  145. 	noexcept(noexcept(std::__invoke(_M_pm, std::forward<_Tp>(__obj))))

  146. 	-> decltype(std::__invoke(_M_pm, std::forward<_Tp>(__obj)))

  147. 	{ return std::__invoke(_M_pm, std::forward<_Tp>(__obj)); }

  148.     };

  149. 

  150.   template<typename _MemberPointer>

  151.     struct _Mem_fn; // undefined

  152. 

  153.   template<typename _Res, typename _Class>

  154.     struct _Mem_fn<_Res _Class::*>

  155.     : _Mem_fn_base<_Res _Class::*>

  156.     {

  157.       using _Mem_fn_base<_Res _Class::*>::_Mem_fn_base;

  158.     };

  159. 

  160.   // _GLIBCXX_RESOLVE_LIB_DEFECTS

  161.   // 2048.  Unnecessary mem_fn overloads

  162.   /**

  163.    *  @brief Returns a function object that forwards to the member

  164.    *  pointer @a pm.

  165.    *  @ingroup functors

  166.    */

  167.   template<typename _Tp, typename _Class>

  168.     _GLIBCXX20_CONSTEXPR

  169.     inline _Mem_fn<_Tp _Class::*>

  170.     mem_fn(_Tp _Class::* __pm) noexcept

  171.     {

  172.       return _Mem_fn<_Tp _Class::*>(__pm);

  173.     }

  174. 

  175.   /**

  176.    *  @brief Determines if the given type _Tp is a function object that

  177.    *  should be treated as a subexpression when evaluating calls to

  178.    *  function objects returned by bind().

  179.    *

  180.    *  C++11 [func.bind.isbind].

  181.    *  @ingroup binders

  182.    */

  183.   template<typename _Tp>

  184.     struct is_bind_expression

  185.     : public false_type { };

  186. 

  187.   /**

  188.    *  @brief Determines if the given type _Tp is a placeholder in a

  189.    *  bind() expression and, if so, which placeholder it is.

  190.    *

  191.    *  C++11 [func.bind.isplace].

  192.    *  @ingroup binders

  193.    */

  194.   template<typename _Tp>

  195.     struct is_placeholder

  196.     : public integral_constant<int, 0>

  197.     { };

  198. 

  199. #if __cplusplus > 201402L

  200.   template <typename _Tp> inline constexpr bool is_bind_expression_v

  201.     = is_bind_expression<_Tp>::value;

  202.   template <typename _Tp> inline constexpr int is_placeholder_v

  203.     = is_placeholder<_Tp>::value;

  204. #endif // C++17

  205. 

  206.   /** @brief The type of placeholder objects defined by libstdc++.

  207.    *  @ingroup binders

  208.    */

  209.   template<int _Num> struct _Placeholder { };

  210. 

  211.   /** @namespace std::placeholders

  212.    *  @brief ISO C++ 2011 namespace for std::bind placeholders.

  213.    *  @ingroup binders

  214.    */

  215.   namespace placeholders

  216.   {

  217.   /* Define a large number of placeholders. There is no way to

  218.    * simplify this with variadic templates, because we're introducing

  219.    * unique names for each.

  220.    */

  221.     extern const _Placeholder<1> _1;

  222.     extern const _Placeholder<2> _2;

  223.     extern const _Placeholder<3> _3;

  224.     extern const _Placeholder<4> _4;

  225.     extern const _Placeholder<5> _5;

  226.     extern const _Placeholder<6> _6;

  227.     extern const _Placeholder<7> _7;

  228.     extern const _Placeholder<8> _8;

  229.     extern const _Placeholder<9> _9;

  230.     extern const _Placeholder<10> _10;

  231.     extern const _Placeholder<11> _11;

  232.     extern const _Placeholder<12> _12;

  233.     extern const _Placeholder<13> _13;

  234.     extern const _Placeholder<14> _14;

  235.     extern const _Placeholder<15> _15;

  236.     extern const _Placeholder<16> _16;

  237.     extern const _Placeholder<17> _17;

  238.     extern const _Placeholder<18> _18;

  239.     extern const _Placeholder<19> _19;

  240.     extern const _Placeholder<20> _20;

  241.     extern const _Placeholder<21> _21;

  242.     extern const _Placeholder<22> _22;

  243.     extern const _Placeholder<23> _23;

  244.     extern const _Placeholder<24> _24;

  245.     extern const _Placeholder<25> _25;

  246.     extern const _Placeholder<26> _26;

  247.     extern const _Placeholder<27> _27;

  248.     extern const _Placeholder<28> _28;

  249.     extern const _Placeholder<29> _29;

  250.   }

  251. 

  252.   /**

  253.    *  Partial specialization of is_placeholder that provides the placeholder

  254.    *  number for the placeholder objects defined by libstdc++.

  255.    *  @ingroup binders

  256.    */

  257.   template<int _Num>

  258.     struct is_placeholder<_Placeholder<_Num> >

  259.     : public integral_constant<int, _Num>

  260.     { };

  261. 

  262.   template<int _Num>

  263.     struct is_placeholder<const _Placeholder<_Num> >

  264.     : public integral_constant<int, _Num>

  265.     { };

  266. 

  267. 

  268.   // Like tuple_element_t but SFINAE-friendly.

  269.   template<std::size_t __i, typename _Tuple>

  270.     using _Safe_tuple_element_t

  271.       = typename enable_if<(__i < tuple_size<_Tuple>::value),

  272. 			   tuple_element<__i, _Tuple>>::type::type;

  273. 

  274.   /**

  275.    *  Maps an argument to bind() into an actual argument to the bound

  276.    *  function object [func.bind.bind]/10. Only the first parameter should

  277.    *  be specified: the rest are used to determine among the various

  278.    *  implementations. Note that, although this class is a function

  279.    *  object, it isn't entirely normal because it takes only two

  280.    *  parameters regardless of the number of parameters passed to the

  281.    *  bind expression. The first parameter is the bound argument and

  282.    *  the second parameter is a tuple containing references to the

  283.    *  rest of the arguments.

  284.    */

  285.   template<typename _Arg,

  286. 	   bool _IsBindExp = is_bind_expression<_Arg>::value,

  287. 	   bool _IsPlaceholder = (is_placeholder<_Arg>::value > 0)>

  288.     class _Mu;

  289. 

  290.   /**

  291.    *  If the argument is reference_wrapper<_Tp>, returns the

  292.    *  underlying reference.

  293.    *  C++11 [func.bind.bind] p10 bullet 1.

  294.    */

  295.   template<typename _Tp>

  296.     class _Mu<reference_wrapper<_Tp>, false, false>

  297.     {

  298.     public:

  299.       /* Note: This won't actually work for const volatile

  300.        * reference_wrappers, because reference_wrapper::get() is const

  301.        * but not volatile-qualified. This might be a defect in the TR.

  302.        */

  303.       template<typename _CVRef, typename _Tuple>

  304. 	_GLIBCXX20_CONSTEXPR

  305. 	_Tp&

  306. 	operator()(_CVRef& __arg, _Tuple&) const volatile

  307. 	{ return __arg.get(); }

  308.     };

  309. 

  310.   /**

  311.    *  If the argument is a bind expression, we invoke the underlying

  312.    *  function object with the same cv-qualifiers as we are given and

  313.    *  pass along all of our arguments (unwrapped).

  314.    *  C++11 [func.bind.bind] p10 bullet 2.

  315.    */

  316.   template<typename _Arg>

  317.     class _Mu<_Arg, true, false>

  318.     {

  319.     public:

  320.       template<typename _CVArg, typename... _Args>

  321. 	_GLIBCXX20_CONSTEXPR

  322. 	auto

  323. 	operator()(_CVArg& __arg,

  324. 		   tuple<_Args...>& __tuple) const volatile

  325. 	-> decltype(__arg(declval<_Args>()...))

  326. 	{

  327. 	  // Construct an index tuple and forward to __call

  328. 	  typedef typename _Build_index_tuple<sizeof...(_Args)>::__type

  329. 	    _Indexes;

  330. 	  return this->__call(__arg, __tuple, _Indexes());

  331. 	}

  332. 

  333.     private:

  334.       // Invokes the underlying function object __arg by unpacking all

  335.       // of the arguments in the tuple.

  336.       template<typename _CVArg, typename... _Args, std::size_t... _Indexes>

  337. 	_GLIBCXX20_CONSTEXPR

  338. 	auto

  339. 	__call(_CVArg& __arg, tuple<_Args...>& __tuple,

  340. 	       const _Index_tuple<_Indexes...>&) const volatile

  341. 	-> decltype(__arg(declval<_Args>()...))

  342. 	{

  343. 	  return __arg(std::get<_Indexes>(std::move(__tuple))...);

  344. 	}

  345.     };

  346. 

  347.   /**

  348.    *  If the argument is a placeholder for the Nth argument, returns

  349.    *  a reference to the Nth argument to the bind function object.

  350.    *  C++11 [func.bind.bind] p10 bullet 3.

  351.    */

  352.   template<typename _Arg>

  353.     class _Mu<_Arg, false, true>

  354.     {

  355.     public:

  356.       template<typename _Tuple>

  357. 	_GLIBCXX20_CONSTEXPR

  358. 	_Safe_tuple_element_t<(is_placeholder<_Arg>::value - 1), _Tuple>&&

  359. 	operator()(const volatile _Arg&, _Tuple& __tuple) const volatile

  360. 	{

  361. 	  return

  362. 	    ::std::get<(is_placeholder<_Arg>::value - 1)>(std::move(__tuple));

  363. 	}

  364.     };

  365. 

  366.   /**

  367.    *  If the argument is just a value, returns a reference to that

  368.    *  value. The cv-qualifiers on the reference are determined by the caller.

  369.    *  C++11 [func.bind.bind] p10 bullet 4.

  370.    */

  371.   template<typename _Arg>

  372.     class _Mu<_Arg, false, false>

  373.     {

  374.     public:

  375.       template<typename _CVArg, typename _Tuple>

  376. 	_GLIBCXX20_CONSTEXPR

  377. 	_CVArg&&

  378. 	operator()(_CVArg&& __arg, _Tuple&) const volatile

  379. 	{ return std::forward<_CVArg>(__arg); }

  380.     };

  381. 

  382.   // std::get<I> for volatile-qualified tuples

  383.   template<std::size_t _Ind, typename... _Tp>

  384.     inline auto

  385.     __volget(volatile tuple<_Tp...>& __tuple)

  386.     -> __tuple_element_t<_Ind, tuple<_Tp...>> volatile&

  387.     { return std::get<_Ind>(const_cast<tuple<_Tp...>&>(__tuple)); }

  388. 

  389.   // std::get<I> for const-volatile-qualified tuples

  390.   template<std::size_t _Ind, typename... _Tp>

  391.     inline auto

  392.     __volget(const volatile tuple<_Tp...>& __tuple)

  393.     -> __tuple_element_t<_Ind, tuple<_Tp...>> const volatile&

  394.     { return std::get<_Ind>(const_cast<const tuple<_Tp...>&>(__tuple)); }

  395. 

  396.   /// Type of the function object returned from bind().

  397.   template<typename _Signature>

  398.     struct _Bind;

  399. 

  400.    template<typename _Functor, typename... _Bound_args>

  401.     class _Bind<_Functor(_Bound_args...)>

  402.     : public _Weak_result_type<_Functor>

  403.     {

  404.       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type

  405. 	_Bound_indexes;

  406. 

  407.       _Functor _M_f;

  408.       tuple<_Bound_args...> _M_bound_args;

  409. 

  410.       // Call unqualified

  411.       template<typename _Result, typename... _Args, std::size_t... _Indexes>

  412. 	_GLIBCXX20_CONSTEXPR

  413. 	_Result

  414. 	__call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)

  415. 	{

  416. 	  return std::__invoke(_M_f,

  417. 	      _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...

  418. 	      );

  419. 	}

  420. 

  421.       // Call as const

  422.       template<typename _Result, typename... _Args, std::size_t... _Indexes>

  423. 	_GLIBCXX20_CONSTEXPR

  424. 	_Result

  425. 	__call_c(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const

  426. 	{

  427. 	  return std::__invoke(_M_f,

  428. 	      _Mu<_Bound_args>()(std::get<_Indexes>(_M_bound_args), __args)...

  429. 	      );

  430. 	}

  431. 

  432.       // Call as volatile

  433.       template<typename _Result, typename... _Args, std::size_t... _Indexes>

  434. 	_Result

  435. 	__call_v(tuple<_Args...>&& __args,

  436. 		 _Index_tuple<_Indexes...>) volatile

  437. 	{

  438. 	  return std::__invoke(_M_f,

  439. 	      _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...

  440. 	      );

  441. 	}

  442. 

  443.       // Call as const volatile

  444.       template<typename _Result, typename... _Args, std::size_t... _Indexes>

  445. 	_Result

  446. 	__call_c_v(tuple<_Args...>&& __args,

  447. 		   _Index_tuple<_Indexes...>) const volatile

  448. 	{

  449. 	  return std::__invoke(_M_f,

  450. 	      _Mu<_Bound_args>()(__volget<_Indexes>(_M_bound_args), __args)...

  451. 	      );

  452. 	}

  453. 

  454.       template<typename _BoundArg, typename _CallArgs>

  455. 	using _Mu_type = decltype(

  456. 	    _Mu<typename remove_cv<_BoundArg>::type>()(

  457. 	      std::declval<_BoundArg&>(), std::declval<_CallArgs&>()) );

  458. 

  459.       template<typename _Fn, typename _CallArgs, typename... _BArgs>

  460. 	using _Res_type_impl

  461. 	  = typename result_of< _Fn&(_Mu_type<_BArgs, _CallArgs>&&...) >::type;

  462. 

  463.       template<typename _CallArgs>

  464. 	using _Res_type = _Res_type_impl<_Functor, _CallArgs, _Bound_args...>;

  465. 

  466.       template<typename _CallArgs>

  467. 	using __dependent = typename

  468. 	  enable_if<bool(tuple_size<_CallArgs>::value+1), _Functor>::type;

  469. 

  470.       template<typename _CallArgs, template<class> class __cv_quals>

  471. 	using _Res_type_cv = _Res_type_impl<

  472. 	  typename __cv_quals<__dependent<_CallArgs>>::type,

  473. 	  _CallArgs,

  474. 	  typename __cv_quals<_Bound_args>::type...>;

  475. 

  476.      public:

  477.       template<typename... _Args>

  478. 	explicit _GLIBCXX20_CONSTEXPR

  479. 	_Bind(const _Functor& __f, _Args&&... __args)

  480. 	: _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)

  481. 	{ }

  482. 

  483.       template<typename... _Args>

  484. 	explicit _GLIBCXX20_CONSTEXPR

  485. 	_Bind(_Functor&& __f, _Args&&... __args)

  486. 	: _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)

  487. 	{ }

  488. 

  489.       _Bind(const _Bind&) = default;

  490.       _Bind(_Bind&&) = default;

  491. 

  492.       // Call unqualified

  493.       template<typename... _Args,

  494. 	       typename _Result = _Res_type<tuple<_Args...>>>

  495. 	_GLIBCXX20_CONSTEXPR

  496. 	_Result

  497. 	operator()(_Args&&... __args)

  498. 	{

  499. 	  return this->__call<_Result>(

  500. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  501. 	      _Bound_indexes());

  502. 	}

  503. 

  504.       // Call as const

  505.       template<typename... _Args,

  506. 	       typename _Result = _Res_type_cv<tuple<_Args...>, add_const>>

  507. 	_GLIBCXX20_CONSTEXPR

  508. 	_Result

  509. 	operator()(_Args&&... __args) const

  510. 	{

  511. 	  return this->__call_c<_Result>(

  512. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  513. 	      _Bound_indexes());

  514. 	}

  515. 

  516. #if __cplusplus > 201402L

  517. # define _GLIBCXX_DEPR_BIND \

  518.       [[deprecated("std::bind does not support volatile in C++17")]]

  519. #else

  520. # define _GLIBCXX_DEPR_BIND

  521. #endif

  522.       // Call as volatile

  523.       template<typename... _Args,

  524. 	       typename _Result = _Res_type_cv<tuple<_Args...>, add_volatile>>

  525. 	_GLIBCXX_DEPR_BIND

  526. 	_Result

  527. 	operator()(_Args&&... __args) volatile

  528. 	{

  529. 	  return this->__call_v<_Result>(

  530. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  531. 	      _Bound_indexes());

  532. 	}

  533. 

  534.       // Call as const volatile

  535.       template<typename... _Args,

  536. 	       typename _Result = _Res_type_cv<tuple<_Args...>, add_cv>>

  537. 	_GLIBCXX_DEPR_BIND

  538. 	_Result

  539. 	operator()(_Args&&... __args) const volatile

  540. 	{

  541. 	  return this->__call_c_v<_Result>(

  542. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  543. 	      _Bound_indexes());

  544. 	}

  545.     };

  546. 

  547.   /// Type of the function object returned from bind<R>().

  548.   template<typename _Result, typename _Signature>

  549.     struct _Bind_result;

  550. 

  551.   template<typename _Result, typename _Functor, typename... _Bound_args>

  552.     class _Bind_result<_Result, _Functor(_Bound_args...)>

  553.     {

  554.       typedef typename _Build_index_tuple<sizeof...(_Bound_args)>::__type

  555. 	_Bound_indexes;

  556. 

  557.       _Functor _M_f;

  558.       tuple<_Bound_args...> _M_bound_args;

  559. 

  560.       // Call unqualified

  561.       template<typename _Res, typename... _Args, std::size_t... _Indexes>

  562. 	_GLIBCXX20_CONSTEXPR

  563. 	_Res

  564. 	__call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>)

  565. 	{

  566. 	  return std::__invoke_r<_Res>(_M_f, _Mu<_Bound_args>()

  567. 		      (std::get<_Indexes>(_M_bound_args), __args)...);

  568. 	}

  569. 

  570.       // Call as const

  571.       template<typename _Res, typename... _Args, std::size_t... _Indexes>

  572. 	_GLIBCXX20_CONSTEXPR

  573. 	_Res

  574. 	__call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) const

  575. 	{

  576. 	  return std::__invoke_r<_Res>(_M_f, _Mu<_Bound_args>()

  577. 		      (std::get<_Indexes>(_M_bound_args), __args)...);

  578. 	}

  579. 

  580.       // Call as volatile

  581.       template<typename _Res, typename... _Args, std::size_t... _Indexes>

  582. 	_GLIBCXX20_CONSTEXPR

  583. 	_Res

  584. 	__call(tuple<_Args...>&& __args, _Index_tuple<_Indexes...>) volatile

  585. 	{

  586. 	  return std::__invoke_r<_Res>(_M_f, _Mu<_Bound_args>()

  587. 		      (__volget<_Indexes>(_M_bound_args), __args)...);

  588. 	}

  589. 

  590.       // Call as const volatile

  591.       template<typename _Res, typename... _Args, std::size_t... _Indexes>

  592. 	_GLIBCXX20_CONSTEXPR

  593. 	_Res

  594. 	__call(tuple<_Args...>&& __args,

  595. 	       _Index_tuple<_Indexes...>) const volatile

  596. 	{

  597. 	  return std::__invoke_r<_Res>(_M_f, _Mu<_Bound_args>()

  598. 		      (__volget<_Indexes>(_M_bound_args), __args)...);

  599. 	}

  600. 

  601.     public:

  602.       typedef _Result result_type;

  603. 

  604.       template<typename... _Args>

  605. 	explicit _GLIBCXX20_CONSTEXPR

  606. 	_Bind_result(const _Functor& __f, _Args&&... __args)

  607. 	: _M_f(__f), _M_bound_args(std::forward<_Args>(__args)...)

  608. 	{ }

  609. 

  610.       template<typename... _Args>

  611. 	explicit _GLIBCXX20_CONSTEXPR

  612. 	_Bind_result(_Functor&& __f, _Args&&... __args)

  613. 	: _M_f(std::move(__f)), _M_bound_args(std::forward<_Args>(__args)...)

  614. 	{ }

  615. 

  616.       _Bind_result(const _Bind_result&) = default;

  617.       _Bind_result(_Bind_result&&) = default;

  618. 

  619.       // Call unqualified

  620.       template<typename... _Args>

  621. 	_GLIBCXX20_CONSTEXPR

  622. 	result_type

  623. 	operator()(_Args&&... __args)

  624. 	{

  625. 	  return this->__call<_Result>(

  626. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  627. 	      _Bound_indexes());

  628. 	}

  629. 

  630.       // Call as const

  631.       template<typename... _Args>

  632. 	_GLIBCXX20_CONSTEXPR

  633. 	result_type

  634. 	operator()(_Args&&... __args) const

  635. 	{

  636. 	  return this->__call<_Result>(

  637. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  638. 	      _Bound_indexes());

  639. 	}

  640. 

  641.       // Call as volatile

  642.       template<typename... _Args>

  643. 	_GLIBCXX_DEPR_BIND

  644. 	result_type

  645. 	operator()(_Args&&... __args) volatile

  646. 	{

  647. 	  return this->__call<_Result>(

  648. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  649. 	      _Bound_indexes());

  650. 	}

  651. 

  652.       // Call as const volatile

  653.       template<typename... _Args>

  654. 	_GLIBCXX_DEPR_BIND

  655. 	result_type

  656. 	operator()(_Args&&... __args) const volatile

  657. 	{

  658. 	  return this->__call<_Result>(

  659. 	      std::forward_as_tuple(std::forward<_Args>(__args)...),

  660. 	      _Bound_indexes());

  661. 	}

  662.     };

  663. #undef _GLIBCXX_DEPR_BIND

  664. 

  665.   /**

  666.    *  @brief Class template _Bind is always a bind expression.

  667.    *  @ingroup binders

  668.    */

  669.   template<typename _Signature>

  670.     struct is_bind_expression<_Bind<_Signature> >

  671.     : public true_type { };

  672. 

  673.   /**

  674.    *  @brief Class template _Bind is always a bind expression.

  675.    *  @ingroup binders

  676.    */

  677.   template<typename _Signature>

  678.     struct is_bind_expression<const _Bind<_Signature> >

  679.     : public true_type { };

  680. 

  681.   /**

  682.    *  @brief Class template _Bind is always a bind expression.

  683.    *  @ingroup binders

  684.    */

  685.   template<typename _Signature>

  686.     struct is_bind_expression<volatile _Bind<_Signature> >

  687.     : public true_type { };

  688. 

  689.   /**

  690.    *  @brief Class template _Bind is always a bind expression.

  691.    *  @ingroup binders

  692.    */

  693.   template<typename _Signature>

  694.     struct is_bind_expression<const volatile _Bind<_Signature>>

  695.     : public true_type { };

  696. 

  697.   /**

  698.    *  @brief Class template _Bind_result is always a bind expression.

  699.    *  @ingroup binders

  700.    */

  701.   template<typename _Result, typename _Signature>

  702.     struct is_bind_expression<_Bind_result<_Result, _Signature>>

  703.     : public true_type { };

  704. 

  705.   /**

  706.    *  @brief Class template _Bind_result is always a bind expression.

  707.    *  @ingroup binders

  708.    */

  709.   template<typename _Result, typename _Signature>

  710.     struct is_bind_expression<const _Bind_result<_Result, _Signature>>

  711.     : public true_type { };

  712. 

  713.   /**

  714.    *  @brief Class template _Bind_result is always a bind expression.

  715.    *  @ingroup binders

  716.    */

  717.   template<typename _Result, typename _Signature>

  718.     struct is_bind_expression<volatile _Bind_result<_Result, _Signature>>

  719.     : public true_type { };

  720. 

  721.   /**

  722.    *  @brief Class template _Bind_result is always a bind expression.

  723.    *  @ingroup binders

  724.    */

  725.   template<typename _Result, typename _Signature>

  726.     struct is_bind_expression<const volatile _Bind_result<_Result, _Signature>>

  727.     : public true_type { };

  728. 

  729.   template<typename _Func, typename... _BoundArgs>

  730.     struct _Bind_check_arity { };

  731. 

  732.   template<typename _Ret, typename... _Args, typename... _BoundArgs>

  733.     struct _Bind_check_arity<_Ret (*)(_Args...), _BoundArgs...>

  734.     {

  735.       static_assert(sizeof...(_BoundArgs) == sizeof...(_Args),

  736.                    "Wrong number of arguments for function");

  737.     };

  738. 

  739.   template<typename _Ret, typename... _Args, typename... _BoundArgs>

  740.     struct _Bind_check_arity<_Ret (*)(_Args......), _BoundArgs...>

  741.     {

  742.       static_assert(sizeof...(_BoundArgs) >= sizeof...(_Args),

  743.                    "Wrong number of arguments for function");

  744.     };

  745. 

  746.   template<typename _Tp, typename _Class, typename... _BoundArgs>

  747.     struct _Bind_check_arity<_Tp _Class::*, _BoundArgs...>

  748.     {

  749.       using _Arity = typename _Mem_fn<_Tp _Class::*>::_Arity;

  750.       using _Varargs = typename _Mem_fn<_Tp _Class::*>::_Varargs;

  751.       static_assert(_Varargs::value

  752. 		    ? sizeof...(_BoundArgs) >= _Arity::value + 1

  753. 		    : sizeof...(_BoundArgs) == _Arity::value + 1,

  754. 		    "Wrong number of arguments for pointer-to-member");

  755.     };

  756. 

  757.   // Trait type used to remove std::bind() from overload set via SFINAE

  758.   // when first argument has integer type, so that std::bind() will

  759.   // not be a better match than ::bind() from the BSD Sockets API.

  760.   template<typename _Tp, typename _Tp2 = typename decay<_Tp>::type>

  761.     using __is_socketlike = __or_<is_integral<_Tp2>, is_enum<_Tp2>>;

  762. 

  763.   template<bool _SocketLike, typename _Func, typename... _BoundArgs>

  764.     struct _Bind_helper

  765.     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>

  766.     {

  767.       typedef typename decay<_Func>::type __func_type;

  768.       typedef _Bind<__func_type(typename decay<_BoundArgs>::type...)> type;

  769.     };

  770. 

  771.   // Partial specialization for is_socketlike == true, does not define

  772.   // nested type so std::bind() will not participate in overload resolution

  773.   // when the first argument might be a socket file descriptor.

  774.   template<typename _Func, typename... _BoundArgs>

  775.     struct _Bind_helper<true, _Func, _BoundArgs...>

  776.     { };

  777. 

  778.   /**

  779.    *  @brief Function template for std::bind.

  780.    *  @ingroup binders

  781.    */

  782.   template<typename _Func, typename... _BoundArgs>

  783.     inline _GLIBCXX20_CONSTEXPR typename

  784.     _Bind_helper<__is_socketlike<_Func>::value, _Func, _BoundArgs...>::type

  785.     bind(_Func&& __f, _BoundArgs&&... __args)

  786.     {

  787.       typedef _Bind_helper<false, _Func, _BoundArgs...> __helper_type;

  788.       return typename __helper_type::type(std::forward<_Func>(__f),

  789. 					  std::forward<_BoundArgs>(__args)...);

  790.     }

  791. 

  792.   template<typename _Result, typename _Func, typename... _BoundArgs>

  793.     struct _Bindres_helper

  794.     : _Bind_check_arity<typename decay<_Func>::type, _BoundArgs...>

  795.     {

  796.       typedef typename decay<_Func>::type __functor_type;

  797.       typedef _Bind_result<_Result,

  798. 			   __functor_type(typename decay<_BoundArgs>::type...)>

  799. 	type;

  800.     };

  801. 

  802.   /**

  803.    *  @brief Function template for std::bind<R>.

  804.    *  @ingroup binders

  805.    */

  806.   template<typename _Result, typename _Func, typename... _BoundArgs>

  807.     inline _GLIBCXX20_CONSTEXPR

  808.     typename _Bindres_helper<_Result, _Func, _BoundArgs...>::type

  809.     bind(_Func&& __f, _BoundArgs&&... __args)

  810.     {

  811.       typedef _Bindres_helper<_Result, _Func, _BoundArgs...> __helper_type;

  812.       return typename __helper_type::type(std::forward<_Func>(__f),

  813. 					  std::forward<_BoundArgs>(__args)...);

  814.     }

  815. 

  816. #if __cplusplus > 201703L

  817. #define __cpp_lib_bind_front 201907L

  818. 

  819.   template<typename _Fd, typename... _BoundArgs>

  820.     struct _Bind_front

  821.     {

  822.       static_assert(is_move_constructible_v<_Fd>);

  823.       static_assert((is_move_constructible_v<_BoundArgs> && ...));

  824. 

  825.       // First parameter is to ensure this constructor is never used

  826.       // instead of the copy/move constructor.

  827.       template<typename _Fn, typename... _Args>

  828. 	explicit constexpr

  829. 	_Bind_front(int, _Fn&& __fn, _Args&&... __args)

  830. 	noexcept(__and_<is_nothrow_constructible<_Fd, _Fn>,

  831. 			is_nothrow_constructible<_BoundArgs, _Args>...>::value)

  832. 	: _M_fd(std::forward<_Fn>(__fn)),

  833. 	  _M_bound_args(std::forward<_Args>(__args)...)

  834. 	{ static_assert(sizeof...(_Args) == sizeof...(_BoundArgs)); }

  835. 

  836.       _Bind_front(const _Bind_front&) = default;

  837.       _Bind_front(_Bind_front&&) = default;

  838.       _Bind_front& operator=(const _Bind_front&) = default;

  839.       _Bind_front& operator=(_Bind_front&&) = default;

  840.       ~_Bind_front() = default;

  841. 

  842.       template<typename... _CallArgs>

  843. 	constexpr

  844. 	invoke_result_t<_Fd&, _BoundArgs&..., _CallArgs...>

  845. 	operator()(_CallArgs&&... __call_args) &

  846. 	noexcept(is_nothrow_invocable_v<_Fd&, _BoundArgs&..., _CallArgs...>)

  847. 	{

  848. 	  return _S_call(*this, _BoundIndices(),

  849. 	      std::forward<_CallArgs>(__call_args)...);

  850. 	}

  851. 

  852.       template<typename... _CallArgs>

  853. 	constexpr

  854. 	invoke_result_t<const _Fd&, const _BoundArgs&..., _CallArgs...>

  855. 	operator()(_CallArgs&&... __call_args) const &

  856. 	noexcept(is_nothrow_invocable_v<const _Fd&, const _BoundArgs&...,

  857. 					_CallArgs...>)

  858. 	{

  859. 	  return _S_call(*this, _BoundIndices(),

  860. 	      std::forward<_CallArgs>(__call_args)...);

  861. 	}

  862. 

  863.       template<typename... _CallArgs>

  864. 	constexpr

  865. 	invoke_result_t<_Fd, _BoundArgs..., _CallArgs...>

  866. 	operator()(_CallArgs&&... __call_args) &&

  867. 	noexcept(is_nothrow_invocable_v<_Fd, _BoundArgs..., _CallArgs...>)

  868. 	{

  869. 	  return _S_call(std::move(*this), _BoundIndices(),

  870. 	      std::forward<_CallArgs>(__call_args)...);

  871. 	}

  872. 

  873.       template<typename... _CallArgs>

  874. 	constexpr

  875. 	invoke_result_t<const _Fd, const _BoundArgs..., _CallArgs...>

  876. 	operator()(_CallArgs&&... __call_args) const &&

  877. 	noexcept(is_nothrow_invocable_v<const _Fd, const _BoundArgs...,

  878. 					_CallArgs...>)

  879. 	{

  880. 	  return _S_call(std::move(*this), _BoundIndices(),

  881. 	      std::forward<_CallArgs>(__call_args)...);

  882. 	}

  883. 

  884.     private:

  885.       using _BoundIndices = index_sequence_for<_BoundArgs...>;

  886. 

  887.       template<typename _Tp, size_t... _Ind, typename... _CallArgs>

  888. 	static constexpr

  889. 	decltype(auto)

  890. 	_S_call(_Tp&& __g, index_sequence<_Ind...>, _CallArgs&&... __call_args)

  891. 	{

  892. 	  return std::invoke(std::forward<_Tp>(__g)._M_fd,

  893. 	      std::get<_Ind>(std::forward<_Tp>(__g)._M_bound_args)...,

  894. 	      std::forward<_CallArgs>(__call_args)...);

  895. 	}

  896. 

  897.       _Fd _M_fd;

  898.       std::tuple<_BoundArgs...> _M_bound_args;

  899.     };

  900. 

  901.   template<typename _Fn, typename... _Args>

  902.     using _Bind_front_t

  903.       = _Bind_front<decay_t<_Fn>, decay_t<_Args>...>;

  904. 

  905.   template<typename _Fn, typename... _Args>

  906.     constexpr _Bind_front_t<_Fn, _Args...>

  907.     bind_front(_Fn&& __fn, _Args&&... __args)

  908.     noexcept(is_nothrow_constructible_v<_Bind_front_t<_Fn, _Args...>,

  909. 					int, _Fn, _Args...>)

  910.     {

  911.       return _Bind_front_t<_Fn, _Args...>(0, std::forward<_Fn>(__fn),

  912. 					  std::forward<_Args>(__args)...);

  913.     }

  914. #endif

  915. 

  916. #if __cplusplus >= 201402L

  917.   /// Generalized negator.

  918.   template<typename _Fn>

  919.     class _Not_fn

  920.     {

  921.       template<typename _Fn2, typename... _Args>

  922. 	using __inv_res_t = typename __invoke_result<_Fn2, _Args...>::type;

  923. 

  924.       template<typename _Tp>

  925. 	static decltype(!std::declval<_Tp>())

  926. 	_S_not() noexcept(noexcept(!std::declval<_Tp>()));

  927. 

  928.     public:

  929.       template<typename _Fn2>

  930. 	constexpr

  931. 	_Not_fn(_Fn2&& __fn, int)

  932. 	: _M_fn(std::forward<_Fn2>(__fn)) { }

  933. 

  934.       _Not_fn(const _Not_fn& __fn) = default;

  935.       _Not_fn(_Not_fn&& __fn) = default;

  936.       ~_Not_fn() = default;

  937. 

  938.       // Macro to define operator() with given cv-qualifiers ref-qualifiers,

  939.       // forwarding _M_fn and the function arguments with the same qualifiers,

  940.       // and deducing the return type and exception-specification.

  941. #define _GLIBCXX_NOT_FN_CALL_OP( _QUALS )				\

  942.       template<typename... _Args>					\

  943. 	_GLIBCXX20_CONSTEXPR						\

  944. 	decltype(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>())		\

  945. 	operator()(_Args&&... __args) _QUALS				\

  946. 	noexcept(__is_nothrow_invocable<_Fn _QUALS, _Args...>::value	\

  947. 	    && noexcept(_S_not<__inv_res_t<_Fn _QUALS, _Args...>>()))	\

  948. 	{								\

  949. 	  return !std::__invoke(std::forward< _Fn _QUALS >(_M_fn),	\

  950. 				std::forward<_Args>(__args)...);	\

  951. 	}

  952.       _GLIBCXX_NOT_FN_CALL_OP( & )

  953.       _GLIBCXX_NOT_FN_CALL_OP( const & )

  954.       _GLIBCXX_NOT_FN_CALL_OP( && )

  955.       _GLIBCXX_NOT_FN_CALL_OP( const && )

  956. #undef _GLIBCXX_NOT_FN_CALL_OP

  957. 

  958.     private:

  959.       _Fn _M_fn;

  960.     };

  961. 

  962.   template<typename _Tp, typename _Pred>

  963.     struct __is_byte_like : false_type { };

  964. 

  965.   template<typename _Tp>

  966.     struct __is_byte_like<_Tp, equal_to<_Tp>>

  967.     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };

  968. 

  969.   template<typename _Tp>

  970.     struct __is_byte_like<_Tp, equal_to<void>>

  971.     : __bool_constant<sizeof(_Tp) == 1 && is_integral<_Tp>::value> { };

  972. 

  973. #if __cplusplus >= 201703L

  974.   // Declare std::byte (full definition is in <cstddef>).

  975.   enum class byte : unsigned char;

  976. 

  977.   template<>

  978.     struct __is_byte_like<byte, equal_to<byte>>

  979.     : true_type { };

  980. 

  981.   template<>

  982.     struct __is_byte_like<byte, equal_to<void>>

  983.     : true_type { };

  984. 

  985. #define __cpp_lib_not_fn 201603

  986.   /// [func.not_fn] Function template not_fn

  987.   template<typename _Fn>

  988.     _GLIBCXX20_CONSTEXPR

  989.     inline auto

  990.     not_fn(_Fn&& __fn)

  991.     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)

  992.     {

  993.       return _Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};

  994.     }

  995. 

  996.   // Searchers

  997. #define __cpp_lib_boyer_moore_searcher 201603

  998. 

  999.   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>

  1000.     class default_searcher

  1001.     {

  1002.     public:

  1003.       _GLIBCXX20_CONSTEXPR

  1004.       default_searcher(_ForwardIterator1 __pat_first,

  1005. 		       _ForwardIterator1 __pat_last,

  1006. 		       _BinaryPredicate __pred = _BinaryPredicate())

  1007.       : _M_m(__pat_first, __pat_last, std::move(__pred))

  1008.       { }

  1009. 

  1010.       template<typename _ForwardIterator2>

  1011. 	_GLIBCXX20_CONSTEXPR

  1012. 	pair<_ForwardIterator2, _ForwardIterator2>

  1013. 	operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const

  1014. 	{

  1015. 	  _ForwardIterator2 __first_ret =

  1016. 	    std::search(__first, __last, std::get<0>(_M_m), std::get<1>(_M_m),

  1017. 			std::get<2>(_M_m));

  1018. 	  auto __ret = std::make_pair(__first_ret, __first_ret);

  1019. 	  if (__ret.first != __last)

  1020. 	    std::advance(__ret.second, std::distance(std::get<0>(_M_m),

  1021. 						     std::get<1>(_M_m)));

  1022. 	  return __ret;

  1023. 	}

  1024. 

  1025.     private:

  1026.       tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;

  1027.     };

  1028. 

  1029.   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>

  1030.     struct __boyer_moore_map_base

  1031.     {

  1032.       template<typename _RAIter>

  1033. 	__boyer_moore_map_base(_RAIter __pat, size_t __patlen,

  1034. 			       _Hash&& __hf, _Pred&& __pred)

  1035. 	: _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }

  1036. 	{

  1037. 	  if (__patlen > 0)

  1038. 	    for (__diff_type __i = 0; __i < __patlen - 1; ++__i)

  1039. 	      _M_bad_char[__pat[__i]] = __patlen - 1 - __i;

  1040. 	}

  1041. 

  1042.       using __diff_type = _Tp;

  1043. 

  1044.       __diff_type

  1045.       _M_lookup(_Key __key, __diff_type __not_found) const

  1046.       {

  1047. 	auto __iter = _M_bad_char.find(__key);

  1048. 	if (__iter == _M_bad_char.end())

  1049. 	  return __not_found;

  1050. 	return __iter->second;

  1051.       }

  1052. 

  1053.       _Pred

  1054.       _M_pred() const { return _M_bad_char.key_eq(); }

  1055. 

  1056.       _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;

  1057.     };

  1058. 

  1059.   template<typename _Tp, size_t _Len, typename _Pred>

  1060.     struct __boyer_moore_array_base

  1061.     {

  1062.       template<typename _RAIter, typename _Unused>

  1063. 	__boyer_moore_array_base(_RAIter __pat, size_t __patlen,

  1064. 				 _Unused&&, _Pred&& __pred)

  1065. 	: _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }

  1066. 	{

  1067. 	  std::get<0>(_M_bad_char).fill(__patlen);

  1068. 	  if (__patlen > 0)

  1069. 	    for (__diff_type __i = 0; __i < __patlen - 1; ++__i)

  1070. 	      {

  1071. 		auto __ch = __pat[__i];

  1072. 		using _UCh = make_unsigned_t<decltype(__ch)>;

  1073. 		auto __uch = static_cast<_UCh>(__ch);

  1074. 		std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;

  1075. 	      }

  1076. 	}

  1077. 

  1078.       using __diff_type = _Tp;

  1079. 

  1080.       template<typename _Key>

  1081. 	__diff_type

  1082. 	_M_lookup(_Key __key, __diff_type __not_found) const

  1083. 	{

  1084. 	  auto __ukey = static_cast<make_unsigned_t<_Key>>(__key);

  1085. 	  if (__ukey >= _Len)

  1086. 	    return __not_found;

  1087. 	  return std::get<0>(_M_bad_char)[__ukey];

  1088. 	}

  1089. 

  1090.       const _Pred&

  1091.       _M_pred() const { return std::get<1>(_M_bad_char); }

  1092. 

  1093.       tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;

  1094.     };

  1095. 

  1096.   // Use __boyer_moore_array_base when pattern consists of narrow characters

  1097.   // (or std::byte) and uses std::equal_to as the predicate.

  1098.   template<typename _RAIter, typename _Hash, typename _Pred,

  1099.            typename _Val = typename iterator_traits<_RAIter>::value_type,

  1100. 	   typename _Diff = typename iterator_traits<_RAIter>::difference_type>

  1101.     using __boyer_moore_base_t

  1102.       = conditional_t<__is_byte_like<_Val, _Pred>::value,

  1103. 		      __boyer_moore_array_base<_Diff, 256, _Pred>,

  1104. 		      __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;

  1105. 

  1106.   template<typename _RAIter, typename _Hash

  1107. 	     = hash<typename iterator_traits<_RAIter>::value_type>,

  1108. 	   typename _BinaryPredicate = equal_to<>>

  1109.     class boyer_moore_searcher

  1110.     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>

  1111.     {

  1112.       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;

  1113.       using typename _Base::__diff_type;

  1114. 

  1115.     public:

  1116.       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,

  1117. 			   _Hash __hf = _Hash(),

  1118. 			   _BinaryPredicate __pred = _BinaryPredicate());

  1119. 

  1120.       template<typename _RandomAccessIterator2>

  1121.         pair<_RandomAccessIterator2, _RandomAccessIterator2>

  1122. 	operator()(_RandomAccessIterator2 __first,

  1123. 		   _RandomAccessIterator2 __last) const;

  1124. 

  1125.     private:

  1126.       bool

  1127.       _M_is_prefix(_RAIter __word, __diff_type __len,

  1128. 		   __diff_type __pos)

  1129.       {

  1130. 	const auto& __pred = this->_M_pred();

  1131. 	__diff_type __suffixlen = __len - __pos;

  1132. 	for (__diff_type __i = 0; __i < __suffixlen; ++__i)

  1133. 	  if (!__pred(__word[__i], __word[__pos + __i]))

  1134. 	    return false;

  1135. 	return true;

  1136.       }

  1137. 

  1138.       __diff_type

  1139.       _M_suffix_length(_RAIter __word, __diff_type __len,

  1140. 		       __diff_type __pos)

  1141.       {

  1142. 	const auto& __pred = this->_M_pred();

  1143. 	__diff_type __i = 0;

  1144. 	while (__pred(__word[__pos - __i], __word[__len - 1 - __i])

  1145. 	       && __i < __pos)

  1146. 	  {

  1147. 	    ++__i;

  1148. 	  }

  1149. 	return __i;

  1150.       }

  1151. 

  1152.       template<typename _Tp>

  1153. 	__diff_type

  1154. 	_M_bad_char_shift(_Tp __c) const

  1155. 	{ return this->_M_lookup(__c, _M_pat_end - _M_pat); }

  1156. 

  1157.       _RAIter _M_pat;

  1158.       _RAIter _M_pat_end;

  1159.       _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;

  1160.     };

  1161. 

  1162.   template<typename _RAIter, typename _Hash

  1163. 	     = hash<typename iterator_traits<_RAIter>::value_type>,

  1164. 	   typename _BinaryPredicate = equal_to<>>

  1165.     class boyer_moore_horspool_searcher

  1166.     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>

  1167.     {

  1168.       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;

  1169.       using typename _Base::__diff_type;

  1170. 

  1171.     public:

  1172.       boyer_moore_horspool_searcher(_RAIter __pat,

  1173. 				    _RAIter __pat_end,

  1174. 				    _Hash __hf = _Hash(),

  1175. 				    _BinaryPredicate __pred

  1176. 				    = _BinaryPredicate())

  1177.       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),

  1178. 	_M_pat(__pat), _M_pat_end(__pat_end)

  1179.       { }

  1180. 

  1181.       template<typename _RandomAccessIterator2>

  1182.         pair<_RandomAccessIterator2, _RandomAccessIterator2>

  1183. 	operator()(_RandomAccessIterator2 __first,

  1184. 		   _RandomAccessIterator2 __last) const

  1185. 	{

  1186. 	  const auto& __pred = this->_M_pred();

  1187. 	  auto __patlen = _M_pat_end - _M_pat;

  1188. 	  if (__patlen == 0)

  1189. 	    return std::make_pair(__first, __first);

  1190. 	  auto __len = __last - __first;

  1191. 	  while (__len >= __patlen)

  1192. 	    {

  1193. 	      for (auto __scan = __patlen - 1;

  1194. 		   __pred(__first[__scan], _M_pat[__scan]); --__scan)

  1195. 		if (__scan == 0)

  1196. 		  return std::make_pair(__first, __first + __patlen);

  1197. 	      auto __shift = _M_bad_char_shift(__first[__patlen - 1]);

  1198. 	      __len -= __shift;

  1199. 	      __first += __shift;

  1200. 	    }

  1201. 	  return std::make_pair(__last, __last);

  1202. 	}

  1203. 

  1204.     private:

  1205.       template<typename _Tp>

  1206. 	__diff_type

  1207. 	_M_bad_char_shift(_Tp __c) const

  1208. 	{ return this->_M_lookup(__c, _M_pat_end - _M_pat); }

  1209. 

  1210.       _RAIter _M_pat;

  1211.       _RAIter _M_pat_end;

  1212.     };

  1213. 

  1214.   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>

  1215.     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::

  1216.     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,

  1217. 			 _Hash __hf, _BinaryPredicate __pred)

  1218.     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),

  1219.       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)

  1220.     {

  1221.       auto __patlen = __pat_end - __pat;

  1222.       if (__patlen == 0)

  1223. 	return;

  1224.       __diff_type __last_prefix = __patlen - 1;

  1225.       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)

  1226. 	{

  1227. 	  if (_M_is_prefix(__pat, __patlen, __p + 1))

  1228. 	    __last_prefix = __p + 1;

  1229. 	  _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);

  1230. 	}

  1231.       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)

  1232. 	{

  1233. 	  auto __slen = _M_suffix_length(__pat, __patlen, __p);

  1234. 	  auto __pos = __patlen - 1 - __slen;

  1235. 	  if (!__pred(__pat[__p - __slen], __pat[__pos]))

  1236. 	    _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;

  1237. 	}

  1238.     }

  1239. 

  1240.   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>

  1241.   template<typename _RandomAccessIterator2>

  1242.     pair<_RandomAccessIterator2, _RandomAccessIterator2>

  1243.     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::

  1244.     operator()(_RandomAccessIterator2 __first,

  1245. 	       _RandomAccessIterator2 __last) const

  1246.     {

  1247.       auto __patlen = _M_pat_end - _M_pat;

  1248.       if (__patlen == 0)

  1249. 	return std::make_pair(__first, __first);

  1250.       const auto& __pred = this->_M_pred();

  1251.       __diff_type __i = __patlen - 1;

  1252.       auto __stringlen = __last - __first;

  1253.       while (__i < __stringlen)

  1254. 	{

  1255. 	  __diff_type __j = __patlen - 1;

  1256. 	  while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))

  1257. 	    {

  1258. 	      --__i;

  1259. 	      --__j;

  1260. 	    }

  1261. 	  if (__j < 0)

  1262. 	    {

  1263. 	      const auto __match = __first + __i + 1;

  1264. 	      return std::make_pair(__match, __match + __patlen);

  1265. 	    }

  1266. 	  __i += std::max(_M_bad_char_shift(__first[__i]),

  1267. 			  _M_good_suffix[__j]);

  1268. 	}

  1269.       return std::make_pair(__last, __last);

  1270.     }

  1271. 

  1272. #endif // C++17

  1273. #endif // C++14

  1274. 

  1275. _GLIBCXX_END_NAMESPACE_VERSION

  1276. } // namespace std

  1277. 

  1278. #endif // C++11

  1279. 

  1280. #endif // _GLIBCXX_FUNCTIONAL