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