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 *__result
78 template<typename _Iterator>
80 __move_median_to_first(_Iterator __result, _Iterator __a,
81 _Iterator __b, _Iterator __c)
83 // concept requirements
84 __glibcxx_function_requires(_LessThanComparableConcept<
85 typename iterator_traits<_Iterator>::value_type>)
90 std::iter_swap(__result, __b);
92 std::iter_swap(__result, __c);
94 std::iter_swap(__result, __a);
97 std::iter_swap(__result, __a);
99 std::iter_swap(__result, __c);
101 std::iter_swap(__result, __b);
104 /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
105 template<typename _Iterator, typename _Compare>
107 __move_median_to_first(_Iterator __result, _Iterator __a,
108 _Iterator __b, _Iterator __c,
111 // concept requirements
112 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
113 typename iterator_traits<_Iterator>::value_type,
114 typename iterator_traits<_Iterator>::value_type>)
116 if (__comp(*__a, *__b))
118 if (__comp(*__b, *__c))
119 std::iter_swap(__result, __b);
120 else if (__comp(*__a, *__c))
121 std::iter_swap(__result, __c);
123 std::iter_swap(__result, __a);
125 else if (__comp(*__a, *__c))
126 std::iter_swap(__result, __a);
127 else if (__comp(*__b, *__c))
128 std::iter_swap(__result, __c);
130 std::iter_swap(__result, __b);
135 /// This is an overload used by find() for the Input Iterator case.
136 template<typename _InputIterator, typename _Tp>
137 inline _InputIterator
138 __find(_InputIterator __first, _InputIterator __last,
139 const _Tp& __val, input_iterator_tag)
141 while (__first != __last && !(*__first == __val))
146 /// This is an overload used by find_if() for the Input Iterator case.
147 template<typename _InputIterator, typename _Predicate>
148 inline _InputIterator
149 __find_if(_InputIterator __first, _InputIterator __last,
150 _Predicate __pred, input_iterator_tag)
152 while (__first != __last && !bool(__pred(*__first)))
157 /// This is an overload used by find() for the RAI case.
158 template<typename _RandomAccessIterator, typename _Tp>
159 _RandomAccessIterator
160 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
161 const _Tp& __val, random_access_iterator_tag)
163 typename iterator_traits<_RandomAccessIterator>::difference_type
164 __trip_count = (__last - __first) >> 2;
166 for (; __trip_count > 0; --__trip_count)
168 if (*__first == __val)
172 if (*__first == __val)
176 if (*__first == __val)
180 if (*__first == __val)
185 switch (__last - __first)
188 if (*__first == __val)
192 if (*__first == __val)
196 if (*__first == __val)
205 /// This is an overload used by find_if() for the RAI case.
206 template<typename _RandomAccessIterator, typename _Predicate>
207 _RandomAccessIterator
208 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
209 _Predicate __pred, random_access_iterator_tag)
211 typename iterator_traits<_RandomAccessIterator>::difference_type
212 __trip_count = (__last - __first) >> 2;
214 for (; __trip_count > 0; --__trip_count)
216 if (__pred(*__first))
220 if (__pred(*__first))
224 if (__pred(*__first))
228 if (__pred(*__first))
233 switch (__last - __first)
236 if (__pred(*__first))
240 if (__pred(*__first))
244 if (__pred(*__first))
253 /// This is an overload used by find_if_not() for the Input Iterator case.
254 template<typename _InputIterator, typename _Predicate>
255 inline _InputIterator
256 __find_if_not(_InputIterator __first, _InputIterator __last,
257 _Predicate __pred, input_iterator_tag)
259 while (__first != __last && bool(__pred(*__first)))
264 /// This is an overload used by find_if_not() for the RAI case.
265 template<typename _RandomAccessIterator, typename _Predicate>
266 _RandomAccessIterator
267 __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last,
268 _Predicate __pred, random_access_iterator_tag)
270 typename iterator_traits<_RandomAccessIterator>::difference_type
271 __trip_count = (__last - __first) >> 2;
273 for (; __trip_count > 0; --__trip_count)
275 if (!bool(__pred(*__first)))
279 if (!bool(__pred(*__first)))
283 if (!bool(__pred(*__first)))
287 if (!bool(__pred(*__first)))
292 switch (__last - __first)
295 if (!bool(__pred(*__first)))
299 if (!bool(__pred(*__first)))
303 if (!bool(__pred(*__first)))
312 /// Provided for stable_partition to use.
313 template<typename _InputIterator, typename _Predicate>
314 inline _InputIterator
315 __find_if_not(_InputIterator __first, _InputIterator __last,
318 return std::__find_if_not(__first, __last, __pred,
319 std::__iterator_category(__first));
322 /// Like find_if_not(), but uses and updates a count of the
323 /// remaining range length instead of comparing against an end
325 template<typename _InputIterator, typename _Predicate, typename _Distance>
327 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
329 for (; __len; --__len, ++__first)
330 if (!bool(__pred(*__first)))
337 // set_symmetric_difference
349 * This is an uglified
350 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
351 * overloaded for forward iterators.
353 template<typename _ForwardIterator, typename _Integer, typename _Tp>
355 __search_n(_ForwardIterator __first, _ForwardIterator __last,
356 _Integer __count, const _Tp& __val,
357 std::forward_iterator_tag)
359 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
360 while (__first != __last)
362 typename iterator_traits<_ForwardIterator>::difference_type
364 _ForwardIterator __i = __first;
366 while (__i != __last && __n != 1 && *__i == __val)
375 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
381 * This is an uglified
382 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
383 * overloaded for random access iterators.
385 template<typename _RandomAccessIter, typename _Integer, typename _Tp>
387 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
388 _Integer __count, const _Tp& __val,
389 std::random_access_iterator_tag)
392 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
395 _DistanceType __tailSize = __last - __first;
396 const _DistanceType __pattSize = __count;
398 if (__tailSize < __pattSize)
401 const _DistanceType __skipOffset = __pattSize - 1;
402 _RandomAccessIter __lookAhead = __first + __skipOffset;
403 __tailSize -= __pattSize;
405 while (1) // the main loop...
407 // __lookAhead here is always pointing to the last element of next
409 while (!(*__lookAhead == __val)) // the skip loop...
411 if (__tailSize < __pattSize)
412 return __last; // Failure
413 __lookAhead += __pattSize;
414 __tailSize -= __pattSize;
416 _DistanceType __remainder = __skipOffset;
417 for (_RandomAccessIter __backTrack = __lookAhead - 1;
418 *__backTrack == __val; --__backTrack)
420 if (--__remainder == 0)
421 return (__lookAhead - __skipOffset); // Success
423 if (__remainder > __tailSize)
424 return __last; // Failure
425 __lookAhead += __remainder;
426 __tailSize -= __remainder;
433 * This is an uglified
434 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
436 * overloaded for forward iterators.
438 template<typename _ForwardIterator, typename _Integer, typename _Tp,
439 typename _BinaryPredicate>
441 __search_n(_ForwardIterator __first, _ForwardIterator __last,
442 _Integer __count, const _Tp& __val,
443 _BinaryPredicate __binary_pred, std::forward_iterator_tag)
445 while (__first != __last && !bool(__binary_pred(*__first, __val)))
448 while (__first != __last)
450 typename iterator_traits<_ForwardIterator>::difference_type
452 _ForwardIterator __i = __first;
454 while (__i != __last && __n != 1 && bool(__binary_pred(*__i, __val)))
464 while (__first != __last
465 && !bool(__binary_pred(*__first, __val)))
472 * This is an uglified
473 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
475 * overloaded for random access iterators.
477 template<typename _RandomAccessIter, typename _Integer, typename _Tp,
478 typename _BinaryPredicate>
480 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
481 _Integer __count, const _Tp& __val,
482 _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
485 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
488 _DistanceType __tailSize = __last - __first;
489 const _DistanceType __pattSize = __count;
491 if (__tailSize < __pattSize)
494 const _DistanceType __skipOffset = __pattSize - 1;
495 _RandomAccessIter __lookAhead = __first + __skipOffset;
496 __tailSize -= __pattSize;
498 while (1) // the main loop...
500 // __lookAhead here is always pointing to the last element of next
502 while (!bool(__binary_pred(*__lookAhead, __val))) // the skip loop...
504 if (__tailSize < __pattSize)
505 return __last; // Failure
506 __lookAhead += __pattSize;
507 __tailSize -= __pattSize;
509 _DistanceType __remainder = __skipOffset;
510 for (_RandomAccessIter __backTrack = __lookAhead - 1;
511 __binary_pred(*__backTrack, __val); --__backTrack)
513 if (--__remainder == 0)
514 return (__lookAhead - __skipOffset); // Success
516 if (__remainder > __tailSize)
517 return __last; // Failure
518 __lookAhead += __remainder;
519 __tailSize -= __remainder;
523 // find_end for forward iterators.
524 template<typename _ForwardIterator1, typename _ForwardIterator2>
526 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
527 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
528 forward_iterator_tag, forward_iterator_tag)
530 if (__first2 == __last2)
534 _ForwardIterator1 __result = __last1;
537 _ForwardIterator1 __new_result
538 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
539 if (__new_result == __last1)
543 __result = __new_result;
544 __first1 = __new_result;
551 template<typename _ForwardIterator1, typename _ForwardIterator2,
552 typename _BinaryPredicate>
554 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
555 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
556 forward_iterator_tag, forward_iterator_tag,
557 _BinaryPredicate __comp)
559 if (__first2 == __last2)
563 _ForwardIterator1 __result = __last1;
566 _ForwardIterator1 __new_result
567 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
569 if (__new_result == __last1)
573 __result = __new_result;
574 __first1 = __new_result;
581 // find_end for bidirectional iterators (much faster).
582 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
583 _BidirectionalIterator1
584 __find_end(_BidirectionalIterator1 __first1,
585 _BidirectionalIterator1 __last1,
586 _BidirectionalIterator2 __first2,
587 _BidirectionalIterator2 __last2,
588 bidirectional_iterator_tag, bidirectional_iterator_tag)
590 // concept requirements
591 __glibcxx_function_requires(_BidirectionalIteratorConcept<
592 _BidirectionalIterator1>)
593 __glibcxx_function_requires(_BidirectionalIteratorConcept<
594 _BidirectionalIterator2>)
596 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
597 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
599 _RevIterator1 __rlast1(__first1);
600 _RevIterator2 __rlast2(__first2);
601 _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
603 _RevIterator2(__last2),
606 if (__rresult == __rlast1)
610 _BidirectionalIterator1 __result = __rresult.base();
611 std::advance(__result, -std::distance(__first2, __last2));
616 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
617 typename _BinaryPredicate>
618 _BidirectionalIterator1
619 __find_end(_BidirectionalIterator1 __first1,
620 _BidirectionalIterator1 __last1,
621 _BidirectionalIterator2 __first2,
622 _BidirectionalIterator2 __last2,
623 bidirectional_iterator_tag, bidirectional_iterator_tag,
624 _BinaryPredicate __comp)
626 // concept requirements
627 __glibcxx_function_requires(_BidirectionalIteratorConcept<
628 _BidirectionalIterator1>)
629 __glibcxx_function_requires(_BidirectionalIteratorConcept<
630 _BidirectionalIterator2>)
632 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
633 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
635 _RevIterator1 __rlast1(__first1);
636 _RevIterator2 __rlast2(__first2);
637 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
638 _RevIterator2(__last2), __rlast2,
641 if (__rresult == __rlast1)
645 _BidirectionalIterator1 __result = __rresult.base();
646 std::advance(__result, -std::distance(__first2, __last2));
652 * @brief Find last matching subsequence in a sequence.
653 * @ingroup non_mutating_algorithms
654 * @param __first1 Start of range to search.
655 * @param __last1 End of range to search.
656 * @param __first2 Start of sequence to match.
657 * @param __last2 End of sequence to match.
658 * @return The last iterator @c i in the range
659 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
660 * @p *(__first2+N) for each @c N in the range @p
661 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
663 * Searches the range @p [__first1,__last1) for a sub-sequence that
664 * compares equal value-by-value with the sequence given by @p
665 * [__first2,__last2) and returns an iterator to the __first
666 * element of the sub-sequence, or @p __last1 if the sub-sequence
667 * is not found. The sub-sequence will be the last such
668 * subsequence contained in [__first,__last1).
670 * Because the sub-sequence must lie completely within the range @p
671 * [__first1,__last1) it must start at a position less than @p
672 * __last1-(__last2-__first2) where @p __last2-__first2 is the
673 * length of the sub-sequence. This means that the returned
674 * iterator @c i will be in the range @p
675 * [__first1,__last1-(__last2-__first2))
677 template<typename _ForwardIterator1, typename _ForwardIterator2>
678 inline _ForwardIterator1
679 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
680 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
682 // concept requirements
683 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
684 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
685 __glibcxx_function_requires(_EqualOpConcept<
686 typename iterator_traits<_ForwardIterator1>::value_type,
687 typename iterator_traits<_ForwardIterator2>::value_type>)
688 __glibcxx_requires_valid_range(__first1, __last1);
689 __glibcxx_requires_valid_range(__first2, __last2);
691 return std::__find_end(__first1, __last1, __first2, __last2,
692 std::__iterator_category(__first1),
693 std::__iterator_category(__first2));
697 * @brief Find last matching subsequence in a sequence using a predicate.
698 * @ingroup non_mutating_algorithms
699 * @param __first1 Start of range to search.
700 * @param __last1 End of range to search.
701 * @param __first2 Start of sequence to match.
702 * @param __last2 End of sequence to match.
703 * @param __comp The predicate to use.
704 * @return The last iterator @c i in the range @p
705 * [__first1,__last1-(__last2-__first2)) such that @c
706 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
707 * range @p [0,__last2-__first2), or @p __last1 if no such iterator
710 * Searches the range @p [__first1,__last1) for a sub-sequence that
711 * compares equal value-by-value with the sequence given by @p
712 * [__first2,__last2) using comp as a predicate and returns an
713 * iterator to the first element of the sub-sequence, or @p __last1
714 * if the sub-sequence is not found. The sub-sequence will be the
715 * last such subsequence contained in [__first,__last1).
717 * Because the sub-sequence must lie completely within the range @p
718 * [__first1,__last1) it must start at a position less than @p
719 * __last1-(__last2-__first2) where @p __last2-__first2 is the
720 * length of the sub-sequence. This means that the returned
721 * iterator @c i will be in the range @p
722 * [__first1,__last1-(__last2-__first2))
724 template<typename _ForwardIterator1, typename _ForwardIterator2,
725 typename _BinaryPredicate>
726 inline _ForwardIterator1
727 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
728 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
729 _BinaryPredicate __comp)
731 // concept requirements
732 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
733 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
734 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
735 typename iterator_traits<_ForwardIterator1>::value_type,
736 typename iterator_traits<_ForwardIterator2>::value_type>)
737 __glibcxx_requires_valid_range(__first1, __last1);
738 __glibcxx_requires_valid_range(__first2, __last2);
740 return std::__find_end(__first1, __last1, __first2, __last2,
741 std::__iterator_category(__first1),
742 std::__iterator_category(__first2),
746 #ifdef __GXX_EXPERIMENTAL_CXX0X__
748 * @brief Checks that a predicate is true for all the elements
750 * @ingroup non_mutating_algorithms
751 * @param __first An input iterator.
752 * @param __last An input iterator.
753 * @param __pred A predicate.
754 * @return True if the check is true, false otherwise.
756 * Returns true if @p __pred is true for each element in the range
757 * @p [__first,__last), and false otherwise.
759 template<typename _InputIterator, typename _Predicate>
761 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
762 { return __last == std::find_if_not(__first, __last, __pred); }
765 * @brief Checks that a predicate is false for all the elements
767 * @ingroup non_mutating_algorithms
768 * @param __first An input iterator.
769 * @param __last An input iterator.
770 * @param __pred A predicate.
771 * @return True if the check is true, false otherwise.
773 * Returns true if @p __pred is false for each element in the range
774 * @p [__first,__last), and false otherwise.
776 template<typename _InputIterator, typename _Predicate>
778 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
779 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
782 * @brief Checks that a predicate is false for at least an element
784 * @ingroup non_mutating_algorithms
785 * @param __first An input iterator.
786 * @param __last An input iterator.
787 * @param __pred A predicate.
788 * @return True if the check is true, false otherwise.
790 * Returns true if an element exists in the range @p
791 * [__first,__last) such that @p __pred is true, and false
794 template<typename _InputIterator, typename _Predicate>
796 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
797 { return !std::none_of(__first, __last, __pred); }
800 * @brief Find the first element in a sequence for which a
801 * predicate is false.
802 * @ingroup non_mutating_algorithms
803 * @param __first An input iterator.
804 * @param __last An input iterator.
805 * @param __pred A predicate.
806 * @return The first iterator @c i in the range @p [__first,__last)
807 * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
809 template<typename _InputIterator, typename _Predicate>
810 inline _InputIterator
811 find_if_not(_InputIterator __first, _InputIterator __last,
814 // concept requirements
815 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
816 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
817 typename iterator_traits<_InputIterator>::value_type>)
818 __glibcxx_requires_valid_range(__first, __last);
819 return std::__find_if_not(__first, __last, __pred);
823 * @brief Checks whether the sequence is partitioned.
824 * @ingroup mutating_algorithms
825 * @param __first An input iterator.
826 * @param __last An input iterator.
827 * @param __pred A predicate.
828 * @return True if the range @p [__first,__last) is partioned by @p __pred,
829 * i.e. if all elements that satisfy @p __pred appear before those that
832 template<typename _InputIterator, typename _Predicate>
834 is_partitioned(_InputIterator __first, _InputIterator __last,
837 __first = std::find_if_not(__first, __last, __pred);
838 return std::none_of(__first, __last, __pred);
842 * @brief Find the partition point of a partitioned range.
843 * @ingroup mutating_algorithms
844 * @param __first An iterator.
845 * @param __last Another iterator.
846 * @param __pred A predicate.
847 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
848 * and @p none_of(mid, __last, __pred) are both true.
850 template<typename _ForwardIterator, typename _Predicate>
852 partition_point(_ForwardIterator __first, _ForwardIterator __last,
855 // concept requirements
856 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
857 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
858 typename iterator_traits<_ForwardIterator>::value_type>)
860 // A specific debug-mode test will be necessary...
861 __glibcxx_requires_valid_range(__first, __last);
863 typedef typename iterator_traits<_ForwardIterator>::difference_type
866 _DistanceType __len = std::distance(__first, __last);
867 _DistanceType __half;
868 _ForwardIterator __middle;
874 std::advance(__middle, __half);
875 if (__pred(*__middle))
879 __len = __len - __half - 1;
890 * @brief Copy a sequence, removing elements of a given value.
891 * @ingroup mutating_algorithms
892 * @param __first An input iterator.
893 * @param __last An input iterator.
894 * @param __result An output iterator.
895 * @param __value The value to be removed.
896 * @return An iterator designating the end of the resulting sequence.
898 * Copies each element in the range @p [__first,__last) not equal
899 * to @p __value to the range beginning at @p __result.
900 * remove_copy() is stable, so the relative order of elements that
901 * are copied is unchanged.
903 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
905 remove_copy(_InputIterator __first, _InputIterator __last,
906 _OutputIterator __result, const _Tp& __value)
908 // concept requirements
909 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
910 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
911 typename iterator_traits<_InputIterator>::value_type>)
912 __glibcxx_function_requires(_EqualOpConcept<
913 typename iterator_traits<_InputIterator>::value_type, _Tp>)
914 __glibcxx_requires_valid_range(__first, __last);
916 for (; __first != __last; ++__first)
917 if (!(*__first == __value))
919 *__result = *__first;
926 * @brief Copy a sequence, removing elements for which a predicate is true.
927 * @ingroup mutating_algorithms
928 * @param __first An input iterator.
929 * @param __last An input iterator.
930 * @param __result An output iterator.
931 * @param __pred A predicate.
932 * @return An iterator designating the end of the resulting sequence.
934 * Copies each element in the range @p [__first,__last) for which
935 * @p __pred returns false to the range beginning at @p __result.
937 * remove_copy_if() is stable, so the relative order of elements that are
938 * copied is unchanged.
940 template<typename _InputIterator, typename _OutputIterator,
943 remove_copy_if(_InputIterator __first, _InputIterator __last,
944 _OutputIterator __result, _Predicate __pred)
946 // concept requirements
947 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
948 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
949 typename iterator_traits<_InputIterator>::value_type>)
950 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
951 typename iterator_traits<_InputIterator>::value_type>)
952 __glibcxx_requires_valid_range(__first, __last);
954 for (; __first != __last; ++__first)
955 if (!bool(__pred(*__first)))
957 *__result = *__first;
963 #ifdef __GXX_EXPERIMENTAL_CXX0X__
965 * @brief Copy the elements of a sequence for which a predicate is true.
966 * @ingroup mutating_algorithms
967 * @param __first An input iterator.
968 * @param __last An input iterator.
969 * @param __result An output iterator.
970 * @param __pred A predicate.
971 * @return An iterator designating the end of the resulting sequence.
973 * Copies each element in the range @p [__first,__last) for which
974 * @p __pred returns true to the range beginning at @p __result.
976 * copy_if() is stable, so the relative order of elements that are
977 * copied is unchanged.
979 template<typename _InputIterator, typename _OutputIterator,
982 copy_if(_InputIterator __first, _InputIterator __last,
983 _OutputIterator __result, _Predicate __pred)
985 // concept requirements
986 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
987 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
988 typename iterator_traits<_InputIterator>::value_type>)
989 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
990 typename iterator_traits<_InputIterator>::value_type>)
991 __glibcxx_requires_valid_range(__first, __last);
993 for (; __first != __last; ++__first)
994 if (__pred(*__first))
996 *__result = *__first;
1003 template<typename _InputIterator, typename _Size, typename _OutputIterator>
1005 __copy_n(_InputIterator __first, _Size __n,
1006 _OutputIterator __result, input_iterator_tag)
1012 *__result = *__first;
1023 template<typename _RandomAccessIterator, typename _Size,
1024 typename _OutputIterator>
1025 inline _OutputIterator
1026 __copy_n(_RandomAccessIterator __first, _Size __n,
1027 _OutputIterator __result, random_access_iterator_tag)
1028 { return std::copy(__first, __first + __n, __result); }
1031 * @brief Copies the range [first,first+n) into [result,result+n).
1032 * @ingroup mutating_algorithms
1033 * @param __first An input iterator.
1034 * @param __n The number of elements to copy.
1035 * @param __result An output iterator.
1038 * This inline function will boil down to a call to @c memmove whenever
1039 * possible. Failing that, if random access iterators are passed, then the
1040 * loop count will be known (and therefore a candidate for compiler
1041 * optimizations such as unrolling).
1043 template<typename _InputIterator, typename _Size, typename _OutputIterator>
1044 inline _OutputIterator
1045 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1047 // concept requirements
1048 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1049 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1050 typename iterator_traits<_InputIterator>::value_type>)
1052 return std::__copy_n(__first, __n, __result,
1053 std::__iterator_category(__first));
1057 * @brief Copy the elements of a sequence to separate output sequences
1058 * depending on the truth value of a predicate.
1059 * @ingroup mutating_algorithms
1060 * @param __first An input iterator.
1061 * @param __last An input iterator.
1062 * @param __out_true An output iterator.
1063 * @param __out_false An output iterator.
1064 * @param __pred A predicate.
1065 * @return A pair designating the ends of the resulting sequences.
1067 * Copies each element in the range @p [__first,__last) for which
1068 * @p __pred returns true to the range beginning at @p out_true
1069 * and each element for which @p __pred returns false to @p __out_false.
1071 template<typename _InputIterator, typename _OutputIterator1,
1072 typename _OutputIterator2, typename _Predicate>
1073 pair<_OutputIterator1, _OutputIterator2>
1074 partition_copy(_InputIterator __first, _InputIterator __last,
1075 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1078 // concept requirements
1079 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1080 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1081 typename iterator_traits<_InputIterator>::value_type>)
1082 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1083 typename iterator_traits<_InputIterator>::value_type>)
1084 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1085 typename iterator_traits<_InputIterator>::value_type>)
1086 __glibcxx_requires_valid_range(__first, __last);
1088 for (; __first != __last; ++__first)
1089 if (__pred(*__first))
1091 *__out_true = *__first;
1096 *__out_false = *__first;
1100 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);
1105 * @brief Remove elements from a sequence.
1106 * @ingroup mutating_algorithms
1107 * @param __first An input iterator.
1108 * @param __last An input iterator.
1109 * @param __value The value to be removed.
1110 * @return An iterator designating the end of the resulting sequence.
1112 * All elements equal to @p __value are removed from the range
1113 * @p [__first,__last).
1115 * remove() is stable, so the relative order of elements that are
1116 * not removed is unchanged.
1118 * Elements between the end of the resulting sequence and @p __last
1119 * are still present, but their value is unspecified.
1121 template<typename _ForwardIterator, typename _Tp>
1123 remove(_ForwardIterator __first, _ForwardIterator __last,
1126 // concept requirements
1127 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1129 __glibcxx_function_requires(_EqualOpConcept<
1130 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1131 __glibcxx_requires_valid_range(__first, __last);
1133 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1134 if(__first == __last)
1136 _ForwardIterator __result = __first;
1138 for(; __first != __last; ++__first)
1139 if(!(*__first == __value))
1141 *__result = _GLIBCXX_MOVE(*__first);
1148 * @brief Remove elements from a sequence using a predicate.
1149 * @ingroup mutating_algorithms
1150 * @param __first A forward iterator.
1151 * @param __last A forward iterator.
1152 * @param __pred A predicate.
1153 * @return An iterator designating the end of the resulting sequence.
1155 * All elements for which @p __pred returns true are removed from the range
1156 * @p [__first,__last).
1158 * remove_if() is stable, so the relative order of elements that are
1159 * not removed is unchanged.
1161 * Elements between the end of the resulting sequence and @p __last
1162 * are still present, but their value is unspecified.
1164 template<typename _ForwardIterator, typename _Predicate>
1166 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1169 // concept requirements
1170 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1172 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1173 typename iterator_traits<_ForwardIterator>::value_type>)
1174 __glibcxx_requires_valid_range(__first, __last);
1176 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1177 if(__first == __last)
1179 _ForwardIterator __result = __first;
1181 for(; __first != __last; ++__first)
1182 if(!bool(__pred(*__first)))
1184 *__result = _GLIBCXX_MOVE(*__first);
1191 * @brief Remove consecutive duplicate values from a sequence.
1192 * @ingroup mutating_algorithms
1193 * @param __first A forward iterator.
1194 * @param __last A forward iterator.
1195 * @return An iterator designating the end of the resulting sequence.
1197 * Removes all but the first element from each group of consecutive
1198 * values that compare equal.
1199 * unique() is stable, so the relative order of elements that are
1200 * not removed is unchanged.
1201 * Elements between the end of the resulting sequence and @p __last
1202 * are still present, but their value is unspecified.
1204 template<typename _ForwardIterator>
1206 unique(_ForwardIterator __first, _ForwardIterator __last)
1208 // concept requirements
1209 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1211 __glibcxx_function_requires(_EqualityComparableConcept<
1212 typename iterator_traits<_ForwardIterator>::value_type>)
1213 __glibcxx_requires_valid_range(__first, __last);
1215 // Skip the beginning, if already unique.
1216 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1217 if (__first == __last)
1220 // Do the real copy work.
1221 _ForwardIterator __dest = __first;
1223 while (++__first != __last)
1224 if (!(*__dest == *__first))
1225 *++__dest = _GLIBCXX_MOVE(*__first);
1230 * @brief Remove consecutive values from a sequence using a predicate.
1231 * @ingroup mutating_algorithms
1232 * @param __first A forward iterator.
1233 * @param __last A forward iterator.
1234 * @param __binary_pred A binary predicate.
1235 * @return An iterator designating the end of the resulting sequence.
1237 * Removes all but the first element from each group of consecutive
1238 * values for which @p __binary_pred returns true.
1239 * unique() is stable, so the relative order of elements that are
1240 * not removed is unchanged.
1241 * Elements between the end of the resulting sequence and @p __last
1242 * are still present, but their value is unspecified.
1244 template<typename _ForwardIterator, typename _BinaryPredicate>
1246 unique(_ForwardIterator __first, _ForwardIterator __last,
1247 _BinaryPredicate __binary_pred)
1249 // concept requirements
1250 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1252 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1253 typename iterator_traits<_ForwardIterator>::value_type,
1254 typename iterator_traits<_ForwardIterator>::value_type>)
1255 __glibcxx_requires_valid_range(__first, __last);
1257 // Skip the beginning, if already unique.
1258 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1259 if (__first == __last)
1262 // Do the real copy work.
1263 _ForwardIterator __dest = __first;
1265 while (++__first != __last)
1266 if (!bool(__binary_pred(*__dest, *__first)))
1267 *++__dest = _GLIBCXX_MOVE(*__first);
1272 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1274 * overloaded for forward iterators and output iterator as result.
1276 template<typename _ForwardIterator, typename _OutputIterator>
1278 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1279 _OutputIterator __result,
1280 forward_iterator_tag, output_iterator_tag)
1282 // concept requirements -- taken care of in dispatching function
1283 _ForwardIterator __next = __first;
1284 *__result = *__first;
1285 while (++__next != __last)
1286 if (!(*__first == *__next))
1289 *++__result = *__first;
1295 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1297 * overloaded for input iterators and output iterator as result.
1299 template<typename _InputIterator, typename _OutputIterator>
1301 __unique_copy(_InputIterator __first, _InputIterator __last,
1302 _OutputIterator __result,
1303 input_iterator_tag, output_iterator_tag)
1305 // concept requirements -- taken care of in dispatching function
1306 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1307 *__result = __value;
1308 while (++__first != __last)
1309 if (!(__value == *__first))
1312 *++__result = __value;
1318 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1320 * overloaded for input iterators and forward iterator as result.
1322 template<typename _InputIterator, typename _ForwardIterator>
1324 __unique_copy(_InputIterator __first, _InputIterator __last,
1325 _ForwardIterator __result,
1326 input_iterator_tag, forward_iterator_tag)
1328 // concept requirements -- taken care of in dispatching function
1329 *__result = *__first;
1330 while (++__first != __last)
1331 if (!(*__result == *__first))
1332 *++__result = *__first;
1337 * This is an uglified
1338 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1340 * overloaded for forward iterators and output iterator as result.
1342 template<typename _ForwardIterator, typename _OutputIterator,
1343 typename _BinaryPredicate>
1345 __unique_copy(_ForwardIterator __first, _ForwardIterator __last,
1346 _OutputIterator __result, _BinaryPredicate __binary_pred,
1347 forward_iterator_tag, output_iterator_tag)
1349 // concept requirements -- iterators already checked
1350 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1351 typename iterator_traits<_ForwardIterator>::value_type,
1352 typename iterator_traits<_ForwardIterator>::value_type>)
1354 _ForwardIterator __next = __first;
1355 *__result = *__first;
1356 while (++__next != __last)
1357 if (!bool(__binary_pred(*__first, *__next)))
1360 *++__result = *__first;
1366 * This is an uglified
1367 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1369 * overloaded for input iterators and output iterator as result.
1371 template<typename _InputIterator, typename _OutputIterator,
1372 typename _BinaryPredicate>
1374 __unique_copy(_InputIterator __first, _InputIterator __last,
1375 _OutputIterator __result, _BinaryPredicate __binary_pred,
1376 input_iterator_tag, output_iterator_tag)
1378 // concept requirements -- iterators already checked
1379 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1380 typename iterator_traits<_InputIterator>::value_type,
1381 typename iterator_traits<_InputIterator>::value_type>)
1383 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1384 *__result = __value;
1385 while (++__first != __last)
1386 if (!bool(__binary_pred(__value, *__first)))
1389 *++__result = __value;
1395 * This is an uglified
1396 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1398 * overloaded for input iterators and forward iterator as result.
1400 template<typename _InputIterator, typename _ForwardIterator,
1401 typename _BinaryPredicate>
1403 __unique_copy(_InputIterator __first, _InputIterator __last,
1404 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1405 input_iterator_tag, forward_iterator_tag)
1407 // concept requirements -- iterators already checked
1408 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1409 typename iterator_traits<_ForwardIterator>::value_type,
1410 typename iterator_traits<_InputIterator>::value_type>)
1412 *__result = *__first;
1413 while (++__first != __last)
1414 if (!bool(__binary_pred(*__result, *__first)))
1415 *++__result = *__first;
1420 * This is an uglified reverse(_BidirectionalIterator,
1421 * _BidirectionalIterator)
1422 * overloaded for bidirectional iterators.
1424 template<typename _BidirectionalIterator>
1426 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1427 bidirectional_iterator_tag)
1430 if (__first == __last || __first == --__last)
1434 std::iter_swap(__first, __last);
1440 * This is an uglified reverse(_BidirectionalIterator,
1441 * _BidirectionalIterator)
1442 * overloaded for random access iterators.
1444 template<typename _RandomAccessIterator>
1446 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1447 random_access_iterator_tag)
1449 if (__first == __last)
1452 while (__first < __last)
1454 std::iter_swap(__first, __last);
1461 * @brief Reverse a sequence.
1462 * @ingroup mutating_algorithms
1463 * @param __first A bidirectional iterator.
1464 * @param __last A bidirectional iterator.
1465 * @return reverse() returns no value.
1467 * Reverses the order of the elements in the range @p [__first,__last),
1468 * so that the first element becomes the last etc.
1469 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1470 * swaps @p *(__first+i) and @p *(__last-(i+1))
1472 template<typename _BidirectionalIterator>
1474 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1476 // concept requirements
1477 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1478 _BidirectionalIterator>)
1479 __glibcxx_requires_valid_range(__first, __last);
1480 std::__reverse(__first, __last, std::__iterator_category(__first));
1484 * @brief Copy a sequence, reversing its elements.
1485 * @ingroup mutating_algorithms
1486 * @param __first A bidirectional iterator.
1487 * @param __last A bidirectional iterator.
1488 * @param __result An output iterator.
1489 * @return An iterator designating the end of the resulting sequence.
1491 * Copies the elements in the range @p [__first,__last) to the
1492 * range @p [__result,__result+(__last-__first)) such that the
1493 * order of the elements is reversed. For every @c i such that @p
1494 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1495 * assignment @p *(__result+(__last-__first)-i) = *(__first+i).
1496 * The ranges @p [__first,__last) and @p
1497 * [__result,__result+(__last-__first)) must not overlap.
1499 template<typename _BidirectionalIterator, typename _OutputIterator>
1501 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1502 _OutputIterator __result)
1504 // concept requirements
1505 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1506 _BidirectionalIterator>)
1507 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1508 typename iterator_traits<_BidirectionalIterator>::value_type>)
1509 __glibcxx_requires_valid_range(__first, __last);
1511 while (__first != __last)
1514 *__result = *__last;
1521 * This is a helper function for the rotate algorithm specialized on RAIs.
1522 * It returns the greatest common divisor of two integer values.
1524 template<typename _EuclideanRingElement>
1525 _EuclideanRingElement
1526 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1530 _EuclideanRingElement __t = __m % __n;
1537 /// This is a helper function for the rotate algorithm.
1538 template<typename _ForwardIterator>
1540 __rotate(_ForwardIterator __first,
1541 _ForwardIterator __middle,
1542 _ForwardIterator __last,
1543 forward_iterator_tag)
1545 if (__first == __middle || __last == __middle)
1548 _ForwardIterator __first2 = __middle;
1551 std::iter_swap(__first, __first2);
1554 if (__first == __middle)
1555 __middle = __first2;
1557 while (__first2 != __last);
1559 __first2 = __middle;
1561 while (__first2 != __last)
1563 std::iter_swap(__first, __first2);
1566 if (__first == __middle)
1567 __middle = __first2;
1568 else if (__first2 == __last)
1569 __first2 = __middle;
1573 /// This is a helper function for the rotate algorithm.
1574 template<typename _BidirectionalIterator>
1576 __rotate(_BidirectionalIterator __first,
1577 _BidirectionalIterator __middle,
1578 _BidirectionalIterator __last,
1579 bidirectional_iterator_tag)
1581 // concept requirements
1582 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1583 _BidirectionalIterator>)
1585 if (__first == __middle || __last == __middle)
1588 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1589 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1591 while (__first != __middle && __middle != __last)
1593 std::iter_swap(__first, --__last);
1597 if (__first == __middle)
1598 std::__reverse(__middle, __last, bidirectional_iterator_tag());
1600 std::__reverse(__first, __middle, bidirectional_iterator_tag());
1603 /// This is a helper function for the rotate algorithm.
1604 template<typename _RandomAccessIterator>
1606 __rotate(_RandomAccessIterator __first,
1607 _RandomAccessIterator __middle,
1608 _RandomAccessIterator __last,
1609 random_access_iterator_tag)
1611 // concept requirements
1612 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1613 _RandomAccessIterator>)
1615 if (__first == __middle || __last == __middle)
1618 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1620 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1623 _Distance __n = __last - __first;
1624 _Distance __k = __middle - __first;
1626 if (__k == __n - __k)
1628 std::swap_ranges(__first, __middle, __middle);
1632 _RandomAccessIterator __p = __first;
1636 if (__k < __n - __k)
1638 if (__is_pod(_ValueType) && __k == 1)
1640 _ValueType __t = _GLIBCXX_MOVE(*__p);
1641 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1642 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1645 _RandomAccessIterator __q = __p + __k;
1646 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1648 std::iter_swap(__p, __q);
1655 std::swap(__n, __k);
1661 if (__is_pod(_ValueType) && __k == 1)
1663 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1664 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1665 *__p = _GLIBCXX_MOVE(__t);
1668 _RandomAccessIterator __q = __p + __n;
1670 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1674 std::iter_swap(__p, __q);
1679 std::swap(__n, __k);
1685 * @brief Rotate the elements of a sequence.
1686 * @ingroup mutating_algorithms
1687 * @param __first A forward iterator.
1688 * @param __middle A forward iterator.
1689 * @param __last A forward iterator.
1692 * Rotates the elements of the range @p [__first,__last) by
1693 * @p (__middle - __first) positions so that the element at @p __middle
1694 * is moved to @p __first, the element at @p __middle+1 is moved to
1695 * @p __first+1 and so on for each element in the range
1696 * @p [__first,__last).
1698 * This effectively swaps the ranges @p [__first,__middle) and
1699 * @p [__middle,__last).
1702 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1703 * for each @p n in the range @p [0,__last-__first).
1705 template<typename _ForwardIterator>
1707 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1708 _ForwardIterator __last)
1710 // concept requirements
1711 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1713 __glibcxx_requires_valid_range(__first, __middle);
1714 __glibcxx_requires_valid_range(__middle, __last);
1716 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1718 std::__rotate(__first, __middle, __last, _IterType());
1722 * @brief Copy a sequence, rotating its elements.
1723 * @ingroup mutating_algorithms
1724 * @param __first A forward iterator.
1725 * @param __middle A forward iterator.
1726 * @param __last A forward iterator.
1727 * @param __result An output iterator.
1728 * @return An iterator designating the end of the resulting sequence.
1730 * Copies the elements of the range @p [__first,__last) to the
1731 * range beginning at @result, rotating the copied elements by
1732 * @p (__middle-__first) positions so that the element at @p __middle
1733 * is moved to @p __result, the element at @p __middle+1 is moved
1734 * to @p __result+1 and so on for each element in the range @p
1738 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1739 * for each @p n in the range @p [0,__last-__first).
1741 template<typename _ForwardIterator, typename _OutputIterator>
1743 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1744 _ForwardIterator __last, _OutputIterator __result)
1746 // concept requirements
1747 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1748 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1749 typename iterator_traits<_ForwardIterator>::value_type>)
1750 __glibcxx_requires_valid_range(__first, __middle);
1751 __glibcxx_requires_valid_range(__middle, __last);
1753 return std::copy(__first, __middle,
1754 std::copy(__middle, __last, __result));
1757 /// This is a helper function...
1758 template<typename _ForwardIterator, typename _Predicate>
1760 __partition(_ForwardIterator __first, _ForwardIterator __last,
1761 _Predicate __pred, forward_iterator_tag)
1763 if (__first == __last)
1766 while (__pred(*__first))
1767 if (++__first == __last)
1770 _ForwardIterator __next = __first;
1772 while (++__next != __last)
1773 if (__pred(*__next))
1775 std::iter_swap(__first, __next);
1782 /// This is a helper function...
1783 template<typename _BidirectionalIterator, typename _Predicate>
1784 _BidirectionalIterator
1785 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1786 _Predicate __pred, bidirectional_iterator_tag)
1791 if (__first == __last)
1793 else if (__pred(*__first))
1799 if (__first == __last)
1801 else if (!bool(__pred(*__last)))
1805 std::iter_swap(__first, __last);
1812 /// This is a helper function...
1813 /// Requires __len != 0 and !__pred(*__first),
1814 /// same as __stable_partition_adaptive.
1815 template<typename _ForwardIterator, typename _Predicate, typename _Distance>
1817 __inplace_stable_partition(_ForwardIterator __first,
1818 _Predicate __pred, _Distance __len)
1822 _ForwardIterator __middle = __first;
1823 std::advance(__middle, __len / 2);
1824 _ForwardIterator __left_split =
1825 std::__inplace_stable_partition(__first, __pred, __len / 2);
1826 // Advance past true-predicate values to satisfy this
1827 // function's preconditions.
1828 _Distance __right_len = __len - __len / 2;
1829 _ForwardIterator __right_split =
1830 std::__find_if_not_n(__middle, __right_len, __pred);
1832 __right_split = std::__inplace_stable_partition(__middle,
1835 std::rotate(__left_split, __middle, __right_split);
1836 std::advance(__left_split, std::distance(__middle, __right_split));
1837 return __left_split;
1840 /// This is a helper function...
1841 /// Requires __first != __last and !__pred(*__first)
1842 /// and __len == distance(__first, __last).
1844 /// !__pred(*__first) allows us to guarantee that we don't
1845 /// move-assign an element onto itself.
1846 template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
1849 __stable_partition_adaptive(_ForwardIterator __first,
1850 _ForwardIterator __last,
1851 _Predicate __pred, _Distance __len,
1853 _Distance __buffer_size)
1855 if (__len <= __buffer_size)
1857 _ForwardIterator __result1 = __first;
1858 _Pointer __result2 = __buffer;
1859 // The precondition guarantees that !__pred(*__first), so
1860 // move that element to the buffer before starting the loop.
1861 // This ensures that we only call __pred once per element.
1862 *__result2 = _GLIBCXX_MOVE(*__first);
1865 for (; __first != __last; ++__first)
1866 if (__pred(*__first))
1868 *__result1 = _GLIBCXX_MOVE(*__first);
1873 *__result2 = _GLIBCXX_MOVE(*__first);
1876 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1881 _ForwardIterator __middle = __first;
1882 std::advance(__middle, __len / 2);
1883 _ForwardIterator __left_split =
1884 std::__stable_partition_adaptive(__first, __middle, __pred,
1885 __len / 2, __buffer,
1887 // Advance past true-predicate values to satisfy this
1888 // function's preconditions.
1889 _Distance __right_len = __len - __len / 2;
1890 _ForwardIterator __right_split =
1891 std::__find_if_not_n(__middle, __right_len, __pred);
1894 std::__stable_partition_adaptive(__right_split, __last, __pred,
1896 __buffer, __buffer_size);
1897 std::rotate(__left_split, __middle, __right_split);
1898 std::advance(__left_split, std::distance(__middle, __right_split));
1899 return __left_split;
1904 * @brief Move elements for which a predicate is true to the beginning
1905 * of a sequence, preserving relative ordering.
1906 * @ingroup mutating_algorithms
1907 * @param __first A forward iterator.
1908 * @param __last A forward iterator.
1909 * @param __pred A predicate functor.
1910 * @return An iterator @p middle such that @p __pred(i) is true for each
1911 * iterator @p i in the range @p [first,middle) and false for each @p i
1912 * in the range @p [middle,last).
1914 * Performs the same function as @p partition() with the additional
1915 * guarantee that the relative ordering of elements in each group is
1916 * preserved, so any two elements @p x and @p y in the range
1917 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1918 * relative ordering after calling @p stable_partition().
1920 template<typename _ForwardIterator, typename _Predicate>
1922 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1925 // concept requirements
1926 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1928 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1929 typename iterator_traits<_ForwardIterator>::value_type>)
1930 __glibcxx_requires_valid_range(__first, __last);
1932 __first = std::__find_if_not(__first, __last, __pred);
1934 if (__first == __last)
1938 typedef typename iterator_traits<_ForwardIterator>::value_type
1940 typedef typename iterator_traits<_ForwardIterator>::difference_type
1943 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first,
1945 if (__buf.size() > 0)
1947 std::__stable_partition_adaptive(__first, __last, __pred,
1948 _DistanceType(__buf.requested_size()),
1950 _DistanceType(__buf.size()));
1953 std::__inplace_stable_partition(__first, __pred,
1954 _DistanceType(__buf.requested_size()));
1958 /// This is a helper function for the sort routines.
1959 template<typename _RandomAccessIterator>
1961 __heap_select(_RandomAccessIterator __first,
1962 _RandomAccessIterator __middle,
1963 _RandomAccessIterator __last)
1965 std::make_heap(__first, __middle);
1966 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1967 if (*__i < *__first)
1968 std::__pop_heap(__first, __middle, __i);
1971 /// This is a helper function for the sort routines.
1972 template<typename _RandomAccessIterator, typename _Compare>
1974 __heap_select(_RandomAccessIterator __first,
1975 _RandomAccessIterator __middle,
1976 _RandomAccessIterator __last, _Compare __comp)
1978 std::make_heap(__first, __middle, __comp);
1979 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1980 if (__comp(*__i, *__first))
1981 std::__pop_heap(__first, __middle, __i, __comp);
1987 * @brief Copy the smallest elements of a sequence.
1988 * @ingroup sorting_algorithms
1989 * @param __first An iterator.
1990 * @param __last Another iterator.
1991 * @param __result_first A random-access iterator.
1992 * @param __result_last Another random-access iterator.
1993 * @return An iterator indicating the end of the resulting sequence.
1995 * Copies and sorts the smallest N values from the range @p [__first,__last)
1996 * to the range beginning at @p __result_first, where the number of
1997 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1998 * @p (__result_last-__result_first).
1999 * After the sort if @e i and @e j are iterators in the range
2000 * @p [__result_first,__result_first+N) such that i precedes j then
2002 * The value returned is @p __result_first+N.
2004 template<typename _InputIterator, typename _RandomAccessIterator>
2005 _RandomAccessIterator
2006 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2007 _RandomAccessIterator __result_first,
2008 _RandomAccessIterator __result_last)
2010 typedef typename iterator_traits<_InputIterator>::value_type
2012 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2014 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2017 // concept requirements
2018 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2019 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2021 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2023 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2024 __glibcxx_requires_valid_range(__first, __last);
2025 __glibcxx_requires_valid_range(__result_first, __result_last);
2027 if (__result_first == __result_last)
2028 return __result_last;
2029 _RandomAccessIterator __result_real_last = __result_first;
2030 while(__first != __last && __result_real_last != __result_last)
2032 *__result_real_last = *__first;
2033 ++__result_real_last;
2036 std::make_heap(__result_first, __result_real_last);
2037 while (__first != __last)
2039 if (*__first < *__result_first)
2040 std::__adjust_heap(__result_first, _DistanceType(0),
2041 _DistanceType(__result_real_last
2043 _InputValueType(*__first));
2046 std::sort_heap(__result_first, __result_real_last);
2047 return __result_real_last;
2051 * @brief Copy the smallest elements of a sequence using a predicate for
2053 * @ingroup sorting_algorithms
2054 * @param __first An input iterator.
2055 * @param __last Another input iterator.
2056 * @param __result_first A random-access iterator.
2057 * @param __result_last Another random-access iterator.
2058 * @param __comp A comparison functor.
2059 * @return An iterator indicating the end of the resulting sequence.
2061 * Copies and sorts the smallest N values from the range @p [__first,__last)
2062 * to the range beginning at @p result_first, where the number of
2063 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
2064 * @p (__result_last-__result_first).
2065 * After the sort if @e i and @e j are iterators in the range
2066 * @p [__result_first,__result_first+N) such that i precedes j then
2067 * @p __comp(*j,*i) is false.
2068 * The value returned is @p __result_first+N.
2070 template<typename _InputIterator, typename _RandomAccessIterator, typename _Compare>
2071 _RandomAccessIterator
2072 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2073 _RandomAccessIterator __result_first,
2074 _RandomAccessIterator __result_last,
2077 typedef typename iterator_traits<_InputIterator>::value_type
2079 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2081 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2084 // concept requirements
2085 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2086 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2087 _RandomAccessIterator>)
2088 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2090 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2091 _InputValueType, _OutputValueType>)
2092 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2093 _OutputValueType, _OutputValueType>)
2094 __glibcxx_requires_valid_range(__first, __last);
2095 __glibcxx_requires_valid_range(__result_first, __result_last);
2097 if (__result_first == __result_last)
2098 return __result_last;
2099 _RandomAccessIterator __result_real_last = __result_first;
2100 while(__first != __last && __result_real_last != __result_last)
2102 *__result_real_last = *__first;
2103 ++__result_real_last;
2106 std::make_heap(__result_first, __result_real_last, __comp);
2107 while (__first != __last)
2109 if (__comp(*__first, *__result_first))
2110 std::__adjust_heap(__result_first, _DistanceType(0),
2111 _DistanceType(__result_real_last
2113 _InputValueType(*__first),
2117 std::sort_heap(__result_first, __result_real_last, __comp);
2118 return __result_real_last;
2121 /// This is a helper function for the sort routine.
2122 template<typename _RandomAccessIterator>
2124 __unguarded_linear_insert(_RandomAccessIterator __last)
2126 typename iterator_traits<_RandomAccessIterator>::value_type
2127 __val = _GLIBCXX_MOVE(*__last);
2128 _RandomAccessIterator __next = __last;
2130 while (__val < *__next)
2132 *__last = _GLIBCXX_MOVE(*__next);
2136 *__last = _GLIBCXX_MOVE(__val);
2139 /// This is a helper function for the sort routine.
2140 template<typename _RandomAccessIterator, typename _Compare>
2142 __unguarded_linear_insert(_RandomAccessIterator __last,
2145 typename iterator_traits<_RandomAccessIterator>::value_type
2146 __val = _GLIBCXX_MOVE(*__last);
2147 _RandomAccessIterator __next = __last;
2149 while (__comp(__val, *__next))
2151 *__last = _GLIBCXX_MOVE(*__next);
2155 *__last = _GLIBCXX_MOVE(__val);
2158 /// This is a helper function for the sort routine.
2159 template<typename _RandomAccessIterator>
2161 __insertion_sort(_RandomAccessIterator __first,
2162 _RandomAccessIterator __last)
2164 if (__first == __last)
2167 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2169 if (*__i < *__first)
2171 typename iterator_traits<_RandomAccessIterator>::value_type
2172 __val = _GLIBCXX_MOVE(*__i);
2173 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2174 *__first = _GLIBCXX_MOVE(__val);
2177 std::__unguarded_linear_insert(__i);
2181 /// This is a helper function for the sort routine.
2182 template<typename _RandomAccessIterator, typename _Compare>
2184 __insertion_sort(_RandomAccessIterator __first,
2185 _RandomAccessIterator __last, _Compare __comp)
2187 if (__first == __last) return;
2189 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2191 if (__comp(*__i, *__first))
2193 typename iterator_traits<_RandomAccessIterator>::value_type
2194 __val = _GLIBCXX_MOVE(*__i);
2195 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2196 *__first = _GLIBCXX_MOVE(__val);
2199 std::__unguarded_linear_insert(__i, __comp);
2203 /// This is a helper function for the sort routine.
2204 template<typename _RandomAccessIterator>
2206 __unguarded_insertion_sort(_RandomAccessIterator __first,
2207 _RandomAccessIterator __last)
2209 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2212 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2213 std::__unguarded_linear_insert(__i);
2216 /// This is a helper function for the sort routine.
2217 template<typename _RandomAccessIterator, typename _Compare>
2219 __unguarded_insertion_sort(_RandomAccessIterator __first,
2220 _RandomAccessIterator __last, _Compare __comp)
2222 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2225 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2226 std::__unguarded_linear_insert(__i, __comp);
2231 * This controls some aspect of the sort routines.
2233 enum { _S_threshold = 16 };
2235 /// This is a helper function for the sort routine.
2236 template<typename _RandomAccessIterator>
2238 __final_insertion_sort(_RandomAccessIterator __first,
2239 _RandomAccessIterator __last)
2241 if (__last - __first > int(_S_threshold))
2243 std::__insertion_sort(__first, __first + int(_S_threshold));
2244 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last);
2247 std::__insertion_sort(__first, __last);
2250 /// This is a helper function for the sort routine.
2251 template<typename _RandomAccessIterator, typename _Compare>
2253 __final_insertion_sort(_RandomAccessIterator __first,
2254 _RandomAccessIterator __last, _Compare __comp)
2256 if (__last - __first > int(_S_threshold))
2258 std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
2259 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last,
2263 std::__insertion_sort(__first, __last, __comp);
2266 /// This is a helper function...
2267 template<typename _RandomAccessIterator, typename _Tp>
2268 _RandomAccessIterator
2269 __unguarded_partition(_RandomAccessIterator __first,
2270 _RandomAccessIterator __last, const _Tp& __pivot)
2274 while (*__first < __pivot)
2277 while (__pivot < *__last)
2279 if (!(__first < __last))
2281 std::iter_swap(__first, __last);
2286 /// This is a helper function...
2287 template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
2288 _RandomAccessIterator
2289 __unguarded_partition(_RandomAccessIterator __first,
2290 _RandomAccessIterator __last,
2291 const _Tp& __pivot, _Compare __comp)
2295 while (__comp(*__first, __pivot))
2298 while (__comp(__pivot, *__last))
2300 if (!(__first < __last))
2302 std::iter_swap(__first, __last);
2307 /// This is a helper function...
2308 template<typename _RandomAccessIterator>
2309 inline _RandomAccessIterator
2310 __unguarded_partition_pivot(_RandomAccessIterator __first,
2311 _RandomAccessIterator __last)
2313 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2314 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1);
2315 return std::__unguarded_partition(__first + 1, __last, *__first);
2319 /// This is a helper function...
2320 template<typename _RandomAccessIterator, typename _Compare>
2321 inline _RandomAccessIterator
2322 __unguarded_partition_pivot(_RandomAccessIterator __first,
2323 _RandomAccessIterator __last, _Compare __comp)
2325 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2326 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
2328 return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
2331 /// This is a helper function for the sort routine.
2332 template<typename _RandomAccessIterator, typename _Size>
2334 __introsort_loop(_RandomAccessIterator __first,
2335 _RandomAccessIterator __last,
2336 _Size __depth_limit)
2338 while (__last - __first > int(_S_threshold))
2340 if (__depth_limit == 0)
2342 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2346 _RandomAccessIterator __cut =
2347 std::__unguarded_partition_pivot(__first, __last);
2348 std::__introsort_loop(__cut, __last, __depth_limit);
2353 /// This is a helper function for the sort routine.
2354 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2356 __introsort_loop(_RandomAccessIterator __first,
2357 _RandomAccessIterator __last,
2358 _Size __depth_limit, _Compare __comp)
2360 while (__last - __first > int(_S_threshold))
2362 if (__depth_limit == 0)
2364 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2368 _RandomAccessIterator __cut =
2369 std::__unguarded_partition_pivot(__first, __last, __comp);
2370 std::__introsort_loop(__cut, __last, __depth_limit, __comp);
2377 template<typename _RandomAccessIterator, typename _Size>
2379 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2380 _RandomAccessIterator __last, _Size __depth_limit)
2382 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2385 while (__last - __first > 3)
2387 if (__depth_limit == 0)
2389 std::__heap_select(__first, __nth + 1, __last);
2391 // Place the nth largest element in its final position.
2392 std::iter_swap(__first, __nth);
2396 _RandomAccessIterator __cut =
2397 std::__unguarded_partition_pivot(__first, __last);
2403 std::__insertion_sort(__first, __last);
2406 template<typename _RandomAccessIterator, typename _Size, typename _Compare>
2408 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2409 _RandomAccessIterator __last, _Size __depth_limit,
2412 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2415 while (__last - __first > 3)
2417 if (__depth_limit == 0)
2419 std::__heap_select(__first, __nth + 1, __last, __comp);
2420 // Place the nth largest element in its final position.
2421 std::iter_swap(__first, __nth);
2425 _RandomAccessIterator __cut =
2426 std::__unguarded_partition_pivot(__first, __last, __comp);
2432 std::__insertion_sort(__first, __last, __comp);
2437 // lower_bound moved to stl_algobase.h
2440 * @brief Finds the first position in which @p __val could be inserted
2441 * without changing the ordering.
2442 * @ingroup binary_search_algorithms
2443 * @param __first An iterator.
2444 * @param __last Another iterator.
2445 * @param __val The search term.
2446 * @param __comp A functor to use for comparisons.
2447 * @return An iterator pointing to the first element <em>not less
2448 * than</em> @p __val, or end() if every element is less
2450 * @ingroup binary_search_algorithms
2452 * The comparison function should have the same effects on ordering as
2453 * the function used for the initial sort.
2455 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2457 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2458 const _Tp& __val, _Compare __comp)
2460 typedef typename iterator_traits<_ForwardIterator>::value_type
2462 typedef typename iterator_traits<_ForwardIterator>::difference_type
2465 // concept requirements
2466 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2467 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2469 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2472 _DistanceType __len = std::distance(__first, __last);
2476 _DistanceType __half = __len >> 1;
2477 _ForwardIterator __middle = __first;
2478 std::advance(__middle, __half);
2479 if (__comp(*__middle, __val))
2483 __len = __len - __half - 1;
2492 * @brief Finds the last position in which @p __val could be inserted
2493 * without changing the ordering.
2494 * @ingroup binary_search_algorithms
2495 * @param __first An iterator.
2496 * @param __last Another iterator.
2497 * @param __val The search term.
2498 * @return An iterator pointing to the first element greater than @p __val,
2499 * or end() if no elements are greater than @p __val.
2500 * @ingroup binary_search_algorithms
2502 template<typename _ForwardIterator, typename _Tp>
2504 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2507 typedef typename iterator_traits<_ForwardIterator>::value_type
2509 typedef typename iterator_traits<_ForwardIterator>::difference_type
2512 // concept requirements
2513 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2514 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2515 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2517 _DistanceType __len = std::distance(__first, __last);
2521 _DistanceType __half = __len >> 1;
2522 _ForwardIterator __middle = __first;
2523 std::advance(__middle, __half);
2524 if (__val < *__middle)
2530 __len = __len - __half - 1;
2537 * @brief Finds the last position in which @p __val could be inserted
2538 * without changing the ordering.
2539 * @ingroup binary_search_algorithms
2540 * @param __first An iterator.
2541 * @param __last Another iterator.
2542 * @param __val The search term.
2543 * @param __comp A functor to use for comparisons.
2544 * @return An iterator pointing to the first element greater than @p __val,
2545 * or end() if no elements are greater than @p __val.
2546 * @ingroup binary_search_algorithms
2548 * The comparison function should have the same effects on ordering as
2549 * the function used for the initial sort.
2551 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2553 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2554 const _Tp& __val, _Compare __comp)
2556 typedef typename iterator_traits<_ForwardIterator>::value_type
2558 typedef typename iterator_traits<_ForwardIterator>::difference_type
2561 // concept requirements
2562 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2563 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2565 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2568 _DistanceType __len = std::distance(__first, __last);
2572 _DistanceType __half = __len >> 1;
2573 _ForwardIterator __middle = __first;
2574 std::advance(__middle, __half);
2575 if (__comp(__val, *__middle))
2581 __len = __len - __half - 1;
2588 * @brief Finds the largest subrange in which @p __val could be inserted
2589 * at any place in it without changing the ordering.
2590 * @ingroup binary_search_algorithms
2591 * @param __first An iterator.
2592 * @param __last Another iterator.
2593 * @param __val The search term.
2594 * @return An pair of iterators defining the subrange.
2595 * @ingroup binary_search_algorithms
2597 * This is equivalent to
2599 * std::make_pair(lower_bound(__first, __last, __val),
2600 * upper_bound(__first, __last, __val))
2602 * but does not actually call those functions.
2604 template<typename _ForwardIterator, typename _Tp>
2605 pair<_ForwardIterator, _ForwardIterator>
2606 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2609 typedef typename iterator_traits<_ForwardIterator>::value_type
2611 typedef typename iterator_traits<_ForwardIterator>::difference_type
2614 // concept requirements
2615 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2616 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2617 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2618 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2619 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2621 _DistanceType __len = std::distance(__first, __last);
2625 _DistanceType __half = __len >> 1;
2626 _ForwardIterator __middle = __first;
2627 std::advance(__middle, __half);
2628 if (*__middle < __val)
2632 __len = __len - __half - 1;
2634 else if (__val < *__middle)
2638 _ForwardIterator __left = std::lower_bound(__first, __middle,
2640 std::advance(__first, __len);
2641 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2643 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2646 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2650 * @brief Finds the largest subrange in which @p __val could be inserted
2651 * at any place in it without changing the ordering.
2652 * @param __first An iterator.
2653 * @param __last Another iterator.
2654 * @param __val The search term.
2655 * @param __comp A functor to use for comparisons.
2656 * @return An pair of iterators defining the subrange.
2657 * @ingroup binary_search_algorithms
2659 * This is equivalent to
2661 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2662 * upper_bound(__first, __last, __val, __comp))
2664 * but does not actually call those functions.
2666 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2667 pair<_ForwardIterator, _ForwardIterator>
2668 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2669 const _Tp& __val, _Compare __comp)
2671 typedef typename iterator_traits<_ForwardIterator>::value_type
2673 typedef typename iterator_traits<_ForwardIterator>::difference_type
2676 // concept requirements
2677 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2678 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2680 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2682 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2684 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2687 _DistanceType __len = std::distance(__first, __last);
2691 _DistanceType __half = __len >> 1;
2692 _ForwardIterator __middle = __first;
2693 std::advance(__middle, __half);
2694 if (__comp(*__middle, __val))
2698 __len = __len - __half - 1;
2700 else if (__comp(__val, *__middle))
2704 _ForwardIterator __left = std::lower_bound(__first, __middle,
2706 std::advance(__first, __len);
2707 _ForwardIterator __right = std::upper_bound(++__middle, __first,
2709 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2712 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2716 * @brief Determines whether an element exists in a range.
2717 * @ingroup binary_search_algorithms
2718 * @param __first An iterator.
2719 * @param __last Another iterator.
2720 * @param __val The search term.
2721 * @return True if @p __val (or its equivalent) is in [@p
2722 * __first,@p __last ].
2724 * Note that this does not actually return an iterator to @p __val. For
2725 * that, use std::find or a container's specialized find member functions.
2727 template<typename _ForwardIterator, typename _Tp>
2729 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2732 typedef typename iterator_traits<_ForwardIterator>::value_type
2735 // concept requirements
2736 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2737 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2738 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2739 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2741 _ForwardIterator __i = std::lower_bound(__first, __last, __val);
2742 return __i != __last && !(__val < *__i);
2746 * @brief Determines whether an element exists in a range.
2747 * @ingroup binary_search_algorithms
2748 * @param __first An iterator.
2749 * @param __last Another iterator.
2750 * @param __val The search term.
2751 * @param __comp A functor to use for comparisons.
2752 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2754 * Note that this does not actually return an iterator to @p __val. For
2755 * that, use std::find or a container's specialized find member functions.
2757 * The comparison function should have the same effects on ordering as
2758 * the function used for the initial sort.
2760 template<typename _ForwardIterator, typename _Tp, typename _Compare>
2762 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2763 const _Tp& __val, _Compare __comp)
2765 typedef typename iterator_traits<_ForwardIterator>::value_type
2768 // concept requirements
2769 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2770 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2772 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2774 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2777 _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
2778 return __i != __last && !bool(__comp(__val, *__i));
2783 /// This is a helper function for the __merge_adaptive routines.
2784 template<typename _InputIterator1, typename _InputIterator2,
2785 typename _OutputIterator>
2787 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2788 _InputIterator2 __first2, _InputIterator2 __last2,
2789 _OutputIterator __result)
2791 while (__first1 != __last1 && __first2 != __last2)
2793 if (*__first2 < *__first1)
2795 *__result = _GLIBCXX_MOVE(*__first2);
2800 *__result = _GLIBCXX_MOVE(*__first1);
2805 if (__first1 != __last1)
2806 _GLIBCXX_MOVE3(__first1, __last1, __result);
2809 /// This is a helper function for the __merge_adaptive routines.
2810 template<typename _InputIterator1, typename _InputIterator2,
2811 typename _OutputIterator, typename _Compare>
2813 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1,
2814 _InputIterator2 __first2, _InputIterator2 __last2,
2815 _OutputIterator __result, _Compare __comp)
2817 while (__first1 != __last1 && __first2 != __last2)
2819 if (__comp(*__first2, *__first1))
2821 *__result = _GLIBCXX_MOVE(*__first2);
2826 *__result = _GLIBCXX_MOVE(*__first1);
2831 if (__first1 != __last1)
2832 _GLIBCXX_MOVE3(__first1, __last1, __result);
2835 /// This is a helper function for the __merge_adaptive routines.
2836 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2837 typename _BidirectionalIterator3>
2839 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2840 _BidirectionalIterator1 __last1,
2841 _BidirectionalIterator2 __first2,
2842 _BidirectionalIterator2 __last2,
2843 _BidirectionalIterator3 __result)
2845 if (__first1 == __last1)
2847 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2850 else if (__first2 == __last2)
2857 if (*__last2 < *__last1)
2859 *--__result = _GLIBCXX_MOVE(*__last1);
2860 if (__first1 == __last1)
2862 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2869 *--__result = _GLIBCXX_MOVE(*__last2);
2870 if (__first2 == __last2)
2877 /// This is a helper function for the __merge_adaptive routines.
2878 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2879 typename _BidirectionalIterator3, typename _Compare>
2881 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1,
2882 _BidirectionalIterator1 __last1,
2883 _BidirectionalIterator2 __first2,
2884 _BidirectionalIterator2 __last2,
2885 _BidirectionalIterator3 __result,
2888 if (__first1 == __last1)
2890 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2893 else if (__first2 == __last2)
2900 if (__comp(*__last2, *__last1))
2902 *--__result = _GLIBCXX_MOVE(*__last1);
2903 if (__first1 == __last1)
2905 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2912 *--__result = _GLIBCXX_MOVE(*__last2);
2913 if (__first2 == __last2)
2920 /// This is a helper function for the merge routines.
2921 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
2923 _BidirectionalIterator1
2924 __rotate_adaptive(_BidirectionalIterator1 __first,
2925 _BidirectionalIterator1 __middle,
2926 _BidirectionalIterator1 __last,
2927 _Distance __len1, _Distance __len2,
2928 _BidirectionalIterator2 __buffer,
2929 _Distance __buffer_size)
2931 _BidirectionalIterator2 __buffer_end;
2932 if (__len1 > __len2 && __len2 <= __buffer_size)
2936 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2937 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2938 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2943 else if (__len1 <= __buffer_size)
2947 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2948 _GLIBCXX_MOVE3(__middle, __last, __first);
2949 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2956 std::rotate(__first, __middle, __last);
2957 std::advance(__first, std::distance(__middle, __last));
2962 /// This is a helper function for the merge routines.
2963 template<typename _BidirectionalIterator, typename _Distance,
2966 __merge_adaptive(_BidirectionalIterator __first,
2967 _BidirectionalIterator __middle,
2968 _BidirectionalIterator __last,
2969 _Distance __len1, _Distance __len2,
2970 _Pointer __buffer, _Distance __buffer_size)
2972 if (__len1 <= __len2 && __len1 <= __buffer_size)
2974 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2975 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
2978 else if (__len2 <= __buffer_size)
2980 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2981 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
2982 __buffer_end, __last);
2986 _BidirectionalIterator __first_cut = __first;
2987 _BidirectionalIterator __second_cut = __middle;
2988 _Distance __len11 = 0;
2989 _Distance __len22 = 0;
2990 if (__len1 > __len2)
2992 __len11 = __len1 / 2;
2993 std::advance(__first_cut, __len11);
2994 __second_cut = std::lower_bound(__middle, __last,
2996 __len22 = std::distance(__middle, __second_cut);
3000 __len22 = __len2 / 2;
3001 std::advance(__second_cut, __len22);
3002 __first_cut = std::upper_bound(__first, __middle,
3004 __len11 = std::distance(__first, __first_cut);
3006 _BidirectionalIterator __new_middle =
3007 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3008 __len1 - __len11, __len22, __buffer,
3010 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3011 __len22, __buffer, __buffer_size);
3012 std::__merge_adaptive(__new_middle, __second_cut, __last,
3014 __len2 - __len22, __buffer, __buffer_size);
3018 /// This is a helper function for the merge routines.
3019 template<typename _BidirectionalIterator, typename _Distance,
3020 typename _Pointer, typename _Compare>
3022 __merge_adaptive(_BidirectionalIterator __first,
3023 _BidirectionalIterator __middle,
3024 _BidirectionalIterator __last,
3025 _Distance __len1, _Distance __len2,
3026 _Pointer __buffer, _Distance __buffer_size,
3029 if (__len1 <= __len2 && __len1 <= __buffer_size)
3031 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3032 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
3035 else if (__len2 <= __buffer_size)
3037 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
3038 std::__move_merge_adaptive_backward(__first, __middle, __buffer,
3039 __buffer_end, __last, __comp);
3043 _BidirectionalIterator __first_cut = __first;
3044 _BidirectionalIterator __second_cut = __middle;
3045 _Distance __len11 = 0;
3046 _Distance __len22 = 0;
3047 if (__len1 > __len2)
3049 __len11 = __len1 / 2;
3050 std::advance(__first_cut, __len11);
3051 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3053 __len22 = std::distance(__middle, __second_cut);
3057 __len22 = __len2 / 2;
3058 std::advance(__second_cut, __len22);
3059 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3061 __len11 = std::distance(__first, __first_cut);
3063 _BidirectionalIterator __new_middle =
3064 std::__rotate_adaptive(__first_cut, __middle, __second_cut,
3065 __len1 - __len11, __len22, __buffer,
3067 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
3068 __len22, __buffer, __buffer_size, __comp);
3069 std::__merge_adaptive(__new_middle, __second_cut, __last,
3071 __len2 - __len22, __buffer,
3072 __buffer_size, __comp);
3076 /// This is a helper function for the merge routines.
3077 template<typename _BidirectionalIterator, typename _Distance>
3079 __merge_without_buffer(_BidirectionalIterator __first,
3080 _BidirectionalIterator __middle,
3081 _BidirectionalIterator __last,
3082 _Distance __len1, _Distance __len2)
3084 if (__len1 == 0 || __len2 == 0)
3086 if (__len1 + __len2 == 2)
3088 if (*__middle < *__first)
3089 std::iter_swap(__first, __middle);
3092 _BidirectionalIterator __first_cut = __first;
3093 _BidirectionalIterator __second_cut = __middle;
3094 _Distance __len11 = 0;
3095 _Distance __len22 = 0;
3096 if (__len1 > __len2)
3098 __len11 = __len1 / 2;
3099 std::advance(__first_cut, __len11);
3100 __second_cut = std::lower_bound(__middle, __last, *__first_cut);
3101 __len22 = std::distance(__middle, __second_cut);
3105 __len22 = __len2 / 2;
3106 std::advance(__second_cut, __len22);
3107 __first_cut = std::upper_bound(__first, __middle, *__second_cut);
3108 __len11 = std::distance(__first, __first_cut);
3110 std::rotate(__first_cut, __middle, __second_cut);
3111 _BidirectionalIterator __new_middle = __first_cut;
3112 std::advance(__new_middle, std::distance(__middle, __second_cut));
3113 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3115 std::__merge_without_buffer(__new_middle, __second_cut, __last,
3116 __len1 - __len11, __len2 - __len22);
3119 /// This is a helper function for the merge routines.
3120 template<typename _BidirectionalIterator, typename _Distance,
3123 __merge_without_buffer(_BidirectionalIterator __first,
3124 _BidirectionalIterator __middle,
3125 _BidirectionalIterator __last,
3126 _Distance __len1, _Distance __len2,
3129 if (__len1 == 0 || __len2 == 0)
3131 if (__len1 + __len2 == 2)
3133 if (__comp(*__middle, *__first))
3134 std::iter_swap(__first, __middle);
3137 _BidirectionalIterator __first_cut = __first;
3138 _BidirectionalIterator __second_cut = __middle;
3139 _Distance __len11 = 0;
3140 _Distance __len22 = 0;
3141 if (__len1 > __len2)
3143 __len11 = __len1 / 2;
3144 std::advance(__first_cut, __len11);
3145 __second_cut = std::lower_bound(__middle, __last, *__first_cut,
3147 __len22 = std::distance(__middle, __second_cut);
3151 __len22 = __len2 / 2;
3152 std::advance(__second_cut, __len22);
3153 __first_cut = std::upper_bound(__first, __middle, *__second_cut,
3155 __len11 = std::distance(__first, __first_cut);
3157 std::rotate(__first_cut, __middle, __second_cut);
3158 _BidirectionalIterator __new_middle = __first_cut;
3159 std::advance(__new_middle, std::distance(__middle, __second_cut));
3160 std::__merge_without_buffer(__first, __first_cut, __new_middle,
3161 __len11, __len22, __comp);
3162 std::__merge_without_buffer(__new_middle, __second_cut, __last,
3163 __len1 - __len11, __len2 - __len22, __comp);
3167 * @brief Merges two sorted ranges in place.
3168 * @ingroup sorting_algorithms
3169 * @param __first An iterator.
3170 * @param __middle Another iterator.
3171 * @param __last Another iterator.
3174 * Merges two sorted and consecutive ranges, [__first,__middle) and
3175 * [__middle,__last), and puts the result in [__first,__last). The
3176 * output will be sorted. The sort is @e stable, that is, for
3177 * equivalent elements in the two ranges, elements from the first
3178 * range will always come before elements from the second.
3180 * If enough additional memory is available, this takes (__last-__first)-1
3181 * comparisons. Otherwise an NlogN algorithm is used, where N is
3182 * distance(__first,__last).
3184 template<typename _BidirectionalIterator>
3186 inplace_merge(_BidirectionalIterator __first,
3187 _BidirectionalIterator __middle,
3188 _BidirectionalIterator __last)
3190 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3192 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3195 // concept requirements
3196 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3197 _BidirectionalIterator>)
3198 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3199 __glibcxx_requires_sorted(__first, __middle);
3200 __glibcxx_requires_sorted(__middle, __last);
3202 if (__first == __middle || __middle == __last)
3205 _DistanceType __len1 = std::distance(__first, __middle);
3206 _DistanceType __len2 = std::distance(__middle, __last);
3208 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3210 if (__buf.begin() == 0)
3211 std::__merge_without_buffer(__first, __middle, __last, __len1, __len2);
3213 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3214 __buf.begin(), _DistanceType(__buf.size()));
3218 * @brief Merges two sorted ranges in place.
3219 * @ingroup sorting_algorithms
3220 * @param __first An iterator.
3221 * @param __middle Another iterator.
3222 * @param __last Another iterator.
3223 * @param __comp A functor to use for comparisons.
3226 * Merges two sorted and consecutive ranges, [__first,__middle) and
3227 * [middle,last), and puts the result in [__first,__last). The output will
3228 * be sorted. The sort is @e stable, that is, for equivalent
3229 * elements in the two ranges, elements from the first range will always
3230 * come before elements from the second.
3232 * If enough additional memory is available, this takes (__last-__first)-1
3233 * comparisons. Otherwise an NlogN algorithm is used, where N is
3234 * distance(__first,__last).
3236 * The comparison function should have the same effects on ordering as
3237 * the function used for the initial sort.
3239 template<typename _BidirectionalIterator, typename _Compare>
3241 inplace_merge(_BidirectionalIterator __first,
3242 _BidirectionalIterator __middle,
3243 _BidirectionalIterator __last,
3246 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3248 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3251 // concept requirements
3252 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3253 _BidirectionalIterator>)
3254 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3255 _ValueType, _ValueType>)
3256 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3257 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3259 if (__first == __middle || __middle == __last)
3262 const _DistanceType __len1 = std::distance(__first, __middle);
3263 const _DistanceType __len2 = std::distance(__middle, __last);
3265 _Temporary_buffer<_BidirectionalIterator, _ValueType> __buf(__first,
3267 if (__buf.begin() == 0)
3268 std::__merge_without_buffer(__first, __middle, __last, __len1,
3271 std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
3272 __buf.begin(), _DistanceType(__buf.size()),
3277 /// This is a helper function for the __merge_sort_loop routines.
3278 template<typename _InputIterator1, typename _InputIterator2,
3279 typename _OutputIterator>
3281 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3282 _InputIterator2 __first2, _InputIterator2 __last2,
3283 _OutputIterator __result)
3285 while (__first1 != __last1 && __first2 != __last2)
3287 if (*__first2 < *__first1)
3289 *__result = _GLIBCXX_MOVE(*__first2);
3294 *__result = _GLIBCXX_MOVE(*__first1);
3299 return _GLIBCXX_MOVE3(__first2, __last2,
3300 _GLIBCXX_MOVE3(__first1, __last1,
3304 /// This is a helper function for the __merge_sort_loop routines.
3305 template<typename _InputIterator1, typename _InputIterator2,
3306 typename _OutputIterator, typename _Compare>
3308 __move_merge(_InputIterator1 __first1, _InputIterator1 __last1,
3309 _InputIterator2 __first2, _InputIterator2 __last2,
3310 _OutputIterator __result, _Compare __comp)
3312 while (__first1 != __last1 && __first2 != __last2)
3314 if (__comp(*__first2, *__first1))
3316 *__result = _GLIBCXX_MOVE(*__first2);
3321 *__result = _GLIBCXX_MOVE(*__first1);
3326 return _GLIBCXX_MOVE3(__first2, __last2,
3327 _GLIBCXX_MOVE3(__first1, __last1,
3331 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3334 __merge_sort_loop(_RandomAccessIterator1 __first,
3335 _RandomAccessIterator1 __last,
3336 _RandomAccessIterator2 __result,
3337 _Distance __step_size)
3339 const _Distance __two_step = 2 * __step_size;
3341 while (__last - __first >= __two_step)
3343 __result = std::__move_merge(__first, __first + __step_size,
3344 __first + __step_size,
3345 __first + __two_step, __result);
3346 __first += __two_step;
3349 __step_size = std::min(_Distance(__last - __first), __step_size);
3350 std::__move_merge(__first, __first + __step_size,
3351 __first + __step_size, __last, __result);
3354 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
3355 typename _Distance, typename _Compare>
3357 __merge_sort_loop(_RandomAccessIterator1 __first,
3358 _RandomAccessIterator1 __last,
3359 _RandomAccessIterator2 __result, _Distance __step_size,
3362 const _Distance __two_step = 2 * __step_size;
3364 while (__last - __first >= __two_step)
3366 __result = std::__move_merge(__first, __first + __step_size,
3367 __first + __step_size,
3368 __first + __two_step,
3370 __first += __two_step;
3372 __step_size = std::min(_Distance(__last - __first), __step_size);
3374 std::__move_merge(__first,__first + __step_size,
3375 __first + __step_size, __last, __result, __comp);
3378 template<typename _RandomAccessIterator, typename _Distance>
3380 __chunk_insertion_sort(_RandomAccessIterator __first,
3381 _RandomAccessIterator __last,
3382 _Distance __chunk_size)
3384 while (__last - __first >= __chunk_size)
3386 std::__insertion_sort(__first, __first + __chunk_size);
3387 __first += __chunk_size;
3389 std::__insertion_sort(__first, __last);
3392 template<typename _RandomAccessIterator, typename _Distance,
3395 __chunk_insertion_sort(_RandomAccessIterator __first,
3396 _RandomAccessIterator __last,
3397 _Distance __chunk_size, _Compare __comp)
3399 while (__last - __first >= __chunk_size)
3401 std::__insertion_sort(__first, __first + __chunk_size, __comp);
3402 __first += __chunk_size;
3404 std::__insertion_sort(__first, __last, __comp);
3407 enum { _S_chunk_size = 7 };
3409 template<typename _RandomAccessIterator, typename _Pointer>
3411 __merge_sort_with_buffer(_RandomAccessIterator __first,
3412 _RandomAccessIterator __last,
3415 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3418 const _Distance __len = __last - __first;
3419 const _Pointer __buffer_last = __buffer + __len;
3421 _Distance __step_size = _S_chunk_size;
3422 std::__chunk_insertion_sort(__first, __last, __step_size);
3424 while (__step_size < __len)
3426 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3428 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3433 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare>
3435 __merge_sort_with_buffer(_RandomAccessIterator __first,
3436 _RandomAccessIterator __last,
3437 _Pointer __buffer, _Compare __comp)
3439 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3442 const _Distance __len = __last - __first;
3443 const _Pointer __buffer_last = __buffer + __len;
3445 _Distance __step_size = _S_chunk_size;
3446 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3448 while (__step_size < __len)
3450 std::__merge_sort_loop(__first, __last, __buffer,
3451 __step_size, __comp);
3453 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3454 __step_size, __comp);
3459 template<typename _RandomAccessIterator, typename _Pointer,
3462 __stable_sort_adaptive(_RandomAccessIterator __first,
3463 _RandomAccessIterator __last,
3464 _Pointer __buffer, _Distance __buffer_size)
3466 const _Distance __len = (__last - __first + 1) / 2;
3467 const _RandomAccessIterator __middle = __first + __len;
3468 if (__len > __buffer_size)
3470 std::__stable_sort_adaptive(__first, __middle,
3471 __buffer, __buffer_size);
3472 std::__stable_sort_adaptive(__middle, __last,
3473 __buffer, __buffer_size);
3477 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3478 std::__merge_sort_with_buffer(__middle, __last, __buffer);
3480 std::__merge_adaptive(__first, __middle, __last,
3481 _Distance(__middle - __first),
3482 _Distance(__last - __middle),
3483 __buffer, __buffer_size);
3486 template<typename _RandomAccessIterator, typename _Pointer,
3487 typename _Distance, typename _Compare>
3489 __stable_sort_adaptive(_RandomAccessIterator __first,
3490 _RandomAccessIterator __last,
3491 _Pointer __buffer, _Distance __buffer_size,
3494 const _Distance __len = (__last - __first + 1) / 2;
3495 const _RandomAccessIterator __middle = __first + __len;
3496 if (__len > __buffer_size)
3498 std::__stable_sort_adaptive(__first, __middle, __buffer,
3499 __buffer_size, __comp);
3500 std::__stable_sort_adaptive(__middle, __last, __buffer,
3501 __buffer_size, __comp);
3505 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3506 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3508 std::__merge_adaptive(__first, __middle, __last,
3509 _Distance(__middle - __first),
3510 _Distance(__last - __middle),
3511 __buffer, __buffer_size,
3515 /// This is a helper function for the stable sorting routines.
3516 template<typename _RandomAccessIterator>
3518 __inplace_stable_sort(_RandomAccessIterator __first,
3519 _RandomAccessIterator __last)
3521 if (__last - __first < 15)
3523 std::__insertion_sort(__first, __last);
3526 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3527 std::__inplace_stable_sort(__first, __middle);
3528 std::__inplace_stable_sort(__middle, __last);
3529 std::__merge_without_buffer(__first, __middle, __last,
3534 /// This is a helper function for the stable sorting routines.
3535 template<typename _RandomAccessIterator, typename _Compare>
3537 __inplace_stable_sort(_RandomAccessIterator __first,
3538 _RandomAccessIterator __last, _Compare __comp)
3540 if (__last - __first < 15)
3542 std::__insertion_sort(__first, __last, __comp);
3545 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3546 std::__inplace_stable_sort(__first, __middle, __comp);
3547 std::__inplace_stable_sort(__middle, __last, __comp);
3548 std::__merge_without_buffer(__first, __middle, __last,
3556 // Set algorithms: includes, set_union, set_intersection, set_difference,
3557 // set_symmetric_difference. All of these algorithms have the precondition
3558 // that their input ranges are sorted and the postcondition that their output
3559 // ranges are sorted.
3562 * @brief Determines whether all elements of a sequence exists in a range.
3563 * @param __first1 Start of search range.
3564 * @param __last1 End of search range.
3565 * @param __first2 Start of sequence
3566 * @param __last2 End of sequence.
3567 * @return True if each element in [__first2,__last2) is contained in order
3568 * within [__first1,__last1). False otherwise.
3569 * @ingroup set_algorithms
3571 * This operation expects both [__first1,__last1) and
3572 * [__first2,__last2) to be sorted. Searches for the presence of
3573 * each element in [__first2,__last2) within [__first1,__last1).
3574 * The iterators over each range only move forward, so this is a
3575 * linear algorithm. If an element in [__first2,__last2) is not
3576 * found before the search iterator reaches @p __last2, false is
3579 template<typename _InputIterator1, typename _InputIterator2>
3581 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3582 _InputIterator2 __first2, _InputIterator2 __last2)
3584 typedef typename iterator_traits<_InputIterator1>::value_type
3586 typedef typename iterator_traits<_InputIterator2>::value_type
3589 // concept requirements
3590 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3591 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3592 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3593 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3594 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3595 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3597 while (__first1 != __last1 && __first2 != __last2)
3598 if (*__first2 < *__first1)
3600 else if(*__first1 < *__first2)
3603 ++__first1, ++__first2;
3605 return __first2 == __last2;
3609 * @brief Determines whether all elements of a sequence exists in a range
3611 * @ingroup set_algorithms
3612 * @param __first1 Start of search range.
3613 * @param __last1 End of search range.
3614 * @param __first2 Start of sequence
3615 * @param __last2 End of sequence.
3616 * @param __comp Comparison function to use.
3617 * @return True if each element in [__first2,__last2) is contained
3618 * in order within [__first1,__last1) according to comp. False
3619 * otherwise. @ingroup set_algorithms
3621 * This operation expects both [__first1,__last1) and
3622 * [__first2,__last2) to be sorted. Searches for the presence of
3623 * each element in [__first2,__last2) within [__first1,__last1),
3624 * using comp to decide. The iterators over each range only move
3625 * forward, so this is a linear algorithm. If an element in
3626 * [__first2,__last2) is not found before the search iterator
3627 * reaches @p __last2, false is returned.
3629 template<typename _InputIterator1, typename _InputIterator2,
3632 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3633 _InputIterator2 __first2, _InputIterator2 __last2,
3636 typedef typename iterator_traits<_InputIterator1>::value_type
3638 typedef typename iterator_traits<_InputIterator2>::value_type
3641 // concept requirements
3642 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3643 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3644 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3645 _ValueType1, _ValueType2>)
3646 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3647 _ValueType2, _ValueType1>)
3648 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3649 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3651 while (__first1 != __last1 && __first2 != __last2)
3652 if (__comp(*__first2, *__first1))
3654 else if(__comp(*__first1, *__first2))
3657 ++__first1, ++__first2;
3659 return __first2 == __last2;
3668 // set_symmetric_difference
3673 * @brief Permute range into the next @e dictionary ordering.
3674 * @ingroup sorting_algorithms
3675 * @param __first Start of range.
3676 * @param __last End of range.
3677 * @return False if wrapped to first permutation, true otherwise.
3679 * Treats all permutations of the range as a set of @e dictionary sorted
3680 * sequences. Permutes the current sequence into the next one of this set.
3681 * Returns true if there are more sequences to generate. If the sequence
3682 * is the largest of the set, the smallest is generated and false returned.
3684 template<typename _BidirectionalIterator>
3686 next_permutation(_BidirectionalIterator __first,
3687 _BidirectionalIterator __last)
3689 // concept requirements
3690 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3691 _BidirectionalIterator>)
3692 __glibcxx_function_requires(_LessThanComparableConcept<
3693 typename iterator_traits<_BidirectionalIterator>::value_type>)
3694 __glibcxx_requires_valid_range(__first, __last);
3696 if (__first == __last)
3698 _BidirectionalIterator __i = __first;
3707 _BidirectionalIterator __ii = __i;
3711 _BidirectionalIterator __j = __last;
3712 while (!(*__i < *--__j))
3714 std::iter_swap(__i, __j);
3715 std::reverse(__ii, __last);
3720 std::reverse(__first, __last);
3727 * @brief Permute range into the next @e dictionary ordering using
3728 * comparison functor.
3729 * @ingroup sorting_algorithms
3730 * @param __first Start of range.
3731 * @param __last End of range.
3732 * @param __comp A comparison functor.
3733 * @return False if wrapped to first permutation, true otherwise.
3735 * Treats all permutations of the range [__first,__last) as a set of
3736 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3737 * sequence into the next one of this set. Returns true if there are more
3738 * sequences to generate. If the sequence is the largest of the set, the
3739 * smallest is generated and false returned.
3741 template<typename _BidirectionalIterator, typename _Compare>
3743 next_permutation(_BidirectionalIterator __first,
3744 _BidirectionalIterator __last, _Compare __comp)
3746 // concept requirements
3747 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3748 _BidirectionalIterator>)
3749 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3750 typename iterator_traits<_BidirectionalIterator>::value_type,
3751 typename iterator_traits<_BidirectionalIterator>::value_type>)
3752 __glibcxx_requires_valid_range(__first, __last);
3754 if (__first == __last)
3756 _BidirectionalIterator __i = __first;
3765 _BidirectionalIterator __ii = __i;
3767 if (__comp(*__i, *__ii))
3769 _BidirectionalIterator __j = __last;
3770 while (!bool(__comp(*__i, *--__j)))
3772 std::iter_swap(__i, __j);
3773 std::reverse(__ii, __last);
3778 std::reverse(__first, __last);
3785 * @brief Permute range into the previous @e dictionary ordering.
3786 * @ingroup sorting_algorithms
3787 * @param __first Start of range.
3788 * @param __last End of range.
3789 * @return False if wrapped to last permutation, true otherwise.
3791 * Treats all permutations of the range as a set of @e dictionary sorted
3792 * sequences. Permutes the current sequence into the previous one of this
3793 * set. Returns true if there are more sequences to generate. If the
3794 * sequence is the smallest of the set, the largest is generated and false
3797 template<typename _BidirectionalIterator>
3799 prev_permutation(_BidirectionalIterator __first,
3800 _BidirectionalIterator __last)
3802 // concept requirements
3803 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3804 _BidirectionalIterator>)
3805 __glibcxx_function_requires(_LessThanComparableConcept<
3806 typename iterator_traits<_BidirectionalIterator>::value_type>)
3807 __glibcxx_requires_valid_range(__first, __last);
3809 if (__first == __last)
3811 _BidirectionalIterator __i = __first;
3820 _BidirectionalIterator __ii = __i;
3824 _BidirectionalIterator __j = __last;
3825 while (!(*--__j < *__i))
3827 std::iter_swap(__i, __j);
3828 std::reverse(__ii, __last);
3833 std::reverse(__first, __last);
3840 * @brief Permute range into the previous @e dictionary ordering using
3841 * comparison functor.
3842 * @ingroup sorting_algorithms
3843 * @param __first Start of range.
3844 * @param __last End of range.
3845 * @param __comp A comparison functor.
3846 * @return False if wrapped to last permutation, true otherwise.
3848 * Treats all permutations of the range [__first,__last) as a set of
3849 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3850 * sequence into the previous one of this set. Returns true if there are
3851 * more sequences to generate. If the sequence is the smallest of the set,
3852 * the largest is generated and false returned.
3854 template<typename _BidirectionalIterator, typename _Compare>
3856 prev_permutation(_BidirectionalIterator __first,
3857 _BidirectionalIterator __last, _Compare __comp)
3859 // concept requirements
3860 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3861 _BidirectionalIterator>)
3862 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3863 typename iterator_traits<_BidirectionalIterator>::value_type,
3864 typename iterator_traits<_BidirectionalIterator>::value_type>)
3865 __glibcxx_requires_valid_range(__first, __last);
3867 if (__first == __last)
3869 _BidirectionalIterator __i = __first;
3878 _BidirectionalIterator __ii = __i;
3880 if (__comp(*__ii, *__i))
3882 _BidirectionalIterator __j = __last;
3883 while (!bool(__comp(*--__j, *__i)))
3885 std::iter_swap(__i, __j);
3886 std::reverse(__ii, __last);
3891 std::reverse(__first, __last);
3901 * @brief Copy a sequence, replacing each element of one value with another
3903 * @param __first An input iterator.
3904 * @param __last An input iterator.
3905 * @param __result An output iterator.
3906 * @param __old_value The value to be replaced.
3907 * @param __new_value The replacement value.
3908 * @return The end of the output sequence, @p result+(last-first).
3910 * Copies each element in the input range @p [__first,__last) to the
3911 * output range @p [__result,__result+(__last-__first)) replacing elements
3912 * equal to @p __old_value with @p __new_value.
3914 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
3916 replace_copy(_InputIterator __first, _InputIterator __last,
3917 _OutputIterator __result,
3918 const _Tp& __old_value, const _Tp& __new_value)
3920 // concept requirements
3921 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3922 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3923 typename iterator_traits<_InputIterator>::value_type>)
3924 __glibcxx_function_requires(_EqualOpConcept<
3925 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3926 __glibcxx_requires_valid_range(__first, __last);
3928 for (; __first != __last; ++__first, ++__result)
3929 if (*__first == __old_value)
3930 *__result = __new_value;
3932 *__result = *__first;
3937 * @brief Copy a sequence, replacing each value for which a predicate
3938 * returns true with another value.
3939 * @ingroup mutating_algorithms
3940 * @param __first An input iterator.
3941 * @param __last An input iterator.
3942 * @param __result An output iterator.
3943 * @param __pred A predicate.
3944 * @param __new_value The replacement value.
3945 * @return The end of the output sequence, @p __result+(__last-__first).
3947 * Copies each element in the range @p [__first,__last) to the range
3948 * @p [__result,__result+(__last-__first)) replacing elements for which
3949 * @p __pred returns true with @p __new_value.
3951 template<typename _InputIterator, typename _OutputIterator,
3952 typename _Predicate, typename _Tp>
3954 replace_copy_if(_InputIterator __first, _InputIterator __last,
3955 _OutputIterator __result,
3956 _Predicate __pred, const _Tp& __new_value)
3958 // concept requirements
3959 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3960 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3961 typename iterator_traits<_InputIterator>::value_type>)
3962 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3963 typename iterator_traits<_InputIterator>::value_type>)
3964 __glibcxx_requires_valid_range(__first, __last);
3966 for (; __first != __last; ++__first, ++__result)
3967 if (__pred(*__first))
3968 *__result = __new_value;
3970 *__result = *__first;
3974 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3976 * @brief Determines whether the elements of a sequence are sorted.
3977 * @ingroup sorting_algorithms
3978 * @param __first An iterator.
3979 * @param __last Another iterator.
3980 * @return True if the elements are sorted, false otherwise.
3982 template<typename _ForwardIterator>
3984 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3985 { return std::is_sorted_until(__first, __last) == __last; }
3988 * @brief Determines whether the elements of a sequence are sorted
3989 * according to a comparison functor.
3990 * @ingroup sorting_algorithms
3991 * @param __first An iterator.
3992 * @param __last Another iterator.
3993 * @param __comp A comparison functor.
3994 * @return True if the elements are sorted, false otherwise.
3996 template<typename _ForwardIterator, typename _Compare>
3998 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
4000 { return std::is_sorted_until(__first, __last, __comp) == __last; }
4003 * @brief Determines the end of a sorted sequence.
4004 * @ingroup sorting_algorithms
4005 * @param __first An iterator.
4006 * @param __last Another iterator.
4007 * @return An iterator pointing to the last iterator i in [__first, __last)
4008 * for which the range [__first, i) is sorted.
4010 template<typename _ForwardIterator>
4012 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
4014 // concept requirements
4015 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4016 __glibcxx_function_requires(_LessThanComparableConcept<
4017 typename iterator_traits<_ForwardIterator>::value_type>)
4018 __glibcxx_requires_valid_range(__first, __last);
4020 if (__first == __last)
4023 _ForwardIterator __next = __first;
4024 for (++__next; __next != __last; __first = __next, ++__next)
4025 if (*__next < *__first)
4031 * @brief Determines the end of a sorted sequence using comparison functor.
4032 * @ingroup sorting_algorithms
4033 * @param __first An iterator.
4034 * @param __last Another iterator.
4035 * @param __comp A comparison functor.
4036 * @return An iterator pointing to the last iterator i in [__first, __last)
4037 * for which the range [__first, i) is sorted.
4039 template<typename _ForwardIterator, typename _Compare>
4041 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4044 // concept requirements
4045 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4046 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4047 typename iterator_traits<_ForwardIterator>::value_type,
4048 typename iterator_traits<_ForwardIterator>::value_type>)
4049 __glibcxx_requires_valid_range(__first, __last);
4051 if (__first == __last)
4054 _ForwardIterator __next = __first;
4055 for (++__next; __next != __last; __first = __next, ++__next)
4056 if (__comp(*__next, *__first))
4062 * @brief Determines min and max at once as an ordered pair.
4063 * @ingroup sorting_algorithms
4064 * @param __a A thing of arbitrary type.
4065 * @param __b Another thing of arbitrary type.
4066 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4069 template<typename _Tp>
4070 inline pair<const _Tp&, const _Tp&>
4071 minmax(const _Tp& __a, const _Tp& __b)
4073 // concept requirements
4074 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4076 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4077 : pair<const _Tp&, const _Tp&>(__a, __b);
4081 * @brief Determines min and max at once as an ordered pair.
4082 * @ingroup sorting_algorithms
4083 * @param __a A thing of arbitrary type.
4084 * @param __b Another thing of arbitrary type.
4085 * @param __comp A @link comparison_functors comparison functor @endlink.
4086 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4089 template<typename _Tp, typename _Compare>
4090 inline pair<const _Tp&, const _Tp&>
4091 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
4093 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
4094 : pair<const _Tp&, const _Tp&>(__a, __b);
4098 * @brief Return a pair of iterators pointing to the minimum and maximum
4099 * elements in a range.
4100 * @ingroup sorting_algorithms
4101 * @param __first Start of range.
4102 * @param __last End of range.
4103 * @return make_pair(m, M), where m is the first iterator i in
4104 * [__first, __last) such that no other element in the range is
4105 * smaller, and where M is the last iterator i in [__first, __last)
4106 * such that no other element in the range is larger.
4108 template<typename _ForwardIterator>
4109 pair<_ForwardIterator, _ForwardIterator>
4110 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4112 // concept requirements
4113 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4114 __glibcxx_function_requires(_LessThanComparableConcept<
4115 typename iterator_traits<_ForwardIterator>::value_type>)
4116 __glibcxx_requires_valid_range(__first, __last);
4118 _ForwardIterator __next = __first;
4119 if (__first == __last
4120 || ++__next == __last)
4121 return std::make_pair(__first, __first);
4123 _ForwardIterator __min, __max;
4124 if (*__next < *__first)
4138 while (__first != __last)
4141 if (++__next == __last)
4143 if (*__first < *__min)
4145 else if (!(*__first < *__max))
4150 if (*__next < *__first)
4152 if (*__next < *__min)
4154 if (!(*__first < *__max))
4159 if (*__first < *__min)
4161 if (!(*__next < *__max))
4169 return std::make_pair(__min, __max);
4173 * @brief Return a pair of iterators pointing to the minimum and maximum
4174 * elements in a range.
4175 * @ingroup sorting_algorithms
4176 * @param __first Start of range.
4177 * @param __last End of range.
4178 * @param __comp Comparison functor.
4179 * @return make_pair(m, M), where m is the first iterator i in
4180 * [__first, __last) such that no other element in the range is
4181 * smaller, and where M is the last iterator i in [__first, __last)
4182 * such that no other element in the range is larger.
4184 template<typename _ForwardIterator, typename _Compare>
4185 pair<_ForwardIterator, _ForwardIterator>
4186 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4189 // concept requirements
4190 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4191 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4192 typename iterator_traits<_ForwardIterator>::value_type,
4193 typename iterator_traits<_ForwardIterator>::value_type>)
4194 __glibcxx_requires_valid_range(__first, __last);
4196 _ForwardIterator __next = __first;
4197 if (__first == __last
4198 || ++__next == __last)
4199 return std::make_pair(__first, __first);
4201 _ForwardIterator __min, __max;
4202 if (__comp(*__next, *__first))
4216 while (__first != __last)
4219 if (++__next == __last)
4221 if (__comp(*__first, *__min))
4223 else if (!__comp(*__first, *__max))
4228 if (__comp(*__next, *__first))
4230 if (__comp(*__next, *__min))
4232 if (!__comp(*__first, *__max))
4237 if (__comp(*__first, *__min))
4239 if (!__comp(*__next, *__max))
4247 return std::make_pair(__min, __max);
4251 template<typename _Tp>
4253 min(initializer_list<_Tp> __l)
4254 { return *std::min_element(__l.begin(), __l.end()); }
4256 template<typename _Tp, typename _Compare>
4258 min(initializer_list<_Tp> __l, _Compare __comp)
4259 { return *std::min_element(__l.begin(), __l.end(), __comp); }
4261 template<typename _Tp>
4263 max(initializer_list<_Tp> __l)
4264 { return *std::max_element(__l.begin(), __l.end()); }
4266 template<typename _Tp, typename _Compare>
4268 max(initializer_list<_Tp> __l, _Compare __comp)
4269 { return *std::max_element(__l.begin(), __l.end(), __comp); }
4271 template<typename _Tp>
4272 inline pair<_Tp, _Tp>
4273 minmax(initializer_list<_Tp> __l)
4275 pair<const _Tp*, const _Tp*> __p =
4276 std::minmax_element(__l.begin(), __l.end());
4277 return std::make_pair(*__p.first, *__p.second);
4280 template<typename _Tp, typename _Compare>
4281 inline pair<_Tp, _Tp>
4282 minmax(initializer_list<_Tp> __l, _Compare __comp)
4284 pair<const _Tp*, const _Tp*> __p =
4285 std::minmax_element(__l.begin(), __l.end(), __comp);
4286 return std::make_pair(*__p.first, *__p.second);
4290 * @brief Checks whether a permutaion of the second sequence is equal
4291 * to the first sequence.
4292 * @ingroup non_mutating_algorithms
4293 * @param __first1 Start of first range.
4294 * @param __last1 End of first range.
4295 * @param __first2 Start of second range.
4296 * @return true if there exists a permutation of the elements in the range
4297 * [__first2, __first2 + (__last1 - __first1)), beginning with
4298 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
4299 * returns true; otherwise, returns false.
4301 template<typename _ForwardIterator1, typename _ForwardIterator2>
4303 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4304 _ForwardIterator2 __first2)
4306 // Efficiently compare identical prefixes: O(N) if sequences
4307 // have the same elements in the same order.
4308 for (; __first1 != __last1; ++__first1, ++__first2)
4309 if (!(*__first1 == *__first2))
4312 if (__first1 == __last1)
4315 // Establish __last2 assuming equal ranges by iterating over the
4316 // rest of the list.
4317 _ForwardIterator2 __last2 = __first2;
4318 std::advance(__last2, std::distance(__first1, __last1));
4319 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4321 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4322 continue; // We've seen this one before.
4324 auto __matches = std::count(__first2, __last2, *__scan);
4326 || std::count(__scan, __last1, *__scan) != __matches)
4333 * @brief Checks whether a permutation of the second sequence is equal
4334 * to the first sequence.
4335 * @ingroup non_mutating_algorithms
4336 * @param __first1 Start of first range.
4337 * @param __last1 End of first range.
4338 * @param __first2 Start of second range.
4339 * @param __pred A binary predicate.
4340 * @return true if there exists a permutation of the elements in
4341 * the range [__first2, __first2 + (__last1 - __first1)),
4342 * beginning with ForwardIterator2 begin, such that
4343 * equal(__first1, __last1, __begin, __pred) returns true;
4344 * otherwise, returns false.
4346 template<typename _ForwardIterator1, typename _ForwardIterator2,
4347 typename _BinaryPredicate>
4349 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4350 _ForwardIterator2 __first2, _BinaryPredicate __pred)
4352 // Efficiently compare identical prefixes: O(N) if sequences
4353 // have the same elements in the same order.
4354 for (; __first1 != __last1; ++__first1, ++__first2)
4355 if (!bool(__pred(*__first1, *__first2)))
4358 if (__first1 == __last1)
4361 // Establish __last2 assuming equal ranges by iterating over the
4362 // rest of the list.
4363 _ForwardIterator2 __last2 = __first2;
4364 std::advance(__last2, std::distance(__first1, __last1));
4365 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4367 using std::placeholders::_1;
4369 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4370 std::bind(__pred, _1, *__scan)))
4371 continue; // We've seen this one before.
4373 auto __matches = std::count_if(__first2, __last2,
4374 std::bind(__pred, _1, *__scan));
4376 || std::count_if(__scan, __last1,
4377 std::bind(__pred, _1, *__scan)) != __matches)
4383 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4385 * @brief Shuffle the elements of a sequence using a uniform random
4387 * @ingroup mutating_algorithms
4388 * @param __first A forward iterator.
4389 * @param __last A forward iterator.
4390 * @param __g A UniformRandomNumberGenerator (26.5.1.3).
4393 * Reorders the elements in the range @p [__first,__last) using @p __g to
4394 * provide random numbers.
4396 template<typename _RandomAccessIterator,
4397 typename _UniformRandomNumberGenerator>
4399 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4400 _UniformRandomNumberGenerator&& __g)
4402 // concept requirements
4403 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4404 _RandomAccessIterator>)
4405 __glibcxx_requires_valid_range(__first, __last);
4407 if (__first == __last)
4410 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4413 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4414 typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
4415 typedef typename __distr_type::param_type __p_type;
4418 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4419 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4423 #endif // __GXX_EXPERIMENTAL_CXX0X__
4425 _GLIBCXX_END_NAMESPACE_VERSION
4427 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4430 * @brief Apply a function to every element of a sequence.
4431 * @ingroup non_mutating_algorithms
4432 * @param __first An input iterator.
4433 * @param __last An input iterator.
4434 * @param __f A unary function object.
4435 * @return @p __f (std::move(@p __f) in C++0x).
4437 * Applies the function object @p __f to each element in the range
4438 * @p [first,last). @p __f must not modify the order of the sequence.
4439 * If @p __f has a return value it is ignored.
4441 template<typename _InputIterator, typename _Function>
4443 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4445 // concept requirements
4446 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4447 __glibcxx_requires_valid_range(__first, __last);
4448 for (; __first != __last; ++__first)
4450 return _GLIBCXX_MOVE(__f);
4454 * @brief Find the first occurrence of a value in a sequence.
4455 * @ingroup non_mutating_algorithms
4456 * @param __first An input iterator.
4457 * @param __last An input iterator.
4458 * @param __val The value to find.
4459 * @return The first iterator @c i in the range @p [__first,__last)
4460 * such that @c *i == @p __val, or @p __last if no such iterator exists.
4462 template<typename _InputIterator, typename _Tp>
4463 inline _InputIterator
4464 find(_InputIterator __first, _InputIterator __last,
4467 // concept requirements
4468 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4469 __glibcxx_function_requires(_EqualOpConcept<
4470 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4471 __glibcxx_requires_valid_range(__first, __last);
4472 return std::__find(__first, __last, __val,
4473 std::__iterator_category(__first));
4477 * @brief Find the first element in a sequence for which a
4478 * predicate is true.
4479 * @ingroup non_mutating_algorithms
4480 * @param __first An input iterator.
4481 * @param __last An input iterator.
4482 * @param __pred A predicate.
4483 * @return The first iterator @c i in the range @p [__first,__last)
4484 * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
4486 template<typename _InputIterator, typename _Predicate>
4487 inline _InputIterator
4488 find_if(_InputIterator __first, _InputIterator __last,
4491 // concept requirements
4492 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4493 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4494 typename iterator_traits<_InputIterator>::value_type>)
4495 __glibcxx_requires_valid_range(__first, __last);
4496 return std::__find_if(__first, __last, __pred,
4497 std::__iterator_category(__first));
4501 * @brief Find element from a set in a sequence.
4502 * @ingroup non_mutating_algorithms
4503 * @param __first1 Start of range to search.
4504 * @param __last1 End of range to search.
4505 * @param __first2 Start of match candidates.
4506 * @param __last2 End of match candidates.
4507 * @return The first iterator @c i in the range
4508 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
4509 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
4511 * Searches the range @p [__first1,__last1) for an element that is
4512 * equal to some element in the range [__first2,__last2). If
4513 * found, returns an iterator in the range [__first1,__last1),
4514 * otherwise returns @p __last1.
4516 template<typename _InputIterator, typename _ForwardIterator>
4518 find_first_of(_InputIterator __first1, _InputIterator __last1,
4519 _ForwardIterator __first2, _ForwardIterator __last2)
4521 // concept requirements
4522 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4523 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4524 __glibcxx_function_requires(_EqualOpConcept<
4525 typename iterator_traits<_InputIterator>::value_type,
4526 typename iterator_traits<_ForwardIterator>::value_type>)
4527 __glibcxx_requires_valid_range(__first1, __last1);
4528 __glibcxx_requires_valid_range(__first2, __last2);
4530 for (; __first1 != __last1; ++__first1)
4531 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4532 if (*__first1 == *__iter)
4538 * @brief Find element from a set in a sequence using a predicate.
4539 * @ingroup non_mutating_algorithms
4540 * @param __first1 Start of range to search.
4541 * @param __last1 End of range to search.
4542 * @param __first2 Start of match candidates.
4543 * @param __last2 End of match candidates.
4544 * @param __comp Predicate to use.
4545 * @return The first iterator @c i in the range
4546 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
4547 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
4548 * such iterator exists.
4551 * Searches the range @p [__first1,__last1) for an element that is
4552 * equal to some element in the range [__first2,__last2). If
4553 * found, returns an iterator in the range [__first1,__last1),
4554 * otherwise returns @p __last1.
4556 template<typename _InputIterator, typename _ForwardIterator,
4557 typename _BinaryPredicate>
4559 find_first_of(_InputIterator __first1, _InputIterator __last1,
4560 _ForwardIterator __first2, _ForwardIterator __last2,
4561 _BinaryPredicate __comp)
4563 // concept requirements
4564 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4565 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4566 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4567 typename iterator_traits<_InputIterator>::value_type,
4568 typename iterator_traits<_ForwardIterator>::value_type>)
4569 __glibcxx_requires_valid_range(__first1, __last1);
4570 __glibcxx_requires_valid_range(__first2, __last2);
4572 for (; __first1 != __last1; ++__first1)
4573 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4574 if (__comp(*__first1, *__iter))
4580 * @brief Find two adjacent values in a sequence that are equal.
4581 * @ingroup non_mutating_algorithms
4582 * @param __first A forward iterator.
4583 * @param __last A forward iterator.
4584 * @return The first iterator @c i such that @c i and @c i+1 are both
4585 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4586 * or @p __last if no such iterator exists.
4588 template<typename _ForwardIterator>
4590 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4592 // concept requirements
4593 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4594 __glibcxx_function_requires(_EqualityComparableConcept<
4595 typename iterator_traits<_ForwardIterator>::value_type>)
4596 __glibcxx_requires_valid_range(__first, __last);
4597 if (__first == __last)
4599 _ForwardIterator __next = __first;
4600 while(++__next != __last)
4602 if (*__first == *__next)
4610 * @brief Find two adjacent values in a sequence using a predicate.
4611 * @ingroup non_mutating_algorithms
4612 * @param __first A forward iterator.
4613 * @param __last A forward iterator.
4614 * @param __binary_pred A binary predicate.
4615 * @return The first iterator @c i such that @c i and @c i+1 are both
4616 * valid iterators in @p [__first,__last) and such that
4617 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4620 template<typename _ForwardIterator, typename _BinaryPredicate>
4622 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4623 _BinaryPredicate __binary_pred)
4625 // concept requirements
4626 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4627 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4628 typename iterator_traits<_ForwardIterator>::value_type,
4629 typename iterator_traits<_ForwardIterator>::value_type>)
4630 __glibcxx_requires_valid_range(__first, __last);
4631 if (__first == __last)
4633 _ForwardIterator __next = __first;
4634 while(++__next != __last)
4636 if (__binary_pred(*__first, *__next))
4644 * @brief Count the number of copies of a value in a sequence.
4645 * @ingroup non_mutating_algorithms
4646 * @param __first An input iterator.
4647 * @param __last An input iterator.
4648 * @param __value The value to be counted.
4649 * @return The number of iterators @c i in the range @p [__first,__last)
4650 * for which @c *i == @p __value
4652 template<typename _InputIterator, typename _Tp>
4653 typename iterator_traits<_InputIterator>::difference_type
4654 count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
4656 // concept requirements
4657 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4658 __glibcxx_function_requires(_EqualOpConcept<
4659 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4660 __glibcxx_requires_valid_range(__first, __last);
4661 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4662 for (; __first != __last; ++__first)
4663 if (*__first == __value)
4669 * @brief Count the elements of a sequence for which a predicate is true.
4670 * @ingroup non_mutating_algorithms
4671 * @param __first An input iterator.
4672 * @param __last An input iterator.
4673 * @param __pred A predicate.
4674 * @return The number of iterators @c i in the range @p [__first,__last)
4675 * for which @p __pred(*i) is true.
4677 template<typename _InputIterator, typename _Predicate>
4678 typename iterator_traits<_InputIterator>::difference_type
4679 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4681 // concept requirements
4682 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4683 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4684 typename iterator_traits<_InputIterator>::value_type>)
4685 __glibcxx_requires_valid_range(__first, __last);
4686 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4687 for (; __first != __last; ++__first)
4688 if (__pred(*__first))
4694 * @brief Search a sequence for a matching sub-sequence.
4695 * @ingroup non_mutating_algorithms
4696 * @param __first1 A forward iterator.
4697 * @param __last1 A forward iterator.
4698 * @param __first2 A forward iterator.
4699 * @param __last2 A forward iterator.
4700 * @return The first iterator @c i in the range @p
4701 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4702 * *(__first2+N) for each @c N in the range @p
4703 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4705 * Searches the range @p [__first1,__last1) for a sub-sequence that
4706 * compares equal value-by-value with the sequence given by @p
4707 * [__first2,__last2) and returns an iterator to the first element
4708 * of the sub-sequence, or @p __last1 if the sub-sequence is not
4711 * Because the sub-sequence must lie completely within the range @p
4712 * [__first1,__last1) it must start at a position less than @p
4713 * __last1-(__last2-__first2) where @p __last2-__first2 is the
4714 * length of the sub-sequence.
4716 * This means that the returned iterator @c i will be in the range
4717 * @p [__first1,__last1-(__last2-__first2))
4719 template<typename _ForwardIterator1, typename _ForwardIterator2>
4721 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4722 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4724 // concept requirements
4725 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4726 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4727 __glibcxx_function_requires(_EqualOpConcept<
4728 typename iterator_traits<_ForwardIterator1>::value_type,
4729 typename iterator_traits<_ForwardIterator2>::value_type>)
4730 __glibcxx_requires_valid_range(__first1, __last1);
4731 __glibcxx_requires_valid_range(__first2, __last2);
4733 // Test for empty ranges
4734 if (__first1 == __last1 || __first2 == __last2)
4737 // Test for a pattern of length 1.
4738 _ForwardIterator2 __p1(__first2);
4739 if (++__p1 == __last2)
4740 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4743 _ForwardIterator2 __p;
4744 _ForwardIterator1 __current = __first1;
4748 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4749 if (__first1 == __last1)
4753 __current = __first1;
4754 if (++__current == __last1)
4757 while (*__current == *__p)
4759 if (++__p == __last2)
4761 if (++__current == __last1)
4770 * @brief Search a sequence for a matching sub-sequence using a predicate.
4771 * @ingroup non_mutating_algorithms
4772 * @param __first1 A forward iterator.
4773 * @param __last1 A forward iterator.
4774 * @param __first2 A forward iterator.
4775 * @param __last2 A forward iterator.
4776 * @param __predicate A binary predicate.
4777 * @return The first iterator @c i in the range
4778 * @p [__first1,__last1-(__last2-__first2)) such that
4779 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4780 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4782 * Searches the range @p [__first1,__last1) for a sub-sequence that
4783 * compares equal value-by-value with the sequence given by @p
4784 * [__first2,__last2), using @p __predicate to determine equality,
4785 * and returns an iterator to the first element of the
4786 * sub-sequence, or @p __last1 if no such iterator exists.
4788 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4790 template<typename _ForwardIterator1, typename _ForwardIterator2,
4791 typename _BinaryPredicate>
4793 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4794 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4795 _BinaryPredicate __predicate)
4797 // concept requirements
4798 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4799 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4800 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4801 typename iterator_traits<_ForwardIterator1>::value_type,
4802 typename iterator_traits<_ForwardIterator2>::value_type>)
4803 __glibcxx_requires_valid_range(__first1, __last1);
4804 __glibcxx_requires_valid_range(__first2, __last2);
4806 // Test for empty ranges
4807 if (__first1 == __last1 || __first2 == __last2)
4810 // Test for a pattern of length 1.
4811 _ForwardIterator2 __p1(__first2);
4812 if (++__p1 == __last2)
4814 while (__first1 != __last1
4815 && !bool(__predicate(*__first1, *__first2)))
4821 _ForwardIterator2 __p;
4822 _ForwardIterator1 __current = __first1;
4826 while (__first1 != __last1
4827 && !bool(__predicate(*__first1, *__first2)))
4829 if (__first1 == __last1)
4833 __current = __first1;
4834 if (++__current == __last1)
4837 while (__predicate(*__current, *__p))
4839 if (++__p == __last2)
4841 if (++__current == __last1)
4851 * @brief Search a sequence for a number of consecutive values.
4852 * @ingroup non_mutating_algorithms
4853 * @param __first A forward iterator.
4854 * @param __last A forward iterator.
4855 * @param __count The number of consecutive values.
4856 * @param __val The value to find.
4857 * @return The first iterator @c i in the range @p
4858 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4859 * each @c N in the range @p [0,__count), or @p __last if no such
4862 * Searches the range @p [__first,__last) for @p count consecutive elements
4863 * equal to @p __val.
4865 template<typename _ForwardIterator, typename _Integer, typename _Tp>
4867 search_n(_ForwardIterator __first, _ForwardIterator __last,
4868 _Integer __count, const _Tp& __val)
4870 // concept requirements
4871 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4872 __glibcxx_function_requires(_EqualOpConcept<
4873 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4874 __glibcxx_requires_valid_range(__first, __last);
4879 return _GLIBCXX_STD_A::find(__first, __last, __val);
4880 return std::__search_n(__first, __last, __count, __val,
4881 std::__iterator_category(__first));
4886 * @brief Search a sequence for a number of consecutive values using a
4888 * @ingroup non_mutating_algorithms
4889 * @param __first A forward iterator.
4890 * @param __last A forward iterator.
4891 * @param __count The number of consecutive values.
4892 * @param __val The value to find.
4893 * @param __binary_pred A binary predicate.
4894 * @return The first iterator @c i in the range @p
4895 * [__first,__last-__count) such that @p
4896 * __binary_pred(*(i+N),__val) is true for each @c N in the range
4897 * @p [0,__count), or @p __last if no such iterator exists.
4899 * Searches the range @p [__first,__last) for @p __count
4900 * consecutive elements for which the predicate returns true.
4902 template<typename _ForwardIterator, typename _Integer, typename _Tp,
4903 typename _BinaryPredicate>
4905 search_n(_ForwardIterator __first, _ForwardIterator __last,
4906 _Integer __count, const _Tp& __val,
4907 _BinaryPredicate __binary_pred)
4909 // concept requirements
4910 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4911 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4912 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4913 __glibcxx_requires_valid_range(__first, __last);
4919 while (__first != __last && !bool(__binary_pred(*__first, __val)))
4923 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4924 std::__iterator_category(__first));
4929 * @brief Perform an operation on a sequence.
4930 * @ingroup mutating_algorithms
4931 * @param __first An input iterator.
4932 * @param __last An input iterator.
4933 * @param __result An output iterator.
4934 * @param __unary_op A unary operator.
4935 * @return An output iterator equal to @p __result+(__last-__first).
4937 * Applies the operator to each element in the input range and assigns
4938 * the results to successive elements of the output sequence.
4939 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
4940 * range @p [0,__last-__first).
4942 * @p unary_op must not alter its argument.
4944 template<typename _InputIterator, typename _OutputIterator,
4945 typename _UnaryOperation>
4947 transform(_InputIterator __first, _InputIterator __last,
4948 _OutputIterator __result, _UnaryOperation __unary_op)
4950 // concept requirements
4951 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4952 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4953 // "the type returned by a _UnaryOperation"
4954 __typeof__(__unary_op(*__first))>)
4955 __glibcxx_requires_valid_range(__first, __last);
4957 for (; __first != __last; ++__first, ++__result)
4958 *__result = __unary_op(*__first);
4963 * @brief Perform an operation on corresponding elements of two sequences.
4964 * @ingroup mutating_algorithms
4965 * @param __first1 An input iterator.
4966 * @param __last1 An input iterator.
4967 * @param __first2 An input iterator.
4968 * @param __result An output iterator.
4969 * @param __binary_op A binary operator.
4970 * @return An output iterator equal to @p result+(last-first).
4972 * Applies the operator to the corresponding elements in the two
4973 * input ranges and assigns the results to successive elements of the
4976 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
4977 * @c N in the range @p [0,__last1-__first1).
4979 * @p binary_op must not alter either of its arguments.
4981 template<typename _InputIterator1, typename _InputIterator2,
4982 typename _OutputIterator, typename _BinaryOperation>
4984 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4985 _InputIterator2 __first2, _OutputIterator __result,
4986 _BinaryOperation __binary_op)
4988 // concept requirements
4989 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4990 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4991 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4992 // "the type returned by a _BinaryOperation"
4993 __typeof__(__binary_op(*__first1,*__first2))>)
4994 __glibcxx_requires_valid_range(__first1, __last1);
4996 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4997 *__result = __binary_op(*__first1, *__first2);
5002 * @brief Replace each occurrence of one value in a sequence with another
5004 * @ingroup mutating_algorithms
5005 * @param __first A forward iterator.
5006 * @param __last A forward iterator.
5007 * @param __old_value The value to be replaced.
5008 * @param __new_value The replacement value.
5009 * @return replace() returns no value.
5011 * For each iterator @c i in the range @p [__first,__last) if @c *i ==
5012 * @p __old_value then the assignment @c *i = @p __new_value is performed.
5014 template<typename _ForwardIterator, typename _Tp>
5016 replace(_ForwardIterator __first, _ForwardIterator __last,
5017 const _Tp& __old_value, const _Tp& __new_value)
5019 // concept requirements
5020 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5022 __glibcxx_function_requires(_EqualOpConcept<
5023 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
5024 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5025 typename iterator_traits<_ForwardIterator>::value_type>)
5026 __glibcxx_requires_valid_range(__first, __last);
5028 for (; __first != __last; ++__first)
5029 if (*__first == __old_value)
5030 *__first = __new_value;
5034 * @brief Replace each value in a sequence for which a predicate returns
5035 * true with another value.
5036 * @ingroup mutating_algorithms
5037 * @param __first A forward iterator.
5038 * @param __last A forward iterator.
5039 * @param __pred A predicate.
5040 * @param __new_value The replacement value.
5041 * @return replace_if() returns no value.
5043 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
5044 * is true then the assignment @c *i = @p __new_value is performed.
5046 template<typename _ForwardIterator, typename _Predicate, typename _Tp>
5048 replace_if(_ForwardIterator __first, _ForwardIterator __last,
5049 _Predicate __pred, const _Tp& __new_value)
5051 // concept requirements
5052 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5054 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5055 typename iterator_traits<_ForwardIterator>::value_type>)
5056 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5057 typename iterator_traits<_ForwardIterator>::value_type>)
5058 __glibcxx_requires_valid_range(__first, __last);
5060 for (; __first != __last; ++__first)
5061 if (__pred(*__first))
5062 *__first = __new_value;
5066 * @brief Assign the result of a function object to each value in a
5068 * @ingroup mutating_algorithms
5069 * @param __first A forward iterator.
5070 * @param __last A forward iterator.
5071 * @param __gen A function object taking no arguments and returning
5072 * std::iterator_traits<_ForwardIterator>::value_type
5073 * @return generate() returns no value.
5075 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5076 * @p [__first,__last).
5078 template<typename _ForwardIterator, typename _Generator>
5080 generate(_ForwardIterator __first, _ForwardIterator __last,
5083 // concept requirements
5084 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5085 __glibcxx_function_requires(_GeneratorConcept<_Generator,
5086 typename iterator_traits<_ForwardIterator>::value_type>)
5087 __glibcxx_requires_valid_range(__first, __last);
5089 for (; __first != __last; ++__first)
5094 * @brief Assign the result of a function object to each value in a
5096 * @ingroup mutating_algorithms
5097 * @param __first A forward iterator.
5098 * @param __n The length of the sequence.
5099 * @param __gen A function object taking no arguments and returning
5100 * std::iterator_traits<_ForwardIterator>::value_type
5101 * @return The end of the sequence, @p __first+__n
5103 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5104 * @p [__first,__first+__n).
5106 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5107 * DR 865. More algorithms that throw away information
5109 template<typename _OutputIterator, typename _Size, typename _Generator>
5111 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5113 // concept requirements
5114 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5115 // "the type returned by a _Generator"
5116 __typeof__(__gen())>)
5118 for (__decltype(__n + 0) __niter = __n;
5119 __niter > 0; --__niter, ++__first)
5126 * @brief Copy a sequence, removing consecutive duplicate values.
5127 * @ingroup mutating_algorithms
5128 * @param __first An input iterator.
5129 * @param __last An input iterator.
5130 * @param __result An output iterator.
5131 * @return An iterator designating the end of the resulting sequence.
5133 * Copies each element in the range @p [__first,__last) to the range
5134 * beginning at @p __result, except that only the first element is copied
5135 * from groups of consecutive elements that compare equal.
5136 * unique_copy() is stable, so the relative order of elements that are
5137 * copied is unchanged.
5139 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5140 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5142 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5143 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
5146 template<typename _InputIterator, typename _OutputIterator>
5147 inline _OutputIterator
5148 unique_copy(_InputIterator __first, _InputIterator __last,
5149 _OutputIterator __result)
5151 // concept requirements
5152 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5153 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5154 typename iterator_traits<_InputIterator>::value_type>)
5155 __glibcxx_function_requires(_EqualityComparableConcept<
5156 typename iterator_traits<_InputIterator>::value_type>)
5157 __glibcxx_requires_valid_range(__first, __last);
5159 if (__first == __last)
5161 return std::__unique_copy(__first, __last, __result,
5162 std::__iterator_category(__first),
5163 std::__iterator_category(__result));
5167 * @brief Copy a sequence, removing consecutive values using a predicate.
5168 * @ingroup mutating_algorithms
5169 * @param __first An input iterator.
5170 * @param __last An input iterator.
5171 * @param __result An output iterator.
5172 * @param __binary_pred A binary predicate.
5173 * @return An iterator designating the end of the resulting sequence.
5175 * Copies each element in the range @p [__first,__last) to the range
5176 * beginning at @p __result, except that only the first element is copied
5177 * from groups of consecutive elements for which @p __binary_pred returns
5179 * unique_copy() is stable, so the relative order of elements that are
5180 * copied is unchanged.
5182 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5183 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5185 template<typename _InputIterator, typename _OutputIterator,
5186 typename _BinaryPredicate>
5187 inline _OutputIterator
5188 unique_copy(_InputIterator __first, _InputIterator __last,
5189 _OutputIterator __result,
5190 _BinaryPredicate __binary_pred)
5192 // concept requirements -- predicates checked later
5193 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5194 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5195 typename iterator_traits<_InputIterator>::value_type>)
5196 __glibcxx_requires_valid_range(__first, __last);
5198 if (__first == __last)
5200 return std::__unique_copy(__first, __last, __result, __binary_pred,
5201 std::__iterator_category(__first),
5202 std::__iterator_category(__result));
5207 * @brief Randomly shuffle the elements of a sequence.
5208 * @ingroup mutating_algorithms
5209 * @param __first A forward iterator.
5210 * @param __last A forward iterator.
5213 * Reorder the elements in the range @p [__first,__last) using a random
5214 * distribution, so that every possible ordering of the sequence is
5217 template<typename _RandomAccessIterator>
5219 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5221 // concept requirements
5222 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5223 _RandomAccessIterator>)
5224 __glibcxx_requires_valid_range(__first, __last);
5226 if (__first != __last)
5227 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5228 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5232 * @brief Shuffle the elements of a sequence using a random number
5234 * @ingroup mutating_algorithms
5235 * @param __first A forward iterator.
5236 * @param __last A forward iterator.
5237 * @param __rand The RNG functor or function.
5240 * Reorders the elements in the range @p [__first,__last) using @p __rand to
5241 * provide a random distribution. Calling @p __rand(N) for a positive
5242 * integer @p N should return a randomly chosen integer from the
5245 template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
5247 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5248 #ifdef __GXX_EXPERIMENTAL_CXX0X__
5249 _RandomNumberGenerator&& __rand)
5251 _RandomNumberGenerator& __rand)
5254 // concept requirements
5255 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5256 _RandomAccessIterator>)
5257 __glibcxx_requires_valid_range(__first, __last);
5259 if (__first == __last)
5261 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5262 std::iter_swap(__i, __first + __rand((__i - __first) + 1));
5267 * @brief Move elements for which a predicate is true to the beginning
5269 * @ingroup mutating_algorithms
5270 * @param __first A forward iterator.
5271 * @param __last A forward iterator.
5272 * @param __pred A predicate functor.
5273 * @return An iterator @p middle such that @p __pred(i) is true for each
5274 * iterator @p i in the range @p [__first,middle) and false for each @p i
5275 * in the range @p [middle,__last).
5277 * @p __pred must not modify its operand. @p partition() does not preserve
5278 * the relative ordering of elements in each group, use
5279 * @p stable_partition() if this is needed.
5281 template<typename _ForwardIterator, typename _Predicate>
5282 inline _ForwardIterator
5283 partition(_ForwardIterator __first, _ForwardIterator __last,
5286 // concept requirements
5287 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5289 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5290 typename iterator_traits<_ForwardIterator>::value_type>)
5291 __glibcxx_requires_valid_range(__first, __last);
5293 return std::__partition(__first, __last, __pred,
5294 std::__iterator_category(__first));
5300 * @brief Sort the smallest elements of a sequence.
5301 * @ingroup sorting_algorithms
5302 * @param __first An iterator.
5303 * @param __middle Another iterator.
5304 * @param __last Another iterator.
5307 * Sorts the smallest @p (__middle-__first) elements in the range
5308 * @p [first,last) and moves them to the range @p [__first,__middle). The
5309 * order of the remaining elements in the range @p [__middle,__last) is
5311 * After the sort if @e i and @e j are iterators in the range
5312 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5313 * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
5315 template<typename _RandomAccessIterator>
5317 partial_sort(_RandomAccessIterator __first,
5318 _RandomAccessIterator __middle,
5319 _RandomAccessIterator __last)
5321 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5324 // concept requirements
5325 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5326 _RandomAccessIterator>)
5327 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5328 __glibcxx_requires_valid_range(__first, __middle);
5329 __glibcxx_requires_valid_range(__middle, __last);
5331 std::__heap_select(__first, __middle, __last);
5332 std::sort_heap(__first, __middle);
5336 * @brief Sort the smallest elements of a sequence using a predicate
5338 * @ingroup sorting_algorithms
5339 * @param __first An iterator.
5340 * @param __middle Another iterator.
5341 * @param __last Another iterator.
5342 * @param __comp A comparison functor.
5345 * Sorts the smallest @p (__middle-__first) elements in the range
5346 * @p [__first,__last) and moves them to the range @p [__first,__middle). The
5347 * order of the remaining elements in the range @p [__middle,__last) is
5349 * After the sort if @e i and @e j are iterators in the range
5350 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5351 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
5354 template<typename _RandomAccessIterator, typename _Compare>
5356 partial_sort(_RandomAccessIterator __first,
5357 _RandomAccessIterator __middle,
5358 _RandomAccessIterator __last,
5361 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5364 // concept requirements
5365 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5366 _RandomAccessIterator>)
5367 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5368 _ValueType, _ValueType>)
5369 __glibcxx_requires_valid_range(__first, __middle);
5370 __glibcxx_requires_valid_range(__middle, __last);
5372 std::__heap_select(__first, __middle, __last, __comp);
5373 std::sort_heap(__first, __middle, __comp);
5377 * @brief Sort a sequence just enough to find a particular position.
5378 * @ingroup sorting_algorithms
5379 * @param __first An iterator.
5380 * @param __nth Another iterator.
5381 * @param __last Another iterator.
5384 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5385 * is the same element that would have been in that position had the
5386 * whole sequence been sorted. The elements either side of @p *__nth are
5387 * not completely sorted, but for any iterator @e i in the range
5388 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5389 * holds that *j < *i is false.
5391 template<typename _RandomAccessIterator>
5393 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5394 _RandomAccessIterator __last)
5396 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5399 // concept requirements
5400 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5401 _RandomAccessIterator>)
5402 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5403 __glibcxx_requires_valid_range(__first, __nth);
5404 __glibcxx_requires_valid_range(__nth, __last);
5406 if (__first == __last || __nth == __last)
5409 std::__introselect(__first, __nth, __last,
5410 std::__lg(__last - __first) * 2);
5414 * @brief Sort a sequence just enough to find a particular position
5415 * using a predicate for comparison.
5416 * @ingroup sorting_algorithms
5417 * @param __first An iterator.
5418 * @param __nth Another iterator.
5419 * @param __last Another iterator.
5420 * @param __comp A comparison functor.
5423 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5424 * is the same element that would have been in that position had the
5425 * whole sequence been sorted. The elements either side of @p *__nth are
5426 * not completely sorted, but for any iterator @e i in the range
5427 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5428 * holds that @p __comp(*j,*i) is false.
5430 template<typename _RandomAccessIterator, typename _Compare>
5432 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5433 _RandomAccessIterator __last, _Compare __comp)
5435 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5438 // concept requirements
5439 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5440 _RandomAccessIterator>)
5441 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5442 _ValueType, _ValueType>)
5443 __glibcxx_requires_valid_range(__first, __nth);
5444 __glibcxx_requires_valid_range(__nth, __last);
5446 if (__first == __last || __nth == __last)
5449 std::__introselect(__first, __nth, __last,
5450 std::__lg(__last - __first) * 2, __comp);
5455 * @brief Sort the elements of a sequence.
5456 * @ingroup sorting_algorithms
5457 * @param __first An iterator.
5458 * @param __last Another iterator.
5461 * Sorts the elements in the range @p [__first,__last) in ascending order,
5462 * such that for each iterator @e i in the range @p [__first,__last-1),
5463 * *(i+1)<*i is false.
5465 * The relative ordering of equivalent elements is not preserved, use
5466 * @p stable_sort() if this is needed.
5468 template<typename _RandomAccessIterator>
5470 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5472 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5475 // concept requirements
5476 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5477 _RandomAccessIterator>)
5478 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5479 __glibcxx_requires_valid_range(__first, __last);
5481 if (__first != __last)
5483 std::__introsort_loop(__first, __last,
5484 std::__lg(__last - __first) * 2);
5485 std::__final_insertion_sort(__first, __last);
5490 * @brief Sort the elements of a sequence using a predicate for comparison.
5491 * @ingroup sorting_algorithms
5492 * @param __first An iterator.
5493 * @param __last Another iterator.
5494 * @param __comp A comparison functor.
5497 * Sorts the elements in the range @p [__first,__last) in ascending order,
5498 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
5499 * range @p [__first,__last-1).
5501 * The relative ordering of equivalent elements is not preserved, use
5502 * @p stable_sort() if this is needed.
5504 template<typename _RandomAccessIterator, typename _Compare>
5506 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5509 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5512 // concept requirements
5513 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5514 _RandomAccessIterator>)
5515 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5517 __glibcxx_requires_valid_range(__first, __last);
5519 if (__first != __last)
5521 std::__introsort_loop(__first, __last,
5522 std::__lg(__last - __first) * 2, __comp);
5523 std::__final_insertion_sort(__first, __last, __comp);
5528 * @brief Merges two sorted ranges.
5529 * @ingroup sorting_algorithms
5530 * @param __first1 An iterator.
5531 * @param __first2 Another iterator.
5532 * @param __last1 Another iterator.
5533 * @param __last2 Another iterator.
5534 * @param __result An iterator pointing to the end of the merged range.
5535 * @return An iterator pointing to the first element <em>not less
5538 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5539 * the sorted range @p [__result, __result + (__last1-__first1) +
5540 * (__last2-__first2)). Both input ranges must be sorted, and the
5541 * output range must not overlap with either of the input ranges.
5542 * The sort is @e stable, that is, for equivalent elements in the
5543 * two ranges, elements from the first range will always come
5544 * before elements from the second.
5546 template<typename _InputIterator1, typename _InputIterator2,
5547 typename _OutputIterator>
5549 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5550 _InputIterator2 __first2, _InputIterator2 __last2,
5551 _OutputIterator __result)
5553 typedef typename iterator_traits<_InputIterator1>::value_type
5555 typedef typename iterator_traits<_InputIterator2>::value_type
5558 // concept requirements
5559 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5560 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5561 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5563 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5565 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5566 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5567 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5569 while (__first1 != __last1 && __first2 != __last2)
5571 if (*__first2 < *__first1)
5573 *__result = *__first2;
5578 *__result = *__first1;
5583 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5588 * @brief Merges two sorted ranges.
5589 * @ingroup sorting_algorithms
5590 * @param __first1 An iterator.
5591 * @param __first2 Another iterator.
5592 * @param __last1 Another iterator.
5593 * @param __last2 Another iterator.
5594 * @param __result An iterator pointing to the end of the merged range.
5595 * @param __comp A functor to use for comparisons.
5596 * @return An iterator pointing to the first element "not less
5599 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5600 * the sorted range @p [__result, __result + (__last1-__first1) +
5601 * (__last2-__first2)). Both input ranges must be sorted, and the
5602 * output range must not overlap with either of the input ranges.
5603 * The sort is @e stable, that is, for equivalent elements in the
5604 * two ranges, elements from the first range will always come
5605 * before elements from the second.
5607 * The comparison function should have the same effects on ordering as
5608 * the function used for the initial sort.
5610 template<typename _InputIterator1, typename _InputIterator2,
5611 typename _OutputIterator, typename _Compare>
5613 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5614 _InputIterator2 __first2, _InputIterator2 __last2,
5615 _OutputIterator __result, _Compare __comp)
5617 typedef typename iterator_traits<_InputIterator1>::value_type
5619 typedef typename iterator_traits<_InputIterator2>::value_type
5622 // concept requirements
5623 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5624 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5625 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5627 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5629 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5630 _ValueType2, _ValueType1>)
5631 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5632 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5634 while (__first1 != __last1 && __first2 != __last2)
5636 if (__comp(*__first2, *__first1))
5638 *__result = *__first2;
5643 *__result = *__first1;
5648 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5654 * @brief Sort the elements of a sequence, preserving the relative order
5655 * of equivalent elements.
5656 * @ingroup sorting_algorithms
5657 * @param __first An iterator.
5658 * @param __last Another iterator.
5661 * Sorts the elements in the range @p [__first,__last) in ascending order,
5662 * such that for each iterator @p i in the range @p [__first,__last-1),
5663 * @p *(i+1)<*i is false.
5665 * The relative ordering of equivalent elements is preserved, so any two
5666 * elements @p x and @p y in the range @p [__first,__last) such that
5667 * @p x<y is false and @p y<x is false will have the same relative
5668 * ordering after calling @p stable_sort().
5670 template<typename _RandomAccessIterator>
5672 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5674 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5676 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5679 // concept requirements
5680 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5681 _RandomAccessIterator>)
5682 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5683 __glibcxx_requires_valid_range(__first, __last);
5685 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5687 if (__buf.begin() == 0)
5688 std::__inplace_stable_sort(__first, __last);
5690 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5691 _DistanceType(__buf.size()));
5695 * @brief Sort the elements of a sequence using a predicate for comparison,
5696 * preserving the relative order of equivalent elements.
5697 * @ingroup sorting_algorithms
5698 * @param __first An iterator.
5699 * @param __last Another iterator.
5700 * @param __comp A comparison functor.
5703 * Sorts the elements in the range @p [__first,__last) in ascending order,
5704 * such that for each iterator @p i in the range @p [__first,__last-1),
5705 * @p __comp(*(i+1),*i) is false.
5707 * The relative ordering of equivalent elements is preserved, so any two
5708 * elements @p x and @p y in the range @p [__first,__last) such that
5709 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5710 * relative ordering after calling @p stable_sort().
5712 template<typename _RandomAccessIterator, typename _Compare>
5714 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5717 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5719 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5722 // concept requirements
5723 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5724 _RandomAccessIterator>)
5725 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5728 __glibcxx_requires_valid_range(__first, __last);
5730 _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
5732 if (__buf.begin() == 0)
5733 std::__inplace_stable_sort(__first, __last, __comp);
5735 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5736 _DistanceType(__buf.size()), __comp);
5741 * @brief Return the union of two sorted ranges.
5742 * @ingroup set_algorithms
5743 * @param __first1 Start of first range.
5744 * @param __last1 End of first range.
5745 * @param __first2 Start of second range.
5746 * @param __last2 End of second range.
5747 * @return End of the output range.
5748 * @ingroup set_algorithms
5750 * This operation iterates over both ranges, copying elements present in
5751 * each range in order to the output range. Iterators increment for each
5752 * range. When the current element of one range is less than the other,
5753 * that element is copied and the iterator advanced. If an element is
5754 * contained in both ranges, the element from the first range is copied and
5755 * both ranges advance. The output range may not overlap either input
5758 template<typename _InputIterator1, typename _InputIterator2,
5759 typename _OutputIterator>
5761 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5762 _InputIterator2 __first2, _InputIterator2 __last2,
5763 _OutputIterator __result)
5765 typedef typename iterator_traits<_InputIterator1>::value_type
5767 typedef typename iterator_traits<_InputIterator2>::value_type
5770 // concept requirements
5771 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5772 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5773 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5775 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5777 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5778 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5779 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5780 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5782 while (__first1 != __last1 && __first2 != __last2)
5784 if (*__first1 < *__first2)
5786 *__result = *__first1;
5789 else if (*__first2 < *__first1)
5791 *__result = *__first2;
5796 *__result = *__first1;
5802 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5807 * @brief Return the union of two sorted ranges using a comparison functor.
5808 * @ingroup set_algorithms
5809 * @param __first1 Start of first range.
5810 * @param __last1 End of first range.
5811 * @param __first2 Start of second range.
5812 * @param __last2 End of second range.
5813 * @param __comp The comparison functor.
5814 * @return End of the output range.
5815 * @ingroup set_algorithms
5817 * This operation iterates over both ranges, copying elements present in
5818 * each range in order to the output range. Iterators increment for each
5819 * range. When the current element of one range is less than the other
5820 * according to @p __comp, that element is copied and the iterator advanced.
5821 * If an equivalent element according to @p __comp is contained in both
5822 * ranges, the element from the first range is copied and both ranges
5823 * advance. The output range may not overlap either input range.
5825 template<typename _InputIterator1, typename _InputIterator2,
5826 typename _OutputIterator, typename _Compare>
5828 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5829 _InputIterator2 __first2, _InputIterator2 __last2,
5830 _OutputIterator __result, _Compare __comp)
5832 typedef typename iterator_traits<_InputIterator1>::value_type
5834 typedef typename iterator_traits<_InputIterator2>::value_type
5837 // concept requirements
5838 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5839 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5840 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5842 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5844 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5845 _ValueType1, _ValueType2>)
5846 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5847 _ValueType2, _ValueType1>)
5848 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5849 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5851 while (__first1 != __last1 && __first2 != __last2)
5853 if (__comp(*__first1, *__first2))
5855 *__result = *__first1;
5858 else if (__comp(*__first2, *__first1))
5860 *__result = *__first2;
5865 *__result = *__first1;
5871 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5876 * @brief Return the intersection of two sorted ranges.
5877 * @ingroup set_algorithms
5878 * @param __first1 Start of first range.
5879 * @param __last1 End of first range.
5880 * @param __first2 Start of second range.
5881 * @param __last2 End of second range.
5882 * @return End of the output range.
5883 * @ingroup set_algorithms
5885 * This operation iterates over both ranges, copying elements present in
5886 * both ranges in order to the output range. Iterators increment for each
5887 * range. When the current element of one range is less than the other,
5888 * that iterator advances. If an element is contained in both ranges, the
5889 * element from the first range is copied and both ranges advance. The
5890 * output range may not overlap either input range.
5892 template<typename _InputIterator1, typename _InputIterator2,
5893 typename _OutputIterator>
5895 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5896 _InputIterator2 __first2, _InputIterator2 __last2,
5897 _OutputIterator __result)
5899 typedef typename iterator_traits<_InputIterator1>::value_type
5901 typedef typename iterator_traits<_InputIterator2>::value_type
5904 // concept requirements
5905 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5906 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5907 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5909 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5910 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5911 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5912 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5914 while (__first1 != __last1 && __first2 != __last2)
5915 if (*__first1 < *__first2)
5917 else if (*__first2 < *__first1)
5921 *__result = *__first1;
5930 * @brief Return the intersection of two sorted ranges using comparison
5932 * @ingroup set_algorithms
5933 * @param __first1 Start of first range.
5934 * @param __last1 End of first range.
5935 * @param __first2 Start of second range.
5936 * @param __last2 End of second range.
5937 * @param __comp The comparison functor.
5938 * @return End of the output range.
5939 * @ingroup set_algorithms
5941 * This operation iterates over both ranges, copying elements present in
5942 * both ranges in order to the output range. Iterators increment for each
5943 * range. When the current element of one range is less than the other
5944 * according to @p __comp, that iterator advances. If an element is
5945 * contained in both ranges according to @p __comp, the element from the
5946 * first range is copied and both ranges advance. The output range may not
5947 * overlap either input range.
5949 template<typename _InputIterator1, typename _InputIterator2,
5950 typename _OutputIterator, typename _Compare>
5952 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5953 _InputIterator2 __first2, _InputIterator2 __last2,
5954 _OutputIterator __result, _Compare __comp)
5956 typedef typename iterator_traits<_InputIterator1>::value_type
5958 typedef typename iterator_traits<_InputIterator2>::value_type
5961 // concept requirements
5962 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5963 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5964 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5966 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5967 _ValueType1, _ValueType2>)
5968 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5969 _ValueType2, _ValueType1>)
5970 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5971 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5973 while (__first1 != __last1 && __first2 != __last2)
5974 if (__comp(*__first1, *__first2))
5976 else if (__comp(*__first2, *__first1))
5980 *__result = *__first1;
5989 * @brief Return the difference of two sorted ranges.
5990 * @ingroup set_algorithms
5991 * @param __first1 Start of first range.
5992 * @param __last1 End of first range.
5993 * @param __first2 Start of second range.
5994 * @param __last2 End of second range.
5995 * @return End of the output range.
5996 * @ingroup set_algorithms
5998 * This operation iterates over both ranges, copying elements present in
5999 * the first range but not the second in order to the output range.
6000 * Iterators increment for each range. When the current element of the
6001 * first range is less than the second, that element is copied and the
6002 * iterator advances. If the current element of the second range is less,
6003 * the iterator advances, but no element is copied. If an element is
6004 * contained in both ranges, no elements are copied and both ranges
6005 * advance. The output range may not overlap either input range.
6007 template<typename _InputIterator1, typename _InputIterator2,
6008 typename _OutputIterator>
6010 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6011 _InputIterator2 __first2, _InputIterator2 __last2,
6012 _OutputIterator __result)
6014 typedef typename iterator_traits<_InputIterator1>::value_type
6016 typedef typename iterator_traits<_InputIterator2>::value_type
6019 // concept requirements
6020 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6021 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6022 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6024 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6025 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6026 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6027 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6029 while (__first1 != __last1 && __first2 != __last2)
6030 if (*__first1 < *__first2)
6032 *__result = *__first1;
6036 else if (*__first2 < *__first1)
6043 return std::copy(__first1, __last1, __result);
6047 * @brief Return the difference of two sorted ranges using comparison
6049 * @ingroup set_algorithms
6050 * @param __first1 Start of first range.
6051 * @param __last1 End of first range.
6052 * @param __first2 Start of second range.
6053 * @param __last2 End of second range.
6054 * @param __comp The comparison functor.
6055 * @return End of the output range.
6056 * @ingroup set_algorithms
6058 * This operation iterates over both ranges, copying elements present in
6059 * the first range but not the second in order to the output range.
6060 * Iterators increment for each range. When the current element of the
6061 * first range is less than the second according to @p __comp, that element
6062 * is copied and the iterator advances. If the current element of the
6063 * second range is less, no element is copied and the iterator advances.
6064 * If an element is contained in both ranges according to @p __comp, no
6065 * elements are copied and both ranges advance. The output range may not
6066 * overlap either input range.
6068 template<typename _InputIterator1, typename _InputIterator2,
6069 typename _OutputIterator, typename _Compare>
6071 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6072 _InputIterator2 __first2, _InputIterator2 __last2,
6073 _OutputIterator __result, _Compare __comp)
6075 typedef typename iterator_traits<_InputIterator1>::value_type
6077 typedef typename iterator_traits<_InputIterator2>::value_type
6080 // concept requirements
6081 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6082 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6083 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6085 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6086 _ValueType1, _ValueType2>)
6087 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6088 _ValueType2, _ValueType1>)
6089 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6090 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6092 while (__first1 != __last1 && __first2 != __last2)
6093 if (__comp(*__first1, *__first2))
6095 *__result = *__first1;
6099 else if (__comp(*__first2, *__first1))
6106 return std::copy(__first1, __last1, __result);
6110 * @brief Return the symmetric difference of two sorted ranges.
6111 * @ingroup set_algorithms
6112 * @param __first1 Start of first range.
6113 * @param __last1 End of first range.
6114 * @param __first2 Start of second range.
6115 * @param __last2 End of second range.
6116 * @return End of the output range.
6117 * @ingroup set_algorithms
6119 * This operation iterates over both ranges, copying elements present in
6120 * one range but not the other in order to the output range. Iterators
6121 * increment for each range. When the current element of one range is less
6122 * than the other, that element is copied and the iterator advances. If an
6123 * element is contained in both ranges, no elements are copied and both
6124 * ranges advance. The output range may not overlap either input range.
6126 template<typename _InputIterator1, typename _InputIterator2,
6127 typename _OutputIterator>
6129 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6130 _InputIterator2 __first2, _InputIterator2 __last2,
6131 _OutputIterator __result)
6133 typedef typename iterator_traits<_InputIterator1>::value_type
6135 typedef typename iterator_traits<_InputIterator2>::value_type
6138 // concept requirements
6139 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6140 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6141 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6143 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6145 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6146 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6147 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6148 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6150 while (__first1 != __last1 && __first2 != __last2)
6151 if (*__first1 < *__first2)
6153 *__result = *__first1;
6157 else if (*__first2 < *__first1)
6159 *__result = *__first2;
6168 return std::copy(__first2, __last2, std::copy(__first1,
6169 __last1, __result));
6173 * @brief Return the symmetric difference of two sorted ranges using
6174 * comparison functor.
6175 * @ingroup set_algorithms
6176 * @param __first1 Start of first range.
6177 * @param __last1 End of first range.
6178 * @param __first2 Start of second range.
6179 * @param __last2 End of second range.
6180 * @param __comp The comparison functor.
6181 * @return End of the output range.
6182 * @ingroup set_algorithms
6184 * This operation iterates over both ranges, copying elements present in
6185 * one range but not the other in order to the output range. Iterators
6186 * increment for each range. When the current element of one range is less
6187 * than the other according to @p comp, that element is copied and the
6188 * iterator advances. If an element is contained in both ranges according
6189 * to @p __comp, no elements are copied and both ranges advance. The output
6190 * range may not overlap either input range.
6192 template<typename _InputIterator1, typename _InputIterator2,
6193 typename _OutputIterator, typename _Compare>
6195 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6196 _InputIterator2 __first2, _InputIterator2 __last2,
6197 _OutputIterator __result,
6200 typedef typename iterator_traits<_InputIterator1>::value_type
6202 typedef typename iterator_traits<_InputIterator2>::value_type
6205 // concept requirements
6206 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6207 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6208 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6212 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6213 _ValueType1, _ValueType2>)
6214 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6215 _ValueType2, _ValueType1>)
6216 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6217 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6219 while (__first1 != __last1 && __first2 != __last2)
6220 if (__comp(*__first1, *__first2))
6222 *__result = *__first1;
6226 else if (__comp(*__first2, *__first1))
6228 *__result = *__first2;
6237 return std::copy(__first2, __last2,
6238 std::copy(__first1, __last1, __result));
6243 * @brief Return the minimum element in a range.
6244 * @ingroup sorting_algorithms
6245 * @param __first Start of range.
6246 * @param __last End of range.
6247 * @return Iterator referencing the first instance of the smallest value.
6249 template<typename _ForwardIterator>
6251 min_element(_ForwardIterator __first, _ForwardIterator __last)
6253 // concept requirements
6254 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6255 __glibcxx_function_requires(_LessThanComparableConcept<
6256 typename iterator_traits<_ForwardIterator>::value_type>)
6257 __glibcxx_requires_valid_range(__first, __last);
6259 if (__first == __last)
6261 _ForwardIterator __result = __first;
6262 while (++__first != __last)
6263 if (*__first < *__result)
6269 * @brief Return the minimum element in a range using comparison functor.
6270 * @ingroup sorting_algorithms
6271 * @param __first Start of range.
6272 * @param __last End of range.
6273 * @param __comp Comparison functor.
6274 * @return Iterator referencing the first instance of the smallest value
6275 * according to __comp.
6277 template<typename _ForwardIterator, typename _Compare>
6279 min_element(_ForwardIterator __first, _ForwardIterator __last,
6282 // concept requirements
6283 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6284 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6285 typename iterator_traits<_ForwardIterator>::value_type,
6286 typename iterator_traits<_ForwardIterator>::value_type>)
6287 __glibcxx_requires_valid_range(__first, __last);
6289 if (__first == __last)
6291 _ForwardIterator __result = __first;
6292 while (++__first != __last)
6293 if (__comp(*__first, *__result))
6299 * @brief Return the maximum element in a range.
6300 * @ingroup sorting_algorithms
6301 * @param __first Start of range.
6302 * @param __last End of range.
6303 * @return Iterator referencing the first instance of the largest value.
6305 template<typename _ForwardIterator>
6307 max_element(_ForwardIterator __first, _ForwardIterator __last)
6309 // concept requirements
6310 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6311 __glibcxx_function_requires(_LessThanComparableConcept<
6312 typename iterator_traits<_ForwardIterator>::value_type>)
6313 __glibcxx_requires_valid_range(__first, __last);
6315 if (__first == __last)
6317 _ForwardIterator __result = __first;
6318 while (++__first != __last)
6319 if (*__result < *__first)
6325 * @brief Return the maximum element in a range using comparison functor.
6326 * @ingroup sorting_algorithms
6327 * @param __first Start of range.
6328 * @param __last End of range.
6329 * @param __comp Comparison functor.
6330 * @return Iterator referencing the first instance of the largest value
6331 * according to __comp.
6333 template<typename _ForwardIterator, typename _Compare>
6335 max_element(_ForwardIterator __first, _ForwardIterator __last,
6338 // concept requirements
6339 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6340 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6341 typename iterator_traits<_ForwardIterator>::value_type,
6342 typename iterator_traits<_ForwardIterator>::value_type>)
6343 __glibcxx_requires_valid_range(__first, __last);
6345 if (__first == __last) return __first;
6346 _ForwardIterator __result = __first;
6347 while (++__first != __last)
6348 if (__comp(*__result, *__first))
6353 _GLIBCXX_END_NAMESPACE_ALGO
6356 #endif /* _STL_ALGO_H */