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