WebSVN – Kolibri OS – Blame – /contrib/media/updf/include/bits/stl_algo.h

Rev	Author	Line No.	Line
4680	right-hear	1	/*
		2	*
		3	* Copyright (c) 1994
		4	* Hewlett-Packard Company
		5	*
		6	* Permission to use, copy, modify, distribute and sell this software
		7	* and its documentation for any purpose is hereby granted without fee,
		8	* provided that the above copyright notice appear in all copies and
		9	* that both that copyright notice and this permission notice appear
		10	* in supporting documentation. Hewlett-Packard Company makes no
		11	* representations about the suitability of this software for any
		12	* purpose. It is provided "as is" without express or implied warranty.
		13	*
		14	*
		15	* Copyright (c) 1996
		16	* Silicon Graphics Computer Systems, Inc.
		17	*
		18	* Permission to use, copy, modify, distribute and sell this software
		19	* and its documentation for any purpose is hereby granted without fee,
		20	* provided that the above copyright notice appear in all copies and
		21	* that both that copyright notice and this permission notice appear
		22	* in supporting documentation. Silicon Graphics makes no
		23	* representations about the suitability of this software for any
		24	* purpose. It is provided "as is" without express or implied warranty.
		25	*/
		26
		27	/* NOTE: This is an internal header file, included by other STL headers.
		28	* You should not attempt to use it directly.
		29	*/
		30
		31	#ifndef __SGI_STL_INTERNAL_ALGO_H
		32	#define __SGI_STL_INTERNAL_ALGO_H
		33
		34	#include
		35
		36	// See concept_check.h for the __glibcpp_*_requires macros.
		37
		38	namespace std
		39	{
		40
		41	// __median (an extension, not present in the C++ standard).
		42
		43	template
		44	inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
		45	{
		46	// concept requirements
		47	__glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
		48	if (__a < __b)
		49	if (__b < __c)
		50	return __b;
		51	else if (__a < __c)
		52	return __c;
		53	else
		54	return __a;
		55	else if (__a < __c)
		56	return __a;
		57	else if (__b < __c)
		58	return __c;
		59	else
		60	return __b;
		61	}
		62
		63	template
		64	inline const _Tp&
		65	__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
		66	{
		67	// concept requirements
		68	__glibcpp_function_requires(_BinaryFunctionConcept<_Compare, bool, _Tp, _Tp>);
		69	if (__comp(__a, __b))
		70	if (__comp(__b, __c))
		71	return __b;
		72	else if (__comp(__a, __c))
		73	return __c;
		74	else
		75	return __a;
		76	else if (__comp(__a, __c))
		77	return __a;
		78	else if (__comp(__b, __c))
		79	return __c;
		80	else
		81	return __b;
		82	}
		83
		84	// for_each. Apply a function to every element of a range.
		85	template
		86	_Function for_each(_InputIter __first, _InputIter __last, _Function __f)
		87	{
		88	// concept requirements
		89	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		90	for ( ; __first != __last; ++__first)
		91	__f(*__first);
		92	return __f;
		93	}
		94
		95	// find and find_if.
		96
		97	template
		98	inline _InputIter find(_InputIter __first, _InputIter __last,
		99	const _Tp& __val,
		100	input_iterator_tag)
		101	{
		102	while (__first != __last && !(*__first == __val))
		103	++__first;
		104	return __first;
		105	}
		106
		107	template
		108	inline _InputIter find_if(_InputIter __first, _InputIter __last,
		109	_Predicate __pred,
		110	input_iterator_tag)
		111	{
		112	while (__first != __last && !__pred(*__first))
		113	++__first;
		114	return __first;
		115	}
		116
		117	template
		118	_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
		119	const _Tp& __val,
		120	random_access_iterator_tag)
		121	{
		122	typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
		123	= (__last - __first) >> 2;
		124
		125	for ( ; __trip_count > 0 ; --__trip_count) {
		126	if (*__first == __val) return __first;
		127	++__first;
		128
		129	if (*__first == __val) return __first;
		130	++__first;
		131
		132	if (*__first == __val) return __first;
		133	++__first;
		134
		135	if (*__first == __val) return __first;
		136	++__first;
		137	}
		138
		139	switch(__last - __first) {
		140	case 3:
		141	if (*__first == __val) return __first;
		142	++__first;
		143	case 2:
		144	if (*__first == __val) return __first;
		145	++__first;
		146	case 1:
		147	if (*__first == __val) return __first;
		148	++__first;
		149	case 0:
		150	default:
		151	return __last;
		152	}
		153	}
		154
		155	template
		156	_RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
		157	_Predicate __pred,
		158	random_access_iterator_tag)
		159	{
		160	typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
		161	= (__last - __first) >> 2;
		162
		163	for ( ; __trip_count > 0 ; --__trip_count) {
		164	if (__pred(*__first)) return __first;
		165	++__first;
		166
		167	if (__pred(*__first)) return __first;
		168	++__first;
		169
		170	if (__pred(*__first)) return __first;
		171	++__first;
		172
		173	if (__pred(*__first)) return __first;
		174	++__first;
		175	}
		176
		177	switch(__last - __first) {
		178	case 3:
		179	if (__pred(*__first)) return __first;
		180	++__first;
		181	case 2:
		182	if (__pred(*__first)) return __first;
		183	++__first;
		184	case 1:
		185	if (__pred(*__first)) return __first;
		186	++__first;
		187	case 0:
		188	default:
		189	return __last;
		190	}
		191	}
		192
		193	template
		194	inline _InputIter find(_InputIter __first, _InputIter __last,
		195	const _Tp& __val)
		196	{
		197	// concept requirements
		198	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		199	__glibcpp_function_requires(_EqualOpConcept<
		200	typename iterator_traits<_InputIter>::value_type, _Tp>);
		201	return find(__first, __last, __val, __iterator_category(__first));
		202	}
		203
		204	template
		205	inline _InputIter find_if(_InputIter __first, _InputIter __last,
		206	_Predicate __pred)
		207	{
		208	// concept requirements
		209	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		210	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		211	typename iterator_traits<_InputIter>::value_type>);
		212	return find_if(__first, __last, __pred, __iterator_category(__first));
		213	}
		214
		215	// adjacent_find.
		216
		217	template
		218	_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last)
		219	{
		220	// concept requirements
		221	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		222	__glibcpp_function_requires(_EqualityComparableConcept<
		223	typename iterator_traits<_ForwardIter>::value_type>);
		224	if (__first == __last)
		225	return __last;
		226	_ForwardIter __next = __first;
		227	while(++__next != __last) {
		228	if (__first == __next)
		229	return __first;
		230	__first = __next;
		231	}
		232	return __last;
		233	}
		234
		235	template
		236	_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
		237	_BinaryPredicate __binary_pred)
		238	{
		239	// concept requirements
		240	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		241	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
		242	typename iterator_traits<_ForwardIter>::value_type,
		243	typename iterator_traits<_ForwardIter>::value_type>);
		244	if (__first == __last)
		245	return __last;
		246	_ForwardIter __next = __first;
		247	while(++__next != __last) {
		248	if (__binary_pred(__first, __next))
		249	return __first;
		250	__first = __next;
		251	}
		252	return __last;
		253	}
		254
		255	// count and count_if. There are two version of each, one whose return type
		256	// type is void and one (present only if we have partial specialization)
		257	// whose return type is iterator_traits<_InputIter>::difference_type. The
		258	// C++ standard only has the latter version, but the former, which was present
		259	// in the HP STL, is retained for backward compatibility.
		260
		261	template
		262	void count(_InputIter __first, _InputIter __last, const _Tp& __value,
		263	_Size& __n)
		264	{
		265	// concept requirements
		266	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		267	__glibcpp_function_requires(_EqualityComparableConcept<
		268	typename iterator_traits<_InputIter>::value_type >);
		269	__glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
		270	for ( ; __first != __last; ++__first)
		271	if (*__first == __value)
		272	++__n;
		273	}
		274
		275	template
		276	void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
		277	_Size& __n)
		278	{
		279	// concept requirements
		280	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		281	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		282	typename iterator_traits<_InputIter>::value_type>);
		283	for ( ; __first != __last; ++__first)
		284	if (__pred(*__first))
		285	++__n;
		286	}
		287
		288	template
		289	typename iterator_traits<_InputIter>::difference_type
		290	count(_InputIter __first, _InputIter __last, const _Tp& __value)
		291	{
		292	// concept requirements
		293	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		294	__glibcpp_function_requires(_EqualityComparableConcept<
		295	typename iterator_traits<_InputIter>::value_type >);
		296	__glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
		297	typename iterator_traits<_InputIter>::difference_type __n = 0;
		298	for ( ; __first != __last; ++__first)
		299	if (*__first == __value)
		300	++__n;
		301	return __n;
		302	}
		303
		304	template
		305	typename iterator_traits<_InputIter>::difference_type
		306	count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
		307	{
		308	// concept requirements
		309	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		310	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		311	typename iterator_traits<_InputIter>::value_type>);
		312	typename iterator_traits<_InputIter>::difference_type __n = 0;
		313	for ( ; __first != __last; ++__first)
		314	if (__pred(*__first))
		315	++__n;
		316	return __n;
		317	}
		318
		319
		320	// search.
		321
		322	template
		323	_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
		324	_ForwardIter2 __first2, _ForwardIter2 __last2)
		325	{
		326	// concept requirements
		327	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
		328	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
		329	__glibcpp_function_requires(_EqualOpConcept<
		330	typename iterator_traits<_ForwardIter1>::value_type,
		331	typename iterator_traits<_ForwardIter2>::value_type>);
		332
		333	// Test for empty ranges
		334	if (__first1 == __last1 \|\| __first2 == __last2)
		335	return __first1;
		336
		337	// Test for a pattern of length 1.
		338	_ForwardIter2 __tmp(__first2);
		339	++__tmp;
		340	if (__tmp == __last2)
		341	return find(__first1, __last1, *__first2);
		342
		343	// General case.
		344
		345	_ForwardIter2 __p1, __p;
		346
		347	__p1 = __first2; ++__p1;
		348
		349	_ForwardIter1 __current = __first1;
		350
		351	while (__first1 != __last1) {
		352	__first1 = find(__first1, __last1, *__first2);
		353	if (__first1 == __last1)
		354	return __last1;
		355
		356	__p = __p1;
		357	__current = __first1;
		358	if (++__current == __last1)
		359	return __last1;
		360
		361	while (__current == __p) {
		362	if (++__p == __last2)
		363	return __first1;
		364	if (++__current == __last1)
		365	return __last1;
		366	}
		367
		368	++__first1;
		369	}
		370	return __first1;
		371	}
		372
		373	template
		374	_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
		375	_ForwardIter2 __first2, _ForwardIter2 __last2,
		376	_BinaryPred __predicate)
		377	{
		378	// concept requirements
		379	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
		380	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
		381	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
		382	typename iterator_traits<_ForwardIter1>::value_type,
		383	typename iterator_traits<_ForwardIter2>::value_type>);
		384
		385	// Test for empty ranges
		386	if (__first1 == __last1 \|\| __first2 == __last2)
		387	return __first1;
		388
		389	// Test for a pattern of length 1.
		390	_ForwardIter2 __tmp(__first2);
		391	++__tmp;
		392	if (__tmp == __last2) {
		393	while (__first1 != __last1 && !__predicate(__first1, __first2))
		394	++__first1;
		395	return __first1;
		396	}
		397
		398	// General case.
		399
		400	_ForwardIter2 __p1, __p;
		401
		402	__p1 = __first2; ++__p1;
		403
		404	_ForwardIter1 __current = __first1;
		405
		406	while (__first1 != __last1) {
		407	while (__first1 != __last1) {
		408	if (__predicate(__first1, __first2))
		409	break;
		410	++__first1;
		411	}
		412	while (__first1 != __last1 && !__predicate(__first1, __first2))
		413	++__first1;
		414	if (__first1 == __last1)
		415	return __last1;
		416
		417	__p = __p1;
		418	__current = __first1;
		419	if (++__current == __last1) return __last1;
		420
		421	while (__predicate(__current, __p)) {
		422	if (++__p == __last2)
		423	return __first1;
		424	if (++__current == __last1)
		425	return __last1;
		426	}
		427
		428	++__first1;
		429	}
		430	return __first1;
		431	}
		432
		433	// search_n. Search for __count consecutive copies of __val.
		434
		435	template
		436	_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
		437	_Integer __count, const _Tp& __val)
		438	{
		439	// concept requirements
		440	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		441	__glibcpp_function_requires(_EqualityComparableConcept<
		442	typename iterator_traits<_ForwardIter>::value_type>);
		443	__glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
		444
		445	if (__count <= 0)
		446	return __first;
		447	else {
		448	__first = find(__first, __last, __val);
		449	while (__first != __last) {
		450	_Integer __n = __count - 1;
		451	_ForwardIter __i = __first;
		452	++__i;
		453	while (__i != __last && __n != 0 && *__i == __val) {
		454	++__i;
		455	--__n;
		456	}
		457	if (__n == 0)
		458	return __first;
		459	else
		460	__first = find(__i, __last, __val);
		461	}
		462	return __last;
		463	}
		464	}
		465
		466	template
		467	_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
		468	_Integer __count, const _Tp& __val,
		469	_BinaryPred __binary_pred)
		470	{
		471	// concept requirements
		472	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		473	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
		474	typename iterator_traits<_ForwardIter>::value_type, _Tp>);
		475
		476	if (__count <= 0)
		477	return __first;
		478	else {
		479	while (__first != __last) {
		480	if (__binary_pred(*__first, __val))
		481	break;
		482	++__first;
		483	}
		484	while (__first != __last) {
		485	_Integer __n = __count - 1;
		486	_ForwardIter __i = __first;
		487	++__i;
		488	while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
		489	++__i;
		490	--__n;
		491	}
		492	if (__n == 0)
		493	return __first;
		494	else {
		495	while (__i != __last) {
		496	if (__binary_pred(*__i, __val))
		497	break;
		498	++__i;
		499	}
		500	__first = __i;
		501	}
		502	}
		503	return __last;
		504	}
		505	}
		506
		507	// swap_ranges
		508
		509	template
		510	_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
		511	_ForwardIter2 __first2)
		512	{
		513	// concept requirements
		514	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>);
		515	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>);
		516	__glibcpp_function_requires(_ConvertibleConcept<
		517	typename iterator_traits<_ForwardIter1>::value_type,
		518	typename iterator_traits<_ForwardIter2>::value_type>);
		519	__glibcpp_function_requires(_ConvertibleConcept<
		520	typename iterator_traits<_ForwardIter2>::value_type,
		521	typename iterator_traits<_ForwardIter1>::value_type>);
		522
		523	for ( ; __first1 != __last1; ++__first1, ++__first2)
		524	iter_swap(__first1, __first2);
		525	return __first2;
		526	}
		527
		528	// transform
		529
		530	template
		531	_OutputIter transform(_InputIter __first, _InputIter __last,
		532	_OutputIter __result, _UnaryOperation __unary_op)
		533	{
		534	// concept requirements
		535	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		536	/* XXX
		537	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		538	// should be "the type returned by _UnaryOperation"
		539	typename iterator_traits<_InputIter>::value_type>);
		540	*/
		541
		542	for ( ; __first != __last; ++__first, ++__result)
		543	__result = __unary_op(__first);
		544	return __result;
		545	}
		546
		547	template
		548	class _BinaryOperation>
		549	_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
		550	_InputIter2 __first2, _OutputIter __result,
		551	_BinaryOperation __binary_op)
		552	{
		553	// concept requirements
		554	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		555	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		556	/* XXX
		557	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		558	// should be "the type returned by _BinaryOperation"
		559	typename iterator_traits<_InputIter1>::value_type>);
		560	*/
		561
		562	for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
		563	__result = __binary_op(__first1, *__first2);
		564	return __result;
		565	}
		566
		567	// replace, replace_if, replace_copy, replace_copy_if
		568
		569	template
		570	void replace(_ForwardIter __first, _ForwardIter __last,
		571	const _Tp& __old_value, const _Tp& __new_value)
		572	{
		573	// concept requirements
		574	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		575	__glibcpp_function_requires(_EqualOpConcept<
		576	typename iterator_traits<_ForwardIter>::value_type, _Tp>);
		577	__glibcpp_function_requires(_ConvertibleConcept<_Tp,
		578	typename iterator_traits<_ForwardIter>::value_type>);
		579
		580	for ( ; __first != __last; ++__first)
		581	if (*__first == __old_value)
		582	*__first = __new_value;
		583	}
		584
		585	template
		586	void replace_if(_ForwardIter __first, _ForwardIter __last,
		587	_Predicate __pred, const _Tp& __new_value)
		588	{
		589	// concept requirements
		590	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		591	__glibcpp_function_requires(_ConvertibleConcept<_Tp,
		592	typename iterator_traits<_ForwardIter>::value_type>);
		593	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		594	typename iterator_traits<_ForwardIter>::value_type>);
		595
		596	for ( ; __first != __last; ++__first)
		597	if (__pred(*__first))
		598	*__first = __new_value;
		599	}
		600
		601	template
		602	_OutputIter replace_copy(_InputIter __first, _InputIter __last,
		603	_OutputIter __result,
		604	const _Tp& __old_value, const _Tp& __new_value)
		605	{
		606	// concept requirements
		607	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		608	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		609	typename iterator_traits<_InputIter>::value_type>);
		610	__glibcpp_function_requires(_EqualOpConcept<
		611	typename iterator_traits<_InputIter>::value_type, _Tp>);
		612
		613	for ( ; __first != __last; ++__first, ++__result)
		614	__result = __first == __old_value ? __new_value : *__first;
		615	return __result;
		616	}
		617
		618	template
		619	_OutputIter replace_copy_if(_InputIter __first, _InputIter __last,
		620	_OutputIter __result,
		621	_Predicate __pred, const _Tp& __new_value)
		622	{
		623	// concept requirements
		624	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		625	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		626	typename iterator_traits<_InputIter>::value_type>);
		627	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		628	typename iterator_traits<_InputIter>::value_type>);
		629
		630	for ( ; __first != __last; ++__first, ++__result)
		631	__result = __pred(__first) ? __new_value : *__first;
		632	return __result;
		633	}
		634
		635	// generate and generate_n
		636
		637	template
		638	void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen)
		639	{
		640	// concept requirements
		641	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		642	__glibcpp_function_requires(_GeneratorConcept<_Generator,
		643	typename iterator_traits<_ForwardIter>::value_type>);
		644
		645	for ( ; __first != __last; ++__first)
		646	*__first = __gen();
		647	}
		648
		649	template
		650	_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen)
		651	{
		652	/*
		653	// XXX concept requirements
		654	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		655	"the return type of _Generator" ?? >);
		656	*/
		657
		658	for ( ; __n > 0; --__n, ++__first)
		659	*__first = __gen();
		660	return __first;
		661	}
		662
		663	// remove, remove_if, remove_copy, remove_copy_if
		664
		665	template
		666	_OutputIter remove_copy(_InputIter __first, _InputIter __last,
		667	_OutputIter __result, const _Tp& __value)
		668	{
		669	// concept requirements
		670	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		671	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		672	typename iterator_traits<_InputIter>::value_type>);
		673	__glibcpp_function_requires(_EqualOpConcept<
		674	typename iterator_traits<_InputIter>::value_type, _Tp>);
		675
		676	for ( ; __first != __last; ++__first)
		677	if (!(*__first == __value)) {
		678	__result = __first;
		679	++__result;
		680	}
		681	return __result;
		682	}
		683
		684	template
		685	_OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
		686	_OutputIter __result, _Predicate __pred)
		687	{
		688	// concept requirements
		689	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		690	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		691	typename iterator_traits<_InputIter>::value_type>);
		692	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		693	typename iterator_traits<_InputIter>::value_type>);
		694
		695	for ( ; __first != __last; ++__first)
		696	if (!__pred(*__first)) {
		697	__result = __first;
		698	++__result;
		699	}
		700	return __result;
		701	}
		702
		703	template
		704	_ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
		705	const _Tp& __value)
		706	{
		707	// concept requirements
		708	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		709	__glibcpp_function_requires(_ConvertibleConcept<_Tp,
		710	typename iterator_traits<_ForwardIter>::value_type>);
		711	__glibcpp_function_requires(_EqualOpConcept<
		712	typename iterator_traits<_ForwardIter>::value_type, _Tp>);
		713
		714	__first = find(__first, __last, __value);
		715	_ForwardIter __i = __first;
		716	return __first == __last ? __first
		717	: remove_copy(++__i, __last, __first, __value);
		718	}
		719
		720	template
		721	_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
		722	_Predicate __pred)
		723	{
		724	// concept requirements
		725	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		726	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		727	typename iterator_traits<_ForwardIter>::value_type>);
		728
		729	__first = find_if(__first, __last, __pred);
		730	_ForwardIter __i = __first;
		731	return __first == __last ? __first
		732	: remove_copy_if(++__i, __last, __first, __pred);
		733	}
		734
		735	// unique and unique_copy
		736
		737	template
		738	_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
		739	_OutputIter __result, _Tp*)
		740	{
		741	// concept requirements -- taken care of in dispatching function
		742	_Tp __value = *__first;
		743	*__result = __value;
		744	while (++__first != __last)
		745	if (!(__value == *__first)) {
		746	__value = *__first;
		747	*++__result = __value;
		748	}
		749	return ++__result;
		750	}
		751
		752	template
		753	inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
		754	_OutputIter __result,
		755	output_iterator_tag)
		756	{
		757	// concept requirements -- taken care of in dispatching function
		758	return __unique_copy(__first, __last, __result, __value_type(__first));
		759	}
		760
		761	template
		762	_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
		763	_ForwardIter __result, forward_iterator_tag)
		764	{
		765	// concept requirements -- taken care of in dispatching function
		766	__result = __first;
		767	while (++__first != __last)
		768	if (!(__result == __first))
		769	++__result = __first;
		770	return ++__result;
		771	}
		772
		773	template
		774	inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
		775	_OutputIter __result)
		776	{
		777	// concept requirements
		778	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		779	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		780	typename iterator_traits<_InputIter>::value_type>);
		781	__glibcpp_function_requires(_EqualityComparableConcept<
		782	typename iterator_traits<_InputIter>::value_type>);
		783
		784	if (__first == __last) return __result;
		785	return __unique_copy(__first, __last, __result,
		786	__iterator_category(__result));
		787	}
		788
		789	template
		790	class _Tp>
		791	_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
		792	_OutputIter __result,
		793	_BinaryPredicate __binary_pred, _Tp*)
		794	{
		795	// concept requirements -- iterators already checked
		796	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, _Tp, _Tp>);
		797
		798	_Tp __value = *__first;
		799	*__result = __value;
		800	while (++__first != __last)
		801	if (!__binary_pred(__value, *__first)) {
		802	__value = *__first;
		803	*++__result = __value;
		804	}
		805	return ++__result;
		806	}
		807
		808	template
		809	inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
		810	_OutputIter __result,
		811	_BinaryPredicate __binary_pred,
		812	output_iterator_tag)
		813	{
		814	// concept requirements -- taken care of in dispatching function
		815	return __unique_copy(__first, __last, __result, __binary_pred,
		816	__value_type(__first));
		817	}
		818
		819	template
		820	_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
		821	_ForwardIter __result,
		822	_BinaryPredicate __binary_pred,
		823	forward_iterator_tag)
		824	{
		825	// concept requirements -- iterators already checked
		826	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
		827	typename iterator_traits<_ForwardIter>::value_type,
		828	typename iterator_traits<_InputIter>::value_type>);
		829
		830	__result = __first;
		831	while (++__first != __last)
		832	if (!__binary_pred(__result, __first)) ++__result = __first;
		833	return ++__result;
		834	}
		835
		836	template
		837	inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
		838	_OutputIter __result,
		839	_BinaryPredicate __binary_pred)
		840	{
		841	// concept requirements -- predicates checked later
		842	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		843	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		844	typename iterator_traits<_InputIter>::value_type>);
		845
		846	if (__first == __last) return __result;
		847	return __unique_copy(__first, __last, __result, __binary_pred,
		848	__iterator_category(__result));
		849	}
		850
		851	template
		852	_ForwardIter unique(_ForwardIter __first, _ForwardIter __last)
		853	{
		854	// concept requirements
		855	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		856	__glibcpp_function_requires(_EqualityComparableConcept<
		857	typename iterator_traits<_ForwardIter>::value_type>);
		858
		859	__first = adjacent_find(__first, __last);
		860	return unique_copy(__first, __last, __first);
		861	}
		862
		863	template
		864	_ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
		865	_BinaryPredicate __binary_pred)
		866	{
		867	// concept requirements
		868	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		869	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
		870	typename iterator_traits<_ForwardIter>::value_type,
		871	typename iterator_traits<_ForwardIter>::value_type>);
		872
		873	__first = adjacent_find(__first, __last, __binary_pred);
		874	return unique_copy(__first, __last, __first, __binary_pred);
		875	}
		876
		877	// reverse and reverse_copy, and their auxiliary functions
		878
		879	template
		880	void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
		881	bidirectional_iterator_tag) {
		882	while (true)
		883	if (__first == __last \|\| __first == --__last)
		884	return;
		885	else
		886	iter_swap(__first++, __last);
		887	}
		888
		889	template
		890	void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
		891	random_access_iterator_tag) {
		892	while (__first < __last)
		893	iter_swap(__first++, --__last);
		894	}
		895
		896	template
		897	inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last)
		898	{
		899	// concept requirements
		900	__glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
		901	_BidirectionalIter>);
		902	__reverse(__first, __last, __iterator_category(__first));
		903	}
		904
		905	template
		906	_OutputIter reverse_copy(_BidirectionalIter __first,
		907	_BidirectionalIter __last,
		908	_OutputIter __result)
		909	{
		910	// concept requirements
		911	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
		912	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		913	typename iterator_traits<_BidirectionalIter>::value_type>);
		914
		915	while (__first != __last) {
		916	--__last;
		917	__result = __last;
		918	++__result;
		919	}
		920	return __result;
		921	}
		922
		923	// rotate and rotate_copy, and their auxiliary functions
		924
		925	template
		926	_EuclideanRingElement __gcd(_EuclideanRingElement __m,
		927	_EuclideanRingElement __n)
		928	{
		929	while (__n != 0) {
		930	_EuclideanRingElement __t = __m % __n;
		931	__m = __n;
		932	__n = __t;
		933	}
		934	return __m;
		935	}
		936
		937	template
		938	_ForwardIter __rotate(_ForwardIter __first,
		939	_ForwardIter __middle,
		940	_ForwardIter __last,
		941	_Distance*,
		942	forward_iterator_tag)
		943	{
		944	if (__first == __middle)
		945	return __last;
		946	if (__last == __middle)
		947	return __first;
		948
		949	_ForwardIter __first2 = __middle;
		950	do {
		951	swap(__first++, __first2++);
		952	if (__first == __middle)
		953	__middle = __first2;
		954	} while (__first2 != __last);
		955
		956	_ForwardIter __new_middle = __first;
		957
		958	__first2 = __middle;
		959
		960	while (__first2 != __last) {
		961	swap (__first++, __first2++);
		962	if (__first == __middle)
		963	__middle = __first2;
		964	else if (__first2 == __last)
		965	__first2 = __middle;
		966	}
		967
		968	return __new_middle;
		969	}
		970
		971
		972	template
		973	_BidirectionalIter __rotate(_BidirectionalIter __first,
		974	_BidirectionalIter __middle,
		975	_BidirectionalIter __last,
		976	_Distance*,
		977	bidirectional_iterator_tag)
		978	{
		979	// concept requirements
		980	__glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
		981	_BidirectionalIter>);
		982
		983	if (__first == __middle)
		984	return __last;
		985	if (__last == __middle)
		986	return __first;
		987
		988	__reverse(__first, __middle, bidirectional_iterator_tag());
		989	__reverse(__middle, __last, bidirectional_iterator_tag());
		990
		991	while (__first != __middle && __middle != __last)
		992	swap (__first++, --__last);
		993
		994	if (__first == __middle) {
		995	__reverse(__middle, __last, bidirectional_iterator_tag());
		996	return __last;
		997	}
		998	else {
		999	__reverse(__first, __middle, bidirectional_iterator_tag());
		1000	return __first;
		1001	}
		1002	}
		1003
		1004	template
		1005	_RandomAccessIter __rotate(_RandomAccessIter __first,
		1006	_RandomAccessIter __middle,
		1007	_RandomAccessIter __last,
		1008	_Distance , _Tp )
		1009	{
		1010	// concept requirements
		1011	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1012	_RandomAccessIter>);
		1013
		1014	_Distance __n = __last - __first;
		1015	_Distance __k = __middle - __first;
		1016	_Distance __l = __n - __k;
		1017	_RandomAccessIter __result = __first + (__last - __middle);
		1018
		1019	if (__k == 0)
		1020	return __last;
		1021
		1022	else if (__k == __l) {
		1023	swap_ranges(__first, __middle, __middle);
		1024	return __result;
		1025	}
		1026
		1027	_Distance __d = __gcd(__n, __k);
		1028
		1029	for (_Distance __i = 0; __i < __d; __i++) {
		1030	_Tp __tmp = *__first;
		1031	_RandomAccessIter __p = __first;
		1032
		1033	if (__k < __l) {
		1034	for (_Distance __j = 0; __j < __l/__d; __j++) {
		1035	if (__p > __first + __l) {
		1036	__p = (__p - __l);
		1037	__p -= __l;
		1038	}
		1039
		1040	__p = (__p + __k);
		1041	__p += __k;
		1042	}
		1043	}
		1044
		1045	else {
		1046	for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
		1047	if (__p < __last - __k) {
		1048	__p = (__p + __k);
		1049	__p += __k;
		1050	}
		1051
		1052	__p = (__p - __l);
		1053	__p -= __l;
		1054	}
		1055	}
		1056
		1057	*__p = __tmp;
		1058	++__first;
		1059	}
		1060
		1061	return __result;
		1062	}
		1063
		1064	template
		1065	inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
		1066	_ForwardIter __last)
		1067	{
		1068	// concept requirements
		1069	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		1070
		1071	return __rotate(__first, __middle, __last,
		1072	__distance_type(__first),
		1073	__iterator_category(__first));
		1074	}
		1075
		1076	template
		1077	_OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
		1078	_ForwardIter __last, _OutputIter __result)
		1079	{
		1080	// concept requirements
		1081	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		1082	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		1083	typename iterator_traits<_ForwardIter>::value_type>);
		1084
		1085	return copy(__first, __middle, copy(__middle, __last, __result));
		1086	}
		1087
		1088	// Return a random number in the range [0, __n). This function encapsulates
		1089	// whether we're using rand (part of the standard C library) or lrand48
		1090	// (not standard, but a much better choice whenever it's available).
		1091	template
		1092	inline _Distance __random_number(_Distance __n) {
		1093	#ifdef _GLIBCPP_HAVE_DRAND48
		1094	return lrand48() % __n;
		1095	#else
		1096	return rand() % __n;
		1097	#endif
		1098	}
		1099
		1100	// random_shuffle
		1101
		1102	template
		1103	inline void random_shuffle(_RandomAccessIter __first,
		1104	_RandomAccessIter __last)
		1105	{
		1106	// concept requirements
		1107	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1108	_RandomAccessIter>);
		1109
		1110	if (__first == __last) return;
		1111	for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
		1112	iter_swap(__i, __first + __random_number((__i - __first) + 1));
		1113	}
		1114
		1115	template
		1116	void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
		1117	_RandomNumberGenerator& __rand)
		1118	{
		1119	// concept requirements
		1120	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1121	_RandomAccessIter>);
		1122
		1123	if (__first == __last) return;
		1124	for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
		1125	iter_swap(__i, __first + __rand((__i - __first) + 1));
		1126	}
		1127
		1128	// random_sample and random_sample_n (extensions, not part of the standard).
		1129
		1130	template
		1131	_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
		1132	_OutputIter __out, const _Distance __n)
		1133	{
		1134	// concept requirements
		1135	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		1136	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		1137	typename iterator_traits<_ForwardIter>::value_type>);
		1138
		1139	_Distance __remaining = 0;
		1140	distance(__first, __last, __remaining);
		1141	_Distance __m = min(__n, __remaining);
		1142
		1143	while (__m > 0) {
		1144	if (__random_number(__remaining) < __m) {
		1145	__out = __first;
		1146	++__out;
		1147	--__m;
		1148	}
		1149
		1150	--__remaining;
		1151	++__first;
		1152	}
		1153	return __out;
		1154	}
		1155
		1156	template
		1157	class _RandomNumberGenerator>
		1158	_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
		1159	_OutputIter __out, const _Distance __n,
		1160	_RandomNumberGenerator& __rand)
		1161	{
		1162	// concept requirements
		1163	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		1164	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		1165	typename iterator_traits<_ForwardIter>::value_type>);
		1166	__glibcpp_function_requires(_UnaryFunctionConcept<
		1167	_RandomNumberGenerator, _Distance, _Distance>);
		1168
		1169	_Distance __remaining = 0;
		1170	distance(__first, __last, __remaining);
		1171	_Distance __m = min(__n, __remaining);
		1172
		1173	while (__m > 0) {
		1174	if (__rand(__remaining) < __m) {
		1175	__out = __first;
		1176	++__out;
		1177	--__m;
		1178	}
		1179
		1180	--__remaining;
		1181	++__first;
		1182	}
		1183	return __out;
		1184	}
		1185
		1186	template
		1187	_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
		1188	_RandomAccessIter __out,
		1189	const _Distance __n)
		1190	{
		1191	_Distance __m = 0;
		1192	_Distance __t = __n;
		1193	for ( ; __first != __last && __m < __n; ++__m, ++__first)
		1194	__out[__m] = *__first;
		1195
		1196	while (__first != __last) {
		1197	++__t;
		1198	_Distance __M = __random_number(__t);
		1199	if (__M < __n)
		1200	__out[__M] = *__first;
		1201	++__first;
		1202	}
		1203
		1204	return __out + __m;
		1205	}
		1206
		1207	template
		1208	class _RandomNumberGenerator, class _Distance>
		1209	_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
		1210	_RandomAccessIter __out,
		1211	_RandomNumberGenerator& __rand,
		1212	const _Distance __n)
		1213	{
		1214	// concept requirements
		1215	__glibcpp_function_requires(_UnaryFunctionConcept<
		1216	_RandomNumberGenerator, _Distance, _Distance>);
		1217
		1218	_Distance __m = 0;
		1219	_Distance __t = __n;
		1220	for ( ; __first != __last && __m < __n; ++__m, ++__first)
		1221	__out[__m] = *__first;
		1222
		1223	while (__first != __last) {
		1224	++__t;
		1225	_Distance __M = __rand(__t);
		1226	if (__M < __n)
		1227	__out[__M] = *__first;
		1228	++__first;
		1229	}
		1230
		1231	return __out + __m;
		1232	}
		1233
		1234	template
		1235	inline _RandomAccessIter
		1236	random_sample(_InputIter __first, _InputIter __last,
		1237	_RandomAccessIter __out_first, _RandomAccessIter __out_last)
		1238	{
		1239	// concept requirements
		1240	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		1241	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1242	_RandomAccessIter>);
		1243
		1244	return __random_sample(__first, __last,
		1245	__out_first, __out_last - __out_first);
		1246	}
		1247
		1248
		1249	template
		1250	class _RandomNumberGenerator>
		1251	inline _RandomAccessIter
		1252	random_sample(_InputIter __first, _InputIter __last,
		1253	_RandomAccessIter __out_first, _RandomAccessIter __out_last,
		1254	_RandomNumberGenerator& __rand)
		1255	{
		1256	// concept requirements
		1257	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		1258	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1259	_RandomAccessIter>);
		1260
		1261	return __random_sample(__first, __last,
		1262	__out_first, __rand,
		1263	__out_last - __out_first);
		1264	}
		1265
		1266	// partition, stable_partition, and their auxiliary functions
		1267
		1268	template
		1269	_ForwardIter __partition(_ForwardIter __first,
		1270	_ForwardIter __last,
		1271	_Predicate __pred,
		1272	forward_iterator_tag)
		1273	{
		1274	if (__first == __last) return __first;
		1275
		1276	while (__pred(*__first))
		1277	if (++__first == __last) return __first;
		1278
		1279	_ForwardIter __next = __first;
		1280
		1281	while (++__next != __last)
		1282	if (__pred(*__next)) {
		1283	swap(__first, __next);
		1284	++__first;
		1285	}
		1286
		1287	return __first;
		1288	}
		1289
		1290	template
		1291	_BidirectionalIter __partition(_BidirectionalIter __first,
		1292	_BidirectionalIter __last,
		1293	_Predicate __pred,
		1294	bidirectional_iterator_tag)
		1295	{
		1296	while (true) {
		1297	while (true)
		1298	if (__first == __last)
		1299	return __first;
		1300	else if (__pred(*__first))
		1301	++__first;
		1302	else
		1303	break;
		1304	--__last;
		1305	while (true)
		1306	if (__first == __last)
		1307	return __first;
		1308	else if (!__pred(*__last))
		1309	--__last;
		1310	else
		1311	break;
		1312	iter_swap(__first, __last);
		1313	++__first;
		1314	}
		1315	}
		1316
		1317	template
		1318	inline _ForwardIter partition(_ForwardIter __first,
		1319	_ForwardIter __last,
		1320	_Predicate __pred)
		1321	{
		1322	// concept requirements
		1323	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		1324	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		1325	typename iterator_traits<_ForwardIter>::value_type>);
		1326
		1327	return __partition(__first, __last, __pred, __iterator_category(__first));
		1328	}
		1329
		1330
		1331	template
		1332	_ForwardIter __inplace_stable_partition(_ForwardIter __first,
		1333	_ForwardIter __last,
		1334	_Predicate __pred, _Distance __len)
		1335	{
		1336	if (__len == 1)
		1337	return __pred(*__first) ? __last : __first;
		1338	_ForwardIter __middle = __first;
		1339	advance(__middle, __len / 2);
		1340	return rotate(__inplace_stable_partition(__first, __middle, __pred,
		1341	__len / 2),
		1342	__middle,
		1343	__inplace_stable_partition(__middle, __last, __pred,
		1344	__len - __len / 2));
		1345	}
		1346
		1347	template
		1348	class _Distance>
		1349	_ForwardIter __stable_partition_adaptive(_ForwardIter __first,
		1350	_ForwardIter __last,
		1351	_Predicate __pred, _Distance __len,
		1352	_Pointer __buffer,
		1353	_Distance __buffer_size)
		1354	{
		1355	if (__len <= __buffer_size) {
		1356	_ForwardIter __result1 = __first;
		1357	_Pointer __result2 = __buffer;
		1358	for ( ; __first != __last ; ++__first)
		1359	if (__pred(*__first)) {
		1360	__result1 = __first;
		1361	++__result1;
		1362	}
		1363	else {
		1364	__result2 = __first;
		1365	++__result2;
		1366	}
		1367	copy(__buffer, __result2, __result1);
		1368	return __result1;
		1369	}
		1370	else {
		1371	_ForwardIter __middle = __first;
		1372	advance(__middle, __len / 2);
		1373	return rotate(__stable_partition_adaptive(
		1374	__first, __middle, __pred,
		1375	__len / 2, __buffer, __buffer_size),
		1376	__middle,
		1377	__stable_partition_adaptive(
		1378	__middle, __last, __pred,
		1379	__len - __len / 2, __buffer, __buffer_size));
		1380	}
		1381	}
		1382
		1383	template
		1384	inline _ForwardIter
		1385	__stable_partition_aux(_ForwardIter __first, _ForwardIter __last,
		1386	_Predicate __pred, _Tp, _Distance)
		1387	{
		1388	_Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
		1389	if (__buf.size() > 0)
		1390	return __stable_partition_adaptive(__first, __last, __pred,
		1391	_Distance(__buf.requested_size()),
		1392	__buf.begin(), __buf.size());
		1393	else
		1394	return __inplace_stable_partition(__first, __last, __pred,
		1395	_Distance(__buf.requested_size()));
		1396	}
		1397
		1398	template
		1399	inline _ForwardIter stable_partition(_ForwardIter __first,
		1400	_ForwardIter __last,
		1401	_Predicate __pred)
		1402	{
		1403	// concept requirements
		1404	__glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>);
		1405	__glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
		1406	typename iterator_traits<_ForwardIter>::value_type>);
		1407
		1408	if (__first == __last)
		1409	return __first;
		1410	else
		1411	return __stable_partition_aux(__first, __last, __pred,
		1412	__value_type(__first),
		1413	__distance_type(__first));
		1414	}
		1415
		1416	template
		1417	_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
		1418	_RandomAccessIter __last,
		1419	_Tp __pivot)
		1420	{
		1421	while (true) {
		1422	while (*__first < __pivot)
		1423	++__first;
		1424	--__last;
		1425	while (__pivot < *__last)
		1426	--__last;
		1427	if (!(__first < __last))
		1428	return __first;
		1429	iter_swap(__first, __last);
		1430	++__first;
		1431	}
		1432	}
		1433
		1434	template
		1435	_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
		1436	_RandomAccessIter __last,
		1437	_Tp __pivot, _Compare __comp)
		1438	{
		1439	while (true) {
		1440	while (__comp(*__first, __pivot))
		1441	++__first;
		1442	--__last;
		1443	while (__comp(__pivot, *__last))
		1444	--__last;
		1445	if (!(__first < __last))
		1446	return __first;
		1447	iter_swap(__first, __last);
		1448	++__first;
		1449	}
		1450	}
		1451
		1452	const int __stl_threshold = 16;
		1453
		1454	// sort() and its auxiliary functions.
		1455
		1456	template
		1457	void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val)
		1458	{
		1459	_RandomAccessIter __next = __last;
		1460	--__next;
		1461	while (__val < *__next) {
		1462	__last = __next;
		1463	__last = __next;
		1464	--__next;
		1465	}
		1466	*__last = __val;
		1467	}
		1468
		1469	template
		1470	void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
		1471	_Compare __comp)
		1472	{
		1473	_RandomAccessIter __next = __last;
		1474	--__next;
		1475	while (__comp(__val, *__next)) {
		1476	__last = __next;
		1477	__last = __next;
		1478	--__next;
		1479	}
		1480	*__last = __val;
		1481	}
		1482
		1483	template
		1484	inline void __linear_insert(_RandomAccessIter __first,
		1485	_RandomAccessIter __last, _Tp*)
		1486	{
		1487	_Tp __val = *__last;
		1488	if (__val < *__first) {
		1489	copy_backward(__first, __last, __last + 1);
		1490	*__first = __val;
		1491	}
		1492	else
		1493	__unguarded_linear_insert(__last, __val);
		1494	}
		1495
		1496	template
		1497	inline void __linear_insert(_RandomAccessIter __first,
		1498	_RandomAccessIter __last, _Tp*, _Compare __comp)
		1499	{
		1500	_Tp __val = *__last;
		1501	if (__comp(__val, *__first)) {
		1502	copy_backward(__first, __last, __last + 1);
		1503	*__first = __val;
		1504	}
		1505	else
		1506	__unguarded_linear_insert(__last, __val, __comp);
		1507	}
		1508
		1509	template
		1510	void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last)
		1511	{
		1512	if (__first == __last) return;
		1513	for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
		1514	__linear_insert(__first, __i, __value_type(__first));
		1515	}
		1516
		1517	template
		1518	void __insertion_sort(_RandomAccessIter __first,
		1519	_RandomAccessIter __last, _Compare __comp)
		1520	{
		1521	if (__first == __last) return;
		1522	for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
		1523	__linear_insert(__first, __i, __value_type(__first), __comp);
		1524	}
		1525
		1526	template
		1527	void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
		1528	_RandomAccessIter __last, _Tp*)
		1529	{
		1530	for (_RandomAccessIter __i = __first; __i != __last; ++__i)
		1531	__unguarded_linear_insert(__i, _Tp(*__i));
		1532	}
		1533
		1534	template
		1535	inline void __unguarded_insertion_sort(_RandomAccessIter __first,
		1536	_RandomAccessIter __last) {
		1537	__unguarded_insertion_sort_aux(__first, __last, __value_type(__first));
		1538	}
		1539
		1540	template
		1541	void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
		1542	_RandomAccessIter __last,
		1543	_Tp*, _Compare __comp)
		1544	{
		1545	for (_RandomAccessIter __i = __first; __i != __last; ++__i)
		1546	__unguarded_linear_insert(__i, _Tp(*__i), __comp);
		1547	}
		1548
		1549	template
		1550	inline void __unguarded_insertion_sort(_RandomAccessIter __first,
		1551	_RandomAccessIter __last,
		1552	_Compare __comp)
		1553	{
		1554	__unguarded_insertion_sort_aux(__first, __last, __value_type(__first),
		1555	__comp);
		1556	}
		1557
		1558	template
		1559	void __final_insertion_sort(_RandomAccessIter __first,
		1560	_RandomAccessIter __last)
		1561	{
		1562	if (__last - __first > __stl_threshold) {
		1563	__insertion_sort(__first, __first + __stl_threshold);
		1564	__unguarded_insertion_sort(__first + __stl_threshold, __last);
		1565	}
		1566	else
		1567	__insertion_sort(__first, __last);
		1568	}
		1569
		1570	template
		1571	void __final_insertion_sort(_RandomAccessIter __first,
		1572	_RandomAccessIter __last, _Compare __comp)
		1573	{
		1574	if (__last - __first > __stl_threshold) {
		1575	__insertion_sort(__first, __first + __stl_threshold, __comp);
		1576	__unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
		1577	}
		1578	else
		1579	__insertion_sort(__first, __last, __comp);
		1580	}
		1581
		1582	template
		1583	inline _Size __lg(_Size __n)
		1584	{
		1585	_Size __k;
		1586	for (__k = 0; __n != 1; __n >>= 1) ++__k;
		1587	return __k;
		1588	}
		1589
		1590	template
		1591	void __introsort_loop(_RandomAccessIter __first,
		1592	_RandomAccessIter __last, _Tp*,
		1593	_Size __depth_limit)
		1594	{
		1595	while (__last - __first > __stl_threshold) {
		1596	if (__depth_limit == 0) {
		1597	partial_sort(__first, __last, __last);
		1598	return;
		1599	}
		1600	--__depth_limit;
		1601	_RandomAccessIter __cut =
		1602	__unguarded_partition(__first, __last,
		1603	_Tp(__median(*__first,
		1604	*(__first + (__last - __first)/2),
		1605	*(__last - 1))));
		1606	__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);
		1607	__last = __cut;
		1608	}
		1609	}
		1610
		1611	template
		1612	void __introsort_loop(_RandomAccessIter __first,
		1613	_RandomAccessIter __last, _Tp*,
		1614	_Size __depth_limit, _Compare __comp)
		1615	{
		1616	while (__last - __first > __stl_threshold) {
		1617	if (__depth_limit == 0) {
		1618	partial_sort(__first, __last, __last, __comp);
		1619	return;
		1620	}
		1621	--__depth_limit;
		1622	_RandomAccessIter __cut =
		1623	__unguarded_partition(__first, __last,
		1624	_Tp(__median(*__first,
		1625	*(__first + (__last - __first)/2),
		1626	*(__last - 1), __comp)),
		1627	__comp);
		1628	__introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
		1629	__last = __cut;
		1630	}
		1631	}
		1632
		1633	template
		1634	inline void sort(_RandomAccessIter __first, _RandomAccessIter __last)
		1635	{
		1636	// concept requirements
		1637	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1638	_RandomAccessIter>);
		1639	__glibcpp_function_requires(_LessThanComparableConcept<
		1640	typename iterator_traits<_RandomAccessIter>::value_type>);
		1641
		1642	if (__first != __last) {
		1643	__introsort_loop(__first, __last,
		1644	__value_type(__first),
		1645	__lg(__last - __first) * 2);
		1646	__final_insertion_sort(__first, __last);
		1647	}
		1648	}
		1649
		1650	template
		1651	inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
		1652	_Compare __comp)
		1653	{
		1654	// concept requirements
		1655	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1656	_RandomAccessIter>);
		1657	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		1658	typename iterator_traits<_RandomAccessIter>::value_type,
		1659	typename iterator_traits<_RandomAccessIter>::value_type>);
		1660
		1661	if (__first != __last) {
		1662	__introsort_loop(__first, __last,
		1663	__value_type(__first),
		1664	__lg(__last - __first) * 2,
		1665	__comp);
		1666	__final_insertion_sort(__first, __last, __comp);
		1667	}
		1668	}
		1669
		1670	// stable_sort() and its auxiliary functions.
		1671
		1672	template
		1673	void __inplace_stable_sort(_RandomAccessIter __first,
		1674	_RandomAccessIter __last)
		1675	{
		1676	if (__last - __first < 15) {
		1677	__insertion_sort(__first, __last);
		1678	return;
		1679	}
		1680	_RandomAccessIter __middle = __first + (__last - __first) / 2;
		1681	__inplace_stable_sort(__first, __middle);
		1682	__inplace_stable_sort(__middle, __last);
		1683	__merge_without_buffer(__first, __middle, __last,
		1684	__middle - __first,
		1685	__last - __middle);
		1686	}
		1687
		1688	template
		1689	void __inplace_stable_sort(_RandomAccessIter __first,
		1690	_RandomAccessIter __last, _Compare __comp)
		1691	{
		1692	if (__last - __first < 15) {
		1693	__insertion_sort(__first, __last, __comp);
		1694	return;
		1695	}
		1696	_RandomAccessIter __middle = __first + (__last - __first) / 2;
		1697	__inplace_stable_sort(__first, __middle, __comp);
		1698	__inplace_stable_sort(__middle, __last, __comp);
		1699	__merge_without_buffer(__first, __middle, __last,
		1700	__middle - __first,
		1701	__last - __middle,
		1702	__comp);
		1703	}
		1704
		1705	template
		1706	class _Distance>
		1707	void __merge_sort_loop(_RandomAccessIter1 __first,
		1708	_RandomAccessIter1 __last,
		1709	_RandomAccessIter2 __result, _Distance __step_size)
		1710	{
		1711	_Distance __two_step = 2 * __step_size;
		1712
		1713	while (__last - __first >= __two_step) {
		1714	__result = merge(__first, __first + __step_size,
		1715	__first + __step_size, __first + __two_step,
		1716	__result);
		1717	__first += __two_step;
		1718	}
		1719
		1720	__step_size = min(_Distance(__last - __first), __step_size);
		1721	merge(__first, __first + __step_size, __first + __step_size, __last,
		1722	__result);
		1723	}
		1724
		1725	template
		1726	class _Distance, class _Compare>
		1727	void __merge_sort_loop(_RandomAccessIter1 __first,
		1728	_RandomAccessIter1 __last,
		1729	_RandomAccessIter2 __result, _Distance __step_size,
		1730	_Compare __comp)
		1731	{
		1732	_Distance __two_step = 2 * __step_size;
		1733
		1734	while (__last - __first >= __two_step) {
		1735	__result = merge(__first, __first + __step_size,
		1736	__first + __step_size, __first + __two_step,
		1737	__result,
		1738	__comp);
		1739	__first += __two_step;
		1740	}
		1741	__step_size = min(_Distance(__last - __first), __step_size);
		1742
		1743	merge(__first, __first + __step_size,
		1744	__first + __step_size, __last,
		1745	__result,
		1746	__comp);
		1747	}
		1748
		1749	const int __stl_chunk_size = 7;
		1750
		1751	template
		1752	void __chunk_insertion_sort(_RandomAccessIter __first,
		1753	_RandomAccessIter __last, _Distance __chunk_size)
		1754	{
		1755	while (__last - __first >= __chunk_size) {
		1756	__insertion_sort(__first, __first + __chunk_size);
		1757	__first += __chunk_size;
		1758	}
		1759	__insertion_sort(__first, __last);
		1760	}
		1761
		1762	template
		1763	void __chunk_insertion_sort(_RandomAccessIter __first,
		1764	_RandomAccessIter __last,
		1765	_Distance __chunk_size, _Compare __comp)
		1766	{
		1767	while (__last - __first >= __chunk_size) {
		1768	__insertion_sort(__first, __first + __chunk_size, __comp);
		1769	__first += __chunk_size;
		1770	}
		1771	__insertion_sort(__first, __last, __comp);
		1772	}
		1773
		1774	template
		1775	void __merge_sort_with_buffer(_RandomAccessIter __first,
		1776	_RandomAccessIter __last,
		1777	_Pointer __buffer, _Distance*)
		1778	{
		1779	_Distance __len = __last - __first;
		1780	_Pointer __buffer_last = __buffer + __len;
		1781
		1782	_Distance __step_size = __stl_chunk_size;
		1783	__chunk_insertion_sort(__first, __last, __step_size);
		1784
		1785	while (__step_size < __len) {
		1786	__merge_sort_loop(__first, __last, __buffer, __step_size);
		1787	__step_size *= 2;
		1788	__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
		1789	__step_size *= 2;
		1790	}
		1791	}
		1792
		1793	template
		1794	class _Compare>
		1795	void __merge_sort_with_buffer(_RandomAccessIter __first,
		1796	_RandomAccessIter __last, _Pointer __buffer,
		1797	_Distance*, _Compare __comp)
		1798	{
		1799	_Distance __len = __last - __first;
		1800	_Pointer __buffer_last = __buffer + __len;
		1801
		1802	_Distance __step_size = __stl_chunk_size;
		1803	__chunk_insertion_sort(__first, __last, __step_size, __comp);
		1804
		1805	while (__step_size < __len) {
		1806	__merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
		1807	__step_size *= 2;
		1808	__merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
		1809	__step_size *= 2;
		1810	}
		1811	}
		1812
		1813	template
		1814	void __stable_sort_adaptive(_RandomAccessIter __first,
		1815	_RandomAccessIter __last, _Pointer __buffer,
		1816	_Distance __buffer_size)
		1817	{
		1818	_Distance __len = (__last - __first + 1) / 2;
		1819	_RandomAccessIter __middle = __first + __len;
		1820	if (__len > __buffer_size) {
		1821	__stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
		1822	__stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
		1823	}
		1824	else {
		1825	__merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);
		1826	__merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);
		1827	}
		1828	__merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
		1829	_Distance(__last - __middle), __buffer, __buffer_size);
		1830	}
		1831
		1832	template
		1833	class _Compare>
		1834	void __stable_sort_adaptive(_RandomAccessIter __first,
		1835	_RandomAccessIter __last, _Pointer __buffer,
		1836	_Distance __buffer_size, _Compare __comp)
		1837	{
		1838	_Distance __len = (__last - __first + 1) / 2;
		1839	_RandomAccessIter __middle = __first + __len;
		1840	if (__len > __buffer_size) {
		1841	__stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
		1842	__comp);
		1843	__stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
		1844	__comp);
		1845	}
		1846	else {
		1847	__merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
		1848	__comp);
		1849	__merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
		1850	__comp);
		1851	}
		1852	__merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
		1853	_Distance(__last - __middle), __buffer, __buffer_size,
		1854	__comp);
		1855	}
		1856
		1857	template
		1858	inline void __stable_sort_aux(_RandomAccessIter __first,
		1859	_RandomAccessIter __last, _Tp, _Distance)
		1860	{
		1861	_Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
		1862	if (buf.begin() == 0)
		1863	__inplace_stable_sort(__first, __last);
		1864	else
		1865	__stable_sort_adaptive(__first, __last, buf.begin(),
		1866	_Distance(buf.size()));
		1867	}
		1868
		1869	template
		1870	inline void __stable_sort_aux(_RandomAccessIter __first,
		1871	_RandomAccessIter __last, _Tp, _Distance,
		1872	_Compare __comp)
		1873	{
		1874	_Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
		1875	if (buf.begin() == 0)
		1876	__inplace_stable_sort(__first, __last, __comp);
		1877	else
		1878	__stable_sort_adaptive(__first, __last, buf.begin(),
		1879	_Distance(buf.size()),
		1880	__comp);
		1881	}
		1882
		1883	template
		1884	inline void stable_sort(_RandomAccessIter __first,
		1885	_RandomAccessIter __last)
		1886	{
		1887	// concept requirements
		1888	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1889	_RandomAccessIter>);
		1890	__glibcpp_function_requires(_LessThanComparableConcept<
		1891	typename iterator_traits<_RandomAccessIter>::value_type>);
		1892
		1893	__stable_sort_aux(__first, __last,
		1894	__value_type(__first),
		1895	__distance_type(__first));
		1896	}
		1897
		1898	template
		1899	inline void stable_sort(_RandomAccessIter __first,
		1900	_RandomAccessIter __last, _Compare __comp)
		1901	{
		1902	// concept requirements
		1903	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1904	_RandomAccessIter>);
		1905	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		1906	typename iterator_traits<_RandomAccessIter>::value_type,
		1907	typename iterator_traits<_RandomAccessIter>::value_type>);
		1908
		1909	__stable_sort_aux(__first, __last,
		1910	__value_type(__first),
		1911	__distance_type(__first),
		1912	__comp);
		1913	}
		1914
		1915	// partial_sort, partial_sort_copy, and auxiliary functions.
		1916
		1917	template
		1918	void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
		1919	_RandomAccessIter __last, _Tp*)
		1920	{
		1921	make_heap(__first, __middle);
		1922	for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
		1923	if (__i < __first)
		1924	__pop_heap(__first, __middle, __i, _Tp(*__i),
		1925	__distance_type(__first));
		1926	sort_heap(__first, __middle);
		1927	}
		1928
		1929	template
		1930	inline void partial_sort(_RandomAccessIter __first,
		1931	_RandomAccessIter __middle,
		1932	_RandomAccessIter __last)
		1933	{
		1934	// concept requirements
		1935	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1936	_RandomAccessIter>);
		1937	__glibcpp_function_requires(_LessThanComparableConcept<
		1938	typename iterator_traits<_RandomAccessIter>::value_type>);
		1939
		1940	__partial_sort(__first, __middle, __last, __value_type(__first));
		1941	}
		1942
		1943	template
		1944	void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
		1945	_RandomAccessIter __last, _Tp*, _Compare __comp)
		1946	{
		1947	make_heap(__first, __middle, __comp);
		1948	for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
		1949	if (__comp(__i, __first))
		1950	__pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
		1951	__distance_type(__first));
		1952	sort_heap(__first, __middle, __comp);
		1953	}
		1954
		1955	template
		1956	inline void partial_sort(_RandomAccessIter __first,
		1957	_RandomAccessIter __middle,
		1958	_RandomAccessIter __last, _Compare __comp)
		1959	{
		1960	// concept requirements
		1961	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		1962	_RandomAccessIter>);
		1963	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		1964	typename iterator_traits<_RandomAccessIter>::value_type,
		1965	typename iterator_traits<_RandomAccessIter>::value_type>);
		1966
		1967	__partial_sort(__first, __middle, __last, __value_type(__first), __comp);
		1968	}
		1969
		1970	template
		1971	class _Tp>
		1972	_RandomAccessIter __partial_sort_copy(_InputIter __first,
		1973	_InputIter __last,
		1974	_RandomAccessIter __result_first,
		1975	_RandomAccessIter __result_last,
		1976	_Distance, _Tp)
		1977	{
		1978	if (__result_first == __result_last) return __result_last;
		1979	_RandomAccessIter __result_real_last = __result_first;
		1980	while(__first != __last && __result_real_last != __result_last) {
		1981	__result_real_last = __first;
		1982	++__result_real_last;
		1983	++__first;
		1984	}
		1985	make_heap(__result_first, __result_real_last);
		1986	while (__first != __last) {
		1987	if (__first < __result_first)
		1988	__adjust_heap(__result_first, _Distance(0),
		1989	_Distance(__result_real_last - __result_first),
		1990	_Tp(*__first));
		1991	++__first;
		1992	}
		1993	sort_heap(__result_first, __result_real_last);
		1994	return __result_real_last;
		1995	}
		1996
		1997	template
		1998	inline _RandomAccessIter
		1999	partial_sort_copy(_InputIter __first, _InputIter __last,
		2000	_RandomAccessIter __result_first,
		2001	_RandomAccessIter __result_last)
		2002	{
		2003	// concept requirements
		2004	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		2005	__glibcpp_function_requires(_ConvertibleConcept<
		2006	typename iterator_traits<_InputIter>::value_type,
		2007	typename iterator_traits<_RandomAccessIter>::value_type>);
		2008	__glibcpp_function_requires(_LessThanComparableConcept<
		2009	typename iterator_traits<_RandomAccessIter>::value_type>);
		2010	__glibcpp_function_requires(_LessThanComparableConcept<
		2011	typename iterator_traits<_InputIter>::value_type>);
		2012
		2013	return __partial_sort_copy(__first, __last, __result_first, __result_last,
		2014	__distance_type(__result_first),
		2015	__value_type(__first));
		2016	}
		2017
		2018	template
		2019	class _Distance, class _Tp>
		2020	_RandomAccessIter __partial_sort_copy(_InputIter __first,
		2021	_InputIter __last,
		2022	_RandomAccessIter __result_first,
		2023	_RandomAccessIter __result_last,
		2024	_Compare __comp, _Distance, _Tp)
		2025	{
		2026	if (__result_first == __result_last) return __result_last;
		2027	_RandomAccessIter __result_real_last = __result_first;
		2028	while(__first != __last && __result_real_last != __result_last) {
		2029	__result_real_last = __first;
		2030	++__result_real_last;
		2031	++__first;
		2032	}
		2033	make_heap(__result_first, __result_real_last, __comp);
		2034	while (__first != __last) {
		2035	if (__comp(__first, __result_first))
		2036	__adjust_heap(__result_first, _Distance(0),
		2037	_Distance(__result_real_last - __result_first),
		2038	_Tp(*__first),
		2039	__comp);
		2040	++__first;
		2041	}
		2042	sort_heap(__result_first, __result_real_last, __comp);
		2043	return __result_real_last;
		2044	}
		2045
		2046	template
		2047	inline _RandomAccessIter
		2048	partial_sort_copy(_InputIter __first, _InputIter __last,
		2049	_RandomAccessIter __result_first,
		2050	_RandomAccessIter __result_last, _Compare __comp)
		2051	{
		2052	// concept requirements
		2053	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		2054	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		2055	_RandomAccessIter>);
		2056	__glibcpp_function_requires(_ConvertibleConcept<
		2057	typename iterator_traits<_InputIter>::value_type,
		2058	typename iterator_traits<_RandomAccessIter>::value_type>);
		2059	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		2060	typename iterator_traits<_RandomAccessIter>::value_type,
		2061	typename iterator_traits<_RandomAccessIter>::value_type>);
		2062
		2063	return __partial_sort_copy(__first, __last, __result_first, __result_last,
		2064	__comp,
		2065	__distance_type(__result_first),
		2066	__value_type(__first));
		2067	}
		2068
		2069	// nth_element() and its auxiliary functions.
		2070
		2071	template
		2072	void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
		2073	_RandomAccessIter __last, _Tp*)
		2074	{
		2075	while (__last - __first > 3) {
		2076	_RandomAccessIter __cut =
		2077	__unguarded_partition(__first, __last,
		2078	_Tp(__median(*__first,
		2079	*(__first + (__last - __first)/2),
		2080	*(__last - 1))));
		2081	if (__cut <= __nth)
		2082	__first = __cut;
		2083	else
		2084	__last = __cut;
		2085	}
		2086	__insertion_sort(__first, __last);
		2087	}
		2088
		2089	template
		2090	inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
		2091	_RandomAccessIter __last)
		2092	{
		2093	// concept requirements
		2094	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		2095	_RandomAccessIter>);
		2096	__glibcpp_function_requires(_LessThanComparableConcept<
		2097	typename iterator_traits<_RandomAccessIter>::value_type>);
		2098
		2099	__nth_element(__first, __nth, __last, __value_type(__first));
		2100	}
		2101
		2102	template
		2103	void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
		2104	_RandomAccessIter __last, _Tp*, _Compare __comp)
		2105	{
		2106	while (__last - __first > 3) {
		2107	_RandomAccessIter __cut =
		2108	__unguarded_partition(__first, __last,
		2109	_Tp(__median(*__first,
		2110	*(__first + (__last - __first)/2),
		2111	*(__last - 1),
		2112	__comp)),
		2113	__comp);
		2114	if (__cut <= __nth)
		2115	__first = __cut;
		2116	else
		2117	__last = __cut;
		2118	}
		2119	__insertion_sort(__first, __last, __comp);
		2120	}
		2121
		2122	template
		2123	inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
		2124	_RandomAccessIter __last, _Compare __comp)
		2125	{
		2126	// concept requirements
		2127	__glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
		2128	_RandomAccessIter>);
		2129	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		2130	typename iterator_traits<_RandomAccessIter>::value_type,
		2131	typename iterator_traits<_RandomAccessIter>::value_type>);
		2132
		2133	__nth_element(__first, __nth, __last, __value_type(__first), __comp);
		2134	}
		2135
		2136
		2137	// Binary search (lower_bound, upper_bound, equal_range, binary_search).
		2138
		2139	template
		2140	_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
		2141	const _Tp& __val, _Distance*)
		2142	{
		2143	_Distance __len = 0;
		2144	distance(__first, __last, __len);
		2145	_Distance __half;
		2146	_ForwardIter __middle;
		2147
		2148	while (__len > 0) {
		2149	__half = __len >> 1;
		2150	__middle = __first;
		2151	advance(__middle, __half);
		2152	if (*__middle < __val) {
		2153	__first = __middle;
		2154	++__first;
		2155	__len = __len - __half - 1;
		2156	}
		2157	else
		2158	__len = __half;
		2159	}
		2160	return __first;
		2161	}
		2162
		2163	template
		2164	inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
		2165	const _Tp& __val)
		2166	{
		2167	// concept requirements
		2168	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2169	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2170	typename iterator_traits<_ForwardIter>::value_type>);
		2171	__glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
		2172
		2173	return __lower_bound(__first, __last, __val,
		2174	__distance_type(__first));
		2175	}
		2176
		2177	template
		2178	_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
		2179	const _Tp& __val, _Compare __comp, _Distance*)
		2180	{
		2181	_Distance __len = 0;
		2182	distance(__first, __last, __len);
		2183	_Distance __half;
		2184	_ForwardIter __middle;
		2185
		2186	while (__len > 0) {
		2187	__half = __len >> 1;
		2188	__middle = __first;
		2189	advance(__middle, __half);
		2190	if (__comp(*__middle, __val)) {
		2191	__first = __middle;
		2192	++__first;
		2193	__len = __len - __half - 1;
		2194	}
		2195	else
		2196	__len = __half;
		2197	}
		2198	return __first;
		2199	}
		2200
		2201	template
		2202	inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
		2203	const _Tp& __val, _Compare __comp)
		2204	{
		2205	// concept requirements
		2206	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2207	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2208	typename iterator_traits<_ForwardIter>::value_type>);
		2209	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
		2210
		2211	return __lower_bound(__first, __last, __val, __comp,
		2212	__distance_type(__first));
		2213	}
		2214
		2215	template
		2216	_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
		2217	const _Tp& __val, _Distance*)
		2218	{
		2219	_Distance __len = 0;
		2220	distance(__first, __last, __len);
		2221	_Distance __half;
		2222	_ForwardIter __middle;
		2223
		2224	while (__len > 0) {
		2225	__half = __len >> 1;
		2226	__middle = __first;
		2227	advance(__middle, __half);
		2228	if (__val < *__middle)
		2229	__len = __half;
		2230	else {
		2231	__first = __middle;
		2232	++__first;
		2233	__len = __len - __half - 1;
		2234	}
		2235	}
		2236	return __first;
		2237	}
		2238
		2239	template
		2240	inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
		2241	const _Tp& __val)
		2242	{
		2243	// concept requirements
		2244	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2245	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2246	typename iterator_traits<_ForwardIter>::value_type>);
		2247	__glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
		2248
		2249	return __upper_bound(__first, __last, __val,
		2250	__distance_type(__first));
		2251	}
		2252
		2253	template
		2254	_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
		2255	const _Tp& __val, _Compare __comp, _Distance*)
		2256	{
		2257	_Distance __len = 0;
		2258	distance(__first, __last, __len);
		2259	_Distance __half;
		2260	_ForwardIter __middle;
		2261
		2262	while (__len > 0) {
		2263	__half = __len >> 1;
		2264	__middle = __first;
		2265	advance(__middle, __half);
		2266	if (__comp(__val, *__middle))
		2267	__len = __half;
		2268	else {
		2269	__first = __middle;
		2270	++__first;
		2271	__len = __len - __half - 1;
		2272	}
		2273	}
		2274	return __first;
		2275	}
		2276
		2277	template
		2278	inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
		2279	const _Tp& __val, _Compare __comp)
		2280	{
		2281	// concept requirements
		2282	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2283	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2284	typename iterator_traits<_ForwardIter>::value_type>);
		2285	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
		2286
		2287	return __upper_bound(__first, __last, __val, __comp,
		2288	__distance_type(__first));
		2289	}
		2290
		2291	template
		2292	pair<_ForwardIter, _ForwardIter>
		2293	__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
		2294	_Distance*)
		2295	{
		2296	_Distance __len = 0;
		2297	distance(__first, __last, __len);
		2298	_Distance __half;
		2299	_ForwardIter __middle, __left, __right;
		2300
		2301	while (__len > 0) {
		2302	__half = __len >> 1;
		2303	__middle = __first;
		2304	advance(__middle, __half);
		2305	if (*__middle < __val) {
		2306	__first = __middle;
		2307	++__first;
		2308	__len = __len - __half - 1;
		2309	}
		2310	else if (__val < *__middle)
		2311	__len = __half;
		2312	else {
		2313	__left = lower_bound(__first, __middle, __val);
		2314	advance(__first, __len);
		2315	__right = upper_bound(++__middle, __first, __val);
		2316	return pair<_ForwardIter, _ForwardIter>(__left, __right);
		2317	}
		2318	}
		2319	return pair<_ForwardIter, _ForwardIter>(__first, __first);
		2320	}
		2321
		2322	template
		2323	inline pair<_ForwardIter, _ForwardIter>
		2324	equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val)
		2325	{
		2326	// concept requirements
		2327	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2328	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2329	typename iterator_traits<_ForwardIter>::value_type>);
		2330	__glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
		2331
		2332	return __equal_range(__first, __last, __val,
		2333	__distance_type(__first));
		2334	}
		2335
		2336	template
		2337	pair<_ForwardIter, _ForwardIter>
		2338	__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
		2339	_Compare __comp, _Distance*)
		2340	{
		2341	_Distance __len = 0;
		2342	distance(__first, __last, __len);
		2343	_Distance __half;
		2344	_ForwardIter __middle, __left, __right;
		2345
		2346	while (__len > 0) {
		2347	__half = __len >> 1;
		2348	__middle = __first;
		2349	advance(__middle, __half);
		2350	if (__comp(*__middle, __val)) {
		2351	__first = __middle;
		2352	++__first;
		2353	__len = __len - __half - 1;
		2354	}
		2355	else if (__comp(__val, *__middle))
		2356	__len = __half;
		2357	else {
		2358	__left = lower_bound(__first, __middle, __val, __comp);
		2359	advance(__first, __len);
		2360	__right = upper_bound(++__middle, __first, __val, __comp);
		2361	return pair<_ForwardIter, _ForwardIter>(__left, __right);
		2362	}
		2363	}
		2364	return pair<_ForwardIter, _ForwardIter>(__first, __first);
		2365	}
		2366
		2367	template
		2368	inline pair<_ForwardIter, _ForwardIter>
		2369	equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
		2370	_Compare __comp)
		2371	{
		2372	// concept requirements
		2373	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2374	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2375	typename iterator_traits<_ForwardIter>::value_type>);
		2376	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
		2377
		2378	return __equal_range(__first, __last, __val, __comp,
		2379	__distance_type(__first));
		2380	}
		2381
		2382	template
		2383	bool binary_search(_ForwardIter __first, _ForwardIter __last,
		2384	const _Tp& __val)
		2385	{
		2386	// concept requirements
		2387	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2388	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2389	typename iterator_traits<_ForwardIter>::value_type>);
		2390	__glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
		2391
		2392	_ForwardIter __i = lower_bound(__first, __last, __val);
		2393	return __i != __last && !(__val < *__i);
		2394	}
		2395
		2396	template
		2397	bool binary_search(_ForwardIter __first, _ForwardIter __last,
		2398	const _Tp& __val,
		2399	_Compare __comp)
		2400	{
		2401	// concept requirements
		2402	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		2403	__glibcpp_function_requires(_SameTypeConcept<_Tp,
		2404	typename iterator_traits<_ForwardIter>::value_type>);
		2405	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>);
		2406
		2407	_ForwardIter __i = lower_bound(__first, __last, __val, __comp);
		2408	return __i != __last && !__comp(__val, *__i);
		2409	}
		2410
		2411	// merge, with and without an explicitly supplied comparison function.
		2412
		2413	template
		2414	_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
		2415	_InputIter2 __first2, _InputIter2 __last2,
		2416	_OutputIter __result)
		2417	{
		2418	// concept requirements
		2419	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2420	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2421	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		2422	typename iterator_traits<_InputIter1>::value_type>);
		2423	__glibcpp_function_requires(_SameTypeConcept<
		2424	typename iterator_traits<_InputIter1>::value_type,
		2425	typename iterator_traits<_InputIter2>::value_type>);
		2426	__glibcpp_function_requires(_LessThanComparableConcept<
		2427	typename iterator_traits<_InputIter1>::value_type>);
		2428
		2429	while (__first1 != __last1 && __first2 != __last2) {
		2430	if (__first2 < __first1) {
		2431	__result = __first2;
		2432	++__first2;
		2433	}
		2434	else {
		2435	__result = __first1;
		2436	++__first1;
		2437	}
		2438	++__result;
		2439	}
		2440	return copy(__first2, __last2, copy(__first1, __last1, __result));
		2441	}
		2442
		2443	template
		2444	class _Compare>
		2445	_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
		2446	_InputIter2 __first2, _InputIter2 __last2,
		2447	_OutputIter __result, _Compare __comp)
		2448	{
		2449	// concept requirements
		2450	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2451	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2452	__glibcpp_function_requires(_SameTypeConcept<
		2453	typename iterator_traits<_InputIter1>::value_type,
		2454	typename iterator_traits<_InputIter2>::value_type>);
		2455	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		2456	typename iterator_traits<_InputIter1>::value_type>);
		2457	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		2458	typename iterator_traits<_InputIter1>::value_type,
		2459	typename iterator_traits<_InputIter2>::value_type>);
		2460
		2461	while (__first1 != __last1 && __first2 != __last2) {
		2462	if (__comp(__first2, __first1)) {
		2463	__result = __first2;
		2464	++__first2;
		2465	}
		2466	else {
		2467	__result = __first1;
		2468	++__first1;
		2469	}
		2470	++__result;
		2471	}
		2472	return copy(__first2, __last2, copy(__first1, __last1, __result));
		2473	}
		2474
		2475	// inplace_merge and its auxiliary functions.
		2476
		2477	template
		2478	void __merge_without_buffer(_BidirectionalIter __first,
		2479	_BidirectionalIter __middle,
		2480	_BidirectionalIter __last,
		2481	_Distance __len1, _Distance __len2)
		2482	{
		2483	if (__len1 == 0 \|\| __len2 == 0)
		2484	return;
		2485	if (__len1 + __len2 == 2) {
		2486	if (__middle < __first)
		2487	iter_swap(__first, __middle);
		2488	return;
		2489	}
		2490	_BidirectionalIter __first_cut = __first;
		2491	_BidirectionalIter __second_cut = __middle;
		2492	_Distance __len11 = 0;
		2493	_Distance __len22 = 0;
		2494	if (__len1 > __len2) {
		2495	__len11 = __len1 / 2;
		2496	advance(__first_cut, __len11);
		2497	__second_cut = lower_bound(__middle, __last, *__first_cut);
		2498	distance(__middle, __second_cut, __len22);
		2499	}
		2500	else {
		2501	__len22 = __len2 / 2;
		2502	advance(__second_cut, __len22);
		2503	__first_cut = upper_bound(__first, __middle, *__second_cut);
		2504	distance(__first, __first_cut, __len11);
		2505	}
		2506	_BidirectionalIter __new_middle
		2507	= rotate(__first_cut, __middle, __second_cut);
		2508	__merge_without_buffer(__first, __first_cut, __new_middle,
		2509	__len11, __len22);
		2510	__merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
		2511	__len2 - __len22);
		2512	}
		2513
		2514	template
		2515	void __merge_without_buffer(_BidirectionalIter __first,
		2516	_BidirectionalIter __middle,
		2517	_BidirectionalIter __last,
		2518	_Distance __len1, _Distance __len2,
		2519	_Compare __comp)
		2520	{
		2521	if (__len1 == 0 \|\| __len2 == 0)
		2522	return;
		2523	if (__len1 + __len2 == 2) {
		2524	if (__comp(__middle, __first))
		2525	iter_swap(__first, __middle);
		2526	return;
		2527	}
		2528	_BidirectionalIter __first_cut = __first;
		2529	_BidirectionalIter __second_cut = __middle;
		2530	_Distance __len11 = 0;
		2531	_Distance __len22 = 0;
		2532	if (__len1 > __len2) {
		2533	__len11 = __len1 / 2;
		2534	advance(__first_cut, __len11);
		2535	__second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
		2536	distance(__middle, __second_cut, __len22);
		2537	}
		2538	else {
		2539	__len22 = __len2 / 2;
		2540	advance(__second_cut, __len22);
		2541	__first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
		2542	distance(__first, __first_cut, __len11);
		2543	}
		2544	_BidirectionalIter __new_middle
		2545	= rotate(__first_cut, __middle, __second_cut);
		2546	__merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
		2547	__comp);
		2548	__merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
		2549	__len2 - __len22, __comp);
		2550	}
		2551
		2552	template
		2553	class _Distance>
		2554	_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
		2555	_BidirectionalIter1 __middle,
		2556	_BidirectionalIter1 __last,
		2557	_Distance __len1, _Distance __len2,
		2558	_BidirectionalIter2 __buffer,
		2559	_Distance __buffer_size)
		2560	{
		2561	_BidirectionalIter2 __buffer_end;
		2562	if (__len1 > __len2 && __len2 <= __buffer_size) {
		2563	__buffer_end = copy(__middle, __last, __buffer);
		2564	copy_backward(__first, __middle, __last);
		2565	return copy(__buffer, __buffer_end, __first);
		2566	}
		2567	else if (__len1 <= __buffer_size) {
		2568	__buffer_end = copy(__first, __middle, __buffer);
		2569	copy(__middle, __last, __first);
		2570	return copy_backward(__buffer, __buffer_end, __last);
		2571	}
		2572	else
		2573	return rotate(__first, __middle, __last);
		2574	}
		2575
		2576	template
		2577	class _BidirectionalIter3>
		2578	_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
		2579	_BidirectionalIter1 __last1,
		2580	_BidirectionalIter2 __first2,
		2581	_BidirectionalIter2 __last2,
		2582	_BidirectionalIter3 __result)
		2583	{
		2584	if (__first1 == __last1)
		2585	return copy_backward(__first2, __last2, __result);
		2586	if (__first2 == __last2)
		2587	return copy_backward(__first1, __last1, __result);
		2588	--__last1;
		2589	--__last2;
		2590	while (true) {
		2591	if (__last2 < __last1) {
		2592	--__result = __last1;
		2593	if (__first1 == __last1)
		2594	return copy_backward(__first2, ++__last2, __result);
		2595	--__last1;
		2596	}
		2597	else {
		2598	--__result = __last2;
		2599	if (__first2 == __last2)
		2600	return copy_backward(__first1, ++__last1, __result);
		2601	--__last2;
		2602	}
		2603	}
		2604	}
		2605
		2606	template
		2607	class _BidirectionalIter3, class _Compare>
		2608	_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
		2609	_BidirectionalIter1 __last1,
		2610	_BidirectionalIter2 __first2,
		2611	_BidirectionalIter2 __last2,
		2612	_BidirectionalIter3 __result,
		2613	_Compare __comp)
		2614	{
		2615	if (__first1 == __last1)
		2616	return copy_backward(__first2, __last2, __result);
		2617	if (__first2 == __last2)
		2618	return copy_backward(__first1, __last1, __result);
		2619	--__last1;
		2620	--__last2;
		2621	while (true) {
		2622	if (__comp(__last2, __last1)) {
		2623	--__result = __last1;
		2624	if (__first1 == __last1)
		2625	return copy_backward(__first2, ++__last2, __result);
		2626	--__last1;
		2627	}
		2628	else {
		2629	--__result = __last2;
		2630	if (__first2 == __last2)
		2631	return copy_backward(__first1, ++__last1, __result);
		2632	--__last2;
		2633	}
		2634	}
		2635	}
		2636
		2637	template
		2638	void __merge_adaptive(_BidirectionalIter __first,
		2639	_BidirectionalIter __middle,
		2640	_BidirectionalIter __last,
		2641	_Distance __len1, _Distance __len2,
		2642	_Pointer __buffer, _Distance __buffer_size)
		2643	{
		2644	if (__len1 <= __len2 && __len1 <= __buffer_size) {
		2645	_Pointer __buffer_end = copy(__first, __middle, __buffer);
		2646	merge(__buffer, __buffer_end, __middle, __last, __first);
		2647	}
		2648	else if (__len2 <= __buffer_size) {
		2649	_Pointer __buffer_end = copy(__middle, __last, __buffer);
		2650	__merge_backward(__first, __middle, __buffer, __buffer_end, __last);
		2651	}
		2652	else {
		2653	_BidirectionalIter __first_cut = __first;
		2654	_BidirectionalIter __second_cut = __middle;
		2655	_Distance __len11 = 0;
		2656	_Distance __len22 = 0;
		2657	if (__len1 > __len2) {
		2658	__len11 = __len1 / 2;
		2659	advance(__first_cut, __len11);
		2660	__second_cut = lower_bound(__middle, __last, *__first_cut);
		2661	distance(__middle, __second_cut, __len22);
		2662	}
		2663	else {
		2664	__len22 = __len2 / 2;
		2665	advance(__second_cut, __len22);
		2666	__first_cut = upper_bound(__first, __middle, *__second_cut);
		2667	distance(__first, __first_cut, __len11);
		2668	}
		2669	_BidirectionalIter __new_middle =
		2670	__rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
		2671	__len22, __buffer, __buffer_size);
		2672	__merge_adaptive(__first, __first_cut, __new_middle, __len11,
		2673	__len22, __buffer, __buffer_size);
		2674	__merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
		2675	__len2 - __len22, __buffer, __buffer_size);
		2676	}
		2677	}
		2678
		2679	template
		2680	class _Compare>
		2681	void __merge_adaptive(_BidirectionalIter __first,
		2682	_BidirectionalIter __middle,
		2683	_BidirectionalIter __last,
		2684	_Distance __len1, _Distance __len2,
		2685	_Pointer __buffer, _Distance __buffer_size,
		2686	_Compare __comp)
		2687	{
		2688	if (__len1 <= __len2 && __len1 <= __buffer_size) {
		2689	_Pointer __buffer_end = copy(__first, __middle, __buffer);
		2690	merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
		2691	}
		2692	else if (__len2 <= __buffer_size) {
		2693	_Pointer __buffer_end = copy(__middle, __last, __buffer);
		2694	__merge_backward(__first, __middle, __buffer, __buffer_end, __last,
		2695	__comp);
		2696	}
		2697	else {
		2698	_BidirectionalIter __first_cut = __first;
		2699	_BidirectionalIter __second_cut = __middle;
		2700	_Distance __len11 = 0;
		2701	_Distance __len22 = 0;
		2702	if (__len1 > __len2) {
		2703	__len11 = __len1 / 2;
		2704	advance(__first_cut, __len11);
		2705	__second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
		2706	distance(__middle, __second_cut, __len22);
		2707	}
		2708	else {
		2709	__len22 = __len2 / 2;
		2710	advance(__second_cut, __len22);
		2711	__first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
		2712	distance(__first, __first_cut, __len11);
		2713	}
		2714	_BidirectionalIter __new_middle =
		2715	__rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
		2716	__len22, __buffer, __buffer_size);
		2717	__merge_adaptive(__first, __first_cut, __new_middle, __len11,
		2718	__len22, __buffer, __buffer_size, __comp);
		2719	__merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
		2720	__len2 - __len22, __buffer, __buffer_size, __comp);
		2721	}
		2722	}
		2723
		2724	template
		2725	inline void __inplace_merge_aux(_BidirectionalIter __first,
		2726	_BidirectionalIter __middle,
		2727	_BidirectionalIter __last, _Tp, _Distance)
		2728	{
		2729	_Distance __len1 = 0;
		2730	distance(__first, __middle, __len1);
		2731	_Distance __len2 = 0;
		2732	distance(__middle, __last, __len2);
		2733
		2734	_Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
		2735	if (__buf.begin() == 0)
		2736	__merge_without_buffer(__first, __middle, __last, __len1, __len2);
		2737	else
		2738	__merge_adaptive(__first, __middle, __last, __len1, __len2,
		2739	__buf.begin(), _Distance(__buf.size()));
		2740	}
		2741
		2742	template
		2743	class _Distance, class _Compare>
		2744	inline void __inplace_merge_aux(_BidirectionalIter __first,
		2745	_BidirectionalIter __middle,
		2746	_BidirectionalIter __last, _Tp, _Distance,
		2747	_Compare __comp)
		2748	{
		2749	_Distance __len1 = 0;
		2750	distance(__first, __middle, __len1);
		2751	_Distance __len2 = 0;
		2752	distance(__middle, __last, __len2);
		2753
		2754	_Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
		2755	if (__buf.begin() == 0)
		2756	__merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
		2757	else
		2758	__merge_adaptive(__first, __middle, __last, __len1, __len2,
		2759	__buf.begin(), _Distance(__buf.size()),
		2760	__comp);
		2761	}
		2762
		2763	template
		2764	inline void inplace_merge(_BidirectionalIter __first,
		2765	_BidirectionalIter __middle,
		2766	_BidirectionalIter __last)
		2767	{
		2768	// concept requirements
		2769	__glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
		2770	_BidirectionalIter>);
		2771	__glibcpp_function_requires(_LessThanComparableConcept<
		2772	typename iterator_traits<_BidirectionalIter>::value_type>);
		2773
		2774	if (__first == __middle \|\| __middle == __last)
		2775	return;
		2776	__inplace_merge_aux(__first, __middle, __last,
		2777	__value_type(__first), __distance_type(__first));
		2778	}
		2779
		2780	template
		2781	inline void inplace_merge(_BidirectionalIter __first,
		2782	_BidirectionalIter __middle,
		2783	_BidirectionalIter __last, _Compare __comp)
		2784	{
		2785	// concept requirements
		2786	__glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<
		2787	_BidirectionalIter>);
		2788	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		2789	typename iterator_traits<_BidirectionalIter>::value_type,
		2790	typename iterator_traits<_BidirectionalIter>::value_type>);
		2791
		2792	if (__first == __middle \|\| __middle == __last)
		2793	return;
		2794	__inplace_merge_aux(__first, __middle, __last,
		2795	__value_type(__first), __distance_type(__first),
		2796	__comp);
		2797	}
		2798
		2799	// Set algorithms: includes, set_union, set_intersection, set_difference,
		2800	// set_symmetric_difference. All of these algorithms have the precondition
		2801	// that their input ranges are sorted and the postcondition that their output
		2802	// ranges are sorted.
		2803
		2804	template
		2805	bool includes(_InputIter1 __first1, _InputIter1 __last1,
		2806	_InputIter2 __first2, _InputIter2 __last2)
		2807	{
		2808	// concept requirements
		2809	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2810	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2811	__glibcpp_function_requires(_SameTypeConcept<
		2812	typename iterator_traits<_InputIter1>::value_type,
		2813	typename iterator_traits<_InputIter2>::value_type>);
		2814	__glibcpp_function_requires(_LessThanComparableConcept<
		2815	typename iterator_traits<_InputIter1>::value_type>);
		2816
		2817	while (__first1 != __last1 && __first2 != __last2)
		2818	if (__first2 < __first1)
		2819	return false;
		2820	else if(__first1 < __first2)
		2821	++__first1;
		2822	else
		2823	++__first1, ++__first2;
		2824
		2825	return __first2 == __last2;
		2826	}
		2827
		2828	template
		2829	bool includes(_InputIter1 __first1, _InputIter1 __last1,
		2830	_InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
		2831	{
		2832	// concept requirements
		2833	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2834	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2835	__glibcpp_function_requires(_SameTypeConcept<
		2836	typename iterator_traits<_InputIter1>::value_type,
		2837	typename iterator_traits<_InputIter2>::value_type>);
		2838	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		2839	typename iterator_traits<_InputIter1>::value_type,
		2840	typename iterator_traits<_InputIter2>::value_type>);
		2841
		2842	while (__first1 != __last1 && __first2 != __last2)
		2843	if (__comp(__first2, __first1))
		2844	return false;
		2845	else if(__comp(__first1, __first2))
		2846	++__first1;
		2847	else
		2848	++__first1, ++__first2;
		2849
		2850	return __first2 == __last2;
		2851	}
		2852
		2853	template
		2854	_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
		2855	_InputIter2 __first2, _InputIter2 __last2,
		2856	_OutputIter __result)
		2857	{
		2858	// concept requirements
		2859	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2860	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2861	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		2862	typename iterator_traits<_InputIter1>::value_type>);
		2863	__glibcpp_function_requires(_SameTypeConcept<
		2864	typename iterator_traits<_InputIter1>::value_type,
		2865	typename iterator_traits<_InputIter2>::value_type>);
		2866	__glibcpp_function_requires(_LessThanComparableConcept<
		2867	typename iterator_traits<_InputIter1>::value_type>);
		2868
		2869	while (__first1 != __last1 && __first2 != __last2) {
		2870	if (__first1 < __first2) {
		2871	__result = __first1;
		2872	++__first1;
		2873	}
		2874	else if (__first2 < __first1) {
		2875	__result = __first2;
		2876	++__first2;
		2877	}
		2878	else {
		2879	__result = __first1;
		2880	++__first1;
		2881	++__first2;
		2882	}
		2883	++__result;
		2884	}
		2885	return copy(__first2, __last2, copy(__first1, __last1, __result));
		2886	}
		2887
		2888	template
		2889	class _Compare>
		2890	_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
		2891	_InputIter2 __first2, _InputIter2 __last2,
		2892	_OutputIter __result, _Compare __comp)
		2893	{
		2894	// concept requirements
		2895	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2896	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2897	__glibcpp_function_requires(_SameTypeConcept<
		2898	typename iterator_traits<_InputIter1>::value_type,
		2899	typename iterator_traits<_InputIter2>::value_type>);
		2900	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		2901	typename iterator_traits<_InputIter1>::value_type>);
		2902	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		2903	typename iterator_traits<_InputIter1>::value_type,
		2904	typename iterator_traits<_InputIter2>::value_type>);
		2905
		2906	while (__first1 != __last1 && __first2 != __last2) {
		2907	if (__comp(__first1, __first2)) {
		2908	__result = __first1;
		2909	++__first1;
		2910	}
		2911	else if (__comp(__first2, __first1)) {
		2912	__result = __first2;
		2913	++__first2;
		2914	}
		2915	else {
		2916	__result = __first1;
		2917	++__first1;
		2918	++__first2;
		2919	}
		2920	++__result;
		2921	}
		2922	return copy(__first2, __last2, copy(__first1, __last1, __result));
		2923	}
		2924
		2925	template
		2926	_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
		2927	_InputIter2 __first2, _InputIter2 __last2,
		2928	_OutputIter __result)
		2929	{
		2930	// concept requirements
		2931	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2932	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2933	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		2934	typename iterator_traits<_InputIter1>::value_type>);
		2935	__glibcpp_function_requires(_SameTypeConcept<
		2936	typename iterator_traits<_InputIter1>::value_type,
		2937	typename iterator_traits<_InputIter2>::value_type>);
		2938	__glibcpp_function_requires(_LessThanComparableConcept<
		2939	typename iterator_traits<_InputIter1>::value_type>);
		2940
		2941	while (__first1 != __last1 && __first2 != __last2)
		2942	if (__first1 < __first2)
		2943	++__first1;
		2944	else if (__first2 < __first1)
		2945	++__first2;
		2946	else {
		2947	__result = __first1;
		2948	++__first1;
		2949	++__first2;
		2950	++__result;
		2951	}
		2952	return __result;
		2953	}
		2954
		2955	template
		2956	class _Compare>
		2957	_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
		2958	_InputIter2 __first2, _InputIter2 __last2,
		2959	_OutputIter __result, _Compare __comp)
		2960	{
		2961	// concept requirements
		2962	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2963	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2964	__glibcpp_function_requires(_SameTypeConcept<
		2965	typename iterator_traits<_InputIter1>::value_type,
		2966	typename iterator_traits<_InputIter2>::value_type>);
		2967	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		2968	typename iterator_traits<_InputIter1>::value_type>);
		2969	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		2970	typename iterator_traits<_InputIter1>::value_type,
		2971	typename iterator_traits<_InputIter2>::value_type>);
		2972
		2973	while (__first1 != __last1 && __first2 != __last2)
		2974	if (__comp(__first1, __first2))
		2975	++__first1;
		2976	else if (__comp(__first2, __first1))
		2977	++__first2;
		2978	else {
		2979	__result = __first1;
		2980	++__first1;
		2981	++__first2;
		2982	++__result;
		2983	}
		2984	return __result;
		2985	}
		2986
		2987	template
		2988	_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
		2989	_InputIter2 __first2, _InputIter2 __last2,
		2990	_OutputIter __result)
		2991	{
		2992	// concept requirements
		2993	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		2994	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		2995	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		2996	typename iterator_traits<_InputIter1>::value_type>);
		2997	__glibcpp_function_requires(_SameTypeConcept<
		2998	typename iterator_traits<_InputIter1>::value_type,
		2999	typename iterator_traits<_InputIter2>::value_type>);
		3000	__glibcpp_function_requires(_LessThanComparableConcept<
		3001	typename iterator_traits<_InputIter1>::value_type>);
		3002
		3003	while (__first1 != __last1 && __first2 != __last2)
		3004	if (__first1 < __first2) {
		3005	__result = __first1;
		3006	++__first1;
		3007	++__result;
		3008	}
		3009	else if (__first2 < __first1)
		3010	++__first2;
		3011	else {
		3012	++__first1;
		3013	++__first2;
		3014	}
		3015	return copy(__first1, __last1, __result);
		3016	}
		3017
		3018	template
		3019	class _Compare>
		3020	_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
		3021	_InputIter2 __first2, _InputIter2 __last2,
		3022	_OutputIter __result, _Compare __comp)
		3023	{
		3024	// concept requirements
		3025	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		3026	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		3027	__glibcpp_function_requires(_SameTypeConcept<
		3028	typename iterator_traits<_InputIter1>::value_type,
		3029	typename iterator_traits<_InputIter2>::value_type>);
		3030	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		3031	typename iterator_traits<_InputIter1>::value_type>);
		3032	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		3033	typename iterator_traits<_InputIter1>::value_type,
		3034	typename iterator_traits<_InputIter2>::value_type>);
		3035
		3036	while (__first1 != __last1 && __first2 != __last2)
		3037	if (__comp(__first1, __first2)) {
		3038	__result = __first1;
		3039	++__first1;
		3040	++__result;
		3041	}
		3042	else if (__comp(__first2, __first1))
		3043	++__first2;
		3044	else {
		3045	++__first1;
		3046	++__first2;
		3047	}
		3048	return copy(__first1, __last1, __result);
		3049	}
		3050
		3051	template
		3052	_OutputIter
		3053	set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
		3054	_InputIter2 __first2, _InputIter2 __last2,
		3055	_OutputIter __result)
		3056	{
		3057	// concept requirements
		3058	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		3059	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		3060	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		3061	typename iterator_traits<_InputIter1>::value_type>);
		3062	__glibcpp_function_requires(_SameTypeConcept<
		3063	typename iterator_traits<_InputIter1>::value_type,
		3064	typename iterator_traits<_InputIter2>::value_type>);
		3065	__glibcpp_function_requires(_LessThanComparableConcept<
		3066	typename iterator_traits<_InputIter1>::value_type>);
		3067
		3068	while (__first1 != __last1 && __first2 != __last2)
		3069	if (__first1 < __first2) {
		3070	__result = __first1;
		3071	++__first1;
		3072	++__result;
		3073	}
		3074	else if (__first2 < __first1) {
		3075	__result = __first2;
		3076	++__first2;
		3077	++__result;
		3078	}
		3079	else {
		3080	++__first1;
		3081	++__first2;
		3082	}
		3083	return copy(__first2, __last2, copy(__first1, __last1, __result));
		3084	}
		3085
		3086	template
		3087	class _Compare>
		3088	_OutputIter
		3089	set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
		3090	_InputIter2 __first2, _InputIter2 __last2,
		3091	_OutputIter __result,
		3092	_Compare __comp)
		3093	{
		3094	// concept requirements
		3095	__glibcpp_function_requires(_InputIteratorConcept<_InputIter1>);
		3096	__glibcpp_function_requires(_InputIteratorConcept<_InputIter2>);
		3097	__glibcpp_function_requires(_SameTypeConcept<
		3098	typename iterator_traits<_InputIter1>::value_type,
		3099	typename iterator_traits<_InputIter2>::value_type>);
		3100	__glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
		3101	typename iterator_traits<_InputIter1>::value_type>);
		3102	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		3103	typename iterator_traits<_InputIter1>::value_type,
		3104	typename iterator_traits<_InputIter2>::value_type>);
		3105
		3106	while (__first1 != __last1 && __first2 != __last2)
		3107	if (__comp(__first1, __first2)) {
		3108	__result = __first1;
		3109	++__first1;
		3110	++__result;
		3111	}
		3112	else if (__comp(__first2, __first1)) {
		3113	__result = __first2;
		3114	++__first2;
		3115	++__result;
		3116	}
		3117	else {
		3118	++__first1;
		3119	++__first2;
		3120	}
		3121	return copy(__first2, __last2, copy(__first1, __last1, __result));
		3122	}
		3123
		3124	// min_element and max_element, with and without an explicitly supplied
		3125	// comparison function.
		3126
		3127	template
		3128	_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last)
		3129	{
		3130	// concept requirements
		3131	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3132	__glibcpp_function_requires(_LessThanComparableConcept<
		3133	typename iterator_traits<_ForwardIter>::value_type>);
		3134
		3135	if (__first == __last) return __first;
		3136	_ForwardIter __result = __first;
		3137	while (++__first != __last)
		3138	if (__result < __first)
		3139	__result = __first;
		3140	return __result;
		3141	}
		3142
		3143	template
		3144	_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
		3145	_Compare __comp)
		3146	{
		3147	// concept requirements
		3148	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3149	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		3150	typename iterator_traits<_ForwardIter>::value_type,
		3151	typename iterator_traits<_ForwardIter>::value_type>);
		3152
		3153	if (__first == __last) return __first;
		3154	_ForwardIter __result = __first;
		3155	while (++__first != __last)
		3156	if (__comp(__result, __first)) __result = __first;
		3157	return __result;
		3158	}
		3159
		3160	template
		3161	_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last)
		3162	{
		3163	// concept requirements
		3164	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3165	__glibcpp_function_requires(_LessThanComparableConcept<
		3166	typename iterator_traits<_ForwardIter>::value_type>);
		3167
		3168	if (__first == __last) return __first;
		3169	_ForwardIter __result = __first;
		3170	while (++__first != __last)
		3171	if (__first < __result)
		3172	__result = __first;
		3173	return __result;
		3174	}
		3175
		3176	template
		3177	_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
		3178	_Compare __comp)
		3179	{
		3180	// concept requirements
		3181	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3182	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		3183	typename iterator_traits<_ForwardIter>::value_type,
		3184	typename iterator_traits<_ForwardIter>::value_type>);
		3185
		3186	if (__first == __last) return __first;
		3187	_ForwardIter __result = __first;
		3188	while (++__first != __last)
		3189	if (__comp(__first, __result))
		3190	__result = __first;
		3191	return __result;
		3192	}
		3193
		3194	// next_permutation and prev_permutation, with and without an explicitly
		3195	// supplied comparison function.
		3196
		3197	template
		3198	bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
		3199	{
		3200	// concept requirements
		3201	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
		3202	__glibcpp_function_requires(_LessThanComparableConcept<
		3203	typename iterator_traits<_BidirectionalIter>::value_type>);
		3204
		3205	if (__first == __last)
		3206	return false;
		3207	_BidirectionalIter __i = __first;
		3208	++__i;
		3209	if (__i == __last)
		3210	return false;
		3211	__i = __last;
		3212	--__i;
		3213
		3214	for(;;) {
		3215	_BidirectionalIter __ii = __i;
		3216	--__i;
		3217	if (__i < __ii) {
		3218	_BidirectionalIter __j = __last;
		3219	while (!(__i < --__j))
		3220	{}
		3221	iter_swap(__i, __j);
		3222	reverse(__ii, __last);
		3223	return true;
		3224	}
		3225	if (__i == __first) {
		3226	reverse(__first, __last);
		3227	return false;
		3228	}
		3229	}
		3230	}
		3231
		3232	template
		3233	bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
		3234	_Compare __comp)
		3235	{
		3236	// concept requirements
		3237	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
		3238	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		3239	typename iterator_traits<_BidirectionalIter>::value_type,
		3240	typename iterator_traits<_BidirectionalIter>::value_type>);
		3241
		3242	if (__first == __last)
		3243	return false;
		3244	_BidirectionalIter __i = __first;
		3245	++__i;
		3246	if (__i == __last)
		3247	return false;
		3248	__i = __last;
		3249	--__i;
		3250
		3251	for(;;) {
		3252	_BidirectionalIter __ii = __i;
		3253	--__i;
		3254	if (__comp(__i, __ii)) {
		3255	_BidirectionalIter __j = __last;
		3256	while (!__comp(__i, --__j))
		3257	{}
		3258	iter_swap(__i, __j);
		3259	reverse(__ii, __last);
		3260	return true;
		3261	}
		3262	if (__i == __first) {
		3263	reverse(__first, __last);
		3264	return false;
		3265	}
		3266	}
		3267	}
		3268
		3269	template
		3270	bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last)
		3271	{
		3272	// concept requirements
		3273	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
		3274	__glibcpp_function_requires(_LessThanComparableConcept<
		3275	typename iterator_traits<_BidirectionalIter>::value_type>);
		3276
		3277	if (__first == __last)
		3278	return false;
		3279	_BidirectionalIter __i = __first;
		3280	++__i;
		3281	if (__i == __last)
		3282	return false;
		3283	__i = __last;
		3284	--__i;
		3285
		3286	for(;;) {
		3287	_BidirectionalIter __ii = __i;
		3288	--__i;
		3289	if (__ii < __i) {
		3290	_BidirectionalIter __j = __last;
		3291	while (!(--__j < __i))
		3292	{}
		3293	iter_swap(__i, __j);
		3294	reverse(__ii, __last);
		3295	return true;
		3296	}
		3297	if (__i == __first) {
		3298	reverse(__first, __last);
		3299	return false;
		3300	}
		3301	}
		3302	}
		3303
		3304	template
		3305	bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
		3306	_Compare __comp)
		3307	{
		3308	// concept requirements
		3309	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>);
		3310	__glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
		3311	typename iterator_traits<_BidirectionalIter>::value_type,
		3312	typename iterator_traits<_BidirectionalIter>::value_type>);
		3313
		3314	if (__first == __last)
		3315	return false;
		3316	_BidirectionalIter __i = __first;
		3317	++__i;
		3318	if (__i == __last)
		3319	return false;
		3320	__i = __last;
		3321	--__i;
		3322
		3323	for(;;) {
		3324	_BidirectionalIter __ii = __i;
		3325	--__i;
		3326	if (__comp(__ii, __i)) {
		3327	_BidirectionalIter __j = __last;
		3328	while (!__comp(--__j, __i))
		3329	{}
		3330	iter_swap(__i, __j);
		3331	reverse(__ii, __last);
		3332	return true;
		3333	}
		3334	if (__i == __first) {
		3335	reverse(__first, __last);
		3336	return false;
		3337	}
		3338	}
		3339	}
		3340
		3341	// find_first_of, with and without an explicitly supplied comparison function.
		3342
		3343	template
		3344	_InputIter find_first_of(_InputIter __first1, _InputIter __last1,
		3345	_ForwardIter __first2, _ForwardIter __last2)
		3346	{
		3347	// concept requirements
		3348	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		3349	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3350	__glibcpp_function_requires(_EqualOpConcept<
		3351	typename iterator_traits<_InputIter>::value_type,
		3352	typename iterator_traits<_ForwardIter>::value_type>);
		3353
		3354	for ( ; __first1 != __last1; ++__first1)
		3355	for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
		3356	if (__first1 == __iter)
		3357	return __first1;
		3358	return __last1;
		3359	}
		3360
		3361	template
		3362	_InputIter find_first_of(_InputIter __first1, _InputIter __last1,
		3363	_ForwardIter __first2, _ForwardIter __last2,
		3364	_BinaryPredicate __comp)
		3365	{
		3366	// concept requirements
		3367	__glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
		3368	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3369	__glibcpp_function_requires(_EqualOpConcept<
		3370	typename iterator_traits<_InputIter>::value_type,
		3371	typename iterator_traits<_ForwardIter>::value_type>);
		3372	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
		3373	typename iterator_traits<_InputIter>::value_type,
		3374	typename iterator_traits<_ForwardIter>::value_type>);
		3375
		3376	for ( ; __first1 != __last1; ++__first1)
		3377	for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
		3378	if (__comp(__first1, __iter))
		3379	return __first1;
		3380	return __last1;
		3381	}
		3382
		3383
		3384	// find_end, with and without an explicitly supplied comparison function.
		3385	// Search [first2, last2) as a subsequence in [first1, last1), and return
		3386	// the last possible match. Note that find_end for bidirectional iterators
		3387	// is much faster than for forward iterators.
		3388
		3389	// find_end for forward iterators.
		3390	template
		3391	_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
		3392	_ForwardIter2 __first2, _ForwardIter2 __last2,
		3393	forward_iterator_tag, forward_iterator_tag)
		3394	{
		3395	if (__first2 == __last2)
		3396	return __last1;
		3397	else {
		3398	_ForwardIter1 __result = __last1;
		3399	while (1) {
		3400	_ForwardIter1 __new_result
		3401	= search(__first1, __last1, __first2, __last2);
		3402	if (__new_result == __last1)
		3403	return __result;
		3404	else {
		3405	__result = __new_result;
		3406	__first1 = __new_result;
		3407	++__first1;
		3408	}
		3409	}
		3410	}
		3411	}
		3412
		3413	template
		3414	class _BinaryPredicate>
		3415	_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
		3416	_ForwardIter2 __first2, _ForwardIter2 __last2,
		3417	forward_iterator_tag, forward_iterator_tag,
		3418	_BinaryPredicate __comp)
		3419	{
		3420	if (__first2 == __last2)
		3421	return __last1;
		3422	else {
		3423	_ForwardIter1 __result = __last1;
		3424	while (1) {
		3425	_ForwardIter1 __new_result
		3426	= search(__first1, __last1, __first2, __last2, __comp);
		3427	if (__new_result == __last1)
		3428	return __result;
		3429	else {
		3430	__result = __new_result;
		3431	__first1 = __new_result;
		3432	++__first1;
		3433	}
		3434	}
		3435	}
		3436	}
		3437
		3438	// find_end for bidirectional iterators. Requires partial specialization.
		3439	template
		3440	_BidirectionalIter1
		3441	__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
		3442	_BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
		3443	bidirectional_iterator_tag, bidirectional_iterator_tag)
		3444	{
		3445	// concept requirements
		3446	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>);
		3447	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>);
		3448
		3449	typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
		3450	typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
		3451
		3452	_RevIter1 __rlast1(__first1);
		3453	_RevIter2 __rlast2(__first2);
		3454	_RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
		3455	_RevIter2(__last2), __rlast2);
		3456
		3457	if (__rresult == __rlast1)
		3458	return __last1;
		3459	else {
		3460	_BidirectionalIter1 __result = __rresult.base();
		3461	advance(__result, -distance(__first2, __last2));
		3462	return __result;
		3463	}
		3464	}
		3465
		3466	template
		3467	class _BinaryPredicate>
		3468	_BidirectionalIter1
		3469	__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
		3470	_BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
		3471	bidirectional_iterator_tag, bidirectional_iterator_tag,
		3472	_BinaryPredicate __comp)
		3473	{
		3474	// concept requirements
		3475	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>);
		3476	__glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>);
		3477
		3478	typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
		3479	typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
		3480
		3481	_RevIter1 __rlast1(__first1);
		3482	_RevIter2 __rlast2(__first2);
		3483	_RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
		3484	_RevIter2(__last2), __rlast2,
		3485	__comp);
		3486
		3487	if (__rresult == __rlast1)
		3488	return __last1;
		3489	else {
		3490	_BidirectionalIter1 __result = __rresult.base();
		3491	advance(__result, -distance(__first2, __last2));
		3492	return __result;
		3493	}
		3494	}
		3495
		3496	// Dispatching functions for find_end.
		3497
		3498	template
		3499	inline _ForwardIter1
		3500	find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
		3501	_ForwardIter2 __first2, _ForwardIter2 __last2)
		3502	{
		3503	// concept requirements
		3504	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
		3505	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
		3506	__glibcpp_function_requires(_EqualOpConcept<
		3507	typename iterator_traits<_ForwardIter1>::value_type,
		3508	typename iterator_traits<_ForwardIter2>::value_type>);
		3509
		3510	return __find_end(__first1, __last1, __first2, __last2,
		3511	__iterator_category(__first1),
		3512	__iterator_category(__first2));
		3513	}
		3514
		3515	template
		3516	class _BinaryPredicate>
		3517	inline _ForwardIter1
		3518	find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
		3519	_ForwardIter2 __first2, _ForwardIter2 __last2,
		3520	_BinaryPredicate __comp)
		3521	{
		3522	// concept requirements
		3523	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
		3524	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
		3525	__glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
		3526	typename iterator_traits<_ForwardIter1>::value_type,
		3527	typename iterator_traits<_ForwardIter2>::value_type>);
		3528
		3529	return __find_end(__first1, __last1, __first2, __last2,
		3530	__iterator_category(__first1),
		3531	__iterator_category(__first2),
		3532	__comp);
		3533	}
		3534
		3535	// is_heap, a predicate testing whether or not a range is
		3536	// a heap. This function is an extension, not part of the C++
		3537	// standard.
		3538
		3539	template
		3540	bool __is_heap(_RandomAccessIter __first, _Distance __n)
		3541	{
		3542	_Distance __parent = 0;
		3543	for (_Distance __child = 1; __child < __n; ++__child) {
		3544	if (__first[__parent] < __first[__child])
		3545	return false;
		3546	if ((__child & 1) == 0)
		3547	++__parent;
		3548	}
		3549	return true;
		3550	}
		3551
		3552	template
		3553	bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
		3554	_Distance __n)
		3555	{
		3556	_Distance __parent = 0;
		3557	for (_Distance __child = 1; __child < __n; ++__child) {
		3558	if (__comp(__first[__parent], __first[__child]))
		3559	return false;
		3560	if ((__child & 1) == 0)
		3561	++__parent;
		3562	}
		3563	return true;
		3564	}
		3565
		3566	template
		3567	inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
		3568	{
		3569	// concept requirements
		3570	__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>);
		3571	__glibcpp_function_requires(_LessThanComparableConcept<
		3572	typename iterator_traits<_RandomAccessIter>::value_type>);
		3573
		3574	return __is_heap(__first, __last - __first);
		3575	}
		3576
		3577
		3578	template
		3579	inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
		3580	_StrictWeakOrdering __comp)
		3581	{
		3582	// concept requirements
		3583	__glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>);
		3584	__glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
		3585	typename iterator_traits<_RandomAccessIter>::value_type,
		3586	typename iterator_traits<_RandomAccessIter>::value_type>);
		3587
		3588	return __is_heap(__first, __comp, __last - __first);
		3589	}
		3590
		3591	// is_sorted, a predicated testing whether a range is sorted in
		3592	// nondescending order. This is an extension, not part of the C++
		3593	// standard.
		3594
		3595	template
		3596	bool is_sorted(_ForwardIter __first, _ForwardIter __last)
		3597	{
		3598	// concept requirements
		3599	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3600	__glibcpp_function_requires(_LessThanComparableConcept<
		3601	typename iterator_traits<_ForwardIter>::value_type>);
		3602
		3603	if (__first == __last)
		3604	return true;
		3605
		3606	_ForwardIter __next = __first;
		3607	for (++__next; __next != __last; __first = __next, ++__next) {
		3608	if (__next < __first)
		3609	return false;
		3610	}
		3611
		3612	return true;
		3613	}
		3614
		3615	template
		3616	bool is_sorted(_ForwardIter __first, _ForwardIter __last,
		3617	_StrictWeakOrdering __comp)
		3618	{
		3619	// concept requirements
		3620	__glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
		3621	__glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
		3622	typename iterator_traits<_ForwardIter>::value_type,
		3623	typename iterator_traits<_ForwardIter>::value_type>);
		3624
		3625	if (__first == __last)
		3626	return true;
		3627
		3628	_ForwardIter __next = __first;
		3629	for (++__next; __next != __last; __first = __next, ++__next) {
		3630	if (__comp(__next, __first))
		3631	return false;
		3632	}
		3633
		3634	return true;
		3635	}
		3636
		3637	} // namespace std
		3638
		3639	#endif /* __SGI_STL_INTERNAL_ALGO_H */
		3640
		3641	// Local Variables:
		3642	// mode:C++
		3643	// End:

Subversion Repositories Kolibri OS

(root)/contrib/media/updf/include/bits/stl_algo.h @ 5507 – Rev 4680