stl_algo.h source code [include/c++/14/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	template<typename _ForwardIterator1, typename _ForwardIterator2,
3491	typename _BinaryPredicate>
3492	_GLIBCXX20_CONSTEXPR
3493	bool
3494	__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3495	_ForwardIterator2 __first2, _ForwardIterator2 __last2,
3496	_BinaryPredicate __pred)
3497	{
3498	using _Cat1
3499	= typename iterator_traits<_ForwardIterator1>::iterator_category;
3500	using _Cat2
3501	= typename iterator_traits<_ForwardIterator2>::iterator_category;
3502	using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3503	using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3504	constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3505	if (__ra_iters)
3506	{
3507	auto __d1 = std::distance(__first1, __last1);
3508	auto __d2 = std::distance(__first2, __last2);
3509	if (__d1 != __d2)
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 (__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
3552	/**
3553	* @brief Checks whether a permutaion of the second sequence is equal
3554	* to the first sequence.
3555	* @ingroup non_mutating_algorithms
3556	* @param __first1 Start of first range.
3557	* @param __last1 End of first range.
3558	* @param __first2 Start of second range.
3559	* @param __last2 End of first range.
3560	* @return true if there exists a permutation of the elements in the range
3561	* [__first2, __last2), beginning with ForwardIterator2 begin,
3562	* such that equal(__first1, __last1, begin) returns true;
3563	* otherwise, returns false.
3564	*/
3565	template<typename _ForwardIterator1, typename _ForwardIterator2>
3566	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3567	inline bool
3568	is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3569	_ForwardIterator2 __first2, _ForwardIterator2 __last2)
3570	{
3571	__glibcxx_requires_valid_range(__first1, __last1);
3572	__glibcxx_requires_valid_range(__first2, __last2);
3573
3574	return
3575	std::__is_permutation(__first1, __last1, __first2, __last2,
3576	__gnu_cxx::__ops::__iter_equal_to_iter());
3577	}
3578
3579	/**
3580	* @brief Checks whether a permutation of the second sequence is equal
3581	* to the first sequence.
3582	* @ingroup non_mutating_algorithms
3583	* @param __first1 Start of first range.
3584	* @param __last1 End of first range.
3585	* @param __first2 Start of second range.
3586	* @param __last2 End of first range.
3587	* @param __pred A binary predicate.
3588	* @return true if there exists a permutation of the elements in the range
3589	* [__first2, __last2), beginning with ForwardIterator2 begin,
3590	* such that equal(__first1, __last1, __begin, __pred) returns true;
3591	* otherwise, returns false.
3592	*/
3593	template<typename _ForwardIterator1, typename _ForwardIterator2,
3594	typename _BinaryPredicate>
3595	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3596	inline bool
3597	is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3598	_ForwardIterator2 __first2, _ForwardIterator2 __last2,
3599	_BinaryPredicate __pred)
3600	{
3601	__glibcxx_requires_valid_range(__first1, __last1);
3602	__glibcxx_requires_valid_range(__first2, __last2);
3603
3604	return std::__is_permutation(__first1, __last1, __first2, __last2,
3605	__gnu_cxx::__ops::__iter_comp_iter(__pred));
3606	}
3607	#endif // C++14
3608
3609	#ifdef __glibcxx_clamp // C++ >= 17
3610	/**
3611	* @brief Returns the value clamped between lo and hi.
3612	* @ingroup sorting_algorithms
3613	* @param __val A value of arbitrary type.
3614	* @param __lo A lower limit of arbitrary type.
3615	* @param __hi An upper limit of arbitrary type.
3616	* @retval `__lo` if `__val < __lo`
3617	* @retval `__hi` if `__hi < __val`
3618	* @retval `__val` otherwise.
3619	* @pre `_Tp` is LessThanComparable and `(__hi < __lo)` is false.
3620	*/
3621	template<typename _Tp>
3622	[[nodiscard]] constexpr const _Tp&
3623	clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
3624	{
3625	__glibcxx_assert(!(__hi < __lo));
3626	return std::min(std::max(__val, __lo), __hi);
3627	}
3628
3629	/**
3630	* @brief Returns the value clamped between lo and hi.
3631	* @ingroup sorting_algorithms
3632	* @param __val A value of arbitrary type.
3633	* @param __lo A lower limit of arbitrary type.
3634	* @param __hi An upper limit of arbitrary type.
3635	* @param __comp A comparison functor.
3636	* @retval `__lo` if `__comp(__val, __lo)`
3637	* @retval `__hi` if `__comp(__hi, __val)`
3638	* @retval `__val` otherwise.
3639	* @pre `__comp(__hi, __lo)` is false.
3640	*/
3641	template<typename _Tp, typename _Compare>
3642	[[nodiscard]] constexpr const _Tp&
3643	clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp)
3644	{
3645	__glibcxx_assert(!__comp(__hi, __lo));
3646	return std::min(std::max(__val, __lo, __comp), __hi, __comp);
3647	}
3648	#endif // __glibcxx_clamp
3649
3650	/**
3651	* @brief Generate two uniformly distributed integers using a
3652	* single distribution invocation.
3653	* @param __b0 The upper bound for the first integer.
3654	* @param __b1 The upper bound for the second integer.
3655	* @param __g A UniformRandomBitGenerator.
3656	* @return A pair (i, j) with i and j uniformly distributed
3657	* over [0, __b0) and [0, __b1), respectively.
3658	*
3659	* Requires: __b0 * __b1 <= __g.max() - __g.min().
3660	*
3661	* Using uniform_int_distribution with a range that is very
3662	* small relative to the range of the generator ends up wasting
3663	* potentially expensively generated randomness, since
3664	* uniform_int_distribution does not store leftover randomness
3665	* between invocations.
3666	*
3667	* If we know we want two integers in ranges that are sufficiently
3668	* small, we can compose the ranges, use a single distribution
3669	* invocation, and significantly reduce the waste.
3670	*/
3671	template<typename _IntType, typename _UniformRandomBitGenerator>
3672	pair<_IntType, _IntType>
3673	__gen_two_uniform_ints(_IntType __b0, _IntType __b1,
3674	_UniformRandomBitGenerator&& __g)
3675	{
3676	_IntType __x
3677	= uniform_int_distribution<_IntType>{`0`, (__b0 * __b1) - `1`}(__g);
3678	return std::make_pair(__x / __b1, __x % __b1);
3679	}
3680
3681	/**
3682	* @brief Shuffle the elements of a sequence using a uniform random
3683	* number generator.
3684	* @ingroup mutating_algorithms
3685	* @param __first A forward iterator.
3686	* @param __last A forward iterator.
3687	* @param __g A UniformRandomNumberGenerator (26.5.1.3).
3688	* @return Nothing.
3689	*
3690	* Reorders the elements in the range @p [__first,__last) using @p __g to
3691	* provide random numbers.
3692	*/
3693	template<typename _RandomAccessIterator,
3694	typename _UniformRandomNumberGenerator>
3695	void
3696	shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3697	_UniformRandomNumberGenerator&& __g)
3698	{
3699	// concept requirements
3700	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3701	_RandomAccessIterator>)
3702	__glibcxx_requires_valid_range(__first, __last);
3703
3704	if (__first == __last)
3705	return;
3706
3707	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3708	_DistanceType;
3709
3710	typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3711	typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
3712	typedef typename __distr_type::param_type __p_type;
3713
3714	typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3715	_Gen;
3716	typedef typename common_type<typename _Gen::result_type, __ud_type>::type
3717	__uc_type;
3718
3719	const __uc_type __urngrange = __g.max() - __g.min();
3720	const __uc_type __urange = __uc_type(__last - __first);
3721
3722	if (__urngrange / __urange >= __urange)
3723	// I.e. (__urngrange >= __urange __urange) but without wrap issues.*
3724	{
3725	_RandomAccessIterator __i = __first + `1`;
3726
3727	// Since we know the range isn't empty, an even number of elements
3728	// means an uneven number of elements /to swap/, in which case we
3729	// do the first one up front:
3730
3731	if ((__urange % `2`) == `0`)
3732	{
3733	__distr_type __d{`0`, `1`};
3734	std::iter_swap(__i++, __first + __d(__g));
3735	}
3736
3737	// Now we know that __last - __i is even, so we do the rest in pairs,
3738	// using a single distribution invocation to produce swap positions
3739	// for two successive elements at a time:
3740
3741	while (__i != __last)
3742	{
3743	const __uc_type __swap_range = __uc_type(__i - __first) + `1`;
3744
3745	const pair<__uc_type, __uc_type> __pospos =
3746	__gen_two_uniform_ints(__swap_range, __swap_range + `1`, __g);
3747
3748	std::iter_swap(__i++, __first + __pospos.first);
3749	std::iter_swap(__i++, __first + __pospos.second);
3750	}
3751
3752	return;
3753	}
3754
3755	__distr_type __d;
3756
3757	for (_RandomAccessIterator __i = __first + `1`; __i != __last; ++__i)
3758	std::iter_swap(__i, __first + __d(__g, __p_type(`0`, __i - __first)));
3759	}
3760	#endif // C++11
3761
3762	_GLIBCXX_BEGIN_NAMESPACE_ALGO
3763
3764	/**
3765	* @brief Apply a function to every element of a sequence.
3766	* @ingroup non_mutating_algorithms
3767	* @param __first An input iterator.
3768	* @param __last An input iterator.
3769	* @param __f A unary function object.
3770	* @return @p __f
3771	*
3772	* Applies the function object @p __f to each element in the range
3773	* @p [first,last). @p __f must not modify the order of the sequence.
3774	* If @p __f has a return value it is ignored.
3775	*/
3776	template<typename _InputIterator, typename _Function>
3777	_GLIBCXX20_CONSTEXPR
3778	_Function
3779	for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3780	{
3781	// concept requirements
3782	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3783	__glibcxx_requires_valid_range(__first, __last);
3784	for (; __first != __last; ++__first)
3785	__f(*__first);
3786	return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
3787	}
3788
3789	#if __cplusplus >= 201703L
3790	/**
3791	* @brief Apply a function to every element of a sequence.
3792	* @ingroup non_mutating_algorithms
3793	* @param __first An input iterator.
3794	* @param __n A value convertible to an integer.
3795	* @param __f A unary function object.
3796	* @return `__first+__n`
3797	*
3798	* Applies the function object `__f` to each element in the range
3799	* `[first, first+n)`. `__f` must not modify the order of the sequence.
3800	* If `__f` has a return value it is ignored.
3801	*/
3802	template<typename _InputIterator, typename _Size, typename _Function>
3803	_GLIBCXX20_CONSTEXPR
3804	_InputIterator
3805	for_each_n(_InputIterator __first, _Size __n, _Function __f)
3806	{
3807	auto __n2 = std::__size_to_integer(__n);
3808	using _Cat = typename iterator_traits<_InputIterator>::iterator_category;
3809	if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3810	{
3811	if (__n2 <= `0`)
3812	return __first;
3813	auto __last = __first + __n2;
3814	std::for_each(__first, __last, std::move(__f));
3815	return __last;
3816	}
3817	else
3818	{
3819	while (__n2-->`0`)
3820	{
3821	__f(*__first);
3822	++__first;
3823	}
3824	return __first;
3825	}
3826	}
3827	#endif // C++17
3828
3829	/**
3830	* @brief Find the first occurrence of a value in a sequence.
3831	* @ingroup non_mutating_algorithms
3832	* @param __first An input iterator.
3833	* @param __last An input iterator.
3834	* @param __val The value to find.
3835	* @return The first iterator @c i in the range @p [__first,__last)
3836	* such that @c *i == @p __val, or @p __last if no such iterator exists.
3837	*/
3838	template<typename _InputIterator, typename _Tp>
3839	_GLIBCXX20_CONSTEXPR
3840	inline _InputIterator
3841	find(_InputIterator __first, _InputIterator __last,
3842	const _Tp& __val)
3843	{
3844	// concept requirements
3845	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3846	__glibcxx_function_requires(_EqualOpConcept<
3847	typename iterator_traits<_InputIterator>::value_type, _Tp>)
3848	__glibcxx_requires_valid_range(__first, __last);
3849	return std::__find_if(__first, __last,
3850	__gnu_cxx::__ops::__iter_equals_val(__val));
3851	}
3852
3853	/**
3854	* @brief Find the first element in a sequence for which a
3855	* predicate is true.
3856	* @ingroup non_mutating_algorithms
3857	* @param __first An input iterator.
3858	* @param __last An input iterator.
3859	* @param __pred A predicate.
3860	* @return The first iterator @c i in the range @p [__first,__last)
3861	* such that @p __pred(*i) is true, or @p __last if no such iterator exists.
3862	*/
3863	template<typename _InputIterator, typename _Predicate>
3864	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3865	inline _InputIterator
3866	find_if(_InputIterator __first, _InputIterator __last,
3867	_Predicate __pred)
3868	{
3869	// concept requirements
3870	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3871	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3872	typename iterator_traits<_InputIterator>::value_type>)
3873	__glibcxx_requires_valid_range(__first, __last);
3874
3875	return std::__find_if(__first, __last,
3876	__gnu_cxx::__ops::__pred_iter(__pred));
3877	}
3878
3879	/**
3880	* @brief Find element from a set in a sequence.
3881	* @ingroup non_mutating_algorithms
3882	* @param __first1 Start of range to search.
3883	* @param __last1 End of range to search.
3884	* @param __first2 Start of match candidates.
3885	* @param __last2 End of match candidates.
3886	* @return The first iterator @c i in the range
3887	* @p [__first1,__last1) such that @c i == @p (i2) such that i2 is an
3888	* iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
3889	*
3890	* Searches the range @p [__first1,__last1) for an element that is
3891	* equal to some element in the range [__first2,__last2). If
3892	* found, returns an iterator in the range [__first1,__last1),
3893	* otherwise returns @p __last1.
3894	*/
3895	template<typename _InputIterator, typename _ForwardIterator>
3896	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3897	_InputIterator
3898	find_first_of(_InputIterator __first1, _InputIterator __last1,
3899	_ForwardIterator __first2, _ForwardIterator __last2)
3900	{
3901	// concept requirements
3902	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3903	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3904	__glibcxx_function_requires(_EqualOpConcept<
3905	typename iterator_traits<_InputIterator>::value_type,
3906	typename iterator_traits<_ForwardIterator>::value_type>)
3907	__glibcxx_requires_valid_range(__first1, __last1);
3908	__glibcxx_requires_valid_range(__first2, __last2);
3909
3910	for (; __first1 != __last1; ++__first1)
3911	for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3912	if (__first1 == __iter)
3913	return __first1;
3914	return __last1;
3915	}
3916
3917	/**
3918	* @brief Find element from a set in a sequence using a predicate.
3919	* @ingroup non_mutating_algorithms
3920	* @param __first1 Start of range to search.
3921	* @param __last1 End of range to search.
3922	* @param __first2 Start of match candidates.
3923	* @param __last2 End of match candidates.
3924	* @param __comp Predicate to use.
3925	* @return The first iterator @c i in the range
3926	* @p [__first1,__last1) such that @c comp(i, @p (i2)) is true
3927	* and i2 is an iterator in [__first2,__last2), or @p __last1 if no
3928	* such iterator exists.
3929	*
3930
3931	* Searches the range @p [__first1,__last1) for an element that is
3932	* equal to some element in the range [__first2,__last2). If
3933	* found, returns an iterator in the range [__first1,__last1),
3934	* otherwise returns @p __last1.
3935	*/
3936	template<typename _InputIterator, typename _ForwardIterator,
3937	typename _BinaryPredicate>
3938	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3939	_InputIterator
3940	find_first_of(_InputIterator __first1, _InputIterator __last1,
3941	_ForwardIterator __first2, _ForwardIterator __last2,
3942	_BinaryPredicate __comp)
3943	{
3944	// concept requirements
3945	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3946	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3947	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3948	typename iterator_traits<_InputIterator>::value_type,
3949	typename iterator_traits<_ForwardIterator>::value_type>)
3950	__glibcxx_requires_valid_range(__first1, __last1);
3951	__glibcxx_requires_valid_range(__first2, __last2);
3952
3953	for (; __first1 != __last1; ++__first1)
3954	for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3955	if (__comp(__first1, __iter))
3956	return __first1;
3957	return __last1;
3958	}
3959
3960	/**
3961	* @brief Find two adjacent values in a sequence that are equal.
3962	* @ingroup non_mutating_algorithms
3963	* @param __first A forward iterator.
3964	* @param __last A forward iterator.
3965	* @return The first iterator @c i such that @c i and @c i+1 are both
3966	* valid iterators in @p [__first,__last) and such that @c i == @c (i+1),
3967	* or @p __last if no such iterator exists.
3968	*/
3969	template<typename _ForwardIterator>
3970	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3971	inline _ForwardIterator
3972	adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3973	{
3974	// concept requirements
3975	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3976	__glibcxx_function_requires(_EqualityComparableConcept<
3977	typename iterator_traits<_ForwardIterator>::value_type>)
3978	__glibcxx_requires_valid_range(__first, __last);
3979
3980	return std::__adjacent_find(__first, __last,
3981	__gnu_cxx::__ops::__iter_equal_to_iter());
3982	}
3983
3984	/**
3985	* @brief Find two adjacent values in a sequence using a predicate.
3986	* @ingroup non_mutating_algorithms
3987	* @param __first A forward iterator.
3988	* @param __last A forward iterator.
3989	* @param __binary_pred A binary predicate.
3990	* @return The first iterator @c i such that @c i and @c i+1 are both
3991	* valid iterators in @p [__first,__last) and such that
3992	* @p __binary_pred(i,(i+1)) is true, or @p __last if no such iterator
3993	* exists.
3994	*/
3995	template<typename _ForwardIterator, typename _BinaryPredicate>
3996	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
3997	inline _ForwardIterator
3998	adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
3999	_BinaryPredicate __binary_pred)
4000	{
4001	// concept requirements
4002	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4003	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4004	typename iterator_traits<_ForwardIterator>::value_type,
4005	typename iterator_traits<_ForwardIterator>::value_type>)
4006	__glibcxx_requires_valid_range(__first, __last);
4007
4008	return std::__adjacent_find(__first, __last,
4009	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4010	}
4011
4012	/**
4013	* @brief Count the number of copies of a value in a sequence.
4014	* @ingroup non_mutating_algorithms
4015	* @param __first An input iterator.
4016	* @param __last An input iterator.
4017	* @param __value The value to be counted.
4018	* @return The number of iterators @c i in the range @p [__first,__last)
4019	* for which @c *i == @p __value
4020	*/
4021	template<typename _InputIterator, typename _Tp>
4022	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4023	inline typename iterator_traits<_InputIterator>::difference_type
4024	count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4025	{
4026	// concept requirements
4027	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4028	__glibcxx_function_requires(_EqualOpConcept<
4029	typename iterator_traits<_InputIterator>::value_type, _Tp>)
4030	__glibcxx_requires_valid_range(__first, __last);
4031
4032	return std::__count_if(__first, __last,
4033	__gnu_cxx::__ops::__iter_equals_val(__value));
4034	}
4035
4036	/**
4037	* @brief Count the elements of a sequence for which a predicate is true.
4038	* @ingroup non_mutating_algorithms
4039	* @param __first An input iterator.
4040	* @param __last An input iterator.
4041	* @param __pred A predicate.
4042	* @return The number of iterators @c i in the range @p [__first,__last)
4043	* for which @p __pred(*i) is true.
4044	*/
4045	template<typename _InputIterator, typename _Predicate>
4046	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4047	inline typename iterator_traits<_InputIterator>::difference_type
4048	count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4049	{
4050	// concept requirements
4051	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4052	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4053	typename iterator_traits<_InputIterator>::value_type>)
4054	__glibcxx_requires_valid_range(__first, __last);
4055
4056	return std::__count_if(__first, __last,
4057	__gnu_cxx::__ops::__pred_iter(__pred));
4058	}
4059
4060	/**
4061	* @brief Search a sequence for a matching sub-sequence.
4062	* @ingroup non_mutating_algorithms
4063	* @param __first1 A forward iterator.
4064	* @param __last1 A forward iterator.
4065	* @param __first2 A forward iterator.
4066	* @param __last2 A forward iterator.
4067	* @return The first iterator @c i in the range @p
4068	* [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4069	* *(__first2+N) for each @c N in the range @p
4070	* [0,__last2-__first2), or @p __last1 if no such iterator exists.
4071	*
4072	* Searches the range @p [__first1,__last1) for a sub-sequence that
4073	* compares equal value-by-value with the sequence given by @p
4074	* [__first2,__last2) and returns an iterator to the first element
4075	* of the sub-sequence, or @p __last1 if the sub-sequence is not
4076	* found.
4077	*
4078	* Because the sub-sequence must lie completely within the range @p
4079	* [__first1,__last1) it must start at a position less than @p
4080	* __last1-(__last2-__first2) where @p __last2-__first2 is the
4081	* length of the sub-sequence.
4082	*
4083	* This means that the returned iterator @c i will be in the range
4084	* @p [__first1,__last1-(__last2-__first2))
4085	*/
4086	template<typename _ForwardIterator1, typename _ForwardIterator2>
4087	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4088	inline _ForwardIterator1
4089	search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4090	_ForwardIterator2 __first2, _ForwardIterator2 __last2)
4091	{
4092	// concept requirements
4093	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4094	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4095	__glibcxx_function_requires(_EqualOpConcept<
4096	typename iterator_traits<_ForwardIterator1>::value_type,
4097	typename iterator_traits<_ForwardIterator2>::value_type>)
4098	__glibcxx_requires_valid_range(__first1, __last1);
4099	__glibcxx_requires_valid_range(__first2, __last2);
4100
4101	return std::__search(__first1, __last1, __first2, __last2,
4102	__gnu_cxx::__ops::__iter_equal_to_iter());
4103	}
4104
4105	/**
4106	* @brief Search a sequence for a number of consecutive values.
4107	* @ingroup non_mutating_algorithms
4108	* @param __first A forward iterator.
4109	* @param __last A forward iterator.
4110	* @param __count The number of consecutive values.
4111	* @param __val The value to find.
4112	* @return The first iterator @c i in the range @p
4113	* [__first,__last-__count) such that @c *(i+N) == @p __val for
4114	* each @c N in the range @p [0,__count), or @p __last if no such
4115	* iterator exists.
4116	*
4117	* Searches the range @p [__first,__last) for @p count consecutive elements
4118	* equal to @p __val.
4119	*/
4120	template<typename _ForwardIterator, typename _Integer, typename _Tp>
4121	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4122	inline _ForwardIterator
4123	search_n(_ForwardIterator __first, _ForwardIterator __last,
4124	_Integer __count, const _Tp& __val)
4125	{
4126	// concept requirements
4127	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4128	__glibcxx_function_requires(_EqualOpConcept<
4129	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4130	__glibcxx_requires_valid_range(__first, __last);
4131
4132	return std::__search_n(__first, __last, __count,
4133	__gnu_cxx::__ops::__iter_equals_val(__val));
4134	}
4135
4136
4137	/**
4138	* @brief Search a sequence for a number of consecutive values using a
4139	* predicate.
4140	* @ingroup non_mutating_algorithms
4141	* @param __first A forward iterator.
4142	* @param __last A forward iterator.
4143	* @param __count The number of consecutive values.
4144	* @param __val The value to find.
4145	* @param __binary_pred A binary predicate.
4146	* @return The first iterator @c i in the range @p
4147	* [__first,__last-__count) such that @p
4148	* __binary_pred(*(i+N),__val) is true for each @c N in the range
4149	* @p [0,__count), or @p __last if no such iterator exists.
4150	*
4151	* Searches the range @p [__first,__last) for @p __count
4152	* consecutive elements for which the predicate returns true.
4153	*/
4154	template<typename _ForwardIterator, typename _Integer, typename _Tp,
4155	typename _BinaryPredicate>
4156	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4157	inline _ForwardIterator
4158	search_n(_ForwardIterator __first, _ForwardIterator __last,
4159	_Integer __count, const _Tp& __val,
4160	_BinaryPredicate __binary_pred)
4161	{
4162	// concept requirements
4163	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4164	__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4165	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4166	__glibcxx_requires_valid_range(__first, __last);
4167
4168	return std::__search_n(__first, __last, __count,
4169	__gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4170	}
4171
4172	#if __cplusplus >= 201703L
4173	/* @brief Search a sequence using a Searcher object.*
4174	*
4175	* @param __first A forward iterator.
4176	* @param __last A forward iterator.
4177	* @param __searcher A callable object.
4178	* @return @p __searcher(__first,__last).first
4179	*/
4180	template<typename _ForwardIterator, typename _Searcher>
4181	_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
4182	inline _ForwardIterator
4183	search(_ForwardIterator __first, _ForwardIterator __last,
4184	const _Searcher& __searcher)
4185	{ return __searcher(__first, __last).first; }
4186	#endif
4187
4188	/**
4189	* @brief Perform an operation on a sequence.
4190	* @ingroup mutating_algorithms
4191	* @param __first An input iterator.
4192	* @param __last An input iterator.
4193	* @param __result An output iterator.
4194	* @param __unary_op A unary operator.
4195	* @return An output iterator equal to @p __result+(__last-__first).
4196	*
4197	* Applies the operator to each element in the input range and assigns
4198	* the results to successive elements of the output sequence.
4199	* Evaluates @p (__result+N)=unary_op((__first+N)) for each @c N in the
4200	* range @p [0,__last-__first).
4201	*
4202	* @p unary_op must not alter its argument.
4203	*/
4204	template<typename _InputIterator, typename _OutputIterator,
4205	typename _UnaryOperation>
4206	_GLIBCXX20_CONSTEXPR
4207	_OutputIterator
4208	transform(_InputIterator __first, _InputIterator __last,
4209	_OutputIterator __result, _UnaryOperation __unary_op)
4210	{
4211	// concept requirements
4212	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4213	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4214	// "the type returned by a _UnaryOperation"
4215	__typeof__(__unary_op(*__first))>)
4216	__glibcxx_requires_valid_range(__first, __last);
4217
4218	for (; __first != __last; ++__first, (void)++__result)
4219	__result = __unary_op(__first);
4220	return __result;
4221	}
4222
4223	/**
4224	* @brief Perform an operation on corresponding elements of two sequences.
4225	* @ingroup mutating_algorithms
4226	* @param __first1 An input iterator.
4227	* @param __last1 An input iterator.
4228	* @param __first2 An input iterator.
4229	* @param __result An output iterator.
4230	* @param __binary_op A binary operator.
4231	* @return An output iterator equal to @p result+(last-first).
4232	*
4233	* Applies the operator to the corresponding elements in the two
4234	* input ranges and assigns the results to successive elements of the
4235	* output sequence.
4236	* Evaluates @p
4237	* (__result+N)=__binary_op((__first1+N),*(__first2+N)) for each
4238	* @c N in the range @p [0,__last1-__first1).
4239	*
4240	* @p binary_op must not alter either of its arguments.
4241	*/
4242	template<typename _InputIterator1, typename _InputIterator2,
4243	typename _OutputIterator, typename _BinaryOperation>
4244	_GLIBCXX20_CONSTEXPR
4245	_OutputIterator
4246	transform(_InputIterator1 __first1, _InputIterator1 __last1,
4247	_InputIterator2 __first2, _OutputIterator __result,
4248	_BinaryOperation __binary_op)
4249	{
4250	// concept requirements
4251	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4252	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4253	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4254	// "the type returned by a _BinaryOperation"
4255	__typeof__(__binary_op(__first1,__first2))>)
4256	__glibcxx_requires_valid_range(__first1, __last1);
4257
4258	for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4259	__result = __binary_op(__first1, *__first2);
4260	return __result;
4261	}
4262
4263	/**
4264	* @brief Replace each occurrence of one value in a sequence with another
4265	* value.
4266	* @ingroup mutating_algorithms
4267	* @param __first A forward iterator.
4268	* @param __last A forward iterator.
4269	* @param __old_value The value to be replaced.
4270	* @param __new_value The replacement value.
4271	* @return replace() returns no value.
4272	*
4273	* For each iterator `i` in the range `[__first,__last)` if
4274	* `i == __old_value` then the assignment `i = __new_value` is performed.
4275	*/
4276	template<typename _ForwardIterator, typename _Tp>
4277	_GLIBCXX20_CONSTEXPR
4278	void
4279	replace(_ForwardIterator __first, _ForwardIterator __last,
4280	const _Tp& __old_value, const _Tp& __new_value)
4281	{
4282	// concept requirements
4283	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4284	_ForwardIterator>)
4285	__glibcxx_function_requires(_EqualOpConcept<
4286	typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4287	__glibcxx_function_requires(_ConvertibleConcept<_Tp,
4288	typename iterator_traits<_ForwardIterator>::value_type>)
4289	__glibcxx_requires_valid_range(__first, __last);
4290
4291	for (; __first != __last; ++__first)
4292	if (*__first == __old_value)
4293	*__first = __new_value;
4294	}
4295
4296	/**
4297	* @brief Replace each value in a sequence for which a predicate returns
4298	* true with another value.
4299	* @ingroup mutating_algorithms
4300	* @param __first A forward iterator.
4301	* @param __last A forward iterator.
4302	* @param __pred A predicate.
4303	* @param __new_value The replacement value.
4304	* @return replace_if() returns no value.
4305	*
4306	* For each iterator `i` in the range `[__first,__last)` if `__pred(*i)`
4307	* is true then the assignment `*i = __new_value` is performed.
4308	*/
4309	template<typename _ForwardIterator, typename _Predicate, typename _Tp>
4310	_GLIBCXX20_CONSTEXPR
4311	void
4312	replace_if(_ForwardIterator __first, _ForwardIterator __last,
4313	_Predicate __pred, const _Tp& __new_value)
4314	{
4315	// concept requirements
4316	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4317	_ForwardIterator>)
4318	__glibcxx_function_requires(_ConvertibleConcept<_Tp,
4319	typename iterator_traits<_ForwardIterator>::value_type>)
4320	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4321	typename iterator_traits<_ForwardIterator>::value_type>)
4322	__glibcxx_requires_valid_range(__first, __last);
4323
4324	for (; __first != __last; ++__first)
4325	if (__pred(*__first))
4326	*__first = __new_value;
4327	}
4328
4329	/**
4330	* @brief Assign the result of a function object to each value in a
4331	* sequence.
4332	* @ingroup mutating_algorithms
4333	* @param __first A forward iterator.
4334	* @param __last A forward iterator.
4335	* @param __gen A function object callable with no arguments.
4336	* @return generate() returns no value.
4337	*
4338	* Performs the assignment `*i = __gen()` for each `i` in the range
4339	* `[__first, __last)`.
4340	*/
4341	template<typename _ForwardIterator, typename _Generator>
4342	_GLIBCXX20_CONSTEXPR
4343	void
4344	generate(_ForwardIterator __first, _ForwardIterator __last,
4345	_Generator __gen)
4346	{
4347	// concept requirements
4348	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4349	__glibcxx_function_requires(_GeneratorConcept<_Generator,
4350	typename iterator_traits<_ForwardIterator>::value_type>)
4351	__glibcxx_requires_valid_range(__first, __last);
4352
4353	for (; __first != __last; ++__first)
4354	*__first = __gen();
4355	}
4356
4357	/**
4358	* @brief Assign the result of a function object to each value in a
4359	* sequence.
4360	* @ingroup mutating_algorithms
4361	* @param __first A forward iterator.
4362	* @param __n The length of the sequence.
4363	* @param __gen A function object callable with no arguments.
4364	* @return The end of the sequence, i.e., `__first + __n`
4365	*
4366	* Performs the assignment `*i = __gen()` for each `i` in the range
4367	* `[__first, __first + __n)`.
4368	*
4369	* If `__n` is negative, the function does nothing and returns `__first`.
4370	*/
4371	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4372	// DR 865. More algorithms that throw away information
4373	// DR 426. search_n(), fill_n(), and generate_n() with negative n
4374	template<typename _OutputIterator, typename _Size, typename _Generator>
4375	_GLIBCXX20_CONSTEXPR
4376	_OutputIterator
4377	generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4378	{
4379	// concept requirements
4380	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4381	// "the type returned by a _Generator"
4382	__typeof__(__gen())>)
4383
4384	typedef __decltype(std::__size_to_integer(__n)) _IntSize;
4385	for (_IntSize __niter = std::__size_to_integer(__n);
4386	__niter > `0`; --__niter, (void) ++__first)
4387	*__first = __gen();
4388	return __first;
4389	}
4390
4391	/**
4392	* @brief Copy a sequence, removing consecutive duplicate values.
4393	* @ingroup mutating_algorithms
4394	* @param __first An input iterator.
4395	* @param __last An input iterator.
4396	* @param __result An output iterator.
4397	* @return An iterator designating the end of the resulting sequence.
4398	*
4399	* Copies each element in the range `[__first, __last)` to the range
4400	* beginning at `__result`, except that only the first element is copied
4401	* from groups of consecutive elements that compare equal.
4402	* `unique_copy()` is stable, so the relative order of elements that are
4403	* copied is unchanged.
4404	*/
4405	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4406	// DR 241. Does unique_copy() require CopyConstructible and Assignable?
4407	// DR 538. 241 again: Does unique_copy() require CopyConstructible and
4408	// Assignable?
4409	template<typename _InputIterator, typename _OutputIterator>
4410	_GLIBCXX20_CONSTEXPR
4411	inline _OutputIterator
4412	unique_copy(_InputIterator __first, _InputIterator __last,
4413	_OutputIterator __result)
4414	{
4415	// concept requirements
4416	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4417	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4418	typename iterator_traits<_InputIterator>::value_type>)
4419	__glibcxx_function_requires(_EqualityComparableConcept<
4420	typename iterator_traits<_InputIterator>::value_type>)
4421	__glibcxx_requires_valid_range(__first, __last);
4422
4423	if (__first == __last)
4424	return __result;
4425	return std::__unique_copy(__first, __last, __result,
4426	__gnu_cxx::__ops::__iter_equal_to_iter(),
4427	std::__iterator_category(__first),
4428	std::__iterator_category(__result));
4429	}
4430
4431	/**
4432	* @brief Copy a sequence, removing consecutive values using a predicate.
4433	* @ingroup mutating_algorithms
4434	* @param __first An input iterator.
4435	* @param __last An input iterator.
4436	* @param __result An output iterator.
4437	* @param __binary_pred A binary predicate.
4438	* @return An iterator designating the end of the resulting sequence.
4439	*
4440	* Copies each element in the range `[__first, __last)` to the range
4441	* beginning at `__result`, except that only the first element is copied
4442	* from groups of consecutive elements for which `__binary_pred` returns
4443	* true.
4444	* `unique_copy()` is stable, so the relative order of elements that are
4445	* copied is unchanged.
4446	*/
4447	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4448	// DR 241. Does unique_copy() require CopyConstructible and Assignable?
4449	template<typename _InputIterator, typename _OutputIterator,
4450	typename _BinaryPredicate>
4451	_GLIBCXX20_CONSTEXPR
4452	inline _OutputIterator
4453	unique_copy(_InputIterator __first, _InputIterator __last,
4454	_OutputIterator __result,
4455	_BinaryPredicate __binary_pred)
4456	{
4457	// concept requirements -- predicates checked later
4458	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4459	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4460	typename iterator_traits<_InputIterator>::value_type>)
4461	__glibcxx_requires_valid_range(__first, __last);
4462
4463	if (__first == __last)
4464	return __result;
4465	return std::__unique_copy(__first, __last, __result,
4466	__gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4467	std::__iterator_category(__first),
4468	std::__iterator_category(__result));
4469	}
4470
4471	#if __cplusplus <= 201103L \|\| _GLIBCXX_USE_DEPRECATED
4472	#if _GLIBCXX_HOSTED
4473	/**
4474	* @brief Randomly shuffle the elements of a sequence.
4475	* @ingroup mutating_algorithms
4476	* @param __first A forward iterator.
4477	* @param __last A forward iterator.
4478	* @return Nothing.
4479	*
4480	* Reorder the elements in the range `[__first, __last)` using a random
4481	* distribution, so that every possible ordering of the sequence is
4482	* equally likely.
4483	*
4484	* @deprecated
4485	* Since C++17, `std::random_shuffle` is not part of the C++ standard.
4486	* Use `std::shuffle` instead, which was introduced in C++11.
4487	*/
4488	template<typename _RandomAccessIterator>
4489	_GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4490	inline void
4491	random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4492	{
4493	// concept requirements
4494	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4495	_RandomAccessIterator>)
4496	__glibcxx_requires_valid_range(__first, __last);
4497
4498	if (__first != __last)
4499	for (_RandomAccessIterator __i = __first + `1`; __i != __last; ++__i)
4500	{
4501	// XXX rand() % N is not uniformly distributed
4502	_RandomAccessIterator __j = __first
4503	+ std::rand() % ((__i - __first) + `1`);
4504	if (__i != __j)
4505	std::iter_swap(__i, __j);
4506	}
4507	}
4508
4509	/**
4510	* @brief Shuffle the elements of a sequence using a random number
4511	* generator.
4512	* @ingroup mutating_algorithms
4513	* @param __first A forward iterator.
4514	* @param __last A forward iterator.
4515	* @param __rand The RNG functor or function.
4516	* @return Nothing.
4517	*
4518	* Reorders the elements in the range `[__first, __last)` using `__rand`
4519	* to provide a random distribution. Calling `__rand(N)` for a positive
4520	* integer `N` should return a randomly chosen integer from the
4521	* range `[0, N)`.
4522	*
4523	* @deprecated
4524	* Since C++17, `std::random_shuffle` is not part of the C++ standard.
4525	* Use `std::shuffle` instead, which was introduced in C++11.
4526	*/
4527	template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
4528	_GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle")
4529	void
4530	random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4531	#if __cplusplus >= 201103L
4532	_RandomNumberGenerator&& __rand)
4533	#else
4534	_RandomNumberGenerator& __rand)
4535	#endif
4536	{
4537	// concept requirements
4538	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4539	_RandomAccessIterator>)
4540	__glibcxx_requires_valid_range(__first, __last);
4541
4542	if (__first == __last)
4543	return;
4544	for (_RandomAccessIterator __i = __first + `1`; __i != __last; ++__i)
4545	{
4546	_RandomAccessIterator __j = __first + __rand((__i - __first) + `1`);
4547	if (__i != __j)
4548	std::iter_swap(__i, __j);
4549	}
4550	}
4551	#endif // HOSTED
4552	#endif // <= C++11 \|\| USE_DEPRECATED
4553
4554	/**
4555	* @brief Move elements for which a predicate is true to the beginning
4556	* of a sequence.
4557	* @ingroup mutating_algorithms
4558	* @param __first A forward iterator.
4559	* @param __last A forward iterator.
4560	* @param __pred A predicate functor.
4561	* @return An iterator `middle` such that `__pred(i)` is true for each
4562	* iterator `i` in the range `[__first, middle)` and false for each `i`
4563	* in the range `[middle, __last)`.
4564	*
4565	* `__pred` must not modify its operand. `partition()` does not preserve
4566	* the relative ordering of elements in each group, use
4567	* `stable_partition()` if this is needed.
4568	*/
4569	template<typename _ForwardIterator, typename _Predicate>
4570	_GLIBCXX20_CONSTEXPR
4571	inline _ForwardIterator
4572	partition(_ForwardIterator __first, _ForwardIterator __last,
4573	_Predicate __pred)
4574	{
4575	// concept requirements
4576	__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4577	_ForwardIterator>)
4578	__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4579	typename iterator_traits<_ForwardIterator>::value_type>)
4580	__glibcxx_requires_valid_range(__first, __last);
4581
4582	return std::__partition(__first, __last, __pred,
4583	std::__iterator_category(__first));
4584	}
4585
4586
4587	/**
4588	* @brief Sort the smallest elements of a sequence.
4589	* @ingroup sorting_algorithms
4590	* @param __first An iterator.
4591	* @param __middle Another iterator.
4592	* @param __last Another iterator.
4593	* @return Nothing.
4594	*
4595	* Sorts the smallest `(__middle - __first)` elements in the range
4596	* `[first, last)` and moves them to the range `[__first, __middle)`. The
4597	* order of the remaining elements in the range `[__middle, __last)` is
4598	* unspecified.
4599	* After the sort if `i` and `j` are iterators in the range
4600	* `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4601	* in the range `[__middle, __last)` then `j < i` and `k < i` are
4602	* both false.
4603	*/
4604	template<typename _RandomAccessIterator>
4605	_GLIBCXX20_CONSTEXPR
4606	inline void
4607	partial_sort(_RandomAccessIterator __first,
4608	_RandomAccessIterator __middle,
4609	_RandomAccessIterator __last)
4610	{
4611	// concept requirements
4612	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4613	_RandomAccessIterator>)
4614	__glibcxx_function_requires(_LessThanComparableConcept<
4615	typename iterator_traits<_RandomAccessIterator>::value_type>)
4616	__glibcxx_requires_valid_range(__first, __middle);
4617	__glibcxx_requires_valid_range(__middle, __last);
4618	__glibcxx_requires_irreflexive(__first, __last);
4619
4620	std::__partial_sort(__first, __middle, __last,
4621	__gnu_cxx::__ops::__iter_less_iter());
4622	}
4623
4624	/**
4625	* @brief Sort the smallest elements of a sequence using a predicate
4626	* for comparison.
4627	* @ingroup sorting_algorithms
4628	* @param __first An iterator.
4629	* @param __middle Another iterator.
4630	* @param __last Another iterator.
4631	* @param __comp A comparison functor.
4632	* @return Nothing.
4633	*
4634	* Sorts the smallest `(__middle - __first)` elements in the range
4635	* `[__first, __last)` and moves them to the range `[__first, __middle)`.
4636	* The order of the remaining elements in the range `[__middle, __last)` is
4637	* unspecified.
4638	* After the sort if `i` and `j` are iterators in the range
4639	* `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator
4640	* in the range `[__middle, __last)` then `__comp(j, i)` and
4641	* `__comp(k, i)` are both false.
4642	*/
4643	template<typename _RandomAccessIterator, typename _Compare>
4644	_GLIBCXX20_CONSTEXPR
4645	inline void
4646	partial_sort(_RandomAccessIterator __first,
4647	_RandomAccessIterator __middle,
4648	_RandomAccessIterator __last,
4649	_Compare __comp)
4650	{
4651	// concept requirements
4652	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4653	_RandomAccessIterator>)
4654	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4655	typename iterator_traits<_RandomAccessIterator>::value_type,
4656	typename iterator_traits<_RandomAccessIterator>::value_type>)
4657	__glibcxx_requires_valid_range(__first, __middle);
4658	__glibcxx_requires_valid_range(__middle, __last);
4659	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4660
4661	std::__partial_sort(__first, __middle, __last,
4662	__gnu_cxx::__ops::__iter_comp_iter(__comp));
4663	}
4664
4665	/**
4666	* @brief Sort a sequence just enough to find a particular position.
4667	* @ingroup sorting_algorithms
4668	* @param __first An iterator.
4669	* @param __nth Another iterator.
4670	* @param __last Another iterator.
4671	* @return Nothing.
4672	*
4673	* Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4674	* is the same element that would have been in that position had the
4675	* whole sequence been sorted. The elements either side of `*__nth` are
4676	* not completely sorted, but for any iterator `i` in the range
4677	* `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)` it
4678	* holds that `j < i` is false.
4679	*/
4680	template<typename _RandomAccessIterator>
4681	_GLIBCXX20_CONSTEXPR
4682	inline void
4683	nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4684	_RandomAccessIterator __last)
4685	{
4686	// concept requirements
4687	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4688	_RandomAccessIterator>)
4689	__glibcxx_function_requires(_LessThanComparableConcept<
4690	typename iterator_traits<_RandomAccessIterator>::value_type>)
4691	__glibcxx_requires_valid_range(__first, __nth);
4692	__glibcxx_requires_valid_range(__nth, __last);
4693	__glibcxx_requires_irreflexive(__first, __last);
4694
4695	if (__first == __last \|\| __nth == __last)
4696	return;
4697
4698	std::__introselect(__first, __nth, __last,
4699	std::__lg(__last - __first) * `2`,
4700	__gnu_cxx::__ops::__iter_less_iter());
4701	}
4702
4703	/**
4704	* @brief Sort a sequence just enough to find a particular position
4705	* using a predicate for comparison.
4706	* @ingroup sorting_algorithms
4707	* @param __first An iterator.
4708	* @param __nth Another iterator.
4709	* @param __last Another iterator.
4710	* @param __comp A comparison functor.
4711	* @return Nothing.
4712	*
4713	* Rearranges the elements in the range `[__first, __last)` so that `*__nth`
4714	* is the same element that would have been in that position had the
4715	* whole sequence been sorted. The elements either side of `*__nth` are
4716	* not completely sorted, but for any iterator `i` in the range
4717	* `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)`
4718	* it holds that `__comp(j, i)` is false.
4719	*/
4720	template<typename _RandomAccessIterator, typename _Compare>
4721	_GLIBCXX20_CONSTEXPR
4722	inline void
4723	nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4724	_RandomAccessIterator __last, _Compare __comp)
4725	{
4726	// concept requirements
4727	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4728	_RandomAccessIterator>)
4729	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4730	typename iterator_traits<_RandomAccessIterator>::value_type,
4731	typename iterator_traits<_RandomAccessIterator>::value_type>)
4732	__glibcxx_requires_valid_range(__first, __nth);
4733	__glibcxx_requires_valid_range(__nth, __last);
4734	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4735
4736	if (__first == __last \|\| __nth == __last)
4737	return;
4738
4739	std::__introselect(__first, __nth, __last,
4740	std::__lg(__last - __first) * `2`,
4741	__gnu_cxx::__ops::__iter_comp_iter(__comp));
4742	}
4743
4744	/**
4745	* @brief Sort the elements of a sequence.
4746	* @ingroup sorting_algorithms
4747	* @param __first An iterator.
4748	* @param __last Another iterator.
4749	* @return Nothing.
4750	*
4751	* Sorts the elements in the range `[__first, __last)` in ascending order,
4752	* such that for each iterator `i` in the range `[__first, __last - 1)`,
4753	* `(i+1) < i` is false.
4754	*
4755	* The relative ordering of equivalent elements is not preserved, use
4756	* `stable_sort()` if this is needed.
4757	*/
4758	template<typename _RandomAccessIterator>
4759	_GLIBCXX20_CONSTEXPR
4760	inline void
4761	sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4762	{
4763	// concept requirements
4764	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4765	_RandomAccessIterator>)
4766	__glibcxx_function_requires(_LessThanComparableConcept<
4767	typename iterator_traits<_RandomAccessIterator>::value_type>)
4768	__glibcxx_requires_valid_range(__first, __last);
4769	__glibcxx_requires_irreflexive(__first, __last);
4770
4771	std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4772	}
4773
4774	/**
4775	* @brief Sort the elements of a sequence using a predicate for comparison.
4776	* @ingroup sorting_algorithms
4777	* @param __first An iterator.
4778	* @param __last Another iterator.
4779	* @param __comp A comparison functor.
4780	* @return Nothing.
4781	*
4782	* Sorts the elements in the range `[__first, __last)` in ascending order,
4783	* such that `__comp((i+1), i)` is false for every iterator `i` in the
4784	* range `[__first, __last - 1)`.
4785	*
4786	* The relative ordering of equivalent elements is not preserved, use
4787	* `stable_sort()` if this is needed.
4788	*/
4789	template<typename _RandomAccessIterator, typename _Compare>
4790	_GLIBCXX20_CONSTEXPR
4791	inline void
4792	sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4793	_Compare __comp)
4794	{
4795	// concept requirements
4796	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4797	_RandomAccessIterator>)
4798	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4799	typename iterator_traits<_RandomAccessIterator>::value_type,
4800	typename iterator_traits<_RandomAccessIterator>::value_type>)
4801	__glibcxx_requires_valid_range(__first, __last);
4802	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4803
4804	std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4805	}
4806
4807	template<typename _InputIterator1, typename _InputIterator2,
4808	typename _OutputIterator, typename _Compare>
4809	_GLIBCXX20_CONSTEXPR
4810	_OutputIterator
4811	__merge(_InputIterator1 __first1, _InputIterator1 __last1,
4812	_InputIterator2 __first2, _InputIterator2 __last2,
4813	_OutputIterator __result, _Compare __comp)
4814	{
4815	while (__first1 != __last1 && __first2 != __last2)
4816	{
4817	if (__comp(__first2, __first1))
4818	{
4819	__result = __first2;
4820	++__first2;
4821	}
4822	else
4823	{
4824	__result = __first1;
4825	++__first1;
4826	}
4827	++__result;
4828	}
4829	return std::copy(__first2, __last2,
4830	std::copy(__first1, __last1, __result));
4831	}
4832
4833	/**
4834	* @brief Merges two sorted ranges.
4835	* @ingroup sorting_algorithms
4836	* @param __first1 An iterator.
4837	* @param __first2 Another iterator.
4838	* @param __last1 Another iterator.
4839	* @param __last2 Another iterator.
4840	* @param __result An iterator pointing to the end of the merged range.
4841	* @return An output iterator equal to @p __result + (__last1 - __first1)
4842	* + (__last2 - __first2).
4843	*
4844	* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4845	* the sorted range @p [__result, __result + (__last1-__first1) +
4846	* (__last2-__first2)). Both input ranges must be sorted, and the
4847	* output range must not overlap with either of the input ranges.
4848	* The sort is @e stable, that is, for equivalent elements in the
4849	* two ranges, elements from the first range will always come
4850	* before elements from the second.
4851	*/
4852	template<typename _InputIterator1, typename _InputIterator2,
4853	typename _OutputIterator>
4854	_GLIBCXX20_CONSTEXPR
4855	inline _OutputIterator
4856	merge(_InputIterator1 __first1, _InputIterator1 __last1,
4857	_InputIterator2 __first2, _InputIterator2 __last2,
4858	_OutputIterator __result)
4859	{
4860	// concept requirements
4861	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4862	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4863	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4864	typename iterator_traits<_InputIterator1>::value_type>)
4865	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4866	typename iterator_traits<_InputIterator2>::value_type>)
4867	__glibcxx_function_requires(_LessThanOpConcept<
4868	typename iterator_traits<_InputIterator2>::value_type,
4869	typename iterator_traits<_InputIterator1>::value_type>)
4870	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
4871	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
4872	__glibcxx_requires_irreflexive2(__first1, __last1);
4873	__glibcxx_requires_irreflexive2(__first2, __last2);
4874
4875	return _GLIBCXX_STD_A::__merge(__first1, __last1,
4876	__first2, __last2, __result,
4877	__gnu_cxx::__ops::__iter_less_iter());
4878	}
4879
4880	/**
4881	* @brief Merges two sorted ranges.
4882	* @ingroup sorting_algorithms
4883	* @param __first1 An iterator.
4884	* @param __first2 Another iterator.
4885	* @param __last1 Another iterator.
4886	* @param __last2 Another iterator.
4887	* @param __result An iterator pointing to the end of the merged range.
4888	* @param __comp A functor to use for comparisons.
4889	* @return An output iterator equal to @p __result + (__last1 - __first1)
4890	* + (__last2 - __first2).
4891	*
4892	* Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
4893	* the sorted range @p [__result, __result + (__last1-__first1) +
4894	* (__last2-__first2)). Both input ranges must be sorted, and the
4895	* output range must not overlap with either of the input ranges.
4896	* The sort is @e stable, that is, for equivalent elements in the
4897	* two ranges, elements from the first range will always come
4898	* before elements from the second.
4899	*
4900	* The comparison function should have the same effects on ordering as
4901	* the function used for the initial sort.
4902	*/
4903	template<typename _InputIterator1, typename _InputIterator2,
4904	typename _OutputIterator, typename _Compare>
4905	_GLIBCXX20_CONSTEXPR
4906	inline _OutputIterator
4907	merge(_InputIterator1 __first1, _InputIterator1 __last1,
4908	_InputIterator2 __first2, _InputIterator2 __last2,
4909	_OutputIterator __result, _Compare __comp)
4910	{
4911	// concept requirements
4912	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4913	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4914	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4915	typename iterator_traits<_InputIterator1>::value_type>)
4916	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4917	typename iterator_traits<_InputIterator2>::value_type>)
4918	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4919	typename iterator_traits<_InputIterator2>::value_type,
4920	typename iterator_traits<_InputIterator1>::value_type>)
4921	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4922	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4923	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4924	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4925
4926	return _GLIBCXX_STD_A::__merge(__first1, __last1,
4927	__first2, __last2, __result,
4928	__gnu_cxx::__ops::__iter_comp_iter(__comp));
4929	}
4930
4931	template<typename _RandomAccessIterator, typename _Compare>
4932	inline void
4933	__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4934	_Compare __comp)
4935	{
4936	typedef typename iterator_traits<_RandomAccessIterator>::value_type
4937	_ValueType;
4938	typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4939	_DistanceType;
4940
4941	if (__first == __last)
4942	return;
4943
4944	#if _GLIBCXX_HOSTED
4945	typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4946	// __stable_sort_adaptive sorts the range in two halves,
4947	// so the buffer only needs to fit half the range at once.
4948	_TmpBuf __buf(__first, (__last - __first + `1`) / `2`);
4949
4950	if (__builtin_expect(__buf.requested_size() == __buf.size(), true))
4951	std::__stable_sort_adaptive(__first,
4952	__first + _DistanceType(__buf.size()),
4953	__last, __buf.begin(), __comp);
4954	else if (__builtin_expect(__buf.begin() == `0`, false))
4955	std::__inplace_stable_sort(__first, __last, __comp);
4956	else
4957	std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
4958	_DistanceType(__buf.size()), __comp);
4959	#else
4960	std::__inplace_stable_sort(__first, __last, __comp);
4961	#endif
4962	}
4963
4964	/**
4965	* @brief Sort the elements of a sequence, preserving the relative order
4966	* of equivalent elements.
4967	* @ingroup sorting_algorithms
4968	* @param __first An iterator.
4969	* @param __last Another iterator.
4970	* @return Nothing.
4971	*
4972	* Sorts the elements in the range @p [__first,__last) in ascending order,
4973	* such that for each iterator @p i in the range @p [__first,__last-1),
4974	* @p (i+1)<i is false.
4975	*
4976	* The relative ordering of equivalent elements is preserved, so any two
4977	* elements @p x and @p y in the range @p [__first,__last) such that
4978	* @p x<y is false and @p y<x is false will have the same relative
4979	* ordering after calling @p stable_sort().
4980	*/
4981	template<typename _RandomAccessIterator>
4982	inline void
4983	stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4984	{
4985	// concept requirements
4986	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4987	_RandomAccessIterator>)
4988	__glibcxx_function_requires(_LessThanComparableConcept<
4989	typename iterator_traits<_RandomAccessIterator>::value_type>)
4990	__glibcxx_requires_valid_range(__first, __last);
4991	__glibcxx_requires_irreflexive(__first, __last);
4992
4993	_GLIBCXX_STD_A::__stable_sort(__first, __last,
4994	__gnu_cxx::__ops::__iter_less_iter());
4995	}
4996
4997	/**
4998	* @brief Sort the elements of a sequence using a predicate for comparison,
4999	* preserving the relative order of equivalent elements.
5000	* @ingroup sorting_algorithms
5001	* @param __first An iterator.
5002	* @param __last Another iterator.
5003	* @param __comp A comparison functor.
5004	* @return Nothing.
5005	*
5006	* Sorts the elements in the range @p [__first,__last) in ascending order,
5007	* such that for each iterator @p i in the range @p [__first,__last-1),
5008	* @p __comp((i+1),i) is false.
5009	*
5010	* The relative ordering of equivalent elements is preserved, so any two
5011	* elements @p x and @p y in the range @p [__first,__last) such that
5012	* @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5013	* relative ordering after calling @p stable_sort().
5014	*/
5015	template<typename _RandomAccessIterator, typename _Compare>
5016	inline void
5017	stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5018	_Compare __comp)
5019	{
5020	// concept requirements
5021	__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5022	_RandomAccessIterator>)
5023	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5024	typename iterator_traits<_RandomAccessIterator>::value_type,
5025	typename iterator_traits<_RandomAccessIterator>::value_type>)
5026	__glibcxx_requires_valid_range(__first, __last);
5027	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5028
5029	_GLIBCXX_STD_A::__stable_sort(__first, __last,
5030	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5031	}
5032
5033	template<typename _InputIterator1, typename _InputIterator2,
5034	typename _OutputIterator,
5035	typename _Compare>
5036	_GLIBCXX20_CONSTEXPR
5037	_OutputIterator
5038	__set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5039	_InputIterator2 __first2, _InputIterator2 __last2,
5040	_OutputIterator __result, _Compare __comp)
5041	{
5042	while (__first1 != __last1 && __first2 != __last2)
5043	{
5044	if (__comp(__first1, __first2))
5045	{
5046	__result = __first1;
5047	++__first1;
5048	}
5049	else if (__comp(__first2, __first1))
5050	{
5051	__result = __first2;
5052	++__first2;
5053	}
5054	else
5055	{
5056	__result = __first1;
5057	++__first1;
5058	++__first2;
5059	}
5060	++__result;
5061	}
5062	return std::copy(__first2, __last2,
5063	std::copy(__first1, __last1, __result));
5064	}
5065
5066	/**
5067	* @brief Return the union of two sorted ranges.
5068	* @ingroup set_algorithms
5069	* @param __first1 Start of first range.
5070	* @param __last1 End of first range.
5071	* @param __first2 Start of second range.
5072	* @param __last2 End of second range.
5073	* @param __result Start of output range.
5074	* @return End of the output range.
5075	* @ingroup set_algorithms
5076	*
5077	* This operation iterates over both ranges, copying elements present in
5078	* each range in order to the output range. Iterators increment for each
5079	* range. When the current element of one range is less than the other,
5080	* that element is copied and the iterator advanced. If an element is
5081	* contained in both ranges, the element from the first range is copied and
5082	* both ranges advance. The output range may not overlap either input
5083	* range.
5084	*/
5085	template<typename _InputIterator1, typename _InputIterator2,
5086	typename _OutputIterator>
5087	_GLIBCXX20_CONSTEXPR
5088	inline _OutputIterator
5089	set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5090	_InputIterator2 __first2, _InputIterator2 __last2,
5091	_OutputIterator __result)
5092	{
5093	// concept requirements
5094	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5095	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5096	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5097	typename iterator_traits<_InputIterator1>::value_type>)
5098	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5099	typename iterator_traits<_InputIterator2>::value_type>)
5100	__glibcxx_function_requires(_LessThanOpConcept<
5101	typename iterator_traits<_InputIterator1>::value_type,
5102	typename iterator_traits<_InputIterator2>::value_type>)
5103	__glibcxx_function_requires(_LessThanOpConcept<
5104	typename iterator_traits<_InputIterator2>::value_type,
5105	typename iterator_traits<_InputIterator1>::value_type>)
5106	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5107	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5108	__glibcxx_requires_irreflexive2(__first1, __last1);
5109	__glibcxx_requires_irreflexive2(__first2, __last2);
5110
5111	return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5112	__first2, __last2, __result,
5113	__gnu_cxx::__ops::__iter_less_iter());
5114	}
5115
5116	/**
5117	* @brief Return the union of two sorted ranges using a comparison functor.
5118	* @ingroup set_algorithms
5119	* @param __first1 Start of first range.
5120	* @param __last1 End of first range.
5121	* @param __first2 Start of second range.
5122	* @param __last2 End of second range.
5123	* @param __result Start of output range.
5124	* @param __comp The comparison functor.
5125	* @return End of the output range.
5126	* @ingroup set_algorithms
5127	*
5128	* This operation iterates over both ranges, copying elements present in
5129	* each range in order to the output range. Iterators increment for each
5130	* range. When the current element of one range is less than the other
5131	* according to @p __comp, that element is copied and the iterator advanced.
5132	* If an equivalent element according to @p __comp is contained in both
5133	* ranges, the element from the first range is copied and both ranges
5134	* advance. The output range may not overlap either input range.
5135	*/
5136	template<typename _InputIterator1, typename _InputIterator2,
5137	typename _OutputIterator, typename _Compare>
5138	_GLIBCXX20_CONSTEXPR
5139	inline _OutputIterator
5140	set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5141	_InputIterator2 __first2, _InputIterator2 __last2,
5142	_OutputIterator __result, _Compare __comp)
5143	{
5144	// concept requirements
5145	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5146	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5147	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5148	typename iterator_traits<_InputIterator1>::value_type>)
5149	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5150	typename iterator_traits<_InputIterator2>::value_type>)
5151	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5152	typename iterator_traits<_InputIterator1>::value_type,
5153	typename iterator_traits<_InputIterator2>::value_type>)
5154	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5155	typename iterator_traits<_InputIterator2>::value_type,
5156	typename iterator_traits<_InputIterator1>::value_type>)
5157	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5158	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5159	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5160	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5161
5162	return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5163	__first2, __last2, __result,
5164	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5165	}
5166
5167	template<typename _InputIterator1, typename _InputIterator2,
5168	typename _OutputIterator,
5169	typename _Compare>
5170	_GLIBCXX20_CONSTEXPR
5171	_OutputIterator
5172	__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5173	_InputIterator2 __first2, _InputIterator2 __last2,
5174	_OutputIterator __result, _Compare __comp)
5175	{
5176	while (__first1 != __last1 && __first2 != __last2)
5177	if (__comp(__first1, __first2))
5178	++__first1;
5179	else if (__comp(__first2, __first1))
5180	++__first2;
5181	else
5182	{
5183	__result = __first1;
5184	++__first1;
5185	++__first2;
5186	++__result;
5187	}
5188	return __result;
5189	}
5190
5191	/**
5192	* @brief Return the intersection of two sorted ranges.
5193	* @ingroup set_algorithms
5194	* @param __first1 Start of first range.
5195	* @param __last1 End of first range.
5196	* @param __first2 Start of second range.
5197	* @param __last2 End of second range.
5198	* @param __result Start of output range.
5199	* @return End of the output range.
5200	* @ingroup set_algorithms
5201	*
5202	* This operation iterates over both ranges, copying elements present in
5203	* both ranges in order to the output range. Iterators increment for each
5204	* range. When the current element of one range is less than the other,
5205	* that iterator advances. If an element is contained in both ranges, the
5206	* element from the first range is copied and both ranges advance. The
5207	* output range may not overlap either input range.
5208	*/
5209	template<typename _InputIterator1, typename _InputIterator2,
5210	typename _OutputIterator>
5211	_GLIBCXX20_CONSTEXPR
5212	inline _OutputIterator
5213	set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5214	_InputIterator2 __first2, _InputIterator2 __last2,
5215	_OutputIterator __result)
5216	{
5217	// concept requirements
5218	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5219	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5220	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5221	typename iterator_traits<_InputIterator1>::value_type>)
5222	__glibcxx_function_requires(_LessThanOpConcept<
5223	typename iterator_traits<_InputIterator1>::value_type,
5224	typename iterator_traits<_InputIterator2>::value_type>)
5225	__glibcxx_function_requires(_LessThanOpConcept<
5226	typename iterator_traits<_InputIterator2>::value_type,
5227	typename iterator_traits<_InputIterator1>::value_type>)
5228	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5229	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5230	__glibcxx_requires_irreflexive2(__first1, __last1);
5231	__glibcxx_requires_irreflexive2(__first2, __last2);
5232
5233	return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5234	__first2, __last2, __result,
5235	__gnu_cxx::__ops::__iter_less_iter());
5236	}
5237
5238	/**
5239	* @brief Return the intersection of two sorted ranges using comparison
5240	* functor.
5241	* @ingroup set_algorithms
5242	* @param __first1 Start of first range.
5243	* @param __last1 End of first range.
5244	* @param __first2 Start of second range.
5245	* @param __last2 End of second range.
5246	* @param __result Start of output range.
5247	* @param __comp The comparison functor.
5248	* @return End of the output range.
5249	* @ingroup set_algorithms
5250	*
5251	* This operation iterates over both ranges, copying elements present in
5252	* both ranges in order to the output range. Iterators increment for each
5253	* range. When the current element of one range is less than the other
5254	* according to @p __comp, that iterator advances. If an element is
5255	* contained in both ranges according to @p __comp, the element from the
5256	* first range is copied and both ranges advance. The output range may not
5257	* overlap either input range.
5258	*/
5259	template<typename _InputIterator1, typename _InputIterator2,
5260	typename _OutputIterator, typename _Compare>
5261	_GLIBCXX20_CONSTEXPR
5262	inline _OutputIterator
5263	set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5264	_InputIterator2 __first2, _InputIterator2 __last2,
5265	_OutputIterator __result, _Compare __comp)
5266	{
5267	// concept requirements
5268	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5269	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5270	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5271	typename iterator_traits<_InputIterator1>::value_type>)
5272	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5273	typename iterator_traits<_InputIterator1>::value_type,
5274	typename iterator_traits<_InputIterator2>::value_type>)
5275	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5276	typename iterator_traits<_InputIterator2>::value_type,
5277	typename iterator_traits<_InputIterator1>::value_type>)
5278	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5279	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5280	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5281	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5282
5283	return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5284	__first2, __last2, __result,
5285	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5286	}
5287
5288	template<typename _InputIterator1, typename _InputIterator2,
5289	typename _OutputIterator,
5290	typename _Compare>
5291	_GLIBCXX20_CONSTEXPR
5292	_OutputIterator
5293	__set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5294	_InputIterator2 __first2, _InputIterator2 __last2,
5295	_OutputIterator __result, _Compare __comp)
5296	{
5297	while (__first1 != __last1 && __first2 != __last2)
5298	if (__comp(__first1, __first2))
5299	{
5300	__result = __first1;
5301	++__first1;
5302	++__result;
5303	}
5304	else if (__comp(__first2, __first1))
5305	++__first2;
5306	else
5307	{
5308	++__first1;
5309	++__first2;
5310	}
5311	return std::copy(__first1, __last1, __result);
5312	}
5313
5314	/**
5315	* @brief Return the difference of two sorted ranges.
5316	* @ingroup set_algorithms
5317	* @param __first1 Start of first range.
5318	* @param __last1 End of first range.
5319	* @param __first2 Start of second range.
5320	* @param __last2 End of second range.
5321	* @param __result Start of output range.
5322	* @return End of the output range.
5323	* @ingroup set_algorithms
5324	*
5325	* This operation iterates over both ranges, copying elements present in
5326	* the first range but not the second in order to the output range.
5327	* Iterators increment for each range. When the current element of the
5328	* first range is less than the second, that element is copied and the
5329	* iterator advances. If the current element of the second range is less,
5330	* the iterator advances, but no element is copied. If an element is
5331	* contained in both ranges, no elements are copied and both ranges
5332	* advance. The output range may not overlap either input range.
5333	*/
5334	template<typename _InputIterator1, typename _InputIterator2,
5335	typename _OutputIterator>
5336	_GLIBCXX20_CONSTEXPR
5337	inline _OutputIterator
5338	set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5339	_InputIterator2 __first2, _InputIterator2 __last2,
5340	_OutputIterator __result)
5341	{
5342	// concept requirements
5343	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5344	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5345	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5346	typename iterator_traits<_InputIterator1>::value_type>)
5347	__glibcxx_function_requires(_LessThanOpConcept<
5348	typename iterator_traits<_InputIterator1>::value_type,
5349	typename iterator_traits<_InputIterator2>::value_type>)
5350	__glibcxx_function_requires(_LessThanOpConcept<
5351	typename iterator_traits<_InputIterator2>::value_type,
5352	typename iterator_traits<_InputIterator1>::value_type>)
5353	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5354	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5355	__glibcxx_requires_irreflexive2(__first1, __last1);
5356	__glibcxx_requires_irreflexive2(__first2, __last2);
5357
5358	return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5359	__first2, __last2, __result,
5360	__gnu_cxx::__ops::__iter_less_iter());
5361	}
5362
5363	/**
5364	* @brief Return the difference of two sorted ranges using comparison
5365	* functor.
5366	* @ingroup set_algorithms
5367	* @param __first1 Start of first range.
5368	* @param __last1 End of first range.
5369	* @param __first2 Start of second range.
5370	* @param __last2 End of second range.
5371	* @param __result Start of output range.
5372	* @param __comp The comparison functor.
5373	* @return End of the output range.
5374	* @ingroup set_algorithms
5375	*
5376	* This operation iterates over both ranges, copying elements present in
5377	* the first range but not the second in order to the output range.
5378	* Iterators increment for each range. When the current element of the
5379	* first range is less than the second according to @p __comp, that element
5380	* is copied and the iterator advances. If the current element of the
5381	* second range is less, no element is copied and the iterator advances.
5382	* If an element is contained in both ranges according to @p __comp, no
5383	* elements are copied and both ranges advance. The output range may not
5384	* overlap either input range.
5385	*/
5386	template<typename _InputIterator1, typename _InputIterator2,
5387	typename _OutputIterator, typename _Compare>
5388	_GLIBCXX20_CONSTEXPR
5389	inline _OutputIterator
5390	set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5391	_InputIterator2 __first2, _InputIterator2 __last2,
5392	_OutputIterator __result, _Compare __comp)
5393	{
5394	// concept requirements
5395	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5396	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5397	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5398	typename iterator_traits<_InputIterator1>::value_type>)
5399	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5400	typename iterator_traits<_InputIterator1>::value_type,
5401	typename iterator_traits<_InputIterator2>::value_type>)
5402	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5403	typename iterator_traits<_InputIterator2>::value_type,
5404	typename iterator_traits<_InputIterator1>::value_type>)
5405	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5406	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5407	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5408	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5409
5410	return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5411	__first2, __last2, __result,
5412	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5413	}
5414
5415	template<typename _InputIterator1, typename _InputIterator2,
5416	typename _OutputIterator,
5417	typename _Compare>
5418	_GLIBCXX20_CONSTEXPR
5419	_OutputIterator
5420	__set_symmetric_difference(_InputIterator1 __first1,
5421	_InputIterator1 __last1,
5422	_InputIterator2 __first2,
5423	_InputIterator2 __last2,
5424	_OutputIterator __result,
5425	_Compare __comp)
5426	{
5427	while (__first1 != __last1 && __first2 != __last2)
5428	if (__comp(__first1, __first2))
5429	{
5430	__result = __first1;
5431	++__first1;
5432	++__result;
5433	}
5434	else if (__comp(__first2, __first1))
5435	{
5436	__result = __first2;
5437	++__first2;
5438	++__result;
5439	}
5440	else
5441	{
5442	++__first1;
5443	++__first2;
5444	}
5445	return std::copy(__first2, __last2,
5446	std::copy(__first1, __last1, __result));
5447	}
5448
5449	/**
5450	* @brief Return the symmetric difference of two sorted ranges.
5451	* @ingroup set_algorithms
5452	* @param __first1 Start of first range.
5453	* @param __last1 End of first range.
5454	* @param __first2 Start of second range.
5455	* @param __last2 End of second range.
5456	* @param __result Start of output range.
5457	* @return End of the output range.
5458	* @ingroup set_algorithms
5459	*
5460	* This operation iterates over both ranges, copying elements present in
5461	* one range but not the other in order to the output range. Iterators
5462	* increment for each range. When the current element of one range is less
5463	* than the other, that element is copied and the iterator advances. If an
5464	* element is contained in both ranges, no elements are copied and both
5465	* ranges advance. The output range may not overlap either input range.
5466	*/
5467	template<typename _InputIterator1, typename _InputIterator2,
5468	typename _OutputIterator>
5469	_GLIBCXX20_CONSTEXPR
5470	inline _OutputIterator
5471	set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5472	_InputIterator2 __first2, _InputIterator2 __last2,
5473	_OutputIterator __result)
5474	{
5475	// concept requirements
5476	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5477	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5478	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5479	typename iterator_traits<_InputIterator1>::value_type>)
5480	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5481	typename iterator_traits<_InputIterator2>::value_type>)
5482	__glibcxx_function_requires(_LessThanOpConcept<
5483	typename iterator_traits<_InputIterator1>::value_type,
5484	typename iterator_traits<_InputIterator2>::value_type>)
5485	__glibcxx_function_requires(_LessThanOpConcept<
5486	typename iterator_traits<_InputIterator2>::value_type,
5487	typename iterator_traits<_InputIterator1>::value_type>)
5488	__glibcxx_requires_sorted_set(__first1, __last1, __first2);
5489	__glibcxx_requires_sorted_set(__first2, __last2, __first1);
5490	__glibcxx_requires_irreflexive2(__first1, __last1);
5491	__glibcxx_requires_irreflexive2(__first2, __last2);
5492
5493	return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5494	__first2, __last2, __result,
5495	__gnu_cxx::__ops::__iter_less_iter());
5496	}
5497
5498	/**
5499	* @brief Return the symmetric difference of two sorted ranges using
5500	* comparison functor.
5501	* @ingroup set_algorithms
5502	* @param __first1 Start of first range.
5503	* @param __last1 End of first range.
5504	* @param __first2 Start of second range.
5505	* @param __last2 End of second range.
5506	* @param __result Start of output range.
5507	* @param __comp The comparison functor.
5508	* @return End of the output range.
5509	* @ingroup set_algorithms
5510	*
5511	* This operation iterates over both ranges, copying elements present in
5512	* one range but not the other in order to the output range. Iterators
5513	* increment for each range. When the current element of one range is less
5514	* than the other according to @p comp, that element is copied and the
5515	* iterator advances. If an element is contained in both ranges according
5516	* to @p __comp, no elements are copied and both ranges advance. The output
5517	* range may not overlap either input range.
5518	*/
5519	template<typename _InputIterator1, typename _InputIterator2,
5520	typename _OutputIterator, typename _Compare>
5521	_GLIBCXX20_CONSTEXPR
5522	inline _OutputIterator
5523	set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5524	_InputIterator2 __first2, _InputIterator2 __last2,
5525	_OutputIterator __result,
5526	_Compare __comp)
5527	{
5528	// concept requirements
5529	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5530	__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5531	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5532	typename iterator_traits<_InputIterator1>::value_type>)
5533	__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5534	typename iterator_traits<_InputIterator2>::value_type>)
5535	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5536	typename iterator_traits<_InputIterator1>::value_type,
5537	typename iterator_traits<_InputIterator2>::value_type>)
5538	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5539	typename iterator_traits<_InputIterator2>::value_type,
5540	typename iterator_traits<_InputIterator1>::value_type>)
5541	__glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5542	__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5543	__glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5544	__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5545
5546	return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5547	__first2, __last2, __result,
5548	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5549	}
5550
5551	template<typename _ForwardIterator, typename _Compare>
5552	_GLIBCXX14_CONSTEXPR
5553	_ForwardIterator
5554	__min_element(_ForwardIterator __first, _ForwardIterator __last,
5555	_Compare __comp)
5556	{
5557	if (__first == __last)
5558	return __first;
5559	_ForwardIterator __result = __first;
5560	while (++__first != __last)
5561	if (__comp(__first, __result))
5562	__result = __first;
5563	return __result;
5564	}
5565
5566	/**
5567	* @brief Return the minimum element in a range.
5568	* @ingroup sorting_algorithms
5569	* @param __first Start of range.
5570	* @param __last End of range.
5571	* @return Iterator referencing the first instance of the smallest value.
5572	*/
5573	template<typename _ForwardIterator>
5574	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5575	_ForwardIterator
5576	inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5577	{
5578	// concept requirements
5579	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5580	__glibcxx_function_requires(_LessThanComparableConcept<
5581	typename iterator_traits<_ForwardIterator>::value_type>)
5582	__glibcxx_requires_valid_range(__first, __last);
5583	__glibcxx_requires_irreflexive(__first, __last);
5584
5585	return _GLIBCXX_STD_A::__min_element(__first, __last,
5586	__gnu_cxx::__ops::__iter_less_iter());
5587	}
5588
5589	/**
5590	* @brief Return the minimum element in a range using comparison functor.
5591	* @ingroup sorting_algorithms
5592	* @param __first Start of range.
5593	* @param __last End of range.
5594	* @param __comp Comparison functor.
5595	* @return Iterator referencing the first instance of the smallest value
5596	* according to __comp.
5597	*/
5598	template<typename _ForwardIterator, typename _Compare>
5599	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5600	inline _ForwardIterator
5601	min_element(_ForwardIterator __first, _ForwardIterator __last,
5602	_Compare __comp)
5603	{
5604	// concept requirements
5605	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5606	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5607	typename iterator_traits<_ForwardIterator>::value_type,
5608	typename iterator_traits<_ForwardIterator>::value_type>)
5609	__glibcxx_requires_valid_range(__first, __last);
5610	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5611
5612	return _GLIBCXX_STD_A::__min_element(__first, __last,
5613	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5614	}
5615
5616	template<typename _ForwardIterator, typename _Compare>
5617	_GLIBCXX14_CONSTEXPR
5618	_ForwardIterator
5619	__max_element(_ForwardIterator __first, _ForwardIterator __last,
5620	_Compare __comp)
5621	{
5622	if (__first == __last) return __first;
5623	_ForwardIterator __result = __first;
5624	while (++__first != __last)
5625	if (__comp(__result, __first))
5626	__result = __first;
5627	return __result;
5628	}
5629
5630	/**
5631	* @brief Return the maximum element in a range.
5632	* @ingroup sorting_algorithms
5633	* @param __first Start of range.
5634	* @param __last End of range.
5635	* @return Iterator referencing the first instance of the largest value.
5636	*/
5637	template<typename _ForwardIterator>
5638	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5639	inline _ForwardIterator
5640	max_element(_ForwardIterator __first, _ForwardIterator __last)
5641	{
5642	// concept requirements
5643	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5644	__glibcxx_function_requires(_LessThanComparableConcept<
5645	typename iterator_traits<_ForwardIterator>::value_type>)
5646	__glibcxx_requires_valid_range(__first, __last);
5647	__glibcxx_requires_irreflexive(__first, __last);
5648
5649	return _GLIBCXX_STD_A::__max_element(__first, __last,
5650	__gnu_cxx::__ops::__iter_less_iter());
5651	}
5652
5653	/**
5654	* @brief Return the maximum element in a range using comparison functor.
5655	* @ingroup sorting_algorithms
5656	* @param __first Start of range.
5657	* @param __last End of range.
5658	* @param __comp Comparison functor.
5659	* @return Iterator referencing the first instance of the largest value
5660	* according to __comp.
5661	*/
5662	template<typename _ForwardIterator, typename _Compare>
5663	_GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
5664	inline _ForwardIterator
5665	max_element(_ForwardIterator __first, _ForwardIterator __last,
5666	_Compare __comp)
5667	{
5668	// concept requirements
5669	__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5670	__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5671	typename iterator_traits<_ForwardIterator>::value_type,
5672	typename iterator_traits<_ForwardIterator>::value_type>)
5673	__glibcxx_requires_valid_range(__first, __last);
5674	__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5675
5676	return _GLIBCXX_STD_A::__max_element(__first, __last,
5677	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5678	}
5679
5680	#if __cplusplus >= 201103L
5681	// N2722 + DR 915.
5682	template<typename _Tp>
5683	_GLIBCXX14_CONSTEXPR
5684	inline _Tp
5685	min(initializer_list<_Tp> __l)
5686	{
5687	__glibcxx_requires_irreflexive(__l.begin(), __l.end());
5688	return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5689	__gnu_cxx::__ops::__iter_less_iter());
5690	}
5691
5692	template<typename _Tp, typename _Compare>
5693	_GLIBCXX14_CONSTEXPR
5694	inline _Tp
5695	min(initializer_list<_Tp> __l, _Compare __comp)
5696	{
5697	__glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5698	return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5699	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5700	}
5701
5702	template<typename _Tp>
5703	_GLIBCXX14_CONSTEXPR
5704	inline _Tp
5705	max(initializer_list<_Tp> __l)
5706	{
5707	__glibcxx_requires_irreflexive(__l.begin(), __l.end());
5708	return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5709	__gnu_cxx::__ops::__iter_less_iter());
5710	}
5711
5712	template<typename _Tp, typename _Compare>
5713	_GLIBCXX14_CONSTEXPR
5714	inline _Tp
5715	max(initializer_list<_Tp> __l, _Compare __comp)
5716	{
5717	__glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5718	return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5719	__gnu_cxx::__ops::__iter_comp_iter(__comp));
5720	}
5721	#endif // C++11
5722
5723	#if __cplusplus >= 201402L
5724	/// Reservoir sampling algorithm.
5725	template<typename _InputIterator, typename _RandomAccessIterator,
5726	typename _Size, typename _UniformRandomBitGenerator>
5727	_RandomAccessIterator
5728	__sample(_InputIterator __first, _InputIterator __last, input_iterator_tag,
5729	_RandomAccessIterator __out, random_access_iterator_tag,
5730	_Size __n, _UniformRandomBitGenerator&& __g)
5731	{
5732	using __distrib_type = uniform_int_distribution<_Size>;
5733	using __param_type = typename __distrib_type::param_type;
5734	__distrib_type __d{};
5735	_Size __sample_sz = `0`;
5736	while (__first != __last && __sample_sz != __n)
5737	{
5738	__out[__sample_sz++] = *__first;
5739	++__first;
5740	}
5741	for (auto __pop_sz = __sample_sz; __first != __last;
5742	++__first, (void) ++__pop_sz)
5743	{
5744	const auto __k = __d(__g, __param_type{`0`, __pop_sz});
5745	if (__k < __n)
5746	__out[__k] = *__first;
5747	}
5748	return __out + __sample_sz;
5749	}
5750
5751	/// Selection sampling algorithm.
5752	template<typename _ForwardIterator, typename _OutputIterator, typename _Cat,
5753	typename _Size, typename _UniformRandomBitGenerator>
5754	_OutputIterator
5755	__sample(_ForwardIterator __first, _ForwardIterator __last,
5756	forward_iterator_tag,
5757	_OutputIterator __out, _Cat,
5758	_Size __n, _UniformRandomBitGenerator&& __g)
5759	{
5760	using __distrib_type = uniform_int_distribution<_Size>;
5761	using __param_type = typename __distrib_type::param_type;
5762	using _USize = make_unsigned_t<_Size>;
5763	using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
5764	using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
5765
5766	if (__first == __last)
5767	return __out;
5768
5769	__distrib_type __d{};
5770	_Size __unsampled_sz = std::distance(__first, __last);
5771	__n = std::min(__n, __unsampled_sz);
5772
5773	// If possible, we use __gen_two_uniform_ints to efficiently produce
5774	// two random numbers using a single distribution invocation:
5775
5776	const __uc_type __urngrange = __g.max() - __g.min();
5777	if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5778	// I.e. (__urngrange >= __unsampled_sz __unsampled_sz) but without*
5779	// wrapping issues.
5780	{
5781	while (__n != `0` && __unsampled_sz >= `2`)
5782	{
5783	const pair<_Size, _Size> __p =
5784	__gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - `1`, __g);
5785
5786	--__unsampled_sz;
5787	if (__p.first < __n)
5788	{
5789	__out++ = __first;
5790	--__n;
5791	}
5792
5793	++__first;
5794
5795	if (__n == `0`) break;
5796
5797	--__unsampled_sz;
5798	if (__p.second < __n)
5799	{
5800	__out++ = __first;
5801	--__n;
5802	}
5803
5804	++__first;
5805	}
5806	}
5807
5808	// The loop above is otherwise equivalent to this one-at-a-time version:
5809
5810	for (; __n != `0`; ++__first)
5811	if (__d(__g, __param_type{`0`, --__unsampled_sz}) < __n)
5812	{
5813	__out++ = __first;
5814	--__n;
5815	}
5816	return __out;
5817	}
5818	#endif // C++14
5819
5820	#ifdef __glibcxx_sample // C++ >= 17
5821	/// Take a random sample from a population.
5822	template<typename _PopulationIterator, typename _SampleIterator,
5823	typename _Distance, typename _UniformRandomBitGenerator>
5824	_SampleIterator
5825	sample(_PopulationIterator __first, _PopulationIterator __last,
5826	_SampleIterator __out, _Distance __n,
5827	_UniformRandomBitGenerator&& __g)
5828	{
5829	using __pop_cat = typename
5830	std::iterator_traits<_PopulationIterator>::iterator_category;
5831	using __samp_cat = typename
5832	std::iterator_traits<_SampleIterator>::iterator_category;
5833
5834	static_assert(
5835	__or_<is_convertible<__pop_cat, forward_iterator_tag>,
5836	is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5837	"output range must use a RandomAccessIterator when input range"
5838	" does not meet the ForwardIterator requirements");
5839
5840	static_assert(is_integral<_Distance>::value,
5841	"sample size must be an integer type");
5842
5843	typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5844	return _GLIBCXX_STD_A::
5845	__sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5846	std::forward<_UniformRandomBitGenerator>(__g));
5847	}
5848	#endif // __glibcxx_sample
5849
5850	_GLIBCXX_END_NAMESPACE_ALGO
5851	_GLIBCXX_END_NAMESPACE_VERSION
5852	} // namespace std
5853
5854	#endif /* _STL_ALGO_H */
5855

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