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