Context Navigation

stl_algo.h

Last change on this file was 2, checked in by jglee, 11 years ago
first commit
Property svn:executable set to ``*
File size: 172.7 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: svn/trunk/newcon3bcm2_21bu/toolchain/include/c++/3.4.2/bits/stl_algo.h

Download in other formats: