stl_algo.h source code [include/c++/14.2.1/bits/stl_algo.h]

1	// Algorithm implementation -- C++ --
2
3	// Copyright (C) 2001-2024 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
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_algo.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_ALGO_H
57	#define _STL_ALGO_H 1
58
59	#include <bits/algorithmfwd.h>
60	#include <bits/stl_algobase.h>
61	#include <bits/stl_heap.h>
62	#include <bits/predefined_ops.h>
63
64	#if __cplusplus >= 201103L
65	#include <bits/uniform_int_dist.h>
66	#endif
67
68	#if _GLIBCXX_HOSTED
69	# include <bits/stl_tempbuf.h> // for _Temporary_buffer
70	# if (__cplusplus <= 201103L \|\| _GLIBCXX_USE_DEPRECATED)
71	# include <cstdlib> // for rand
72	# endif
73	#endif
74
75	// See concept_check.h for the __glibcxx__requires macros.*
76
77	namespace std _GLIBCXX_VISIBILITY(default)
78	{
79	_GLIBCXX_BEGIN_NAMESPACE_VERSION
80
81	/// Swaps the median value of __a, __b and __c under __comp to __result
82	template<typename _Iterator, typename _Compare>
83	_GLIBCXX20_CONSTEXPR
84	void
85	__move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
86	_Iterator __c, _Compare __comp)
87	{
88	if (__comp(__a, __b))
89	{
90	if (__comp(__b, __c))
91	std::iter_swap(__result, __b);
92	else if (__comp(__a, __c))
93	std::iter_swap(__result, __c);
94	else
95	std::iter_swap(__result, __a);
96	}
97	else if (__comp(__a, __c))
98	std::iter_swap(__result, __a);
99	else if (__comp(__b, __c))
100	std::iter_swap(__result, __c);
101	else
102	std::iter_swap(__result, __b);
103	}
104
105	/// Provided for stable_partition to use.
106	template<typename _InputIterator, typename _Predicate>
107	_GLIBCXX20_CONSTEXPR
108	inline _InputIterator
109	__find_if_not(_InputIterator __first, _InputIterator __last,
110	_Predicate __pred)
111	{
112	return std::__find_if(__first, __last,
113	__gnu_cxx::__ops::__negate(__pred),
114	std::__iterator_category(__first));
115	}
116
117	/// Like find_if_not(), but uses and updates a count of the
118	/// remaining range length instead of comparing against an end
119	/// iterator.
120	template<typename _InputIterator, typename _Predicate, typename _Distance>
121	_GLIBCXX20_CONSTEXPR
122	_InputIterator
123	__find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
124	{
125	for (; __len; --__len, (void) ++__first)
126	if (!__pred(__first))
127	break;
128	return __first;
129	}
130
131	// set_difference
132	// set_intersection
133	// set_symmetric_difference
134	// set_union
135	// for_each
136	// find
137	// find_if
138	// find_first_of
139	// adjacent_find
140	// count
141	// count_if
142	// search
143	// search_n
144
145	/**
146	* This is an helper function for search_n overloaded for forward iterators.
147	*/
148	template<typename _ForwardIterator, typename _Integer,
149	typename _UnaryPredicate>
150	_GLIBCXX20_CONSTEXPR
151	_ForwardIterator
152	__search_n_aux(_ForwardIterator __first, _ForwardIterator __last,
153	_Integer __count, _UnaryPredicate __unary_pred,
154	std::forward_iterator_tag)
155	{
156	__first = std::__find_if(__first, __last, __unary_pred);
157	while (__first != __last)
158	{
159	typename iterator_traits<_ForwardIterator>::difference_type
160	__n = __count;
161	_ForwardIterator __i = __first;
162	++__i;
163	while (__i != __last && __n != `1` && __unary_pred(__i))
164	{
165	++__i;
166	--__n;
167	}
168	if (__n == `1`)
169	return __first;
170	if (__i == __last)
171	return __last;
172	__first = std::__find_if(++__i, __last, __unary_pred);
173	}
174	return __last;
175	}
176
177	/**
178	* This is an helper function for search_n overloaded for random access
179	* iterators.
180	*/
181	template<typename _RandomAccessIter, typename _Integer,
182	typename _UnaryPredicate>
183	_GLIBCXX20_CONSTEXPR
184	_RandomAccessIter
185	__search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last,
186	_Integer __count, _UnaryPredicate __unary_pred,
187	std::random_access_iterator_tag)
188	{
189	typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
190	_DistanceType;
191
192	_DistanceType __tailSize = __last - __first;
193	_DistanceType __remainder = __count;
194
195	while (__remainder <= __tailSize) // the main loop...
196	{
197	__first += __remainder;
198	__tailSize -= __remainder;
199	// __first here is always pointing to one past the last element of
200	// next possible match.
201	_RandomAccessIter __backTrack = __first;
202	while (__unary_pred(--__backTrack))
203	{
204	if (--__remainder == `0`)
205	return (__first - __count); // Success
206	}
207	__remainder = __count + `1` - (__first - __backTrack);
208	}
209	return __last; // Failure
210	}
211
212	template<typename _ForwardIterator, typename _Integer,
213	typename _UnaryPredicate>
214	_GLIBCXX20_CONSTEXPR
215	_ForwardIterator
216	__search_n(_ForwardIterator __first, _ForwardIterator __last,
217	_Integer __count,
218	_UnaryPredicate __unary_pred)
219	{
220	if (__count <= `0`)
221	return __first;
222
223	if (__count == `1`)
224	return std::__find_if(__first, __last, __unary_pred);
225
226	return std::__search_n_aux(__first, __last, __count, __unary_pred,
227	std::__iterator_category(__first));
228	}
229
230	// find_end for forward iterators.
231	template<typename _ForwardIterator1, typename _ForwardIterator2,
232	typename _BinaryPredicate>
233	_GLIBCXX20_CONSTEXPR
234	_ForwardIterator1
235	__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
236	_ForwardIterator2 __first2, _ForwardIterator2 __last2,
237	forward_iterator_tag, forward_iterator_tag,
238	_BinaryPredicate __comp)
239	{
240	if (__first2 == __last2)
241	return __last1;
242
243	_ForwardIterator1 __result = __last1;
244	while (`1`)
245	{
246	_ForwardIterator1 __new_result
247	= std::__search(__first1, __last1, __first2, __last2, __comp);
248	if (__new_result == __last1)
249	return __result;
250	else
251	{
252	__result = __new_result;
253	__first1 = __new_result;
254	++__first1;
255	}
256	}
257	}
258
259	// find_end for bidirectional iterators (much faster).
260	template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
261	typename _BinaryPredicate>
262	_GLIBCXX20_CONSTEXPR
263	_BidirectionalIterator1
264	__find_end(_BidirectionalIterator1 __first1,
265	_BidirectionalIterator1 __last1,
266	_BidirectionalIterator2 __first2,
267	_BidirectionalIterator2 __last2,
268	bidirectional_iterator_tag, bidirectional_iterator_tag,
269	_BinaryPredicate __comp)
270	{
271	// concept requirements
272	__glibcxx_function_requires(_BidirectionalIteratorConcept<
273	_BidirectionalIterator1>)
274	__glibcxx_function_requires(_BidirectionalIteratorConcept<
275	_BidirectionalIterator2>)
276
277	typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
278	typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
279
280	_RevIterator1 __rlast1(__first1);
281	_RevIterator2 __rlast2(__first2);
282	_RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
283	_RevIterator2(__last2), __rlast2,
284	__comp);
285
286	if (__rresult == __rlast1)
287	return __last1;
288	else
289	{
290	_BidirectionalIterator1 __result = __rresult.base();
291	std::advance(__result, -std::distance(__first2, __last2));
292	return __result;
293	}
294	}
295
296	/**
297	* @brief Find last matching subsequence in a sequence.
298	* @ingroup non_mutating_algorithms
299	* @param __first1 Start of range to search.
300	* @param __last1 End of range to search.
301	* @param __first2 Start of sequence to match.
302	* @param __last2 End of sequence to match.
303	* @return The last iterator @c i in the range
304	* @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
305	* @p *(__first2+N) for each @c N in the range @p
306	* [0,__last2-__first2), or @p __last1 if no such iterator exists.
307	*
308	* Searches the range @p [__first1,__last1) for a sub-sequence that
309	* compares equal value-by-value with the sequence given by @p
310	* [__first2,__last2) and returns an iterator to the __first
311	* element of the sub-sequence, or @p __last1 if the sub-sequence
312	* is not found. The sub-sequence will be the last such
313	* subsequence contained in [__first1,__last1).
314	*
315	* Because the sub-sequence must lie completely within the range @p
316	* [__first1,__last1) it must start at a position less than @p
317	* __last1-(__last2-__first2) where @p __last2-__first2 is the
318	* length of the sub-sequence. This means that the returned
319	* iterator @c i will be in the range @p
320	* [__first1,__last1-(__last2-__first2))
321	*/
322	template<typename _ForwardIterator1, typename _ForwardIterator2>
323	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
324	inline _ForwardIterator1
325	find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
326	_ForwardIterator2 __first2, _ForwardIterator2 __last2)
327	{
328	// concept requirements
329	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
330	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
331	__glibcxx_function_requires(_EqualOpConcept<
332	typename iterator_traits<_ForwardIterator1>::value_type,
333	typename iterator_traits<_ForwardIterator2>::value_type>)
334	__glibcxx_requires_valid_range(__first1, __last1);
335	__glibcxx_requires_valid_range(__first2, __last2);
336
337	return std::__find_end(__first1, __last1, __first2, __last2,
338	std::__iterator_category(__first1),
339	std::__iterator_category(__first2),
340	__gnu_cxx::__ops::__iter_equal_to_iter());
341	}
342
343	/**
344	* @brief Find last matching subsequence in a sequence using a predicate.
345	* @ingroup non_mutating_algorithms
346	* @param __first1 Start of range to search.
347	* @param __last1 End of range to search.
348	* @param __first2 Start of sequence to match.
349	* @param __last2 End of sequence to match.
350	* @param __comp The predicate to use.
351	* @return The last iterator @c i in the range @p
352	* [__first1,__last1-(__last2-__first2)) such that @c
353	* predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
354	* range @p [0,__last2-__first2), or @p __last1 if no such iterator
355	* exists.
356	*
357	* Searches the range @p [__first1,__last1) for a sub-sequence that
358	* compares equal value-by-value with the sequence given by @p
359	* [__first2,__last2) using comp as a predicate and returns an
360	* iterator to the first element of the sub-sequence, or @p __last1
361	* if the sub-sequence is not found. The sub-sequence will be the
362	* last such subsequence contained in [__first,__last1).
363	*
364	* Because the sub-sequence must lie completely within the range @p
365	* [__first1,__last1) it must start at a position less than @p
366	* __last1-(__last2-__first2) where @p __last2-__first2 is the
367	* length of the sub-sequence. This means that the returned
368	* iterator @c i will be in the range @p
369	* [__first1,__last1-(__last2-__first2))
370	*/
371	template<typename _ForwardIterator1, typename _ForwardIterator2,
372	typename _BinaryPredicate>
373	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
374	inline _ForwardIterator1
375	find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
376	_ForwardIterator2 __first2, _ForwardIterator2 __last2,
377	_BinaryPredicate __comp)
378	{
379	// concept requirements
380	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
381	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
382	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
383	typename iterator_traits<_ForwardIterator1>::value_type,
384	typename iterator_traits<_ForwardIterator2>::value_type>)
385	__glibcxx_requires_valid_range(__first1, __last1);
386	__glibcxx_requires_valid_range(__first2, __last2);
387
388	return std::__find_end(__first1, __last1, __first2, __last2,
389	std::__iterator_category(__first1),
390	std::__iterator_category(__first2),
391	__gnu_cxx::__ops::__iter_comp_iter(__comp));
392	}
393
394	#if __cplusplus >= 201103L
395	/**
396	* @brief Checks that a predicate is true for all the elements
397	* of a sequence.
398	* @ingroup non_mutating_algorithms
399	* @param __first An input iterator.
400	* @param __last An input iterator.
401	* @param __pred A predicate.
402	* @return True if the check is true, false otherwise.
403	*
404	* Returns true if @p __pred is true for each element in the range
405	* @p [__first,__last), and false otherwise.
406	*/
407	template<typename _InputIterator, typename _Predicate>
408	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
409	inline bool
410	all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
411	{ return __last == std::find_if_not(__first, __last, __pred); }
412
413	/**
414	* @brief Checks that a predicate is false for all the elements
415	* of a sequence.
416	* @ingroup non_mutating_algorithms
417	* @param __first An input iterator.
418	* @param __last An input iterator.
419	* @param __pred A predicate.
420	* @return True if the check is true, false otherwise.
421	*
422	* Returns true if @p __pred is false for each element in the range
423	* @p [__first,__last), and false otherwise.
424	*/
425	template<typename _InputIterator, typename _Predicate>
426	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
427	inline bool
428	none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
429	{ return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
430
431	/**
432	* @brief Checks that a predicate is true for at least one element
433	* of a sequence.
434	* @ingroup non_mutating_algorithms
435	* @param __first An input iterator.
436	* @param __last An input iterator.
437	* @param __pred A predicate.
438	* @return True if the check is true, false otherwise.
439	*
440	* Returns true if an element exists in the range @p
441	* [__first,__last) such that @p __pred is true, and false
442	* otherwise.
443	*/
444	template<typename _InputIterator, typename _Predicate>
445	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
446	inline bool
447	any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
448	{ return !std::none_of(__first, __last, __pred); }
449
450	/**
451	* @brief Find the first element in a sequence for which a
452	* predicate is false.
453	* @ingroup non_mutating_algorithms
454	* @param __first An input iterator.
455	* @param __last An input iterator.
456	* @param __pred A predicate.
457	* @return The first iterator @c i in the range @p [__first,__last)
458	* such that @p __pred(*i) is false, or @p __last if no such iterator exists.
459	*/
460	template<typename _InputIterator, typename _Predicate>
461	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
462	inline _InputIterator
463	find_if_not(_InputIterator __first, _InputIterator __last,
464	_Predicate __pred)
465	{
466	// concept requirements
467	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
468	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
469	typename iterator_traits<_InputIterator>::value_type>)
470	__glibcxx_requires_valid_range(__first, __last);
471	return std::__find_if_not(__first, __last,
472	__gnu_cxx::__ops::__pred_iter(__pred));
473	}
474
475	/**
476	* @brief Checks whether the sequence is partitioned.
477	* @ingroup mutating_algorithms
478	* @param __first An input iterator.
479	* @param __last An input iterator.
480	* @param __pred A predicate.
481	* @return True if the range @p [__first,__last) is partioned by @p __pred,
482	* i.e. if all elements that satisfy @p __pred appear before those that
483	* do not.
484	*/
485	template<typename _InputIterator, typename _Predicate>
486	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
487	inline bool
488	is_partitioned(_InputIterator __first, _InputIterator __last,
489	_Predicate __pred)
490	{
491	__first = std::find_if_not(__first, __last, __pred);
492	if (__first == __last)
493	return true;
494	++__first;
495	return std::none_of(__first, __last, __pred);
496	}
497
498	/**
499	* @brief Find the partition point of a partitioned range.
500	* @ingroup mutating_algorithms
501	* @param __first An iterator.
502	* @param __last Another iterator.
503	* @param __pred A predicate.
504	* @return An iterator @p mid such that @p all_of(__first, mid, __pred)
505	* and @p none_of(mid, __last, __pred) are both true.
506	*/
507	template<typename _ForwardIterator, typename _Predicate>
508	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
509	_ForwardIterator
510	partition_point(_ForwardIterator __first, _ForwardIterator __last,
511	_Predicate __pred)
512	{
513	// concept requirements
514	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
515	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
516	typename iterator_traits<_ForwardIterator>::value_type>)
517
518	// A specific debug-mode test will be necessary...
519	__glibcxx_requires_valid_range(__first, __last);
520
521	typedef typename iterator_traits<_ForwardIterator>::difference_type
522	_DistanceType;
523
524	_DistanceType __len = std::distance(__first, __last);
525
526	while (__len > `0`)
527	{
528	_DistanceType __half = __len >> `1`;
529	_ForwardIterator __middle = __first;
530	std::advance(__middle, __half);
531	if (__pred(*__middle))
532	{
533	__first = __middle;
534	++__first;
535	__len = __len - __half - `1`;
536	}
537	else
538	__len = __half;
539	}
540	return __first;
541	}
542	#endif
543
544	template<typename _InputIterator, typename _OutputIterator,
545	typename _Predicate>
546	_GLIBCXX20_CONSTEXPR
547	_OutputIterator
548	__remove_copy_if(_InputIterator __first, _InputIterator __last,
549	_OutputIterator __result, _Predicate __pred)
550	{
551	for (; __first != __last; ++__first)
552	if (!__pred(__first))
553	{
554	__result = __first;
555	++__result;
556	}
557	return __result;
558	}
559
560	/**
561	* @brief Copy a sequence, removing elements of a given value.
562	* @ingroup mutating_algorithms
563	* @param __first An input iterator.
564	* @param __last An input iterator.
565	* @param __result An output iterator.
566	* @param __value The value to be removed.
567	* @return An iterator designating the end of the resulting sequence.
568	*
569	* Copies each element in the range @p [__first,__last) not equal
570	* to @p __value to the range beginning at @p __result.
571	* remove_copy() is stable, so the relative order of elements that
572	* are copied is unchanged.
573	*/
574	template<typename _InputIterator, typename _OutputIterator, typename _Tp>
575	_GLIBCXX20_CONSTEXPR
576	inline _OutputIterator
577	remove_copy(_InputIterator __first, _InputIterator __last,
578	_OutputIterator __result, const _Tp& __value)
579	{
580	// concept requirements
581	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
582	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
583	typename iterator_traits<_InputIterator>::value_type>)
584	__glibcxx_function_requires(_EqualOpConcept<
585	typename iterator_traits<_InputIterator>::value_type, _Tp>)
586	__glibcxx_requires_valid_range(__first, __last);
587
588	return std::__remove_copy_if(__first, __last, __result,
589	__gnu_cxx::__ops::__iter_equals_val(__value));
590	}
591
592	/**
593	* @brief Copy a sequence, removing elements for which a predicate is true.
594	* @ingroup mutating_algorithms
595	* @param __first An input iterator.
596	* @param __last An input iterator.
597	* @param __result An output iterator.
598	* @param __pred A predicate.
599	* @return An iterator designating the end of the resulting sequence.
600	*
601	* Copies each element in the range @p [__first,__last) for which
602	* @p __pred returns false to the range beginning at @p __result.
603	*
604	* remove_copy_if() is stable, so the relative order of elements that are
605	* copied is unchanged.
606	*/
607	template<typename _InputIterator, typename _OutputIterator,
608	typename _Predicate>
609	_GLIBCXX20_CONSTEXPR
610	inline _OutputIterator
611	remove_copy_if(_InputIterator __first, _InputIterator __last,
612	_OutputIterator __result, _Predicate __pred)
613	{
614	// concept requirements
615	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
616	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
617	typename iterator_traits<_InputIterator>::value_type>)
618	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
619	typename iterator_traits<_InputIterator>::value_type>)
620	__glibcxx_requires_valid_range(__first, __last);
621
622	return std::__remove_copy_if(__first, __last, __result,
623	__gnu_cxx::__ops::__pred_iter(__pred));
624	}
625
626	#if __cplusplus >= 201103L
627	/**
628	* @brief Copy the elements of a sequence for which a predicate is true.
629	* @ingroup mutating_algorithms
630	* @param __first An input iterator.
631	* @param __last An input iterator.
632	* @param __result An output iterator.
633	* @param __pred A predicate.
634	* @return An iterator designating the end of the resulting sequence.
635	*
636	* Copies each element in the range @p [__first,__last) for which
637	* @p __pred returns true to the range beginning at @p __result.
638	*
639	* copy_if() is stable, so the relative order of elements that are
640	* copied is unchanged.
641	*/
642	template<typename _InputIterator, typename _OutputIterator,
643	typename _Predicate>
644	_GLIBCXX20_CONSTEXPR
645	_OutputIterator
646	copy_if(_InputIterator __first, _InputIterator __last,
647	_OutputIterator __result, _Predicate __pred)
648	{
649	// concept requirements
650	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
651	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
652	typename iterator_traits<_InputIterator>::value_type>)
653	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
654	typename iterator_traits<_InputIterator>::value_type>)
655	__glibcxx_requires_valid_range(__first, __last);
656
657	for (; __first != __last; ++__first)
658	if (__pred(*__first))
659	{
660	__result = __first;
661	++__result;
662	}
663	return __result;
664	}
665
666	template<typename _InputIterator, typename _Size, typename _OutputIterator>
667	_GLIBCXX20_CONSTEXPR
668	_OutputIterator
669	__copy_n(_InputIterator __first, _Size __n,
670	_OutputIterator __result, input_iterator_tag)
671	{
672	return std::__niter_wrap(__result,
673	__copy_n_a(__first, __n,
674	std::__niter_base(__result), true));
675	}
676
677	template<typename _RandomAccessIterator, typename _Size,
678	typename _OutputIterator>
679	_GLIBCXX20_CONSTEXPR
680	inline _OutputIterator
681	__copy_n(_RandomAccessIterator __first, _Size __n,
682	_OutputIterator __result, random_access_iterator_tag)
683	{ return std::copy(__first, __first + __n, __result); }
684
685	/**
686	* @brief Copies the range [first,first+n) into [result,result+n).
687	* @ingroup mutating_algorithms
688	* @param __first An input iterator.
689	* @param __n The number of elements to copy.
690	* @param __result An output iterator.
691	* @return result+n.
692	*
693	* This inline function will boil down to a call to @c memmove whenever
694	* possible. Failing that, if random access iterators are passed, then the
695	* loop count will be known (and therefore a candidate for compiler
696	* optimizations such as unrolling).
697	*/
698	template<typename _InputIterator, typename _Size, typename _OutputIterator>
699	_GLIBCXX20_CONSTEXPR
700	inline _OutputIterator
701	copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
702	{
703	// concept requirements
704	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
705	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
706	typename iterator_traits<_InputIterator>::value_type>)
707
708	const auto __n2 = std::__size_to_integer(__n);
709	if (__n2 <= `0`)
710	return __result;
711
712	__glibcxx_requires_can_increment(__first, __n2);
713	__glibcxx_requires_can_increment(__result, __n2);
714
715	return std::__copy_n(__first, __n2, __result,
716	std::__iterator_category(__first));
717	}
718
719	/**
720	* @brief Copy the elements of a sequence to separate output sequences
721	* depending on the truth value of a predicate.
722	* @ingroup mutating_algorithms
723	* @param __first An input iterator.
724	* @param __last An input iterator.
725	* @param __out_true An output iterator.
726	* @param __out_false An output iterator.
727	* @param __pred A predicate.
728	* @return A pair designating the ends of the resulting sequences.
729	*
730	* Copies each element in the range @p [__first,__last) for which
731	* @p __pred returns true to the range beginning at @p out_true
732	* and each element for which @p __pred returns false to @p __out_false.
733	*/
734	template<typename _InputIterator, typename _OutputIterator1,
735	typename _OutputIterator2, typename _Predicate>
736	_GLIBCXX20_CONSTEXPR
737	pair<_OutputIterator1, _OutputIterator2>
738	partition_copy(_InputIterator __first, _InputIterator __last,
739	_OutputIterator1 __out_true, _OutputIterator2 __out_false,
740	_Predicate __pred)
741	{
742	// concept requirements
743	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
744	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
745	typename iterator_traits<_InputIterator>::value_type>)
746	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
747	typename iterator_traits<_InputIterator>::value_type>)
748	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
749	typename iterator_traits<_InputIterator>::value_type>)
750	__glibcxx_requires_valid_range(__first, __last);
751
752	for (; __first != __last; ++__first)
753	if (__pred(*__first))
754	{
755	__out_true = __first;
756	++__out_true;
757	}
758	else
759	{
760	__out_false = __first;
761	++__out_false;
762	}
763
764	return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
765	}
766	#endif // C++11
767
768	/**
769	* @brief Remove elements from a sequence.
770	* @ingroup mutating_algorithms
771	* @param __first An input iterator.
772	* @param __last An input iterator.
773	* @param __value The value to be removed.
774	* @return An iterator designating the end of the resulting sequence.
775	*
776	* All elements equal to @p __value are removed from the range
777	* @p [__first,__last).
778	*
779	* remove() is stable, so the relative order of elements that are
780	* not removed is unchanged.
781	*
782	* Elements between the end of the resulting sequence and @p __last
783	* are still present, but their value is unspecified.
784	*/
785	template<typename _ForwardIterator, typename _Tp>
786	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
787	inline _ForwardIterator
788	remove(_ForwardIterator __first, _ForwardIterator __last,
789	const _Tp& __value)
790	{
791	// concept requirements
792	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
793	_ForwardIterator>)
794	__glibcxx_function_requires(_EqualOpConcept<
795	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
796	__glibcxx_requires_valid_range(__first, __last);
797
798	return std::__remove_if(__first, __last,
799	__gnu_cxx::__ops::__iter_equals_val(__value));
800	}
801
802	/**
803	* @brief Remove elements from a sequence using a predicate.
804	* @ingroup mutating_algorithms
805	* @param __first A forward iterator.
806	* @param __last A forward iterator.
807	* @param __pred A predicate.
808	* @return An iterator designating the end of the resulting sequence.
809	*
810	* All elements for which @p __pred returns true are removed from the range
811	* @p [__first,__last).
812	*
813	* remove_if() is stable, so the relative order of elements that are
814	* not removed is unchanged.
815	*
816	* Elements between the end of the resulting sequence and @p __last
817	* are still present, but their value is unspecified.
818	*/
819	template<typename _ForwardIterator, typename _Predicate>
820	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
821	inline _ForwardIterator
822	remove_if(_ForwardIterator __first, _ForwardIterator __last,
823	_Predicate __pred)
824	{
825	// concept requirements
826	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
827	_ForwardIterator>)
828	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
829	typename iterator_traits<_ForwardIterator>::value_type>)
830	__glibcxx_requires_valid_range(__first, __last);
831
832	return std::__remove_if(__first, __last,
833	__gnu_cxx::__ops::__pred_iter(__pred));
834	}
835
836	template<typename _ForwardIterator, typename _BinaryPredicate>
837	_GLIBCXX20_CONSTEXPR
838	_ForwardIterator
839	__adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
840	_BinaryPredicate __binary_pred)
841	{
842	if (__first == __last)
843	return __last;
844	_ForwardIterator __next = __first;
845	while (++__next != __last)
846	{
847	if (__binary_pred(__first, __next))
848	return __first;
849	__first = __next;
850	}
851	return __last;
852	}
853
854	template<typename _ForwardIterator, typename _BinaryPredicate>
855	_GLIBCXX20_CONSTEXPR
856	_ForwardIterator
857	__unique(_ForwardIterator __first, _ForwardIterator __last,
858	_BinaryPredicate __binary_pred)
859	{
860	// Skip the beginning, if already unique.
861	__first = std::__adjacent_find(__first, __last, __binary_pred);
862	if (__first == __last)
863	return __last;
864
865	// Do the real copy work.
866	_ForwardIterator __dest = __first;
867	++__first;
868	while (++__first != __last)
869	if (!__binary_pred(__dest, __first))
870	++__dest = _GLIBCXX_MOVE(__first);
871	return ++__dest;
872	}
873
874	/**
875	* @brief Remove consecutive duplicate values from a sequence.
876	* @ingroup mutating_algorithms
877	* @param __first A forward iterator.
878	* @param __last A forward iterator.
879	* @return An iterator designating the end of the resulting sequence.
880	*
881	* Removes all but the first element from each group of consecutive
882	* values that compare equal.
883	* unique() is stable, so the relative order of elements that are
884	* not removed is unchanged.
885	* Elements between the end of the resulting sequence and @p __last
886	* are still present, but their value is unspecified.
887	*/
888	template<typename _ForwardIterator>
889	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
890	inline _ForwardIterator
891	unique(_ForwardIterator __first, _ForwardIterator __last)
892	{
893	// concept requirements
894	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
895	_ForwardIterator>)
896	__glibcxx_function_requires(_EqualityComparableConcept<
897	typename iterator_traits<_ForwardIterator>::value_type>)
898	__glibcxx_requires_valid_range(__first, __last);
899
900	return std::__unique(__first, __last,
901	__gnu_cxx::__ops::__iter_equal_to_iter());
902	}
903
904	/**
905	* @brief Remove consecutive values from a sequence using a predicate.
906	* @ingroup mutating_algorithms
907	* @param __first A forward iterator.
908	* @param __last A forward iterator.
909	* @param __binary_pred A binary predicate.
910	* @return An iterator designating the end of the resulting sequence.
911	*
912	* Removes all but the first element from each group of consecutive
913	* values for which @p __binary_pred returns true.
914	* unique() is stable, so the relative order of elements that are
915	* not removed is unchanged.
916	* Elements between the end of the resulting sequence and @p __last
917	* are still present, but their value is unspecified.
918	*/
919	template<typename _ForwardIterator, typename _BinaryPredicate>
920	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
921	inline _ForwardIterator
922	unique(_ForwardIterator __first, _ForwardIterator __last,
923	_BinaryPredicate __binary_pred)
924	{
925	// concept requirements
926	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
927	_ForwardIterator>)
928	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
929	typename iterator_traits<_ForwardIterator>::value_type,
930	typename iterator_traits<_ForwardIterator>::value_type>)
931	__glibcxx_requires_valid_range(__first, __last);
932
933	return std::__unique(__first, __last,
934	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
935	}
936
937	/**
938	* This is an uglified
939	* unique_copy(_InputIterator, _InputIterator, _OutputIterator,
940	* _BinaryPredicate)
941	* overloaded for forward iterators and output iterator as result.
942	*/
943	template<typename _ForwardIterator, typename _OutputIterator,
944	typename _BinaryPredicate>
945	_GLIBCXX20_CONSTEXPR
946	_OutputIterator
947	__unique_copy(_ForwardIterator __first, _ForwardIterator __last,
948	_OutputIterator __result, _BinaryPredicate __binary_pred,
949	forward_iterator_tag, output_iterator_tag)
950	{
951	// concept requirements -- iterators already checked
952	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
953	typename iterator_traits<_ForwardIterator>::value_type,
954	typename iterator_traits<_ForwardIterator>::value_type>)
955
956	_ForwardIterator __next = __first;
957	__result = __first;
958	while (++__next != __last)
959	if (!__binary_pred(__first, __next))
960	{
961	__first = __next;
962	++__result = __first;
963	}
964	return ++__result;
965	}
966
967	/**
968	* This is an uglified
969	* unique_copy(_InputIterator, _InputIterator, _OutputIterator,
970	* _BinaryPredicate)
971	* overloaded for input iterators and output iterator as result.
972	*/
973	template<typename _InputIterator, typename _OutputIterator,
974	typename _BinaryPredicate>
975	_GLIBCXX20_CONSTEXPR
976	_OutputIterator
977	__unique_copy(_InputIterator __first, _InputIterator __last,
978	_OutputIterator __result, _BinaryPredicate __binary_pred,
979	input_iterator_tag, output_iterator_tag)
980	{
981	// concept requirements -- iterators already checked
982	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
983	typename iterator_traits<_InputIterator>::value_type,
984	typename iterator_traits<_InputIterator>::value_type>)
985
986	typename iterator_traits<_InputIterator>::value_type __value = *__first;
987	__decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
988	__rebound_pred
989	= __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
990	*__result = __value;
991	while (++__first != __last)
992	if (!__rebound_pred(__first, __value))
993	{
994	__value = *__first;
995	*++__result = __value;
996	}
997	return ++__result;
998	}
999
1000	/**
1001	* This is an uglified
1002	* unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1003	* _BinaryPredicate)
1004	* overloaded for input iterators and forward iterator as result.
1005	*/
1006	template<typename _InputIterator, typename _ForwardIterator,
1007	typename _BinaryPredicate>
1008	_GLIBCXX20_CONSTEXPR
1009	_ForwardIterator
1010	__unique_copy(_InputIterator __first, _InputIterator __last,
1011	_ForwardIterator __result, _BinaryPredicate __binary_pred,
1012	input_iterator_tag, forward_iterator_tag)
1013	{
1014	// concept requirements -- iterators already checked
1015	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1016	typename iterator_traits<_ForwardIterator>::value_type,
1017	typename iterator_traits<_InputIterator>::value_type>)
1018	__result = __first;
1019	while (++__first != __last)
1020	if (!__binary_pred(__result, __first))
1021	++__result = __first;
1022	return ++__result;
1023	}
1024
1025	/**
1026	* This is an uglified reverse(_BidirectionalIterator,
1027	* _BidirectionalIterator)
1028	* overloaded for bidirectional iterators.
1029	*/
1030	template<typename _BidirectionalIterator>
1031	_GLIBCXX20_CONSTEXPR
1032	void
1033	__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1034	bidirectional_iterator_tag)
1035	{
1036	while (true)
1037	if (__first == __last \|\| __first == --__last)
1038	return;
1039	else
1040	{
1041	std::iter_swap(__first, __last);
1042	++__first;
1043	}
1044	}
1045
1046	/**
1047	* This is an uglified reverse(_BidirectionalIterator,
1048	* _BidirectionalIterator)
1049	* overloaded for random access iterators.
1050	*/
1051	template<typename _RandomAccessIterator>
1052	_GLIBCXX20_CONSTEXPR
1053	void
1054	__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1055	random_access_iterator_tag)
1056	{
1057	if (__first == __last)
1058	return;
1059	--__last;
1060	while (__first < __last)
1061	{
1062	std::iter_swap(__first, __last);
1063	++__first;
1064	--__last;
1065	}
1066	}
1067
1068	/**
1069	* @brief Reverse a sequence.
1070	* @ingroup mutating_algorithms
1071	* @param __first A bidirectional iterator.
1072	* @param __last A bidirectional iterator.
1073	* @return reverse() returns no value.
1074	*
1075	* Reverses the order of the elements in the range @p [__first,__last),
1076	* so that the first element becomes the last etc.
1077	* For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1078	* swaps @p (__first+i) and @p (__last-(i+1))
1079	*/
1080	template<typename _BidirectionalIterator>
1081	_GLIBCXX20_CONSTEXPR
1082	inline void
1083	reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1084	{
1085	// concept requirements
1086	__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1087	_BidirectionalIterator>)
1088	__glibcxx_requires_valid_range(__first, __last);
1089	std::__reverse(__first, __last, std::__iterator_category(__first));
1090	}
1091
1092	/**
1093	* @brief Copy a sequence, reversing its elements.
1094	* @ingroup mutating_algorithms
1095	* @param __first A bidirectional iterator.
1096	* @param __last A bidirectional iterator.
1097	* @param __result An output iterator.
1098	* @return An iterator designating the end of the resulting sequence.
1099	*
1100	* Copies the elements in the range @p [__first,__last) to the
1101	* range @p [__result,__result+(__last-__first)) such that the
1102	* order of the elements is reversed. For every @c i such that @p
1103	* 0<=i<=(__last-__first), @p reverse_copy() performs the
1104	* assignment @p (__result+(__last-__first)-1-i) = (__first+i).
1105	* The ranges @p [__first,__last) and @p
1106	* [__result,__result+(__last-__first)) must not overlap.
1107	*/
1108	template<typename _BidirectionalIterator, typename _OutputIterator>
1109	_GLIBCXX20_CONSTEXPR
1110	_OutputIterator
1111	reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1112	_OutputIterator __result)
1113	{
1114	// concept requirements
1115	__glibcxx_function_requires(_BidirectionalIteratorConcept<
1116	_BidirectionalIterator>)
1117	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1118	typename iterator_traits<_BidirectionalIterator>::value_type>)
1119	__glibcxx_requires_valid_range(__first, __last);
1120
1121	while (__first != __last)
1122	{
1123	--__last;
1124	__result = __last;
1125	++__result;
1126	}
1127	return __result;
1128	}
1129
1130	/**
1131	* This is a helper function for the rotate algorithm specialized on RAIs.
1132	* It returns the greatest common divisor of two integer values.
1133	*/
1134	template<typename _EuclideanRingElement>
1135	_GLIBCXX20_CONSTEXPR
1136	_EuclideanRingElement
1137	__gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1138	{
1139	while (__n != `0`)
1140	{
1141	_EuclideanRingElement __t = __m % __n;
1142	__m = __n;
1143	__n = __t;
1144	}
1145	return __m;
1146	}
1147
1148	_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1149
1150	/// This is a helper function for the rotate algorithm.
1151	template<typename _ForwardIterator>
1152	_GLIBCXX20_CONSTEXPR
1153	_ForwardIterator
1154	__rotate(_ForwardIterator __first,
1155	_ForwardIterator __middle,
1156	_ForwardIterator __last,
1157	forward_iterator_tag)
1158	{
1159	if (__first == __middle)
1160	return __last;
1161	else if (__last == __middle)
1162	return __first;
1163
1164	_ForwardIterator __first2 = __middle;
1165	do
1166	{
1167	std::iter_swap(__first, __first2);
1168	++__first;
1169	++__first2;
1170	if (__first == __middle)
1171	__middle = __first2;
1172	}
1173	while (__first2 != __last);
1174
1175	_ForwardIterator __ret = __first;
1176
1177	__first2 = __middle;
1178
1179	while (__first2 != __last)
1180	{
1181	std::iter_swap(__first, __first2);
1182	++__first;
1183	++__first2;
1184	if (__first == __middle)
1185	__middle = __first2;
1186	else if (__first2 == __last)
1187	__first2 = __middle;
1188	}
1189	return __ret;
1190	}
1191
1192	/// This is a helper function for the rotate algorithm.
1193	template<typename _BidirectionalIterator>
1194	_GLIBCXX20_CONSTEXPR
1195	_BidirectionalIterator
1196	__rotate(_BidirectionalIterator __first,
1197	_BidirectionalIterator __middle,
1198	_BidirectionalIterator __last,
1199	bidirectional_iterator_tag)
1200	{
1201	// concept requirements
1202	__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1203	_BidirectionalIterator>)
1204
1205	if (__first == __middle)
1206	return __last;
1207	else if (__last == __middle)
1208	return __first;
1209
1210	std::__reverse(__first, __middle, bidirectional_iterator_tag ());
1211	std::__reverse(__middle, __last, bidirectional_iterator_tag ());
1212
1213	while (__first != __middle && __middle != __last)
1214	{
1215	std::iter_swap(__first, --__last);
1216	++__first;
1217	}
1218
1219	if (__first == __middle)
1220	{
1221	std::__reverse(__middle, __last, bidirectional_iterator_tag ());
1222	return __last;
1223	}
1224	else
1225	{
1226	std::__reverse(__first, __middle, bidirectional_iterator_tag ());
1227	return __first;
1228	}
1229	}
1230
1231	/// This is a helper function for the rotate algorithm.
1232	template<typename _RandomAccessIterator>
1233	_GLIBCXX20_CONSTEXPR
1234	_RandomAccessIterator
1235	__rotate(_RandomAccessIterator __first,
1236	_RandomAccessIterator __middle,
1237	_RandomAccessIterator __last,
1238	random_access_iterator_tag)
1239	{
1240	// concept requirements
1241	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1242	_RandomAccessIterator>)
1243
1244	if (__first == __middle)
1245	return __last;
1246	else if (__last == __middle)
1247	return __first;
1248
1249	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1250	_Distance;
1251	typedef typename iterator_traits<_RandomAccessIterator>::value_type
1252	_ValueType;
1253
1254	#if __cplusplus >= 201103L
1255	typedef typename make_unsigned<_Distance>::type _UDistance;
1256	#else
1257	typedef _Distance _UDistance;
1258	#endif
1259
1260	_Distance __n = __last - __first;
1261	_Distance __k = __middle - __first;
1262
1263	if (__k == __n - __k)
1264	{
1265	std::swap_ranges(__first, __middle, __middle);
1266	return __middle;
1267	}
1268
1269	_RandomAccessIterator __p = __first;
1270	_RandomAccessIterator __ret = __first + (__last - __middle);
1271
1272	for (;;)
1273	{
1274	if (__k < __n - __k)
1275	{
1276	if (__is_pod(_ValueType) && __k == `1`)
1277	{
1278	_ValueType __t = _GLIBCXX_MOVE(*__p);
1279	_GLIBCXX_MOVE3(__p + `1`, __p + __n, __p);
1280	*(__p + __n - `1`) = _GLIBCXX_MOVE(__t);
1281	return __ret;
1282	}
1283	_RandomAccessIterator __q = __p + __k;
1284	for (_Distance __i = `0`; __i < __n - __k; ++ __i)
1285	{
1286	std::iter_swap(__p, __q);
1287	++__p;
1288	++__q;
1289	}
1290	__n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k);
1291	if (__n == `0`)
1292	return __ret;
1293	std::swap(__n, __k);
1294	__k = __n - __k;
1295	}
1296	else
1297	{
1298	__k = __n - __k;
1299	if (__is_pod(_ValueType) && __k == `1`)
1300	{
1301	_ValueType __t = _GLIBCXX_MOVE(*(__p + __n - `1`));
1302	_GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - `1`, __p + __n);
1303	*__p = _GLIBCXX_MOVE(__t);
1304	return __ret;
1305	}
1306	_RandomAccessIterator __q = __p + __n;
1307	__p = __q - __k;
1308	for (_Distance __i = `0`; __i < __n - __k; ++ __i)
1309	{
1310	--__p;
1311	--__q;
1312	std::iter_swap(__p, __q);
1313	}
1314	__n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k);
1315	if (__n == `0`)
1316	return __ret;
1317	std::swap(__n, __k);
1318	}
1319	}
1320	}
1321
1322	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1323	// DR 488. rotate throws away useful information
1324	/**
1325	* @brief Rotate the elements of a sequence.
1326	* @ingroup mutating_algorithms
1327	* @param __first A forward iterator.
1328	* @param __middle A forward iterator.
1329	* @param __last A forward iterator.
1330	* @return first + (last - middle).
1331	*
1332	* Rotates the elements of the range @p [__first,__last) by
1333	* @p (__middle - __first) positions so that the element at @p __middle
1334	* is moved to @p __first, the element at @p __middle+1 is moved to
1335	* @p __first+1 and so on for each element in the range
1336	* @p [__first,__last).
1337	*
1338	* This effectively swaps the ranges @p [__first,__middle) and
1339	* @p [__middle,__last).
1340	*
1341	* Performs
1342	* @p (__first+(n+(__last-__middle))%(__last-__first))=(__first+n)
1343	* for each @p n in the range @p [0,__last-__first).
1344	*/
1345	template<typename _ForwardIterator>
1346	_GLIBCXX20_CONSTEXPR
1347	inline _ForwardIterator
1348	rotate(_ForwardIterator __first, _ForwardIterator __middle,
1349	_ForwardIterator __last)
1350	{
1351	// concept requirements
1352	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1353	_ForwardIterator>)
1354	__glibcxx_requires_valid_range(__first, __middle);
1355	__glibcxx_requires_valid_range(__middle, __last);
1356
1357	return std::__rotate(__first, __middle, __last,
1358	std::__iterator_category(__first));
1359	}
1360
1361	_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1362
1363	/**
1364	* @brief Copy a sequence, rotating its elements.
1365	* @ingroup mutating_algorithms
1366	* @param __first A forward iterator.
1367	* @param __middle A forward iterator.
1368	* @param __last A forward iterator.
1369	* @param __result An output iterator.
1370	* @return An iterator designating the end of the resulting sequence.
1371	*
1372	* Copies the elements of the range @p [__first,__last) to the
1373	* range beginning at @result, rotating the copied elements by
1374	* @p (__middle-__first) positions so that the element at @p __middle
1375	* is moved to @p __result, the element at @p __middle+1 is moved
1376	* to @p __result+1 and so on for each element in the range @p
1377	* [__first,__last).
1378	*
1379	* Performs
1380	* @p (__result+(n+(__last-__middle))%(__last-__first))=(__first+n)
1381	* for each @p n in the range @p [0,__last-__first).
1382	*/
1383	template<typename _ForwardIterator, typename _OutputIterator>
1384	_GLIBCXX20_CONSTEXPR
1385	inline _OutputIterator
1386	rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1387	_ForwardIterator __last, _OutputIterator __result)
1388	{
1389	// concept requirements
1390	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1391	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1392	typename iterator_traits<_ForwardIterator>::value_type>)
1393	__glibcxx_requires_valid_range(__first, __middle);
1394	__glibcxx_requires_valid_range(__middle, __last);
1395
1396	return std::copy(__first, __middle,
1397	std::copy(__middle, __last, __result));
1398	}
1399
1400	/// This is a helper function...
1401	template<typename _ForwardIterator, typename _Predicate>
1402	_GLIBCXX20_CONSTEXPR
1403	_ForwardIterator
1404	__partition(_ForwardIterator __first, _ForwardIterator __last,
1405	_Predicate __pred, forward_iterator_tag)
1406	{
1407	if (__first == __last)
1408	return __first;
1409
1410	while (__pred(*__first))
1411	if (++__first == __last)
1412	return __first;
1413
1414	_ForwardIterator __next = __first;
1415
1416	while (++__next != __last)
1417	if (__pred(*__next))
1418	{
1419	std::iter_swap(__first, __next);
1420	++__first;
1421	}
1422
1423	return __first;
1424	}
1425
1426	/// This is a helper function...
1427	template<typename _BidirectionalIterator, typename _Predicate>
1428	_GLIBCXX20_CONSTEXPR
1429	_BidirectionalIterator
1430	__partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1431	_Predicate __pred, bidirectional_iterator_tag)
1432	{
1433	while (true)
1434	{
1435	while (true)
1436	if (__first == __last)
1437	return __first;
1438	else if (__pred(*__first))
1439	++__first;
1440	else
1441	break;
1442	--__last;
1443	while (true)
1444	if (__first == __last)
1445	return __first;
1446	else if (!bool(__pred(*__last)))
1447	--__last;
1448	else
1449	break;
1450	std::iter_swap(__first, __last);
1451	++__first;
1452	}
1453	}
1454
1455	#if _GLIBCXX_HOSTED
1456	// partition
1457
1458	/// This is a helper function...
1459	/// Requires __first != __last and !__pred(__first)
1460	/// and __len == distance(__first, __last).
1461	///
1462	/// !__pred(__first) allows us to guarantee that we don't
1463	/// move-assign an element onto itself.
1464	template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1465	typename _Distance>
1466	_ForwardIterator
1467	__stable_partition_adaptive(_ForwardIterator __first,
1468	_ForwardIterator __last,
1469	_Predicate __pred, _Distance __len,
1470	_Pointer __buffer,
1471	_Distance __buffer_size)
1472	{
1473	if (__len == `1`)
1474	return __first;
1475
1476	if (__len <= __buffer_size)
1477	{
1478	_ForwardIterator __result1 = __first;
1479	_Pointer __result2 = __buffer;
1480
1481	// The precondition guarantees that !__pred(__first), so
1482	// move that element to the buffer before starting the loop.
1483	// This ensures that we only call __pred once per element.
1484	__result2 = _GLIBCXX_MOVE(__first);
1485	++__result2;
1486	++__first;
1487	for (; __first != __last; ++__first)
1488	if (__pred(__first))
1489	{
1490	__result1 = _GLIBCXX_MOVE(__first);
1491	++__result1;
1492	}
1493	else
1494	{
1495	__result2 = _GLIBCXX_MOVE(__first);
1496	++__result2;
1497	}
1498
1499	_GLIBCXX_MOVE3(__buffer, __result2, __result1);
1500	return __result1;
1501	}
1502
1503	_ForwardIterator __middle = __first;
1504	std::advance(__middle, __len / `2`);
1505	_ForwardIterator __left_split =
1506	std::__stable_partition_adaptive(__first, __middle, __pred,
1507	__len / `2`, __buffer,
1508	__buffer_size);
1509
1510	// Advance past true-predicate values to satisfy this
1511	// function's preconditions.
1512	_Distance __right_len = __len - __len / `2`;
1513	_ForwardIterator __right_split =
1514	std::__find_if_not_n(__middle, __right_len, __pred);
1515
1516	if (__right_len)
1517	__right_split =
1518	std::__stable_partition_adaptive(__right_split, __last, __pred,
1519	__right_len,
1520	__buffer, __buffer_size);
1521
1522	return std::rotate(__left_split, __middle, __right_split);
1523	}
1524
1525	template<typename _ForwardIterator, typename _Predicate>
1526	_ForwardIterator
1527	__stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1528	_Predicate __pred)
1529	{
1530	__first = std::__find_if_not(__first, __last, __pred);
1531
1532	if (__first == __last)
1533	return __first;
1534
1535	typedef typename iterator_traits<_ForwardIterator>::value_type
1536	_ValueType;
1537	typedef typename iterator_traits<_ForwardIterator>::difference_type
1538	_DistanceType;
1539
1540	_Temporary_buffer<_ForwardIterator, _ValueType>
1541	__buf(__first, std::distance(__first, __last));
1542	return
1543	std::__stable_partition_adaptive(__first, __last, __pred,
1544	_DistanceType(__buf.requested_size()),
1545	__buf.begin(),
1546	_DistanceType(__buf.size()));
1547	}
1548
1549	/**
1550	* @brief Move elements for which a predicate is true to the beginning
1551	* of a sequence, preserving relative ordering.
1552	* @ingroup mutating_algorithms
1553	* @param __first A forward iterator.
1554	* @param __last A forward iterator.
1555	* @param __pred A predicate functor.
1556	* @return An iterator @p middle such that @p __pred(i) is true for each
1557	* iterator @p i in the range @p [first,middle) and false for each @p i
1558	* in the range @p [middle,last).
1559	*
1560	* Performs the same function as @p partition() with the additional
1561	* guarantee that the relative ordering of elements in each group is
1562	* preserved, so any two elements @p x and @p y in the range
1563	* @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1564	* relative ordering after calling @p stable_partition().
1565	*/
1566	template<typename _ForwardIterator, typename _Predicate>
1567	inline _ForwardIterator
1568	stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1569	_Predicate __pred)
1570	{
1571	// concept requirements
1572	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1573	_ForwardIterator>)
1574	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1575	typename iterator_traits<_ForwardIterator>::value_type>)
1576	__glibcxx_requires_valid_range(__first, __last);
1577
1578	return std::__stable_partition(__first, __last,
1579	__gnu_cxx::__ops::__pred_iter(__pred));
1580	}
1581	#endif // HOSTED
1582
1583	/// @cond undocumented
1584
1585	/// This is a helper function for the sort routines.
1586	template<typename _RandomAccessIterator, typename _Compare>
1587	_GLIBCXX20_CONSTEXPR
1588	void
1589	__heap_select(_RandomAccessIterator __first,
1590	_RandomAccessIterator __middle,
1591	_RandomAccessIterator __last, _Compare __comp)
1592	{
1593	std::__make_heap(__first, __middle, __comp);
1594	for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1595	if (__comp(__i, __first))
1596	std::__pop_heap(__first, __middle, __i, __comp);
1597	}
1598
1599	// partial_sort
1600
1601	template<typename _InputIterator, typename _RandomAccessIterator,
1602	typename _Compare>
1603	_GLIBCXX20_CONSTEXPR
1604	_RandomAccessIterator
1605	__partial_sort_copy(_InputIterator __first, _InputIterator __last,
1606	_RandomAccessIterator __result_first,
1607	_RandomAccessIterator __result_last,
1608	_Compare __comp)
1609	{
1610	typedef typename iterator_traits<_InputIterator>::value_type
1611	_InputValueType;
1612	typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1613	typedef typename _RItTraits::difference_type _DistanceType;
1614
1615	if (__result_first == __result_last)
1616	return __result_last;
1617	_RandomAccessIterator __result_real_last = __result_first;
1618	while (__first != __last && __result_real_last != __result_last)
1619	{
1620	__result_real_last = __first;
1621	++__result_real_last;
1622	++__first;
1623	}
1624
1625	std::__make_heap(__result_first, __result_real_last, __comp);
1626	while (__first != __last)
1627	{
1628	if (__comp(__first, __result_first))
1629	std::__adjust_heap(__result_first, _DistanceType(`0`),
1630	_DistanceType(__result_real_last
1631	- __result_first),
1632	_InputValueType(*__first), __comp);
1633	++__first;
1634	}
1635	std::__sort_heap(__result_first, __result_real_last, __comp);
1636	return __result_real_last;
1637	}
1638
1639	/// @endcond
1640
1641	/**
1642	* @brief Copy the smallest elements of a sequence.
1643	* @ingroup sorting_algorithms
1644	* @param __first An iterator.
1645	* @param __last Another iterator.
1646	* @param __result_first A random-access iterator.
1647	* @param __result_last Another random-access iterator.
1648	* @return An iterator indicating the end of the resulting sequence.
1649	*
1650	* Copies and sorts the smallest `N` values from the range
1651	* `[__first, __last)` to the range beginning at `__result_first`, where
1652	* the number of elements to be copied, `N`, is the smaller of
1653	* `(__last - __first)` and `(__result_last - __result_first)`.
1654	* After the sort if `i` and `j` are iterators in the range
1655	* `[__result_first,__result_first + N)` such that `i` precedes `j` then
1656	* `j < i` is false.
1657	* The value returned is `__result_first + N`.
1658	*/
1659	template<typename _InputIterator, typename _RandomAccessIterator>
1660	_GLIBCXX20_CONSTEXPR
1661	inline _RandomAccessIterator
1662	partial_sort_copy(_InputIterator __first, _InputIterator __last,
1663	_RandomAccessIterator __result_first,
1664	_RandomAccessIterator __result_last)
1665	{
1666	#ifdef _GLIBCXX_CONCEPT_CHECKS
1667	typedef typename iterator_traits<_InputIterator>::value_type
1668	_InputValueType;
1669	typedef typename iterator_traits<_RandomAccessIterator>::value_type
1670	_OutputValueType;
1671	#endif
1672
1673	// concept requirements
1674	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1675	__glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1676	_OutputValueType>)
1677	__glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1678	_OutputValueType>)
1679	__glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1680	__glibcxx_requires_valid_range(__first, __last);
1681	__glibcxx_requires_irreflexive(__first, __last);
1682	__glibcxx_requires_valid_range(__result_first, __result_last);
1683
1684	return std::__partial_sort_copy(__first, __last,
1685	__result_first, __result_last,
1686	__gnu_cxx::__ops::__iter_less_iter());
1687	}
1688
1689	/**
1690	* @brief Copy the smallest elements of a sequence using a predicate for
1691	* comparison.
1692	* @ingroup sorting_algorithms
1693	* @param __first An input iterator.
1694	* @param __last Another input iterator.
1695	* @param __result_first A random-access iterator.
1696	* @param __result_last Another random-access iterator.
1697	* @param __comp A comparison functor.
1698	* @return An iterator indicating the end of the resulting sequence.
1699	*
1700	* Copies and sorts the smallest `N` values from the range
1701	* `[__first, __last)` to the range beginning at `result_first`, where
1702	* the number of elements to be copied, `N`, is the smaller of
1703	* `(__last - __first)` and `(__result_last - __result_first)`.
1704	* After the sort if `i` and `j` are iterators in the range
1705	* `[__result_first, __result_first + N)` such that `i` precedes `j` then
1706	* `__comp(j, i)` is false.
1707	* The value returned is `__result_first + N`.
1708	*/
1709	template<typename _InputIterator, typename _RandomAccessIterator,
1710	typename _Compare>
1711	_GLIBCXX20_CONSTEXPR
1712	inline _RandomAccessIterator
1713	partial_sort_copy(_InputIterator __first, _InputIterator __last,
1714	_RandomAccessIterator __result_first,
1715	_RandomAccessIterator __result_last,
1716	_Compare __comp)
1717	{
1718	#ifdef _GLIBCXX_CONCEPT_CHECKS
1719	typedef typename iterator_traits<_InputIterator>::value_type
1720	_InputValueType;
1721	typedef typename iterator_traits<_RandomAccessIterator>::value_type
1722	_OutputValueType;
1723	#endif
1724
1725	// concept requirements
1726	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1727	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1728	_RandomAccessIterator>)
1729	__glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1730	_OutputValueType>)
1731	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1732	_InputValueType, _OutputValueType>)
1733	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1734	_OutputValueType, _OutputValueType>)
1735	__glibcxx_requires_valid_range(__first, __last);
1736	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1737	__glibcxx_requires_valid_range(__result_first, __result_last);
1738
1739	return std::__partial_sort_copy(__first, __last,
1740	__result_first, __result_last,
1741	__gnu_cxx::__ops::__iter_comp_iter(__comp));
1742	}
1743
1744	/// @cond undocumented
1745
1746	/// This is a helper function for the sort routine.
1747	template<typename _RandomAccessIterator, typename _Compare>
1748	_GLIBCXX20_CONSTEXPR
1749	void
1750	__unguarded_linear_insert(_RandomAccessIterator __last,
1751	_Compare __comp)
1752	{
1753	typename iterator_traits<_RandomAccessIterator>::value_type
1754	__val = _GLIBCXX_MOVE(*__last);
1755	_RandomAccessIterator __next = __last;
1756	--__next;
1757	while (__comp(__val, __next))
1758	{
1759	__last = _GLIBCXX_MOVE(__next);
1760	__last = __next;
1761	--__next;
1762	}
1763	*__last = _GLIBCXX_MOVE(__val);
1764	}
1765
1766	/// This is a helper function for the sort routine.
1767	template<typename _RandomAccessIterator, typename _Compare>
1768	_GLIBCXX20_CONSTEXPR
1769	void
1770	__insertion_sort(_RandomAccessIterator __first,
1771	_RandomAccessIterator __last, _Compare __comp)
1772	{
1773	if (__first == __last) return;
1774
1775	for (_RandomAccessIterator __i = __first + `1`; __i != __last; ++__i)
1776	{
1777	if (__comp(__i, __first))
1778	{
1779	typename iterator_traits<_RandomAccessIterator>::value_type
1780	__val = _GLIBCXX_MOVE(*__i);
1781	_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + `1`);
1782	*__first = _GLIBCXX_MOVE(__val);
1783	}
1784	else
1785	std::__unguarded_linear_insert(__i,
1786	__gnu_cxx::__ops::__val_comp_iter(__comp));
1787	}
1788	}
1789
1790	/// This is a helper function for the sort routine.
1791	template<typename _RandomAccessIterator, typename _Compare>
1792	_GLIBCXX20_CONSTEXPR
1793	inline void
1794	__unguarded_insertion_sort(_RandomAccessIterator __first,
1795	_RandomAccessIterator __last, _Compare __comp)
1796	{
1797	for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1798	std::__unguarded_linear_insert(__i,
1799	__gnu_cxx::__ops::__val_comp_iter(__comp));
1800	}
1801
1802	/**
1803	* @doctodo
1804	* This controls some aspect of the sort routines.
1805	*/
1806	enum { _S_threshold = `16` };
1807
1808	/// This is a helper function for the sort routine.
1809	template<typename _RandomAccessIterator, typename _Compare>
1810	_GLIBCXX20_CONSTEXPR
1811	void
1812	__final_insertion_sort(_RandomAccessIterator __first,
1813	_RandomAccessIterator __last, _Compare __comp)
1814	{
1815	if (__last - __first > int(_S_threshold))
1816	{
1817	std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
1818	std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
1819	__comp);
1820	}
1821	else
1822	std::__insertion_sort(__first, __last, __comp);
1823	}
1824
1825	/// This is a helper function...
1826	template<typename _RandomAccessIterator, typename _Compare>
1827	_GLIBCXX20_CONSTEXPR
1828	_RandomAccessIterator
1829	__unguarded_partition(_RandomAccessIterator __first,
1830	_RandomAccessIterator __last,
1831	_RandomAccessIterator __pivot, _Compare __comp)
1832	{
1833	while (true)
1834	{
1835	while (__comp(__first, __pivot))
1836	++__first;
1837	--__last;
1838	while (__comp(__pivot, __last))
1839	--__last;
1840	if (!(__first < __last))
1841	return __first;
1842	std::iter_swap(__first, __last);
1843	++__first;
1844	}
1845	}
1846
1847	/// This is a helper function...
1848	template<typename _RandomAccessIterator, typename _Compare>
1849	_GLIBCXX20_CONSTEXPR
1850	inline _RandomAccessIterator
1851	__unguarded_partition_pivot(_RandomAccessIterator __first,
1852	_RandomAccessIterator __last, _Compare __comp)
1853	{
1854	_RandomAccessIterator __mid = __first + (__last - __first) / `2`;
1855	std::__move_median_to_first(__first, __first + `1`, __mid, __last - `1`,
1856	__comp);
1857	return std::__unguarded_partition(__first + `1`, __last, __first, __comp);
1858	}
1859
1860	template<typename _RandomAccessIterator, typename _Compare>
1861	_GLIBCXX20_CONSTEXPR
1862	inline void
1863	__partial_sort(_RandomAccessIterator __first,
1864	_RandomAccessIterator __middle,
1865	_RandomAccessIterator __last,
1866	_Compare __comp)
1867	{
1868	std::__heap_select(__first, __middle, __last, __comp);
1869	std::__sort_heap(__first, __middle, __comp);
1870	}
1871
1872	/// This is a helper function for the sort routine.
1873	template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1874	_GLIBCXX20_CONSTEXPR
1875	void
1876	__introsort_loop(_RandomAccessIterator __first,
1877	_RandomAccessIterator __last,
1878	_Size __depth_limit, _Compare __comp)
1879	{
1880	while (__last - __first > int(_S_threshold))
1881	{
1882	if (__depth_limit == `0`)
1883	{
1884	std::__partial_sort(__first, __last, __last, __comp);
1885	return;
1886	}
1887	--__depth_limit;
1888	_RandomAccessIterator __cut =
1889	std::__unguarded_partition_pivot(__first, __last, __comp);
1890	std::__introsort_loop(__cut, __last, __depth_limit, __comp);
1891	__last = __cut;
1892	}
1893	}
1894
1895	// sort
1896
1897	template<typename _RandomAccessIterator, typename _Compare>
1898	_GLIBCXX20_CONSTEXPR
1899	inline void
1900	__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1901	_Compare __comp)
1902	{
1903	if (__first != __last)
1904	{
1905	std::__introsort_loop(__first, __last,
1906	std::__lg(__last - __first) * `2`,
1907	__comp);
1908	std::__final_insertion_sort(__first, __last, __comp);
1909	}
1910	}
1911
1912	template<typename _RandomAccessIterator, typename _Size, typename _Compare>
1913	_GLIBCXX20_CONSTEXPR
1914	void
1915	__introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1916	_RandomAccessIterator __last, _Size __depth_limit,
1917	_Compare __comp)
1918	{
1919	while (__last - __first > `3`)
1920	{
1921	if (__depth_limit == `0`)
1922	{
1923	std::__heap_select(__first, __nth + `1`, __last, __comp);
1924	// Place the nth largest element in its final position.
1925	std::iter_swap(__first, __nth);
1926	return;
1927	}
1928	--__depth_limit;
1929	_RandomAccessIterator __cut =
1930	std::__unguarded_partition_pivot(__first, __last, __comp);
1931	if (__cut <= __nth)
1932	__first = __cut;
1933	else
1934	__last = __cut;
1935	}
1936	std::__insertion_sort(__first, __last, __comp);
1937	}
1938
1939	/// @endcond
1940
1941	// nth_element
1942
1943	// lower_bound moved to stl_algobase.h
1944
1945	/**
1946	* @brief Finds the first position in which `__val` could be inserted
1947	* without changing the ordering.
1948	* @ingroup binary_search_algorithms
1949	* @param __first An iterator to the start of a sorted range.
1950	* @param __last A past-the-end iterator for the sorted range.
1951	* @param __val The search term.
1952	* @param __comp A functor to use for comparisons.
1953	* @return An iterator pointing to the first element _not less than_
1954	* `__val`, or `end()` if every element is less than `__val`.
1955	* @ingroup binary_search_algorithms
1956	*
1957	* The comparison function should have the same effects on ordering as
1958	* the function used for the initial sort.
1959	*/
1960	template<typename _ForwardIterator, typename _Tp, typename _Compare>
1961	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1962	inline _ForwardIterator
1963	lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1964	const _Tp& __val, _Compare __comp)
1965	{
1966	// concept requirements
1967	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1968	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1969	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1970	__glibcxx_requires_partitioned_lower_pred(__first, __last,
1971	__val, __comp);
1972
1973	return std::__lower_bound(__first, __last, __val,
1974	__gnu_cxx::__ops::__iter_comp_val(__comp));
1975	}
1976
1977	template<typename _ForwardIterator, typename _Tp, typename _Compare>
1978	_GLIBCXX20_CONSTEXPR
1979	_ForwardIterator
1980	__upper_bound(_ForwardIterator __first, _ForwardIterator __last,
1981	const _Tp& __val, _Compare __comp)
1982	{
1983	typedef typename iterator_traits<_ForwardIterator>::difference_type
1984	_DistanceType;
1985
1986	_DistanceType __len = std::distance(__first, __last);
1987
1988	while (__len > `0`)
1989	{
1990	_DistanceType __half = __len >> `1`;
1991	_ForwardIterator __middle = __first;
1992	std::advance(__middle, __half);
1993	if (__comp(__val, __middle))
1994	__len = __half;
1995	else
1996	{
1997	__first = __middle;
1998	++__first;
1999	__len = __len - __half - `1`;
2000	}
2001	}
2002	return __first;
2003	}
2004
2005	/**
2006	* @brief Finds the last position in which @p __val could be inserted
2007	* without changing the ordering.
2008	* @ingroup binary_search_algorithms
2009	* @param __first An iterator.
2010	* @param __last Another iterator.
2011	* @param __val The search term.
2012	* @return An iterator pointing to the first element greater than @p __val,
2013	* or end() if no elements are greater than @p __val.
2014	* @ingroup binary_search_algorithms
2015	*/
2016	template<typename _ForwardIterator, typename _Tp>
2017	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2018	inline _ForwardIterator
2019	upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2020	const _Tp& __val)
2021	{
2022	// concept requirements
2023	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2024	__glibcxx_function_requires(_LessThanOpConcept<
2025	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2026	__glibcxx_requires_partitioned_upper(__first, __last, __val);
2027
2028	return std::__upper_bound(__first, __last, __val,
2029	__gnu_cxx::__ops::__val_less_iter());
2030	}
2031
2032	/**
2033	* @brief Finds the last position in which @p __val could be inserted
2034	* without changing the ordering.
2035	* @ingroup binary_search_algorithms
2036	* @param __first An iterator.
2037	* @param __last Another iterator.
2038	* @param __val The search term.
2039	* @param __comp A functor to use for comparisons.
2040	* @return An iterator pointing to the first element greater than @p __val,
2041	* or end() if no elements are greater than @p __val.
2042	* @ingroup binary_search_algorithms
2043	*
2044	* The comparison function should have the same effects on ordering as
2045	* the function used for the initial sort.
2046	*/
2047	template<typename _ForwardIterator, typename _Tp, typename _Compare>
2048	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2049	inline _ForwardIterator
2050	upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2051	const _Tp& __val, _Compare __comp)
2052	{
2053	// concept requirements
2054	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2055	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2056	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2057	__glibcxx_requires_partitioned_upper_pred(__first, __last,
2058	__val, __comp);
2059
2060	return std::__upper_bound(__first, __last, __val,
2061	__gnu_cxx::__ops::__val_comp_iter(__comp));
2062	}
2063
2064	template<typename _ForwardIterator, typename _Tp,
2065	typename _CompareItTp, typename _CompareTpIt>
2066	_GLIBCXX20_CONSTEXPR
2067	pair<_ForwardIterator, _ForwardIterator>
2068	__equal_range(_ForwardIterator __first, _ForwardIterator __last,
2069	const _Tp& __val,
2070	_CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2071	{
2072	typedef typename iterator_traits<_ForwardIterator>::difference_type
2073	_DistanceType;
2074
2075	_DistanceType __len = std::distance(__first, __last);
2076
2077	while (__len > `0`)
2078	{
2079	_DistanceType __half = __len >> `1`;
2080	_ForwardIterator __middle = __first;
2081	std::advance(__middle, __half);
2082	if (__comp_it_val(__middle, __val))
2083	{
2084	__first = __middle;
2085	++__first;
2086	__len = __len - __half - `1`;
2087	}
2088	else if (__comp_val_it(__val, __middle))
2089	__len = __half;
2090	else
2091	{
2092	_ForwardIterator __left
2093	= std::__lower_bound(__first, __middle, __val, __comp_it_val);
2094	std::advance(__first, __len);
2095	_ForwardIterator __right
2096	= std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2097	return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2098	}
2099	}
2100	return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2101	}
2102
2103	/**
2104	* @brief Finds the largest subrange in which @p __val could be inserted
2105	* at any place in it without changing the ordering.
2106	* @ingroup binary_search_algorithms
2107	* @param __first An iterator.
2108	* @param __last Another iterator.
2109	* @param __val The search term.
2110	* @return An pair of iterators defining the subrange.
2111	* @ingroup binary_search_algorithms
2112	*
2113	* This is equivalent to
2114	* @code
2115	* std::make_pair(lower_bound(__first, __last, __val),
2116	* upper_bound(__first, __last, __val))
2117	* @endcode
2118	* but does not actually call those functions.
2119	*/
2120	template<typename _ForwardIterator, typename _Tp>
2121	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2122	inline pair<_ForwardIterator, _ForwardIterator>
2123	equal_range(_ForwardIterator __first, _ForwardIterator __last,
2124	const _Tp& __val)
2125	{
2126	// concept requirements
2127	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2128	__glibcxx_function_requires(_LessThanOpConcept<
2129	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2130	__glibcxx_function_requires(_LessThanOpConcept<
2131	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2132	__glibcxx_requires_partitioned_lower(__first, __last, __val);
2133	__glibcxx_requires_partitioned_upper(__first, __last, __val);
2134
2135	return std::__equal_range(__first, __last, __val,
2136	__gnu_cxx::__ops::__iter_less_val(),
2137	__gnu_cxx::__ops::__val_less_iter());
2138	}
2139
2140	/**
2141	* @brief Finds the largest subrange in which @p __val could be inserted
2142	* at any place in it without changing the ordering.
2143	* @param __first An iterator.
2144	* @param __last Another iterator.
2145	* @param __val The search term.
2146	* @param __comp A functor to use for comparisons.
2147	* @return An pair of iterators defining the subrange.
2148	* @ingroup binary_search_algorithms
2149	*
2150	* This is equivalent to
2151	* @code
2152	* std::make_pair(lower_bound(__first, __last, __val, __comp),
2153	* upper_bound(__first, __last, __val, __comp))
2154	* @endcode
2155	* but does not actually call those functions.
2156	*/
2157	template<typename _ForwardIterator, typename _Tp, typename _Compare>
2158	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2159	inline pair<_ForwardIterator, _ForwardIterator>
2160	equal_range(_ForwardIterator __first, _ForwardIterator __last,
2161	const _Tp& __val, _Compare __comp)
2162	{
2163	// concept requirements
2164	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2165	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2166	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2167	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2168	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2169	__glibcxx_requires_partitioned_lower_pred(__first, __last,
2170	__val, __comp);
2171	__glibcxx_requires_partitioned_upper_pred(__first, __last,
2172	__val, __comp);
2173
2174	return std::__equal_range(__first, __last, __val,
2175	__gnu_cxx::__ops::__iter_comp_val(__comp),
2176	__gnu_cxx::__ops::__val_comp_iter(__comp));
2177	}
2178
2179	/**
2180	* @brief Determines whether an element exists in a range.
2181	* @ingroup binary_search_algorithms
2182	* @param __first An iterator.
2183	* @param __last Another iterator.
2184	* @param __val The search term.
2185	* @return True if @p __val (or its equivalent) is in [@p
2186	* __first,@p __last ].
2187	*
2188	* Note that this does not actually return an iterator to @p __val. For
2189	* that, use std::find or a container's specialized find member functions.
2190	*/
2191	template<typename _ForwardIterator, typename _Tp>
2192	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2193	bool
2194	binary_search(_ForwardIterator __first, _ForwardIterator __last,
2195	const _Tp& __val)
2196	{
2197	// concept requirements
2198	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2199	__glibcxx_function_requires(_LessThanOpConcept<
2200	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2201	__glibcxx_requires_partitioned_lower(__first, __last, __val);
2202	__glibcxx_requires_partitioned_upper(__first, __last, __val);
2203
2204	_ForwardIterator __i
2205	= std::__lower_bound(__first, __last, __val,
2206	__gnu_cxx::__ops::__iter_less_val());
2207	return __i != __last && !(__val < *__i);
2208	}
2209
2210	/**
2211	* @brief Determines whether an element exists in a range.
2212	* @ingroup binary_search_algorithms
2213	* @param __first An iterator.
2214	* @param __last Another iterator.
2215	* @param __val The search term.
2216	* @param __comp A functor to use for comparisons.
2217	* @return True if @p __val (or its equivalent) is in @p [__first,__last].
2218	*
2219	* Note that this does not actually return an iterator to @p __val. For
2220	* that, use std::find or a container's specialized find member functions.
2221	*
2222	* The comparison function should have the same effects on ordering as
2223	* the function used for the initial sort.
2224	*/
2225	template<typename _ForwardIterator, typename _Tp, typename _Compare>
2226	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2227	bool
2228	binary_search(_ForwardIterator __first, _ForwardIterator __last,
2229	const _Tp& __val, _Compare __comp)
2230	{
2231	// concept requirements
2232	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2233	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2234	_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
2235	__glibcxx_requires_partitioned_lower_pred(__first, __last,
2236	__val, __comp);
2237	__glibcxx_requires_partitioned_upper_pred(__first, __last,
2238	__val, __comp);
2239
2240	_ForwardIterator __i
2241	= std::__lower_bound(__first, __last, __val,
2242	__gnu_cxx::__ops::__iter_comp_val(__comp));
2243	return __i != __last && !bool(__comp(__val, *__i));
2244	}
2245
2246	// merge
2247
2248	/// This is a helper function for the __merge_adaptive routines.
2249	template<typename _InputIterator1, typename _InputIterator2,
2250	typename _OutputIterator, typename _Compare>
2251	void
2252	__move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2253	_InputIterator2 __first2, _InputIterator2 __last2,
2254	_OutputIterator __result, _Compare __comp)
2255	{
2256	while (__first1 != __last1 && __first2 != __last2)
2257	{
2258	if (__comp(__first2, __first1))
2259	{
2260	__result = _GLIBCXX_MOVE(__first2);
2261	++__first2;
2262	}
2263	else
2264	{
2265	__result = _GLIBCXX_MOVE(__first1);
2266	++__first1;
2267	}
2268	++__result;
2269	}
2270	if (__first1 != __last1)
2271	_GLIBCXX_MOVE3(__first1, __last1, __result);
2272	}
2273
2274	/// This is a helper function for the __merge_adaptive routines.
2275	template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2276	typename _BidirectionalIterator3, typename _Compare>
2277	void
2278	__move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2279	_BidirectionalIterator1 __last1,
2280	_BidirectionalIterator2 __first2,
2281	_BidirectionalIterator2 __last2,
2282	_BidirectionalIterator3 __result,
2283	_Compare __comp)
2284	{
2285	if (__first1 == __last1)
2286	{
2287	_GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2288	return;
2289	}
2290	else if (__first2 == __last2)
2291	return;
2292
2293	--__last1;
2294	--__last2;
2295	while (true)
2296	{
2297	if (__comp(__last2, __last1))
2298	{
2299	--__result = _GLIBCXX_MOVE(__last1);
2300	if (__first1 == __last1)
2301	{
2302	_GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2303	return;
2304	}
2305	--__last1;
2306	}
2307	else
2308	{
2309	--__result = _GLIBCXX_MOVE(__last2);
2310	if (__first2 == __last2)
2311	return;
2312	--__last2;
2313	}
2314	}
2315	}
2316
2317	/// This is a helper function for the merge routines.
2318	template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2319	typename _Distance>
2320	_BidirectionalIterator1
2321	__rotate_adaptive(_BidirectionalIterator1 __first,
2322	_BidirectionalIterator1 __middle,
2323	_BidirectionalIterator1 __last,
2324	_Distance __len1, _Distance __len2,
2325	_BidirectionalIterator2 __buffer,
2326	_Distance __buffer_size)
2327	{
2328	_BidirectionalIterator2 __buffer_end;
2329	if (__len1 > __len2 && __len2 <= __buffer_size)
2330	{
2331	if (__len2)
2332	{
2333	__buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2334	_GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2335	return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2336	}
2337	else
2338	return __first;
2339	}
2340	else if (__len1 <= __buffer_size)
2341	{
2342	if (__len1)
2343	{
2344	__buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2345	_GLIBCXX_MOVE3(__middle, __last, __first);
2346	return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2347	}
2348	else
2349	return __last;
2350	}
2351	else
2352	return std::rotate(__first, __middle, __last);
2353	}
2354
2355	/// This is a helper function for the merge routines.
2356	template<typename _BidirectionalIterator, typename _Distance,
2357	typename _Pointer, typename _Compare>
2358	void
2359	__merge_adaptive(_BidirectionalIterator __first,
2360	_BidirectionalIterator __middle,
2361	_BidirectionalIterator __last,
2362	_Distance __len1, _Distance __len2,
2363	_Pointer __buffer, _Compare __comp)
2364	{
2365	if (__len1 <= __len2)
2366	{
2367	_Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2368	std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2369	__first, __comp);
2370	}
2371	else
2372	{
2373	_Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2374	std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2375	__buffer_end, __last, __comp);
2376	}
2377	}
2378
2379	template<typename _BidirectionalIterator, typename _Distance,
2380	typename _Pointer, typename _Compare>
2381	void
2382	__merge_adaptive_resize(_BidirectionalIterator __first,
2383	_BidirectionalIterator __middle,
2384	_BidirectionalIterator __last,
2385	_Distance __len1, _Distance __len2,
2386	_Pointer __buffer, _Distance __buffer_size,
2387	_Compare __comp)
2388	{
2389	if (__len1 <= __buffer_size \|\| __len2 <= __buffer_size)
2390	std::__merge_adaptive(__first, __middle, __last,
2391	__len1, __len2, __buffer, __comp);
2392	else
2393	{
2394	_BidirectionalIterator __first_cut = __first;
2395	_BidirectionalIterator __second_cut = __middle;
2396	_Distance __len11 = `0`;
2397	_Distance __len22 = `0`;
2398	if (__len1 > __len2)
2399	{
2400	__len11 = __len1 / `2`;
2401	std::advance(__first_cut, __len11);
2402	__second_cut
2403	= std::__lower_bound(__middle, __last, *__first_cut,
2404	__gnu_cxx::__ops::__iter_comp_val(__comp));
2405	__len22 = std::distance(__middle, __second_cut);
2406	}
2407	else
2408	{
2409	__len22 = __len2 / `2`;
2410	std::advance(__second_cut, __len22);
2411	__first_cut
2412	= std::__upper_bound(__first, __middle, *__second_cut,
2413	__gnu_cxx::__ops::__val_comp_iter(__comp));
2414	__len11 = std::distance(__first, __first_cut);
2415	}
2416
2417	_BidirectionalIterator __new_middle
2418	= std::__rotate_adaptive(__first_cut, __middle, __second_cut,
2419	_Distance(__len1 - __len11), __len22,
2420	__buffer, __buffer_size);
2421	std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2422	__len11, __len22,
2423	__buffer, __buffer_size, __comp);
2424	std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2425	_Distance(__len1 - __len11),
2426	_Distance(__len2 - __len22),
2427	__buffer, __buffer_size, __comp);
2428	}
2429	}
2430
2431	/// This is a helper function for the merge routines.
2432	template<typename _BidirectionalIterator, typename _Distance,
2433	typename _Compare>
2434	void
2435	__merge_without_buffer(_BidirectionalIterator __first,
2436	_BidirectionalIterator __middle,
2437	_BidirectionalIterator __last,
2438	_Distance __len1, _Distance __len2,
2439	_Compare __comp)
2440	{
2441	if (__len1 == `0` \|\| __len2 == `0`)
2442	return;
2443
2444	if (__len1 + __len2 == `2`)
2445	{
2446	if (__comp(__middle, __first))
2447	std::iter_swap(__first, __middle);
2448	return;
2449	}
2450
2451	_BidirectionalIterator __first_cut = __first;
2452	_BidirectionalIterator __second_cut = __middle;
2453	_Distance __len11 = `0`;
2454	_Distance __len22 = `0`;
2455	if (__len1 > __len2)
2456	{
2457	__len11 = __len1 / `2`;
2458	std::advance(__first_cut, __len11);
2459	__second_cut
2460	= std::__lower_bound(__middle, __last, *__first_cut,
2461	__gnu_cxx::__ops::__iter_comp_val(__comp));
2462	__len22 = std::distance(__middle, __second_cut);
2463	}
2464	else
2465	{
2466	__len22 = __len2 / `2`;
2467	std::advance(__second_cut, __len22);
2468	__first_cut
2469	= std::__upper_bound(__first, __middle, *__second_cut,
2470	__gnu_cxx::__ops::__val_comp_iter(__comp));
2471	__len11 = std::distance(__first, __first_cut);
2472	}
2473
2474	_BidirectionalIterator __new_middle
2475	= std::rotate(__first_cut, __middle, __second_cut);
2476	std::__merge_without_buffer(__first, __first_cut, __new_middle,
2477	__len11, __len22, __comp);
2478	std::__merge_without_buffer(__new_middle, __second_cut, __last,
2479	__len1 - __len11, __len2 - __len22, __comp);
2480	}
2481
2482	template<typename _BidirectionalIterator, typename _Compare>
2483	void
2484	__inplace_merge(_BidirectionalIterator __first,
2485	_BidirectionalIterator __middle,
2486	_BidirectionalIterator __last,
2487	_Compare __comp)
2488	{
2489	typedef typename iterator_traits<_BidirectionalIterator>::value_type
2490	_ValueType;
2491	typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2492	_DistanceType;
2493
2494	if (__first == __middle \|\| __middle == __last)
2495	return;
2496
2497	const _DistanceType __len1 = std::distance(__first, __middle);
2498	const _DistanceType __len2 = std::distance(__middle, __last);
2499
2500	#if _GLIBCXX_HOSTED
2501	typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2502	// __merge_adaptive will use a buffer for the smaller of
2503	// [first,middle) and [middle,last).
2504	_TmpBuf __buf(__first, std::min(__len1, __len2));
2505
2506	if (__builtin_expect(__buf.size() == __buf.requested_size(), true))
2507	std::__merge_adaptive
2508	(__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2509	else if (__builtin_expect(__buf.begin() == `0`, false))
2510	std::__merge_without_buffer
2511	(__first, __middle, __last, __len1, __len2, __comp);
2512	else
2513	std::__merge_adaptive_resize
2514	(__first, __middle, __last, __len1, __len2, __buf.begin(),
2515	_DistanceType(__buf.size()), __comp);
2516	#else
2517	std::__merge_without_buffer
2518	(__first, __middle, __last, __len1, __len2, __comp);
2519	#endif
2520	}
2521
2522	/**
2523	* @brief Merges two sorted ranges in place.
2524	* @ingroup sorting_algorithms
2525	* @param __first An iterator.
2526	* @param __middle Another iterator.
2527	* @param __last Another iterator.
2528	* @return Nothing.
2529	*
2530	* Merges two sorted and consecutive ranges, [__first,__middle) and
2531	* [__middle,__last), and puts the result in [__first,__last). The
2532	* output will be sorted. The sort is @e stable, that is, for
2533	* equivalent elements in the two ranges, elements from the first
2534	* range will always come before elements from the second.
2535	*
2536	* If enough additional memory is available, this takes (__last-__first)-1
2537	* comparisons. Otherwise an NlogN algorithm is used, where N is
2538	* distance(__first,__last).
2539	*/
2540	template<typename _BidirectionalIterator>
2541	inline void
2542	inplace_merge(_BidirectionalIterator __first,
2543	_BidirectionalIterator __middle,
2544	_BidirectionalIterator __last)
2545	{
2546	// concept requirements
2547	__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2548	_BidirectionalIterator>)
2549	__glibcxx_function_requires(_LessThanComparableConcept<
2550	typename iterator_traits<_BidirectionalIterator>::value_type>)
2551	__glibcxx_requires_sorted(__first, __middle);
2552	__glibcxx_requires_sorted(__middle, __last);
2553	__glibcxx_requires_irreflexive(__first, __last);
2554
2555	std::__inplace_merge(__first, __middle, __last,
2556	__gnu_cxx::__ops::__iter_less_iter());
2557	}
2558
2559	/**
2560	* @brief Merges two sorted ranges in place.
2561	* @ingroup sorting_algorithms
2562	* @param __first An iterator.
2563	* @param __middle Another iterator.
2564	* @param __last Another iterator.
2565	* @param __comp A functor to use for comparisons.
2566	* @return Nothing.
2567	*
2568	* Merges two sorted and consecutive ranges, [__first,__middle) and
2569	* [middle,last), and puts the result in [__first,__last). The output will
2570	* be sorted. The sort is @e stable, that is, for equivalent
2571	* elements in the two ranges, elements from the first range will always
2572	* come before elements from the second.
2573	*
2574	* If enough additional memory is available, this takes (__last-__first)-1
2575	* comparisons. Otherwise an NlogN algorithm is used, where N is
2576	* distance(__first,__last).
2577	*
2578	* The comparison function should have the same effects on ordering as
2579	* the function used for the initial sort.
2580	*/
2581	template<typename _BidirectionalIterator, typename _Compare>
2582	inline void
2583	inplace_merge(_BidirectionalIterator __first,
2584	_BidirectionalIterator __middle,
2585	_BidirectionalIterator __last,
2586	_Compare __comp)
2587	{
2588	// concept requirements
2589	__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2590	_BidirectionalIterator>)
2591	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2592	typename iterator_traits<_BidirectionalIterator>::value_type,
2593	typename iterator_traits<_BidirectionalIterator>::value_type>)
2594	__glibcxx_requires_sorted_pred(__first, __middle, __comp);
2595	__glibcxx_requires_sorted_pred(__middle, __last, __comp);
2596	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2597
2598	std::__inplace_merge(__first, __middle, __last,
2599	__gnu_cxx::__ops::__iter_comp_iter(__comp));
2600	}
2601
2602
2603	/// This is a helper function for the __merge_sort_loop routines.
2604	template<typename _InputIterator, typename _OutputIterator,
2605	typename _Compare>
2606	_OutputIterator
2607	__move_merge(_InputIterator __first1, _InputIterator __last1,
2608	_InputIterator __first2, _InputIterator __last2,
2609	_OutputIterator __result, _Compare __comp)
2610	{
2611	while (__first1 != __last1 && __first2 != __last2)
2612	{
2613	if (__comp(__first2, __first1))
2614	{
2615	__result = _GLIBCXX_MOVE(__first2);
2616	++__first2;
2617	}
2618	else
2619	{
2620	__result = _GLIBCXX_MOVE(__first1);
2621	++__first1;
2622	}
2623	++__result;
2624	}
2625	return _GLIBCXX_MOVE3(__first2, __last2,
2626	_GLIBCXX_MOVE3(__first1, __last1,
2627	__result));
2628	}
2629
2630	template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
2631	typename _Distance, typename _Compare>
2632	void
2633	__merge_sort_loop(_RandomAccessIterator1 __first,
2634	_RandomAccessIterator1 __last,
2635	_RandomAccessIterator2 __result, _Distance __step_size,
2636	_Compare __comp)
2637	{
2638	const _Distance __two_step = `2` * __step_size;
2639
2640	while (__last - __first >= __two_step)
2641	{
2642	__result = std::__move_merge(__first, __first + __step_size,
2643	__first + __step_size,
2644	__first + __two_step,
2645	__result, __comp);
2646	__first += __two_step;
2647	}
2648	__step_size = std::min(_Distance(__last - __first), __step_size);
2649
2650	std::__move_merge(__first, __first + __step_size,
2651	__first + __step_size, __last, __result, __comp);
2652	}
2653
2654	template<typename _RandomAccessIterator, typename _Distance,
2655	typename _Compare>
2656	_GLIBCXX20_CONSTEXPR
2657	void
2658	__chunk_insertion_sort(_RandomAccessIterator __first,
2659	_RandomAccessIterator __last,
2660	_Distance __chunk_size, _Compare __comp)
2661	{
2662	while (__last - __first >= __chunk_size)
2663	{
2664	std::__insertion_sort(__first, __first + __chunk_size, __comp);
2665	__first += __chunk_size;
2666	}
2667	std::__insertion_sort(__first, __last, __comp);
2668	}
2669
2670	enum { _S_chunk_size = `7` };
2671
2672	template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2673	void
2674	__merge_sort_with_buffer(_RandomAccessIterator __first,
2675	_RandomAccessIterator __last,
2676	_Pointer __buffer, _Compare __comp)
2677	{
2678	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2679	_Distance;
2680
2681	const _Distance __len = __last - __first;
2682	const _Pointer __buffer_last = __buffer + __len;
2683
2684	_Distance __step_size = _S_chunk_size;
2685	std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2686
2687	while (__step_size < __len)
2688	{
2689	std::__merge_sort_loop(__first, __last, __buffer,
2690	__step_size, __comp);
2691	__step_size *= `2`;
2692	std::__merge_sort_loop(__buffer, __buffer_last, __first,
2693	__step_size, __comp);
2694	__step_size *= `2`;
2695	}
2696	}
2697
2698	template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
2699	void
2700	__stable_sort_adaptive(_RandomAccessIterator __first,
2701	_RandomAccessIterator __middle,
2702	_RandomAccessIterator __last,
2703	_Pointer __buffer, _Compare __comp)
2704	{
2705	std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2706	std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2707
2708	std::__merge_adaptive(__first, __middle, __last,
2709	__middle - __first, __last - __middle,
2710	__buffer, __comp);
2711	}
2712
2713	template<typename _RandomAccessIterator, typename _Pointer,
2714	typename _Distance, typename _Compare>
2715	void
2716	__stable_sort_adaptive_resize(_RandomAccessIterator __first,
2717	_RandomAccessIterator __last,
2718	_Pointer __buffer, _Distance __buffer_size,
2719	_Compare __comp)
2720	{
2721	const _Distance __len = (__last - __first + `1`) / `2`;
2722	const _RandomAccessIterator __middle = __first + __len;
2723	if (__len > __buffer_size)
2724	{
2725	std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2726	__buffer_size, __comp);
2727	std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2728	__buffer_size, __comp);
2729	std::__merge_adaptive_resize(__first, __middle, __last,
2730	_Distance(__middle - __first),
2731	_Distance(__last - __middle),
2732	__buffer, __buffer_size,
2733	__comp);
2734	}
2735	else
2736	std::__stable_sort_adaptive(__first, __middle, __last,
2737	__buffer, __comp);
2738	}
2739
2740	/// This is a helper function for the stable sorting routines.
2741	template<typename _RandomAccessIterator, typename _Compare>
2742	void
2743	__inplace_stable_sort(_RandomAccessIterator __first,
2744	_RandomAccessIterator __last, _Compare __comp)
2745	{
2746	if (__last - __first < `15`)
2747	{
2748	std::__insertion_sort(__first, __last, __comp);
2749	return;
2750	}
2751	_RandomAccessIterator __middle = __first + (__last - __first) / `2`;
2752	std::__inplace_stable_sort(__first, __middle, __comp);
2753	std::__inplace_stable_sort(__middle, __last, __comp);
2754	std::__merge_without_buffer(__first, __middle, __last,
2755	__middle - __first,
2756	__last - __middle,
2757	__comp);
2758	}
2759
2760	// stable_sort
2761
2762	// Set algorithms: includes, set_union, set_intersection, set_difference,
2763	// set_symmetric_difference. All of these algorithms have the precondition
2764	// that their input ranges are sorted and the postcondition that their output
2765	// ranges are sorted.
2766
2767	template<typename _InputIterator1, typename _InputIterator2,
2768	typename _Compare>
2769	_GLIBCXX20_CONSTEXPR
2770	bool
2771	__includes(_InputIterator1 __first1, _InputIterator1 __last1,
2772	_InputIterator2 __first2, _InputIterator2 __last2,
2773	_Compare __comp)
2774	{
2775	while (__first1 != __last1 && __first2 != __last2)
2776	{
2777	if (__comp(__first2, __first1))
2778	return false;
2779	if (!__comp(__first1, __first2))
2780	++__first2;
2781	++__first1;
2782	}
2783
2784	return __first2 == __last2;
2785	}
2786
2787	/**
2788	* @brief Determines whether all elements of a sequence exists in a range.
2789	* @param __first1 Start of search range.
2790	* @param __last1 End of search range.
2791	* @param __first2 Start of sequence
2792	* @param __last2 End of sequence.
2793	* @return True if each element in [__first2,__last2) is contained in order
2794	* within [__first1,__last1). False otherwise.
2795	* @ingroup set_algorithms
2796	*
2797	* This operation expects both [__first1,__last1) and
2798	* [__first2,__last2) to be sorted. Searches for the presence of
2799	* each element in [__first2,__last2) within [__first1,__last1).
2800	* The iterators over each range only move forward, so this is a
2801	* linear algorithm. If an element in [__first2,__last2) is not
2802	* found before the search iterator reaches @p __last2, false is
2803	* returned.
2804	*/
2805	template<typename _InputIterator1, typename _InputIterator2>
2806	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2807	inline bool
2808	includes(_InputIterator1 __first1, _InputIterator1 __last1,
2809	_InputIterator2 __first2, _InputIterator2 __last2)
2810	{
2811	// concept requirements
2812	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2813	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2814	__glibcxx_function_requires(_LessThanOpConcept<
2815	typename iterator_traits<_InputIterator1>::value_type,
2816	typename iterator_traits<_InputIterator2>::value_type>)
2817	__glibcxx_function_requires(_LessThanOpConcept<
2818	typename iterator_traits<_InputIterator2>::value_type,
2819	typename iterator_traits<_InputIterator1>::value_type>)
2820	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
2821	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
2822	__glibcxx_requires_irreflexive2(__first1, __last1);
2823	__glibcxx_requires_irreflexive2(__first2, __last2);
2824
2825	return std::__includes(__first1, __last1, __first2, __last2,
2826	__gnu_cxx::__ops::__iter_less_iter());
2827	}
2828
2829	/**
2830	* @brief Determines whether all elements of a sequence exists in a range
2831	* using comparison.
2832	* @ingroup set_algorithms
2833	* @param __first1 Start of search range.
2834	* @param __last1 End of search range.
2835	* @param __first2 Start of sequence
2836	* @param __last2 End of sequence.
2837	* @param __comp Comparison function to use.
2838	* @return True if each element in [__first2,__last2) is contained
2839	* in order within [__first1,__last1) according to comp. False
2840	* otherwise. @ingroup set_algorithms
2841	*
2842	* This operation expects both [__first1,__last1) and
2843	* [__first2,__last2) to be sorted. Searches for the presence of
2844	* each element in [__first2,__last2) within [__first1,__last1),
2845	* using comp to decide. The iterators over each range only move
2846	* forward, so this is a linear algorithm. If an element in
2847	* [__first2,__last2) is not found before the search iterator
2848	* reaches @p __last2, false is returned.
2849	*/
2850	template<typename _InputIterator1, typename _InputIterator2,
2851	typename _Compare>
2852	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2853	inline bool
2854	includes(_InputIterator1 __first1, _InputIterator1 __last1,
2855	_InputIterator2 __first2, _InputIterator2 __last2,
2856	_Compare __comp)
2857	{
2858	// concept requirements
2859	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2860	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2861	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2862	typename iterator_traits<_InputIterator1>::value_type,
2863	typename iterator_traits<_InputIterator2>::value_type>)
2864	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2865	typename iterator_traits<_InputIterator2>::value_type,
2866	typename iterator_traits<_InputIterator1>::value_type>)
2867	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2868	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2869	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2870	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2871
2872	return std::__includes(__first1, __last1, __first2, __last2,
2873	__gnu_cxx::__ops::__iter_comp_iter(__comp));
2874	}
2875
2876	// nth_element
2877	// merge
2878	// set_difference
2879	// set_intersection
2880	// set_union
2881	// stable_sort
2882	// set_symmetric_difference
2883	// min_element
2884	// max_element
2885
2886	template<typename _BidirectionalIterator, typename _Compare>
2887	_GLIBCXX20_CONSTEXPR
2888	bool
2889	__next_permutation(_BidirectionalIterator __first,
2890	_BidirectionalIterator __last, _Compare __comp)
2891	{
2892	if (__first == __last)
2893	return false;
2894	_BidirectionalIterator __i = __first;
2895	++__i;
2896	if (__i == __last)
2897	return false;
2898	__i = __last;
2899	--__i;
2900
2901	for(;;)
2902	{
2903	_BidirectionalIterator __ii = __i;
2904	--__i;
2905	if (__comp(__i, __ii))
2906	{
2907	_BidirectionalIterator __j = __last;
2908	while (!__comp(__i, --__j))
2909	{}
2910	std::iter_swap(__i, __j);
2911	std::__reverse(__ii, __last,
2912	std::__iterator_category(__first));
2913	return true;
2914	}
2915	if (__i == __first)
2916	{
2917	std::__reverse(__first, __last,
2918	std::__iterator_category(__first));
2919	return false;
2920	}
2921	}
2922	}
2923
2924	/**
2925	* @brief Permute range into the next @e dictionary ordering.
2926	* @ingroup sorting_algorithms
2927	* @param __first Start of range.
2928	* @param __last End of range.
2929	* @return False if wrapped to first permutation, true otherwise.
2930	*
2931	* Treats all permutations of the range as a set of @e dictionary sorted
2932	* sequences. Permutes the current sequence into the next one of this set.
2933	* Returns true if there are more sequences to generate. If the sequence
2934	* is the largest of the set, the smallest is generated and false returned.
2935	*/
2936	template<typename _BidirectionalIterator>
2937	_GLIBCXX20_CONSTEXPR
2938	inline bool
2939	next_permutation(_BidirectionalIterator __first,
2940	_BidirectionalIterator __last)
2941	{
2942	// concept requirements
2943	__glibcxx_function_requires(_BidirectionalIteratorConcept<
2944	_BidirectionalIterator>)
2945	__glibcxx_function_requires(_LessThanComparableConcept<
2946	typename iterator_traits<_BidirectionalIterator>::value_type>)
2947	__glibcxx_requires_valid_range(__first, __last);
2948	__glibcxx_requires_irreflexive(__first, __last);
2949
2950	return std::__next_permutation
2951	(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2952	}
2953
2954	/**
2955	* @brief Permute range into the next @e dictionary ordering using
2956	* comparison functor.
2957	* @ingroup sorting_algorithms
2958	* @param __first Start of range.
2959	* @param __last End of range.
2960	* @param __comp A comparison functor.
2961	* @return False if wrapped to first permutation, true otherwise.
2962	*
2963	* Treats all permutations of the range [__first,__last) as a set of
2964	* @e dictionary sorted sequences ordered by @p __comp. Permutes the current
2965	* sequence into the next one of this set. Returns true if there are more
2966	* sequences to generate. If the sequence is the largest of the set, the
2967	* smallest is generated and false returned.
2968	*/
2969	template<typename _BidirectionalIterator, typename _Compare>
2970	_GLIBCXX20_CONSTEXPR
2971	inline bool
2972	next_permutation(_BidirectionalIterator __first,
2973	_BidirectionalIterator __last, _Compare __comp)
2974	{
2975	// concept requirements
2976	__glibcxx_function_requires(_BidirectionalIteratorConcept<
2977	_BidirectionalIterator>)
2978	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2979	typename iterator_traits<_BidirectionalIterator>::value_type,
2980	typename iterator_traits<_BidirectionalIterator>::value_type>)
2981	__glibcxx_requires_valid_range(__first, __last);
2982	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2983
2984	return std::__next_permutation
2985	(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2986	}
2987
2988	template<typename _BidirectionalIterator, typename _Compare>
2989	_GLIBCXX20_CONSTEXPR
2990	bool
2991	__prev_permutation(_BidirectionalIterator __first,
2992	_BidirectionalIterator __last, _Compare __comp)
2993	{
2994	if (__first == __last)
2995	return false;
2996	_BidirectionalIterator __i = __first;
2997	++__i;
2998	if (__i == __last)
2999	return false;
3000	__i = __last;
3001	--__i;
3002
3003	for(;;)
3004	{
3005	_BidirectionalIterator __ii = __i;
3006	--__i;
3007	if (__comp(__ii, __i))
3008	{
3009	_BidirectionalIterator __j = __last;
3010	while (!__comp(--__j, __i))
3011	{}
3012	std::iter_swap(__i, __j);
3013	std::__reverse(__ii, __last,
3014	std::__iterator_category(__first));
3015	return true;
3016	}
3017	if (__i == __first)
3018	{
3019	std::__reverse(__first, __last,
3020	std::__iterator_category(__first));
3021	return false;
3022	}
3023	}
3024	}
3025
3026	/**
3027	* @brief Permute range into the previous @e dictionary ordering.
3028	* @ingroup sorting_algorithms
3029	* @param __first Start of range.
3030	* @param __last End of range.
3031	* @return False if wrapped to last permutation, true otherwise.
3032	*
3033	* Treats all permutations of the range as a set of @e dictionary sorted
3034	* sequences. Permutes the current sequence into the previous one of this
3035	* set. Returns true if there are more sequences to generate. If the
3036	* sequence is the smallest of the set, the largest is generated and false
3037	* returned.
3038	*/
3039	template<typename _BidirectionalIterator>
3040	_GLIBCXX20_CONSTEXPR
3041	inline bool
3042	prev_permutation(_BidirectionalIterator __first,
3043	_BidirectionalIterator __last)
3044	{
3045	// concept requirements
3046	__glibcxx_function_requires(_BidirectionalIteratorConcept<
3047	_BidirectionalIterator>)
3048	__glibcxx_function_requires(_LessThanComparableConcept<
3049	typename iterator_traits<_BidirectionalIterator>::value_type>)
3050	__glibcxx_requires_valid_range(__first, __last);
3051	__glibcxx_requires_irreflexive(__first, __last);
3052
3053	return std::__prev_permutation(__first, __last,
3054	__gnu_cxx::__ops::__iter_less_iter());
3055	}
3056
3057	/**
3058	* @brief Permute range into the previous @e dictionary ordering using
3059	* comparison functor.
3060	* @ingroup sorting_algorithms
3061	* @param __first Start of range.
3062	* @param __last End of range.
3063	* @param __comp A comparison functor.
3064	* @return False if wrapped to last permutation, true otherwise.
3065	*
3066	* Treats all permutations of the range [__first,__last) as a set of
3067	* @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3068	* sequence into the previous one of this set. Returns true if there are
3069	* more sequences to generate. If the sequence is the smallest of the set,
3070	* the largest is generated and false returned.
3071	*/
3072	template<typename _BidirectionalIterator, typename _Compare>
3073	_GLIBCXX20_CONSTEXPR
3074	inline bool
3075	prev_permutation(_BidirectionalIterator __first,
3076	_BidirectionalIterator __last, _Compare __comp)
3077	{
3078	// concept requirements
3079	__glibcxx_function_requires(_BidirectionalIteratorConcept<
3080	_BidirectionalIterator>)
3081	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3082	typename iterator_traits<_BidirectionalIterator>::value_type,
3083	typename iterator_traits<_BidirectionalIterator>::value_type>)
3084	__glibcxx_requires_valid_range(__first, __last);
3085	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3086
3087	return std::__prev_permutation(__first, __last,
3088	__gnu_cxx::__ops::__iter_comp_iter(__comp));
3089	}
3090
3091	// replace
3092	// replace_if
3093
3094	template<typename _InputIterator, typename _OutputIterator,
3095	typename _Predicate, typename _Tp>
3096	_GLIBCXX20_CONSTEXPR
3097	_OutputIterator
3098	__replace_copy_if(_InputIterator __first, _InputIterator __last,
3099	_OutputIterator __result,
3100	_Predicate __pred, const _Tp& __new_value)
3101	{
3102	for (; __first != __last; ++__first, (void)++__result)
3103	if (__pred(__first))
3104	*__result = __new_value;
3105	else
3106	__result = __first;
3107	return __result;
3108	}
3109
3110	/**
3111	* @brief Copy a sequence, replacing each element of one value with another
3112	* value.
3113	* @param __first An input iterator.
3114	* @param __last An input iterator.
3115	* @param __result An output iterator.
3116	* @param __old_value The value to be replaced.
3117	* @param __new_value The replacement value.
3118	* @return The end of the output sequence, @p result+(last-first).
3119	*
3120	* Copies each element in the input range @p [__first,__last) to the
3121	* output range @p [__result,__result+(__last-__first)) replacing elements
3122	* equal to @p __old_value with @p __new_value.
3123	*/
3124	template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3125	_GLIBCXX20_CONSTEXPR
3126	inline _OutputIterator
3127	replace_copy(_InputIterator __first, _InputIterator __last,
3128	_OutputIterator __result,
3129	const _Tp& __old_value, const _Tp& __new_value)
3130	{
3131	// concept requirements
3132	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3133	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3134	typename iterator_traits<_InputIterator>::value_type>)
3135	__glibcxx_function_requires(_EqualOpConcept<
3136	typename iterator_traits<_InputIterator>::value_type, _Tp>)
3137	__glibcxx_requires_valid_range(__first, __last);
3138
3139	return std::__replace_copy_if(__first, __last, __result,
3140	__gnu_cxx::__ops::__iter_equals_val(__old_value),
3141	__new_value);
3142	}
3143
3144	/**
3145	* @brief Copy a sequence, replacing each value for which a predicate
3146	* returns true with another value.
3147	* @ingroup mutating_algorithms
3148	* @param __first An input iterator.
3149	* @param __last An input iterator.
3150	* @param __result An output iterator.
3151	* @param __pred A predicate.
3152	* @param __new_value The replacement value.
3153	* @return The end of the output sequence, @p __result+(__last-__first).
3154	*
3155	* Copies each element in the range @p [__first,__last) to the range
3156	* @p [__result,__result+(__last-__first)) replacing elements for which
3157	* @p __pred returns true with @p __new_value.
3158	*/
3159	template<typename _InputIterator, typename _OutputIterator,
3160	typename _Predicate, typename _Tp>
3161	_GLIBCXX20_CONSTEXPR
3162	inline _OutputIterator
3163	replace_copy_if(_InputIterator __first, _InputIterator __last,
3164	_OutputIterator __result,
3165	_Predicate __pred, const _Tp& __new_value)
3166	{
3167	// concept requirements
3168	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3169	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3170	typename iterator_traits<_InputIterator>::value_type>)
3171	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3172	typename iterator_traits<_InputIterator>::value_type>)
3173	__glibcxx_requires_valid_range(__first, __last);
3174
3175	return std::__replace_copy_if(__first, __last, __result,
3176	__gnu_cxx::__ops::__pred_iter(__pred),
3177	__new_value);
3178	}
3179
3180	#if __cplusplus >= 201103L
3181	/**
3182	* @brief Determines whether the elements of a sequence are sorted.
3183	* @ingroup sorting_algorithms
3184	* @param __first An iterator.
3185	* @param __last Another iterator.
3186	* @return True if the elements are sorted, false otherwise.
3187	*/
3188	template<typename _ForwardIterator>
3189	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3190	inline bool
3191	is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3192	{ return std::is_sorted_until(__first, __last) == __last; }
3193
3194	/**
3195	* @brief Determines whether the elements of a sequence are sorted
3196	* according to a comparison functor.
3197	* @ingroup sorting_algorithms
3198	* @param __first An iterator.
3199	* @param __last Another iterator.
3200	* @param __comp A comparison functor.
3201	* @return True if the elements are sorted, false otherwise.
3202	*/
3203	template<typename _ForwardIterator, typename _Compare>
3204	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3205	inline bool
3206	is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3207	_Compare __comp)
3208	{ return std::is_sorted_until(__first, __last, __comp) == __last; }
3209
3210	template<typename _ForwardIterator, typename _Compare>
3211	_GLIBCXX20_CONSTEXPR
3212	_ForwardIterator
3213	__is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3214	_Compare __comp)
3215	{
3216	if (__first == __last)
3217	return __last;
3218
3219	_ForwardIterator __next = __first;
3220	for (++__next; __next != __last; __first = __next, (void)++__next)
3221	if (__comp(__next, __first))
3222	return __next;
3223	return __next;
3224	}
3225
3226	/**
3227	* @brief Determines the end of a sorted sequence.
3228	* @ingroup sorting_algorithms
3229	* @param __first An iterator.
3230	* @param __last Another iterator.
3231	* @return An iterator pointing to the last iterator i in [__first, __last)
3232	* for which the range [__first, i) is sorted.
3233	*/
3234	template<typename _ForwardIterator>
3235	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3236	inline _ForwardIterator
3237	is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3238	{
3239	// concept requirements
3240	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3241	__glibcxx_function_requires(_LessThanComparableConcept<
3242	typename iterator_traits<_ForwardIterator>::value_type>)
3243	__glibcxx_requires_valid_range(__first, __last);
3244	__glibcxx_requires_irreflexive(__first, __last);
3245
3246	return std::__is_sorted_until(__first, __last,
3247	__gnu_cxx::__ops::__iter_less_iter());
3248	}
3249
3250	/**
3251	* @brief Determines the end of a sorted sequence using comparison functor.
3252	* @ingroup sorting_algorithms
3253	* @param __first An iterator.
3254	* @param __last Another iterator.
3255	* @param __comp A comparison functor.
3256	* @return An iterator pointing to the last iterator i in [__first, __last)
3257	* for which the range [__first, i) is sorted.
3258	*/
3259	template<typename _ForwardIterator, typename _Compare>
3260	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3261	inline _ForwardIterator
3262	is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3263	_Compare __comp)
3264	{
3265	// concept requirements
3266	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3267	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3268	typename iterator_traits<_ForwardIterator>::value_type,
3269	typename iterator_traits<_ForwardIterator>::value_type>)
3270	__glibcxx_requires_valid_range(__first, __last);
3271	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3272
3273	return std::__is_sorted_until(__first, __last,
3274	__gnu_cxx::__ops::__iter_comp_iter(__comp));
3275	}
3276
3277	/**
3278	* @brief Determines min and max at once as an ordered pair.
3279	* @ingroup sorting_algorithms
3280	* @param __a A thing of arbitrary type.
3281	* @param __b Another thing of arbitrary type.
3282	* @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3283	* __b) otherwise.
3284	*/
3285	template<typename _Tp>
3286	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3287	inline pair<const _Tp&, const _Tp&>
3288	minmax(const _Tp& __a, const _Tp& __b)
3289	{
3290	// concept requirements
3291	__glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3292
3293	return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3294	: pair<const _Tp&, const _Tp&>(__a, __b);
3295	}
3296
3297	/**
3298	* @brief Determines min and max at once as an ordered pair.
3299	* @ingroup sorting_algorithms
3300	* @param __a A thing of arbitrary type.
3301	* @param __b Another thing of arbitrary type.
3302	* @param __comp A @link comparison_functors comparison functor @endlink.
3303	* @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
3304	* __b) otherwise.
3305	*/
3306	template<typename _Tp, typename _Compare>
3307	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3308	inline pair<const _Tp&, const _Tp&>
3309	minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
3310	{
3311	return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
3312	: pair<const _Tp&, const _Tp&>(__a, __b);
3313	}
3314
3315	template<typename _ForwardIterator, typename _Compare>
3316	_GLIBCXX14_CONSTEXPR
3317	pair<_ForwardIterator, _ForwardIterator>
3318	__minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3319	_Compare __comp)
3320	{
3321	_ForwardIterator __next = __first;
3322	if (__first == __last
3323	\|\| ++__next == __last)
3324	return std::make_pair(__first, __first);
3325
3326	_ForwardIterator __min{}, __max{};
3327	if (__comp(__next, __first))
3328	{
3329	__min = __next;
3330	__max = __first;
3331	}
3332	else
3333	{
3334	__min = __first;
3335	__max = __next;
3336	}
3337
3338	__first = __next;
3339	++__first;
3340
3341	while (__first != __last)
3342	{
3343	__next = __first;
3344	if (++__next == __last)
3345	{
3346	if (__comp(__first, __min))
3347	__min = __first;
3348	else if (!__comp(__first, __max))
3349	__max = __first;
3350	break;
3351	}
3352
3353	if (__comp(__next, __first))
3354	{
3355	if (__comp(__next, __min))
3356	__min = __next;
3357	if (!__comp(__first, __max))
3358	__max = __first;
3359	}
3360	else
3361	{
3362	if (__comp(__first, __min))
3363	__min = __first;
3364	if (!__comp(__next, __max))
3365	__max = __next;
3366	}
3367
3368	__first = __next;
3369	++__first;
3370	}
3371
3372	return std::make_pair(__min, __max);
3373	}
3374
3375	/**
3376	* @brief Return a pair of iterators pointing to the minimum and maximum
3377	* elements in a range.
3378	* @ingroup sorting_algorithms
3379	* @param __first Start of range.
3380	* @param __last End of range.
3381	* @return make_pair(m, M), where m is the first iterator i in
3382	* [__first, __last) such that no other element in the range is
3383	* smaller, and where M is the last iterator i in [__first, __last)
3384	* such that no other element in the range is larger.
3385	*/
3386	template<typename _ForwardIterator>
3387	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3388	inline pair<_ForwardIterator, _ForwardIterator>
3389	minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3390	{
3391	// concept requirements
3392	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3393	__glibcxx_function_requires(_LessThanComparableConcept<
3394	typename iterator_traits<_ForwardIterator>::value_type>)
3395	__glibcxx_requires_valid_range(__first, __last);
3396	__glibcxx_requires_irreflexive(__first, __last);
3397
3398	return std::__minmax_element(__first, __last,
3399	__gnu_cxx::__ops::__iter_less_iter());
3400	}
3401
3402	/**
3403	* @brief Return a pair of iterators pointing to the minimum and maximum
3404	* elements in a range.
3405	* @ingroup sorting_algorithms
3406	* @param __first Start of range.
3407	* @param __last End of range.
3408	* @param __comp Comparison functor.
3409	* @return make_pair(m, M), where m is the first iterator i in
3410	* [__first, __last) such that no other element in the range is
3411	* smaller, and where M is the last iterator i in [__first, __last)
3412	* such that no other element in the range is larger.
3413	*/
3414	template<typename _ForwardIterator, typename _Compare>
3415	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3416	inline pair<_ForwardIterator, _ForwardIterator>
3417	minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3418	_Compare __comp)
3419	{
3420	// concept requirements
3421	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3422	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3423	typename iterator_traits<_ForwardIterator>::value_type,
3424	typename iterator_traits<_ForwardIterator>::value_type>)
3425	__glibcxx_requires_valid_range(__first, __last);
3426	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3427
3428	return std::__minmax_element(__first, __last,
3429	__gnu_cxx::__ops::__iter_comp_iter(__comp));
3430	}
3431
3432	template<typename _Tp>
3433	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3434	inline pair<_Tp, _Tp>
3435	minmax(initializer_list<_Tp> __l)
3436	{
3437	__glibcxx_requires_irreflexive(__l.begin(), __l.end());
3438	pair<const _Tp, const* _Tp*> __p =
3439	std::__minmax_element(__l.begin(), __l.end(),
3440	__gnu_cxx::__ops::__iter_less_iter());
3441	return std::make_pair(__p.first, __p.second);
3442	}
3443
3444	template<typename _Tp, typename _Compare>
3445	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
3446	inline pair<_Tp, _Tp>
3447	minmax(initializer_list<_Tp> __l, _Compare __comp)
3448	{
3449	__glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3450	pair<const _Tp, const* _Tp*> __p =
3451	std::__minmax_element(__l.begin(), __l.end(),
3452	__gnu_cxx::__ops::__iter_comp_iter(__comp));
3453	return std::make_pair(__p.first, __p.second);
3454	}
3455
3456	/**
3457	* @brief Checks whether a permutation of the second sequence is equal
3458	* to the first sequence.
3459	* @ingroup non_mutating_algorithms
3460	* @param __first1 Start of first range.
3461	* @param __last1 End of first range.
3462	* @param __first2 Start of second range.
3463	* @param __pred A binary predicate.
3464	* @return true if there exists a permutation of the elements in
3465	* the range [__first2, __first2 + (__last1 - __first1)),
3466	* beginning with ForwardIterator2 begin, such that
3467	* equal(__first1, __last1, __begin, __pred) returns true;
3468	* otherwise, returns false.
3469	*/
3470	template<typename _ForwardIterator1, typename _ForwardIterator2,
3471	typename _BinaryPredicate>
3472	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3473	inline bool
3474	is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3475	_ForwardIterator2 __first2, _BinaryPredicate __pred)
3476	{
3477	// concept requirements
3478	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3479	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3480	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3481	typename iterator_traits<_ForwardIterator1>::value_type,
3482	typename iterator_traits<_ForwardIterator2>::value_type>)
3483	__glibcxx_requires_valid_range(__first1, __last1);
3484
3485	return std::__is_permutation(__first1, __last1, __first2,
3486	__gnu_cxx::__ops::__iter_comp_iter(__pred));
3487	}
3488
3489	#if __cplusplus > 201103L
3490	#pragma GCC diagnostic push
3491	#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
3492	template<typename _ForwardIterator1, typename _ForwardIterator2,
3493	typename _BinaryPredicate>
3494	_GLIBCXX20_CONSTEXPR
3495	bool
3496	__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3497	_ForwardIterator2 __first2, _ForwardIterator2 __last2,
3498	_BinaryPredicate __pred)
3499	{
3500	using _Cat1
3501	= typename iterator_traits<_ForwardIterator1>::iterator_category;
3502	using _Cat2
3503	= typename iterator_traits<_ForwardIterator2>::iterator_category;
3504	using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3505	using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3506	constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value;
3507	if constexpr (__ra_iters)
3508	{
3509	if ((__last1 - __first1) != (__last2 - __first2))
3510	return false;
3511	}
3512
3513	// Efficiently compare identical prefixes: O(N) if sequences
3514	// have the same elements in the same order.
3515	for (; __first1 != __last1 && __first2 != __last2;
3516	++__first1, (void)++__first2)
3517	if (!__pred(__first1, __first2))
3518	break;
3519
3520	if constexpr (__ra_iters)
3521	{
3522	if (__first1 == __last1)
3523	return true;
3524	}
3525	else
3526	{
3527	auto __d1 = std::distance(__first1, __last1);
3528	auto __d2 = std::distance(__first2, __last2);
3529	if (__d1 == `0` && __d2 == `0`)
3530	return true;
3531	if (__d1 != __d2)
3532	return false;
3533	}
3534
3535	for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3536	{
3537	if (__scan != std::__find_if(__first1, __scan,
3538	__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3539	continue; // We've seen this one before.
3540
3541	auto __matches = std::__count_if(__first2, __last2,
3542	__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3543	if (`0` == __matches
3544	\|\| std::__count_if(__scan, __last1,
3545	__gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3546	!= __matches)
3547	return false;
3548	}
3549	return true;
3550	}
3551	#pragma GCC diagnostic pop
3552
3553	/**
3554	* @brief Checks whether a permutaion of the second sequence is equal
3555	* to the first sequence.
3556	* @ingroup non_mutating_algorithms
3557	* @param __first1 Start of first range.
3558	* @param __last1 End of first range.
3559	* @param __first2 Start of second range.
3560	* @param __last2 End of first range.
3561	* @return true if there exists a permutation of the elements in the range
3562	* [__first2, __last2), beginning with ForwardIterator2 begin,
3563	* such that equal(__first1, __last1, begin) returns true;
3564	* otherwise, returns false.
3565	*/
3566	template<typename _ForwardIterator1, typename _ForwardIterator2>
3567	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3568	inline bool
3569	is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3570	_ForwardIterator2 __first2, _ForwardIterator2 __last2)
3571	{
3572	__glibcxx_requires_valid_range(__first1, __last1);
3573	__glibcxx_requires_valid_range(__first2, __last2);
3574
3575	return
3576	std::__is_permutation(__first1, __last1, __first2, __last2,
3577	__gnu_cxx::__ops::__iter_equal_to_iter());
3578	}
3579
3580	/**
3581	* @brief Checks whether a permutation of the second sequence is equal
3582	* to the first sequence.
3583	* @ingroup non_mutating_algorithms
3584	* @param __first1 Start of first range.
3585	* @param __last1 End of first range.
3586	* @param __first2 Start of second range.
3587	* @param __last2 End of first range.
3588	* @param __pred A binary predicate.
3589	* @return true if there exists a permutation of the elements in the range
3590	* [__first2, __last2), beginning with ForwardIterator2 begin,
3591	* such that equal(__first1, __last1, __begin, __pred) returns true;
3592	* otherwise, returns false.
3593	*/
3594	template<typename _ForwardIterator1, typename _ForwardIterator2,
3595	typename _BinaryPredicate>
3596	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3597	inline bool
3598	is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3599	_ForwardIterator2 __first2, _ForwardIterator2 __last2,
3600	_BinaryPredicate __pred)
3601	{
3602	__glibcxx_requires_valid_range(__first1, __last1);
3603	__glibcxx_requires_valid_range(__first2, __last2);
3604
3605	return std::__is_permutation(__first1, __last1, __first2, __last2,
3606	__gnu_cxx::__ops::__iter_comp_iter(__pred));
3607	}
3608	#endif // C++14
3609
3610	#ifdef __glibcxx_clamp // C++ >= 17
3611	/**
3612	* @brief Returns the value clamped between lo and hi.
3613	* @ingroup sorting_algorithms
3614	* @param __val A value of arbitrary type.
3615	* @param __lo A lower limit of arbitrary type.
3616	* @param __hi An upper limit of arbitrary type.
3617	* @retval `__lo` if `__val < __lo`
3618	* @retval `__hi` if `__hi < __val`
3619	* @retval `__val` otherwise.
3620	* @pre `_Tp` is LessThanComparable and `(__hi < __lo)` is false.
3621	*/
3622	template<typename _Tp>
3623	[[nodiscard]] constexpr const _Tp&
3624	clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
3625	{
3626	__glibcxx_assert(!(__hi < __lo));
3627	return std::min(std::max(__val, __lo), __hi);
3628	}
3629
3630	/**
3631	* @brief Returns the value clamped between lo and hi.
3632	* @ingroup sorting_algorithms
3633	* @param __val A value of arbitrary type.
3634	* @param __lo A lower limit of arbitrary type.
3635	* @param __hi An upper limit of arbitrary type.
3636	* @param __comp A comparison functor.
3637	* @retval `__lo` if `__comp(__val, __lo)`
3638	* @retval `__hi` if `__comp(__hi, __val)`
3639	* @retval `__val` otherwise.
3640	* @pre `__comp(__hi, __lo)` is false.
3641	*/
3642	template<typename _Tp, typename _Compare>
3643	[[nodiscard]] constexpr const _Tp&
3644	clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
3645	{
3646	__glibcxx_assert(!__comp(__hi, __lo));
3647	return std::min(std::max(__val, __lo, __comp), __hi, __comp);
3648	}
3649	#endif // __glibcxx_clamp
3650
3651	/**
3652	* @brief Generate two uniformly distributed integers using a
3653	* single distribution invocation.
3654	* @param __b0 The upper bound for the first integer.
3655	* @param __b1 The upper bound for the second integer.
3656	* @param __g A UniformRandomBitGenerator.
3657	* @return A pair (i, j) with i and j uniformly distributed
3658	* over [0, __b0) and [0, __b1), respectively.
3659	*
3660	* Requires: __b0 * __b1 <= __g.max() - __g.min().
3661	*
3662	* Using uniform_int_distribution with a range that is very
3663	* small relative to the range of the generator ends up wasting
3664	* potentially expensively generated randomness, since
3665	* uniform_int_distribution does not store leftover randomness
3666	* between invocations.
3667	*
3668	* If we know we want two integers in ranges that are sufficiently
3669	* small, we can compose the ranges, use a single distribution
3670	* invocation, and significantly reduce the waste.
3671	*/
3672	template<typename _IntType, typename _UniformRandomBitGenerator>
3673	pair<_IntType, _IntType>
3674	__gen_two_uniform_ints(_IntType __b0, _IntType __b1,
3675	_UniformRandomBitGenerator&& __g)
3676	{
3677	_IntType __x
3678	= uniform_int_distribution<_IntType>{`0`, (__b0 * __b1) - `1`}(__g);
3679	return std::make_pair(__x / __b1, __x % __b1);
3680	}
3681
3682	/**
3683	* @brief Shuffle the elements of a sequence using a uniform random
3684	* number generator.
3685	* @ingroup mutating_algorithms
3686	* @param __first A forward iterator.
3687	* @param __last A forward iterator.
3688	* @param __g A UniformRandomNumberGenerator (26.5.1.3).
3689	* @return Nothing.
3690	*
3691	* Reorders the elements in the range @p [__first,__last) using @p __g to
3692	* provide random numbers.
3693	*/
3694	template<typename _RandomAccessIterator,
3695	typename _UniformRandomNumberGenerator>
3696	void
3697	shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3698	_UniformRandomNumberGenerator&& __g)
3699	{
3700	// concept requirements
3701	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3702	_RandomAccessIterator>)
3703	__glibcxx_requires_valid_range(__first, __last);
3704
3705	if (__first == __last)
3706	return;
3707
3708	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3709	_DistanceType;
3710
3711	typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3712	typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
3713	typedef typename __distr_type::param_type __p_type;
3714
3715	typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3716	_Gen;
3717	typedef typename common_type<typename _Gen::result_type, __ud_type>::type
3718	__uc_type;
3719
3720	const __uc_type __urngrange = __g.max() - __g.min();
3721	const __uc_type __urange = __uc_type(__last - __first);
3722
3723	if (__urngrange / __urange >= __urange)
3724	// I.e. (__urngrange >= __urange __urange) but without wrap issues.*
3725	{
3726	_RandomAccessIterator __i = __first + `1`;
3727
3728	// Since we know the range isn't empty, an even number of elements
3729	// means an uneven number of elements /to swap/, in which case we
3730	// do the first one up front:
3731
3732	if ((__urange % `2`) == `0`)
3733	{
3734	__distr_type __d{`0`, `1`};
3735	std::iter_swap(__i++, __first + __d(__g));
3736	}
3737
3738	// Now we know that __last - __i is even, so we do the rest in pairs,
3739	// using a single distribution invocation to produce swap positions
3740	// for two successive elements at a time:
3741
3742	while (__i != __last)
3743	{
3744	const __uc_type __swap_range = __uc_type(__i - __first) + `1`;
3745
3746	const pair<__uc_type, __uc_type> __pospos =
3747	__gen_two_uniform_ints(__swap_range, __swap_range + `1`, __g);
3748
3749	std::iter_swap(__i++, __first + __pospos.first);
3750	std::iter_swap(__i++, __first + __pospos.second);
3751	}
3752
3753	return;
3754	}
3755
3756	__distr_type __d;
3757
3758	for (_RandomAccessIterator __i = __first + `1`; __i != __last; ++__i)
3759	std::iter_swap(__i, __first + __d(__g, __p_type(`0`, __i - __first)));
3760	}
3761	#endif // C++11
3762
3763	_GLIBCXX_BEGIN_NAMESPACE_ALGO
3764
3765	/**
3766	* @brief Apply a function to every element of a sequence.
3767	* @ingroup non_mutating_algorithms
3768	* @param __first An input iterator.
3769	* @param __last An input iterator.
3770	* @param __f A unary function object.
3771	* @return @p __f
3772	*
3773	* Applies the function object @p __f to each element in the range
3774	* @p [first,last). @p __f must not modify the order of the sequence.
3775	* If @p __f has a return value it is ignored.
3776	*/
3777	template<typename _InputIterator, typename _Function>
3778	_GLIBCXX20_CONSTEXPR
3779	_Function
3780	for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3781	{
3782	// concept requirements
3783	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3784	__glibcxx_requires_valid_range(__first, __last);
3785	for (; __first != __last; ++__first)
3786	__f(*__first);
3787	return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3788	}
3789
3790	#if __cplusplus >= 201703L
3791	/**
3792	* @brief Apply a function to every element of a sequence.
3793	* @ingroup non_mutating_algorithms
3794	* @param __first An input iterator.
3795	* @param __n A value convertible to an integer.
3796	* @param __f A unary function object.
3797	* @return `__first+__n`
3798	*
3799	* Applies the function object `__f` to each element in the range
3800	* `[first, first+n)`. `__f` must not modify the order of the sequence.
3801	* If `__f` has a return value it is ignored.
3802	*/
3803	template<typename _InputIterator, typename _Size, typename _Function>
3804	_GLIBCXX20_CONSTEXPR
3805	_InputIterator
3806	for_each_n(_InputIterator __first, _Size __n, _Function __f)
3807	{
3808	auto __n2 = std::__size_to_integer(__n);
3809	using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
3810	if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3811	{
3812	if (__n2 <= `0`)
3813	return __first;
3814	auto __last = __first + __n2;
3815	std::for_each(__first, __last, std::move(__f));
3816	return __last;
3817	}
3818	else
3819	{
3820	while (__n2-->`0`)
3821	{
3822	__f(*__first);
3823	++__first;
3824	}
3825	return __first;
3826	}
3827	}
3828	#endif // C++17
3829
3830	/**
3831	* @brief Find the first occurrence of a value in a sequence.
3832	* @ingroup non_mutating_algorithms
3833	* @param __first An input iterator.
3834	* @param __last An input iterator.
3835	* @param __val The value to find.
3836	* @return The first iterator @c i in the range @p [__first,__last)
3837	* such that @c *i == @p __val, or @p __last if no such iterator exists.
3838	*/
3839	template<typename _InputIterator, typename _Tp>
3840	_GLIBCXX20_CONSTEXPR
3841	inline _InputIterator
3842	find(_InputIterator __first, _InputIterator __last,
3843	const _Tp& __val)
3844	{
3845	// concept requirements
3846	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3847	__glibcxx_function_requires(_EqualOpConcept<
3848	typename iterator_traits<_InputIterator>::value_type, _Tp>)
3849	__glibcxx_requires_valid_range(__first, __last);
3850	return std::__find_if(__first, __last,
3851	__gnu_cxx::__ops::__iter_equals_val(__val));
3852	}
3853
3854	/**
3855	* @brief Find the first element in a sequence for which a
3856	* predicate is true.
3857	* @ingroup non_mutating_algorithms
3858	* @param __first An input iterator.
3859	* @param __last An input iterator.
3860	* @param __pred A predicate.
3861	* @return The first iterator @c i in the range @p [__first,__last)
3862	* such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3863	*/
3864	template<typename _InputIterator, typename _Predicate>
3865	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3866	inline _InputIterator
3867	find_if(_InputIterator __first, _InputIterator __last,
3868	_Predicate __pred)
3869	{
3870	// concept requirements
3871	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3872	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3873	typename iterator_traits<_InputIterator>::value_type>)
3874	__glibcxx_requires_valid_range(__first, __last);
3875
3876	return std::__find_if(__first, __last,
3877	__gnu_cxx::__ops::__pred_iter(__pred));
3878	}
3879
3880	/**
3881	* @brief Find element from a set in a sequence.
3882	* @ingroup non_mutating_algorithms
3883	* @param __first1 Start of range to search.
3884	* @param __last1 End of range to search.
3885	* @param __first2 Start of match candidates.
3886	* @param __last2 End of match candidates.
3887	* @return The first iterator @c i in the range
3888	* @p [__first1,__last1) such that @c i == @p (i2) such that i2 is an
3889	* iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3890	*
3891	* Searches the range @p [__first1,__last1) for an element that is
3892	* equal to some element in the range [__first2,__last2). If
3893	* found, returns an iterator in the range [__first1,__last1),
3894	* otherwise returns @p __last1.
3895	*/
3896	template<typename _InputIterator, typename _ForwardIterator>
3897	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3898	_InputIterator
3899	find_first_of(_InputIterator __first1, _InputIterator __last1,
3900	_ForwardIterator __first2, _ForwardIterator __last2)
3901	{
3902	// concept requirements
3903	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3904	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3905	__glibcxx_function_requires(_EqualOpConcept<
3906	typename iterator_traits<_InputIterator>::value_type,
3907	typename iterator_traits<_ForwardIterator>::value_type>)
3908	__glibcxx_requires_valid_range(__first1, __last1);
3909	__glibcxx_requires_valid_range(__first2, __last2);
3910
3911	for (; __first1 != __last1; ++__first1)
3912	for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3913	if (__first1 == __iter)
3914	return __first1;
3915	return __last1;
3916	}
3917
3918	/**
3919	* @brief Find element from a set in a sequence using a predicate.
3920	* @ingroup non_mutating_algorithms
3921	* @param __first1 Start of range to search.
3922	* @param __last1 End of range to search.
3923	* @param __first2 Start of match candidates.
3924	* @param __last2 End of match candidates.
3925	* @param __comp Predicate to use.
3926	* @return The first iterator @c i in the range
3927	* @p [__first1,__last1) such that @c comp(i, @p (i2)) is true
3928	* and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3929	* such iterator exists.
3930	*
3931
3932	* Searches the range @p [__first1,__last1) for an element that is
3933	* equal to some element in the range [__first2,__last2). If
3934	* found, returns an iterator in the range [__first1,__last1),
3935	* otherwise returns @p __last1.
3936	*/
3937	template<typename _InputIterator, typename _ForwardIterator,
3938	typename _BinaryPredicate>
3939	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3940	_InputIterator
3941	find_first_of(_InputIterator __first1, _InputIterator __last1,
3942	_ForwardIterator __first2, _ForwardIterator __last2,
3943	_BinaryPredicate __comp)
3944	{
3945	// concept requirements
3946	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3947	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3948	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3949	typename iterator_traits<_InputIterator>::value_type,
3950	typename iterator_traits<_ForwardIterator>::value_type>)
3951	__glibcxx_requires_valid_range(__first1, __last1);
3952	__glibcxx_requires_valid_range(__first2, __last2);
3953
3954	for (; __first1 != __last1; ++__first1)
3955	for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3956	if (__comp(__first1, __iter))
3957	return __first1;
3958	return __last1;
3959	}
3960
3961	/**
3962	* @brief Find two adjacent values in a sequence that are equal.
3963	* @ingroup non_mutating_algorithms
3964	* @param __first A forward iterator.
3965	* @param __last A forward iterator.
3966	* @return The first iterator @c i such that @c i and @c i+1 are both
3967	* valid iterators in @p [__first,__last) and such that @c i == @c (i+1),
3968	* or @p __last if no such iterator exists.
3969	*/
3970	template<typename _ForwardIterator>
3971	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3972	inline _ForwardIterator
3973	adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3974	{
3975	// concept requirements
3976	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3977	__glibcxx_function_requires(_EqualityComparableConcept<
3978	typename iterator_traits<_ForwardIterator>::value_type>)
3979	__glibcxx_requires_valid_range(__first, __last);
3980
3981	return std::__adjacent_find(__first, __last,
3982	__gnu_cxx::__ops::__iter_equal_to_iter());
3983	}
3984
3985	/**
3986	* @brief Find two adjacent values in a sequence using a predicate.
3987	* @ingroup non_mutating_algorithms
3988	* @param __first A forward iterator.
3989	* @param __last A forward iterator.
3990	* @param __binary_pred A binary predicate.
3991	* @return The first iterator @c i such that @c i and @c i+1 are both
3992	* valid iterators in @p [__first,__last) and such that
3993	* @p __binary_pred(i,(i+1)) is true, or @p __last if no such iterator
3994	* exists.
3995	*/
3996	template<typename _ForwardIterator, typename _BinaryPredicate>
3997	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3998	inline _ForwardIterator
3999	adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4000	_BinaryPredicate __binary_pred)
4001	{
4002	// concept requirements
4003	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4004	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4005	typename iterator_traits<_ForwardIterator>::value_type,
4006	typename iterator_traits<_ForwardIterator>::value_type>)
4007	__glibcxx_requires_valid_range(__first, __last);
4008
4009	return std::__adjacent_find(__first, __last,
4010	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4011	}
4012
4013	/**
4014	* @brief Count the number of copies of a value in a sequence.
4015	* @ingroup non_mutating_algorithms
4016	* @param __first An input iterator.
4017	* @param __last An input iterator.
4018	* @param __value The value to be counted.
4019	* @return The number of iterators @c i in the range @p [__first,__last)
4020	* for which @c *i == @p __value
4021	*/
4022	template<typename _InputIterator, typename _Tp>
4023	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4024	inline typename iterator_traits<_InputIterator>::difference_type
4025	count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4026	{
4027	// concept requirements
4028	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4029	__glibcxx_function_requires(_EqualOpConcept<
4030	typename iterator_traits<_InputIterator>::value_type, _Tp>)
4031	__glibcxx_requires_valid_range(__first, __last);
4032
4033	return std::__count_if(__first, __last,
4034	__gnu_cxx::__ops::__iter_equals_val(__value));
4035	}
4036
4037	/**
4038	* @brief Count the elements of a sequence for which a predicate is true.
4039	* @ingroup non_mutating_algorithms
4040	* @param __first An input iterator.
4041	* @param __last An input iterator.
4042	* @param __pred A predicate.
4043	* @return The number of iterators @c i in the range @p [__first,__last)
4044	* for which @p __pred(*i) is true.
4045	*/
4046	template<typename _InputIterator, typename _Predicate>
4047	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4048	inline typename iterator_traits<_InputIterator>::difference_type
4049	count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4050	{
4051	// concept requirements
4052	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4053	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4054	typename iterator_traits<_InputIterator>::value_type>)
4055	__glibcxx_requires_valid_range(__first, __last);
4056
4057	return std::__count_if(__first, __last,
4058	__gnu_cxx::__ops::__pred_iter(__pred));
4059	}
4060
4061	/**
4062	* @brief Search a sequence for a matching sub-sequence.
4063	* @ingroup non_mutating_algorithms
4064	* @param __first1 A forward iterator.
4065	* @param __last1 A forward iterator.
4066	* @param __first2 A forward iterator.
4067	* @param __last2 A forward iterator.
4068	* @return The first iterator @c i in the range @p
4069	* [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4070	* *(__first2+N) for each @c N in the range @p
4071	* [0,__last2-__first2), or @p __last1 if no such iterator exists.
4072	*
4073	* Searches the range @p [__first1,__last1) for a sub-sequence that
4074	* compares equal value-by-value with the sequence given by @p
4075	* [__first2,__last2) and returns an iterator to the first element
4076	* of the sub-sequence, or @p __last1 if the sub-sequence is not
4077	* found.
4078	*
4079	* Because the sub-sequence must lie completely within the range @p
4080	* [__first1,__last1) it must start at a position less than @p
4081	* __last1-(__last2-__first2) where @p __last2-__first2 is the
4082	* length of the sub-sequence.
4083	*
4084	* This means that the returned iterator @c i will be in the range
4085	* @p [__first1,__last1-(__last2-__first2))
4086	*/
4087	template<typename _ForwardIterator1, typename _ForwardIterator2>
4088	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4089	inline _ForwardIterator1
4090	search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4091	_ForwardIterator2 __first2, _ForwardIterator2 __last2)
4092	{
4093	// concept requirements
4094	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4095	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4096	__glibcxx_function_requires(_EqualOpConcept<
4097	typename iterator_traits<_ForwardIterator1>::value_type,
4098	typename iterator_traits<_ForwardIterator2>::value_type>)
4099	__glibcxx_requires_valid_range(__first1, __last1);
4100	__glibcxx_requires_valid_range(__first2, __last2);
4101
4102	return std::__search(__first1, __last1, __first2, __last2,
4103	__gnu_cxx::__ops::__iter_equal_to_iter());
4104	}
4105
4106	/**
4107	* @brief Search a sequence for a number of consecutive values.
4108	* @ingroup non_mutating_algorithms
4109	* @param __first A forward iterator.
4110	* @param __last A forward iterator.
4111	* @param __count The number of consecutive values.
4112	* @param __val The value to find.
4113	* @return The first iterator @c i in the range @p
4114	* [__first,__last-__count) such that @c *(i+N) == @p __val for
4115	* each @c N in the range @p [0,__count), or @p __last if no such
4116	* iterator exists.
4117	*
4118	* Searches the range @p [__first,__last) for @p count consecutive elements
4119	* equal to @p __val.
4120	*/
4121	template<typename _ForwardIterator, typename _Integer, typename _Tp>
4122	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4123	inline _ForwardIterator
4124	search_n(_ForwardIterator __first, _ForwardIterator __last,
4125	_Integer __count, const _Tp& __val)
4126	{
4127	// concept requirements
4128	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4129	__glibcxx_function_requires(_EqualOpConcept<
4130	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4131	__glibcxx_requires_valid_range(__first, __last);
4132
4133	return std::__search_n(__first, __last, __count,
4134	__gnu_cxx::__ops::__iter_equals_val(__val));
4135	}
4136
4137
4138	/**
4139	* @brief Search a sequence for a number of consecutive values using a
4140	* predicate.
4141	* @ingroup non_mutating_algorithms
4142	* @param __first A forward iterator.
4143	* @param __last A forward iterator.
4144	* @param __count The number of consecutive values.
4145	* @param __val The value to find.
4146	* @param __binary_pred A binary predicate.
4147	* @return The first iterator @c i in the range @p
4148	* [__first,__last-__count) such that @p
4149	* __binary_pred(*(i+N),__val) is true for each @c N in the range
4150	* @p [0,__count), or @p __last if no such iterator exists.
4151	*
4152	* Searches the range @p [__first,__last) for @p __count
4153	* consecutive elements for which the predicate returns true.
4154	*/
4155	template<typename _ForwardIterator, typename _Integer, typename _Tp,
4156	typename _BinaryPredicate>
4157	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4158	inline _ForwardIterator
4159	search_n(_ForwardIterator __first, _ForwardIterator __last,
4160	_Integer __count, const _Tp& __val,
4161	_BinaryPredicate __binary_pred)
4162	{
4163	// concept requirements
4164	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4165	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4166	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4167	__glibcxx_requires_valid_range(__first, __last);
4168
4169	return std::__search_n(__first, __last, __count,
4170	__gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4171	}
4172
4173	#if __cplusplus >= 201703L
4174	/* @brief Search a sequence using a Searcher object.*
4175	*
4176	* @param __first A forward iterator.
4177	* @param __last A forward iterator.
4178	* @param __searcher A callable object.
4179	* @return @p __searcher(__first,__last).first
4180	*/
4181	template<typename _ForwardIterator, typename _Searcher>
4182	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4183	inline _ForwardIterator
4184	search(_ForwardIterator __first, _ForwardIterator __last,
4185	const _Searcher& __searcher)
4186	{ return __searcher(__first, __last).first; }
4187	#endif
4188
4189	/**
4190	* @brief Perform an operation on a sequence.
4191	* @ingroup mutating_algorithms
4192	* @param __first An input iterator.
4193	* @param __last An input iterator.
4194	* @param __result An output iterator.
4195	* @param __unary_op A unary operator.
4196	* @return An output iterator equal to @p __result+(__last-__first).
4197	*
4198	* Applies the operator to each element in the input range and assigns
4199	* the results to successive elements of the output sequence.
4200	* Evaluates @p (__result+N)=unary_op((__first+N)) for each @c N in the
4201	* range @p [0,__last-__first).
4202	*
4203	* @p unary_op must not alter its argument.
4204	*/
4205	template<typename _InputIterator, typename _OutputIterator,
4206	typename _UnaryOperation>
4207	_GLIBCXX20_CONSTEXPR
4208	_OutputIterator
4209	transform(_InputIterator __first, _InputIterator __last,
4210	_OutputIterator __result, _UnaryOperation __unary_op)
4211	{
4212	// concept requirements
4213	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4214	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4215	// "the type returned by a _UnaryOperation"
4216	__typeof__(__unary_op(*__first))>)
4217	__glibcxx_requires_valid_range(__first, __last);
4218
4219	for (; __first != __last; ++__first, (void)++__result)
4220	__result = __unary_op(__first);
4221	return __result;
4222	}
4223
4224	/**
4225	* @brief Perform an operation on corresponding elements of two sequences.
4226	* @ingroup mutating_algorithms
4227	* @param __first1 An input iterator.
4228	* @param __last1 An input iterator.
4229	* @param __first2 An input iterator.
4230	* @param __result An output iterator.
4231	* @param __binary_op A binary operator.
4232	* @return An output iterator equal to @p result+(last-first).
4233	*
4234	* Applies the operator to the corresponding elements in the two
4235	* input ranges and assigns the results to successive elements of the
4236	* output sequence.
4237	* Evaluates @p
4238	* (__result+N)=__binary_op((__first1+N),*(__first2+N)) for each
4239	* @c N in the range @p [0,__last1-__first1).
4240	*
4241	* @p binary_op must not alter either of its arguments.
4242	*/
4243	template<typename _InputIterator1, typename _InputIterator2,
4244	typename _OutputIterator, typename _BinaryOperation>
4245	_GLIBCXX20_CONSTEXPR
4246	_OutputIterator
4247	transform(_InputIterator1 __first1, _InputIterator1 __last1,
4248	_InputIterator2 __first2, _OutputIterator __result,
4249	_BinaryOperation __binary_op)
4250	{
4251	// concept requirements
4252	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4253	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4254	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4255	// "the type returned by a _BinaryOperation"
4256	__typeof__(__binary_op(__first1,__first2))>)
4257	__glibcxx_requires_valid_range(__first1, __last1);
4258
4259	for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4260	__result = __binary_op(__first1, *__first2);
4261	return __result;
4262	}
4263
4264	/**
4265	* @brief Replace each occurrence of one value in a sequence with another
4266	* value.
4267	* @ingroup mutating_algorithms
4268	* @param __first A forward iterator.
4269	* @param __last A forward iterator.
4270	* @param __old_value The value to be replaced.
4271	* @param __new_value The replacement value.
4272	* @return replace() returns no value.
4273	*
4274	* For each iterator `i` in the range `[__first,__last)` if
4275	* `i == __old_value` then the assignment `i = __new_value` is performed.
4276	*/
4277	template<typename _ForwardIterator, typename _Tp>
4278	_GLIBCXX20_CONSTEXPR
4279	void
4280	replace(_ForwardIterator __first, _ForwardIterator __last,
4281	const _Tp& __old_value, const _Tp& __new_value)
4282	{
4283	// concept requirements
4284	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4285	_ForwardIterator>)
4286	__glibcxx_function_requires(_EqualOpConcept<
4287	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4288	__glibcxx_function_requires(_ConvertibleConcept<_Tp,
4289	typename iterator_traits<_ForwardIterator>::value_type>)
4290	__glibcxx_requires_valid_range(__first, __last);
4291
4292	for (; __first != __last; ++__first)
4293	if (*__first == __old_value)
4294	*__first = __new_value;
4295	}
4296
4297	/**
4298	* @brief Replace each value in a sequence for which a predicate returns
4299	* true with another value.
4300	* @ingroup mutating_algorithms
4301	* @param __first A forward iterator.
4302	* @param __last A forward iterator.
4303	* @param __pred A predicate.
4304	* @param __new_value The replacement value.
4305	* @return replace_if() returns no value.
4306	*
4307	* For each iterator `i` in the range `[__first,__last)` if `__pred(*i)`
4308	* is true then the assignment `*i = __new_value` is performed.
4309	*/
4310	template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4311	_GLIBCXX20_CONSTEXPR
4312	void
4313	replace_if(_ForwardIterator __first, _ForwardIterator __last,
4314	_Predicate __pred, const _Tp& __new_value)
4315	{
4316	// concept requirements
4317	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4318	_ForwardIterator>)
4319	__glibcxx_function_requires(_ConvertibleConcept<_Tp,
4320	typename iterator_traits<_ForwardIterator>::value_type>)
4321	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4322	typename iterator_traits<_ForwardIterator>::value_type>)
4323	__glibcxx_requires_valid_range(__first, __last);
4324
4325	for (; __first != __last; ++__first)
4326	if (__pred(*__first))
4327	*__first = __new_value;
4328	}
4329
4330	/**
4331	* @brief Assign the result of a function object to each value in a
4332	* sequence.
4333	* @ingroup mutating_algorithms
4334	* @param __first A forward iterator.
4335	* @param __last A forward iterator.
4336	* @param __gen A function object callable with no arguments.
4337	* @return generate() returns no value.
4338	*
4339	* Performs the assignment `*i = __gen()` for each `i` in the range
4340	* `[__first, __last)`.
4341	*/
4342	template<typename _ForwardIterator, typename _Generator>
4343	_GLIBCXX20_CONSTEXPR
4344	void
4345	generate(_ForwardIterator __first, _ForwardIterator __last,
4346	_Generator __gen)
4347	{
4348	// concept requirements
4349	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4350	__glibcxx_function_requires(_GeneratorConcept<_Generator,
4351	typename iterator_traits<_ForwardIterator>::value_type>)
4352	__glibcxx_requires_valid_range(__first, __last);
4353
4354	for (; __first != __last; ++__first)
4355	*__first = __gen();
4356	}
4357
4358	/**
4359	* @brief Assign the result of a function object to each value in a
4360	* sequence.
4361	* @ingroup mutating_algorithms
4362	* @param __first A forward iterator.
4363	* @param __n The length of the sequence.
4364	* @param __gen A function object callable with no arguments.
4365	* @return The end of the sequence, i.e., `__first + __n`
4366	*
4367	* Performs the assignment `*i = __gen()` for each `i` in the range
4368	* `[__first, __first + __n)`.
4369	*
4370	* If `__n` is negative, the function does nothing and returns `__first`.
4371	*/
4372	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4373	// DR 865. More algorithms that throw away information
4374	// DR 426. search_n(), fill_n(), and generate_n() with negative n
4375	template<typename _OutputIterator, typename _Size, typename _Generator>
4376	_GLIBCXX20_CONSTEXPR
4377	_OutputIterator
4378	generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4379	{
4380	// concept requirements
4381	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4382	// "the type returned by a _Generator"
4383	__typeof__(__gen())>)
4384
4385	typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4386	for (_IntSize __niter = std::__size_to_integer(__n);
4387	__niter > `0`; --__niter, (void) ++__first)
4388	*__first = __gen();
4389	return __first;
4390	}
4391
4392	/**
4393	* @brief Copy a sequence, removing consecutive duplicate values.
4394	* @ingroup mutating_algorithms
4395	* @param __first An input iterator.
4396	* @param __last An input iterator.
4397	* @param __result An output iterator.
4398	* @return An iterator designating the end of the resulting sequence.
4399	*
4400	* Copies each element in the range `[__first, __last)` to the range
4401	* beginning at `__result`, except that only the first element is copied
4402	* from groups of consecutive elements that compare equal.
4403	* `unique_copy()` is stable, so the relative order of elements that are
4404	* copied is unchanged.
4405	*/
4406	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4407	// DR 241. Does unique_copy() require CopyConstructible and Assignable?
4408	// DR 538. 241 again: Does unique_copy() require CopyConstructible and
4409	// Assignable?
4410	template<typename _InputIterator, typename _OutputIterator>
4411	_GLIBCXX20_CONSTEXPR
4412	inline _OutputIterator
4413	unique_copy(_InputIterator __first, _InputIterator __last,
4414	_OutputIterator __result)
4415	{
4416	// concept requirements
4417	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4418	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4419	typename iterator_traits<_InputIterator>::value_type>)
4420	__glibcxx_function_requires(_EqualityComparableConcept<
4421	typename iterator_traits<_InputIterator>::value_type>)
4422	__glibcxx_requires_valid_range(__first, __last);
4423
4424	if (__first == __last)
4425	return __result;
4426	return std::__unique_copy(__first, __last, __result,
4427	__gnu_cxx::__ops::__iter_equal_to_iter(),
4428	std::__iterator_category(__first),
4429	std::__iterator_category(__result));
4430	}
4431
4432	/**
4433	* @brief Copy a sequence, removing consecutive values using a predicate.
4434	* @ingroup mutating_algorithms
4435	* @param __first An input iterator.
4436	* @param __last An input iterator.
4437	* @param __result An output iterator.
4438	* @param __binary_pred A binary predicate.
4439	* @return An iterator designating the end of the resulting sequence.
4440	*
4441	* Copies each element in the range `[__first, __last)` to the range
4442	* beginning at `__result`, except that only the first element is copied
4443	* from groups of consecutive elements for which `__binary_pred` returns
4444	* true.
4445	* `unique_copy()` is stable, so the relative order of elements that are
4446	* copied is unchanged.
4447	*/
4448	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4449	// DR 241. Does unique_copy() require CopyConstructible and Assignable?
4450	template<typename _InputIterator, typename _OutputIterator,
4451	typename _BinaryPredicate>
4452	_GLIBCXX20_CONSTEXPR
4453	inline _OutputIterator
4454	unique_copy(_InputIterator __first, _InputIterator __last,
4455	_OutputIterator __result,
4456	_BinaryPredicate __binary_pred)
4457	{
4458	// concept requirements -- predicates checked later
4459	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4460	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4461	typename iterator_traits<_InputIterator>::value_type>)
4462	__glibcxx_requires_valid_range(__first, __last);
4463
4464	if (__first == __last)
4465	return __result;
4466	return std::__unique_copy(__first, __last, __result,
4467	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4468	std::__iterator_category(__first),
4469	std::__iterator_category(__result));
4470	}
4471
4472	#if __cplusplus <= 201103L \|\| _GLIBCXX_USE_DEPRECATED
4473	#if _GLIBCXX_HOSTED
4474	/**
4475	* @brief Randomly shuffle the elements of a sequence.
4476	* @ingroup mutating_algorithms
4477	* @param __first A forward iterator.
4478	* @param __last A forward iterator.
4479	* @return Nothing.
4480	*
4481	* Reorder the elements in the range `[__first, __last)` using a random
4482	* distribution, so that every possible ordering of the sequence is
4483	* equally likely.
4484	*
4485	* @deprecated
4486	* Since C++17, `std::random_shuffle` is not part of the C++ standard.
4487	* Use `std::shuffle` instead, which was introduced in C++11.
4488	*/
4489	template<typename _RandomAccessIterator>
4490	_GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4491	inline void
4492	random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4493	{
4494	// concept requirements
4495	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4496	_RandomAccessIterator>)
4497	__glibcxx_requires_valid_range(__first, __last);
4498
4499	if (__first != __last)
4500	for (_RandomAccessIterator __i = __first + `1`; __i != __last; ++__i)
4501	{
4502	// XXX rand() % N is not uniformly distributed
4503	_RandomAccessIterator __j = __first
4504	+ std::rand() % ((__i - __first) + `1`);
4505	if (__i != __j)
4506	std::iter_swap(__i, __j);
4507	}
4508	}
4509
4510	/**
4511	* @brief Shuffle the elements of a sequence using a random number
4512	* generator.
4513	* @ingroup mutating_algorithms
4514	* @param __first A forward iterator.
4515	* @param __last A forward iterator.
4516	* @param __rand The RNG functor or function.
4517	* @return Nothing.
4518	*
4519	* Reorders the elements in the range `[__first, __last)` using `__rand`
4520	* to provide a random distribution. Calling `__rand(N)` for a positive
4521	* integer `N` should return a randomly chosen integer from the
4522	* range `[0, N)`.
4523	*
4524	* @deprecated
4525	* Since C++17, `std::random_shuffle` is not part of the C++ standard.
4526	* Use `std::shuffle` instead, which was introduced in C++11.
4527	*/
4528	template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4529	_GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4530	void
4531	random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4532	#if __cplusplus >= 201103L
4533	_RandomNumberGenerator&& __rand)
4534	#else
4535	_RandomNumberGenerator& __rand)
4536	#endif
4537	{
4538	// concept requirements
4539	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4540	_RandomAccessIterator>)
4541	__glibcxx_requires_valid_range(__first, __last);
4542
4543	if (__first == __last)
4544	return;
4545	for (_RandomAccessIterator __i = __first + `1`; __i != __last; ++__i)
4546	{
4547	_RandomAccessIterator __j = __first + __rand((__i - __first) + `1`);
4548	if (__i != __j)
4549	std::iter_swap(__i, __j);
4550	}
4551	}
4552	#endif // HOSTED
4553	#endif // <= C++11 \|\| USE_DEPRECATED
4554
4555	/**
4556	* @brief Move elements for which a predicate is true to the beginning
4557	* of a sequence.
4558	* @ingroup mutating_algorithms
4559	* @param __first A forward iterator.
4560	* @param __last A forward iterator.
4561	* @param __pred A predicate functor.
4562	* @return An iterator `middle` such that `__pred(i)` is true for each
4563	* iterator `i` in the range `[__first, middle)` and false for each `i`
4564	* in the range `[middle, __last)`.
4565	*
4566	* `__pred` must not modify its operand. `partition()` does not preserve
4567	* the relative ordering of elements in each group, use
4568	* `stable_partition()` if this is needed.
4569	*/
4570	template<typename _ForwardIterator, typename _Predicate>
4571	_GLIBCXX20_CONSTEXPR
4572	inline _ForwardIterator
4573	partition(_ForwardIterator __first, _ForwardIterator __last,
4574	_Predicate __pred)
4575	{
4576	// concept requirements
4577	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4578	_ForwardIterator>)
4579	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4580	typename iterator_traits<_ForwardIterator>::value_type>)
4581	__glibcxx_requires_valid_range(__first, __last);
4582
4583	return std::__partition(__first, __last, __pred,
4584	std::__iterator_category(__first));
4585	}
4586
4587
4588	/**
4589	* @brief Sort the smallest elements of a sequence.
4590	* @ingroup sorting_algorithms
4591	* @param __first An iterator.
4592	* @param __middle Another iterator.
4593	* @param __last Another iterator.
4594	* @return Nothing.
4595	*
4596	* Sorts the smallest `(__middle - __first)` elements in the range
4597	* `[first, last)` and moves them to the range `[__first, __middle)`. The
4598	* order of the remaining elements in the range `[__middle, __last)` is
4599	* unspecified.
4600	* After the sort if `i` and `j` are iterators in the range
4601	* `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4602	* in the range `[__middle, __last)` then `j < i` and `k < i` are
4603	* both false.
4604	*/
4605	template<typename _RandomAccessIterator>
4606	_GLIBCXX20_CONSTEXPR
4607	inline void
4608	partial_sort(_RandomAccessIterator __first,
4609	_RandomAccessIterator __middle,
4610	_RandomAccessIterator __last)
4611	{
4612	// concept requirements
4613	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4614	_RandomAccessIterator>)
4615	__glibcxx_function_requires(_LessThanComparableConcept<
4616	typename iterator_traits<_RandomAccessIterator>::value_type>)
4617	__glibcxx_requires_valid_range(__first, __middle);
4618	__glibcxx_requires_valid_range(__middle, __last);
4619	__glibcxx_requires_irreflexive(__first, __last);
4620
4621	std::__partial_sort(__first, __middle, __last,
4622	__gnu_cxx::__ops::__iter_less_iter());
4623	}
4624
4625	/**
4626	* @brief Sort the smallest elements of a sequence using a predicate
4627	* for comparison.
4628	* @ingroup sorting_algorithms
4629	* @param __first An iterator.
4630	* @param __middle Another iterator.
4631	* @param __last Another iterator.
4632	* @param __comp A comparison functor.
4633	* @return Nothing.
4634	*
4635	* Sorts the smallest `(__middle - __first)` elements in the range
4636	* `[__first, __last)` and moves them to the range `[__first, __middle)`.
4637	* The order of the remaining elements in the range `[__middle, __last)` is
4638	* unspecified.
4639	* After the sort if `i` and `j` are iterators in the range
4640	* `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4641	* in the range `[__middle, __last)` then `__comp(j, i)` and
4642	* `__comp(k, i)` are both false.
4643	*/
4644	template<typename _RandomAccessIterator, typename _Compare>
4645	_GLIBCXX20_CONSTEXPR
4646	inline void
4647	partial_sort(_RandomAccessIterator __first,
4648	_RandomAccessIterator __middle,
4649	_RandomAccessIterator __last,
4650	_Compare __comp)
4651	{
4652	// concept requirements
4653	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4654	_RandomAccessIterator>)
4655	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4656	typename iterator_traits<_RandomAccessIterator>::value_type,
4657	typename iterator_traits<_RandomAccessIterator>::value_type>)
4658	__glibcxx_requires_valid_range(__first, __middle);
4659	__glibcxx_requires_valid_range(__middle, __last);
4660	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4661
4662	std::__partial_sort(__first, __middle, __last,
4663	__gnu_cxx::__ops::__iter_comp_iter(__comp));
4664	}
4665
4666	/**
4667	* @brief Sort a sequence just enough to find a particular position.
4668	* @ingroup sorting_algorithms
4669	* @param __first An iterator.
4670	* @param __nth Another iterator.
4671	* @param __last Another iterator.
4672	* @return Nothing.
4673	*
4674	* Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4675	* is the same element that would have been in that position had the
4676	* whole sequence been sorted. The elements either side of `*__nth` are
4677	* not completely sorted, but for any iterator `i` in the range
4678	* `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)` it
4679	* holds that `j < i` is false.
4680	*/
4681	template<typename _RandomAccessIterator>
4682	_GLIBCXX20_CONSTEXPR
4683	inline void
4684	nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4685	_RandomAccessIterator __last)
4686	{
4687	// concept requirements
4688	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4689	_RandomAccessIterator>)
4690	__glibcxx_function_requires(_LessThanComparableConcept<
4691	typename iterator_traits<_RandomAccessIterator>::value_type>)
4692	__glibcxx_requires_valid_range(__first, __nth);
4693	__glibcxx_requires_valid_range(__nth, __last);
4694	__glibcxx_requires_irreflexive(__first, __last);
4695
4696	if (__first == __last \|\| __nth == __last)
4697	return;
4698
4699	std::__introselect(__first, __nth, __last,
4700	std::__lg(__last - __first) * `2`,
4701	__gnu_cxx::__ops::__iter_less_iter());
4702	}
4703
4704	/**
4705	* @brief Sort a sequence just enough to find a particular position
4706	* using a predicate for comparison.
4707	* @ingroup sorting_algorithms
4708	* @param __first An iterator.
4709	* @param __nth Another iterator.
4710	* @param __last Another iterator.
4711	* @param __comp A comparison functor.
4712	* @return Nothing.
4713	*
4714	* Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4715	* is the same element that would have been in that position had the
4716	* whole sequence been sorted. The elements either side of `*__nth` are
4717	* not completely sorted, but for any iterator `i` in the range
4718	* `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)`
4719	* it holds that `__comp(j, i)` is false.
4720	*/
4721	template<typename _RandomAccessIterator, typename _Compare>
4722	_GLIBCXX20_CONSTEXPR
4723	inline void
4724	nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4725	_RandomAccessIterator __last, _Compare __comp)
4726	{
4727	// concept requirements
4728	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4729	_RandomAccessIterator>)
4730	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4731	typename iterator_traits<_RandomAccessIterator>::value_type,
4732	typename iterator_traits<_RandomAccessIterator>::value_type>)
4733	__glibcxx_requires_valid_range(__first, __nth);
4734	__glibcxx_requires_valid_range(__nth, __last);
4735	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4736
4737	if (__first == __last \|\| __nth == __last)
4738	return;
4739
4740	std::__introselect(__first, __nth, __last,
4741	std::__lg(__last - __first) * `2`,
4742	__gnu_cxx::__ops::__iter_comp_iter(__comp));
4743	}
4744
4745	/**
4746	* @brief Sort the elements of a sequence.
4747	* @ingroup sorting_algorithms
4748	* @param __first An iterator.
4749	* @param __last Another iterator.
4750	* @return Nothing.
4751	*
4752	* Sorts the elements in the range `[__first, __last)` in ascending order,
4753	* such that for each iterator `i` in the range `[__first, __last - 1)`,
4754	* `(i+1) < i` is false.
4755	*
4756	* The relative ordering of equivalent elements is not preserved, use
4757	* `stable_sort()` if this is needed.
4758	*/
4759	template<typename _RandomAccessIterator>
4760	_GLIBCXX20_CONSTEXPR
4761	inline void
4762	sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4763	{
4764	// concept requirements
4765	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4766	_RandomAccessIterator>)
4767	__glibcxx_function_requires(_LessThanComparableConcept<
4768	typename iterator_traits<_RandomAccessIterator>::value_type>)
4769	__glibcxx_requires_valid_range(__first, __last);
4770	__glibcxx_requires_irreflexive(__first, __last);
4771
4772	std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4773	}
4774
4775	/**
4776	* @brief Sort the elements of a sequence using a predicate for comparison.
4777	* @ingroup sorting_algorithms
4778	* @param __first An iterator.
4779	* @param __last Another iterator.
4780	* @param __comp A comparison functor.
4781	* @return Nothing.
4782	*
4783	* Sorts the elements in the range `[__first, __last)` in ascending order,
4784	* such that `__comp((i+1), i)` is false for every iterator `i` in the
4785	* range `[__first, __last - 1)`.
4786	*
4787	* The relative ordering of equivalent elements is not preserved, use
4788	* `stable_sort()` if this is needed.
4789	*/
4790	template<typename _RandomAccessIterator, typename _Compare>
4791	_GLIBCXX20_CONSTEXPR
4792	inline void
4793	sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4794	_Compare __comp)
4795	{
4796	// concept requirements
4797	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4798	_RandomAccessIterator>)
4799	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4800	typename iterator_traits<_RandomAccessIterator>::value_type,
4801	typename iterator_traits<_RandomAccessIterator>::value_type>)
4802	__glibcxx_requires_valid_range(__first, __last);
4803	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4804
4805	std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4806	}
4807
4808	template<typename _InputIterator1, typename _InputIterator2,
4809	typename _OutputIterator, typename _Compare>
4810	_GLIBCXX20_CONSTEXPR
4811	_OutputIterator
4812	__merge(_InputIterator1 __first1, _InputIterator1 __last1,
4813	_InputIterator2 __first2, _InputIterator2 __last2,
4814	_OutputIterator __result, _Compare __comp)
4815	{
4816	while (__first1 != __last1 && __first2 != __last2)
4817	{
4818	if (__comp(__first2, __first1))
4819	{
4820	__result = __first2;
4821	++__first2;
4822	}
4823	else
4824	{
4825	__result = __first1;
4826	++__first1;
4827	}
4828	++__result;
4829	}
4830	return std::copy(__first2, __last2,
4831	std::copy(__first1, __last1, __result));
4832	}
4833
4834	/**
4835	* @brief Merges two sorted ranges.
4836	* @ingroup sorting_algorithms
4837	* @param __first1 An iterator.
4838	* @param __first2 Another iterator.
4839	* @param __last1 Another iterator.
4840	* @param __last2 Another iterator.
4841	* @param __result An iterator pointing to the end of the merged range.
4842	* @return An output iterator equal to @p __result + (__last1 - __first1)
4843	* + (__last2 - __first2).
4844	*
4845	* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4846	* the sorted range @p [__result, __result + (__last1-__first1) +
4847	* (__last2-__first2)). Both input ranges must be sorted, and the
4848	* output range must not overlap with either of the input ranges.
4849	* The sort is @e stable, that is, for equivalent elements in the
4850	* two ranges, elements from the first range will always come
4851	* before elements from the second.
4852	*/
4853	template<typename _InputIterator1, typename _InputIterator2,
4854	typename _OutputIterator>
4855	_GLIBCXX20_CONSTEXPR
4856	inline _OutputIterator
4857	merge(_InputIterator1 __first1, _InputIterator1 __last1,
4858	_InputIterator2 __first2, _InputIterator2 __last2,
4859	_OutputIterator __result)
4860	{
4861	// concept requirements
4862	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4863	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4864	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4865	typename iterator_traits<_InputIterator1>::value_type>)
4866	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4867	typename iterator_traits<_InputIterator2>::value_type>)
4868	__glibcxx_function_requires(_LessThanOpConcept<
4869	typename iterator_traits<_InputIterator2>::value_type,
4870	typename iterator_traits<_InputIterator1>::value_type>)
4871	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
4872	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
4873	__glibcxx_requires_irreflexive2(__first1, __last1);
4874	__glibcxx_requires_irreflexive2(__first2, __last2);
4875
4876	return _GLIBCXX_STD_A::__merge(__first1, __last1,
4877	__first2, __last2, __result,
4878	__gnu_cxx::__ops::__iter_less_iter());
4879	}
4880
4881	/**
4882	* @brief Merges two sorted ranges.
4883	* @ingroup sorting_algorithms
4884	* @param __first1 An iterator.
4885	* @param __first2 Another iterator.
4886	* @param __last1 Another iterator.
4887	* @param __last2 Another iterator.
4888	* @param __result An iterator pointing to the end of the merged range.
4889	* @param __comp A functor to use for comparisons.
4890	* @return An output iterator equal to @p __result + (__last1 - __first1)
4891	* + (__last2 - __first2).
4892	*
4893	* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4894	* the sorted range @p [__result, __result + (__last1-__first1) +
4895	* (__last2-__first2)). Both input ranges must be sorted, and the
4896	* output range must not overlap with either of the input ranges.
4897	* The sort is @e stable, that is, for equivalent elements in the
4898	* two ranges, elements from the first range will always come
4899	* before elements from the second.
4900	*
4901	* The comparison function should have the same effects on ordering as
4902	* the function used for the initial sort.
4903	*/
4904	template<typename _InputIterator1, typename _InputIterator2,
4905	typename _OutputIterator, typename _Compare>
4906	_GLIBCXX20_CONSTEXPR
4907	inline _OutputIterator
4908	merge(_InputIterator1 __first1, _InputIterator1 __last1,
4909	_InputIterator2 __first2, _InputIterator2 __last2,
4910	_OutputIterator __result, _Compare __comp)
4911	{
4912	// concept requirements
4913	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4914	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4915	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4916	typename iterator_traits<_InputIterator1>::value_type>)
4917	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4918	typename iterator_traits<_InputIterator2>::value_type>)
4919	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4920	typename iterator_traits<_InputIterator2>::value_type,
4921	typename iterator_traits<_InputIterator1>::value_type>)
4922	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4923	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4924	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4925	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4926
4927	return _GLIBCXX_STD_A::__merge(__first1, __last1,
4928	__first2, __last2, __result,
4929	__gnu_cxx::__ops::__iter_comp_iter(__comp));
4930	}
4931
4932	template<typename _RandomAccessIterator, typename _Compare>
4933	inline void
4934	__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4935	_Compare __comp)
4936	{
4937	typedef typename iterator_traits<_RandomAccessIterator>::value_type
4938	_ValueType;
4939	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4940	_DistanceType;
4941
4942	if (__first == __last)
4943	return;
4944
4945	#if _GLIBCXX_HOSTED
4946	typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4947	// __stable_sort_adaptive sorts the range in two halves,
4948	// so the buffer only needs to fit half the range at once.
4949	_TmpBuf __buf(__first, (__last - __first + `1`) / `2`);
4950
4951	if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
4952	std::__stable_sort_adaptive(__first,
4953	__first + _DistanceType(__buf.size()),
4954	__last, __buf.begin(), __comp);
4955	else if (__builtin_expect(__buf.begin() == `0`, false))
4956	std::__inplace_stable_sort(__first, __last, __comp);
4957	else
4958	std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
4959	_DistanceType(__buf.size()), __comp);
4960	#else
4961	std::__inplace_stable_sort(__first, __last, __comp);
4962	#endif
4963	}
4964
4965	/**
4966	* @brief Sort the elements of a sequence, preserving the relative order
4967	* of equivalent elements.
4968	* @ingroup sorting_algorithms
4969	* @param __first An iterator.
4970	* @param __last Another iterator.
4971	* @return Nothing.
4972	*
4973	* Sorts the elements in the range @p [__first,__last) in ascending order,
4974	* such that for each iterator @p i in the range @p [__first,__last-1),
4975	* @p (i+1)<i is false.
4976	*
4977	* The relative ordering of equivalent elements is preserved, so any two
4978	* elements @p x and @p y in the range @p [__first,__last) such that
4979	* @p x<y is false and @p y<x is false will have the same relative
4980	* ordering after calling @p stable_sort().
4981	*/
4982	template<typename _RandomAccessIterator>
4983	inline void
4984	stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4985	{
4986	// concept requirements
4987	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4988	_RandomAccessIterator>)
4989	__glibcxx_function_requires(_LessThanComparableConcept<
4990	typename iterator_traits<_RandomAccessIterator>::value_type>)
4991	__glibcxx_requires_valid_range(__first, __last);
4992	__glibcxx_requires_irreflexive(__first, __last);
4993
4994	_GLIBCXX_STD_A::__stable_sort(__first, __last,
4995	__gnu_cxx::__ops::__iter_less_iter());
4996	}
4997
4998	/**
4999	* @brief Sort the elements of a sequence using a predicate for comparison,
5000	* preserving the relative order of equivalent elements.
5001	* @ingroup sorting_algorithms
5002	* @param __first An iterator.
5003	* @param __last Another iterator.
5004	* @param __comp A comparison functor.
5005	* @return Nothing.
5006	*
5007	* Sorts the elements in the range @p [__first,__last) in ascending order,
5008	* such that for each iterator @p i in the range @p [__first,__last-1),
5009	* @p __comp((i+1),i) is false.
5010	*
5011	* The relative ordering of equivalent elements is preserved, so any two
5012	* elements @p x and @p y in the range @p [__first,__last) such that
5013	* @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5014	* relative ordering after calling @p stable_sort().
5015	*/
5016	template<typename _RandomAccessIterator, typename _Compare>
5017	inline void
5018	stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5019	_Compare __comp)
5020	{
5021	// concept requirements
5022	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5023	_RandomAccessIterator>)
5024	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5025	typename iterator_traits<_RandomAccessIterator>::value_type,
5026	typename iterator_traits<_RandomAccessIterator>::value_type>)
5027	__glibcxx_requires_valid_range(__first, __last);
5028	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5029
5030	_GLIBCXX_STD_A::__stable_sort(__first, __last,
5031	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5032	}
5033
5034	template<typename _InputIterator1, typename _InputIterator2,
5035	typename _OutputIterator,
5036	typename _Compare>
5037	_GLIBCXX20_CONSTEXPR
5038	_OutputIterator
5039	__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5040	_InputIterator2 __first2, _InputIterator2 __last2,
5041	_OutputIterator __result, _Compare __comp)
5042	{
5043	while (__first1 != __last1 && __first2 != __last2)
5044	{
5045	if (__comp(__first1, __first2))
5046	{
5047	__result = __first1;
5048	++__first1;
5049	}
5050	else if (__comp(__first2, __first1))
5051	{
5052	__result = __first2;
5053	++__first2;
5054	}
5055	else
5056	{
5057	__result = __first1;
5058	++__first1;
5059	++__first2;
5060	}
5061	++__result;
5062	}
5063	return std::copy(__first2, __last2,
5064	std::copy(__first1, __last1, __result));
5065	}
5066
5067	/**
5068	* @brief Return the union of two sorted ranges.
5069	* @ingroup set_algorithms
5070	* @param __first1 Start of first range.
5071	* @param __last1 End of first range.
5072	* @param __first2 Start of second range.
5073	* @param __last2 End of second range.
5074	* @param __result Start of output range.
5075	* @return End of the output range.
5076	* @ingroup set_algorithms
5077	*
5078	* This operation iterates over both ranges, copying elements present in
5079	* each range in order to the output range. Iterators increment for each
5080	* range. When the current element of one range is less than the other,
5081	* that element is copied and the iterator advanced. If an element is
5082	* contained in both ranges, the element from the first range is copied and
5083	* both ranges advance. The output range may not overlap either input
5084	* range.
5085	*/
5086	template<typename _InputIterator1, typename _InputIterator2,
5087	typename _OutputIterator>
5088	_GLIBCXX20_CONSTEXPR
5089	inline _OutputIterator
5090	set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5091	_InputIterator2 __first2, _InputIterator2 __last2,
5092	_OutputIterator __result)
5093	{
5094	// concept requirements
5095	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5096	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5097	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5098	typename iterator_traits<_InputIterator1>::value_type>)
5099	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5100	typename iterator_traits<_InputIterator2>::value_type>)
5101	__glibcxx_function_requires(_LessThanOpConcept<
5102	typename iterator_traits<_InputIterator1>::value_type,
5103	typename iterator_traits<_InputIterator2>::value_type>)
5104	__glibcxx_function_requires(_LessThanOpConcept<
5105	typename iterator_traits<_InputIterator2>::value_type,
5106	typename iterator_traits<_InputIterator1>::value_type>)
5107	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5108	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5109	__glibcxx_requires_irreflexive2(__first1, __last1);
5110	__glibcxx_requires_irreflexive2(__first2, __last2);
5111
5112	return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5113	__first2, __last2, __result,
5114	__gnu_cxx::__ops::__iter_less_iter());
5115	}
5116
5117	/**
5118	* @brief Return the union of two sorted ranges using a comparison functor.
5119	* @ingroup set_algorithms
5120	* @param __first1 Start of first range.
5121	* @param __last1 End of first range.
5122	* @param __first2 Start of second range.
5123	* @param __last2 End of second range.
5124	* @param __result Start of output range.
5125	* @param __comp The comparison functor.
5126	* @return End of the output range.
5127	* @ingroup set_algorithms
5128	*
5129	* This operation iterates over both ranges, copying elements present in
5130	* each range in order to the output range. Iterators increment for each
5131	* range. When the current element of one range is less than the other
5132	* according to @p __comp, that element is copied and the iterator advanced.
5133	* If an equivalent element according to @p __comp is contained in both
5134	* ranges, the element from the first range is copied and both ranges
5135	* advance. The output range may not overlap either input range.
5136	*/
5137	template<typename _InputIterator1, typename _InputIterator2,
5138	typename _OutputIterator, typename _Compare>
5139	_GLIBCXX20_CONSTEXPR
5140	inline _OutputIterator
5141	set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5142	_InputIterator2 __first2, _InputIterator2 __last2,
5143	_OutputIterator __result, _Compare __comp)
5144	{
5145	// concept requirements
5146	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5147	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5148	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5149	typename iterator_traits<_InputIterator1>::value_type>)
5150	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5151	typename iterator_traits<_InputIterator2>::value_type>)
5152	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5153	typename iterator_traits<_InputIterator1>::value_type,
5154	typename iterator_traits<_InputIterator2>::value_type>)
5155	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5156	typename iterator_traits<_InputIterator2>::value_type,
5157	typename iterator_traits<_InputIterator1>::value_type>)
5158	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5159	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5160	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5161	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5162
5163	return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5164	__first2, __last2, __result,
5165	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5166	}
5167
5168	template<typename _InputIterator1, typename _InputIterator2,
5169	typename _OutputIterator,
5170	typename _Compare>
5171	_GLIBCXX20_CONSTEXPR
5172	_OutputIterator
5173	__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5174	_InputIterator2 __first2, _InputIterator2 __last2,
5175	_OutputIterator __result, _Compare __comp)
5176	{
5177	while (__first1 != __last1 && __first2 != __last2)
5178	if (__comp(__first1, __first2))
5179	++__first1;
5180	else if (__comp(__first2, __first1))
5181	++__first2;
5182	else
5183	{
5184	__result = __first1;
5185	++__first1;
5186	++__first2;
5187	++__result;
5188	}
5189	return __result;
5190	}
5191
5192	/**
5193	* @brief Return the intersection of two sorted ranges.
5194	* @ingroup set_algorithms
5195	* @param __first1 Start of first range.
5196	* @param __last1 End of first range.
5197	* @param __first2 Start of second range.
5198	* @param __last2 End of second range.
5199	* @param __result Start of output range.
5200	* @return End of the output range.
5201	* @ingroup set_algorithms
5202	*
5203	* This operation iterates over both ranges, copying elements present in
5204	* both ranges in order to the output range. Iterators increment for each
5205	* range. When the current element of one range is less than the other,
5206	* that iterator advances. If an element is contained in both ranges, the
5207	* element from the first range is copied and both ranges advance. The
5208	* output range may not overlap either input range.
5209	*/
5210	template<typename _InputIterator1, typename _InputIterator2,
5211	typename _OutputIterator>
5212	_GLIBCXX20_CONSTEXPR
5213	inline _OutputIterator
5214	set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5215	_InputIterator2 __first2, _InputIterator2 __last2,
5216	_OutputIterator __result)
5217	{
5218	// concept requirements
5219	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5220	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5221	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5222	typename iterator_traits<_InputIterator1>::value_type>)
5223	__glibcxx_function_requires(_LessThanOpConcept<
5224	typename iterator_traits<_InputIterator1>::value_type,
5225	typename iterator_traits<_InputIterator2>::value_type>)
5226	__glibcxx_function_requires(_LessThanOpConcept<
5227	typename iterator_traits<_InputIterator2>::value_type,
5228	typename iterator_traits<_InputIterator1>::value_type>)
5229	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5230	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5231	__glibcxx_requires_irreflexive2(__first1, __last1);
5232	__glibcxx_requires_irreflexive2(__first2, __last2);
5233
5234	return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5235	__first2, __last2, __result,
5236	__gnu_cxx::__ops::__iter_less_iter());
5237	}
5238
5239	/**
5240	* @brief Return the intersection of two sorted ranges using comparison
5241	* functor.
5242	* @ingroup set_algorithms
5243	* @param __first1 Start of first range.
5244	* @param __last1 End of first range.
5245	* @param __first2 Start of second range.
5246	* @param __last2 End of second range.
5247	* @param __result Start of output range.
5248	* @param __comp The comparison functor.
5249	* @return End of the output range.
5250	* @ingroup set_algorithms
5251	*
5252	* This operation iterates over both ranges, copying elements present in
5253	* both ranges in order to the output range. Iterators increment for each
5254	* range. When the current element of one range is less than the other
5255	* according to @p __comp, that iterator advances. If an element is
5256	* contained in both ranges according to @p __comp, the element from the
5257	* first range is copied and both ranges advance. The output range may not
5258	* overlap either input range.
5259	*/
5260	template<typename _InputIterator1, typename _InputIterator2,
5261	typename _OutputIterator, typename _Compare>
5262	_GLIBCXX20_CONSTEXPR
5263	inline _OutputIterator
5264	set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5265	_InputIterator2 __first2, _InputIterator2 __last2,
5266	_OutputIterator __result, _Compare __comp)
5267	{
5268	// concept requirements
5269	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5270	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5271	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5272	typename iterator_traits<_InputIterator1>::value_type>)
5273	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5274	typename iterator_traits<_InputIterator1>::value_type,
5275	typename iterator_traits<_InputIterator2>::value_type>)
5276	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5277	typename iterator_traits<_InputIterator2>::value_type,
5278	typename iterator_traits<_InputIterator1>::value_type>)
5279	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5280	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5281	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5282	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5283
5284	return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5285	__first2, __last2, __result,
5286	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5287	}
5288
5289	template<typename _InputIterator1, typename _InputIterator2,
5290	typename _OutputIterator,
5291	typename _Compare>
5292	_GLIBCXX20_CONSTEXPR
5293	_OutputIterator
5294	__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5295	_InputIterator2 __first2, _InputIterator2 __last2,
5296	_OutputIterator __result, _Compare __comp)
5297	{
5298	while (__first1 != __last1 && __first2 != __last2)
5299	if (__comp(__first1, __first2))
5300	{
5301	__result = __first1;
5302	++__first1;
5303	++__result;
5304	}
5305	else if (__comp(__first2, __first1))
5306	++__first2;
5307	else
5308	{
5309	++__first1;
5310	++__first2;
5311	}
5312	return std::copy(__first1, __last1, __result);
5313	}
5314
5315	/**
5316	* @brief Return the difference of two sorted ranges.
5317	* @ingroup set_algorithms
5318	* @param __first1 Start of first range.
5319	* @param __last1 End of first range.
5320	* @param __first2 Start of second range.
5321	* @param __last2 End of second range.
5322	* @param __result Start of output range.
5323	* @return End of the output range.
5324	* @ingroup set_algorithms
5325	*
5326	* This operation iterates over both ranges, copying elements present in
5327	* the first range but not the second in order to the output range.
5328	* Iterators increment for each range. When the current element of the
5329	* first range is less than the second, that element is copied and the
5330	* iterator advances. If the current element of the second range is less,
5331	* the iterator advances, but no element is copied. If an element is
5332	* contained in both ranges, no elements are copied and both ranges
5333	* advance. The output range may not overlap either input range.
5334	*/
5335	template<typename _InputIterator1, typename _InputIterator2,
5336	typename _OutputIterator>
5337	_GLIBCXX20_CONSTEXPR
5338	inline _OutputIterator
5339	set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5340	_InputIterator2 __first2, _InputIterator2 __last2,
5341	_OutputIterator __result)
5342	{
5343	// concept requirements
5344	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5345	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5346	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5347	typename iterator_traits<_InputIterator1>::value_type>)
5348	__glibcxx_function_requires(_LessThanOpConcept<
5349	typename iterator_traits<_InputIterator1>::value_type,
5350	typename iterator_traits<_InputIterator2>::value_type>)
5351	__glibcxx_function_requires(_LessThanOpConcept<
5352	typename iterator_traits<_InputIterator2>::value_type,
5353	typename iterator_traits<_InputIterator1>::value_type>)
5354	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5355	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5356	__glibcxx_requires_irreflexive2(__first1, __last1);
5357	__glibcxx_requires_irreflexive2(__first2, __last2);
5358
5359	return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5360	__first2, __last2, __result,
5361	__gnu_cxx::__ops::__iter_less_iter());
5362	}
5363
5364	/**
5365	* @brief Return the difference of two sorted ranges using comparison
5366	* functor.
5367	* @ingroup set_algorithms
5368	* @param __first1 Start of first range.
5369	* @param __last1 End of first range.
5370	* @param __first2 Start of second range.
5371	* @param __last2 End of second range.
5372	* @param __result Start of output range.
5373	* @param __comp The comparison functor.
5374	* @return End of the output range.
5375	* @ingroup set_algorithms
5376	*
5377	* This operation iterates over both ranges, copying elements present in
5378	* the first range but not the second in order to the output range.
5379	* Iterators increment for each range. When the current element of the
5380	* first range is less than the second according to @p __comp, that element
5381	* is copied and the iterator advances. If the current element of the
5382	* second range is less, no element is copied and the iterator advances.
5383	* If an element is contained in both ranges according to @p __comp, no
5384	* elements are copied and both ranges advance. The output range may not
5385	* overlap either input range.
5386	*/
5387	template<typename _InputIterator1, typename _InputIterator2,
5388	typename _OutputIterator, typename _Compare>
5389	_GLIBCXX20_CONSTEXPR
5390	inline _OutputIterator
5391	set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5392	_InputIterator2 __first2, _InputIterator2 __last2,
5393	_OutputIterator __result, _Compare __comp)
5394	{
5395	// concept requirements
5396	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5397	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5398	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5399	typename iterator_traits<_InputIterator1>::value_type>)
5400	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5401	typename iterator_traits<_InputIterator1>::value_type,
5402	typename iterator_traits<_InputIterator2>::value_type>)
5403	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5404	typename iterator_traits<_InputIterator2>::value_type,
5405	typename iterator_traits<_InputIterator1>::value_type>)
5406	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5407	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5408	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5409	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5410
5411	return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5412	__first2, __last2, __result,
5413	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5414	}
5415
5416	template<typename _InputIterator1, typename _InputIterator2,
5417	typename _OutputIterator,
5418	typename _Compare>
5419	_GLIBCXX20_CONSTEXPR
5420	_OutputIterator
5421	__set_symmetric_difference(_InputIterator1 __first1,
5422	_InputIterator1 __last1,
5423	_InputIterator2 __first2,
5424	_InputIterator2 __last2,
5425	_OutputIterator __result,
5426	_Compare __comp)
5427	{
5428	while (__first1 != __last1 && __first2 != __last2)
5429	if (__comp(__first1, __first2))
5430	{
5431	__result = __first1;
5432	++__first1;
5433	++__result;
5434	}
5435	else if (__comp(__first2, __first1))
5436	{
5437	__result = __first2;
5438	++__first2;
5439	++__result;
5440	}
5441	else
5442	{
5443	++__first1;
5444	++__first2;
5445	}
5446	return std::copy(__first2, __last2,
5447	std::copy(__first1, __last1, __result));
5448	}
5449
5450	/**
5451	* @brief Return the symmetric difference of two sorted ranges.
5452	* @ingroup set_algorithms
5453	* @param __first1 Start of first range.
5454	* @param __last1 End of first range.
5455	* @param __first2 Start of second range.
5456	* @param __last2 End of second range.
5457	* @param __result Start of output range.
5458	* @return End of the output range.
5459	* @ingroup set_algorithms
5460	*
5461	* This operation iterates over both ranges, copying elements present in
5462	* one range but not the other in order to the output range. Iterators
5463	* increment for each range. When the current element of one range is less
5464	* than the other, that element is copied and the iterator advances. If an
5465	* element is contained in both ranges, no elements are copied and both
5466	* ranges advance. The output range may not overlap either input range.
5467	*/
5468	template<typename _InputIterator1, typename _InputIterator2,
5469	typename _OutputIterator>
5470	_GLIBCXX20_CONSTEXPR
5471	inline _OutputIterator
5472	set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5473	_InputIterator2 __first2, _InputIterator2 __last2,
5474	_OutputIterator __result)
5475	{
5476	// concept requirements
5477	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5478	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5479	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5480	typename iterator_traits<_InputIterator1>::value_type>)
5481	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5482	typename iterator_traits<_InputIterator2>::value_type>)
5483	__glibcxx_function_requires(_LessThanOpConcept<
5484	typename iterator_traits<_InputIterator1>::value_type,
5485	typename iterator_traits<_InputIterator2>::value_type>)
5486	__glibcxx_function_requires(_LessThanOpConcept<
5487	typename iterator_traits<_InputIterator2>::value_type,
5488	typename iterator_traits<_InputIterator1>::value_type>)
5489	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5490	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5491	__glibcxx_requires_irreflexive2(__first1, __last1);
5492	__glibcxx_requires_irreflexive2(__first2, __last2);
5493
5494	return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5495	__first2, __last2, __result,
5496	__gnu_cxx::__ops::__iter_less_iter());
5497	}
5498
5499	/**
5500	* @brief Return the symmetric difference of two sorted ranges using
5501	* comparison functor.
5502	* @ingroup set_algorithms
5503	* @param __first1 Start of first range.
5504	* @param __last1 End of first range.
5505	* @param __first2 Start of second range.
5506	* @param __last2 End of second range.
5507	* @param __result Start of output range.
5508	* @param __comp The comparison functor.
5509	* @return End of the output range.
5510	* @ingroup set_algorithms
5511	*
5512	* This operation iterates over both ranges, copying elements present in
5513	* one range but not the other in order to the output range. Iterators
5514	* increment for each range. When the current element of one range is less
5515	* than the other according to @p comp, that element is copied and the
5516	* iterator advances. If an element is contained in both ranges according
5517	* to @p __comp, no elements are copied and both ranges advance. The output
5518	* range may not overlap either input range.
5519	*/
5520	template<typename _InputIterator1, typename _InputIterator2,
5521	typename _OutputIterator, typename _Compare>
5522	_GLIBCXX20_CONSTEXPR
5523	inline _OutputIterator
5524	set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5525	_InputIterator2 __first2, _InputIterator2 __last2,
5526	_OutputIterator __result,
5527	_Compare __comp)
5528	{
5529	// concept requirements
5530	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5531	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5532	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5533	typename iterator_traits<_InputIterator1>::value_type>)
5534	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5535	typename iterator_traits<_InputIterator2>::value_type>)
5536	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5537	typename iterator_traits<_InputIterator1>::value_type,
5538	typename iterator_traits<_InputIterator2>::value_type>)
5539	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5540	typename iterator_traits<_InputIterator2>::value_type,
5541	typename iterator_traits<_InputIterator1>::value_type>)
5542	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5543	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5544	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5545	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5546
5547	return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5548	__first2, __last2, __result,
5549	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5550	}
5551
5552	template<typename _ForwardIterator, typename _Compare>
5553	_GLIBCXX14_CONSTEXPR
5554	_ForwardIterator
5555	__min_element(_ForwardIterator __first, _ForwardIterator __last,
5556	_Compare __comp)
5557	{
5558	if (__first == __last)
5559	return __first;
5560	_ForwardIterator __result = __first;
5561	while (++__first != __last)
5562	if (__comp(__first, __result))
5563	__result = __first;
5564	return __result;
5565	}
5566
5567	/**
5568	* @brief Return the minimum element in a range.
5569	* @ingroup sorting_algorithms
5570	* @param __first Start of range.
5571	* @param __last End of range.
5572	* @return Iterator referencing the first instance of the smallest value.
5573	*/
5574	template<typename _ForwardIterator>
5575	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5576	_ForwardIterator
5577	inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5578	{
5579	// concept requirements
5580	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5581	__glibcxx_function_requires(_LessThanComparableConcept<
5582	typename iterator_traits<_ForwardIterator>::value_type>)
5583	__glibcxx_requires_valid_range(__first, __last);
5584	__glibcxx_requires_irreflexive(__first, __last);
5585
5586	return _GLIBCXX_STD_A::__min_element(__first, __last,
5587	__gnu_cxx::__ops::__iter_less_iter());
5588	}
5589
5590	/**
5591	* @brief Return the minimum element in a range using comparison functor.
5592	* @ingroup sorting_algorithms
5593	* @param __first Start of range.
5594	* @param __last End of range.
5595	* @param __comp Comparison functor.
5596	* @return Iterator referencing the first instance of the smallest value
5597	* according to __comp.
5598	*/
5599	template<typename _ForwardIterator, typename _Compare>
5600	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5601	inline _ForwardIterator
5602	min_element(_ForwardIterator __first, _ForwardIterator __last,
5603	_Compare __comp)
5604	{
5605	// concept requirements
5606	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5607	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5608	typename iterator_traits<_ForwardIterator>::value_type,
5609	typename iterator_traits<_ForwardIterator>::value_type>)
5610	__glibcxx_requires_valid_range(__first, __last);
5611	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5612
5613	return _GLIBCXX_STD_A::__min_element(__first, __last,
5614	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5615	}
5616
5617	template<typename _ForwardIterator, typename _Compare>
5618	_GLIBCXX14_CONSTEXPR
5619	_ForwardIterator
5620	__max_element(_ForwardIterator __first, _ForwardIterator __last,
5621	_Compare __comp)
5622	{
5623	if (__first == __last) return __first;
5624	_ForwardIterator __result = __first;
5625	while (++__first != __last)
5626	if (__comp(__result, __first))
5627	__result = __first;
5628	return __result;
5629	}
5630
5631	/**
5632	* @brief Return the maximum element in a range.
5633	* @ingroup sorting_algorithms
5634	* @param __first Start of range.
5635	* @param __last End of range.
5636	* @return Iterator referencing the first instance of the largest value.
5637	*/
5638	template<typename _ForwardIterator>
5639	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5640	inline _ForwardIterator
5641	max_element(_ForwardIterator __first, _ForwardIterator __last)
5642	{
5643	// concept requirements
5644	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5645	__glibcxx_function_requires(_LessThanComparableConcept<
5646	typename iterator_traits<_ForwardIterator>::value_type>)
5647	__glibcxx_requires_valid_range(__first, __last);
5648	__glibcxx_requires_irreflexive(__first, __last);
5649
5650	return _GLIBCXX_STD_A::__max_element(__first, __last,
5651	__gnu_cxx::__ops::__iter_less_iter());
5652	}
5653
5654	/**
5655	* @brief Return the maximum element in a range using comparison functor.
5656	* @ingroup sorting_algorithms
5657	* @param __first Start of range.
5658	* @param __last End of range.
5659	* @param __comp Comparison functor.
5660	* @return Iterator referencing the first instance of the largest value
5661	* according to __comp.
5662	*/
5663	template<typename _ForwardIterator, typename _Compare>
5664	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5665	inline _ForwardIterator
5666	max_element(_ForwardIterator __first, _ForwardIterator __last,
5667	_Compare __comp)
5668	{
5669	// concept requirements
5670	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5671	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5672	typename iterator_traits<_ForwardIterator>::value_type,
5673	typename iterator_traits<_ForwardIterator>::value_type>)
5674	__glibcxx_requires_valid_range(__first, __last);
5675	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5676
5677	return _GLIBCXX_STD_A::__max_element(__first, __last,
5678	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5679	}
5680
5681	#if __cplusplus >= 201103L
5682	// N2722 + DR 915.
5683	template<typename _Tp>
5684	_GLIBCXX14_CONSTEXPR
5685	inline _Tp
5686	min(initializer_list<_Tp> __l)
5687	{
5688	__glibcxx_requires_irreflexive(__l.begin(), __l.end());
5689	return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5690	__gnu_cxx::__ops::__iter_less_iter());
5691	}
5692
5693	template<typename _Tp, typename _Compare>
5694	_GLIBCXX14_CONSTEXPR
5695	inline _Tp
5696	min(initializer_list<_Tp> __l, _Compare __comp)
5697	{
5698	__glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5699	return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5700	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5701	}
5702
5703	template<typename _Tp>
5704	_GLIBCXX14_CONSTEXPR
5705	inline _Tp
5706	max(initializer_list<_Tp> __l)
5707	{
5708	__glibcxx_requires_irreflexive(__l.begin(), __l.end());
5709	return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5710	__gnu_cxx::__ops::__iter_less_iter());
5711	}
5712
5713	template<typename _Tp, typename _Compare>
5714	_GLIBCXX14_CONSTEXPR
5715	inline _Tp
5716	max(initializer_list<_Tp> __l, _Compare __comp)
5717	{
5718	__glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5719	return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5720	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5721	}
5722	#endif // C++11
5723
5724	#if __cplusplus >= 201402L
5725	/// Reservoir sampling algorithm.
5726	template<typename _InputIterator, typename _RandomAccessIterator,
5727	typename _Size, typename _UniformRandomBitGenerator>
5728	_RandomAccessIterator
5729	__sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
5730	_RandomAccessIterator __out, random_access_iterator_tag,
5731	_Size __n, _UniformRandomBitGenerator&& __g)
5732	{
5733	using __distrib_type = uniform_int_distribution<_Size>;
5734	using __param_type = typename __distrib_type::param_type;
5735	__distrib_type __d{};
5736	_Size __sample_sz = `0`;
5737	while (__first != __last && __sample_sz != __n)
5738	{
5739	__out[__sample_sz++] = *__first;
5740	++__first;
5741	}
5742	for (auto __pop_sz = __sample_sz; __first != __last;
5743	++__first, (void) ++__pop_sz)
5744	{
5745	const auto __k = __d(__g, __param_type{`0`, __pop_sz});
5746	if (__k < __n)
5747	__out[__k] = *__first;
5748	}
5749	return __out + __sample_sz;
5750	}
5751
5752	/// Selection sampling algorithm.
5753	template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5754	typename _Size, typename _UniformRandomBitGenerator>
5755	_OutputIterator
5756	__sample(_ForwardIterator __first, _ForwardIterator __last,
5757	forward_iterator_tag,
5758	_OutputIterator __out, _Cat,
5759	_Size __n, _UniformRandomBitGenerator&& __g)
5760	{
5761	using __distrib_type = uniform_int_distribution<_Size>;
5762	using __param_type = typename __distrib_type::param_type;
5763	using _USize = make_unsigned_t<_Size>;
5764	using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
5765	using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
5766
5767	if (__first == __last)
5768	return __out;
5769
5770	__distrib_type __d{};
5771	_Size __unsampled_sz = std::distance(__first, __last);
5772	__n = std::min(__n, __unsampled_sz);
5773
5774	// If possible, we use __gen_two_uniform_ints to efficiently produce
5775	// two random numbers using a single distribution invocation:
5776
5777	const __uc_type __urngrange = __g.max() - __g.min();
5778	if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5779	// I.e. (__urngrange >= __unsampled_sz __unsampled_sz) but without*
5780	// wrapping issues.
5781	{
5782	while (__n != `0` && __unsampled_sz >= `2`)
5783	{
5784	const pair<_Size, _Size> __p =
5785	__gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - `1`, __g);
5786
5787	--__unsampled_sz;
5788	if (__p.first < __n)
5789	{
5790	__out++ = __first;
5791	--__n;
5792	}
5793
5794	++__first;
5795
5796	if (__n == `0`) break;
5797
5798	--__unsampled_sz;
5799	if (__p.second < __n)
5800	{
5801	__out++ = __first;
5802	--__n;
5803	}
5804
5805	++__first;
5806	}
5807	}
5808
5809	// The loop above is otherwise equivalent to this one-at-a-time version:
5810
5811	for (; __n != `0`; ++__first)
5812	if (__d(__g, __param_type{`0`, --__unsampled_sz}) < __n)
5813	{
5814	__out++ = __first;
5815	--__n;
5816	}
5817	return __out;
5818	}
5819	#endif // C++14
5820
5821	#ifdef __glibcxx_sample // C++ >= 17
5822	/// Take a random sample from a population.
5823	template<typename _PopulationIterator, typename _SampleIterator,
5824	typename _Distance, typename _UniformRandomBitGenerator>
5825	_SampleIterator
5826	sample(_PopulationIterator __first, _PopulationIterator __last,
5827	_SampleIterator __out, _Distance __n,
5828	_UniformRandomBitGenerator&& __g)
5829	{
5830	using __pop_cat = typename
5831	std::iterator_traits<_PopulationIterator>::iterator_category;
5832	using __samp_cat = typename
5833	std::iterator_traits<_SampleIterator>::iterator_category;
5834
5835	static_assert(
5836	__or_<is_convertible<__pop_cat, forward_iterator_tag>,
5837	is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5838	"output range must use a RandomAccessIterator when input range"
5839	" does not meet the ForwardIterator requirements");
5840
5841	static_assert(is_integral<_Distance>::value,
5842	"sample size must be an integer type");
5843
5844	typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5845	return _GLIBCXX_STD_A::
5846	__sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5847	std::forward<_UniformRandomBitGenerator>(__g));
5848	}
5849	#endif // __glibcxx_sample
5850
5851	_GLIBCXX_END_NAMESPACE_ALGO
5852	_GLIBCXX_END_NAMESPACE_VERSION
5853	} // namespace std
5854
5855	#endif /* _STL_ALGO_H */
5856

Browse the source code of include/c++/14.2.1/bits/stl_algo.h