stl_algobase.h source code [include/c++/15.2.1/bits/stl_algobase.h]

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

Browse the source code of include/c++/15.2.1/bits/stl_algobase.h