1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
5 // Free Software Foundation, Inc.
7 // This file is part of the GNU ISO C++ Library. This library is free
8 // software; you can redistribute it and/or modify it under the
9 // terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 3, or (at your option)
13 // This library is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU General Public License for more details.
18 // Under Section 7 of GPL version 3, you are granted additional
19 // permissions described in the GCC Runtime Library Exception, version
20 // 3.1, as published by the Free Software Foundation.
22 // You should have received a copy of the GNU General Public License and
23 // a copy of the GCC Runtime Library Exception along with this program;
24 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25 // <http://www.gnu.org/licenses/>.
30 * Hewlett-Packard Company
32 * Permission to use, copy, modify, distribute and sell this software
33 * and its documentation for any purpose is hereby granted without fee,
34 * provided that the above copyright notice appear in all copies and
35 * that both that copyright notice and this permission notice appear
36 * in supporting documentation. Hewlett-Packard Company makes no
37 * representations about the suitability of this software for any
38 * purpose. It is provided "as is" without express or implied warranty.
42 * Silicon Graphics Computer Systems, Inc.
44 * Permission to use, copy, modify, distribute and sell this software
45 * and its documentation for any purpose is hereby granted without fee,
46 * provided that the above copyright notice appear in all copies and
47 * that both that copyright notice and this permission notice appear
48 * in supporting documentation. Silicon Graphics makes no
49 * representations about the suitability of this software for any
50 * purpose. It is provided "as is" without express or implied warranty.
53 /** @file bits/stl_algo.h
54 * This is an internal header file, included by other library headers.
55 * Do not attempt to use it directly. @headername{algorithm}
61 #include <cstdlib> // for rand
62 #include <bits/algorithmfwd.h>
63 #include <bits/stl_heap.h>
64 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
66 #ifdef __GXX_EXPERIMENTAL_CXX0X__
67 #include <random> // for std::uniform_int_distribution
68 #include <functional> // for std::bind
71 // See concept_check.h for the __glibcxx_*_requires macros.
73 namespace std _GLIBCXX_VISIBILITY(default)
75 _GLIBCXX_BEGIN_NAMESPACE_VERSION
77 /// Swaps the median value of *__a, *__b and *__c to *__a
78 template<typename _Iterator>
80 __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c)
82 // concept requirements
83 __glibcxx_function_requires(_LessThanComparableConcept<
84 typename iterator_traits<_Iterator>::value_type>)
89 std::iter_swap(__a, __b);
91 std::iter_swap(__a, __c);
96 std::iter_swap(__a, __c);
98 std::iter_swap(__a, __b);
101 /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
102 template<typename _Iterator, typename _Compare>
104 __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
107 // concept requirements
108 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
109 typename iterator_traits<_Iterator>::value_type,
110 typename iterator_traits<_Iterator>::value_type>)
112 if (__comp(*__a, *__b))
114 if (__comp(*__b, *__c))
115 std::iter_swap(__a, __b);
116 else if (__comp(*__a, *__c))
117 std::iter_swap(__a, __c);
119 else if (__comp(*__a, *__c))
121 else if (__comp(*__b, *__c))
122 std::iter_swap(__a, __c);
124 std::iter_swap(__a, __b);
129 /// This is an overload used by find() for the Input Iterator case.
130 template<typename _InputIterator, typename _Tp>
131 inline _InputIterator
132 __find(_InputIterator __first, _InputIterator __last,
133 const _Tp& __val, input_iterator_tag)
135 while (__first != __last && !(*__first == __val))
140 /// This is an overload used by find_if() for the Input Iterator case.
141 template<typename _InputIterator, typename _Predicate>
142 inline _InputIterator
143 __find_if(_InputIterator __first, _InputIterator __last,
144 _Predicate __pred, input_iterator_tag)
146 while (__first != __last && !bool(__pred(*__first)))
151 /// This is an overload used by find() for the RAI case.
152 template<typename _RandomAccessIterator, typename _Tp>
153 _RandomAccessIterator
154 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
155 const _Tp& __val, random_access_iterator_tag)
157 typename iterator_traits<_RandomAccessIterator>::difference_type
158 __trip_count = (__last - __first) >> 2;
160 for (; __trip_count > 0; --__trip_count)
162 if (*__first == __val)
166 if (*__first == __val)
170 if (*__first == __val)
174 if (*__first == __val)
179 switch (__last - __first)
182 if (*__first == __val)
186 if (*__first == __val)
190 if (*__first == __val)
199 /// This is an overload used by find_if() for the RAI case.
200 template<typename _RandomAccessIterator, typename _Predicate>
201 _RandomAccessIterator
202 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
203 _Predicate __pred, random_access_iterator_tag)
205 typename iterator_traits<_RandomAccessIterator>::difference_type
206 __trip_count = (__last - __first) >> 2;
208 for (; __trip_count > 0; --__trip_count)
210 if (__pred(*__first))
214 if (__pred(*__first))
218 if (__pred(*__first))
222 if (__pred(*__first))
227 switch (__last - __first)
230 if (__pred(*__first))
234 if (__pred(*__first))
238 if (__pred(*__first))
247 /// This is an overload used by find_if_not() for the Input Iterator case.
248 template<typename _InputIterator, typename _Predicate>
249 inline _InputIterator
250 __find_if_not(_InputIterator __first, _InputIterator __last,
251 _Predicate __pred, input_iterator_tag)
253 while (__first != __last && bool(__pred(*__first)))
258 /// This is an overload used by find_if_not() for the RAI case.
259 template<typename _RandomAccessIterator, typename _Predicate>
260 _RandomAccessIterator
261 __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
262 _Predicate __pred, random_access_iterator_tag)
264 typename iterator_traits<_RandomAccessIterator>::difference_type
265 __trip_count = (__last - __first) >> 2;
267 for (; __trip_count > 0; --__trip_count)
269 if (!bool(__pred(*__first)))
273 if (!bool(__pred(*__first)))
277 if (!bool(__pred(*__first)))
281 if (!bool(__pred(*__first)))
286 switch (__last - __first)
289 if (!bool(__pred(*__first)))
293 if (!bool(__pred(*__first)))
297 if (!bool(__pred(*__first)))
306 /// Provided for stable_partition to use.
307 template<typename _InputIterator, typename _Predicate>
308 inline _InputIterator
309 __find_if_not(_InputIterator __first, _InputIterator __last,
312 return std::__find_if_not(__first, __last, __pred,
313 std::__iterator_category(__first));
316 /// Like find_if_not(), but uses and updates a count of the
317 /// remaining range length instead of comparing against an end
319 template<typename _InputIterator, typename _Predicate, typename _Distance>
321 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
323 for (; __len; --__len, ++__first)
324 if (!bool(__pred(*__first)))
331 // set_symmetric_difference
343 * This is an uglified
344 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
345 * overloaded for forward iterators.
347 template<typename _ForwardIterator, typename _Integer, typename _Tp>
349 __search_n(_ForwardIterator __first, _ForwardIterator __last,
350 _Integer __count, const _Tp& __val,
351 std::forward_iterator_tag)
353 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
354 while (__first != __last)
356 typename iterator_traits<_ForwardIterator>::difference_type
358 _ForwardIterator __i = __first;
360 while (__i != __last && __n != 1 && *__i == __val)
369 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
375 * This is an uglified
376 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
377 * overloaded for random access iterators.
379 template<typename _RandomAccessIter, typename _Integer, typename _Tp>
381 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
382 _Integer __count, const _Tp& __val,
383 std::random_access_iterator_tag)
386 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
389 _DistanceType __tailSize = __last - __first;
390 const _DistanceType __pattSize = __count;
392 if (__tailSize < __pattSize)
395 const _DistanceType __skipOffset = __pattSize - 1;
396 _RandomAccessIter __lookAhead = __first + __skipOffset;
397 __tailSize -= __pattSize;
399 while (1) // the main loop...
401 // __lookAhead here is always pointing to the last element of next
403 while (!(*__lookAhead == __val)) // the skip loop...
405 if (__tailSize < __pattSize)
406 return __last; // Failure
407 __lookAhead += __pattSize;
408 __tailSize -= __pattSize;
410 _DistanceType __remainder = __skipOffset;
411 for (_RandomAccessIter __backTrack = __lookAhead - 1;
412 *__backTrack == __val; --__backTrack)
414 if (--__remainder == 0)
415 return (__lookAhead - __skipOffset); // Success
417 if (__remainder > __tailSize)
418 return __last; // Failure
419 __lookAhead += __remainder;
420 __tailSize -= __remainder;
427 * This is an uglified
428 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
430 * overloaded for forward iterators.
432 template<typename _ForwardIterator, typename _Integer, typename _Tp,
433 typename _BinaryPredicate>
435 __search_n(_ForwardIterator __first, _ForwardIterator __last,
436 _Integer __count, const _Tp& __val,
437 _BinaryPredicate __binary_pred, std::forward_iterator_tag)
439 while (__first != __last && !bool(__binary_pred(*__first, __val)))
442 while (__first != __last)
444 typename iterator_traits<_ForwardIterator>::difference_type
446 _ForwardIterator __i = __first;
448 while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
458 while (__first != __last
459 && !bool(__binary_pred(*__first, __val)))
466 * This is an uglified
467 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
469 * overloaded for random access iterators.
471 template<typename _RandomAccessIter, typename _Integer, typename _Tp,
472 typename _BinaryPredicate>
474 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
475 _Integer __count, const _Tp& __val,
476 _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
479 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
482 _DistanceType __tailSize = __last - __first;
483 const _DistanceType __pattSize = __count;
485 if (__tailSize < __pattSize)
488 const _DistanceType __skipOffset = __pattSize - 1;
489 _RandomAccessIter __lookAhead = __first + __skipOffset;
490 __tailSize -= __pattSize;
492 while (1) // the main loop...
494 // __lookAhead here is always pointing to the last element of next
496 while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
498 if (__tailSize < __pattSize)
499 return __last; // Failure
500 __lookAhead += __pattSize;
501 __tailSize -= __pattSize;
503 _DistanceType __remainder = __skipOffset;
504 for (_RandomAccessIter __backTrack = __lookAhead - 1;
505 __binary_pred(*__backTrack, __val); --__backTrack)
507 if (--__remainder == 0)
508 return (__lookAhead - __skipOffset); // Success
510 if (__remainder > __tailSize)
511 return __last; // Failure
512 __lookAhead += __remainder;
513 __tailSize -= __remainder;
517 // find_end for forward iterators.
518 template<typename _ForwardIterator1, typename _ForwardIterator2>
520 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
521 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
522 forward_iterator_tag, forward_iterator_tag)
524 if (__first2 == __last2)
528 _ForwardIterator1 __result = __last1;
531 _ForwardIterator1 __new_result
532 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
533 if (__new_result == __last1)
537 __result = __new_result;
538 __first1 = __new_result;
545 template<typename _ForwardIterator1, typename _ForwardIterator2,
546 typename _BinaryPredicate>
548 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
549 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
550 forward_iterator_tag, forward_iterator_tag,
551 _BinaryPredicate __comp)
553 if (__first2 == __last2)
557 _ForwardIterator1 __result = __last1;
560 _ForwardIterator1 __new_result
561 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
563 if (__new_result == __last1)
567 __result = __new_result;
568 __first1 = __new_result;
575 // find_end for bidirectional iterators (much faster).
576 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
577 _BidirectionalIterator1
578 __find_end(_BidirectionalIterator1 __first1,
579 _BidirectionalIterator1 __last1,
580 _BidirectionalIterator2 __first2,
581 _BidirectionalIterator2 __last2,
582 bidirectional_iterator_tag, bidirectional_iterator_tag)
584 // concept requirements
585 __glibcxx_function_requires(_BidirectionalIteratorConcept<
586 _BidirectionalIterator1>)
587 __glibcxx_function_requires(_BidirectionalIteratorConcept<
588 _BidirectionalIterator2>)
590 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
591 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
593 _RevIterator1 __rlast1(__first1);
594 _RevIterator2 __rlast2(__first2);
595 _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
597 _RevIterator2(__last2),
600 if (__rresult == __rlast1)
604 _BidirectionalIterator1 __result = __rresult.base();
605 std::advance(__result, -std::distance(__first2, __last2));
610 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
611 typename _BinaryPredicate>
612 _BidirectionalIterator1
613 __find_end(_BidirectionalIterator1 __first1,
614 _BidirectionalIterator1 __last1,
615 _BidirectionalIterator2 __first2,
616 _BidirectionalIterator2 __last2,
617 bidirectional_iterator_tag, bidirectional_iterator_tag,
618 _BinaryPredicate __comp)
620 // concept requirements
621 __glibcxx_function_requires(_BidirectionalIteratorConcept<
622 _BidirectionalIterator1>)
623 __glibcxx_function_requires(_BidirectionalIteratorConcept<
624 _BidirectionalIterator2>)
626 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
627 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
629 _RevIterator1 __rlast1(__first1);
630 _RevIterator2 __rlast2(__first2);
631 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
632 _RevIterator2(__last2), __rlast2,
635 if (__rresult == __rlast1)
639 _BidirectionalIterator1 __result = __rresult.base();
640 std::advance(__result, -std::distance(__first2, __last2));
646 * @brief Find last matching subsequence in a sequence.
647 * @ingroup non_mutating_algorithms
648 * @param __first1 Start of range to search.
649 * @param __last1 End of range to search.
650 * @param __first2 Start of sequence to match.
651 * @param __last2 End of sequence to match.
652 * @return The last iterator @c i in the range
653 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
654 * @p *(__first2+N) for each @c N in the range @p
655 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
657 * Searches the range @p [__first1,__last1) for a sub-sequence that
658 * compares equal value-by-value with the sequence given by @p
659 * [__first2,__last2) and returns an iterator to the __first
660 * element of the sub-sequence, or @p __last1 if the sub-sequence
661 * is not found. The sub-sequence will be the last such
662 * subsequence contained in [__first,__last1).
664 * Because the sub-sequence must lie completely within the range @p
665 * [__first1,__last1) it must start at a position less than @p
666 * __last1-(__last2-__first2) where @p __last2-__first2 is the
667 * length of the sub-sequence. This means that the returned
668 * iterator @c i will be in the range @p
669 * [__first1,__last1-(__last2-__first2))
671 template<typename _ForwardIterator1, typename _ForwardIterator2>
672 inline _ForwardIterator1
673 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
674 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
676 // concept requirements
677 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
678 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
679 __glibcxx_function_requires(_EqualOpConcept<
680 typename iterator_traits<_ForwardIterator1>::value_type,
681 typename iterator_traits<_ForwardIterator2>::value_type>)
682 __glibcxx_requires_valid_range(__first1, __last1);
683 __glibcxx_requires_valid_range(__first2, __last2);
685 return std::__find_end(__first1, __last1, __first2, __last2,
686 std::__iterator_category(__first1),
687 std::__iterator_category(__first2));
691 * @brief Find last matching subsequence in a sequence using a predicate.
692 * @ingroup non_mutating_algorithms
693 * @param __first1 Start of range to search.
694 * @param __last1 End of range to search.
695 * @param __first2 Start of sequence to match.
696 * @param __last2 End of sequence to match.
697 * @param __comp The predicate to use.
698 * @return The last iterator @c i in the range @p
699 * [__first1,__last1-(__last2-__first2)) such that @c
700 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
701 * range @p [0,__last2-__first2), or @p __last1 if no such iterator
704 * Searches the range @p [__first1,__last1) for a sub-sequence that
705 * compares equal value-by-value with the sequence given by @p
706 * [__first2,__last2) using comp as a predicate and returns an
707 * iterator to the first element of the sub-sequence, or @p __last1
708 * if the sub-sequence is not found. The sub-sequence will be the
709 * last such subsequence contained in [__first,__last1).
711 * Because the sub-sequence must lie completely within the range @p
712 * [__first1,__last1) it must start at a position less than @p
713 * __last1-(__last2-__first2) where @p __last2-__first2 is the
714 * length of the sub-sequence. This means that the returned
715 * iterator @c i will be in the range @p
716 * [__first1,__last1-(__last2-__first2))
718 template<typename _ForwardIterator1, typename _ForwardIterator2,
719 typename _BinaryPredicate>
720 inline _ForwardIterator1
721 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
722 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
723 _BinaryPredicate __comp)
725 // concept requirements
726 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
727 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
728 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
729 typename iterator_traits<_ForwardIterator1>::value_type,
730 typename iterator_traits<_ForwardIterator2>::value_type>)
731 __glibcxx_requires_valid_range(__first1, __last1);
732 __glibcxx_requires_valid_range(__first2, __last2);
734 return std::__find_end(__first1, __last1, __first2, __last2,
735 std::__iterator_category(__first1),
736 std::__iterator_category(__first2),
740 #ifdef __GXX_EXPERIMENTAL_CXX0X__
742 * @brief Checks that a predicate is true for all the elements
744 * @ingroup non_mutating_algorithms
745 * @param __first An input iterator.
746 * @param __last An input iterator.
747 * @param __pred A predicate.
748 * @return True if the check is true, false otherwise.
750 * Returns true if @p __pred is true for each element in the range
751 * @p [__first,__last), and false otherwise.
753 template<typename _InputIterator, typename _Predicate>
755 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
756 { return __last == std::find_if_not(__first, __last, __pred); }
759 * @brief Checks that a predicate is false for all the elements
761 * @ingroup non_mutating_algorithms
762 * @param __first An input iterator.
763 * @param __last An input iterator.
764 * @param __pred A predicate.
765 * @return True if the check is true, false otherwise.
767 * Returns true if @p __pred is false for each element in the range
768 * @p [__first,__last), and false otherwise.
770 template<typename _InputIterator, typename _Predicate>
772 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
773 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
776 * @brief Checks that a predicate is false for at least an element
778 * @ingroup non_mutating_algorithms
779 * @param __first An input iterator.
780 * @param __last An input iterator.
781 * @param __pred A predicate.
782 * @return True if the check is true, false otherwise.
784 * Returns true if an element exists in the range @p
785 * [__first,__last) such that @p __pred is true, and false
788 template<typename _InputIterator, typename _Predicate>
790 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
791 { return !std::none_of(__first, __last, __pred); }
794 * @brief Find the first element in a sequence for which a
795 * predicate is false.
796 * @ingroup non_mutating_algorithms
797 * @param __first An input iterator.
798 * @param __last An input iterator.
799 * @param __pred A predicate.
800 * @return The first iterator @c i in the range @p [__first,__last)
801 * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
803 template<typename _InputIterator, typename _Predicate>
804 inline _InputIterator
805 find_if_not(_InputIterator __first, _InputIterator __last,
808 // concept requirements
809 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
810 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
811 typename iterator_traits<_InputIterator>::value_type>)
812 __glibcxx_requires_valid_range(__first, __last);
813 return std::__find_if_not(__first, __last, __pred);
817 * @brief Checks whether the sequence is partitioned.
818 * @ingroup mutating_algorithms
819 * @param __first An input iterator.
820 * @param __last An input iterator.
821 * @param __pred A predicate.
822 * @return True if the range @p [__first,__last) is partioned by @p __pred,
823 * i.e. if all elements that satisfy @p __pred appear before those that
826 template<typename _InputIterator, typename _Predicate>
828 is_partitioned(_InputIterator __first, _InputIterator __last,
831 __first = std::find_if_not(__first, __last, __pred);
832 return std::none_of(__first, __last, __pred);
836 * @brief Find the partition point of a partitioned range.
837 * @ingroup mutating_algorithms
838 * @param __first An iterator.
839 * @param __last Another iterator.
840 * @param __pred A predicate.
841 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
842 * and @p none_of(mid, __last, __pred) are both true.
844 template<typename _ForwardIterator, typename _Predicate>
846 partition_point(_ForwardIterator __first, _ForwardIterator __last,
849 // concept requirements
850 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
851 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
852 typename iterator_traits<_ForwardIterator>::value_type>)
854 // A specific debug-mode test will be necessary...
855 __glibcxx_requires_valid_range(__first, __last);
857 typedef typename iterator_traits<_ForwardIterator>::difference_type
860 _DistanceType __len = std::distance(__first, __last);
861 _DistanceType __half;
862 _ForwardIterator __middle;
868 std::advance(__middle, __half);
869 if (__pred(*__middle))
873 __len = __len - __half - 1;
884 * @brief Copy a sequence, removing elements of a given value.
885 * @ingroup mutating_algorithms
886 * @param __first An input iterator.
887 * @param __last An input iterator.
888 * @param __result An output iterator.
889 * @param __value The value to be removed.
890 * @return An iterator designating the end of the resulting sequence.
892 * Copies each element in the range @p [__first,__last) not equal
893 * to @p __value to the range beginning at @p __result.
894 * remove_copy() is stable, so the relative order of elements that
895 * are copied is unchanged.
897 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
899 remove_copy(_InputIterator __first, _InputIterator __last,
900 _OutputIterator __result, const _Tp& __value)
902 // concept requirements
903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
904 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
905 typename iterator_traits<_InputIterator>::value_type>)
906 __glibcxx_function_requires(_EqualOpConcept<
907 typename iterator_traits<_InputIterator>::value_type, _Tp>)
908 __glibcxx_requires_valid_range(__first, __last);
910 for (; __first != __last; ++__first)
911 if (!(*__first == __value))
913 *__result = *__first;
920 * @brief Copy a sequence, removing elements for which a predicate is true.
921 * @ingroup mutating_algorithms
922 * @param __first An input iterator.
923 * @param __last An input iterator.
924 * @param __result An output iterator.
925 * @param __pred A predicate.
926 * @return An iterator designating the end of the resulting sequence.
928 * Copies each element in the range @p [__first,__last) for which
929 * @p __pred returns false to the range beginning at @p __result.
931 * remove_copy_if() is stable, so the relative order of elements that are
932 * copied is unchanged.
934 template<typename _InputIterator, typename _OutputIterator,
937 remove_copy_if(_InputIterator __first, _InputIterator __last,
938 _OutputIterator __result, _Predicate __pred)
940 // concept requirements
941 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
942 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
943 typename iterator_traits<_InputIterator>::value_type>)
944 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
945 typename iterator_traits<_InputIterator>::value_type>)
946 __glibcxx_requires_valid_range(__first, __last);
948 for (; __first != __last; ++__first)
949 if (!bool(__pred(*__first)))
951 *__result = *__first;
957 #ifdef __GXX_EXPERIMENTAL_CXX0X__
959 * @brief Copy the elements of a sequence for which a predicate is true.
960 * @ingroup mutating_algorithms
961 * @param __first An input iterator.
962 * @param __last An input iterator.
963 * @param __result An output iterator.
964 * @param __pred A predicate.
965 * @return An iterator designating the end of the resulting sequence.
967 * Copies each element in the range @p [__first,__last) for which
968 * @p __pred returns true to the range beginning at @p __result.
970 * copy_if() is stable, so the relative order of elements that are
971 * copied is unchanged.
973 template<typename _InputIterator, typename _OutputIterator,
976 copy_if(_InputIterator __first, _InputIterator __last,
977 _OutputIterator __result, _Predicate __pred)
979 // concept requirements
980 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
981 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
982 typename iterator_traits<_InputIterator>::value_type>)
983 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
984 typename iterator_traits<_InputIterator>::value_type>)
985 __glibcxx_requires_valid_range(__first, __last);
987 for (; __first != __last; ++__first)
988 if (__pred(*__first))
990 *__result = *__first;
997 template<typename _InputIterator, typename _Size, typename _OutputIterator>
999 __copy_n(_InputIterator __first, _Size __n,
1000 _OutputIterator __result, input_iterator_tag)
1006 *__result = *__first;
1017 template<typename _RandomAccessIterator, typename _Size,
1018 typename _OutputIterator>
1019 inline _OutputIterator
1020 __copy_n(_RandomAccessIterator __first, _Size __n,
1021 _OutputIterator __result, random_access_iterator_tag)
1022 { return std::copy(__first, __first + __n, __result); }
1025 * @brief Copies the range [first,first+n) into [result,result+n).
1026 * @ingroup mutating_algorithms
1027 * @param __first An input iterator.
1028 * @param __n The number of elements to copy.
1029 * @param __result An output iterator.
1032 * This inline function will boil down to a call to @c memmove whenever
1033 * possible. Failing that, if random access iterators are passed, then the
1034 * loop count will be known (and therefore a candidate for compiler
1035 * optimizations such as unrolling).
1037 template<typename _InputIterator, typename _Size, typename _OutputIterator>
1038 inline _OutputIterator
1039 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1041 // concept requirements
1042 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1043 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1044 typename iterator_traits<_InputIterator>::value_type>)
1046 return std::__copy_n(__first, __n, __result,
1047 std::__iterator_category(__first));
1051 * @brief Copy the elements of a sequence to separate output sequences
1052 * depending on the truth value of a predicate.
1053 * @ingroup mutating_algorithms
1054 * @param __first An input iterator.
1055 * @param __last An input iterator.
1056 * @param __out_true An output iterator.
1057 * @param __out_false An output iterator.
1058 * @param __pred A predicate.
1059 * @return A pair designating the ends of the resulting sequences.
1061 * Copies each element in the range @p [__first,__last) for which
1062 * @p __pred returns true to the range beginning at @p out_true
1063 * and each element for which @p __pred returns false to @p __out_false.
1065 template<typename _InputIterator, typename _OutputIterator1,
1066 typename _OutputIterator2, typename _Predicate>
1067 pair<_OutputIterator1, _OutputIterator2>
1068 partition_copy(_InputIterator __first, _InputIterator __last,
1069 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1072 // concept requirements
1073 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1074 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1075 typename iterator_traits<_InputIterator>::value_type>)
1076 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1077 typename iterator_traits<_InputIterator>::value_type>)
1078 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1079 typename iterator_traits<_InputIterator>::value_type>)
1080 __glibcxx_requires_valid_range(__first, __last);
1082 for (; __first != __last; ++__first)
1083 if (__pred(*__first))
1085 *__out_true = *__first;
1090 *__out_false = *__first;
1094 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1099 * @brief Remove elements from a sequence.
1100 * @ingroup mutating_algorithms
1101 * @param __first An input iterator.
1102 * @param __last An input iterator.
1103 * @param __value The value to be removed.
1104 * @return An iterator designating the end of the resulting sequence.
1106 * All elements equal to @p __value are removed from the range
1107 * @p [__first,__last).
1109 * remove() is stable, so the relative order of elements that are
1110 * not removed is unchanged.
1112 * Elements between the end of the resulting sequence and @p __last
1113 * are still present, but their value is unspecified.
1115 template<typename _ForwardIterator, typename _Tp>
1117 remove(_ForwardIterator __first, _ForwardIterator __last,
1120 // concept requirements
1121 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1123 __glibcxx_function_requires(_EqualOpConcept<
1124 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1125 __glibcxx_requires_valid_range(__first, __last);
1127 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1128 if(__first == __last)
1130 _ForwardIterator __result = __first;
1132 for(; __first != __last; ++__first)
1133 if(!(*__first == __value))
1135 *__result = _GLIBCXX_MOVE(*__first);
1142 * @brief Remove elements from a sequence using a predicate.
1143 * @ingroup mutating_algorithms
1144 * @param __first A forward iterator.
1145 * @param __last A forward iterator.
1146 * @param __pred A predicate.
1147 * @return An iterator designating the end of the resulting sequence.
1149 * All elements for which @p __pred returns true are removed from the range
1150 * @p [__first,__last).
1152 * remove_if() is stable, so the relative order of elements that are
1153 * not removed is unchanged.
1155 * Elements between the end of the resulting sequence and @p __last
1156 * are still present, but their value is unspecified.
1158 template<typename _ForwardIterator, typename _Predicate>
1160 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1163 // concept requirements
1164 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1166 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1167 typename iterator_traits<_ForwardIterator>::value_type>)
1168 __glibcxx_requires_valid_range(__first, __last);
1170 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1171 if(__first == __last)
1173 _ForwardIterator __result = __first;
1175 for(; __first != __last; ++__first)
1176 if(!bool(__pred(*__first)))
1178 *__result = _GLIBCXX_MOVE(*__first);
1185 * @brief Remove consecutive duplicate values from a sequence.
1186 * @ingroup mutating_algorithms
1187 * @param __first A forward iterator.
1188 * @param __last A forward iterator.
1189 * @return An iterator designating the end of the resulting sequence.
1191 * Removes all but the first element from each group of consecutive
1192 * values that compare equal.
1193 * unique() is stable, so the relative order of elements that are
1194 * not removed is unchanged.
1195 * Elements between the end of the resulting sequence and @p __last
1196 * are still present, but their value is unspecified.
1198 template<typename _ForwardIterator>
1200 unique(_ForwardIterator __first, _ForwardIterator __last)
1202 // concept requirements
1203 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1205 __glibcxx_function_requires(_EqualityComparableConcept<
1206 typename iterator_traits<_ForwardIterator>::value_type>)
1207 __glibcxx_requires_valid_range(__first, __last);
1209 // Skip the beginning, if already unique.
1210 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1211 if (__first == __last)
1214 // Do the real copy work.
1215 _ForwardIterator __dest = __first;
1217 while (++__first != __last)
1218 if (!(*__dest == *__first))
1219 *++__dest = _GLIBCXX_MOVE(*__first);
1224 * @brief Remove consecutive values from a sequence using a predicate.
1225 * @ingroup mutating_algorithms
1226 * @param __first A forward iterator.
1227 * @param __last A forward iterator.
1228 * @param __binary_pred A binary predicate.
1229 * @return An iterator designating the end of the resulting sequence.
1231 * Removes all but the first element from each group of consecutive
1232 * values for which @p __binary_pred returns true.
1233 * unique() is stable, so the relative order of elements that are
1234 * not removed is unchanged.
1235 * Elements between the end of the resulting sequence and @p __last
1236 * are still present, but their value is unspecified.
1238 template<typename _ForwardIterator, typename _BinaryPredicate>
1240 unique(_ForwardIterator __first, _ForwardIterator __last,
1241 _BinaryPredicate __binary_pred)
1243 // concept requirements
1244 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1246 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1247 typename iterator_traits<_ForwardIterator>::value_type,
1248 typename iterator_traits<_ForwardIterator>::value_type>)
1249 __glibcxx_requires_valid_range(__first, __last);
1251 // Skip the beginning, if already unique.
1252 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1253 if (__first == __last)
1256 // Do the real copy work.
1257 _ForwardIterator __dest = __first;
1259 while (++__first != __last)
1260 if (!bool(__binary_pred(*__dest, *__first)))
1261 *++__dest = _GLIBCXX_MOVE(*__first);
1266 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1268 * overloaded for forward iterators and output iterator as result.
1270 template<typename _ForwardIterator, typename _OutputIterator>
1272 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1273 _OutputIterator __result,
1274 forward_iterator_tag, output_iterator_tag)
1276 // concept requirements -- taken care of in dispatching function
1277 _ForwardIterator __next = __first;
1278 *__result = *__first;
1279 while (++__next != __last)
1280 if (!(*__first == *__next))
1283 *++__result = *__first;
1289 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1291 * overloaded for input iterators and output iterator as result.
1293 template<typename _InputIterator, typename _OutputIterator>
1295 __unique_copy(_InputIterator __first, _InputIterator __last,
1296 _OutputIterator __result,
1297 input_iterator_tag, output_iterator_tag)
1299 // concept requirements -- taken care of in dispatching function
1300 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1301 *__result = __value;
1302 while (++__first != __last)
1303 if (!(__value == *__first))
1306 *++__result = __value;
1312 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1314 * overloaded for input iterators and forward iterator as result.
1316 template<typename _InputIterator, typename _ForwardIterator>
1318 __unique_copy(_InputIterator __first, _InputIterator __last,
1319 _ForwardIterator __result,
1320 input_iterator_tag, forward_iterator_tag)
1322 // concept requirements -- taken care of in dispatching function
1323 *__result = *__first;
1324 while (++__first != __last)
1325 if (!(*__result == *__first))
1326 *++__result = *__first;
1331 * This is an uglified
1332 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1334 * overloaded for forward iterators and output iterator as result.
1336 template<typename _ForwardIterator, typename _OutputIterator,
1337 typename _BinaryPredicate>
1339 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1340 _OutputIterator __result, _BinaryPredicate __binary_pred,
1341 forward_iterator_tag, output_iterator_tag)
1343 // concept requirements -- iterators already checked
1344 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1345 typename iterator_traits<_ForwardIterator>::value_type,
1346 typename iterator_traits<_ForwardIterator>::value_type>)
1348 _ForwardIterator __next = __first;
1349 *__result = *__first;
1350 while (++__next != __last)
1351 if (!bool(__binary_pred(*__first, *__next)))
1354 *++__result = *__first;
1360 * This is an uglified
1361 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1363 * overloaded for input iterators and output iterator as result.
1365 template<typename _InputIterator, typename _OutputIterator,
1366 typename _BinaryPredicate>
1368 __unique_copy(_InputIterator __first, _InputIterator __last,
1369 _OutputIterator __result, _BinaryPredicate __binary_pred,
1370 input_iterator_tag, output_iterator_tag)
1372 // concept requirements -- iterators already checked
1373 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1374 typename iterator_traits<_InputIterator>::value_type,
1375 typename iterator_traits<_InputIterator>::value_type>)
1377 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1378 *__result = __value;
1379 while (++__first != __last)
1380 if (!bool(__binary_pred(__value, *__first)))
1383 *++__result = __value;
1389 * This is an uglified
1390 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1392 * overloaded for input iterators and forward iterator as result.
1394 template<typename _InputIterator, typename _ForwardIterator,
1395 typename _BinaryPredicate>
1397 __unique_copy(_InputIterator __first, _InputIterator __last,
1398 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1399 input_iterator_tag, forward_iterator_tag)
1401 // concept requirements -- iterators already checked
1402 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1403 typename iterator_traits<_ForwardIterator>::value_type,
1404 typename iterator_traits<_InputIterator>::value_type>)
1406 *__result = *__first;
1407 while (++__first != __last)
1408 if (!bool(__binary_pred(*__result, *__first)))
1409 *++__result = *__first;
1414 * This is an uglified reverse(_BidirectionalIterator,
1415 * _BidirectionalIterator)
1416 * overloaded for bidirectional iterators.
1418 template<typename _BidirectionalIterator>
1420 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1421 bidirectional_iterator_tag)
1424 if (__first == __last || __first == --__last)
1428 std::iter_swap(__first, __last);
1434 * This is an uglified reverse(_BidirectionalIterator,
1435 * _BidirectionalIterator)
1436 * overloaded for random access iterators.
1438 template<typename _RandomAccessIterator>
1440 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1441 random_access_iterator_tag)
1443 if (__first == __last)
1446 while (__first < __last)
1448 std::iter_swap(__first, __last);
1455 * @brief Reverse a sequence.
1456 * @ingroup mutating_algorithms
1457 * @param __first A bidirectional iterator.
1458 * @param __last A bidirectional iterator.
1459 * @return reverse() returns no value.
1461 * Reverses the order of the elements in the range @p [__first,__last),
1462 * so that the first element becomes the last etc.
1463 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1464 * swaps @p *(__first+i) and @p *(__last-(i+1))
1466 template<typename _BidirectionalIterator>
1468 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1470 // concept requirements
1471 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1472 _BidirectionalIterator>)
1473 __glibcxx_requires_valid_range(__first, __last);
1474 std::__reverse(__first, __last, std::__iterator_category(__first));
1478 * @brief Copy a sequence, reversing its elements.
1479 * @ingroup mutating_algorithms
1480 * @param __first A bidirectional iterator.
1481 * @param __last A bidirectional iterator.
1482 * @param __result An output iterator.
1483 * @return An iterator designating the end of the resulting sequence.
1485 * Copies the elements in the range @p [__first,__last) to the
1486 * range @p [__result,__result+(__last-__first)) such that the
1487 * order of the elements is reversed. For every @c i such that @p
1488 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1489 * assignment @p *(__result+(__last-__first)-i) = *(__first+i).
1490 * The ranges @p [__first,__last) and @p
1491 * [__result,__result+(__last-__first)) must not overlap.
1493 template<typename _BidirectionalIterator, typename _OutputIterator>
1495 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1496 _OutputIterator __result)
1498 // concept requirements
1499 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1500 _BidirectionalIterator>)
1501 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1502 typename iterator_traits<_BidirectionalIterator>::value_type>)
1503 __glibcxx_requires_valid_range(__first, __last);
1505 while (__first != __last)
1508 *__result = *__last;
1515 * This is a helper function for the rotate algorithm specialized on RAIs.
1516 * It returns the greatest common divisor of two integer values.
1518 template<typename _EuclideanRingElement>
1519 _EuclideanRingElement
1520 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1524 _EuclideanRingElement __t = __m % __n;
1531 /// This is a helper function for the rotate algorithm.
1532 template<typename _ForwardIterator>
1534 __rotate(_ForwardIterator __first,
1535 _ForwardIterator __middle,
1536 _ForwardIterator __last,
1537 forward_iterator_tag)
1539 if (__first == __middle || __last == __middle)
1542 _ForwardIterator __first2 = __middle;
1545 std::iter_swap(__first, __first2);
1548 if (__first == __middle)
1549 __middle = __first2;
1551 while (__first2 != __last);
1553 __first2 = __middle;
1555 while (__first2 != __last)
1557 std::iter_swap(__first, __first2);
1560 if (__first == __middle)
1561 __middle = __first2;
1562 else if (__first2 == __last)
1563 __first2 = __middle;
1567 /// This is a helper function for the rotate algorithm.
1568 template<typename _BidirectionalIterator>
1570 __rotate(_BidirectionalIterator __first,
1571 _BidirectionalIterator __middle,
1572 _BidirectionalIterator __last,
1573 bidirectional_iterator_tag)
1575 // concept requirements
1576 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1577 _BidirectionalIterator>)
1579 if (__first == __middle || __last == __middle)
1582 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1583 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1585 while (__first != __middle && __middle != __last)
1587 std::iter_swap(__first, --__last);
1591 if (__first == __middle)
1592 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1594 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1597 /// This is a helper function for the rotate algorithm.
1598 template<typename _RandomAccessIterator>
1600 __rotate(_RandomAccessIterator __first,
1601 _RandomAccessIterator __middle,
1602 _RandomAccessIterator __last,
1603 random_access_iterator_tag)
1605 // concept requirements
1606 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1607 _RandomAccessIterator>)
1609 if (__first == __middle || __last == __middle)
1612 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1614 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1617 _Distance __n = __last - __first;
1618 _Distance __k = __middle - __first;
1620 if (__k == __n - __k)
1622 std::swap_ranges(__first, __middle, __middle);
1626 _RandomAccessIterator __p = __first;
1630 if (__k < __n - __k)
1632 if (__is_pod(_ValueType) && __k == 1)
1634 _ValueType __t = _GLIBCXX_MOVE(*__p);
1635 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1636 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1639 _RandomAccessIterator __q = __p + __k;
1640 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1642 std::iter_swap(__p, __q);
1649 std::swap(__n, __k);
1655 if (__is_pod(_ValueType) && __k == 1)
1657 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1658 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1659 *__p = _GLIBCXX_MOVE(__t);
1662 _RandomAccessIterator __q = __p + __n;
1664 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1668 std::iter_swap(__p, __q);
1673 std::swap(__n, __k);
1679 * @brief Rotate the elements of a sequence.
1680 * @ingroup mutating_algorithms
1681 * @param __first A forward iterator.
1682 * @param __middle A forward iterator.
1683 * @param __last A forward iterator.
1686 * Rotates the elements of the range @p [__first,__last) by
1687 * @p (__middle - __first) positions so that the element at @p __middle
1688 * is moved to @p __first, the element at @p __middle+1 is moved to
1689 * @p __first+1 and so on for each element in the range
1690 * @p [__first,__last).
1692 * This effectively swaps the ranges @p [__first,__middle) and
1693 * @p [__middle,__last).
1696 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1697 * for each @p n in the range @p [0,__last-__first).
1699 template<typename _ForwardIterator>
1701 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1702 _ForwardIterator __last)
1704 // concept requirements
1705 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1707 __glibcxx_requires_valid_range(__first, __middle);
1708 __glibcxx_requires_valid_range(__middle, __last);
1710 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1712 std::__rotate(__first, __middle, __last, _IterType());
1716 * @brief Copy a sequence, rotating its elements.
1717 * @ingroup mutating_algorithms
1718 * @param __first A forward iterator.
1719 * @param __middle A forward iterator.
1720 * @param __last A forward iterator.
1721 * @param __result An output iterator.
1722 * @return An iterator designating the end of the resulting sequence.
1724 * Copies the elements of the range @p [__first,__last) to the
1725 * range beginning at @result, rotating the copied elements by
1726 * @p (__middle-__first) positions so that the element at @p __middle
1727 * is moved to @p __result, the element at @p __middle+1 is moved
1728 * to @p __result+1 and so on for each element in the range @p
1732 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1733 * for each @p n in the range @p [0,__last-__first).
1735 template<typename _ForwardIterator, typename _OutputIterator>
1737 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1738 _ForwardIterator __last, _OutputIterator __result)
1740 // concept requirements
1741 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1742 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1743 typename iterator_traits<_ForwardIterator>::value_type>)
1744 __glibcxx_requires_valid_range(__first, __middle);
1745 __glibcxx_requires_valid_range(__middle, __last);
1747 return std::copy(__first, __middle,
1748 std::copy(__middle, __last, __result));
1751 /// This is a helper function...
1752 template<typename _ForwardIterator, typename _Predicate>
1754 __partition(_ForwardIterator __first, _ForwardIterator __last,
1755 _Predicate __pred, forward_iterator_tag)
1757 if (__first == __last)
1760 while (__pred(*__first))
1761 if (++__first == __last)
1764 _ForwardIterator __next = __first;
1766 while (++__next != __last)
1767 if (__pred(*__next))
1769 std::iter_swap(__first, __next);
1776 /// This is a helper function...
1777 template<typename _BidirectionalIterator, typename _Predicate>
1778 _BidirectionalIterator
1779 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1780 _Predicate __pred, bidirectional_iterator_tag)
1785 if (__first == __last)
1787 else if (__pred(*__first))
1793 if (__first == __last)
1795 else if (!bool(__pred(*__last)))
1799 std::iter_swap(__first, __last);
1806 /// This is a helper function...
1807 /// Requires __len != 0 and !__pred(*__first),
1808 /// same as __stable_partition_adaptive.
1809 template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1811 __inplace_stable_partition(_ForwardIterator __first,
1812 _Predicate __pred, _Distance __len)
1816 _ForwardIterator __middle = __first;
1817 std::advance(__middle, __len / 2);
1818 _ForwardIterator __left_split =
1819 std::__inplace_stable_partition(__first, __pred, __len / 2);
1820 // Advance past true-predicate values to satisfy this
1821 // function's preconditions.
1822 _Distance __right_len = __len - __len / 2;
1823 _ForwardIterator __right_split =
1824 std::__find_if_not_n(__middle, __right_len, __pred);
1826 __right_split = std::__inplace_stable_partition(__middle,
1829 std::rotate(__left_split, __middle, __right_split);
1830 std::advance(__left_split, std::distance(__middle, __right_split));
1831 return __left_split;
1834 /// This is a helper function...
1835 /// Requires __first != __last and !__pred(*__first)
1836 /// and __len == distance(__first, __last).
1838 /// !__pred(*__first) allows us to guarantee that we don't
1839 /// move-assign an element onto itself.
1840 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1843 __stable_partition_adaptive(_ForwardIterator __first,
1844 _ForwardIterator __last,
1845 _Predicate __pred, _Distance __len,
1847 _Distance __buffer_size)
1849 if (__len <= __buffer_size)
1851 _ForwardIterator __result1 = __first;
1852 _Pointer __result2 = __buffer;
1853 // The precondition guarantees that !__pred(*__first), so
1854 // move that element to the buffer before starting the loop.
1855 // This ensures that we only call __pred once per element.
1856 *__result2 = _GLIBCXX_MOVE(*__first);
1859 for (; __first != __last; ++__first)
1860 if (__pred(*__first))
1862 *__result1 = _GLIBCXX_MOVE(*__first);
1867 *__result2 = _GLIBCXX_MOVE(*__first);
1870 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1875 _ForwardIterator __middle = __first;
1876 std::advance(__middle, __len / 2);
1877 _ForwardIterator __left_split =
1878 std::__stable_partition_adaptive(__first, __middle, __pred,
1879 __len / 2, __buffer,
1881 // Advance past true-predicate values to satisfy this
1882 // function's preconditions.
1883 _Distance __right_len = __len - __len / 2;
1884 _ForwardIterator __right_split =
1885 std::__find_if_not_n(__middle, __right_len, __pred);
1888 std::__stable_partition_adaptive(__right_split, __last, __pred,
1890 __buffer, __buffer_size);
1891 std::rotate(__left_split, __middle, __right_split);
1892 std::advance(__left_split, std::distance(__middle, __right_split));
1893 return __left_split;
1898 * @brief Move elements for which a predicate is true to the beginning
1899 * of a sequence, preserving relative ordering.
1900 * @ingroup mutating_algorithms
1901 * @param __first A forward iterator.
1902 * @param __last A forward iterator.
1903 * @param __pred A predicate functor.
1904 * @return An iterator @p middle such that @p __pred(i) is true for each
1905 * iterator @p i in the range @p [first,middle) and false for each @p i
1906 * in the range @p [middle,last).
1908 * Performs the same function as @p partition() with the additional
1909 * guarantee that the relative ordering of elements in each group is
1910 * preserved, so any two elements @p x and @p y in the range
1911 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1912 * relative ordering after calling @p stable_partition().
1914 template<typename _ForwardIterator, typename _Predicate>
1916 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1919 // concept requirements
1920 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1922 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1923 typename iterator_traits<_ForwardIterator>::value_type>)
1924 __glibcxx_requires_valid_range(__first, __last);
1926 __first = std::__find_if_not(__first, __last, __pred);
1928 if (__first == __last)
1932 typedef typename iterator_traits<_ForwardIterator>::value_type
1934 typedef typename iterator_traits<_ForwardIterator>::difference_type
1937 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1939 if (__buf.size() > 0)
1941 std::__stable_partition_adaptive(__first, __last, __pred,
1942 _DistanceType(__buf.requested_size()),
1944 _DistanceType(__buf.size()));
1947 std::__inplace_stable_partition(__first, __pred,
1948 _DistanceType(__buf.requested_size()));
1952 /// This is a helper function for the sort routines.
1953 template<typename _RandomAccessIterator>
1955 __heap_select(_RandomAccessIterator __first,
1956 _RandomAccessIterator __middle,
1957 _RandomAccessIterator __last)
1959 std::make_heap(__first, __middle);
1960 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1961 if (*__i < *__first)
1962 std::__pop_heap(__first, __middle, __i);
1965 /// This is a helper function for the sort routines.
1966 template<typename _RandomAccessIterator, typename _Compare>
1968 __heap_select(_RandomAccessIterator __first,
1969 _RandomAccessIterator __middle,
1970 _RandomAccessIterator __last, _Compare __comp)
1972 std::make_heap(__first, __middle, __comp);
1973 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1974 if (__comp(*__i, *__first))
1975 std::__pop_heap(__first, __middle, __i, __comp);
1981 * @brief Copy the smallest elements of a sequence.
1982 * @ingroup sorting_algorithms
1983 * @param __first An iterator.
1984 * @param __last Another iterator.
1985 * @param __result_first A random-access iterator.
1986 * @param __result_last Another random-access iterator.
1987 * @return An iterator indicating the end of the resulting sequence.
1989 * Copies and sorts the smallest N values from the range @p [__first,__last)
1990 * to the range beginning at @p __result_first, where the number of
1991 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1992 * @p (__result_last-__result_first).
1993 * After the sort if @e i and @e j are iterators in the range
1994 * @p [__result_first,__result_first+N) such that i precedes j then
1996 * The value returned is @p __result_first+N.
1998 template<typename _InputIterator, typename _RandomAccessIterator>
1999 _RandomAccessIterator
2000 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2001 _RandomAccessIterator __result_first,
2002 _RandomAccessIterator __result_last)
2004 typedef typename iterator_traits<_InputIterator>::value_type
2006 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2008 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2011 // concept requirements
2012 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2013 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2015 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2017 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2018 __glibcxx_requires_valid_range(__first, __last);
2019 __glibcxx_requires_valid_range(__result_first, __result_last);
2021 if (__result_first == __result_last)
2022 return __result_last;
2023 _RandomAccessIterator __result_real_last = __result_first;
2024 while(__first != __last && __result_real_last != __result_last)
2026 *__result_real_last = *__first;
2027 ++__result_real_last;
2030 std::make_heap(__result_first, __result_real_last);
2031 while (__first != __last)
2033 if (*__first < *__result_first)
2034 std::__adjust_heap(__result_first, _DistanceType(0),
2035 _DistanceType(__result_real_last
2037 _InputValueType(*__first));
2040 std::sort_heap(__result_first, __result_real_last);
2041 return __result_real_last;
2045 * @brief Copy the smallest elements of a sequence using a predicate for
2047 * @ingroup sorting_algorithms
2048 * @param __first An input iterator.
2049 * @param __last Another input iterator.
2050 * @param __result_first A random-access iterator.
2051 * @param __result_last Another random-access iterator.
2052 * @param __comp A comparison functor.
2053 * @return An iterator indicating the end of the resulting sequence.
2055 * Copies and sorts the smallest N values from the range @p [__first,__last)
2056 * to the range beginning at @p result_first, where the number of
2057 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
2058 * @p (__result_last-__result_first).
2059 * After the sort if @e i and @e j are iterators in the range
2060 * @p [__result_first,__result_first+N) such that i precedes j then
2061 * @p __comp(*j,*i) is false.
2062 * The value returned is @p __result_first+N.
2064 template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2065 _RandomAccessIterator
2066 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2067 _RandomAccessIterator __result_first,
2068 _RandomAccessIterator __result_last,
2071 typedef typename iterator_traits<_InputIterator>::value_type
2073 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2075 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2078 // concept requirements
2079 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2080 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2081 _RandomAccessIterator>)
2082 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2084 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2085 _InputValueType, _OutputValueType>)
2086 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2087 _OutputValueType, _OutputValueType>)
2088 __glibcxx_requires_valid_range(__first, __last);
2089 __glibcxx_requires_valid_range(__result_first, __result_last);
2091 if (__result_first == __result_last)
2092 return __result_last;
2093 _RandomAccessIterator __result_real_last = __result_first;
2094 while(__first != __last && __result_real_last != __result_last)
2096 *__result_real_last = *__first;
2097 ++__result_real_last;
2100 std::make_heap(__result_first, __result_real_last, __comp);
2101 while (__first != __last)
2103 if (__comp(*__first, *__result_first))
2104 std::__adjust_heap(__result_first, _DistanceType(0),
2105 _DistanceType(__result_real_last
2107 _InputValueType(*__first),
2111 std::sort_heap(__result_first, __result_real_last, __comp);
2112 return __result_real_last;
2115 /// This is a helper function for the sort routine.
2116 template<typename _RandomAccessIterator>
2118 __unguarded_linear_insert(_RandomAccessIterator __last)
2120 typename iterator_traits<_RandomAccessIterator>::value_type
2121 __val = _GLIBCXX_MOVE(*__last);
2122 _RandomAccessIterator __next = __last;
2124 while (__val < *__next)
2126 *__last = _GLIBCXX_MOVE(*__next);
2130 *__last = _GLIBCXX_MOVE(__val);
2133 /// This is a helper function for the sort routine.
2134 template<typename _RandomAccessIterator, typename _Compare>
2136 __unguarded_linear_insert(_RandomAccessIterator __last,
2139 typename iterator_traits<_RandomAccessIterator>::value_type
2140 __val = _GLIBCXX_MOVE(*__last);
2141 _RandomAccessIterator __next = __last;
2143 while (__comp(__val, *__next))
2145 *__last = _GLIBCXX_MOVE(*__next);
2149 *__last = _GLIBCXX_MOVE(__val);
2152 /// This is a helper function for the sort routine.
2153 template<typename _RandomAccessIterator>
2155 __insertion_sort(_RandomAccessIterator __first,
2156 _RandomAccessIterator __last)
2158 if (__first == __last)
2161 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2163 if (*__i < *__first)
2165 typename iterator_traits<_RandomAccessIterator>::value_type
2166 __val = _GLIBCXX_MOVE(*__i);
2167 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2168 *__first = _GLIBCXX_MOVE(__val);
2171 std::__unguarded_linear_insert(__i);
2175 /// This is a helper function for the sort routine.
2176 template<typename _RandomAccessIterator, typename _Compare>
2178 __insertion_sort(_RandomAccessIterator __first,
2179 _RandomAccessIterator __last, _Compare __comp)
2181 if (__first == __last) return;
2183 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2185 if (__comp(*__i, *__first))
2187 typename iterator_traits<_RandomAccessIterator>::value_type
2188 __val = _GLIBCXX_MOVE(*__i);
2189 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2190 *__first = _GLIBCXX_MOVE(__val);
2193 std::__unguarded_linear_insert(__i, __comp);
2197 /// This is a helper function for the sort routine.
2198 template<typename _RandomAccessIterator>
2200 __unguarded_insertion_sort(_RandomAccessIterator __first,
2201 _RandomAccessIterator __last)
2203 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2206 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2207 std::__unguarded_linear_insert(__i);
2210 /// This is a helper function for the sort routine.
2211 template<typename _RandomAccessIterator, typename _Compare>
2213 __unguarded_insertion_sort(_RandomAccessIterator __first,
2214 _RandomAccessIterator __last, _Compare __comp)
2216 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2219 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2220 std::__unguarded_linear_insert(__i, __comp);
2225 * This controls some aspect of the sort routines.
2227 enum { _S_threshold = 16 };
2229 /// This is a helper function for the sort routine.
2230 template<typename _RandomAccessIterator>
2232 __final_insertion_sort(_RandomAccessIterator __first,
2233 _RandomAccessIterator __last)
2235 if (__last - __first > int(_S_threshold))
2237 std::__insertion_sort(__first, __first + int(_S_threshold));
2238 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2241 std::__insertion_sort(__first, __last);
2244 /// This is a helper function for the sort routine.
2245 template<typename _RandomAccessIterator, typename _Compare>
2247 __final_insertion_sort(_RandomAccessIterator __first,
2248 _RandomAccessIterator __last, _Compare __comp)
2250 if (__last - __first > int(_S_threshold))
2252 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2253 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2257 std::__insertion_sort(__first, __last, __comp);
2260 /// This is a helper function...
2261 template<typename _RandomAccessIterator, typename _Tp>
2262 _RandomAccessIterator
2263 __unguarded_partition(_RandomAccessIterator __first,
2264 _RandomAccessIterator __last, const _Tp& __pivot)
2268 while (*__first < __pivot)
2271 while (__pivot < *__last)
2273 if (!(__first < __last))
2275 std::iter_swap(__first, __last);
2280 /// This is a helper function...
2281 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2282 _RandomAccessIterator
2283 __unguarded_partition(_RandomAccessIterator __first,
2284 _RandomAccessIterator __last,
2285 const _Tp& __pivot, _Compare __comp)
2289 while (__comp(*__first, __pivot))
2292 while (__comp(__pivot, *__last))
2294 if (!(__first < __last))
2296 std::iter_swap(__first, __last);
2301 /// This is a helper function...
2302 template<typename _RandomAccessIterator>
2303 inline _RandomAccessIterator
2304 __unguarded_partition_pivot(_RandomAccessIterator __first,
2305 _RandomAccessIterator __last)
2307 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2308 std::__move_median_first(__first, __mid, (__last - 1));
2309 return std::__unguarded_partition(__first + 1, __last, *__first);
2313 /// This is a helper function...
2314 template<typename _RandomAccessIterator, typename _Compare>
2315 inline _RandomAccessIterator
2316 __unguarded_partition_pivot(_RandomAccessIterator __first,
2317 _RandomAccessIterator __last, _Compare __comp)
2319 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2320 std::__move_median_first(__first, __mid, (__last - 1), __comp);
2321 return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2324 /// This is a helper function for the sort routine.
2325 template<typename _RandomAccessIterator, typename _Size>
2327 __introsort_loop(_RandomAccessIterator __first,
2328 _RandomAccessIterator __last,
2329 _Size __depth_limit)
2331 while (__last - __first > int(_S_threshold))
2333 if (__depth_limit == 0)
2335 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2339 _RandomAccessIterator __cut =
2340 std::__unguarded_partition_pivot(__first, __last);
2341 std::__introsort_loop(__cut, __last, __depth_limit);
2346 /// This is a helper function for the sort routine.
2347 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2349 __introsort_loop(_RandomAccessIterator __first,
2350 _RandomAccessIterator __last,
2351 _Size __depth_limit, _Compare __comp)
2353 while (__last - __first > int(_S_threshold))
2355 if (__depth_limit == 0)
2357 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2361 _RandomAccessIterator __cut =
2362 std::__unguarded_partition_pivot(__first, __last, __comp);
2363 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2370 template<typename _RandomAccessIterator, typename _Size>
2372 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2373 _RandomAccessIterator __last, _Size __depth_limit)
2375 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2378 while (__last - __first > 3)
2380 if (__depth_limit == 0)
2382 std::__heap_select(__first, __nth + 1, __last);
2384 // Place the nth largest element in its final position.
2385 std::iter_swap(__first, __nth);
2389 _RandomAccessIterator __cut =
2390 std::__unguarded_partition_pivot(__first, __last);
2396 std::__insertion_sort(__first, __last);
2399 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2401 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2402 _RandomAccessIterator __last, _Size __depth_limit,
2405 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2408 while (__last - __first > 3)
2410 if (__depth_limit == 0)
2412 std::__heap_select(__first, __nth + 1, __last, __comp);
2413 // Place the nth largest element in its final position.
2414 std::iter_swap(__first, __nth);
2418 _RandomAccessIterator __cut =
2419 std::__unguarded_partition_pivot(__first, __last, __comp);
2425 std::__insertion_sort(__first, __last, __comp);
2430 // lower_bound moved to stl_algobase.h
2433 * @brief Finds the first position in which @p __val could be inserted
2434 * without changing the ordering.
2435 * @ingroup binary_search_algorithms
2436 * @param __first An iterator.
2437 * @param __last Another iterator.
2438 * @param __val The search term.
2439 * @param __comp A functor to use for comparisons.
2440 * @return An iterator pointing to the first element <em>not less
2441 * than</em> @p __val, or end() if every element is less
2443 * @ingroup binary_search_algorithms
2445 * The comparison function should have the same effects on ordering as
2446 * the function used for the initial sort.
2448 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2450 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2451 const _Tp& __val, _Compare __comp)
2453 typedef typename iterator_traits<_ForwardIterator>::value_type
2455 typedef typename iterator_traits<_ForwardIterator>::difference_type
2458 // concept requirements
2459 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2460 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2462 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2465 _DistanceType __len = std::distance(__first, __last);
2469 _DistanceType __half = __len >> 1;
2470 _ForwardIterator __middle = __first;
2471 std::advance(__middle, __half);
2472 if (__comp(*__middle, __val))
2476 __len = __len - __half - 1;
2485 * @brief Finds the last position in which @p __val could be inserted
2486 * without changing the ordering.
2487 * @ingroup binary_search_algorithms
2488 * @param __first An iterator.
2489 * @param __last Another iterator.
2490 * @param __val The search term.
2491 * @return An iterator pointing to the first element greater than @p __val,
2492 * or end() if no elements are greater than @p __val.
2493 * @ingroup binary_search_algorithms
2495 template<typename _ForwardIterator, typename _Tp>
2497 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2500 typedef typename iterator_traits<_ForwardIterator>::value_type
2502 typedef typename iterator_traits<_ForwardIterator>::difference_type
2505 // concept requirements
2506 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2507 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2508 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2510 _DistanceType __len = std::distance(__first, __last);
2514 _DistanceType __half = __len >> 1;
2515 _ForwardIterator __middle = __first;
2516 std::advance(__middle, __half);
2517 if (__val < *__middle)
2523 __len = __len - __half - 1;
2530 * @brief Finds the last position in which @p __val could be inserted
2531 * without changing the ordering.
2532 * @ingroup binary_search_algorithms
2533 * @param __first An iterator.
2534 * @param __last Another iterator.
2535 * @param __val The search term.
2536 * @param __comp A functor to use for comparisons.
2537 * @return An iterator pointing to the first element greater than @p __val,
2538 * or end() if no elements are greater than @p __val.
2539 * @ingroup binary_search_algorithms
2541 * The comparison function should have the same effects on ordering as
2542 * the function used for the initial sort.
2544 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2546 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2547 const _Tp& __val, _Compare __comp)
2549 typedef typename iterator_traits<_ForwardIterator>::value_type
2551 typedef typename iterator_traits<_ForwardIterator>::difference_type
2554 // concept requirements
2555 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2556 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2558 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2561 _DistanceType __len = std::distance(__first, __last);
2565 _DistanceType __half = __len >> 1;
2566 _ForwardIterator __middle = __first;
2567 std::advance(__middle, __half);
2568 if (__comp(__val, *__middle))
2574 __len = __len - __half - 1;
2581 * @brief Finds the largest subrange in which @p __val could be inserted
2582 * at any place in it without changing the ordering.
2583 * @ingroup binary_search_algorithms
2584 * @param __first An iterator.
2585 * @param __last Another iterator.
2586 * @param __val The search term.
2587 * @return An pair of iterators defining the subrange.
2588 * @ingroup binary_search_algorithms
2590 * This is equivalent to
2592 * std::make_pair(lower_bound(__first, __last, __val),
2593 * upper_bound(__first, __last, __val))
2595 * but does not actually call those functions.
2597 template<typename _ForwardIterator, typename _Tp>
2598 pair<_ForwardIterator, _ForwardIterator>
2599 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2602 typedef typename iterator_traits<_ForwardIterator>::value_type
2604 typedef typename iterator_traits<_ForwardIterator>::difference_type
2607 // concept requirements
2608 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2609 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2610 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2611 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2612 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2614 _DistanceType __len = std::distance(__first, __last);
2618 _DistanceType __half = __len >> 1;
2619 _ForwardIterator __middle = __first;
2620 std::advance(__middle, __half);
2621 if (*__middle < __val)
2625 __len = __len - __half - 1;
2627 else if (__val < *__middle)
2631 _ForwardIterator __left = std::lower_bound(__first, __middle,
2633 std::advance(__first, __len);
2634 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2636 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2639 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2643 * @brief Finds the largest subrange in which @p __val could be inserted
2644 * at any place in it without changing the ordering.
2645 * @param __first An iterator.
2646 * @param __last Another iterator.
2647 * @param __val The search term.
2648 * @param __comp A functor to use for comparisons.
2649 * @return An pair of iterators defining the subrange.
2650 * @ingroup binary_search_algorithms
2652 * This is equivalent to
2654 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2655 * upper_bound(__first, __last, __val, __comp))
2657 * but does not actually call those functions.
2659 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2660 pair<_ForwardIterator, _ForwardIterator>
2661 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2662 const _Tp& __val, _Compare __comp)
2664 typedef typename iterator_traits<_ForwardIterator>::value_type
2666 typedef typename iterator_traits<_ForwardIterator>::difference_type
2669 // concept requirements
2670 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2671 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2673 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2675 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2677 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2680 _DistanceType __len = std::distance(__first, __last);
2684 _DistanceType __half = __len >> 1;
2685 _ForwardIterator __middle = __first;
2686 std::advance(__middle, __half);
2687 if (__comp(*__middle, __val))
2691 __len = __len - __half - 1;
2693 else if (__comp(__val, *__middle))
2697 _ForwardIterator __left = std::lower_bound(__first, __middle,
2699 std::advance(__first, __len);
2700 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2702 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2705 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2709 * @brief Determines whether an element exists in a range.
2710 * @ingroup binary_search_algorithms
2711 * @param __first An iterator.
2712 * @param __last Another iterator.
2713 * @param __val The search term.
2714 * @return True if @p __val (or its equivalent) is in [@p
2715 * __first,@p __last ].
2717 * Note that this does not actually return an iterator to @p __val. For
2718 * that, use std::find or a container's specialized find member functions.
2720 template<typename _ForwardIterator, typename _Tp>
2722 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2725 typedef typename iterator_traits<_ForwardIterator>::value_type
2728 // concept requirements
2729 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2730 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2731 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2732 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2734 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2735 return __i != __last && !(__val < *__i);
2739 * @brief Determines whether an element exists in a range.
2740 * @ingroup binary_search_algorithms
2741 * @param __first An iterator.
2742 * @param __last Another iterator.
2743 * @param __val The search term.
2744 * @param __comp A functor to use for comparisons.
2745 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2747 * Note that this does not actually return an iterator to @p __val. For
2748 * that, use std::find or a container's specialized find member functions.
2750 * The comparison function should have the same effects on ordering as
2751 * the function used for the initial sort.
2753 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2755 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2756 const _Tp& __val, _Compare __comp)
2758 typedef typename iterator_traits<_ForwardIterator>::value_type
2761 // concept requirements
2762 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2763 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2765 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2767 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2770 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2771 return __i != __last && !bool(__comp(__val, *__i));
2776 /// This is a helper function for the __merge_adaptive routines.
2777 template<typename _InputIterator1, typename _InputIterator2,
2778 typename _OutputIterator>
2780 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2781 _InputIterator2 __first2, _InputIterator2 __last2,
2782 _OutputIterator __result)
2784 while (__first1 != __last1 && __first2 != __last2)
2786 if (*__first2 < *__first1)
2788 *__result = _GLIBCXX_MOVE(*__first2);
2793 *__result = _GLIBCXX_MOVE(*__first1);
2798 if (__first1 != __last1)
2799 _GLIBCXX_MOVE3(__first1, __last1, __result);
2802 /// This is a helper function for the __merge_adaptive routines.
2803 template<typename _InputIterator1, typename _InputIterator2,
2804 typename _OutputIterator, typename _Compare>
2806 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2807 _InputIterator2 __first2, _InputIterator2 __last2,
2808 _OutputIterator __result, _Compare __comp)
2810 while (__first1 != __last1 && __first2 != __last2)
2812 if (__comp(*__first2, *__first1))
2814 *__result = _GLIBCXX_MOVE(*__first2);
2819 *__result = _GLIBCXX_MOVE(*__first1);
2824 if (__first1 != __last1)
2825 _GLIBCXX_MOVE3(__first1, __last1, __result);
2828 /// This is a helper function for the __merge_adaptive routines.
2829 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2830 typename _BidirectionalIterator3>
2832 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2833 _BidirectionalIterator1 __last1,
2834 _BidirectionalIterator2 __first2,
2835 _BidirectionalIterator2 __last2,
2836 _BidirectionalIterator3 __result)
2838 if (__first1 == __last1)
2840 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2843 else if (__first2 == __last2)
2850 if (*__last2 < *__last1)
2852 *--__result = _GLIBCXX_MOVE(*__last1);
2853 if (__first1 == __last1)
2855 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2862 *--__result = _GLIBCXX_MOVE(*__last2);
2863 if (__first2 == __last2)
2870 /// This is a helper function for the __merge_adaptive routines.
2871 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2872 typename _BidirectionalIterator3, typename _Compare>
2874 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2875 _BidirectionalIterator1 __last1,
2876 _BidirectionalIterator2 __first2,
2877 _BidirectionalIterator2 __last2,
2878 _BidirectionalIterator3 __result,
2881 if (__first1 == __last1)
2883 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2886 else if (__first2 == __last2)
2893 if (__comp(*__last2, *__last1))
2895 *--__result = _GLIBCXX_MOVE(*__last1);
2896 if (__first1 == __last1)
2898 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2905 *--__result = _GLIBCXX_MOVE(*__last2);
2906 if (__first2 == __last2)
2913 /// This is a helper function for the merge routines.
2914 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2916 _BidirectionalIterator1
2917 __rotate_adaptive(_BidirectionalIterator1 __first,
2918 _BidirectionalIterator1 __middle,
2919 _BidirectionalIterator1 __last,
2920 _Distance __len1, _Distance __len2,
2921 _BidirectionalIterator2 __buffer,
2922 _Distance __buffer_size)
2924 _BidirectionalIterator2 __buffer_end;
2925 if (__len1 > __len2 && __len2 <= __buffer_size)
2929 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2930 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2931 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2936 else if (__len1 <= __buffer_size)
2940 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2941 _GLIBCXX_MOVE3(__middle, __last, __first);
2942 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2949 std::rotate(__first, __middle, __last);
2950 std::advance(__first, std::distance(__middle, __last));
2955 /// This is a helper function for the merge routines.
2956 template<typename _BidirectionalIterator, typename _Distance,
2959 __merge_adaptive(_BidirectionalIterator __first,
2960 _BidirectionalIterator __middle,
2961 _BidirectionalIterator __last,
2962 _Distance __len1, _Distance __len2,
2963 _Pointer __buffer, _Distance __buffer_size)
2965 if (__len1 <= __len2 && __len1 <= __buffer_size)
2967 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2968 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2971 else if (__len2 <= __buffer_size)
2973 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2974 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2975 __buffer_end, __last);
2979 _BidirectionalIterator __first_cut = __first;
2980 _BidirectionalIterator __second_cut = __middle;
2981 _Distance __len11 = 0;
2982 _Distance __len22 = 0;
2983 if (__len1 > __len2)
2985 __len11 = __len1 / 2;
2986 std::advance(__first_cut, __len11);
2987 __second_cut = std::lower_bound(__middle, __last,
2989 __len22 = std::distance(__middle, __second_cut);
2993 __len22 = __len2 / 2;
2994 std::advance(__second_cut, __len22);
2995 __first_cut = std::upper_bound(__first, __middle,
2997 __len11 = std::distance(__first, __first_cut);
2999 _BidirectionalIterator __new_middle =
3000 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3001 __len1 - __len11, __len22, __buffer,
3003 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3004 __len22, __buffer, __buffer_size);
3005 std::__merge_adaptive(__new_middle, __second_cut, __last,
3007 __len2 - __len22, __buffer, __buffer_size);
3011 /// This is a helper function for the merge routines.
3012 template<typename _BidirectionalIterator, typename _Distance,
3013 typename _Pointer, typename _Compare>
3015 __merge_adaptive(_BidirectionalIterator __first,
3016 _BidirectionalIterator __middle,
3017 _BidirectionalIterator __last,
3018 _Distance __len1, _Distance __len2,
3019 _Pointer __buffer, _Distance __buffer_size,
3022 if (__len1 <= __len2 && __len1 <= __buffer_size)
3024 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3025 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
3028 else if (__len2 <= __buffer_size)
3030 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
3031 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
3032 __buffer_end, __last, __comp);
3036 _BidirectionalIterator __first_cut = __first;
3037 _BidirectionalIterator __second_cut = __middle;
3038 _Distance __len11 = 0;
3039 _Distance __len22 = 0;
3040 if (__len1 > __len2)
3042 __len11 = __len1 / 2;
3043 std::advance(__first_cut, __len11);
3044 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3046 __len22 = std::distance(__middle, __second_cut);
3050 __len22 = __len2 / 2;
3051 std::advance(__second_cut, __len22);
3052 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3054 __len11 = std::distance(__first, __first_cut);
3056 _BidirectionalIterator __new_middle =
3057 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3058 __len1 - __len11, __len22, __buffer,
3060 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3061 __len22, __buffer, __buffer_size, __comp);
3062 std::__merge_adaptive(__new_middle, __second_cut, __last,
3064 __len2 - __len22, __buffer,
3065 __buffer_size, __comp);
3069 /// This is a helper function for the merge routines.
3070 template<typename _BidirectionalIterator, typename _Distance>
3072 __merge_without_buffer(_BidirectionalIterator __first,
3073 _BidirectionalIterator __middle,
3074 _BidirectionalIterator __last,
3075 _Distance __len1, _Distance __len2)
3077 if (__len1 == 0 || __len2 == 0)
3079 if (__len1 + __len2 == 2)
3081 if (*__middle < *__first)
3082 std::iter_swap(__first, __middle);
3085 _BidirectionalIterator __first_cut = __first;
3086 _BidirectionalIterator __second_cut = __middle;
3087 _Distance __len11 = 0;
3088 _Distance __len22 = 0;
3089 if (__len1 > __len2)
3091 __len11 = __len1 / 2;
3092 std::advance(__first_cut, __len11);
3093 __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3094 __len22 = std::distance(__middle, __second_cut);
3098 __len22 = __len2 / 2;
3099 std::advance(__second_cut, __len22);
3100 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3101 __len11 = std::distance(__first, __first_cut);
3103 std::rotate(__first_cut, __middle, __second_cut);
3104 _BidirectionalIterator __new_middle = __first_cut;
3105 std::advance(__new_middle, std::distance(__middle, __second_cut));
3106 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3108 std::__merge_without_buffer(__new_middle, __second_cut, __last,
3109 __len1 - __len11, __len2 - __len22);
3112 /// This is a helper function for the merge routines.
3113 template<typename _BidirectionalIterator, typename _Distance,
3116 __merge_without_buffer(_BidirectionalIterator __first,
3117 _BidirectionalIterator __middle,
3118 _BidirectionalIterator __last,
3119 _Distance __len1, _Distance __len2,
3122 if (__len1 == 0 || __len2 == 0)
3124 if (__len1 + __len2 == 2)
3126 if (__comp(*__middle, *__first))
3127 std::iter_swap(__first, __middle);
3130 _BidirectionalIterator __first_cut = __first;
3131 _BidirectionalIterator __second_cut = __middle;
3132 _Distance __len11 = 0;
3133 _Distance __len22 = 0;
3134 if (__len1 > __len2)
3136 __len11 = __len1 / 2;
3137 std::advance(__first_cut, __len11);
3138 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3140 __len22 = std::distance(__middle, __second_cut);
3144 __len22 = __len2 / 2;
3145 std::advance(__second_cut, __len22);
3146 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3148 __len11 = std::distance(__first, __first_cut);
3150 std::rotate(__first_cut, __middle, __second_cut);
3151 _BidirectionalIterator __new_middle = __first_cut;
3152 std::advance(__new_middle, std::distance(__middle, __second_cut));
3153 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3154 __len11, __len22, __comp);
3155 std::__merge_without_buffer(__new_middle, __second_cut, __last,
3156 __len1 - __len11, __len2 - __len22, __comp);
3160 * @brief Merges two sorted ranges in place.
3161 * @ingroup sorting_algorithms
3162 * @param __first An iterator.
3163 * @param __middle Another iterator.
3164 * @param __last Another iterator.
3167 * Merges two sorted and consecutive ranges, [__first,__middle) and
3168 * [__middle,__last), and puts the result in [__first,__last). The
3169 * output will be sorted. The sort is @e stable, that is, for
3170 * equivalent elements in the two ranges, elements from the first
3171 * range will always come before elements from the second.
3173 * If enough additional memory is available, this takes (__last-__first)-1
3174 * comparisons. Otherwise an NlogN algorithm is used, where N is
3175 * distance(__first,__last).
3177 template<typename _BidirectionalIterator>
3179 inplace_merge(_BidirectionalIterator __first,
3180 _BidirectionalIterator __middle,
3181 _BidirectionalIterator __last)
3183 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3185 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3188 // concept requirements
3189 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3190 _BidirectionalIterator>)
3191 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3192 __glibcxx_requires_sorted(__first, __middle);
3193 __glibcxx_requires_sorted(__middle, __last);
3195 if (__first == __middle || __middle == __last)
3198 _DistanceType __len1 = std::distance(__first, __middle);
3199 _DistanceType __len2 = std::distance(__middle, __last);
3201 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3203 if (__buf.begin() == 0)
3204 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3206 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3207 __buf.begin(), _DistanceType(__buf.size()));
3211 * @brief Merges two sorted ranges in place.
3212 * @ingroup sorting_algorithms
3213 * @param __first An iterator.
3214 * @param __middle Another iterator.
3215 * @param __last Another iterator.
3216 * @param __comp A functor to use for comparisons.
3219 * Merges two sorted and consecutive ranges, [__first,__middle) and
3220 * [middle,last), and puts the result in [__first,__last). The output will
3221 * be sorted. The sort is @e stable, that is, for equivalent
3222 * elements in the two ranges, elements from the first range will always
3223 * come before elements from the second.
3225 * If enough additional memory is available, this takes (__last-__first)-1
3226 * comparisons. Otherwise an NlogN algorithm is used, where N is
3227 * distance(__first,__last).
3229 * The comparison function should have the same effects on ordering as
3230 * the function used for the initial sort.
3232 template<typename _BidirectionalIterator, typename _Compare>
3234 inplace_merge(_BidirectionalIterator __first,
3235 _BidirectionalIterator __middle,
3236 _BidirectionalIterator __last,
3239 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3241 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3244 // concept requirements
3245 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3246 _BidirectionalIterator>)
3247 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3248 _ValueType, _ValueType>)
3249 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3250 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3252 if (__first == __middle || __middle == __last)
3255 const _DistanceType __len1 = std::distance(__first, __middle);
3256 const _DistanceType __len2 = std::distance(__middle, __last);
3258 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3260 if (__buf.begin() == 0)
3261 std::__merge_without_buffer(__first, __middle, __last, __len1,
3264 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3265 __buf.begin(), _DistanceType(__buf.size()),
3270 /// This is a helper function for the __merge_sort_loop routines.
3271 template<typename _InputIterator1, typename _InputIterator2,
3272 typename _OutputIterator>
3274 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3275 _InputIterator2 __first2, _InputIterator2 __last2,
3276 _OutputIterator __result)
3278 while (__first1 != __last1 && __first2 != __last2)
3280 if (*__first2 < *__first1)
3282 *__result = _GLIBCXX_MOVE(*__first2);
3287 *__result = _GLIBCXX_MOVE(*__first1);
3292 return _GLIBCXX_MOVE3(__first2, __last2,
3293 _GLIBCXX_MOVE3(__first1, __last1,
3297 /// This is a helper function for the __merge_sort_loop routines.
3298 template<typename _InputIterator1, typename _InputIterator2,
3299 typename _OutputIterator, typename _Compare>
3301 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3302 _InputIterator2 __first2, _InputIterator2 __last2,
3303 _OutputIterator __result, _Compare __comp)
3305 while (__first1 != __last1 && __first2 != __last2)
3307 if (__comp(*__first2, *__first1))
3309 *__result = _GLIBCXX_MOVE(*__first2);
3314 *__result = _GLIBCXX_MOVE(*__first1);
3319 return _GLIBCXX_MOVE3(__first2, __last2,
3320 _GLIBCXX_MOVE3(__first1, __last1,
3324 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3327 __merge_sort_loop(_RandomAccessIterator1 __first,
3328 _RandomAccessIterator1 __last,
3329 _RandomAccessIterator2 __result,
3330 _Distance __step_size)
3332 const _Distance __two_step = 2 * __step_size;
3334 while (__last - __first >= __two_step)
3336 __result = std::__move_merge(__first, __first + __step_size,
3337 __first + __step_size,
3338 __first + __two_step, __result);
3339 __first += __two_step;
3342 __step_size = std::min(_Distance(__last - __first), __step_size);
3343 std::__move_merge(__first, __first + __step_size,
3344 __first + __step_size, __last, __result);
3347 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3348 typename _Distance, typename _Compare>
3350 __merge_sort_loop(_RandomAccessIterator1 __first,
3351 _RandomAccessIterator1 __last,
3352 _RandomAccessIterator2 __result, _Distance __step_size,
3355 const _Distance __two_step = 2 * __step_size;
3357 while (__last - __first >= __two_step)
3359 __result = std::__move_merge(__first, __first + __step_size,
3360 __first + __step_size,
3361 __first + __two_step,
3363 __first += __two_step;
3365 __step_size = std::min(_Distance(__last - __first), __step_size);
3367 std::__move_merge(__first,__first + __step_size,
3368 __first + __step_size, __last, __result, __comp);
3371 template<typename _RandomAccessIterator, typename _Distance>
3373 __chunk_insertion_sort(_RandomAccessIterator __first,
3374 _RandomAccessIterator __last,
3375 _Distance __chunk_size)
3377 while (__last - __first >= __chunk_size)
3379 std::__insertion_sort(__first, __first + __chunk_size);
3380 __first += __chunk_size;
3382 std::__insertion_sort(__first, __last);
3385 template<typename _RandomAccessIterator, typename _Distance,
3388 __chunk_insertion_sort(_RandomAccessIterator __first,
3389 _RandomAccessIterator __last,
3390 _Distance __chunk_size, _Compare __comp)
3392 while (__last - __first >= __chunk_size)
3394 std::__insertion_sort(__first, __first + __chunk_size, __comp);
3395 __first += __chunk_size;
3397 std::__insertion_sort(__first, __last, __comp);
3400 enum { _S_chunk_size = 7 };
3402 template<typename _RandomAccessIterator, typename _Pointer>
3404 __merge_sort_with_buffer(_RandomAccessIterator __first,
3405 _RandomAccessIterator __last,
3408 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3411 const _Distance __len = __last - __first;
3412 const _Pointer __buffer_last = __buffer + __len;
3414 _Distance __step_size = _S_chunk_size;
3415 std::__chunk_insertion_sort(__first, __last, __step_size);
3417 while (__step_size < __len)
3419 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3421 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3426 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3428 __merge_sort_with_buffer(_RandomAccessIterator __first,
3429 _RandomAccessIterator __last,
3430 _Pointer __buffer, _Compare __comp)
3432 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3435 const _Distance __len = __last - __first;
3436 const _Pointer __buffer_last = __buffer + __len;
3438 _Distance __step_size = _S_chunk_size;
3439 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3441 while (__step_size < __len)
3443 std::__merge_sort_loop(__first, __last, __buffer,
3444 __step_size, __comp);
3446 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3447 __step_size, __comp);
3452 template<typename _RandomAccessIterator, typename _Pointer,
3455 __stable_sort_adaptive(_RandomAccessIterator __first,
3456 _RandomAccessIterator __last,
3457 _Pointer __buffer, _Distance __buffer_size)
3459 const _Distance __len = (__last - __first + 1) / 2;
3460 const _RandomAccessIterator __middle = __first + __len;
3461 if (__len > __buffer_size)
3463 std::__stable_sort_adaptive(__first, __middle,
3464 __buffer, __buffer_size);
3465 std::__stable_sort_adaptive(__middle, __last,
3466 __buffer, __buffer_size);
3470 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3471 std::__merge_sort_with_buffer(__middle, __last, __buffer);
3473 std::__merge_adaptive(__first, __middle, __last,
3474 _Distance(__middle - __first),
3475 _Distance(__last - __middle),
3476 __buffer, __buffer_size);
3479 template<typename _RandomAccessIterator, typename _Pointer,
3480 typename _Distance, typename _Compare>
3482 __stable_sort_adaptive(_RandomAccessIterator __first,
3483 _RandomAccessIterator __last,
3484 _Pointer __buffer, _Distance __buffer_size,
3487 const _Distance __len = (__last - __first + 1) / 2;
3488 const _RandomAccessIterator __middle = __first + __len;
3489 if (__len > __buffer_size)
3491 std::__stable_sort_adaptive(__first, __middle, __buffer,
3492 __buffer_size, __comp);
3493 std::__stable_sort_adaptive(__middle, __last, __buffer,
3494 __buffer_size, __comp);
3498 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3499 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3501 std::__merge_adaptive(__first, __middle, __last,
3502 _Distance(__middle - __first),
3503 _Distance(__last - __middle),
3504 __buffer, __buffer_size,
3508 /// This is a helper function for the stable sorting routines.
3509 template<typename _RandomAccessIterator>
3511 __inplace_stable_sort(_RandomAccessIterator __first,
3512 _RandomAccessIterator __last)
3514 if (__last - __first < 15)
3516 std::__insertion_sort(__first, __last);
3519 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3520 std::__inplace_stable_sort(__first, __middle);
3521 std::__inplace_stable_sort(__middle, __last);
3522 std::__merge_without_buffer(__first, __middle, __last,
3527 /// This is a helper function for the stable sorting routines.
3528 template<typename _RandomAccessIterator, typename _Compare>
3530 __inplace_stable_sort(_RandomAccessIterator __first,
3531 _RandomAccessIterator __last, _Compare __comp)
3533 if (__last - __first < 15)
3535 std::__insertion_sort(__first, __last, __comp);
3538 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3539 std::__inplace_stable_sort(__first, __middle, __comp);
3540 std::__inplace_stable_sort(__middle, __last, __comp);
3541 std::__merge_without_buffer(__first, __middle, __last,
3549 // Set algorithms: includes, set_union, set_intersection, set_difference,
3550 // set_symmetric_difference. All of these algorithms have the precondition
3551 // that their input ranges are sorted and the postcondition that their output
3552 // ranges are sorted.
3555 * @brief Determines whether all elements of a sequence exists in a range.
3556 * @param __first1 Start of search range.
3557 * @param __last1 End of search range.
3558 * @param __first2 Start of sequence
3559 * @param __last2 End of sequence.
3560 * @return True if each element in [__first2,__last2) is contained in order
3561 * within [__first1,__last1). False otherwise.
3562 * @ingroup set_algorithms
3564 * This operation expects both [__first1,__last1) and
3565 * [__first2,__last2) to be sorted. Searches for the presence of
3566 * each element in [__first2,__last2) within [__first1,__last1).
3567 * The iterators over each range only move forward, so this is a
3568 * linear algorithm. If an element in [__first2,__last2) is not
3569 * found before the search iterator reaches @p __last2, false is
3572 template<typename _InputIterator1, typename _InputIterator2>
3574 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3575 _InputIterator2 __first2, _InputIterator2 __last2)
3577 typedef typename iterator_traits<_InputIterator1>::value_type
3579 typedef typename iterator_traits<_InputIterator2>::value_type
3582 // concept requirements
3583 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3584 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3585 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3586 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3587 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3588 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3590 while (__first1 != __last1 && __first2 != __last2)
3591 if (*__first2 < *__first1)
3593 else if(*__first1 < *__first2)
3596 ++__first1, ++__first2;
3598 return __first2 == __last2;
3602 * @brief Determines whether all elements of a sequence exists in a range
3604 * @ingroup set_algorithms
3605 * @param __first1 Start of search range.
3606 * @param __last1 End of search range.
3607 * @param __first2 Start of sequence
3608 * @param __last2 End of sequence.
3609 * @param __comp Comparison function to use.
3610 * @return True if each element in [__first2,__last2) is contained
3611 * in order within [__first1,__last1) according to comp. False
3612 * otherwise. @ingroup set_algorithms
3614 * This operation expects both [__first1,__last1) and
3615 * [__first2,__last2) to be sorted. Searches for the presence of
3616 * each element in [__first2,__last2) within [__first1,__last1),
3617 * using comp to decide. The iterators over each range only move
3618 * forward, so this is a linear algorithm. If an element in
3619 * [__first2,__last2) is not found before the search iterator
3620 * reaches @p __last2, false is returned.
3622 template<typename _InputIterator1, typename _InputIterator2,
3625 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3626 _InputIterator2 __first2, _InputIterator2 __last2,
3629 typedef typename iterator_traits<_InputIterator1>::value_type
3631 typedef typename iterator_traits<_InputIterator2>::value_type
3634 // concept requirements
3635 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3636 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3637 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3638 _ValueType1, _ValueType2>)
3639 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3640 _ValueType2, _ValueType1>)
3641 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3642 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3644 while (__first1 != __last1 && __first2 != __last2)
3645 if (__comp(*__first2, *__first1))
3647 else if(__comp(*__first1, *__first2))
3650 ++__first1, ++__first2;
3652 return __first2 == __last2;
3661 // set_symmetric_difference
3666 * @brief Permute range into the next @e dictionary ordering.
3667 * @ingroup sorting_algorithms
3668 * @param __first Start of range.
3669 * @param __last End of range.
3670 * @return False if wrapped to first permutation, true otherwise.
3672 * Treats all permutations of the range as a set of @e dictionary sorted
3673 * sequences. Permutes the current sequence into the next one of this set.
3674 * Returns true if there are more sequences to generate. If the sequence
3675 * is the largest of the set, the smallest is generated and false returned.
3677 template<typename _BidirectionalIterator>
3679 next_permutation(_BidirectionalIterator __first,
3680 _BidirectionalIterator __last)
3682 // concept requirements
3683 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3684 _BidirectionalIterator>)
3685 __glibcxx_function_requires(_LessThanComparableConcept<
3686 typename iterator_traits<_BidirectionalIterator>::value_type>)
3687 __glibcxx_requires_valid_range(__first, __last);
3689 if (__first == __last)
3691 _BidirectionalIterator __i = __first;
3700 _BidirectionalIterator __ii = __i;
3704 _BidirectionalIterator __j = __last;
3705 while (!(*__i < *--__j))
3707 std::iter_swap(__i, __j);
3708 std::reverse(__ii, __last);
3713 std::reverse(__first, __last);
3720 * @brief Permute range into the next @e dictionary ordering using
3721 * comparison functor.
3722 * @ingroup sorting_algorithms
3723 * @param __first Start of range.
3724 * @param __last End of range.
3725 * @param __comp A comparison functor.
3726 * @return False if wrapped to first permutation, true otherwise.
3728 * Treats all permutations of the range [__first,__last) as a set of
3729 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3730 * sequence into the next one of this set. Returns true if there are more
3731 * sequences to generate. If the sequence is the largest of the set, the
3732 * smallest is generated and false returned.
3734 template<typename _BidirectionalIterator, typename _Compare>
3736 next_permutation(_BidirectionalIterator __first,
3737 _BidirectionalIterator __last, _Compare __comp)
3739 // concept requirements
3740 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3741 _BidirectionalIterator>)
3742 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3743 typename iterator_traits<_BidirectionalIterator>::value_type,
3744 typename iterator_traits<_BidirectionalIterator>::value_type>)
3745 __glibcxx_requires_valid_range(__first, __last);
3747 if (__first == __last)
3749 _BidirectionalIterator __i = __first;
3758 _BidirectionalIterator __ii = __i;
3760 if (__comp(*__i, *__ii))
3762 _BidirectionalIterator __j = __last;
3763 while (!bool(__comp(*__i, *--__j)))
3765 std::iter_swap(__i, __j);
3766 std::reverse(__ii, __last);
3771 std::reverse(__first, __last);
3778 * @brief Permute range into the previous @e dictionary ordering.
3779 * @ingroup sorting_algorithms
3780 * @param __first Start of range.
3781 * @param __last End of range.
3782 * @return False if wrapped to last permutation, true otherwise.
3784 * Treats all permutations of the range as a set of @e dictionary sorted
3785 * sequences. Permutes the current sequence into the previous one of this
3786 * set. Returns true if there are more sequences to generate. If the
3787 * sequence is the smallest of the set, the largest is generated and false
3790 template<typename _BidirectionalIterator>
3792 prev_permutation(_BidirectionalIterator __first,
3793 _BidirectionalIterator __last)
3795 // concept requirements
3796 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3797 _BidirectionalIterator>)
3798 __glibcxx_function_requires(_LessThanComparableConcept<
3799 typename iterator_traits<_BidirectionalIterator>::value_type>)
3800 __glibcxx_requires_valid_range(__first, __last);
3802 if (__first == __last)
3804 _BidirectionalIterator __i = __first;
3813 _BidirectionalIterator __ii = __i;
3817 _BidirectionalIterator __j = __last;
3818 while (!(*--__j < *__i))
3820 std::iter_swap(__i, __j);
3821 std::reverse(__ii, __last);
3826 std::reverse(__first, __last);
3833 * @brief Permute range into the previous @e dictionary ordering using
3834 * comparison functor.
3835 * @ingroup sorting_algorithms
3836 * @param __first Start of range.
3837 * @param __last End of range.
3838 * @param __comp A comparison functor.
3839 * @return False if wrapped to last permutation, true otherwise.
3841 * Treats all permutations of the range [__first,__last) as a set of
3842 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3843 * sequence into the previous one of this set. Returns true if there are
3844 * more sequences to generate. If the sequence is the smallest of the set,
3845 * the largest is generated and false returned.
3847 template<typename _BidirectionalIterator, typename _Compare>
3849 prev_permutation(_BidirectionalIterator __first,
3850 _BidirectionalIterator __last, _Compare __comp)
3852 // concept requirements
3853 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3854 _BidirectionalIterator>)
3855 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3856 typename iterator_traits<_BidirectionalIterator>::value_type,
3857 typename iterator_traits<_BidirectionalIterator>::value_type>)
3858 __glibcxx_requires_valid_range(__first, __last);
3860 if (__first == __last)
3862 _BidirectionalIterator __i = __first;
3871 _BidirectionalIterator __ii = __i;
3873 if (__comp(*__ii, *__i))
3875 _BidirectionalIterator __j = __last;
3876 while (!bool(__comp(*--__j, *__i)))
3878 std::iter_swap(__i, __j);
3879 std::reverse(__ii, __last);
3884 std::reverse(__first, __last);
3894 * @brief Copy a sequence, replacing each element of one value with another
3896 * @param __first An input iterator.
3897 * @param __last An input iterator.
3898 * @param __result An output iterator.
3899 * @param __old_value The value to be replaced.
3900 * @param __new_value The replacement value.
3901 * @return The end of the output sequence, @p result+(last-first).
3903 * Copies each element in the input range @p [__first,__last) to the
3904 * output range @p [__result,__result+(__last-__first)) replacing elements
3905 * equal to @p __old_value with @p __new_value.
3907 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3909 replace_copy(_InputIterator __first, _InputIterator __last,
3910 _OutputIterator __result,
3911 const _Tp& __old_value, const _Tp& __new_value)
3913 // concept requirements
3914 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3915 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3916 typename iterator_traits<_InputIterator>::value_type>)
3917 __glibcxx_function_requires(_EqualOpConcept<
3918 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3919 __glibcxx_requires_valid_range(__first, __last);
3921 for (; __first != __last; ++__first, ++__result)
3922 if (*__first == __old_value)
3923 *__result = __new_value;
3925 *__result = *__first;
3930 * @brief Copy a sequence, replacing each value for which a predicate
3931 * returns true with another value.
3932 * @ingroup mutating_algorithms
3933 * @param __first An input iterator.
3934 * @param __last An input iterator.
3935 * @param __result An output iterator.
3936 * @param __pred A predicate.
3937 * @param __new_value The replacement value.
3938 * @return The end of the output sequence, @p __result+(__last-__first).
3940 * Copies each element in the range @p [__first,__last) to the range
3941 * @p [__result,__result+(__last-__first)) replacing elements for which
3942 * @p __pred returns true with @p __new_value.
3944 template<typename _InputIterator, typename _OutputIterator,
3945 typename _Predicate, typename _Tp>
3947 replace_copy_if(_InputIterator __first, _InputIterator __last,
3948 _OutputIterator __result,
3949 _Predicate __pred, const _Tp& __new_value)
3951 // concept requirements
3952 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3953 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3954 typename iterator_traits<_InputIterator>::value_type>)
3955 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3956 typename iterator_traits<_InputIterator>::value_type>)
3957 __glibcxx_requires_valid_range(__first, __last);
3959 for (; __first != __last; ++__first, ++__result)
3960 if (__pred(*__first))
3961 *__result = __new_value;
3963 *__result = *__first;
3967 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3969 * @brief Determines whether the elements of a sequence are sorted.
3970 * @ingroup sorting_algorithms
3971 * @param __first An iterator.
3972 * @param __last Another iterator.
3973 * @return True if the elements are sorted, false otherwise.
3975 template<typename _ForwardIterator>
3977 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3978 { return std::is_sorted_until(__first, __last) == __last; }
3981 * @brief Determines whether the elements of a sequence are sorted
3982 * according to a comparison functor.
3983 * @ingroup sorting_algorithms
3984 * @param __first An iterator.
3985 * @param __last Another iterator.
3986 * @param __comp A comparison functor.
3987 * @return True if the elements are sorted, false otherwise.
3989 template<typename _ForwardIterator, typename _Compare>
3991 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3993 { return std::is_sorted_until(__first, __last, __comp) == __last; }
3996 * @brief Determines the end of a sorted sequence.
3997 * @ingroup sorting_algorithms
3998 * @param __first An iterator.
3999 * @param __last Another iterator.
4000 * @return An iterator pointing to the last iterator i in [__first, __last)
4001 * for which the range [__first, i) is sorted.
4003 template<typename _ForwardIterator>
4005 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
4007 // concept requirements
4008 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4009 __glibcxx_function_requires(_LessThanComparableConcept<
4010 typename iterator_traits<_ForwardIterator>::value_type>)
4011 __glibcxx_requires_valid_range(__first, __last);
4013 if (__first == __last)
4016 _ForwardIterator __next = __first;
4017 for (++__next; __next != __last; __first = __next, ++__next)
4018 if (*__next < *__first)
4024 * @brief Determines the end of a sorted sequence using comparison functor.
4025 * @ingroup sorting_algorithms
4026 * @param __first An iterator.
4027 * @param __last Another iterator.
4028 * @param __comp A comparison functor.
4029 * @return An iterator pointing to the last iterator i in [__first, __last)
4030 * for which the range [__first, i) is sorted.
4032 template<typename _ForwardIterator, typename _Compare>
4034 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4037 // concept requirements
4038 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4039 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4040 typename iterator_traits<_ForwardIterator>::value_type,
4041 typename iterator_traits<_ForwardIterator>::value_type>)
4042 __glibcxx_requires_valid_range(__first, __last);
4044 if (__first == __last)
4047 _ForwardIterator __next = __first;
4048 for (++__next; __next != __last; __first = __next, ++__next)
4049 if (__comp(*__next, *__first))
4055 * @brief Determines min and max at once as an ordered pair.
4056 * @ingroup sorting_algorithms
4057 * @param __a A thing of arbitrary type.
4058 * @param __b Another thing of arbitrary type.
4059 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4062 template<typename _Tp>
4063 inline pair<const _Tp&, const _Tp&>
4064 minmax(const _Tp& __a, const _Tp& __b)
4066 // concept requirements
4067 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4069 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4070 : pair<const _Tp&, const _Tp&>(__a, __b);
4074 * @brief Determines min and max at once as an ordered pair.
4075 * @ingroup sorting_algorithms
4076 * @param __a A thing of arbitrary type.
4077 * @param __b Another thing of arbitrary type.
4078 * @param __comp A @link comparison_functors comparison functor @endlink.
4079 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4082 template<typename _Tp, typename _Compare>
4083 inline pair<const _Tp&, const _Tp&>
4084 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
4086 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
4087 : pair<const _Tp&, const _Tp&>(__a, __b);
4091 * @brief Return a pair of iterators pointing to the minimum and maximum
4092 * elements in a range.
4093 * @ingroup sorting_algorithms
4094 * @param __first Start of range.
4095 * @param __last End of range.
4096 * @return make_pair(m, M), where m is the first iterator i in
4097 * [__first, __last) such that no other element in the range is
4098 * smaller, and where M is the last iterator i in [__first, __last)
4099 * such that no other element in the range is larger.
4101 template<typename _ForwardIterator>
4102 pair<_ForwardIterator, _ForwardIterator>
4103 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4105 // concept requirements
4106 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4107 __glibcxx_function_requires(_LessThanComparableConcept<
4108 typename iterator_traits<_ForwardIterator>::value_type>)
4109 __glibcxx_requires_valid_range(__first, __last);
4111 _ForwardIterator __next = __first;
4112 if (__first == __last
4113 || ++__next == __last)
4114 return std::make_pair(__first, __first);
4116 _ForwardIterator __min, __max;
4117 if (*__next < *__first)
4131 while (__first != __last)
4134 if (++__next == __last)
4136 if (*__first < *__min)
4138 else if (!(*__first < *__max))
4143 if (*__next < *__first)
4145 if (*__next < *__min)
4147 if (!(*__first < *__max))
4152 if (*__first < *__min)
4154 if (!(*__next < *__max))
4162 return std::make_pair(__min, __max);
4166 * @brief Return a pair of iterators pointing to the minimum and maximum
4167 * elements in a range.
4168 * @ingroup sorting_algorithms
4169 * @param __first Start of range.
4170 * @param __last End of range.
4171 * @param __comp Comparison functor.
4172 * @return make_pair(m, M), where m is the first iterator i in
4173 * [__first, __last) such that no other element in the range is
4174 * smaller, and where M is the last iterator i in [__first, __last)
4175 * such that no other element in the range is larger.
4177 template<typename _ForwardIterator, typename _Compare>
4178 pair<_ForwardIterator, _ForwardIterator>
4179 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4182 // concept requirements
4183 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4184 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4185 typename iterator_traits<_ForwardIterator>::value_type,
4186 typename iterator_traits<_ForwardIterator>::value_type>)
4187 __glibcxx_requires_valid_range(__first, __last);
4189 _ForwardIterator __next = __first;
4190 if (__first == __last
4191 || ++__next == __last)
4192 return std::make_pair(__first, __first);
4194 _ForwardIterator __min, __max;
4195 if (__comp(*__next, *__first))
4209 while (__first != __last)
4212 if (++__next == __last)
4214 if (__comp(*__first, *__min))
4216 else if (!__comp(*__first, *__max))
4221 if (__comp(*__next, *__first))
4223 if (__comp(*__next, *__min))
4225 if (!__comp(*__first, *__max))
4230 if (__comp(*__first, *__min))
4232 if (!__comp(*__next, *__max))
4240 return std::make_pair(__min, __max);
4244 template<typename _Tp>
4246 min(initializer_list<_Tp> __l)
4247 { return *std::min_element(__l.begin(), __l.end()); }
4249 template<typename _Tp, typename _Compare>
4251 min(initializer_list<_Tp> __l, _Compare __comp)
4252 { return *std::min_element(__l.begin(), __l.end(), __comp); }
4254 template<typename _Tp>
4256 max(initializer_list<_Tp> __l)
4257 { return *std::max_element(__l.begin(), __l.end()); }
4259 template<typename _Tp, typename _Compare>
4261 max(initializer_list<_Tp> __l, _Compare __comp)
4262 { return *std::max_element(__l.begin(), __l.end(), __comp); }
4264 template<typename _Tp>
4265 inline pair<_Tp, _Tp>
4266 minmax(initializer_list<_Tp> __l)
4268 pair<const _Tp*, const _Tp*> __p =
4269 std::minmax_element(__l.begin(), __l.end());
4270 return std::make_pair(*__p.first, *__p.second);
4273 template<typename _Tp, typename _Compare>
4274 inline pair<_Tp, _Tp>
4275 minmax(initializer_list<_Tp> __l, _Compare __comp)
4277 pair<const _Tp*, const _Tp*> __p =
4278 std::minmax_element(__l.begin(), __l.end(), __comp);
4279 return std::make_pair(*__p.first, *__p.second);
4283 * @brief Checks whether a permutaion of the second sequence is equal
4284 * to the first sequence.
4285 * @ingroup non_mutating_algorithms
4286 * @param __first1 Start of first range.
4287 * @param __last1 End of first range.
4288 * @param __first2 Start of second range.
4289 * @return true if there exists a permutation of the elements in the range
4290 * [__first2, __first2 + (__last1 - __first1)), beginning with
4291 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
4292 * returns true; otherwise, returns false.
4294 template<typename _ForwardIterator1, typename _ForwardIterator2>
4296 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4297 _ForwardIterator2 __first2)
4299 // Efficiently compare identical prefixes: O(N) if sequences
4300 // have the same elements in the same order.
4301 for (; __first1 != __last1; ++__first1, ++__first2)
4302 if (!(*__first1 == *__first2))
4305 if (__first1 == __last1)
4308 // Establish __last2 assuming equal ranges by iterating over the
4309 // rest of the list.
4310 _ForwardIterator2 __last2 = __first2;
4311 std::advance(__last2, std::distance(__first1, __last1));
4312 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4314 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4315 continue; // We've seen this one before.
4317 auto __matches = std::count(__first2, __last2, *__scan);
4319 || std::count(__scan, __last1, *__scan) != __matches)
4326 * @brief Checks whether a permutation of the second sequence is equal
4327 * to the first sequence.
4328 * @ingroup non_mutating_algorithms
4329 * @param __first1 Start of first range.
4330 * @param __last1 End of first range.
4331 * @param __first2 Start of second range.
4332 * @param __pred A binary predicate.
4333 * @return true if there exists a permutation of the elements in
4334 * the range [__first2, __first2 + (__last1 - __first1)),
4335 * beginning with ForwardIterator2 begin, such that
4336 * equal(__first1, __last1, __begin, __pred) returns true;
4337 * otherwise, returns false.
4339 template<typename _ForwardIterator1, typename _ForwardIterator2,
4340 typename _BinaryPredicate>
4342 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4343 _ForwardIterator2 __first2, _BinaryPredicate __pred)
4345 // Efficiently compare identical prefixes: O(N) if sequences
4346 // have the same elements in the same order.
4347 for (; __first1 != __last1; ++__first1, ++__first2)
4348 if (!bool(__pred(*__first1, *__first2)))
4351 if (__first1 == __last1)
4354 // Establish __last2 assuming equal ranges by iterating over the
4355 // rest of the list.
4356 _ForwardIterator2 __last2 = __first2;
4357 std::advance(__last2, std::distance(__first1, __last1));
4358 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4360 using std::placeholders::_1;
4362 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4363 std::bind(__pred, _1, *__scan)))
4364 continue; // We've seen this one before.
4366 auto __matches = std::count_if(__first2, __last2,
4367 std::bind(__pred, _1, *__scan));
4369 || std::count_if(__scan, __last1,
4370 std::bind(__pred, _1, *__scan)) != __matches)
4376 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4378 * @brief Shuffle the elements of a sequence using a uniform random
4380 * @ingroup mutating_algorithms
4381 * @param __first A forward iterator.
4382 * @param __last A forward iterator.
4383 * @param __g A UniformRandomNumberGenerator (26.5.1.3).
4386 * Reorders the elements in the range @p [__first,__last) using @p __g to
4387 * provide random numbers.
4389 template<typename _RandomAccessIterator,
4390 typename _UniformRandomNumberGenerator>
4392 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4393 _UniformRandomNumberGenerator&& __g)
4395 // concept requirements
4396 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4397 _RandomAccessIterator>)
4398 __glibcxx_requires_valid_range(__first, __last);
4400 if (__first == __last)
4403 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4406 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4407 typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
4408 typedef typename __distr_type::param_type __p_type;
4411 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4412 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4416 #endif // __GXX_EXPERIMENTAL_CXX0X__
4418 _GLIBCXX_END_NAMESPACE_VERSION
4420 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4423 * @brief Apply a function to every element of a sequence.
4424 * @ingroup non_mutating_algorithms
4425 * @param __first An input iterator.
4426 * @param __last An input iterator.
4427 * @param __f A unary function object.
4428 * @return @p __f (std::move(@p __f) in C++0x).
4430 * Applies the function object @p __f to each element in the range
4431 * @p [first,last). @p __f must not modify the order of the sequence.
4432 * If @p __f has a return value it is ignored.
4434 template<typename _InputIterator, typename _Function>
4436 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4438 // concept requirements
4439 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4440 __glibcxx_requires_valid_range(__first, __last);
4441 for (; __first != __last; ++__first)
4443 return _GLIBCXX_MOVE(__f);
4447 * @brief Find the first occurrence of a value in a sequence.
4448 * @ingroup non_mutating_algorithms
4449 * @param __first An input iterator.
4450 * @param __last An input iterator.
4451 * @param __val The value to find.
4452 * @return The first iterator @c i in the range @p [__first,__last)
4453 * such that @c *i == @p __val, or @p __last if no such iterator exists.
4455 template<typename _InputIterator, typename _Tp>
4456 inline _InputIterator
4457 find(_InputIterator __first, _InputIterator __last,
4460 // concept requirements
4461 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4462 __glibcxx_function_requires(_EqualOpConcept<
4463 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4464 __glibcxx_requires_valid_range(__first, __last);
4465 return std::__find(__first, __last, __val,
4466 std::__iterator_category(__first));
4470 * @brief Find the first element in a sequence for which a
4471 * predicate is true.
4472 * @ingroup non_mutating_algorithms
4473 * @param __first An input iterator.
4474 * @param __last An input iterator.
4475 * @param __pred A predicate.
4476 * @return The first iterator @c i in the range @p [__first,__last)
4477 * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
4479 template<typename _InputIterator, typename _Predicate>
4480 inline _InputIterator
4481 find_if(_InputIterator __first, _InputIterator __last,
4484 // concept requirements
4485 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4486 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4487 typename iterator_traits<_InputIterator>::value_type>)
4488 __glibcxx_requires_valid_range(__first, __last);
4489 return std::__find_if(__first, __last, __pred,
4490 std::__iterator_category(__first));
4494 * @brief Find element from a set in a sequence.
4495 * @ingroup non_mutating_algorithms
4496 * @param __first1 Start of range to search.
4497 * @param __last1 End of range to search.
4498 * @param __first2 Start of match candidates.
4499 * @param __last2 End of match candidates.
4500 * @return The first iterator @c i in the range
4501 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
4502 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
4504 * Searches the range @p [__first1,__last1) for an element that is
4505 * equal to some element in the range [__first2,__last2). If
4506 * found, returns an iterator in the range [__first1,__last1),
4507 * otherwise returns @p __last1.
4509 template<typename _InputIterator, typename _ForwardIterator>
4511 find_first_of(_InputIterator __first1, _InputIterator __last1,
4512 _ForwardIterator __first2, _ForwardIterator __last2)
4514 // concept requirements
4515 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4516 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4517 __glibcxx_function_requires(_EqualOpConcept<
4518 typename iterator_traits<_InputIterator>::value_type,
4519 typename iterator_traits<_ForwardIterator>::value_type>)
4520 __glibcxx_requires_valid_range(__first1, __last1);
4521 __glibcxx_requires_valid_range(__first2, __last2);
4523 for (; __first1 != __last1; ++__first1)
4524 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4525 if (*__first1 == *__iter)
4531 * @brief Find element from a set in a sequence using a predicate.
4532 * @ingroup non_mutating_algorithms
4533 * @param __first1 Start of range to search.
4534 * @param __last1 End of range to search.
4535 * @param __first2 Start of match candidates.
4536 * @param __last2 End of match candidates.
4537 * @param __comp Predicate to use.
4538 * @return The first iterator @c i in the range
4539 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
4540 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
4541 * such iterator exists.
4544 * Searches the range @p [__first1,__last1) for an element that is
4545 * equal to some element in the range [__first2,__last2). If
4546 * found, returns an iterator in the range [__first1,__last1),
4547 * otherwise returns @p __last1.
4549 template<typename _InputIterator, typename _ForwardIterator,
4550 typename _BinaryPredicate>
4552 find_first_of(_InputIterator __first1, _InputIterator __last1,
4553 _ForwardIterator __first2, _ForwardIterator __last2,
4554 _BinaryPredicate __comp)
4556 // concept requirements
4557 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4558 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4559 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4560 typename iterator_traits<_InputIterator>::value_type,
4561 typename iterator_traits<_ForwardIterator>::value_type>)
4562 __glibcxx_requires_valid_range(__first1, __last1);
4563 __glibcxx_requires_valid_range(__first2, __last2);
4565 for (; __first1 != __last1; ++__first1)
4566 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4567 if (__comp(*__first1, *__iter))
4573 * @brief Find two adjacent values in a sequence that are equal.
4574 * @ingroup non_mutating_algorithms
4575 * @param __first A forward iterator.
4576 * @param __last A forward iterator.
4577 * @return The first iterator @c i such that @c i and @c i+1 are both
4578 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4579 * or @p __last if no such iterator exists.
4581 template<typename _ForwardIterator>
4583 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4585 // concept requirements
4586 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4587 __glibcxx_function_requires(_EqualityComparableConcept<
4588 typename iterator_traits<_ForwardIterator>::value_type>)
4589 __glibcxx_requires_valid_range(__first, __last);
4590 if (__first == __last)
4592 _ForwardIterator __next = __first;
4593 while(++__next != __last)
4595 if (*__first == *__next)
4603 * @brief Find two adjacent values in a sequence using a predicate.
4604 * @ingroup non_mutating_algorithms
4605 * @param __first A forward iterator.
4606 * @param __last A forward iterator.
4607 * @param __binary_pred A binary predicate.
4608 * @return The first iterator @c i such that @c i and @c i+1 are both
4609 * valid iterators in @p [__first,__last) and such that
4610 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4613 template<typename _ForwardIterator, typename _BinaryPredicate>
4615 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4616 _BinaryPredicate __binary_pred)
4618 // concept requirements
4619 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4620 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4621 typename iterator_traits<_ForwardIterator>::value_type,
4622 typename iterator_traits<_ForwardIterator>::value_type>)
4623 __glibcxx_requires_valid_range(__first, __last);
4624 if (__first == __last)
4626 _ForwardIterator __next = __first;
4627 while(++__next != __last)
4629 if (__binary_pred(*__first, *__next))
4637 * @brief Count the number of copies of a value in a sequence.
4638 * @ingroup non_mutating_algorithms
4639 * @param __first An input iterator.
4640 * @param __last An input iterator.
4641 * @param __value The value to be counted.
4642 * @return The number of iterators @c i in the range @p [__first,__last)
4643 * for which @c *i == @p __value
4645 template<typename _InputIterator, typename _Tp>
4646 typename iterator_traits<_InputIterator>::difference_type
4647 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4649 // concept requirements
4650 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4651 __glibcxx_function_requires(_EqualOpConcept<
4652 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4653 __glibcxx_requires_valid_range(__first, __last);
4654 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4655 for (; __first != __last; ++__first)
4656 if (*__first == __value)
4662 * @brief Count the elements of a sequence for which a predicate is true.
4663 * @ingroup non_mutating_algorithms
4664 * @param __first An input iterator.
4665 * @param __last An input iterator.
4666 * @param __pred A predicate.
4667 * @return The number of iterators @c i in the range @p [__first,__last)
4668 * for which @p __pred(*i) is true.
4670 template<typename _InputIterator, typename _Predicate>
4671 typename iterator_traits<_InputIterator>::difference_type
4672 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4674 // concept requirements
4675 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4676 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4677 typename iterator_traits<_InputIterator>::value_type>)
4678 __glibcxx_requires_valid_range(__first, __last);
4679 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4680 for (; __first != __last; ++__first)
4681 if (__pred(*__first))
4687 * @brief Search a sequence for a matching sub-sequence.
4688 * @ingroup non_mutating_algorithms
4689 * @param __first1 A forward iterator.
4690 * @param __last1 A forward iterator.
4691 * @param __first2 A forward iterator.
4692 * @param __last2 A forward iterator.
4693 * @return The first iterator @c i in the range @p
4694 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4695 * *(__first2+N) for each @c N in the range @p
4696 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4698 * Searches the range @p [__first1,__last1) for a sub-sequence that
4699 * compares equal value-by-value with the sequence given by @p
4700 * [__first2,__last2) and returns an iterator to the first element
4701 * of the sub-sequence, or @p __last1 if the sub-sequence is not
4704 * Because the sub-sequence must lie completely within the range @p
4705 * [__first1,__last1) it must start at a position less than @p
4706 * __last1-(__last2-__first2) where @p __last2-__first2 is the
4707 * length of the sub-sequence.
4709 * This means that the returned iterator @c i will be in the range
4710 * @p [__first1,__last1-(__last2-__first2))
4712 template<typename _ForwardIterator1, typename _ForwardIterator2>
4714 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4715 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4717 // concept requirements
4718 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4719 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4720 __glibcxx_function_requires(_EqualOpConcept<
4721 typename iterator_traits<_ForwardIterator1>::value_type,
4722 typename iterator_traits<_ForwardIterator2>::value_type>)
4723 __glibcxx_requires_valid_range(__first1, __last1);
4724 __glibcxx_requires_valid_range(__first2, __last2);
4726 // Test for empty ranges
4727 if (__first1 == __last1 || __first2 == __last2)
4730 // Test for a pattern of length 1.
4731 _ForwardIterator2 __p1(__first2);
4732 if (++__p1 == __last2)
4733 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4736 _ForwardIterator2 __p;
4737 _ForwardIterator1 __current = __first1;
4741 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4742 if (__first1 == __last1)
4746 __current = __first1;
4747 if (++__current == __last1)
4750 while (*__current == *__p)
4752 if (++__p == __last2)
4754 if (++__current == __last1)
4763 * @brief Search a sequence for a matching sub-sequence using a predicate.
4764 * @ingroup non_mutating_algorithms
4765 * @param __first1 A forward iterator.
4766 * @param __last1 A forward iterator.
4767 * @param __first2 A forward iterator.
4768 * @param __last2 A forward iterator.
4769 * @param __predicate A binary predicate.
4770 * @return The first iterator @c i in the range
4771 * @p [__first1,__last1-(__last2-__first2)) such that
4772 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4773 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4775 * Searches the range @p [__first1,__last1) for a sub-sequence that
4776 * compares equal value-by-value with the sequence given by @p
4777 * [__first2,__last2), using @p __predicate to determine equality,
4778 * and returns an iterator to the first element of the
4779 * sub-sequence, or @p __last1 if no such iterator exists.
4781 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4783 template<typename _ForwardIterator1, typename _ForwardIterator2,
4784 typename _BinaryPredicate>
4786 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4787 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4788 _BinaryPredicate __predicate)
4790 // concept requirements
4791 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4792 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4793 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4794 typename iterator_traits<_ForwardIterator1>::value_type,
4795 typename iterator_traits<_ForwardIterator2>::value_type>)
4796 __glibcxx_requires_valid_range(__first1, __last1);
4797 __glibcxx_requires_valid_range(__first2, __last2);
4799 // Test for empty ranges
4800 if (__first1 == __last1 || __first2 == __last2)
4803 // Test for a pattern of length 1.
4804 _ForwardIterator2 __p1(__first2);
4805 if (++__p1 == __last2)
4807 while (__first1 != __last1
4808 && !bool(__predicate(*__first1, *__first2)))
4814 _ForwardIterator2 __p;
4815 _ForwardIterator1 __current = __first1;
4819 while (__first1 != __last1
4820 && !bool(__predicate(*__first1, *__first2)))
4822 if (__first1 == __last1)
4826 __current = __first1;
4827 if (++__current == __last1)
4830 while (__predicate(*__current, *__p))
4832 if (++__p == __last2)
4834 if (++__current == __last1)
4844 * @brief Search a sequence for a number of consecutive values.
4845 * @ingroup non_mutating_algorithms
4846 * @param __first A forward iterator.
4847 * @param __last A forward iterator.
4848 * @param __count The number of consecutive values.
4849 * @param __val The value to find.
4850 * @return The first iterator @c i in the range @p
4851 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4852 * each @c N in the range @p [0,__count), or @p __last if no such
4855 * Searches the range @p [__first,__last) for @p count consecutive elements
4856 * equal to @p __val.
4858 template<typename _ForwardIterator, typename _Integer, typename _Tp>
4860 search_n(_ForwardIterator __first, _ForwardIterator __last,
4861 _Integer __count, const _Tp& __val)
4863 // concept requirements
4864 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4865 __glibcxx_function_requires(_EqualOpConcept<
4866 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4867 __glibcxx_requires_valid_range(__first, __last);
4872 return _GLIBCXX_STD_A::find(__first, __last, __val);
4873 return std::__search_n(__first, __last, __count, __val,
4874 std::__iterator_category(__first));
4879 * @brief Search a sequence for a number of consecutive values using a
4881 * @ingroup non_mutating_algorithms
4882 * @param __first A forward iterator.
4883 * @param __last A forward iterator.
4884 * @param __count The number of consecutive values.
4885 * @param __val The value to find.
4886 * @param __binary_pred A binary predicate.
4887 * @return The first iterator @c i in the range @p
4888 * [__first,__last-__count) such that @p
4889 * __binary_pred(*(i+N),__val) is true for each @c N in the range
4890 * @p [0,__count), or @p __last if no such iterator exists.
4892 * Searches the range @p [__first,__last) for @p __count
4893 * consecutive elements for which the predicate returns true.
4895 template<typename _ForwardIterator, typename _Integer, typename _Tp,
4896 typename _BinaryPredicate>
4898 search_n(_ForwardIterator __first, _ForwardIterator __last,
4899 _Integer __count, const _Tp& __val,
4900 _BinaryPredicate __binary_pred)
4902 // concept requirements
4903 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4904 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4905 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4906 __glibcxx_requires_valid_range(__first, __last);
4912 while (__first != __last && !bool(__binary_pred(*__first, __val)))
4916 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4917 std::__iterator_category(__first));
4922 * @brief Perform an operation on a sequence.
4923 * @ingroup mutating_algorithms
4924 * @param __first An input iterator.
4925 * @param __last An input iterator.
4926 * @param __result An output iterator.
4927 * @param __unary_op A unary operator.
4928 * @return An output iterator equal to @p __result+(__last-__first).
4930 * Applies the operator to each element in the input range and assigns
4931 * the results to successive elements of the output sequence.
4932 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4933 * range @p [0,__last-__first).
4935 * @p unary_op must not alter its argument.
4937 template<typename _InputIterator, typename _OutputIterator,
4938 typename _UnaryOperation>
4940 transform(_InputIterator __first, _InputIterator __last,
4941 _OutputIterator __result, _UnaryOperation __unary_op)
4943 // concept requirements
4944 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4945 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4946 // "the type returned by a _UnaryOperation"
4947 __typeof__(__unary_op(*__first))>)
4948 __glibcxx_requires_valid_range(__first, __last);
4950 for (; __first != __last; ++__first, ++__result)
4951 *__result = __unary_op(*__first);
4956 * @brief Perform an operation on corresponding elements of two sequences.
4957 * @ingroup mutating_algorithms
4958 * @param __first1 An input iterator.
4959 * @param __last1 An input iterator.
4960 * @param __first2 An input iterator.
4961 * @param __result An output iterator.
4962 * @param __binary_op A binary operator.
4963 * @return An output iterator equal to @p result+(last-first).
4965 * Applies the operator to the corresponding elements in the two
4966 * input ranges and assigns the results to successive elements of the
4969 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4970 * @c N in the range @p [0,__last1-__first1).
4972 * @p binary_op must not alter either of its arguments.
4974 template<typename _InputIterator1, typename _InputIterator2,
4975 typename _OutputIterator, typename _BinaryOperation>
4977 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4978 _InputIterator2 __first2, _OutputIterator __result,
4979 _BinaryOperation __binary_op)
4981 // concept requirements
4982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4984 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4985 // "the type returned by a _BinaryOperation"
4986 __typeof__(__binary_op(*__first1,*__first2))>)
4987 __glibcxx_requires_valid_range(__first1, __last1);
4989 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4990 *__result = __binary_op(*__first1, *__first2);
4995 * @brief Replace each occurrence of one value in a sequence with another
4997 * @ingroup mutating_algorithms
4998 * @param __first A forward iterator.
4999 * @param __last A forward iterator.
5000 * @param __old_value The value to be replaced.
5001 * @param __new_value The replacement value.
5002 * @return replace() returns no value.
5004 * For each iterator @c i in the range @p [__first,__last) if @c *i ==
5005 * @p __old_value then the assignment @c *i = @p __new_value is performed.
5007 template<typename _ForwardIterator, typename _Tp>
5009 replace(_ForwardIterator __first, _ForwardIterator __last,
5010 const _Tp& __old_value, const _Tp& __new_value)
5012 // concept requirements
5013 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5015 __glibcxx_function_requires(_EqualOpConcept<
5016 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
5017 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5018 typename iterator_traits<_ForwardIterator>::value_type>)
5019 __glibcxx_requires_valid_range(__first, __last);
5021 for (; __first != __last; ++__first)
5022 if (*__first == __old_value)
5023 *__first = __new_value;
5027 * @brief Replace each value in a sequence for which a predicate returns
5028 * true with another value.
5029 * @ingroup mutating_algorithms
5030 * @param __first A forward iterator.
5031 * @param __last A forward iterator.
5032 * @param __pred A predicate.
5033 * @param __new_value The replacement value.
5034 * @return replace_if() returns no value.
5036 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
5037 * is true then the assignment @c *i = @p __new_value is performed.
5039 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
5041 replace_if(_ForwardIterator __first, _ForwardIterator __last,
5042 _Predicate __pred, const _Tp& __new_value)
5044 // concept requirements
5045 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5047 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5048 typename iterator_traits<_ForwardIterator>::value_type>)
5049 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5050 typename iterator_traits<_ForwardIterator>::value_type>)
5051 __glibcxx_requires_valid_range(__first, __last);
5053 for (; __first != __last; ++__first)
5054 if (__pred(*__first))
5055 *__first = __new_value;
5059 * @brief Assign the result of a function object to each value in a
5061 * @ingroup mutating_algorithms
5062 * @param __first A forward iterator.
5063 * @param __last A forward iterator.
5064 * @param __gen A function object taking no arguments and returning
5065 * std::iterator_traits<_ForwardIterator>::value_type
5066 * @return generate() returns no value.
5068 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5069 * @p [__first,__last).
5071 template<typename _ForwardIterator, typename _Generator>
5073 generate(_ForwardIterator __first, _ForwardIterator __last,
5076 // concept requirements
5077 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5078 __glibcxx_function_requires(_GeneratorConcept<_Generator,
5079 typename iterator_traits<_ForwardIterator>::value_type>)
5080 __glibcxx_requires_valid_range(__first, __last);
5082 for (; __first != __last; ++__first)
5087 * @brief Assign the result of a function object to each value in a
5089 * @ingroup mutating_algorithms
5090 * @param __first A forward iterator.
5091 * @param __n The length of the sequence.
5092 * @param __gen A function object taking no arguments and returning
5093 * std::iterator_traits<_ForwardIterator>::value_type
5094 * @return The end of the sequence, @p __first+__n
5096 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5097 * @p [__first,__first+__n).
5099 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5100 * DR 865. More algorithms that throw away information
5102 template<typename _OutputIterator, typename _Size, typename _Generator>
5104 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5106 // concept requirements
5107 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5108 // "the type returned by a _Generator"
5109 __typeof__(__gen())>)
5111 for (__decltype(__n + 0) __niter = __n;
5112 __niter > 0; --__niter, ++__first)
5119 * @brief Copy a sequence, removing consecutive duplicate values.
5120 * @ingroup mutating_algorithms
5121 * @param __first An input iterator.
5122 * @param __last An input iterator.
5123 * @param __result An output iterator.
5124 * @return An iterator designating the end of the resulting sequence.
5126 * Copies each element in the range @p [__first,__last) to the range
5127 * beginning at @p __result, except that only the first element is copied
5128 * from groups of consecutive elements that compare equal.
5129 * unique_copy() is stable, so the relative order of elements that are
5130 * copied is unchanged.
5132 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5133 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5135 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5136 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
5139 template<typename _InputIterator, typename _OutputIterator>
5140 inline _OutputIterator
5141 unique_copy(_InputIterator __first, _InputIterator __last,
5142 _OutputIterator __result)
5144 // concept requirements
5145 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5146 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5147 typename iterator_traits<_InputIterator>::value_type>)
5148 __glibcxx_function_requires(_EqualityComparableConcept<
5149 typename iterator_traits<_InputIterator>::value_type>)
5150 __glibcxx_requires_valid_range(__first, __last);
5152 if (__first == __last)
5154 return std::__unique_copy(__first, __last, __result,
5155 std::__iterator_category(__first),
5156 std::__iterator_category(__result));
5160 * @brief Copy a sequence, removing consecutive values using a predicate.
5161 * @ingroup mutating_algorithms
5162 * @param __first An input iterator.
5163 * @param __last An input iterator.
5164 * @param __result An output iterator.
5165 * @param __binary_pred A binary predicate.
5166 * @return An iterator designating the end of the resulting sequence.
5168 * Copies each element in the range @p [__first,__last) to the range
5169 * beginning at @p __result, except that only the first element is copied
5170 * from groups of consecutive elements for which @p __binary_pred returns
5172 * unique_copy() is stable, so the relative order of elements that are
5173 * copied is unchanged.
5175 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5176 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5178 template<typename _InputIterator, typename _OutputIterator,
5179 typename _BinaryPredicate>
5180 inline _OutputIterator
5181 unique_copy(_InputIterator __first, _InputIterator __last,
5182 _OutputIterator __result,
5183 _BinaryPredicate __binary_pred)
5185 // concept requirements -- predicates checked later
5186 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5187 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5188 typename iterator_traits<_InputIterator>::value_type>)
5189 __glibcxx_requires_valid_range(__first, __last);
5191 if (__first == __last)
5193 return std::__unique_copy(__first, __last, __result, __binary_pred,
5194 std::__iterator_category(__first),
5195 std::__iterator_category(__result));
5200 * @brief Randomly shuffle the elements of a sequence.
5201 * @ingroup mutating_algorithms
5202 * @param __first A forward iterator.
5203 * @param __last A forward iterator.
5206 * Reorder the elements in the range @p [__first,__last) using a random
5207 * distribution, so that every possible ordering of the sequence is
5210 template<typename _RandomAccessIterator>
5212 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5214 // concept requirements
5215 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5216 _RandomAccessIterator>)
5217 __glibcxx_requires_valid_range(__first, __last);
5219 if (__first != __last)
5220 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5221 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5225 * @brief Shuffle the elements of a sequence using a random number
5227 * @ingroup mutating_algorithms
5228 * @param __first A forward iterator.
5229 * @param __last A forward iterator.
5230 * @param __rand The RNG functor or function.
5233 * Reorders the elements in the range @p [__first,__last) using @p __rand to
5234 * provide a random distribution. Calling @p __rand(N) for a positive
5235 * integer @p N should return a randomly chosen integer from the
5238 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
5240 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5241 #ifdef __GXX_EXPERIMENTAL_CXX0X__
5242 _RandomNumberGenerator&& __rand)
5244 _RandomNumberGenerator& __rand)
5247 // concept requirements
5248 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5249 _RandomAccessIterator>)
5250 __glibcxx_requires_valid_range(__first, __last);
5252 if (__first == __last)
5254 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5255 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
5260 * @brief Move elements for which a predicate is true to the beginning
5262 * @ingroup mutating_algorithms
5263 * @param __first A forward iterator.
5264 * @param __last A forward iterator.
5265 * @param __pred A predicate functor.
5266 * @return An iterator @p middle such that @p __pred(i) is true for each
5267 * iterator @p i in the range @p [__first,middle) and false for each @p i
5268 * in the range @p [middle,__last).
5270 * @p __pred must not modify its operand. @p partition() does not preserve
5271 * the relative ordering of elements in each group, use
5272 * @p stable_partition() if this is needed.
5274 template<typename _ForwardIterator, typename _Predicate>
5275 inline _ForwardIterator
5276 partition(_ForwardIterator __first, _ForwardIterator __last,
5279 // concept requirements
5280 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5282 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5283 typename iterator_traits<_ForwardIterator>::value_type>)
5284 __glibcxx_requires_valid_range(__first, __last);
5286 return std::__partition(__first, __last, __pred,
5287 std::__iterator_category(__first));
5293 * @brief Sort the smallest elements of a sequence.
5294 * @ingroup sorting_algorithms
5295 * @param __first An iterator.
5296 * @param __middle Another iterator.
5297 * @param __last Another iterator.
5300 * Sorts the smallest @p (__middle-__first) elements in the range
5301 * @p [first,last) and moves them to the range @p [__first,__middle). The
5302 * order of the remaining elements in the range @p [__middle,__last) is
5304 * After the sort if @e i and @e j are iterators in the range
5305 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5306 * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
5308 template<typename _RandomAccessIterator>
5310 partial_sort(_RandomAccessIterator __first,
5311 _RandomAccessIterator __middle,
5312 _RandomAccessIterator __last)
5314 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5317 // concept requirements
5318 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5319 _RandomAccessIterator>)
5320 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5321 __glibcxx_requires_valid_range(__first, __middle);
5322 __glibcxx_requires_valid_range(__middle, __last);
5324 std::__heap_select(__first, __middle, __last);
5325 std::sort_heap(__first, __middle);
5329 * @brief Sort the smallest elements of a sequence using a predicate
5331 * @ingroup sorting_algorithms
5332 * @param __first An iterator.
5333 * @param __middle Another iterator.
5334 * @param __last Another iterator.
5335 * @param __comp A comparison functor.
5338 * Sorts the smallest @p (__middle-__first) elements in the range
5339 * @p [__first,__last) and moves them to the range @p [__first,__middle). The
5340 * order of the remaining elements in the range @p [__middle,__last) is
5342 * After the sort if @e i and @e j are iterators in the range
5343 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5344 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
5347 template<typename _RandomAccessIterator, typename _Compare>
5349 partial_sort(_RandomAccessIterator __first,
5350 _RandomAccessIterator __middle,
5351 _RandomAccessIterator __last,
5354 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5357 // concept requirements
5358 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5359 _RandomAccessIterator>)
5360 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5361 _ValueType, _ValueType>)
5362 __glibcxx_requires_valid_range(__first, __middle);
5363 __glibcxx_requires_valid_range(__middle, __last);
5365 std::__heap_select(__first, __middle, __last, __comp);
5366 std::sort_heap(__first, __middle, __comp);
5370 * @brief Sort a sequence just enough to find a particular position.
5371 * @ingroup sorting_algorithms
5372 * @param __first An iterator.
5373 * @param __nth Another iterator.
5374 * @param __last Another iterator.
5377 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5378 * is the same element that would have been in that position had the
5379 * whole sequence been sorted. The elements either side of @p *__nth are
5380 * not completely sorted, but for any iterator @e i in the range
5381 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5382 * holds that *j < *i is false.
5384 template<typename _RandomAccessIterator>
5386 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5387 _RandomAccessIterator __last)
5389 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5392 // concept requirements
5393 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5394 _RandomAccessIterator>)
5395 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5396 __glibcxx_requires_valid_range(__first, __nth);
5397 __glibcxx_requires_valid_range(__nth, __last);
5399 if (__first == __last || __nth == __last)
5402 std::__introselect(__first, __nth, __last,
5403 std::__lg(__last - __first) * 2);
5407 * @brief Sort a sequence just enough to find a particular position
5408 * using a predicate for comparison.
5409 * @ingroup sorting_algorithms
5410 * @param __first An iterator.
5411 * @param __nth Another iterator.
5412 * @param __last Another iterator.
5413 * @param __comp A comparison functor.
5416 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5417 * is the same element that would have been in that position had the
5418 * whole sequence been sorted. The elements either side of @p *__nth are
5419 * not completely sorted, but for any iterator @e i in the range
5420 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5421 * holds that @p __comp(*j,*i) is false.
5423 template<typename _RandomAccessIterator, typename _Compare>
5425 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5426 _RandomAccessIterator __last, _Compare __comp)
5428 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5431 // concept requirements
5432 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5433 _RandomAccessIterator>)
5434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5435 _ValueType, _ValueType>)
5436 __glibcxx_requires_valid_range(__first, __nth);
5437 __glibcxx_requires_valid_range(__nth, __last);
5439 if (__first == __last || __nth == __last)
5442 std::__introselect(__first, __nth, __last,
5443 std::__lg(__last - __first) * 2, __comp);
5448 * @brief Sort the elements of a sequence.
5449 * @ingroup sorting_algorithms
5450 * @param __first An iterator.
5451 * @param __last Another iterator.
5454 * Sorts the elements in the range @p [__first,__last) in ascending order,
5455 * such that for each iterator @e i in the range @p [__first,__last-1),
5456 * *(i+1)<*i is false.
5458 * The relative ordering of equivalent elements is not preserved, use
5459 * @p stable_sort() if this is needed.
5461 template<typename _RandomAccessIterator>
5463 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5465 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5468 // concept requirements
5469 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5470 _RandomAccessIterator>)
5471 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5472 __glibcxx_requires_valid_range(__first, __last);
5474 if (__first != __last)
5476 std::__introsort_loop(__first, __last,
5477 std::__lg(__last - __first) * 2);
5478 std::__final_insertion_sort(__first, __last);
5483 * @brief Sort the elements of a sequence using a predicate for comparison.
5484 * @ingroup sorting_algorithms
5485 * @param __first An iterator.
5486 * @param __last Another iterator.
5487 * @param __comp A comparison functor.
5490 * Sorts the elements in the range @p [__first,__last) in ascending order,
5491 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
5492 * range @p [__first,__last-1).
5494 * The relative ordering of equivalent elements is not preserved, use
5495 * @p stable_sort() if this is needed.
5497 template<typename _RandomAccessIterator, typename _Compare>
5499 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5502 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5505 // concept requirements
5506 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5507 _RandomAccessIterator>)
5508 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5510 __glibcxx_requires_valid_range(__first, __last);
5512 if (__first != __last)
5514 std::__introsort_loop(__first, __last,
5515 std::__lg(__last - __first) * 2, __comp);
5516 std::__final_insertion_sort(__first, __last, __comp);
5521 * @brief Merges two sorted ranges.
5522 * @ingroup sorting_algorithms
5523 * @param __first1 An iterator.
5524 * @param __first2 Another iterator.
5525 * @param __last1 Another iterator.
5526 * @param __last2 Another iterator.
5527 * @param __result An iterator pointing to the end of the merged range.
5528 * @return An iterator pointing to the first element <em>not less
5531 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5532 * the sorted range @p [__result, __result + (__last1-__first1) +
5533 * (__last2-__first2)). Both input ranges must be sorted, and the
5534 * output range must not overlap with either of the input ranges.
5535 * The sort is @e stable, that is, for equivalent elements in the
5536 * two ranges, elements from the first range will always come
5537 * before elements from the second.
5539 template<typename _InputIterator1, typename _InputIterator2,
5540 typename _OutputIterator>
5542 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5543 _InputIterator2 __first2, _InputIterator2 __last2,
5544 _OutputIterator __result)
5546 typedef typename iterator_traits<_InputIterator1>::value_type
5548 typedef typename iterator_traits<_InputIterator2>::value_type
5551 // concept requirements
5552 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5553 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5554 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5556 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5558 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5559 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5560 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5562 while (__first1 != __last1 && __first2 != __last2)
5564 if (*__first2 < *__first1)
5566 *__result = *__first2;
5571 *__result = *__first1;
5576 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5581 * @brief Merges two sorted ranges.
5582 * @ingroup sorting_algorithms
5583 * @param __first1 An iterator.
5584 * @param __first2 Another iterator.
5585 * @param __last1 Another iterator.
5586 * @param __last2 Another iterator.
5587 * @param __result An iterator pointing to the end of the merged range.
5588 * @param __comp A functor to use for comparisons.
5589 * @return An iterator pointing to the first element "not less
5592 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5593 * the sorted range @p [__result, __result + (__last1-__first1) +
5594 * (__last2-__first2)). Both input ranges must be sorted, and the
5595 * output range must not overlap with either of the input ranges.
5596 * The sort is @e stable, that is, for equivalent elements in the
5597 * two ranges, elements from the first range will always come
5598 * before elements from the second.
5600 * The comparison function should have the same effects on ordering as
5601 * the function used for the initial sort.
5603 template<typename _InputIterator1, typename _InputIterator2,
5604 typename _OutputIterator, typename _Compare>
5606 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5607 _InputIterator2 __first2, _InputIterator2 __last2,
5608 _OutputIterator __result, _Compare __comp)
5610 typedef typename iterator_traits<_InputIterator1>::value_type
5612 typedef typename iterator_traits<_InputIterator2>::value_type
5615 // concept requirements
5616 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5617 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5618 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5620 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5622 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5623 _ValueType2, _ValueType1>)
5624 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5625 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5627 while (__first1 != __last1 && __first2 != __last2)
5629 if (__comp(*__first2, *__first1))
5631 *__result = *__first2;
5636 *__result = *__first1;
5641 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5647 * @brief Sort the elements of a sequence, preserving the relative order
5648 * of equivalent elements.
5649 * @ingroup sorting_algorithms
5650 * @param __first An iterator.
5651 * @param __last Another iterator.
5654 * Sorts the elements in the range @p [__first,__last) in ascending order,
5655 * such that for each iterator @p i in the range @p [__first,__last-1),
5656 * @p *(i+1)<*i is false.
5658 * The relative ordering of equivalent elements is preserved, so any two
5659 * elements @p x and @p y in the range @p [__first,__last) such that
5660 * @p x<y is false and @p y<x is false will have the same relative
5661 * ordering after calling @p stable_sort().
5663 template<typename _RandomAccessIterator>
5665 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5667 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5669 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5672 // concept requirements
5673 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5674 _RandomAccessIterator>)
5675 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5676 __glibcxx_requires_valid_range(__first, __last);
5678 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5680 if (__buf.begin() == 0)
5681 std::__inplace_stable_sort(__first, __last);
5683 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5684 _DistanceType(__buf.size()));
5688 * @brief Sort the elements of a sequence using a predicate for comparison,
5689 * preserving the relative order of equivalent elements.
5690 * @ingroup sorting_algorithms
5691 * @param __first An iterator.
5692 * @param __last Another iterator.
5693 * @param __comp A comparison functor.
5696 * Sorts the elements in the range @p [__first,__last) in ascending order,
5697 * such that for each iterator @p i in the range @p [__first,__last-1),
5698 * @p __comp(*(i+1),*i) is false.
5700 * The relative ordering of equivalent elements is preserved, so any two
5701 * elements @p x and @p y in the range @p [__first,__last) such that
5702 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5703 * relative ordering after calling @p stable_sort().
5705 template<typename _RandomAccessIterator, typename _Compare>
5707 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5710 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5712 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5715 // concept requirements
5716 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5717 _RandomAccessIterator>)
5718 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5721 __glibcxx_requires_valid_range(__first, __last);
5723 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5725 if (__buf.begin() == 0)
5726 std::__inplace_stable_sort(__first, __last, __comp);
5728 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5729 _DistanceType(__buf.size()), __comp);
5734 * @brief Return the union of two sorted ranges.
5735 * @ingroup set_algorithms
5736 * @param __first1 Start of first range.
5737 * @param __last1 End of first range.
5738 * @param __first2 Start of second range.
5739 * @param __last2 End of second range.
5740 * @return End of the output range.
5741 * @ingroup set_algorithms
5743 * This operation iterates over both ranges, copying elements present in
5744 * each range in order to the output range. Iterators increment for each
5745 * range. When the current element of one range is less than the other,
5746 * that element is copied and the iterator advanced. If an element is
5747 * contained in both ranges, the element from the first range is copied and
5748 * both ranges advance. The output range may not overlap either input
5751 template<typename _InputIterator1, typename _InputIterator2,
5752 typename _OutputIterator>
5754 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5755 _InputIterator2 __first2, _InputIterator2 __last2,
5756 _OutputIterator __result)
5758 typedef typename iterator_traits<_InputIterator1>::value_type
5760 typedef typename iterator_traits<_InputIterator2>::value_type
5763 // concept requirements
5764 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5765 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5766 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5768 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5770 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5771 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5772 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5773 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5775 while (__first1 != __last1 && __first2 != __last2)
5777 if (*__first1 < *__first2)
5779 *__result = *__first1;
5782 else if (*__first2 < *__first1)
5784 *__result = *__first2;
5789 *__result = *__first1;
5795 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5800 * @brief Return the union of two sorted ranges using a comparison functor.
5801 * @ingroup set_algorithms
5802 * @param __first1 Start of first range.
5803 * @param __last1 End of first range.
5804 * @param __first2 Start of second range.
5805 * @param __last2 End of second range.
5806 * @param __comp The comparison functor.
5807 * @return End of the output range.
5808 * @ingroup set_algorithms
5810 * This operation iterates over both ranges, copying elements present in
5811 * each range in order to the output range. Iterators increment for each
5812 * range. When the current element of one range is less than the other
5813 * according to @p __comp, that element is copied and the iterator advanced.
5814 * If an equivalent element according to @p __comp is contained in both
5815 * ranges, the element from the first range is copied and both ranges
5816 * advance. The output range may not overlap either input range.
5818 template<typename _InputIterator1, typename _InputIterator2,
5819 typename _OutputIterator, typename _Compare>
5821 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5822 _InputIterator2 __first2, _InputIterator2 __last2,
5823 _OutputIterator __result, _Compare __comp)
5825 typedef typename iterator_traits<_InputIterator1>::value_type
5827 typedef typename iterator_traits<_InputIterator2>::value_type
5830 // concept requirements
5831 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5832 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5833 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5835 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5837 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5838 _ValueType1, _ValueType2>)
5839 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5840 _ValueType2, _ValueType1>)
5841 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5842 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5844 while (__first1 != __last1 && __first2 != __last2)
5846 if (__comp(*__first1, *__first2))
5848 *__result = *__first1;
5851 else if (__comp(*__first2, *__first1))
5853 *__result = *__first2;
5858 *__result = *__first1;
5864 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5869 * @brief Return the intersection of two sorted ranges.
5870 * @ingroup set_algorithms
5871 * @param __first1 Start of first range.
5872 * @param __last1 End of first range.
5873 * @param __first2 Start of second range.
5874 * @param __last2 End of second range.
5875 * @return End of the output range.
5876 * @ingroup set_algorithms
5878 * This operation iterates over both ranges, copying elements present in
5879 * both ranges in order to the output range. Iterators increment for each
5880 * range. When the current element of one range is less than the other,
5881 * that iterator advances. If an element is contained in both ranges, the
5882 * element from the first range is copied and both ranges advance. The
5883 * output range may not overlap either input range.
5885 template<typename _InputIterator1, typename _InputIterator2,
5886 typename _OutputIterator>
5888 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5889 _InputIterator2 __first2, _InputIterator2 __last2,
5890 _OutputIterator __result)
5892 typedef typename iterator_traits<_InputIterator1>::value_type
5894 typedef typename iterator_traits<_InputIterator2>::value_type
5897 // concept requirements
5898 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5899 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5900 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5902 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5903 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5904 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5905 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5907 while (__first1 != __last1 && __first2 != __last2)
5908 if (*__first1 < *__first2)
5910 else if (*__first2 < *__first1)
5914 *__result = *__first1;
5923 * @brief Return the intersection of two sorted ranges using comparison
5925 * @ingroup set_algorithms
5926 * @param __first1 Start of first range.
5927 * @param __last1 End of first range.
5928 * @param __first2 Start of second range.
5929 * @param __last2 End of second range.
5930 * @param __comp The comparison functor.
5931 * @return End of the output range.
5932 * @ingroup set_algorithms
5934 * This operation iterates over both ranges, copying elements present in
5935 * both ranges in order to the output range. Iterators increment for each
5936 * range. When the current element of one range is less than the other
5937 * according to @p __comp, that iterator advances. If an element is
5938 * contained in both ranges according to @p __comp, the element from the
5939 * first range is copied and both ranges advance. The output range may not
5940 * overlap either input range.
5942 template<typename _InputIterator1, typename _InputIterator2,
5943 typename _OutputIterator, typename _Compare>
5945 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5946 _InputIterator2 __first2, _InputIterator2 __last2,
5947 _OutputIterator __result, _Compare __comp)
5949 typedef typename iterator_traits<_InputIterator1>::value_type
5951 typedef typename iterator_traits<_InputIterator2>::value_type
5954 // concept requirements
5955 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5956 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5957 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5959 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5960 _ValueType1, _ValueType2>)
5961 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5962 _ValueType2, _ValueType1>)
5963 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5964 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5966 while (__first1 != __last1 && __first2 != __last2)
5967 if (__comp(*__first1, *__first2))
5969 else if (__comp(*__first2, *__first1))
5973 *__result = *__first1;
5982 * @brief Return the difference of two sorted ranges.
5983 * @ingroup set_algorithms
5984 * @param __first1 Start of first range.
5985 * @param __last1 End of first range.
5986 * @param __first2 Start of second range.
5987 * @param __last2 End of second range.
5988 * @return End of the output range.
5989 * @ingroup set_algorithms
5991 * This operation iterates over both ranges, copying elements present in
5992 * the first range but not the second in order to the output range.
5993 * Iterators increment for each range. When the current element of the
5994 * first range is less than the second, that element is copied and the
5995 * iterator advances. If the current element of the second range is less,
5996 * the iterator advances, but no element is copied. If an element is
5997 * contained in both ranges, no elements are copied and both ranges
5998 * advance. The output range may not overlap either input range.
6000 template<typename _InputIterator1, typename _InputIterator2,
6001 typename _OutputIterator>
6003 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6004 _InputIterator2 __first2, _InputIterator2 __last2,
6005 _OutputIterator __result)
6007 typedef typename iterator_traits<_InputIterator1>::value_type
6009 typedef typename iterator_traits<_InputIterator2>::value_type
6012 // concept requirements
6013 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6014 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6015 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6017 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6018 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6019 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6020 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6022 while (__first1 != __last1 && __first2 != __last2)
6023 if (*__first1 < *__first2)
6025 *__result = *__first1;
6029 else if (*__first2 < *__first1)
6036 return std::copy(__first1, __last1, __result);
6040 * @brief Return the difference of two sorted ranges using comparison
6042 * @ingroup set_algorithms
6043 * @param __first1 Start of first range.
6044 * @param __last1 End of first range.
6045 * @param __first2 Start of second range.
6046 * @param __last2 End of second range.
6047 * @param __comp The comparison functor.
6048 * @return End of the output range.
6049 * @ingroup set_algorithms
6051 * This operation iterates over both ranges, copying elements present in
6052 * the first range but not the second in order to the output range.
6053 * Iterators increment for each range. When the current element of the
6054 * first range is less than the second according to @p __comp, that element
6055 * is copied and the iterator advances. If the current element of the
6056 * second range is less, no element is copied and the iterator advances.
6057 * If an element is contained in both ranges according to @p __comp, no
6058 * elements are copied and both ranges advance. The output range may not
6059 * overlap either input range.
6061 template<typename _InputIterator1, typename _InputIterator2,
6062 typename _OutputIterator, typename _Compare>
6064 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6065 _InputIterator2 __first2, _InputIterator2 __last2,
6066 _OutputIterator __result, _Compare __comp)
6068 typedef typename iterator_traits<_InputIterator1>::value_type
6070 typedef typename iterator_traits<_InputIterator2>::value_type
6073 // concept requirements
6074 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6075 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6076 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6078 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6079 _ValueType1, _ValueType2>)
6080 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6081 _ValueType2, _ValueType1>)
6082 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6083 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6085 while (__first1 != __last1 && __first2 != __last2)
6086 if (__comp(*__first1, *__first2))
6088 *__result = *__first1;
6092 else if (__comp(*__first2, *__first1))
6099 return std::copy(__first1, __last1, __result);
6103 * @brief Return the symmetric difference of two sorted ranges.
6104 * @ingroup set_algorithms
6105 * @param __first1 Start of first range.
6106 * @param __last1 End of first range.
6107 * @param __first2 Start of second range.
6108 * @param __last2 End of second range.
6109 * @return End of the output range.
6110 * @ingroup set_algorithms
6112 * This operation iterates over both ranges, copying elements present in
6113 * one range but not the other in order to the output range. Iterators
6114 * increment for each range. When the current element of one range is less
6115 * than the other, that element is copied and the iterator advances. If an
6116 * element is contained in both ranges, no elements are copied and both
6117 * ranges advance. The output range may not overlap either input range.
6119 template<typename _InputIterator1, typename _InputIterator2,
6120 typename _OutputIterator>
6122 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6123 _InputIterator2 __first2, _InputIterator2 __last2,
6124 _OutputIterator __result)
6126 typedef typename iterator_traits<_InputIterator1>::value_type
6128 typedef typename iterator_traits<_InputIterator2>::value_type
6131 // concept requirements
6132 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6133 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6134 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6136 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6138 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6139 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6140 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6141 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6143 while (__first1 != __last1 && __first2 != __last2)
6144 if (*__first1 < *__first2)
6146 *__result = *__first1;
6150 else if (*__first2 < *__first1)
6152 *__result = *__first2;
6161 return std::copy(__first2, __last2, std::copy(__first1,
6162 __last1, __result));
6166 * @brief Return the symmetric difference of two sorted ranges using
6167 * comparison functor.
6168 * @ingroup set_algorithms
6169 * @param __first1 Start of first range.
6170 * @param __last1 End of first range.
6171 * @param __first2 Start of second range.
6172 * @param __last2 End of second range.
6173 * @param __comp The comparison functor.
6174 * @return End of the output range.
6175 * @ingroup set_algorithms
6177 * This operation iterates over both ranges, copying elements present in
6178 * one range but not the other in order to the output range. Iterators
6179 * increment for each range. When the current element of one range is less
6180 * than the other according to @p comp, that element is copied and the
6181 * iterator advances. If an element is contained in both ranges according
6182 * to @p __comp, no elements are copied and both ranges advance. The output
6183 * range may not overlap either input range.
6185 template<typename _InputIterator1, typename _InputIterator2,
6186 typename _OutputIterator, typename _Compare>
6188 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6189 _InputIterator2 __first2, _InputIterator2 __last2,
6190 _OutputIterator __result,
6193 typedef typename iterator_traits<_InputIterator1>::value_type
6195 typedef typename iterator_traits<_InputIterator2>::value_type
6198 // concept requirements
6199 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6200 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6201 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6203 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6205 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6206 _ValueType1, _ValueType2>)
6207 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6208 _ValueType2, _ValueType1>)
6209 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6210 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6212 while (__first1 != __last1 && __first2 != __last2)
6213 if (__comp(*__first1, *__first2))
6215 *__result = *__first1;
6219 else if (__comp(*__first2, *__first1))
6221 *__result = *__first2;
6230 return std::copy(__first2, __last2,
6231 std::copy(__first1, __last1, __result));
6236 * @brief Return the minimum element in a range.
6237 * @ingroup sorting_algorithms
6238 * @param __first Start of range.
6239 * @param __last End of range.
6240 * @return Iterator referencing the first instance of the smallest value.
6242 template<typename _ForwardIterator>
6244 min_element(_ForwardIterator __first, _ForwardIterator __last)
6246 // concept requirements
6247 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6248 __glibcxx_function_requires(_LessThanComparableConcept<
6249 typename iterator_traits<_ForwardIterator>::value_type>)
6250 __glibcxx_requires_valid_range(__first, __last);
6252 if (__first == __last)
6254 _ForwardIterator __result = __first;
6255 while (++__first != __last)
6256 if (*__first < *__result)
6262 * @brief Return the minimum element in a range using comparison functor.
6263 * @ingroup sorting_algorithms
6264 * @param __first Start of range.
6265 * @param __last End of range.
6266 * @param __comp Comparison functor.
6267 * @return Iterator referencing the first instance of the smallest value
6268 * according to __comp.
6270 template<typename _ForwardIterator, typename _Compare>
6272 min_element(_ForwardIterator __first, _ForwardIterator __last,
6275 // concept requirements
6276 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6277 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6278 typename iterator_traits<_ForwardIterator>::value_type,
6279 typename iterator_traits<_ForwardIterator>::value_type>)
6280 __glibcxx_requires_valid_range(__first, __last);
6282 if (__first == __last)
6284 _ForwardIterator __result = __first;
6285 while (++__first != __last)
6286 if (__comp(*__first, *__result))
6292 * @brief Return the maximum element in a range.
6293 * @ingroup sorting_algorithms
6294 * @param __first Start of range.
6295 * @param __last End of range.
6296 * @return Iterator referencing the first instance of the largest value.
6298 template<typename _ForwardIterator>
6300 max_element(_ForwardIterator __first, _ForwardIterator __last)
6302 // concept requirements
6303 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6304 __glibcxx_function_requires(_LessThanComparableConcept<
6305 typename iterator_traits<_ForwardIterator>::value_type>)
6306 __glibcxx_requires_valid_range(__first, __last);
6308 if (__first == __last)
6310 _ForwardIterator __result = __first;
6311 while (++__first != __last)
6312 if (*__result < *__first)
6318 * @brief Return the maximum element in a range using comparison functor.
6319 * @ingroup sorting_algorithms
6320 * @param __first Start of range.
6321 * @param __last End of range.
6322 * @param __comp Comparison functor.
6323 * @return Iterator referencing the first instance of the largest value
6324 * according to __comp.
6326 template<typename _ForwardIterator, typename _Compare>
6328 max_element(_ForwardIterator __first, _ForwardIterator __last,
6331 // concept requirements
6332 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6333 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6334 typename iterator_traits<_ForwardIterator>::value_type,
6335 typename iterator_traits<_ForwardIterator>::value_type>)
6336 __glibcxx_requires_valid_range(__first, __last);
6338 if (__first == __last) return __first;
6339 _ForwardIterator __result = __first;
6340 while (++__first != __last)
6341 if (__comp(*__result, *__first))
6346 _GLIBCXX_END_NAMESPACE_ALGO
6349 #endif /* _STL_ALGO_H */