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