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