libstdc++
stl_algobase.h
Go to the documentation of this file.
1 // Core algorithmic facilities -*- C++ -*-
2 
3 // Copyright (C) 2001-2026 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  *
27  * Copyright (c) 1994
28  * Hewlett-Packard Company
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation. Hewlett-Packard Company makes no
35  * representations about the suitability of this software for any
36  * purpose. It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1996-1998
40  * Silicon Graphics Computer Systems, Inc.
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation. Silicon Graphics makes no
47  * representations about the suitability of this software for any
48  * purpose. It is provided "as is" without express or implied warranty.
49  */
50 
51 /** @file bits/stl_algobase.h
52  * This is an internal header file, included by other library headers.
53  * Do not attempt to use it directly. @headername{algorithm}
54  */
55 
56 #ifndef _STL_ALGOBASE_H
57 #define _STL_ALGOBASE_H 1
58 
59 #include <bits/c++config.h>
60 #include <bits/cpp_type_traits.h>
61 #include <ext/type_traits.h>
62 #include <ext/numeric_traits.h>
63 #include <bits/stl_pair.h>
64 #include <bits/stl_iterator_base_types.h>
65 #include <bits/stl_iterator_base_funcs.h>
66 #include <bits/stl_iterator.h>
67 #include <bits/concept_check.h>
68 #include <debug/debug.h>
69 #include <bits/move.h> // For std::swap
70 #include <bits/predefined_ops.h>
71 #if __cplusplus >= 201103L
72 # include <type_traits>
73 #endif
74 #if __cplusplus >= 201402L
75 # include <bit> // std::__bit_width
76 #endif
77 #if __cplusplus >= 202002L
78 # include <compare>
79 # include <bits/ptr_traits.h> // std::to_address
80 #endif
81 
82 namespace std _GLIBCXX_VISIBILITY(default)
83 {
84 _GLIBCXX_BEGIN_NAMESPACE_VERSION
85 
86  /*
87  * A constexpr wrapper for __builtin_memcmp.
88  * @param __num The number of elements of type _Tp (not bytes).
89  */
90  template<typename _Tp, typename _Up>
91  _GLIBCXX14_CONSTEXPR
92  inline int
93  __memcmp(const _Tp* __first1, const _Up* __first2, size_t __num)
94  {
95 #if __cplusplus >= 201103L
96  static_assert(sizeof(_Tp) == sizeof(_Up), "can be compared with memcmp");
97 #endif
98 #ifdef __cpp_lib_is_constant_evaluated
99  if (std::is_constant_evaluated())
100  {
101  for(; __num > 0; ++__first1, ++__first2, --__num)
102  if (*__first1 != *__first2)
103  return *__first1 < *__first2 ? -1 : 1;
104  return 0;
105  }
106  else
107 #endif
108  return __builtin_memcmp(__first1, __first2, sizeof(_Tp) * __num);
109  }
110 
111 #if __cplusplus < 201103L
112  // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
113  // nutshell, we are partially implementing the resolution of DR 187,
114  // when it's safe, i.e., the value_types are equal.
115  template<bool _BoolType>
116  struct __iter_swap
117  {
118  template<typename _ForwardIterator1, typename _ForwardIterator2>
119  static void
120  iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
121  {
122  typedef typename iterator_traits<_ForwardIterator1>::value_type
123  _ValueType1;
124  _ValueType1 __tmp = *__a;
125  *__a = *__b;
126  *__b = __tmp;
127  }
128  };
129 
130  template<>
131  struct __iter_swap<true>
132  {
133  template<typename _ForwardIterator1, typename _ForwardIterator2>
134  static void
135  iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
136  {
137  swap(*__a, *__b);
138  }
139  };
140 #endif // C++03
141 
142  /**
143  * @brief Swaps the contents of two iterators.
144  * @ingroup mutating_algorithms
145  * @param __a An iterator.
146  * @param __b Another iterator.
147  * @return Nothing.
148  *
149  * This function swaps the values pointed to by two iterators, not the
150  * iterators themselves.
151  */
152  template<typename _ForwardIterator1, typename _ForwardIterator2>
153  _GLIBCXX20_CONSTEXPR
154  inline void
155  iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
156  {
157  // concept requirements
158  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
159  _ForwardIterator1>)
160  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
161  _ForwardIterator2>)
162 
163 #if __cplusplus < 201103L
164  typedef typename iterator_traits<_ForwardIterator1>::value_type
165  _ValueType1;
166  typedef typename iterator_traits<_ForwardIterator2>::value_type
167  _ValueType2;
168 
169  __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
170  _ValueType2>)
171  __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
172  _ValueType1>)
173 
174  typedef typename iterator_traits<_ForwardIterator1>::reference
175  _ReferenceType1;
176  typedef typename iterator_traits<_ForwardIterator2>::reference
177  _ReferenceType2;
178  std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
179  && __are_same<_ValueType1&, _ReferenceType1>::__value
180  && __are_same<_ValueType2&, _ReferenceType2>::__value>::
181  iter_swap(__a, __b);
182 #else
183  // _GLIBCXX_RESOLVE_LIB_DEFECTS
184  // 187. iter_swap underspecified
185  swap(*__a, *__b);
186 #endif
187  }
188 
189  /**
190  * @brief Swap the elements of two sequences.
191  * @ingroup mutating_algorithms
192  * @param __first1 A forward iterator.
193  * @param __last1 A forward iterator.
194  * @param __first2 A forward iterator.
195  * @return An iterator equal to @p first2+(last1-first1).
196  *
197  * Swaps each element in the range @p [first1,last1) with the
198  * corresponding element in the range @p [first2,(last1-first1)).
199  * The ranges must not overlap.
200  */
201  template<typename _ForwardIterator1, typename _ForwardIterator2>
202  _GLIBCXX20_CONSTEXPR
203  _ForwardIterator2
204  swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
205  _ForwardIterator2 __first2)
206  {
207  // concept requirements
208  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
209  _ForwardIterator1>)
210  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
211  _ForwardIterator2>)
212  __glibcxx_requires_valid_range(__first1, __last1);
213 
214  for (; __first1 != __last1; ++__first1, (void)++__first2)
215  std::iter_swap(__first1, __first2);
216  return __first2;
217  }
218 
219  /**
220  * @brief This does what you think it does.
221  * @ingroup sorting_algorithms
222  * @param __a A thing of arbitrary type.
223  * @param __b Another thing of arbitrary type.
224  * @return The lesser of the parameters.
225  *
226  * This is the simple classic generic implementation. It will work on
227  * temporary expressions, since they are only evaluated once, unlike a
228  * preprocessor macro.
229  */
230  template<typename _Tp>
231  _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
232  inline const _Tp&
233  min(const _Tp& __a, const _Tp& __b)
234  {
235  // concept requirements
236  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
237  //return __b < __a ? __b : __a;
238  if (__b < __a)
239  return __b;
240  return __a;
241  }
242 
243  /**
244  * @brief This does what you think it does.
245  * @ingroup sorting_algorithms
246  * @param __a A thing of arbitrary type.
247  * @param __b Another thing of arbitrary type.
248  * @return The greater of the parameters.
249  *
250  * This is the simple classic generic implementation. It will work on
251  * temporary expressions, since they are only evaluated once, unlike a
252  * preprocessor macro.
253  */
254  template<typename _Tp>
255  _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
256  inline const _Tp&
257  max(const _Tp& __a, const _Tp& __b)
258  {
259  // concept requirements
260  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
261  //return __a < __b ? __b : __a;
262  if (__a < __b)
263  return __b;
264  return __a;
265  }
266 
267  /**
268  * @brief This does what you think it does.
269  * @ingroup sorting_algorithms
270  * @param __a A thing of arbitrary type.
271  * @param __b Another thing of arbitrary type.
272  * @param __comp A @link comparison_functors comparison functor@endlink.
273  * @return The lesser of the parameters.
274  *
275  * This will work on temporary expressions, since they are only evaluated
276  * once, unlike a preprocessor macro.
277  */
278  template<typename _Tp, typename _Compare>
279  _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
280  inline const _Tp&
281  min(const _Tp& __a, const _Tp& __b, _Compare __comp)
282  {
283  //return __comp(__b, __a) ? __b : __a;
284  if (__comp(__b, __a))
285  return __b;
286  return __a;
287  }
288 
289  /**
290  * @brief This does what you think it does.
291  * @ingroup sorting_algorithms
292  * @param __a A thing of arbitrary type.
293  * @param __b Another thing of arbitrary type.
294  * @param __comp A @link comparison_functors comparison functor@endlink.
295  * @return The greater of the parameters.
296  *
297  * This will work on temporary expressions, since they are only evaluated
298  * once, unlike a preprocessor macro.
299  */
300  template<typename _Tp, typename _Compare>
301  _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
302  inline const _Tp&
303  max(const _Tp& __a, const _Tp& __b, _Compare __comp)
304  {
305  //return __comp(__a, __b) ? __b : __a;
306  if (__comp(__a, __b))
307  return __b;
308  return __a;
309  }
310 
311 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
312 
313  template<typename _Tp, typename _Ref, typename _Ptr>
314  struct _Deque_iterator;
315 
316  struct _Bit_iterator;
317 
318 _GLIBCXX_END_NAMESPACE_CONTAINER
319 
320 #if _GLIBCXX_HOSTED
321  // Helpers for streambuf iterators (either istream or ostream).
322  // NB: avoid including <iosfwd>, relatively large.
323  template<typename _CharT>
324  struct char_traits;
325 
326  template<typename _CharT, typename _Traits>
327  class istreambuf_iterator;
328 
329  template<typename _CharT, typename _Traits>
330  class ostreambuf_iterator;
331 
332  template<bool _IsMove, typename _CharT>
333  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
334  ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
335  __copy_move_a2(_CharT*, _CharT*,
336  ostreambuf_iterator<_CharT, char_traits<_CharT> >);
337 
338  template<bool _IsMove, typename _CharT>
339  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
340  ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
341  __copy_move_a2(const _CharT*, const _CharT*,
342  ostreambuf_iterator<_CharT, char_traits<_CharT> >);
343 
344  template<bool _IsMove, typename _CharT>
345  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
346  _CharT*>::__type
347  __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
348  istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
349 
350  template<bool _IsMove, typename _CharT>
351  typename __gnu_cxx::__enable_if<
352  __is_char<_CharT>::__value,
353  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
354  __copy_move_a2(
355  istreambuf_iterator<_CharT, char_traits<_CharT> >,
356  istreambuf_iterator<_CharT, char_traits<_CharT> >,
357  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
358 #endif // HOSTED
359 
360 #if __cpp_lib_concepts
361  template<typename _OutIter, typename _InIter, typename _Sent = _InIter>
362  concept __memcpyable_iterators
363  = contiguous_iterator<_OutIter> && contiguous_iterator<_InIter>
364  && sized_sentinel_for<_Sent, _InIter>
365  && requires (_OutIter __o, _InIter __i) {
366  requires !!__memcpyable<decltype(std::to_address(__o)),
367  decltype(std::to_address(__i))>::__value;
368  };
369 #endif
370 
371 #if __cplusplus < 201103L
372  // Used by __copy_move_a2, __copy_n_a and __copy_move_backward_a2 to
373  // get raw pointers so that calls to __builtin_memmove will compile,
374  // because C++98 can't use 'if constexpr' so statements that use memmove
375  // with pointer arguments need to also compile for arbitrary iterator types.
376  template<typename _Iter> __attribute__((__always_inline__))
377  inline void* __ptr_or_null(_Iter) { return 0; }
378  template<typename _Tp> __attribute__((__always_inline__))
379  inline void* __ptr_or_null(_Tp* __p) { return (void*)__p; }
380 # define _GLIBCXX_TO_ADDR(P) std::__ptr_or_null(P)
381  // Used to advance output iterators (std::advance requires InputIterator).
382  template<typename _Iter> __attribute__((__always_inline__))
383  inline void __ptr_advance(_Iter&, ptrdiff_t) { }
384  template<typename _Tp> __attribute__((__always_inline__))
385  inline void __ptr_advance(_Tp*& __p, ptrdiff_t __n) { __p += __n; }
386 # define _GLIBCXX_ADVANCE(P, N) std::__ptr_advance(P, N)
387 #else
388  // For C++11 mode the __builtin_memmove calls are guarded by 'if constexpr'
389  // so we know the iterators used with memmove are guaranteed to be pointers.
390 # define _GLIBCXX_TO_ADDR(P) P
391 # define _GLIBCXX_ADVANCE(P, N) P += N
392 #endif
393 
394 #pragma GCC diagnostic push
395 #pragma GCC diagnostic ignored "-Wc++17-extensions"
396  template<bool _IsMove, typename _OutIter, typename _InIter>
397  __attribute__((__always_inline__)) _GLIBCXX20_CONSTEXPR
398  inline void
399  __assign_one(_OutIter& __out, _InIter& __in)
400  {
401 #if __cplusplus >= 201103L
402  if constexpr (_IsMove)
403  *__out = std::move(*__in);
404  else
405 #endif
406  *__out = *__in;
407  }
408 
409  template<bool _IsMove, typename _InIter, typename _Sent, typename _OutIter>
410  _GLIBCXX20_CONSTEXPR
411  inline _OutIter
412  __copy_move_a2(_InIter __first, _Sent __last, _OutIter __result)
413  {
414  typedef __decltype(*__first) _InRef;
415  typedef __decltype(*__result) _OutRef;
416  if _GLIBCXX_CONSTEXPR (!__is_trivially_assignable(_OutRef, _InRef))
417  { } /* Skip the optimizations and use the loop at the end. */
418  else if (std::__is_constant_evaluated())
419  { } /* Skip the optimizations and use the loop at the end. */
420  else if _GLIBCXX_CONSTEXPR (__memcpyable<_OutIter, _InIter>::__value)
421  {
422  ptrdiff_t __n = std::distance(__first, __last);
423  if (__builtin_expect(__n > 1, true))
424  {
425  __builtin_memmove(_GLIBCXX_TO_ADDR(__result),
426  _GLIBCXX_TO_ADDR(__first),
427  __n * sizeof(*__first));
428  _GLIBCXX_ADVANCE(__result, __n);
429  }
430  else if (__n == 1)
431  {
432  std::__assign_one<_IsMove>(__result, __first);
433  ++__result;
434  }
435  return __result;
436  }
437 #if __cpp_lib_concepts
438  else if constexpr (__memcpyable_iterators<_OutIter, _InIter, _Sent>)
439  {
440  if (auto __n = __last - __first; __n > 1) [[likely]]
441  {
442  void* __dest = std::to_address(__result);
443  const void* __src = std::to_address(__first);
444  size_t __nbytes = __n * sizeof(iter_value_t<_InIter>);
445  // Advance the iterators and convert to pointers first.
446  // This gives the iterators a chance to do bounds checking.
447  (void) std::to_address(__result += __n);
448  (void) std::to_address(__first += __n);
449  __builtin_memmove(__dest, __src, __nbytes);
450  }
451  else if (__n == 1)
452  {
453  std::__assign_one<_IsMove>(__result, __first);
454  ++__result;
455  }
456  return __result;
457  }
458 #endif
459 
460  for (; __first != __last; ++__result, (void)++__first)
461  std::__assign_one<_IsMove>(__result, __first);
462  return __result;
463  }
464 #pragma GCC diagnostic pop
465 
466  template<bool _IsMove,
467  typename _Tp, typename _Ref, typename _Ptr, typename _OI>
468  _OI
469  __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
470  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
471  _OI);
472 
473  template<bool _IsMove,
474  typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
475  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
476  __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
477  _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
478  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
479 
480  template<bool _IsMove, typename _II, typename _Tp>
481  typename __gnu_cxx::__enable_if<
482  __is_any_random_access_iter<_II>::__value,
483  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
484  __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
485 
486  template<bool _IsMove, typename _II, typename _OI>
487  __attribute__((__always_inline__))
488  _GLIBCXX20_CONSTEXPR
489  inline _OI
490  __copy_move_a1(_II __first, _II __last, _OI __result)
491  { return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
492 
493  template<bool _IsMove, typename _II, typename _OI>
494  __attribute__((__always_inline__))
495  _GLIBCXX20_CONSTEXPR
496  inline _OI
497  __copy_move_a(_II __first, _II __last, _OI __result)
498  {
499  return std::__niter_wrap(__result,
500  std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
501  std::__niter_base(__last),
502  std::__niter_base(__result)));
503  }
504 
505  template<bool _IsMove,
506  typename _Ite, typename _Seq, typename _Cat, typename _OI>
507  _GLIBCXX20_CONSTEXPR
508  _OI
509  __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
510  const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
511  _OI);
512 
513  template<bool _IsMove,
514  typename _II, typename _Ite, typename _Seq, typename _Cat>
515  _GLIBCXX20_CONSTEXPR
516  __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
517  __copy_move_a(_II, _II,
518  const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
519 
520  template<bool _IsMove,
521  typename _IIte, typename _ISeq, typename _ICat,
522  typename _OIte, typename _OSeq, typename _OCat>
523  _GLIBCXX20_CONSTEXPR
524  ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
525  __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
526  const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
527  const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
528 
529 #pragma GCC diagnostic push
530 #pragma GCC diagnostic ignored "-Wc++17-extensions" // for if-constexpr
531  template<typename _InputIterator, typename _Size, typename _OutputIterator>
532  _GLIBCXX20_CONSTEXPR
533  _OutputIterator
534  __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
535  bool)
536  {
537  typedef __decltype(*__first) _InRef;
538  typedef __decltype(*__result) _OutRef;
539  if _GLIBCXX_CONSTEXPR (!__is_trivially_assignable(_OutRef, _InRef))
540  { } /* Skip the optimizations and use the loop at the end. */
541 #ifdef __cpp_lib_is_constant_evaluated
542  else if (std::is_constant_evaluated())
543  { } /* Skip the optimizations and use the loop at the end. */
544 #endif
545  else if _GLIBCXX_CONSTEXPR (__memcpyable<_OutputIterator,
546  _InputIterator>::__value)
547  {
548  if (__builtin_expect(__n > 1, true))
549  {
550  __builtin_memmove(_GLIBCXX_TO_ADDR(__result),
551  _GLIBCXX_TO_ADDR(__first),
552  __n * sizeof(*__first));
553  _GLIBCXX_ADVANCE(__result, __n);
554  }
555  else if (__n == 1)
556  *__result++ = *__first;
557  return __result;
558  }
559 #if __cpp_lib_concepts
560  else if constexpr (__memcpyable_iterators<_OutputIterator,
561  _InputIterator>)
562  {
563  if (__n > 1) [[likely]]
564  {
565  void* __dest = std::to_address(__result);
566  const void* __src = std::to_address(__first);
567  size_t __nbytes = __n * sizeof(iter_value_t<_InputIterator>);
568  // Advance the iterators and convert to pointers first.
569  // This gives the iterators a chance to do bounds checking.
570  (void) std::to_address(__result += __n);
571  (void) std::to_address(__first += __n);
572  __builtin_memmove(__dest, __src, __nbytes);
573  }
574  else if (__n == 1)
575  *__result++ = *__first;
576  return __result;
577  }
578 #endif
579 
580  if (__n > 0)
581  {
582  while (true)
583  {
584  *__result = *__first;
585  ++__result;
586  if (--__n > 0)
587  ++__first;
588  else
589  break;
590  }
591  }
592  return __result;
593  }
594 #pragma GCC diagnostic pop
595 
596 #if _GLIBCXX_HOSTED
597  template<typename _CharT, typename _Size>
598  typename __gnu_cxx::__enable_if<
599  __is_char<_CharT>::__value, _CharT*>::__type
600  __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
601  _Size, _CharT*, bool);
602 
603  template<typename _CharT, typename _Size>
604  typename __gnu_cxx::__enable_if<
605  __is_char<_CharT>::__value,
606  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
607  __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
608  _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
609  bool);
610 #endif
611 
612  /**
613  * @brief Copies the range [first,last) into result.
614  * @ingroup mutating_algorithms
615  * @param __first An input iterator.
616  * @param __last An input iterator.
617  * @param __result An output iterator.
618  * @return result + (last - first)
619  *
620  * This inline function will boil down to a call to @c memmove whenever
621  * possible. Failing that, if random access iterators are passed, then the
622  * loop count will be known (and therefore a candidate for compiler
623  * optimizations such as unrolling). Result may not be contained within
624  * [first,last); the copy_backward function should be used instead.
625  *
626  * Note that the end of the output range is permitted to be contained
627  * within [first,last).
628  */
629  template<typename _II, typename _OI>
630  _GLIBCXX20_CONSTEXPR
631  inline _OI
632  copy(_II __first, _II __last, _OI __result)
633  {
634  // concept requirements
635  __glibcxx_function_requires(_InputIteratorConcept<_II>)
636  __glibcxx_function_requires(_OutputIteratorConcept<_OI,
637  typename iterator_traits<_II>::reference>)
638  __glibcxx_requires_can_increment_range(__first, __last, __result);
639 
640  return std::__copy_move_a<__is_move_iterator<_II>::__value>
641  (std::__miter_base(__first), std::__miter_base(__last), __result);
642  }
643 
644 #if __cplusplus >= 201103L
645  /**
646  * @brief Moves the range [first,last) into result.
647  * @ingroup mutating_algorithms
648  * @param __first An input iterator.
649  * @param __last An input iterator.
650  * @param __result An output iterator.
651  * @return result + (last - first)
652  *
653  * This inline function will boil down to a call to @c memmove whenever
654  * possible. Failing that, if random access iterators are passed, then the
655  * loop count will be known (and therefore a candidate for compiler
656  * optimizations such as unrolling). Result may not be contained within
657  * [first,last); the move_backward function should be used instead.
658  *
659  * Note that the end of the output range is permitted to be contained
660  * within [first,last).
661  */
662  template<typename _II, typename _OI>
663  _GLIBCXX20_CONSTEXPR
664  inline _OI
665  move(_II __first, _II __last, _OI __result)
666  {
667  // concept requirements
668  __glibcxx_function_requires(_InputIteratorConcept<_II>)
669  __glibcxx_function_requires(_OutputIteratorConcept<_OI,
670  typename iterator_traits<_II>::value_type&&>)
671  __glibcxx_requires_can_increment_range(__first, __last, __result);
672 
673  return std::__copy_move_a<true>(std::__miter_base(__first),
674  std::__miter_base(__last), __result);
675  }
676 
677 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
678 #else
679 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
680 #endif
681 
682 #pragma GCC diagnostic push
683 #pragma GCC diagnostic ignored "-Wc++17-extensions"
684  template<bool _IsMove, typename _BI1, typename _BI2>
685  _GLIBCXX20_CONSTEXPR
686  inline _BI2
687  __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
688  {
689  typedef __decltype(*__first) _InRef;
690  typedef __decltype(*__result) _OutRef;
691  if _GLIBCXX_CONSTEXPR (!__is_trivially_assignable(_OutRef, _InRef))
692  { } /* Skip the optimizations and use the loop at the end. */
693 #ifdef __cpp_lib_is_constant_evaluated
694  else if (std::is_constant_evaluated())
695  { } /* Skip the optimizations and use the loop at the end. */
696 #endif
697  else if _GLIBCXX_CONSTEXPR (__memcpyable<_BI2, _BI1>::__value)
698  {
699  ptrdiff_t __n = std::distance(__first, __last);
700  std::advance(__result, -__n);
701  if (__builtin_expect(__n > 1, true))
702  {
703  __builtin_memmove(_GLIBCXX_TO_ADDR(__result),
704  _GLIBCXX_TO_ADDR(__first),
705  __n * sizeof(*__first));
706  }
707  else if (__n == 1)
708  std::__assign_one<_IsMove>(__result, __first);
709  return __result;
710  }
711 #if __cpp_lib_concepts
712  else if constexpr (__memcpyable_iterators<_BI2, _BI1>)
713  {
714  if (auto __n = __last - __first; __n > 1) [[likely]]
715  {
716  const void* __src = std::to_address(__first);
717  // Advance the iterators and convert to pointers first.
718  // This gives the iterators a chance to do bounds checking.
719  (void) std::to_address(__result -= __n);
720  (void) std::to_address(__first += __n);
721  void* __dest = std::to_address(__result);
722  size_t __nbytes = __n * sizeof(iter_value_t<_BI1>);
723  __builtin_memmove(__dest, __src, __nbytes);
724  }
725  else if (__n == 1)
726  {
727  --__result;
728  std::__assign_one<_IsMove>(__result, __first);
729  }
730  return __result;
731  }
732 #endif
733 
734  while (__first != __last)
735  {
736  --__last;
737  --__result;
738  std::__assign_one<_IsMove>(__result, __last);
739  }
740  return __result;
741  }
742 #pragma GCC diagnostic pop
743 
744 #undef _GLIBCXX_TO_ADDR
745 #undef _GLIBCXX_ADVANCE
746 
747  template<bool _IsMove, typename _BI1, typename _BI2>
748  __attribute__((__always_inline__))
749  _GLIBCXX20_CONSTEXPR
750  inline _BI2
751  __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
752  { return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); }
753 
754  template<bool _IsMove,
755  typename _Tp, typename _Ref, typename _Ptr, typename _OI>
756  _OI
757  __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
758  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
759  _OI);
760 
761  template<bool _IsMove,
762  typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
763  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
764  __copy_move_backward_a1(
765  _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
766  _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
767  _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
768 
769  template<bool _IsMove, typename _II, typename _Tp>
770  typename __gnu_cxx::__enable_if<
771  __is_any_random_access_iter<_II>::__value,
772  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
773  __copy_move_backward_a1(_II, _II,
774  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
775 
776  template<bool _IsMove, typename _II, typename _OI>
777  __attribute__((__always_inline__))
778  _GLIBCXX20_CONSTEXPR
779  inline _OI
780  __copy_move_backward_a(_II __first, _II __last, _OI __result)
781  {
782  return std::__niter_wrap(__result,
783  std::__copy_move_backward_a1<_IsMove>
784  (std::__niter_base(__first), std::__niter_base(__last),
785  std::__niter_base(__result)));
786  }
787 
788  template<bool _IsMove,
789  typename _Ite, typename _Seq, typename _Cat, typename _OI>
790  _GLIBCXX20_CONSTEXPR
791  _OI
792  __copy_move_backward_a(
793  const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
794  const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
795  _OI);
796 
797  template<bool _IsMove,
798  typename _II, typename _Ite, typename _Seq, typename _Cat>
799  _GLIBCXX20_CONSTEXPR
800  __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
801  __copy_move_backward_a(_II, _II,
802  const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
803 
804  template<bool _IsMove,
805  typename _IIte, typename _ISeq, typename _ICat,
806  typename _OIte, typename _OSeq, typename _OCat>
807  _GLIBCXX20_CONSTEXPR
808  ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
809  __copy_move_backward_a(
810  const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
811  const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
812  const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
813 
814  /**
815  * @brief Copies the range [first,last) into result.
816  * @ingroup mutating_algorithms
817  * @param __first A bidirectional iterator.
818  * @param __last A bidirectional iterator.
819  * @param __result A bidirectional iterator.
820  * @return result - (last - first)
821  *
822  * The function has the same effect as copy, but starts at the end of the
823  * range and works its way to the start, returning the start of the result.
824  * This inline function will boil down to a call to @c memmove whenever
825  * possible. Failing that, if random access iterators are passed, then the
826  * loop count will be known (and therefore a candidate for compiler
827  * optimizations such as unrolling).
828  *
829  * Result may not be in the range (first,last]. Use copy instead. Note
830  * that the start of the output range may overlap [first,last).
831  */
832  template<typename _BI1, typename _BI2>
833  __attribute__((__always_inline__))
834  _GLIBCXX20_CONSTEXPR
835  inline _BI2
836  copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
837  {
838  // concept requirements
839  __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
840  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
841  __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
842  typename iterator_traits<_BI1>::reference>)
843  __glibcxx_requires_can_decrement_range(__first, __last, __result);
844 
845  return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
846  (std::__miter_base(__first), std::__miter_base(__last), __result);
847  }
848 
849 #if __cplusplus >= 201103L
850  /**
851  * @brief Moves the range [first,last) into result.
852  * @ingroup mutating_algorithms
853  * @param __first A bidirectional iterator.
854  * @param __last A bidirectional iterator.
855  * @param __result A bidirectional iterator.
856  * @return result - (last - first)
857  *
858  * The function has the same effect as move, but starts at the end of the
859  * range and works its way to the start, returning the start of the result.
860  * This inline function will boil down to a call to @c memmove whenever
861  * possible. Failing that, if random access iterators are passed, then the
862  * loop count will be known (and therefore a candidate for compiler
863  * optimizations such as unrolling).
864  *
865  * Result may not be in the range (first,last]. Use move instead. Note
866  * that the start of the output range may overlap [first,last).
867  */
868  template<typename _BI1, typename _BI2>
869  __attribute__((__always_inline__))
870  _GLIBCXX20_CONSTEXPR
871  inline _BI2
872  move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
873  {
874  // concept requirements
875  __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
876  __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
877  __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
878  typename iterator_traits<_BI1>::value_type&&>)
879  __glibcxx_requires_can_decrement_range(__first, __last, __result);
880 
881  return std::__copy_move_backward_a<true>(std::__miter_base(__first),
882  std::__miter_base(__last),
883  __result);
884  }
885 
886 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
887 #else
888 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
889 #endif
890 
891 #pragma GCC diagnostic push
892 #pragma GCC diagnostic ignored "-Wc++17-extensions"
893  template<typename _ForwardIterator, typename _Tp>
894  _GLIBCXX20_CONSTEXPR
895  inline void
896  __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
897  const _Tp& __value)
898  {
899 #pragma GCC diagnostic push
900 #pragma GCC diagnostic ignored "-Wlong-long"
901  // We can optimize this loop by moving the load from __value outside
902  // the loop, but only if we know that making that copy is trivial,
903  // and the assignment in the loop is also trivial (so that the identity
904  // of the operand doesn't matter).
905  const bool __load_outside_loop =
906 #if __has_builtin(__is_trivially_constructible) \
907  && __has_builtin(__is_trivially_assignable)
908  __is_trivially_constructible(_Tp, const _Tp&)
909  && __is_trivially_assignable(__decltype(*__first), const _Tp&)
910 #else
911  __is_trivially_copyable(_Tp)
912  && __is_same(_Tp, __typeof__(*__first))
913 #endif
914  && sizeof(_Tp) <= sizeof(long long);
915 #pragma GCC diagnostic pop
916 
917  // When the condition is true, we use a copy of __value,
918  // otherwise we just use another reference.
919  typedef typename __gnu_cxx::__conditional_type<__load_outside_loop,
920  const _Tp,
921  const _Tp&>::__type _Up;
922  _Up __val(__value);
923  for (; __first != __last; ++__first)
924  *__first = __val;
925  }
926 #pragma GCC diagnostic pop
927 
928  // Specialization: for char types we can use memset.
929  template<typename _Up, typename _Tp>
930  _GLIBCXX20_CONSTEXPR
931  inline typename
932  __gnu_cxx::__enable_if<__is_byte<_Up>::__value
933  && (__are_same<_Up, _Tp>::__value // for std::byte
934  || __memcpyable_integer<_Tp>::__width),
935  void>::__type
936  __fill_a1(_Up* __first, _Up* __last, const _Tp& __x)
937  {
938  // This hoists the load out of the loop and also ensures that we don't
939  // use memset for cases where the assignment would be ill-formed.
940  const _Up __val = __x;
941 #if __cpp_lib_is_constant_evaluated
942  if (std::is_constant_evaluated())
943  {
944  for (; __first != __last; ++__first)
945  *__first = __val;
946  return;
947  }
948 #endif
949  if (const size_t __len = __last - __first)
950  __builtin_memset(__first, static_cast<unsigned char>(__val), __len);
951  }
952 
953  template<typename _Ite, typename _Cont, typename _Tp>
954  __attribute__((__always_inline__))
955  _GLIBCXX20_CONSTEXPR
956  inline void
957  __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
958  ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
959  const _Tp& __value)
960  { std::__fill_a1(__first.base(), __last.base(), __value); }
961 
962  template<typename _Tp, typename _VTp>
963  void
964  __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
965  const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
966  const _VTp&);
967 
968  _GLIBCXX20_CONSTEXPR
969  void
970  __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
971  const bool&);
972 
973  template<typename _FIte, typename _Tp>
974  __attribute__((__always_inline__))
975  _GLIBCXX20_CONSTEXPR
976  inline void
977  __fill_a(_FIte __first, _FIte __last, const _Tp& __value)
978  { std::__fill_a1(__first, __last, __value); }
979 
980  template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
981  _GLIBCXX20_CONSTEXPR
982  void
983  __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
984  const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
985  const _Tp&);
986 
987  /**
988  * @brief Fills the range [first,last) with copies of value.
989  * @ingroup mutating_algorithms
990  * @param __first A forward iterator.
991  * @param __last A forward iterator.
992  * @param __value A reference-to-const of arbitrary type.
993  * @return Nothing.
994  *
995  * This function fills a range with copies of the same value. For char
996  * types filling contiguous areas of memory, this becomes an inline call
997  * to @c memset or @c wmemset.
998  */
999  template<typename _ForwardIterator, typename _Tp>
1000  __attribute__((__always_inline__))
1001  _GLIBCXX20_CONSTEXPR
1002  inline void
1003  fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
1004  {
1005  // concept requirements
1006  __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1007  _ForwardIterator>)
1008  __glibcxx_requires_valid_range(__first, __last);
1009 
1010  std::__fill_a(__first, __last, __value);
1011  }
1012 
1013 #pragma GCC diagnostic push
1014 #pragma GCC diagnostic ignored "-Wlong-long"
1015  // Used by fill_n, generate_n, etc. to convert _Size to an integral type:
1016  inline _GLIBCXX_CONSTEXPR int
1017  __size_to_integer(int __n) { return __n; }
1018  inline _GLIBCXX_CONSTEXPR unsigned
1019  __size_to_integer(unsigned __n) { return __n; }
1020  inline _GLIBCXX_CONSTEXPR long
1021  __size_to_integer(long __n) { return __n; }
1022  inline _GLIBCXX_CONSTEXPR unsigned long
1023  __size_to_integer(unsigned long __n) { return __n; }
1024  inline _GLIBCXX_CONSTEXPR long long
1025  __size_to_integer(long long __n) { return __n; }
1026  inline _GLIBCXX_CONSTEXPR unsigned long long
1027  __size_to_integer(unsigned long long __n) { return __n; }
1028 
1029 #if defined(__GLIBCXX_TYPE_INT_N_0)
1030  __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1031  __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
1032  __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0
1033  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
1034 #endif
1035 #if defined(__GLIBCXX_TYPE_INT_N_1)
1036  __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1037  __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
1038  __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1
1039  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
1040 #endif
1041 #if defined(__GLIBCXX_TYPE_INT_N_2)
1042  __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1043  __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
1044  __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2
1045  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
1046 #endif
1047 #if defined(__GLIBCXX_TYPE_INT_N_3)
1048  __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1049  __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
1050  __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3
1051  __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
1052 #endif
1053 
1054 #if defined(__STRICT_ANSI__) && defined(__SIZEOF_INT128__)
1055  __extension__ inline _GLIBCXX_CONSTEXPR __int128
1056  __size_to_integer(__int128 __n) { return __n; }
1057  __extension__ inline _GLIBCXX_CONSTEXPR unsigned __int128
1058  __size_to_integer(unsigned __int128 __n) { return __n; }
1059 #endif
1060 
1061  inline _GLIBCXX_CONSTEXPR long long
1062  __size_to_integer(float __n) { return (long long)__n; }
1063  inline _GLIBCXX_CONSTEXPR long long
1064  __size_to_integer(double __n) { return (long long)__n; }
1065  inline _GLIBCXX_CONSTEXPR long long
1066  __size_to_integer(long double __n) { return (long long)__n; }
1067 #if defined(_GLIBCXX_USE_FLOAT128) && !defined(__CUDACC__)
1068  __extension__ inline _GLIBCXX_CONSTEXPR long long
1069  __size_to_integer(__float128 __n) { return (long long)__n; }
1070 #endif
1071 #pragma GCC diagnostic pop
1072 
1073 #pragma GCC diagnostic push
1074 #pragma GCC diagnostic ignored "-Wc++17-extensions"
1075 #pragma GCC diagnostic ignored "-Wlong-long"
1076  template<typename _OutputIterator, typename _Size, typename _Tp>
1077  _GLIBCXX20_CONSTEXPR
1078  inline _OutputIterator
1079  __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value)
1080  {
1081  // See std::__fill_a1 for explanation of this condition.
1082  const bool __load_outside_loop =
1083 #if __has_builtin(__is_trivially_constructible) \
1084  && __has_builtin(__is_trivially_assignable)
1085  __is_trivially_constructible(_Tp, const _Tp&)
1086  && __is_trivially_assignable(__decltype(*__first), const _Tp&)
1087 #else
1088  __is_trivially_copyable(_Tp)
1089  && __is_same(_Tp, __typeof__(*__first))
1090 #endif
1091  && sizeof(_Tp) <= sizeof(long long);
1092 
1093  // When the condition is true, we use a copy of __value,
1094  // otherwise we just use another reference.
1095  typedef typename __gnu_cxx::__conditional_type<__load_outside_loop,
1096  const _Tp,
1097  const _Tp&>::__type _Up;
1098  _Up __val(__value);
1099  for (; __n > 0; --__n, (void) ++__first)
1100  *__first = __val;
1101  return __first;
1102  }
1103 #pragma GCC diagnostic pop
1104 
1105  template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
1106  typename _Tp>
1107  _GLIBCXX20_CONSTEXPR
1108  ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1109  __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1110  _Size __n, const _Tp& __value,
1111  std::input_iterator_tag);
1112 
1113  template<typename _OutputIterator, typename _Size, typename _Tp>
1114  __attribute__((__always_inline__))
1115  _GLIBCXX20_CONSTEXPR
1116  inline _OutputIterator
1117  __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1118  std::output_iterator_tag)
1119  {
1120 #if __cplusplus >= 201103L
1121  static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1122 #endif
1123  return __fill_n_a1(__first, __n, __value);
1124  }
1125 
1126  template<typename _OutputIterator, typename _Size, typename _Tp>
1127  __attribute__((__always_inline__))
1128  _GLIBCXX20_CONSTEXPR
1129  inline _OutputIterator
1130  __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1131  std::input_iterator_tag)
1132  {
1133 #if __cplusplus >= 201103L
1134  static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1135 #endif
1136  return __fill_n_a1(__first, __n, __value);
1137  }
1138 
1139  template<typename _OutputIterator, typename _Size, typename _Tp>
1140  __attribute__((__always_inline__))
1141  _GLIBCXX20_CONSTEXPR
1142  inline _OutputIterator
1143  __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value,
1144  std::random_access_iterator_tag)
1145  {
1146 #if __cplusplus >= 201103L
1147  static_assert(is_integral<_Size>{}, "fill_n must pass integral size");
1148 #endif
1149  if (__n <= 0)
1150  return __first;
1151 
1152  typename iterator_traits<_OutputIterator>::difference_type __d = __n;
1153  __glibcxx_requires_can_increment(__first, __d);
1154 
1155  _OutputIterator __last = __first + __d;
1156  std::__fill_a(__first, __last, __value);
1157  return __last;
1158  }
1159 
1160  /**
1161  * @brief Fills the range [first,first+n) with copies of value.
1162  * @ingroup mutating_algorithms
1163  * @param __first An output iterator.
1164  * @param __n The count of copies to perform.
1165  * @param __value A reference-to-const of arbitrary type.
1166  * @return The iterator at first+n.
1167  *
1168  * This function fills a range with copies of the same value. For char
1169  * types filling contiguous areas of memory, this becomes an inline call
1170  * to @c memset or @c wmemset.
1171  *
1172  * If @p __n is negative, the function does nothing.
1173  */
1174  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1175  // DR 865. More algorithms that throw away information
1176  // DR 426. search_n(), fill_n(), and generate_n() with negative n
1177  template<typename _OI, typename _Size, typename _Tp>
1178  __attribute__((__always_inline__))
1179  _GLIBCXX20_CONSTEXPR
1180  inline _OI
1181  fill_n(_OI __first, _Size __n, const _Tp& __value)
1182  {
1183  // concept requirements
1184  __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1185 
1186  return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1187  std::__iterator_category(__first));
1188  }
1189 
1190  template<bool _BoolType>
1191  struct __equal
1192  {
1193  template<typename _II1, typename _II2>
1194  _GLIBCXX20_CONSTEXPR
1195  static bool
1196  equal(_II1 __first1, _II1 __last1, _II2 __first2)
1197  {
1198  for (; __first1 != __last1; ++__first1, (void) ++__first2)
1199  if (!(*__first1 == *__first2))
1200  return false;
1201  return true;
1202  }
1203  };
1204 
1205  template<>
1206  struct __equal<true>
1207  {
1208  template<typename _Tp>
1209  _GLIBCXX20_CONSTEXPR
1210  static bool
1211  equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
1212  {
1213  if (const size_t __len = (__last1 - __first1))
1214  return !std::__memcmp(__first1, __first2, __len);
1215  return true;
1216  }
1217  };
1218 
1219  template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1220  typename __gnu_cxx::__enable_if<
1221  __is_any_random_access_iter<_II>::__value, bool>::__type
1222  __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1223  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1224  _II);
1225 
1226  template<typename _Tp1, typename _Ref1, typename _Ptr1,
1227  typename _Tp2, typename _Ref2, typename _Ptr2>
1228  bool
1229  __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1230  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1231  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1232 
1233  template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
1234  typename __gnu_cxx::__enable_if<
1235  __is_any_random_access_iter<_II>::__value, bool>::__type
1236  __equal_aux1(_II, _II,
1237  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1238 
1239  template<typename _II1, typename _II2>
1240  _GLIBCXX20_CONSTEXPR
1241  inline bool
1242  __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1243  {
1244  typedef typename iterator_traits<_II1>::value_type _ValueType1;
1245  const bool __simple = ((__is_integer<_ValueType1>::__value
1246 #if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1247  || __is_pointer(_ValueType1)
1248 #endif
1249 #if __glibcxx_byte && __glibcxx_type_trait_variable_templates
1250  // bits/cpp_type_traits.h declares std::byte
1251  || is_same_v<_ValueType1, byte>
1252 #endif
1253  ) && __memcmpable<_II1, _II2>::__value);
1254  return std::__equal<__simple>::equal(__first1, __last1, __first2);
1255  }
1256 
1257  template<typename _II1, typename _II2>
1258  __attribute__((__always_inline__))
1259  _GLIBCXX20_CONSTEXPR
1260  inline bool
1261  __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1262  {
1263  return std::__equal_aux1(std::__niter_base(__first1),
1264  std::__niter_base(__last1),
1265  std::__niter_base(__first2));
1266  }
1267 
1268  template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
1269  _GLIBCXX20_CONSTEXPR
1270  bool
1271  __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1272  const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1273  _II2);
1274 
1275  template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
1276  _GLIBCXX20_CONSTEXPR
1277  bool
1278  __equal_aux(_II1, _II1,
1279  const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1280 
1281  template<typename _II1, typename _Seq1, typename _Cat1,
1282  typename _II2, typename _Seq2, typename _Cat2>
1283  _GLIBCXX20_CONSTEXPR
1284  bool
1285  __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1286  const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1287  const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1288 
1289  template<typename, typename>
1290  struct __lc_rai
1291  {
1292  template<typename _II1, typename _II2>
1293  _GLIBCXX20_CONSTEXPR
1294  static _II1
1295  __newlast1(_II1, _II1 __last1, _II2, _II2)
1296  { return __last1; }
1297 
1298  template<typename _II>
1299  _GLIBCXX20_CONSTEXPR
1300  static bool
1301  __cnd2(_II __first, _II __last)
1302  { return __first != __last; }
1303  };
1304 
1305  template<>
1306  struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1307  {
1308  template<typename _RAI1, typename _RAI2>
1309  _GLIBCXX20_CONSTEXPR
1310  static _RAI1
1311  __newlast1(_RAI1 __first1, _RAI1 __last1,
1312  _RAI2 __first2, _RAI2 __last2)
1313  {
1314  typedef typename iterator_traits<_RAI1>::difference_type _Diff1;
1315  typedef typename iterator_traits<_RAI2>::difference_type _Diff2;
1316  const _Diff1 __diff1 = __last1 - __first1;
1317  const _Diff2 __diff2 = __last2 - __first2;
1318  return __diff2 < __diff1 ? __first1 + _Diff1(__diff2) : __last1;
1319  }
1320 
1321  template<typename _RAI>
1322  static _GLIBCXX20_CONSTEXPR bool
1323  __cnd2(_RAI, _RAI)
1324  { return true; }
1325  };
1326 
1327  template<typename _II1, typename _II2, typename _Compare>
1328  _GLIBCXX20_CONSTEXPR
1329  bool
1330  __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1331  _II2 __first2, _II2 __last2,
1332  _Compare __comp)
1333  {
1334  typedef __decltype(std::__iter_concept_or_category<_II1>()) _Category1;
1335  typedef __decltype(std::__iter_concept_or_category<_II2>()) _Category2;
1336  typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1337 
1338  __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1339  for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1340  ++__first1, (void)++__first2)
1341  {
1342  if (__comp(*__first1, *__first2))
1343  return true;
1344  if (__comp(*__first2, *__first1))
1345  return false;
1346  }
1347  return __first1 == __last1 && __first2 != __last2;
1348  }
1349 
1350  template<bool _BoolType>
1351  struct __lexicographical_compare
1352  {
1353  template<typename _II1, typename _II2>
1354  _GLIBCXX20_CONSTEXPR
1355  static bool
1356  __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1357  {
1358  using __gnu_cxx::__ops::less;
1359  return std::__lexicographical_compare_impl(__first1, __last1,
1360  __first2, __last2,
1361  less());
1362  }
1363 
1364  template<typename _II1, typename _II2>
1365  _GLIBCXX20_CONSTEXPR
1366  static int
1367  __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1368  {
1369  while (__first1 != __last1)
1370  {
1371  if (__first2 == __last2)
1372  return +1;
1373  if (*__first1 < *__first2)
1374  return -1;
1375  if (*__first2 < *__first1)
1376  return +1;
1377  ++__first1;
1378  ++__first2;
1379  }
1380  return int(__first2 == __last2) - 1;
1381  }
1382  };
1383 
1384  template<>
1385  struct __lexicographical_compare<true>
1386  {
1387  template<typename _Tp, typename _Up>
1388  _GLIBCXX20_CONSTEXPR
1389  static bool
1390  __lc(const _Tp* __first1, const _Tp* __last1,
1391  const _Up* __first2, const _Up* __last2)
1392  { return __3way(__first1, __last1, __first2, __last2) < 0; }
1393 
1394  template<typename _Tp, typename _Up>
1395  _GLIBCXX20_CONSTEXPR
1396  static ptrdiff_t
1397  __3way(const _Tp* __first1, const _Tp* __last1,
1398  const _Up* __first2, const _Up* __last2)
1399  {
1400  const size_t __len1 = __last1 - __first1;
1401  const size_t __len2 = __last2 - __first2;
1402  if (const size_t __len = std::min(__len1, __len2))
1403  if (int __result = std::__memcmp(__first1, __first2, __len))
1404  return __result;
1405  return ptrdiff_t(__len1 - __len2);
1406  }
1407  };
1408 
1409  template<typename _II1, typename _II2>
1410  _GLIBCXX20_CONSTEXPR
1411  inline bool
1412  __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1413  _II2 __first2, _II2 __last2)
1414  {
1415  typedef typename iterator_traits<_II1>::value_type _ValueType1;
1416  typedef typename iterator_traits<_II2>::value_type _ValueType2;
1417 #if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1418  const bool __simple =
1419  (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1420  && __is_pointer(_II1) && __is_pointer(_II2)
1421 #if __cplusplus > 201703L && __glibcxx_concepts
1422  // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
1423  // so __is_byte<T> could be true, but we can't use memcmp with
1424  // volatile data.
1425  && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1426  && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1427 #endif
1428  );
1429 #else
1430  const bool __simple = false;
1431 #endif
1432 
1433  return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1434  __first2, __last2);
1435  }
1436 
1437  template<typename _Tp1, typename _Ref1, typename _Ptr1,
1438  typename _Tp2>
1439  bool
1440  __lexicographical_compare_aux1(
1441  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1442  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1443  _Tp2*, _Tp2*);
1444 
1445  template<typename _Tp1,
1446  typename _Tp2, typename _Ref2, typename _Ptr2>
1447  bool
1448  __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1449  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1450  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1451 
1452  template<typename _Tp1, typename _Ref1, typename _Ptr1,
1453  typename _Tp2, typename _Ref2, typename _Ptr2>
1454  bool
1455  __lexicographical_compare_aux1(
1456  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1457  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1458  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1459  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1460 
1461  template<typename _II1, typename _II2>
1462  _GLIBCXX20_CONSTEXPR
1463  inline bool
1464  __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1465  _II2 __first2, _II2 __last2)
1466  {
1467  return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1468  std::__niter_base(__last1),
1469  std::__niter_base(__first2),
1470  std::__niter_base(__last2));
1471  }
1472 
1473  template<typename _Iter1, typename _Seq1, typename _Cat1,
1474  typename _II2>
1475  _GLIBCXX20_CONSTEXPR
1476  bool
1477  __lexicographical_compare_aux(
1478  const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1479  const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1480  _II2, _II2);
1481 
1482  template<typename _II1,
1483  typename _Iter2, typename _Seq2, typename _Cat2>
1484  _GLIBCXX20_CONSTEXPR
1485  bool
1486  __lexicographical_compare_aux(
1487  _II1, _II1,
1488  const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1489  const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1490 
1491  template<typename _Iter1, typename _Seq1, typename _Cat1,
1492  typename _Iter2, typename _Seq2, typename _Cat2>
1493  _GLIBCXX20_CONSTEXPR
1494  bool
1495  __lexicographical_compare_aux(
1496  const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1497  const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1498  const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1499  const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1500 
1501  template<typename _ForwardIterator, typename _Tp, typename _Compare>
1502  _GLIBCXX20_CONSTEXPR
1503  _ForwardIterator
1504  __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1505  const _Tp& __val, _Compare __comp)
1506  {
1507  typedef typename iterator_traits<_ForwardIterator>::difference_type
1508  _DistanceType;
1509 
1510  _DistanceType __len = std::distance(__first, __last);
1511 
1512  while (__len > 0)
1513  {
1514  _DistanceType __half = __len >> 1;
1515  _ForwardIterator __middle = __first;
1516  std::advance(__middle, __half);
1517  if (__comp(*__middle, __val))
1518  {
1519  __first = __middle;
1520  ++__first;
1521  __len = __len - __half - 1;
1522  }
1523  else
1524  __len = __half;
1525  }
1526  return __first;
1527  }
1528 
1529  /**
1530  * @brief Finds the first position in which @a val could be inserted
1531  * without changing the ordering.
1532  * @param __first An iterator.
1533  * @param __last Another iterator.
1534  * @param __val The search term.
1535  * @return An iterator pointing to the first element <em>not less
1536  * than</em> @a val, or end() if every element is less than
1537  * @a val.
1538  * @ingroup binary_search_algorithms
1539  */
1540  template<typename _ForwardIterator, typename _Tp>
1541  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1542  inline _ForwardIterator
1543  lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1544  const _Tp& __val)
1545  {
1546  // concept requirements
1547  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1548  __glibcxx_function_requires(_LessThanOpConcept<
1549  typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1550  __glibcxx_requires_partitioned_lower(__first, __last, __val);
1551 
1552  return std::__lower_bound(__first, __last, __val,
1553  __gnu_cxx::__ops::less());
1554  }
1555 
1556  /// This is a helper function for the sort routines and for random.tcc.
1557  // Precondition: __n > 0.
1558  template<typename _Tp>
1559  inline _GLIBCXX_CONSTEXPR _Tp
1560  __lg(_Tp __n)
1561  {
1562 #if __cplusplus >= 201402L
1563  return std::__bit_width(make_unsigned_t<_Tp>(__n)) - 1;
1564 #else
1565 #pragma GCC diagnostic push
1566 #pragma GCC diagnostic ignored "-Wlong-long"
1567  // Use +__n so it promotes to at least int.
1568  return (sizeof(+__n) * __CHAR_BIT__ - 1)
1569  - (sizeof(+__n) == sizeof(long long)
1570  ? __builtin_clzll(+__n)
1571  : (sizeof(+__n) == sizeof(long)
1572  ? __builtin_clzl(+__n)
1573  : __builtin_clz(+__n)));
1574 #pragma GCC diagnostic pop
1575 #endif
1576  }
1577 
1578 _GLIBCXX_BEGIN_NAMESPACE_ALGO
1579 
1580  /**
1581  * @brief Tests a range for element-wise equality.
1582  * @ingroup non_mutating_algorithms
1583  * @param __first1 An input iterator.
1584  * @param __last1 An input iterator.
1585  * @param __first2 An input iterator.
1586  * @return A boolean true or false.
1587  *
1588  * This compares the elements of two ranges using @c == and returns true or
1589  * false depending on whether all of the corresponding elements of the
1590  * ranges are equal.
1591  */
1592  template<typename _II1, typename _II2>
1593  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1594  inline bool
1595  equal(_II1 __first1, _II1 __last1, _II2 __first2)
1596  {
1597  // concept requirements
1598  __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1599  __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1600  __glibcxx_function_requires(_EqualOpConcept<
1601  typename iterator_traits<_II1>::value_type,
1602  typename iterator_traits<_II2>::value_type>)
1603  __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1604 
1605  return std::__equal_aux(__first1, __last1, __first2);
1606  }
1607 
1608  /**
1609  * @brief Tests a range for element-wise equality.
1610  * @ingroup non_mutating_algorithms
1611  * @param __first1 An input iterator.
1612  * @param __last1 An input iterator.
1613  * @param __first2 An input iterator.
1614  * @param __binary_pred A binary predicate @link functors
1615  * functor@endlink.
1616  * @return A boolean true or false.
1617  *
1618  * This compares the elements of two ranges using the binary_pred
1619  * parameter, and returns true or
1620  * false depending on whether all of the corresponding elements of the
1621  * ranges are equal.
1622  */
1623  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1624  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1625  inline bool
1626  equal(_IIter1 __first1, _IIter1 __last1,
1627  _IIter2 __first2, _BinaryPredicate __binary_pred)
1628  {
1629  // concept requirements
1630  __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1631  __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1632  __glibcxx_requires_valid_range(__first1, __last1);
1633 
1634  for (; __first1 != __last1; ++__first1, (void)++__first2)
1635  if (!bool(__binary_pred(*__first1, *__first2)))
1636  return false;
1637  return true;
1638  }
1639 
1640 #if __cplusplus >= 201103L
1641 #pragma GCC diagnostic push
1642 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
1643 
1644  // 4-iterator version of std::equal<It1, It2> for use in C++11.
1645  template<typename _II1, typename _II2>
1646  _GLIBCXX20_CONSTEXPR
1647  inline bool
1648  __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1649  {
1650  using _RATag = random_access_iterator_tag;
1651  using _Cat1 = decltype(std::__iter_concept_or_category<_II1>());
1652  using _Cat2 = decltype(std::__iter_concept_or_category<_II2>());
1653  using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1654  if constexpr (_RAIters::value)
1655  {
1656  if ((__last1 - __first1) != (__last2 - __first2))
1657  return false;
1658  return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1659  }
1660  else
1661  {
1662  for (; __first1 != __last1 && __first2 != __last2;
1663  ++__first1, (void)++__first2)
1664  if (!(*__first1 == *__first2))
1665  return false;
1666  return __first1 == __last1 && __first2 == __last2;
1667  }
1668  }
1669 
1670  // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11.
1671  template<typename _II1, typename _II2, typename _BinaryPredicate>
1672  _GLIBCXX20_CONSTEXPR
1673  inline bool
1674  __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1675  _BinaryPredicate __binary_pred)
1676  {
1677  using _RATag = random_access_iterator_tag;
1678  using _Cat1 = decltype(std::__iter_concept_or_category<_II1>());
1679  using _Cat2 = decltype(std::__iter_concept_or_category<_II2>());
1680  using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1681  if constexpr (_RAIters::value)
1682  {
1683  if ((__last1 - __first1) != (__last2 - __first2))
1684  return false;
1685  return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1686  __binary_pred);
1687  }
1688  else
1689  {
1690  for (; __first1 != __last1 && __first2 != __last2;
1691  ++__first1, (void)++__first2)
1692  if (!bool(__binary_pred(*__first1, *__first2)))
1693  return false;
1694  return __first1 == __last1 && __first2 == __last2;
1695  }
1696  }
1697 #pragma GCC diagnostic pop
1698 #endif // C++11
1699 
1700 #ifdef __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14
1701  /**
1702  * @brief Tests a range for element-wise equality.
1703  * @ingroup non_mutating_algorithms
1704  * @param __first1 An input iterator.
1705  * @param __last1 An input iterator.
1706  * @param __first2 An input iterator.
1707  * @param __last2 An input iterator.
1708  * @return A boolean true or false.
1709  *
1710  * This compares the elements of two ranges using @c == and returns true or
1711  * false depending on whether all of the corresponding elements of the
1712  * ranges are equal.
1713  */
1714  template<typename _II1, typename _II2>
1715  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1716  inline bool
1717  equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1718  {
1719  // concept requirements
1720  __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1721  __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1722  __glibcxx_function_requires(_EqualOpConcept<
1723  typename iterator_traits<_II1>::value_type,
1724  typename iterator_traits<_II2>::value_type>)
1725  __glibcxx_requires_valid_range(__first1, __last1);
1726  __glibcxx_requires_valid_range(__first2, __last2);
1727 
1728  return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1729  }
1730 
1731  /**
1732  * @brief Tests a range for element-wise equality.
1733  * @ingroup non_mutating_algorithms
1734  * @param __first1 An input iterator.
1735  * @param __last1 An input iterator.
1736  * @param __first2 An input iterator.
1737  * @param __last2 An input iterator.
1738  * @param __binary_pred A binary predicate @link functors
1739  * functor@endlink.
1740  * @return A boolean true or false.
1741  *
1742  * This compares the elements of two ranges using the binary_pred
1743  * parameter, and returns true or
1744  * false depending on whether all of the corresponding elements of the
1745  * ranges are equal.
1746  */
1747  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
1748  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1749  inline bool
1750  equal(_IIter1 __first1, _IIter1 __last1,
1751  _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1752  {
1753  // concept requirements
1754  __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1755  __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1756  __glibcxx_requires_valid_range(__first1, __last1);
1757  __glibcxx_requires_valid_range(__first2, __last2);
1758 
1759  return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1760  __binary_pred);
1761  }
1762 #endif // __glibcxx_robust_nonmodifying_seq_ops
1763 
1764  /**
1765  * @brief Performs @b dictionary comparison on ranges.
1766  * @ingroup sorting_algorithms
1767  * @param __first1 An input iterator.
1768  * @param __last1 An input iterator.
1769  * @param __first2 An input iterator.
1770  * @param __last2 An input iterator.
1771  * @return A boolean true or false.
1772  *
1773  * <em>Returns true if the sequence of elements defined by the range
1774  * [first1,last1) is lexicographically less than the sequence of elements
1775  * defined by the range [first2,last2). Returns false otherwise.</em>
1776  * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
1777  * then this is an inline call to @c memcmp.
1778  */
1779  template<typename _II1, typename _II2>
1780  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1781  inline bool
1782  lexicographical_compare(_II1 __first1, _II1 __last1,
1783  _II2 __first2, _II2 __last2)
1784  {
1785 #ifdef _GLIBCXX_CONCEPT_CHECKS
1786  // concept requirements
1787  typedef typename iterator_traits<_II1>::value_type _ValueType1;
1788  typedef typename iterator_traits<_II2>::value_type _ValueType2;
1789 #endif
1790  __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1791  __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1792  __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1793  __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1794  __glibcxx_requires_valid_range(__first1, __last1);
1795  __glibcxx_requires_valid_range(__first2, __last2);
1796 
1797  return std::__lexicographical_compare_aux(__first1, __last1,
1798  __first2, __last2);
1799  }
1800 
1801  /**
1802  * @brief Performs @b dictionary comparison on ranges.
1803  * @ingroup sorting_algorithms
1804  * @param __first1 An input iterator.
1805  * @param __last1 An input iterator.
1806  * @param __first2 An input iterator.
1807  * @param __last2 An input iterator.
1808  * @param __comp A @link comparison_functors comparison functor@endlink.
1809  * @return A boolean true or false.
1810  *
1811  * The same as the four-parameter @c lexicographical_compare, but uses the
1812  * comp parameter instead of @c <.
1813  */
1814  template<typename _II1, typename _II2, typename _Compare>
1815  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1816  inline bool
1817  lexicographical_compare(_II1 __first1, _II1 __last1,
1818  _II2 __first2, _II2 __last2, _Compare __comp)
1819  {
1820  // concept requirements
1821  __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1822  __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1823  __glibcxx_requires_valid_range(__first1, __last1);
1824  __glibcxx_requires_valid_range(__first2, __last2);
1825 
1826  return std::__lexicographical_compare_impl
1827  (__first1, __last1, __first2, __last2, __comp);
1828  }
1829 
1830 #if __cpp_lib_three_way_comparison
1831  // Both iterators refer to contiguous ranges of unsigned narrow characters,
1832  // or std::byte, or big-endian unsigned integers, suitable for comparison
1833  // using memcmp.
1834  template<typename _Iter1, typename _Iter2>
1835  concept __memcmp_ordered_with
1836  = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1837  iter_value_t<_Iter2>>::__value)
1838  && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
1839 
1840  // Return a struct with two members, initialized to the smaller of x and y
1841  // (or x if they compare equal) and the result of the comparison x <=> y.
1842  template<typename _Tp>
1843  constexpr auto
1844  __min_cmp(_Tp __x, _Tp __y)
1845  {
1846  struct _Res {
1847  _Tp _M_min;
1848  decltype(__x <=> __y) _M_cmp;
1849  };
1850  auto __c = __x <=> __y;
1851  if (__c > 0)
1852  return _Res{__y, __c};
1853  return _Res{__x, __c};
1854  }
1855 
1856  /**
1857  * @brief Performs dictionary comparison on ranges.
1858  * @ingroup sorting_algorithms
1859  * @param __first1 An input iterator.
1860  * @param __last1 An input iterator.
1861  * @param __first2 An input iterator.
1862  * @param __last2 An input iterator.
1863  * @param __comp A @link comparison_functors comparison functor@endlink.
1864  * @return The comparison category that `__comp(*__first1, *__first2)`
1865  * returns.
1866  */
1867  template<typename _InputIter1, typename _InputIter2, typename _Comp>
1868  [[nodiscard]] constexpr auto
1869  lexicographical_compare_three_way(_InputIter1 __first1,
1870  _InputIter1 __last1,
1871  _InputIter2 __first2,
1872  _InputIter2 __last2,
1873  _Comp __comp)
1874  -> decltype(__comp(*__first1, *__first2))
1875  {
1876  // concept requirements
1877  __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1878  __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1879  __glibcxx_requires_valid_range(__first1, __last1);
1880  __glibcxx_requires_valid_range(__first2, __last2);
1881 
1882  using _Cat = decltype(__comp(*__first1, *__first2));
1883  static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1884 
1885  if (!std::__is_constant_evaluated())
1886  if constexpr (same_as<_Comp, __detail::_Synth3way>
1887  || same_as<_Comp, compare_three_way>)
1888  if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1889  {
1890  const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1891  __min_cmp(__last1 - __first1, __last2 - __first2);
1892  if (__len)
1893  {
1894  const auto __blen = __len * sizeof(*__first1);
1895  const auto __c
1896  = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
1897  if (__c != 0)
1898  return __c;
1899  }
1900  return __lencmp;
1901  }
1902 
1903  while (__first1 != __last1)
1904  {
1905  if (__first2 == __last2)
1906  return strong_ordering::greater;
1907  if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1908  return __cmp;
1909  ++__first1;
1910  ++__first2;
1911  }
1912  return (__first2 == __last2) <=> true; // See PR 94006
1913  }
1914 
1915  template<typename _InputIter1, typename _InputIter2>
1916  constexpr auto
1917  lexicographical_compare_three_way(_InputIter1 __first1,
1918  _InputIter1 __last1,
1919  _InputIter2 __first2,
1920  _InputIter2 __last2)
1921  {
1922  return _GLIBCXX_STD_A::
1923  lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1924  compare_three_way{});
1925  }
1926 #endif // three_way_comparison
1927 
1928  template<typename _InputIterator1, typename _InputIterator2,
1929  typename _BinaryPredicate>
1930  _GLIBCXX20_CONSTEXPR
1931  pair<_InputIterator1, _InputIterator2>
1932  __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1933  _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1934  {
1935  while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
1936  {
1937  ++__first1;
1938  ++__first2;
1939  }
1940  return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1941  }
1942 
1943  /**
1944  * @brief Finds the places in ranges which don't match.
1945  * @ingroup non_mutating_algorithms
1946  * @param __first1 An input iterator.
1947  * @param __last1 An input iterator.
1948  * @param __first2 An input iterator.
1949  * @return A pair of iterators pointing to the first mismatch.
1950  *
1951  * This compares the elements of two ranges using @c == and returns a pair
1952  * of iterators. The first iterator points into the first range, the
1953  * second iterator points into the second range, and the elements pointed
1954  * to by the iterators are not equal.
1955  */
1956  template<typename _InputIterator1, typename _InputIterator2>
1957  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1958  inline pair<_InputIterator1, _InputIterator2>
1959  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1960  _InputIterator2 __first2)
1961  {
1962  // concept requirements
1963  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1964  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1965  __glibcxx_function_requires(_EqualOpConcept<
1966  typename iterator_traits<_InputIterator1>::value_type,
1967  typename iterator_traits<_InputIterator2>::value_type>)
1968  __glibcxx_requires_valid_range(__first1, __last1);
1969 
1970  return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1971  __gnu_cxx::__ops::equal_to());
1972  }
1973 
1974  /**
1975  * @brief Finds the places in ranges which don't match.
1976  * @ingroup non_mutating_algorithms
1977  * @param __first1 An input iterator.
1978  * @param __last1 An input iterator.
1979  * @param __first2 An input iterator.
1980  * @param __binary_pred A binary predicate @link functors
1981  * functor@endlink.
1982  * @return A pair of iterators pointing to the first mismatch.
1983  *
1984  * This compares the elements of two ranges using the binary_pred
1985  * parameter, and returns a pair
1986  * of iterators. The first iterator points into the first range, the
1987  * second iterator points into the second range, and the elements pointed
1988  * to by the iterators are not equal.
1989  */
1990  template<typename _InputIterator1, typename _InputIterator2,
1991  typename _BinaryPredicate>
1992  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1993  inline pair<_InputIterator1, _InputIterator2>
1994  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1995  _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1996  {
1997  // concept requirements
1998  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1999  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2000  __glibcxx_requires_valid_range(__first1, __last1);
2001 
2002  return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
2003  __binary_pred);
2004  }
2005 
2006 #if __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14
2007  template<typename _InputIterator1, typename _InputIterator2,
2008  typename _BinaryPredicate>
2009  _GLIBCXX20_CONSTEXPR
2010  pair<_InputIterator1, _InputIterator2>
2011  __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2012  _InputIterator2 __first2, _InputIterator2 __last2,
2013  _BinaryPredicate __binary_pred)
2014  {
2015  while (__first1 != __last1 && __first2 != __last2
2016  && __binary_pred(*__first1, *__first2))
2017  {
2018  ++__first1;
2019  ++__first2;
2020  }
2021  return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
2022  }
2023 
2024  /**
2025  * @brief Finds the places in ranges which don't match.
2026  * @ingroup non_mutating_algorithms
2027  * @param __first1 An input iterator.
2028  * @param __last1 An input iterator.
2029  * @param __first2 An input iterator.
2030  * @param __last2 An input iterator.
2031  * @return A pair of iterators pointing to the first mismatch.
2032  *
2033  * This compares the elements of two ranges using @c == and returns a pair
2034  * of iterators. The first iterator points into the first range, the
2035  * second iterator points into the second range, and the elements pointed
2036  * to by the iterators are not equal.
2037  */
2038  template<typename _InputIterator1, typename _InputIterator2>
2039  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2040  inline pair<_InputIterator1, _InputIterator2>
2041  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2042  _InputIterator2 __first2, _InputIterator2 __last2)
2043  {
2044  // concept requirements
2045  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2046  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2047  __glibcxx_function_requires(_EqualOpConcept<
2048  typename iterator_traits<_InputIterator1>::value_type,
2049  typename iterator_traits<_InputIterator2>::value_type>)
2050  __glibcxx_requires_valid_range(__first1, __last1);
2051  __glibcxx_requires_valid_range(__first2, __last2);
2052 
2053  return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2054  __gnu_cxx::__ops::equal_to());
2055  }
2056 
2057  /**
2058  * @brief Finds the places in ranges which don't match.
2059  * @ingroup non_mutating_algorithms
2060  * @param __first1 An input iterator.
2061  * @param __last1 An input iterator.
2062  * @param __first2 An input iterator.
2063  * @param __last2 An input iterator.
2064  * @param __binary_pred A binary predicate @link functors
2065  * functor@endlink.
2066  * @return A pair of iterators pointing to the first mismatch.
2067  *
2068  * This compares the elements of two ranges using the binary_pred
2069  * parameter, and returns a pair
2070  * of iterators. The first iterator points into the first range, the
2071  * second iterator points into the second range, and the elements pointed
2072  * to by the iterators are not equal.
2073  */
2074  template<typename _InputIterator1, typename _InputIterator2,
2075  typename _BinaryPredicate>
2076  _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2077  inline pair<_InputIterator1, _InputIterator2>
2078  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2079  _InputIterator2 __first2, _InputIterator2 __last2,
2080  _BinaryPredicate __binary_pred)
2081  {
2082  // concept requirements
2083  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2084  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2085  __glibcxx_requires_valid_range(__first1, __last1);
2086  __glibcxx_requires_valid_range(__first2, __last2);
2087 
2088  return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2089  __binary_pred);
2090  }
2091 #endif // __glibcxx_robust_nonmodifying_seq_ops
2092 
2093 _GLIBCXX_END_NAMESPACE_ALGO
2094 
2095  // Implementation of std::find_if, also used in std::remove_if and others.
2096  template<typename _Iterator, typename _Predicate>
2097  _GLIBCXX20_CONSTEXPR
2098  inline _Iterator
2099  __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2100  {
2101 #pragma GCC unroll 4
2102  while (__first != __last && !__pred(*__first))
2103  ++__first;
2104  return __first;
2105  }
2106 
2107  template<typename _InputIterator, typename _Predicate>
2108  _GLIBCXX20_CONSTEXPR
2109  typename iterator_traits<_InputIterator>::difference_type
2110  __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2111  {
2112  typename iterator_traits<_InputIterator>::difference_type __n = 0;
2113  for (; __first != __last; ++__first)
2114  if (__pred(*__first))
2115  ++__n;
2116  return __n;
2117  }
2118 
2119  template<typename _ForwardIterator, typename _Predicate>
2120  _GLIBCXX20_CONSTEXPR
2121  _ForwardIterator
2122  __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2123  _Predicate __pred)
2124  {
2125  __first = std::__find_if(__first, __last, __pred);
2126  if (__first == __last)
2127  return __first;
2128  _ForwardIterator __result = __first;
2129  ++__first;
2130  for (; __first != __last; ++__first)
2131  if (!__pred(*__first))
2132  {
2133  *__result = _GLIBCXX_MOVE(*__first);
2134  ++__result;
2135  }
2136  return __result;
2137  }
2138 
2139  template<typename _ForwardIterator1, typename _ForwardIterator2,
2140  typename _BinaryPredicate>
2141  _GLIBCXX20_CONSTEXPR
2142  _ForwardIterator1
2143  __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2144  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2145  _BinaryPredicate __predicate)
2146  {
2147  // Test for empty ranges
2148  if (__first1 == __last1 || __first2 == __last2)
2149  return __first1;
2150 
2151  __decltype(*__first2) __first2_val(*__first2);
2152  __decltype(__gnu_cxx::__ops::bind2nd(__predicate, __first2_val))
2153  __match_first = __gnu_cxx::__ops::bind2nd(__predicate, __first2_val);
2154 
2155  // Test for a pattern of length 1.
2156  _ForwardIterator2 __p1(__first2);
2157  if (++__p1 == __last2)
2158  return std::__find_if(__first1, __last1, __match_first);
2159 
2160  // General case.
2161  _ForwardIterator1 __current = __first1;
2162 
2163  for (;;)
2164  {
2165  __first1 = std::__find_if(__first1, __last1, __match_first);
2166 
2167  if (__first1 == __last1)
2168  return __last1;
2169 
2170  _ForwardIterator2 __p = __p1;
2171  __current = __first1;
2172  if (++__current == __last1)
2173  return __last1;
2174 
2175  while (__predicate(*__current, *__p))
2176  {
2177  if (++__p == __last2)
2178  return __first1;
2179  if (++__current == __last1)
2180  return __last1;
2181  }
2182  ++__first1;
2183  }
2184  return __first1;
2185  }
2186 #undef __match_first
2187 
2188 #if __cplusplus >= 201103L
2189  template<typename _ForwardIterator1, typename _ForwardIterator2,
2190  typename _BinaryPredicate>
2191  _GLIBCXX20_CONSTEXPR
2192  bool
2193  __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2194  _ForwardIterator2 __first2, _BinaryPredicate __pred)
2195  {
2196  // Efficiently compare identical prefixes: O(N) if sequences
2197  // have the same elements in the same order.
2198  for (; __first1 != __last1; ++__first1, (void)++__first2)
2199  if (!__pred(*__first1, *__first2))
2200  break;
2201 
2202  if (__first1 == __last1)
2203  return true;
2204 
2205  // Establish __last2 assuming equal ranges by iterating over the
2206  // rest of the list.
2207  _ForwardIterator2 __last2 = __first2;
2208  std::advance(__last2, std::distance(__first1, __last1));
2209  for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2210  {
2211  auto&& __scan_val = *__scan;
2212  auto __scaneq = __gnu_cxx::__ops::bind1st(__pred, __scan_val);
2213  if (__scan != std::__find_if(__first1, __scan, __scaneq))
2214  continue; // We've seen this one before.
2215 
2216  auto __matches = std::__count_if(__first2, __last2, __scaneq);
2217  if (0 == __matches
2218  || std::__count_if(__scan, __last1, __scaneq) != __matches)
2219  return false;
2220  }
2221  return true;
2222  }
2223 
2224  /**
2225  * @brief Checks whether a permutation of the second sequence is equal
2226  * to the first sequence.
2227  * @ingroup non_mutating_algorithms
2228  * @param __first1 Start of first range.
2229  * @param __last1 End of first range.
2230  * @param __first2 Start of second range.
2231  * @return true if there exists a permutation of the elements in the range
2232  * [__first2, __first2 + (__last1 - __first1)), beginning with
2233  * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
2234  * returns true; otherwise, returns false.
2235  */
2236  template<typename _ForwardIterator1, typename _ForwardIterator2>
2237  _GLIBCXX20_CONSTEXPR
2238  inline bool
2239  is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2240  _ForwardIterator2 __first2)
2241  {
2242  // concept requirements
2243  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2244  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2245  __glibcxx_function_requires(_EqualOpConcept<
2246  typename iterator_traits<_ForwardIterator1>::value_type,
2247  typename iterator_traits<_ForwardIterator2>::value_type>)
2248  __glibcxx_requires_valid_range(__first1, __last1);
2249 
2250  return std::__is_permutation(__first1, __last1, __first2,
2251  __gnu_cxx::__ops::equal_to());
2252  }
2253 #endif // C++11
2254 
2255 _GLIBCXX_BEGIN_NAMESPACE_ALGO
2256 
2257  /**
2258  * @brief Search a sequence for a matching sub-sequence using a predicate.
2259  * @ingroup non_mutating_algorithms
2260  * @param __first1 A forward iterator.
2261  * @param __last1 A forward iterator.
2262  * @param __first2 A forward iterator.
2263  * @param __last2 A forward iterator.
2264  * @param __predicate A binary predicate.
2265  * @return The first iterator @c i in the range
2266  * @p [__first1,__last1-(__last2-__first2)) such that
2267  * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
2268  * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
2269  *
2270  * Searches the range @p [__first1,__last1) for a sub-sequence that
2271  * compares equal value-by-value with the sequence given by @p
2272  * [__first2,__last2), using @p __predicate to determine equality,
2273  * and returns an iterator to the first element of the
2274  * sub-sequence, or @p __last1 if no such iterator exists.
2275  *
2276  * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
2277  */
2278  template<typename _ForwardIterator1, typename _ForwardIterator2,
2279  typename _BinaryPredicate>
2280  _GLIBCXX20_CONSTEXPR
2281  inline _ForwardIterator1
2282  search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2283  _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2284  _BinaryPredicate __predicate)
2285  {
2286  // concept requirements
2287  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2288  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2289  __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
2290  typename iterator_traits<_ForwardIterator1>::value_type,
2291  typename iterator_traits<_ForwardIterator2>::value_type>)
2292  __glibcxx_requires_valid_range(__first1, __last1);
2293  __glibcxx_requires_valid_range(__first2, __last2);
2294 
2295  return std::__search(__first1, __last1, __first2, __last2, __predicate);
2296  }
2297 
2298 _GLIBCXX_END_NAMESPACE_ALGO
2299 _GLIBCXX_END_NAMESPACE_VERSION
2300 } // namespace std
2301 
2302 // NB: This file is included within many other C++ includes, as a way
2303 // of getting the base algorithms. So, make sure that parallel bits
2304 // come in too if requested.
2305 #ifdef _GLIBCXX_PARALLEL
2306 # include <parallel/algobase.h>
2307 #endif
2308 
2309 #endif
algobase.h
Parallel STL function calls corresponding to the stl_algobase.h header. The functions defined here ma...
std::to_address
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition: ptr_traits.h:232
std::make_unsigned_t
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
Definition: type_traits:2248
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
std::fill
constexpr void fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__value)
Fills the range [first,last) with copies of value.
Definition: stl_algobase.h:1003
std::copy
constexpr _OI copy(_II __first, _II __last, _OI __result)
Copies the range [first,last) into result.
Definition: stl_algobase.h:632
std::copy_backward
constexpr _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Copies the range [first,last) into result.
Definition: stl_algobase.h:836
std::move_backward
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
Definition: stl_algobase.h:872
std::fill_n
constexpr _OI fill_n(_OI __first, _Size __n, const _Tp &__value)
Fills the range [first,first+n) with copies of value.
Definition: stl_algobase.h:1181
std::equal
constexpr bool equal(_IIter1 __first1, _IIter1 __last1, _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
Tests a range for element-wise equality.
Definition: stl_algobase.h:1750
std::lexicographical_compare_three_way
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
Definition: stl_algobase.h:1869
std::max
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:257
std::min
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:233
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition: stl_iterator_base_types.h:241
std
ISO C++ entities toplevel namespace is std.
std::distance
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:172
std::same_as
concept same_as
[concept.same], concept same_as
Definition: concepts:65
std::__lg
constexpr _Tp __lg(_Tp __n)
This is a helper function for the sort routines and for random.tcc.
Definition: stl_algobase.h:1560
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition: stl_iterator_base_funcs.h:262
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: safe_iterator.h:133
std::iterator_traits
Traits class for iterators.
Definition: stl_iterator_base_types.h:180
std::equal_to< void >
One of the comparison functors.
Definition: stl_function.h:496
std::less< void >
One of the comparison functors.
Definition: stl_function.h:595
std::input_iterator_tag
Marking input iterators.
Definition: stl_iterator_base_types.h:95
std::output_iterator_tag
Marking output iterators.
Definition: stl_iterator_base_types.h:98
std::random_access_iterator_tag
Random-access iterators support a superset of bidirectional iterator operations.
Definition: stl_iterator_base_types.h:109