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