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