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