1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
29 * Hewlett-Packard Company
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
41 * Silicon Graphics Computer Systems, Inc.
43 * Permission to use, copy, modify, distribute and sell this software
44 * and its documentation for any purpose is hereby granted without fee,
45 * provided that the above copyright notice appear in all copies and
46 * that both that copyright notice and this permission notice appear
47 * in supporting documentation. Silicon Graphics makes no
48 * representations about the suitability of this software for any
49 * purpose. It is provided "as is" without express or implied warranty.
53 * This is an internal header file, included by other library headers.
54 * You should not attempt to use it directly.
60 #include <cstdlib> // for rand
61 #include <bits/algorithmfwd.h>
62 #include <bits/stl_heap.h>
63 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
65 // See concept_check.h for the __glibcxx_*_requires macros.
67 _GLIBCXX_BEGIN_NAMESPACE(std
)
70 * @brief Find the median of three values.
74 * @return One of @p a, @p b or @p c.
76 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
77 * then the value returned will be @c m.
78 * This is an SGI extension.
79 * @ingroup SGIextensions
81 template<typename _Tp
>
83 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
)
85 // concept requirements
86 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
103 * @brief Find the median of three values using a predicate for comparison.
107 * @param comp A binary predicate.
108 * @return One of @p a, @p b or @p c.
110 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
111 * and @p comp(m,n) are both true then the value returned will be @c m.
112 * This is an SGI extension.
113 * @ingroup SGIextensions
115 template<typename _Tp
, typename _Compare
>
117 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
, _Compare __comp
)
119 // concept requirements
120 __glibcxx_function_requires(_BinaryFunctionConcept
<_Compare
, bool,
122 if (__comp(__a
, __b
))
123 if (__comp(__b
, __c
))
125 else if (__comp(__a
, __c
))
129 else if (__comp(__a
, __c
))
131 else if (__comp(__b
, __c
))
137 /// Swaps the median value of *__a, *__b and *__c to *__a
138 template<typename _Iterator
>
140 __move_median_first(_Iterator __a
, _Iterator __b
, _Iterator __c
)
142 // concept requirements
143 __glibcxx_function_requires(_LessThanComparableConcept
<
144 typename iterator_traits
<_Iterator
>::value_type
>)
149 std::iter_swap(__a
, __b
);
150 else if (*__a
< *__c
)
151 std::iter_swap(__a
, __c
);
153 else if (*__a
< *__c
)
155 else if (*__b
< *__c
)
156 std::iter_swap(__a
, __c
);
158 std::iter_swap(__a
, __b
);
161 /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
162 template<typename _Iterator
, typename _Compare
>
164 __move_median_first(_Iterator __a
, _Iterator __b
, _Iterator __c
,
167 // concept requirements
168 __glibcxx_function_requires(_BinaryFunctionConcept
<_Compare
, bool,
169 typename iterator_traits
<_Iterator
>::value_type
,
170 typename iterator_traits
<_Iterator
>::value_type
>)
172 if (__comp(*__a
, *__b
))
174 if (__comp(*__b
, *__c
))
175 std::iter_swap(__a
, __b
);
176 else if (__comp(*__a
, *__c
))
177 std::iter_swap(__a
, __c
);
179 else if (__comp(*__a
, *__c
))
181 else if (__comp(*__b
, *__c
))
182 std::iter_swap(__a
, __c
);
184 std::iter_swap(__a
, __b
);
189 /// This is an overload used by find() for the Input Iterator case.
190 template<typename _InputIterator
, typename _Tp
>
191 inline _InputIterator
192 __find(_InputIterator __first
, _InputIterator __last
,
193 const _Tp
& __val
, input_iterator_tag
)
195 while (__first
!= __last
&& !(*__first
== __val
))
200 /// This is an overload used by find_if() for the Input Iterator case.
201 template<typename _InputIterator
, typename _Predicate
>
202 inline _InputIterator
203 __find_if(_InputIterator __first
, _InputIterator __last
,
204 _Predicate __pred
, input_iterator_tag
)
206 while (__first
!= __last
&& !bool(__pred(*__first
)))
211 /// This is an overload used by find() for the RAI case.
212 template<typename _RandomAccessIterator
, typename _Tp
>
213 _RandomAccessIterator
214 __find(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
215 const _Tp
& __val
, random_access_iterator_tag
)
217 typename iterator_traits
<_RandomAccessIterator
>::difference_type
218 __trip_count
= (__last
- __first
) >> 2;
220 for (; __trip_count
> 0; --__trip_count
)
222 if (*__first
== __val
)
226 if (*__first
== __val
)
230 if (*__first
== __val
)
234 if (*__first
== __val
)
239 switch (__last
- __first
)
242 if (*__first
== __val
)
246 if (*__first
== __val
)
250 if (*__first
== __val
)
259 /// This is an overload used by find_if() for the RAI case.
260 template<typename _RandomAccessIterator
, typename _Predicate
>
261 _RandomAccessIterator
262 __find_if(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
263 _Predicate __pred
, random_access_iterator_tag
)
265 typename iterator_traits
<_RandomAccessIterator
>::difference_type
266 __trip_count
= (__last
- __first
) >> 2;
268 for (; __trip_count
> 0; --__trip_count
)
270 if (__pred(*__first
))
274 if (__pred(*__first
))
278 if (__pred(*__first
))
282 if (__pred(*__first
))
287 switch (__last
- __first
)
290 if (__pred(*__first
))
294 if (__pred(*__first
))
298 if (__pred(*__first
))
307 #ifdef __GXX_EXPERIMENTAL_CXX0X__
308 /// This is an overload used by find_if_not() for the Input Iterator case.
309 template<typename _InputIterator
, typename _Predicate
>
310 inline _InputIterator
311 __find_if_not(_InputIterator __first
, _InputIterator __last
,
312 _Predicate __pred
, input_iterator_tag
)
314 while (__first
!= __last
&& bool(__pred(*__first
)))
319 /// This is an overload used by find_if_not() for the RAI case.
320 template<typename _RandomAccessIterator
, typename _Predicate
>
321 _RandomAccessIterator
322 __find_if_not(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
323 _Predicate __pred
, random_access_iterator_tag
)
325 typename iterator_traits
<_RandomAccessIterator
>::difference_type
326 __trip_count
= (__last
- __first
) >> 2;
328 for (; __trip_count
> 0; --__trip_count
)
330 if (!bool(__pred(*__first
)))
334 if (!bool(__pred(*__first
)))
338 if (!bool(__pred(*__first
)))
342 if (!bool(__pred(*__first
)))
347 switch (__last
- __first
)
350 if (!bool(__pred(*__first
)))
354 if (!bool(__pred(*__first
)))
358 if (!bool(__pred(*__first
)))
370 // set_symmetric_difference
382 * This is an uglified
383 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
384 * overloaded for forward iterators.
386 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
388 __search_n(_ForwardIterator __first
, _ForwardIterator __last
,
389 _Integer __count
, const _Tp
& __val
,
390 std::forward_iterator_tag
)
392 __first
= _GLIBCXX_STD_P::find(__first
, __last
, __val
);
393 while (__first
!= __last
)
395 typename iterator_traits
<_ForwardIterator
>::difference_type
397 _ForwardIterator __i
= __first
;
399 while (__i
!= __last
&& __n
!= 1 && *__i
== __val
)
408 __first
= _GLIBCXX_STD_P::find(++__i
, __last
, __val
);
414 * This is an uglified
415 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
416 * overloaded for random access iterators.
418 template<typename _RandomAccessIter
, typename _Integer
, typename _Tp
>
420 __search_n(_RandomAccessIter __first
, _RandomAccessIter __last
,
421 _Integer __count
, const _Tp
& __val
,
422 std::random_access_iterator_tag
)
425 typedef typename
std::iterator_traits
<_RandomAccessIter
>::difference_type
428 _DistanceType __tailSize
= __last
- __first
;
429 const _DistanceType __pattSize
= __count
;
431 if (__tailSize
< __pattSize
)
434 const _DistanceType __skipOffset
= __pattSize
- 1;
435 _RandomAccessIter __lookAhead
= __first
+ __skipOffset
;
436 __tailSize
-= __pattSize
;
438 while (1) // the main loop...
440 // __lookAhead here is always pointing to the last element of next
442 while (!(*__lookAhead
== __val
)) // the skip loop...
444 if (__tailSize
< __pattSize
)
445 return __last
; // Failure
446 __lookAhead
+= __pattSize
;
447 __tailSize
-= __pattSize
;
449 _DistanceType __remainder
= __skipOffset
;
450 for (_RandomAccessIter __backTrack
= __lookAhead
- 1;
451 *__backTrack
== __val
; --__backTrack
)
453 if (--__remainder
== 0)
454 return (__lookAhead
- __skipOffset
); // Success
456 if (__remainder
> __tailSize
)
457 return __last
; // Failure
458 __lookAhead
+= __remainder
;
459 __tailSize
-= __remainder
;
466 * This is an uglified
467 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
469 * overloaded for forward iterators.
471 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
472 typename _BinaryPredicate
>
474 __search_n(_ForwardIterator __first
, _ForwardIterator __last
,
475 _Integer __count
, const _Tp
& __val
,
476 _BinaryPredicate __binary_pred
, std::forward_iterator_tag
)
478 while (__first
!= __last
&& !bool(__binary_pred(*__first
, __val
)))
481 while (__first
!= __last
)
483 typename iterator_traits
<_ForwardIterator
>::difference_type
485 _ForwardIterator __i
= __first
;
487 while (__i
!= __last
&& __n
!= 1 && bool(__binary_pred(*__i
, __val
)))
497 while (__first
!= __last
498 && !bool(__binary_pred(*__first
, __val
)))
505 * This is an uglified
506 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
508 * overloaded for random access iterators.
510 template<typename _RandomAccessIter
, typename _Integer
, typename _Tp
,
511 typename _BinaryPredicate
>
513 __search_n(_RandomAccessIter __first
, _RandomAccessIter __last
,
514 _Integer __count
, const _Tp
& __val
,
515 _BinaryPredicate __binary_pred
, std::random_access_iterator_tag
)
518 typedef typename
std::iterator_traits
<_RandomAccessIter
>::difference_type
521 _DistanceType __tailSize
= __last
- __first
;
522 const _DistanceType __pattSize
= __count
;
524 if (__tailSize
< __pattSize
)
527 const _DistanceType __skipOffset
= __pattSize
- 1;
528 _RandomAccessIter __lookAhead
= __first
+ __skipOffset
;
529 __tailSize
-= __pattSize
;
531 while (1) // the main loop...
533 // __lookAhead here is always pointing to the last element of next
535 while (!bool(__binary_pred(*__lookAhead
, __val
))) // the skip loop...
537 if (__tailSize
< __pattSize
)
538 return __last
; // Failure
539 __lookAhead
+= __pattSize
;
540 __tailSize
-= __pattSize
;
542 _DistanceType __remainder
= __skipOffset
;
543 for (_RandomAccessIter __backTrack
= __lookAhead
- 1;
544 __binary_pred(*__backTrack
, __val
); --__backTrack
)
546 if (--__remainder
== 0)
547 return (__lookAhead
- __skipOffset
); // Success
549 if (__remainder
> __tailSize
)
550 return __last
; // Failure
551 __lookAhead
+= __remainder
;
552 __tailSize
-= __remainder
;
556 // find_end for forward iterators.
557 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
559 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
560 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
561 forward_iterator_tag
, forward_iterator_tag
)
563 if (__first2
== __last2
)
567 _ForwardIterator1 __result
= __last1
;
570 _ForwardIterator1 __new_result
571 = _GLIBCXX_STD_P::search(__first1
, __last1
, __first2
, __last2
);
572 if (__new_result
== __last1
)
576 __result
= __new_result
;
577 __first1
= __new_result
;
584 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
585 typename _BinaryPredicate
>
587 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
588 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
589 forward_iterator_tag
, forward_iterator_tag
,
590 _BinaryPredicate __comp
)
592 if (__first2
== __last2
)
596 _ForwardIterator1 __result
= __last1
;
599 _ForwardIterator1 __new_result
600 = _GLIBCXX_STD_P::search(__first1
, __last1
, __first2
,
602 if (__new_result
== __last1
)
606 __result
= __new_result
;
607 __first1
= __new_result
;
614 // find_end for bidirectional iterators (much faster).
615 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
>
616 _BidirectionalIterator1
617 __find_end(_BidirectionalIterator1 __first1
,
618 _BidirectionalIterator1 __last1
,
619 _BidirectionalIterator2 __first2
,
620 _BidirectionalIterator2 __last2
,
621 bidirectional_iterator_tag
, bidirectional_iterator_tag
)
623 // concept requirements
624 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
625 _BidirectionalIterator1
>)
626 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
627 _BidirectionalIterator2
>)
629 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
630 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
632 _RevIterator1
__rlast1(__first1
);
633 _RevIterator2
__rlast2(__first2
);
634 _RevIterator1 __rresult
= _GLIBCXX_STD_P::search(_RevIterator1(__last1
),
636 _RevIterator2(__last2
),
639 if (__rresult
== __rlast1
)
643 _BidirectionalIterator1 __result
= __rresult
.base();
644 std::advance(__result
, -std::distance(__first2
, __last2
));
649 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
650 typename _BinaryPredicate
>
651 _BidirectionalIterator1
652 __find_end(_BidirectionalIterator1 __first1
,
653 _BidirectionalIterator1 __last1
,
654 _BidirectionalIterator2 __first2
,
655 _BidirectionalIterator2 __last2
,
656 bidirectional_iterator_tag
, bidirectional_iterator_tag
,
657 _BinaryPredicate __comp
)
659 // concept requirements
660 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
661 _BidirectionalIterator1
>)
662 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
663 _BidirectionalIterator2
>)
665 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
666 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
668 _RevIterator1
__rlast1(__first1
);
669 _RevIterator2
__rlast2(__first2
);
670 _RevIterator1 __rresult
= std::search(_RevIterator1(__last1
), __rlast1
,
671 _RevIterator2(__last2
), __rlast2
,
674 if (__rresult
== __rlast1
)
678 _BidirectionalIterator1 __result
= __rresult
.base();
679 std::advance(__result
, -std::distance(__first2
, __last2
));
685 * @brief Find last matching subsequence in a sequence.
686 * @ingroup non_mutating_algorithms
687 * @param first1 Start of range to search.
688 * @param last1 End of range to search.
689 * @param first2 Start of sequence to match.
690 * @param last2 End of sequence to match.
691 * @return The last iterator @c i in the range
692 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
693 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
694 * such iterator exists.
696 * Searches the range @p [first1,last1) for a sub-sequence that compares
697 * equal value-by-value with the sequence given by @p [first2,last2) and
698 * returns an iterator to the first element of the sub-sequence, or
699 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
700 * last such subsequence contained in [first,last1).
702 * Because the sub-sequence must lie completely within the range
703 * @p [first1,last1) it must start at a position less than
704 * @p last1-(last2-first2) where @p last2-first2 is the length of the
706 * This means that the returned iterator @c i will be in the range
707 * @p [first1,last1-(last2-first2))
709 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
710 inline _ForwardIterator1
711 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
712 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
714 // concept requirements
715 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
716 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
717 __glibcxx_function_requires(_EqualOpConcept
<
718 typename iterator_traits
<_ForwardIterator1
>::value_type
,
719 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
720 __glibcxx_requires_valid_range(__first1
, __last1
);
721 __glibcxx_requires_valid_range(__first2
, __last2
);
723 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
724 std::__iterator_category(__first1
),
725 std::__iterator_category(__first2
));
729 * @brief Find last matching subsequence in a sequence using a predicate.
730 * @ingroup non_mutating_algorithms
731 * @param first1 Start of range to search.
732 * @param last1 End of range to search.
733 * @param first2 Start of sequence to match.
734 * @param last2 End of sequence to match.
735 * @param comp The predicate to use.
736 * @return The last iterator @c i in the range
737 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
738 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
739 * @p last1 if no such iterator exists.
741 * Searches the range @p [first1,last1) for a sub-sequence that compares
742 * equal value-by-value with the sequence given by @p [first2,last2) using
743 * comp as a predicate and returns an iterator to the first element of the
744 * sub-sequence, or @p last1 if the sub-sequence is not found. The
745 * sub-sequence will be the last such subsequence contained in
748 * Because the sub-sequence must lie completely within the range
749 * @p [first1,last1) it must start at a position less than
750 * @p last1-(last2-first2) where @p last2-first2 is the length of the
752 * This means that the returned iterator @c i will be in the range
753 * @p [first1,last1-(last2-first2))
755 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
756 typename _BinaryPredicate
>
757 inline _ForwardIterator1
758 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
759 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
760 _BinaryPredicate __comp
)
762 // concept requirements
763 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
764 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
765 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
766 typename iterator_traits
<_ForwardIterator1
>::value_type
,
767 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
768 __glibcxx_requires_valid_range(__first1
, __last1
);
769 __glibcxx_requires_valid_range(__first2
, __last2
);
771 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
772 std::__iterator_category(__first1
),
773 std::__iterator_category(__first2
),
777 #ifdef __GXX_EXPERIMENTAL_CXX0X__
779 * @brief Checks that a predicate is true for all the elements
781 * @ingroup non_mutating_algorithms
782 * @param first An input iterator.
783 * @param last An input iterator.
784 * @param pred A predicate.
785 * @return True if the check is true, false otherwise.
787 * Returns true if @p pred is true for each element in the range
788 * @p [first,last), and false otherwise.
790 template<typename _InputIterator
, typename _Predicate
>
792 all_of(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
793 { return __last
== std::find_if_not(__first
, __last
, __pred
); }
796 * @brief Checks that a predicate is false for all the elements
798 * @ingroup non_mutating_algorithms
799 * @param first An input iterator.
800 * @param last An input iterator.
801 * @param pred A predicate.
802 * @return True if the check is true, false otherwise.
804 * Returns true if @p pred is false for each element in the range
805 * @p [first,last), and false otherwise.
807 template<typename _InputIterator
, typename _Predicate
>
809 none_of(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
810 { return __last
== _GLIBCXX_STD_P::find_if(__first
, __last
, __pred
); }
813 * @brief Checks that a predicate is false for at least an element
815 * @ingroup non_mutating_algorithms
816 * @param first An input iterator.
817 * @param last An input iterator.
818 * @param pred A predicate.
819 * @return True if the check is true, false otherwise.
821 * Returns true if an element exists in the range @p [first,last) such that
822 * @p pred is true, and false otherwise.
824 template<typename _InputIterator
, typename _Predicate
>
826 any_of(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
827 { return !std::none_of(__first
, __last
, __pred
); }
830 * @brief Find the first element in a sequence for which a
831 * predicate is false.
832 * @ingroup non_mutating_algorithms
833 * @param first An input iterator.
834 * @param last An input iterator.
835 * @param pred A predicate.
836 * @return The first iterator @c i in the range @p [first,last)
837 * such that @p pred(*i) is false, or @p last if no such iterator exists.
839 template<typename _InputIterator
, typename _Predicate
>
840 inline _InputIterator
841 find_if_not(_InputIterator __first
, _InputIterator __last
,
844 // concept requirements
845 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
846 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
847 typename iterator_traits
<_InputIterator
>::value_type
>)
848 __glibcxx_requires_valid_range(__first
, __last
);
849 return std::__find_if_not(__first
, __last
, __pred
,
850 std::__iterator_category(__first
));
854 * @brief Checks whether the sequence is partitioned.
855 * @ingroup mutating_algorithms
856 * @param first An input iterator.
857 * @param last An input iterator.
858 * @param pred A predicate.
859 * @return True if the range @p [first,last) is partioned by @p pred,
860 * i.e. if all elements that satisfy @p pred appear before those that
863 template<typename _InputIterator
, typename _Predicate
>
865 is_partitioned(_InputIterator __first
, _InputIterator __last
,
868 __first
= std::find_if_not(__first
, __last
, __pred
);
869 return std::none_of(__first
, __last
, __pred
);
873 * @brief Find the partition point of a partitioned range.
874 * @ingroup mutating_algorithms
875 * @param first An iterator.
876 * @param last Another iterator.
877 * @param pred A predicate.
878 * @return An iterator @p mid such that @p all_of(first, mid, pred)
879 * and @p none_of(mid, last, pred) are both true.
881 template<typename _ForwardIterator
, typename _Predicate
>
883 partition_point(_ForwardIterator __first
, _ForwardIterator __last
,
886 // concept requirements
887 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
888 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
889 typename iterator_traits
<_ForwardIterator
>::value_type
>)
891 // A specific debug-mode test will be necessary...
892 __glibcxx_requires_valid_range(__first
, __last
);
894 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
897 _DistanceType __len
= std::distance(__first
, __last
);
898 _DistanceType __half
;
899 _ForwardIterator __middle
;
905 std::advance(__middle
, __half
);
906 if (__pred(*__middle
))
910 __len
= __len
- __half
- 1;
921 * @brief Copy a sequence, removing elements of a given value.
922 * @ingroup mutating_algorithms
923 * @param first An input iterator.
924 * @param last An input iterator.
925 * @param result An output iterator.
926 * @param value The value to be removed.
927 * @return An iterator designating the end of the resulting sequence.
929 * Copies each element in the range @p [first,last) not equal to @p value
930 * to the range beginning at @p result.
931 * remove_copy() is stable, so the relative order of elements that are
932 * copied is unchanged.
934 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
936 remove_copy(_InputIterator __first
, _InputIterator __last
,
937 _OutputIterator __result
, const _Tp
& __value
)
939 // concept requirements
940 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
941 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
942 typename iterator_traits
<_InputIterator
>::value_type
>)
943 __glibcxx_function_requires(_EqualOpConcept
<
944 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
945 __glibcxx_requires_valid_range(__first
, __last
);
947 for (; __first
!= __last
; ++__first
)
948 if (!(*__first
== __value
))
950 *__result
= *__first
;
957 * @brief Copy a sequence, removing elements for which a predicate is true.
958 * @ingroup mutating_algorithms
959 * @param first An input iterator.
960 * @param last An input iterator.
961 * @param result An output iterator.
962 * @param pred A predicate.
963 * @return An iterator designating the end of the resulting sequence.
965 * Copies each element in the range @p [first,last) for which
966 * @p pred returns false to the range beginning at @p result.
968 * remove_copy_if() is stable, so the relative order of elements that are
969 * copied is unchanged.
971 template<typename _InputIterator
, typename _OutputIterator
,
974 remove_copy_if(_InputIterator __first
, _InputIterator __last
,
975 _OutputIterator __result
, _Predicate __pred
)
977 // concept requirements
978 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
979 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
980 typename iterator_traits
<_InputIterator
>::value_type
>)
981 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
982 typename iterator_traits
<_InputIterator
>::value_type
>)
983 __glibcxx_requires_valid_range(__first
, __last
);
985 for (; __first
!= __last
; ++__first
)
986 if (!bool(__pred(*__first
)))
988 *__result
= *__first
;
994 #ifdef __GXX_EXPERIMENTAL_CXX0X__
996 * @brief Copy the elements of a sequence for which a predicate is true.
997 * @ingroup mutating_algorithms
998 * @param first An input iterator.
999 * @param last An input iterator.
1000 * @param result An output iterator.
1001 * @param pred A predicate.
1002 * @return An iterator designating the end of the resulting sequence.
1004 * Copies each element in the range @p [first,last) for which
1005 * @p pred returns true to the range beginning at @p result.
1007 * copy_if() is stable, so the relative order of elements that are
1008 * copied is unchanged.
1010 template<typename _InputIterator
, typename _OutputIterator
,
1011 typename _Predicate
>
1013 copy_if(_InputIterator __first
, _InputIterator __last
,
1014 _OutputIterator __result
, _Predicate __pred
)
1016 // concept requirements
1017 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1018 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1019 typename iterator_traits
<_InputIterator
>::value_type
>)
1020 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1021 typename iterator_traits
<_InputIterator
>::value_type
>)
1022 __glibcxx_requires_valid_range(__first
, __last
);
1024 for (; __first
!= __last
; ++__first
)
1025 if (__pred(*__first
))
1027 *__result
= *__first
;
1034 template<typename _InputIterator
, typename _Size
, typename _OutputIterator
>
1036 __copy_n(_InputIterator __first
, _Size __n
,
1037 _OutputIterator __result
, input_iterator_tag
)
1039 for (; __n
> 0; --__n
)
1041 *__result
= *__first
;
1048 template<typename _RandomAccessIterator
, typename _Size
,
1049 typename _OutputIterator
>
1050 inline _OutputIterator
1051 __copy_n(_RandomAccessIterator __first
, _Size __n
,
1052 _OutputIterator __result
, random_access_iterator_tag
)
1053 { return std::copy(__first
, __first
+ __n
, __result
); }
1056 * @brief Copies the range [first,first+n) into [result,result+n).
1057 * @ingroup mutating_algorithms
1058 * @param first An input iterator.
1059 * @param n The number of elements to copy.
1060 * @param result An output iterator.
1063 * This inline function will boil down to a call to @c memmove whenever
1064 * possible. Failing that, if random access iterators are passed, then the
1065 * loop count will be known (and therefore a candidate for compiler
1066 * optimizations such as unrolling).
1068 template<typename _InputIterator
, typename _Size
, typename _OutputIterator
>
1069 inline _OutputIterator
1070 copy_n(_InputIterator __first
, _Size __n
, _OutputIterator __result
)
1072 // concept requirements
1073 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1074 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1075 typename iterator_traits
<_InputIterator
>::value_type
>)
1077 return std::__copy_n(__first
, __n
, __result
,
1078 std::__iterator_category(__first
));
1082 * @brief Copy the elements of a sequence to separate output sequences
1083 * depending on the truth value of a predicate.
1084 * @ingroup mutating_algorithms
1085 * @param first An input iterator.
1086 * @param last An input iterator.
1087 * @param out_true An output iterator.
1088 * @param out_false An output iterator.
1089 * @param pred A predicate.
1090 * @return A pair designating the ends of the resulting sequences.
1092 * Copies each element in the range @p [first,last) for which
1093 * @p pred returns true to the range beginning at @p out_true
1094 * and each element for which @p pred returns false to @p out_false.
1096 template<typename _InputIterator
, typename _OutputIterator1
,
1097 typename _OutputIterator2
, typename _Predicate
>
1098 pair
<_OutputIterator1
, _OutputIterator2
>
1099 partition_copy(_InputIterator __first
, _InputIterator __last
,
1100 _OutputIterator1 __out_true
, _OutputIterator2 __out_false
,
1103 // concept requirements
1104 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1105 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator1
,
1106 typename iterator_traits
<_InputIterator
>::value_type
>)
1107 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator2
,
1108 typename iterator_traits
<_InputIterator
>::value_type
>)
1109 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1110 typename iterator_traits
<_InputIterator
>::value_type
>)
1111 __glibcxx_requires_valid_range(__first
, __last
);
1113 for (; __first
!= __last
; ++__first
)
1114 if (__pred(*__first
))
1116 *__out_true
= *__first
;
1121 *__out_false
= *__first
;
1125 return pair
<_OutputIterator1
, _OutputIterator2
>(__out_true
, __out_false
);
1130 * @brief Remove elements from a sequence.
1131 * @ingroup mutating_algorithms
1132 * @param first An input iterator.
1133 * @param last An input iterator.
1134 * @param value The value to be removed.
1135 * @return An iterator designating the end of the resulting sequence.
1137 * All elements equal to @p value are removed from the range
1140 * remove() is stable, so the relative order of elements that are
1141 * not removed is unchanged.
1143 * Elements between the end of the resulting sequence and @p last
1144 * are still present, but their value is unspecified.
1146 template<typename _ForwardIterator
, typename _Tp
>
1148 remove(_ForwardIterator __first
, _ForwardIterator __last
,
1151 // concept requirements
1152 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1154 __glibcxx_function_requires(_EqualOpConcept
<
1155 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
1156 __glibcxx_requires_valid_range(__first
, __last
);
1158 __first
= _GLIBCXX_STD_P::find(__first
, __last
, __value
);
1159 if(__first
== __last
)
1161 _ForwardIterator __result
= __first
;
1163 for(; __first
!= __last
; ++__first
)
1164 if(!(*__first
== __value
))
1166 *__result
= _GLIBCXX_MOVE(*__first
);
1173 * @brief Remove elements from a sequence using a predicate.
1174 * @ingroup mutating_algorithms
1175 * @param first A forward iterator.
1176 * @param last A forward iterator.
1177 * @param pred A predicate.
1178 * @return An iterator designating the end of the resulting sequence.
1180 * All elements for which @p pred returns true are removed from the range
1183 * remove_if() is stable, so the relative order of elements that are
1184 * not removed is unchanged.
1186 * Elements between the end of the resulting sequence and @p last
1187 * are still present, but their value is unspecified.
1189 template<typename _ForwardIterator
, typename _Predicate
>
1191 remove_if(_ForwardIterator __first
, _ForwardIterator __last
,
1194 // concept requirements
1195 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1197 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1198 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1199 __glibcxx_requires_valid_range(__first
, __last
);
1201 __first
= _GLIBCXX_STD_P::find_if(__first
, __last
, __pred
);
1202 if(__first
== __last
)
1204 _ForwardIterator __result
= __first
;
1206 for(; __first
!= __last
; ++__first
)
1207 if(!bool(__pred(*__first
)))
1209 *__result
= _GLIBCXX_MOVE(*__first
);
1216 * @brief Remove consecutive duplicate values from a sequence.
1217 * @ingroup mutating_algorithms
1218 * @param first A forward iterator.
1219 * @param last A forward iterator.
1220 * @return An iterator designating the end of the resulting sequence.
1222 * Removes all but the first element from each group of consecutive
1223 * values that compare equal.
1224 * unique() is stable, so the relative order of elements that are
1225 * not removed is unchanged.
1226 * Elements between the end of the resulting sequence and @p last
1227 * are still present, but their value is unspecified.
1229 template<typename _ForwardIterator
>
1231 unique(_ForwardIterator __first
, _ForwardIterator __last
)
1233 // concept requirements
1234 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1236 __glibcxx_function_requires(_EqualityComparableConcept
<
1237 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1238 __glibcxx_requires_valid_range(__first
, __last
);
1240 // Skip the beginning, if already unique.
1241 __first
= _GLIBCXX_STD_P::adjacent_find(__first
, __last
);
1242 if (__first
== __last
)
1245 // Do the real copy work.
1246 _ForwardIterator __dest
= __first
;
1248 while (++__first
!= __last
)
1249 if (!(*__dest
== *__first
))
1250 *++__dest
= _GLIBCXX_MOVE(*__first
);
1255 * @brief Remove consecutive values from a sequence using a predicate.
1256 * @ingroup mutating_algorithms
1257 * @param first A forward iterator.
1258 * @param last A forward iterator.
1259 * @param binary_pred A binary predicate.
1260 * @return An iterator designating the end of the resulting sequence.
1262 * Removes all but the first element from each group of consecutive
1263 * values for which @p binary_pred returns true.
1264 * unique() is stable, so the relative order of elements that are
1265 * not removed is unchanged.
1266 * Elements between the end of the resulting sequence and @p last
1267 * are still present, but their value is unspecified.
1269 template<typename _ForwardIterator
, typename _BinaryPredicate
>
1271 unique(_ForwardIterator __first
, _ForwardIterator __last
,
1272 _BinaryPredicate __binary_pred
)
1274 // concept requirements
1275 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1277 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1278 typename iterator_traits
<_ForwardIterator
>::value_type
,
1279 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1280 __glibcxx_requires_valid_range(__first
, __last
);
1282 // Skip the beginning, if already unique.
1283 __first
= _GLIBCXX_STD_P::adjacent_find(__first
, __last
, __binary_pred
);
1284 if (__first
== __last
)
1287 // Do the real copy work.
1288 _ForwardIterator __dest
= __first
;
1290 while (++__first
!= __last
)
1291 if (!bool(__binary_pred(*__dest
, *__first
)))
1292 *++__dest
= _GLIBCXX_MOVE(*__first
);
1297 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1299 * overloaded for forward iterators and output iterator as result.
1301 template<typename _ForwardIterator
, typename _OutputIterator
>
1303 __unique_copy(_ForwardIterator __first
, _ForwardIterator __last
,
1304 _OutputIterator __result
,
1305 forward_iterator_tag
, output_iterator_tag
)
1307 // concept requirements -- taken care of in dispatching function
1308 _ForwardIterator __next
= __first
;
1309 *__result
= *__first
;
1310 while (++__next
!= __last
)
1311 if (!(*__first
== *__next
))
1314 *++__result
= *__first
;
1320 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1322 * overloaded for input iterators and output iterator as result.
1324 template<typename _InputIterator
, typename _OutputIterator
>
1326 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1327 _OutputIterator __result
,
1328 input_iterator_tag
, output_iterator_tag
)
1330 // concept requirements -- taken care of in dispatching function
1331 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1332 *__result
= __value
;
1333 while (++__first
!= __last
)
1334 if (!(__value
== *__first
))
1337 *++__result
= __value
;
1343 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1345 * overloaded for input iterators and forward iterator as result.
1347 template<typename _InputIterator
, typename _ForwardIterator
>
1349 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1350 _ForwardIterator __result
,
1351 input_iterator_tag
, forward_iterator_tag
)
1353 // concept requirements -- taken care of in dispatching function
1354 *__result
= *__first
;
1355 while (++__first
!= __last
)
1356 if (!(*__result
== *__first
))
1357 *++__result
= *__first
;
1362 * This is an uglified
1363 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1365 * overloaded for forward iterators and output iterator as result.
1367 template<typename _ForwardIterator
, typename _OutputIterator
,
1368 typename _BinaryPredicate
>
1370 __unique_copy(_ForwardIterator __first
, _ForwardIterator __last
,
1371 _OutputIterator __result
, _BinaryPredicate __binary_pred
,
1372 forward_iterator_tag
, output_iterator_tag
)
1374 // concept requirements -- iterators already checked
1375 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1376 typename iterator_traits
<_ForwardIterator
>::value_type
,
1377 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1379 _ForwardIterator __next
= __first
;
1380 *__result
= *__first
;
1381 while (++__next
!= __last
)
1382 if (!bool(__binary_pred(*__first
, *__next
)))
1385 *++__result
= *__first
;
1391 * This is an uglified
1392 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1394 * overloaded for input iterators and output iterator as result.
1396 template<typename _InputIterator
, typename _OutputIterator
,
1397 typename _BinaryPredicate
>
1399 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1400 _OutputIterator __result
, _BinaryPredicate __binary_pred
,
1401 input_iterator_tag
, output_iterator_tag
)
1403 // concept requirements -- iterators already checked
1404 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1405 typename iterator_traits
<_InputIterator
>::value_type
,
1406 typename iterator_traits
<_InputIterator
>::value_type
>)
1408 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1409 *__result
= __value
;
1410 while (++__first
!= __last
)
1411 if (!bool(__binary_pred(__value
, *__first
)))
1414 *++__result
= __value
;
1420 * This is an uglified
1421 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1423 * overloaded for input iterators and forward iterator as result.
1425 template<typename _InputIterator
, typename _ForwardIterator
,
1426 typename _BinaryPredicate
>
1428 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1429 _ForwardIterator __result
, _BinaryPredicate __binary_pred
,
1430 input_iterator_tag
, forward_iterator_tag
)
1432 // concept requirements -- iterators already checked
1433 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1434 typename iterator_traits
<_ForwardIterator
>::value_type
,
1435 typename iterator_traits
<_InputIterator
>::value_type
>)
1437 *__result
= *__first
;
1438 while (++__first
!= __last
)
1439 if (!bool(__binary_pred(*__result
, *__first
)))
1440 *++__result
= *__first
;
1445 * This is an uglified reverse(_BidirectionalIterator,
1446 * _BidirectionalIterator)
1447 * overloaded for bidirectional iterators.
1449 template<typename _BidirectionalIterator
>
1451 __reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1452 bidirectional_iterator_tag
)
1455 if (__first
== __last
|| __first
== --__last
)
1459 std::iter_swap(__first
, __last
);
1465 * This is an uglified reverse(_BidirectionalIterator,
1466 * _BidirectionalIterator)
1467 * overloaded for random access iterators.
1469 template<typename _RandomAccessIterator
>
1471 __reverse(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1472 random_access_iterator_tag
)
1474 if (__first
== __last
)
1477 while (__first
< __last
)
1479 std::iter_swap(__first
, __last
);
1486 * @brief Reverse a sequence.
1487 * @ingroup mutating_algorithms
1488 * @param first A bidirectional iterator.
1489 * @param last A bidirectional iterator.
1490 * @return reverse() returns no value.
1492 * Reverses the order of the elements in the range @p [first,last),
1493 * so that the first element becomes the last etc.
1494 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1495 * swaps @p *(first+i) and @p *(last-(i+1))
1497 template<typename _BidirectionalIterator
>
1499 reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
)
1501 // concept requirements
1502 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1503 _BidirectionalIterator
>)
1504 __glibcxx_requires_valid_range(__first
, __last
);
1505 std::__reverse(__first
, __last
, std::__iterator_category(__first
));
1509 * @brief Copy a sequence, reversing its elements.
1510 * @ingroup mutating_algorithms
1511 * @param first A bidirectional iterator.
1512 * @param last A bidirectional iterator.
1513 * @param result An output iterator.
1514 * @return An iterator designating the end of the resulting sequence.
1516 * Copies the elements in the range @p [first,last) to the range
1517 * @p [result,result+(last-first)) such that the order of the
1518 * elements is reversed.
1519 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1520 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1521 * The ranges @p [first,last) and @p [result,result+(last-first))
1524 template<typename _BidirectionalIterator
, typename _OutputIterator
>
1526 reverse_copy(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1527 _OutputIterator __result
)
1529 // concept requirements
1530 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
1531 _BidirectionalIterator
>)
1532 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1533 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
1534 __glibcxx_requires_valid_range(__first
, __last
);
1536 while (__first
!= __last
)
1539 *__result
= *__last
;
1546 * This is a helper function for the rotate algorithm specialized on RAIs.
1547 * It returns the greatest common divisor of two integer values.
1549 template<typename _EuclideanRingElement
>
1550 _EuclideanRingElement
1551 __gcd(_EuclideanRingElement __m
, _EuclideanRingElement __n
)
1555 _EuclideanRingElement __t
= __m
% __n
;
1562 /// This is a helper function for the rotate algorithm.
1563 template<typename _ForwardIterator
>
1565 __rotate(_ForwardIterator __first
,
1566 _ForwardIterator __middle
,
1567 _ForwardIterator __last
,
1568 forward_iterator_tag
)
1570 if (__first
== __middle
|| __last
== __middle
)
1573 _ForwardIterator __first2
= __middle
;
1576 std::iter_swap(__first
, __first2
);
1579 if (__first
== __middle
)
1580 __middle
= __first2
;
1582 while (__first2
!= __last
);
1584 __first2
= __middle
;
1586 while (__first2
!= __last
)
1588 std::iter_swap(__first
, __first2
);
1591 if (__first
== __middle
)
1592 __middle
= __first2
;
1593 else if (__first2
== __last
)
1594 __first2
= __middle
;
1598 /// This is a helper function for the rotate algorithm.
1599 template<typename _BidirectionalIterator
>
1601 __rotate(_BidirectionalIterator __first
,
1602 _BidirectionalIterator __middle
,
1603 _BidirectionalIterator __last
,
1604 bidirectional_iterator_tag
)
1606 // concept requirements
1607 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1608 _BidirectionalIterator
>)
1610 if (__first
== __middle
|| __last
== __middle
)
1613 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1614 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1616 while (__first
!= __middle
&& __middle
!= __last
)
1618 std::iter_swap(__first
, --__last
);
1622 if (__first
== __middle
)
1623 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1625 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1628 /// This is a helper function for the rotate algorithm.
1629 template<typename _RandomAccessIterator
>
1631 __rotate(_RandomAccessIterator __first
,
1632 _RandomAccessIterator __middle
,
1633 _RandomAccessIterator __last
,
1634 random_access_iterator_tag
)
1636 // concept requirements
1637 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1638 _RandomAccessIterator
>)
1640 if (__first
== __middle
|| __last
== __middle
)
1643 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
1645 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
1648 _Distance __n
= __last
- __first
;
1649 _Distance __k
= __middle
- __first
;
1651 if (__k
== __n
- __k
)
1653 std::swap_ranges(__first
, __middle
, __middle
);
1657 _RandomAccessIterator __p
= __first
;
1661 if (__k
< __n
- __k
)
1663 if (__is_pod(_ValueType
) && __k
== 1)
1665 _ValueType __t
= _GLIBCXX_MOVE(*__p
);
1666 _GLIBCXX_MOVE3(__p
+ 1, __p
+ __n
, __p
);
1667 *(__p
+ __n
- 1) = _GLIBCXX_MOVE(__t
);
1670 _RandomAccessIterator __q
= __p
+ __k
;
1671 for (_Distance __i
= 0; __i
< __n
- __k
; ++ __i
)
1673 std::iter_swap(__p
, __q
);
1680 std::swap(__n
, __k
);
1686 if (__is_pod(_ValueType
) && __k
== 1)
1688 _ValueType __t
= _GLIBCXX_MOVE(*(__p
+ __n
- 1));
1689 _GLIBCXX_MOVE_BACKWARD3(__p
, __p
+ __n
- 1, __p
+ __n
);
1690 *__p
= _GLIBCXX_MOVE(__t
);
1693 _RandomAccessIterator __q
= __p
+ __n
;
1695 for (_Distance __i
= 0; __i
< __n
- __k
; ++ __i
)
1699 std::iter_swap(__p
, __q
);
1704 std::swap(__n
, __k
);
1710 * @brief Rotate the elements of a sequence.
1711 * @ingroup mutating_algorithms
1712 * @param first A forward iterator.
1713 * @param middle A forward iterator.
1714 * @param last A forward iterator.
1717 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1718 * positions so that the element at @p middle is moved to @p first, the
1719 * element at @p middle+1 is moved to @first+1 and so on for each element
1720 * in the range @p [first,last).
1722 * This effectively swaps the ranges @p [first,middle) and
1725 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1726 * each @p n in the range @p [0,last-first).
1728 template<typename _ForwardIterator
>
1730 rotate(_ForwardIterator __first
, _ForwardIterator __middle
,
1731 _ForwardIterator __last
)
1733 // concept requirements
1734 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1736 __glibcxx_requires_valid_range(__first
, __middle
);
1737 __glibcxx_requires_valid_range(__middle
, __last
);
1739 typedef typename iterator_traits
<_ForwardIterator
>::iterator_category
1741 std::__rotate(__first
, __middle
, __last
, _IterType());
1745 * @brief Copy a sequence, rotating its elements.
1746 * @ingroup mutating_algorithms
1747 * @param first A forward iterator.
1748 * @param middle A forward iterator.
1749 * @param last A forward iterator.
1750 * @param result An output iterator.
1751 * @return An iterator designating the end of the resulting sequence.
1753 * Copies the elements of the range @p [first,last) to the range
1754 * beginning at @result, rotating the copied elements by @p (middle-first)
1755 * positions so that the element at @p middle is moved to @p result, the
1756 * element at @p middle+1 is moved to @result+1 and so on for each element
1757 * in the range @p [first,last).
1759 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1760 * each @p n in the range @p [0,last-first).
1762 template<typename _ForwardIterator
, typename _OutputIterator
>
1764 rotate_copy(_ForwardIterator __first
, _ForwardIterator __middle
,
1765 _ForwardIterator __last
, _OutputIterator __result
)
1767 // concept requirements
1768 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1769 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1770 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1771 __glibcxx_requires_valid_range(__first
, __middle
);
1772 __glibcxx_requires_valid_range(__middle
, __last
);
1774 return std::copy(__first
, __middle
,
1775 std::copy(__middle
, __last
, __result
));
1778 /// This is a helper function...
1779 template<typename _ForwardIterator
, typename _Predicate
>
1781 __partition(_ForwardIterator __first
, _ForwardIterator __last
,
1782 _Predicate __pred
, forward_iterator_tag
)
1784 if (__first
== __last
)
1787 while (__pred(*__first
))
1788 if (++__first
== __last
)
1791 _ForwardIterator __next
= __first
;
1793 while (++__next
!= __last
)
1794 if (__pred(*__next
))
1796 std::iter_swap(__first
, __next
);
1803 /// This is a helper function...
1804 template<typename _BidirectionalIterator
, typename _Predicate
>
1805 _BidirectionalIterator
1806 __partition(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1807 _Predicate __pred
, bidirectional_iterator_tag
)
1812 if (__first
== __last
)
1814 else if (__pred(*__first
))
1820 if (__first
== __last
)
1822 else if (!bool(__pred(*__last
)))
1826 std::iter_swap(__first
, __last
);
1833 /// This is a helper function...
1834 template<typename _ForwardIterator
, typename _Predicate
, typename _Distance
>
1836 __inplace_stable_partition(_ForwardIterator __first
,
1837 _ForwardIterator __last
,
1838 _Predicate __pred
, _Distance __len
)
1841 return __pred(*__first
) ? __last
: __first
;
1842 _ForwardIterator __middle
= __first
;
1843 std::advance(__middle
, __len
/ 2);
1844 _ForwardIterator __begin
= std::__inplace_stable_partition(__first
,
1848 _ForwardIterator __end
= std::__inplace_stable_partition(__middle
, __last
,
1852 std::rotate(__begin
, __middle
, __end
);
1853 std::advance(__begin
, std::distance(__middle
, __end
));
1857 /// This is a helper function...
1858 template<typename _ForwardIterator
, typename _Pointer
, typename _Predicate
,
1861 __stable_partition_adaptive(_ForwardIterator __first
,
1862 _ForwardIterator __last
,
1863 _Predicate __pred
, _Distance __len
,
1865 _Distance __buffer_size
)
1867 if (__len
<= __buffer_size
)
1869 _ForwardIterator __result1
= __first
;
1870 _Pointer __result2
= __buffer
;
1871 for (; __first
!= __last
; ++__first
)
1872 if (__pred(*__first
))
1874 *__result1
= _GLIBCXX_MOVE(*__first
);
1879 *__result2
= _GLIBCXX_MOVE(*__first
);
1882 _GLIBCXX_MOVE3(__buffer
, __result2
, __result1
);
1887 _ForwardIterator __middle
= __first
;
1888 std::advance(__middle
, __len
/ 2);
1889 _ForwardIterator __begin
=
1890 std::__stable_partition_adaptive(__first
, __middle
, __pred
,
1891 __len
/ 2, __buffer
,
1893 _ForwardIterator __end
=
1894 std::__stable_partition_adaptive(__middle
, __last
, __pred
,
1896 __buffer
, __buffer_size
);
1897 std::rotate(__begin
, __middle
, __end
);
1898 std::advance(__begin
, std::distance(__middle
, __end
));
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 if (__first
== __last
)
1936 typedef typename iterator_traits
<_ForwardIterator
>::value_type
1938 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
1941 _Temporary_buffer
<_ForwardIterator
, _ValueType
> __buf(__first
,
1943 if (__buf
.size() > 0)
1945 std::__stable_partition_adaptive(__first
, __last
, __pred
,
1946 _DistanceType(__buf
.requested_size()),
1948 _DistanceType(__buf
.size()));
1951 std::__inplace_stable_partition(__first
, __last
, __pred
,
1952 _DistanceType(__buf
.requested_size()));
1956 /// This is a helper function for the sort routines.
1957 template<typename _RandomAccessIterator
>
1959 __heap_select(_RandomAccessIterator __first
,
1960 _RandomAccessIterator __middle
,
1961 _RandomAccessIterator __last
)
1963 std::make_heap(__first
, __middle
);
1964 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
1965 if (*__i
< *__first
)
1966 std::__pop_heap(__first
, __middle
, __i
);
1969 /// This is a helper function for the sort routines.
1970 template<typename _RandomAccessIterator
, typename _Compare
>
1972 __heap_select(_RandomAccessIterator __first
,
1973 _RandomAccessIterator __middle
,
1974 _RandomAccessIterator __last
, _Compare __comp
)
1976 std::make_heap(__first
, __middle
, __comp
);
1977 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
1978 if (__comp(*__i
, *__first
))
1979 std::__pop_heap(__first
, __middle
, __i
, __comp
);
1985 * @brief Copy the smallest elements of a sequence.
1986 * @ingroup sorting_algorithms
1987 * @param first An iterator.
1988 * @param last Another iterator.
1989 * @param result_first A random-access iterator.
1990 * @param result_last Another random-access iterator.
1991 * @return An iterator indicating the end of the resulting sequence.
1993 * Copies and sorts the smallest N values from the range @p [first,last)
1994 * to the range beginning at @p result_first, where the number of
1995 * elements to be copied, @p N, is the smaller of @p (last-first) and
1996 * @p (result_last-result_first).
1997 * After the sort if @p i and @j are iterators in the range
1998 * @p [result_first,result_first+N) such that @i precedes @j then
1999 * @p *j<*i is false.
2000 * The value returned is @p result_first+N.
2002 template<typename _InputIterator
, typename _RandomAccessIterator
>
2003 _RandomAccessIterator
2004 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2005 _RandomAccessIterator __result_first
,
2006 _RandomAccessIterator __result_last
)
2008 typedef typename iterator_traits
<_InputIterator
>::value_type
2010 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2012 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2015 // concept requirements
2016 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2017 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2019 __glibcxx_function_requires(_LessThanOpConcept
<_InputValueType
,
2021 __glibcxx_function_requires(_LessThanComparableConcept
<_OutputValueType
>)
2022 __glibcxx_requires_valid_range(__first
, __last
);
2023 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2025 if (__result_first
== __result_last
)
2026 return __result_last
;
2027 _RandomAccessIterator __result_real_last
= __result_first
;
2028 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2030 *__result_real_last
= *__first
;
2031 ++__result_real_last
;
2034 std::make_heap(__result_first
, __result_real_last
);
2035 while (__first
!= __last
)
2037 if (*__first
< *__result_first
)
2038 std::__adjust_heap(__result_first
, _DistanceType(0),
2039 _DistanceType(__result_real_last
2041 _InputValueType(*__first
));
2044 std::sort_heap(__result_first
, __result_real_last
);
2045 return __result_real_last
;
2049 * @brief Copy the smallest elements of a sequence using a predicate for
2051 * @ingroup sorting_algorithms
2052 * @param first An input iterator.
2053 * @param last Another input iterator.
2054 * @param result_first A random-access iterator.
2055 * @param result_last Another random-access iterator.
2056 * @param comp A comparison functor.
2057 * @return An iterator indicating the end of the resulting sequence.
2059 * Copies and sorts the smallest N values from the range @p [first,last)
2060 * to the range beginning at @p result_first, where the number of
2061 * elements to be copied, @p N, is the smaller of @p (last-first) and
2062 * @p (result_last-result_first).
2063 * After the sort if @p i and @j are iterators in the range
2064 * @p [result_first,result_first+N) such that @i precedes @j then
2065 * @p comp(*j,*i) is false.
2066 * The value returned is @p result_first+N.
2068 template<typename _InputIterator
, typename _RandomAccessIterator
, typename _Compare
>
2069 _RandomAccessIterator
2070 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2071 _RandomAccessIterator __result_first
,
2072 _RandomAccessIterator __result_last
,
2075 typedef typename iterator_traits
<_InputIterator
>::value_type
2077 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2079 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2082 // concept requirements
2083 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2084 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2085 _RandomAccessIterator
>)
2086 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2088 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2089 _InputValueType
, _OutputValueType
>)
2090 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2091 _OutputValueType
, _OutputValueType
>)
2092 __glibcxx_requires_valid_range(__first
, __last
);
2093 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2095 if (__result_first
== __result_last
)
2096 return __result_last
;
2097 _RandomAccessIterator __result_real_last
= __result_first
;
2098 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2100 *__result_real_last
= *__first
;
2101 ++__result_real_last
;
2104 std::make_heap(__result_first
, __result_real_last
, __comp
);
2105 while (__first
!= __last
)
2107 if (__comp(*__first
, *__result_first
))
2108 std::__adjust_heap(__result_first
, _DistanceType(0),
2109 _DistanceType(__result_real_last
2111 _InputValueType(*__first
),
2115 std::sort_heap(__result_first
, __result_real_last
, __comp
);
2116 return __result_real_last
;
2119 /// This is a helper function for the sort routine.
2120 template<typename _RandomAccessIterator
>
2122 __unguarded_linear_insert(_RandomAccessIterator __last
)
2124 typename iterator_traits
<_RandomAccessIterator
>::value_type
2125 __val
= _GLIBCXX_MOVE(*__last
);
2126 _RandomAccessIterator __next
= __last
;
2128 while (__val
< *__next
)
2130 *__last
= _GLIBCXX_MOVE(*__next
);
2134 *__last
= _GLIBCXX_MOVE(__val
);
2137 /// This is a helper function for the sort routine.
2138 template<typename _RandomAccessIterator
, typename _Compare
>
2140 __unguarded_linear_insert(_RandomAccessIterator __last
,
2143 typename iterator_traits
<_RandomAccessIterator
>::value_type
2144 __val
= _GLIBCXX_MOVE(*__last
);
2145 _RandomAccessIterator __next
= __last
;
2147 while (__comp(__val
, *__next
))
2149 *__last
= _GLIBCXX_MOVE(*__next
);
2153 *__last
= _GLIBCXX_MOVE(__val
);
2156 /// This is a helper function for the sort routine.
2157 template<typename _RandomAccessIterator
>
2159 __insertion_sort(_RandomAccessIterator __first
,
2160 _RandomAccessIterator __last
)
2162 if (__first
== __last
)
2165 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2167 if (*__i
< *__first
)
2169 typename iterator_traits
<_RandomAccessIterator
>::value_type
2170 __val
= _GLIBCXX_MOVE(*__i
);
2171 _GLIBCXX_MOVE_BACKWARD3(__first
, __i
, __i
+ 1);
2172 *__first
= _GLIBCXX_MOVE(__val
);
2175 std::__unguarded_linear_insert(__i
);
2179 /// This is a helper function for the sort routine.
2180 template<typename _RandomAccessIterator
, typename _Compare
>
2182 __insertion_sort(_RandomAccessIterator __first
,
2183 _RandomAccessIterator __last
, _Compare __comp
)
2185 if (__first
== __last
) return;
2187 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2189 if (__comp(*__i
, *__first
))
2191 typename iterator_traits
<_RandomAccessIterator
>::value_type
2192 __val
= _GLIBCXX_MOVE(*__i
);
2193 _GLIBCXX_MOVE_BACKWARD3(__first
, __i
, __i
+ 1);
2194 *__first
= _GLIBCXX_MOVE(__val
);
2197 std::__unguarded_linear_insert(__i
, __comp
);
2201 /// This is a helper function for the sort routine.
2202 template<typename _RandomAccessIterator
>
2204 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2205 _RandomAccessIterator __last
)
2207 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2210 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2211 std::__unguarded_linear_insert(__i
);
2214 /// This is a helper function for the sort routine.
2215 template<typename _RandomAccessIterator
, typename _Compare
>
2217 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2218 _RandomAccessIterator __last
, _Compare __comp
)
2220 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2223 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2224 std::__unguarded_linear_insert(__i
, __comp
);
2229 * This controls some aspect of the sort routines.
2231 enum { _S_threshold
= 16 };
2233 /// This is a helper function for the sort routine.
2234 template<typename _RandomAccessIterator
>
2236 __final_insertion_sort(_RandomAccessIterator __first
,
2237 _RandomAccessIterator __last
)
2239 if (__last
- __first
> int(_S_threshold
))
2241 std::__insertion_sort(__first
, __first
+ int(_S_threshold
));
2242 std::__unguarded_insertion_sort(__first
+ int(_S_threshold
), __last
);
2245 std::__insertion_sort(__first
, __last
);
2248 /// This is a helper function for the sort routine.
2249 template<typename _RandomAccessIterator
, typename _Compare
>
2251 __final_insertion_sort(_RandomAccessIterator __first
,
2252 _RandomAccessIterator __last
, _Compare __comp
)
2254 if (__last
- __first
> int(_S_threshold
))
2256 std::__insertion_sort(__first
, __first
+ int(_S_threshold
), __comp
);
2257 std::__unguarded_insertion_sort(__first
+ int(_S_threshold
), __last
,
2261 std::__insertion_sort(__first
, __last
, __comp
);
2264 /// This is a helper function...
2265 template<typename _RandomAccessIterator
, typename _Tp
>
2266 _RandomAccessIterator
2267 __unguarded_partition(_RandomAccessIterator __first
,
2268 _RandomAccessIterator __last
, const _Tp
& __pivot
)
2272 while (*__first
< __pivot
)
2275 while (__pivot
< *__last
)
2277 if (!(__first
< __last
))
2279 std::iter_swap(__first
, __last
);
2284 /// This is a helper function...
2285 template<typename _RandomAccessIterator
, typename _Tp
, typename _Compare
>
2286 _RandomAccessIterator
2287 __unguarded_partition(_RandomAccessIterator __first
,
2288 _RandomAccessIterator __last
,
2289 const _Tp
& __pivot
, _Compare __comp
)
2293 while (__comp(*__first
, __pivot
))
2296 while (__comp(__pivot
, *__last
))
2298 if (!(__first
< __last
))
2300 std::iter_swap(__first
, __last
);
2305 /// This is a helper function...
2306 template<typename _RandomAccessIterator
>
2307 inline _RandomAccessIterator
2308 __unguarded_partition_pivot(_RandomAccessIterator __first
,
2309 _RandomAccessIterator __last
)
2311 _RandomAccessIterator __mid
= __first
+ (__last
- __first
) / 2;
2312 std::__move_median_first(__first
, __mid
, (__last
- 1));
2313 return std::__unguarded_partition(__first
+ 1, __last
, *__first
);
2317 /// This is a helper function...
2318 template<typename _RandomAccessIterator
, typename _Compare
>
2319 inline _RandomAccessIterator
2320 __unguarded_partition_pivot(_RandomAccessIterator __first
,
2321 _RandomAccessIterator __last
, _Compare __comp
)
2323 _RandomAccessIterator __mid
= __first
+ (__last
- __first
) / 2;
2324 std::__move_median_first(__first
, __mid
, (__last
- 1), __comp
);
2325 return std::__unguarded_partition(__first
+ 1, __last
, *__first
, __comp
);
2328 /// This is a helper function for the sort routine.
2329 template<typename _RandomAccessIterator
, typename _Size
>
2331 __introsort_loop(_RandomAccessIterator __first
,
2332 _RandomAccessIterator __last
,
2333 _Size __depth_limit
)
2335 while (__last
- __first
> int(_S_threshold
))
2337 if (__depth_limit
== 0)
2339 _GLIBCXX_STD_P::partial_sort(__first
, __last
, __last
);
2343 _RandomAccessIterator __cut
=
2344 std::__unguarded_partition_pivot(__first
, __last
);
2345 std::__introsort_loop(__cut
, __last
, __depth_limit
);
2350 /// This is a helper function for the sort routine.
2351 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
2353 __introsort_loop(_RandomAccessIterator __first
,
2354 _RandomAccessIterator __last
,
2355 _Size __depth_limit
, _Compare __comp
)
2357 while (__last
- __first
> int(_S_threshold
))
2359 if (__depth_limit
== 0)
2361 _GLIBCXX_STD_P::partial_sort(__first
, __last
, __last
, __comp
);
2365 _RandomAccessIterator __cut
=
2366 std::__unguarded_partition_pivot(__first
, __last
, __comp
);
2367 std::__introsort_loop(__cut
, __last
, __depth_limit
, __comp
);
2372 /// This is a helper function for the sort routines. Precondition: __n > 0.
2373 template<typename _Size
>
2378 for (__k
= 0; __n
!= 0; __n
>>= 1)
2385 { return sizeof(int) * __CHAR_BIT__
- 1 - __builtin_clz(__n
); }
2389 { return sizeof(long) * __CHAR_BIT__
- 1 - __builtin_clzl(__n
); }
2393 { return sizeof(long long) * __CHAR_BIT__
- 1 - __builtin_clzll(__n
); }
2397 template<typename _RandomAccessIterator
, typename _Size
>
2399 __introselect(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
2400 _RandomAccessIterator __last
, _Size __depth_limit
)
2402 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2405 while (__last
- __first
> 3)
2407 if (__depth_limit
== 0)
2409 std::__heap_select(__first
, __nth
+ 1, __last
);
2411 // Place the nth largest element in its final position.
2412 std::iter_swap(__first
, __nth
);
2416 _RandomAccessIterator __cut
=
2417 std::__unguarded_partition_pivot(__first
, __last
);
2423 std::__insertion_sort(__first
, __last
);
2426 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
2428 __introselect(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
2429 _RandomAccessIterator __last
, _Size __depth_limit
,
2432 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2435 while (__last
- __first
> 3)
2437 if (__depth_limit
== 0)
2439 std::__heap_select(__first
, __nth
+ 1, __last
, __comp
);
2440 // Place the nth largest element in its final position.
2441 std::iter_swap(__first
, __nth
);
2445 _RandomAccessIterator __cut
=
2446 std::__unguarded_partition_pivot(__first
, __last
, __comp
);
2452 std::__insertion_sort(__first
, __last
, __comp
);
2458 * @brief Finds the first position in which @a val could be inserted
2459 * without changing the ordering.
2460 * @param first An iterator.
2461 * @param last Another iterator.
2462 * @param val The search term.
2463 * @return An iterator pointing to the first element "not less
2464 * than" @a val, or end() if every element is less than
2466 * @ingroup binary_search_algorithms
2468 template<typename _ForwardIterator
, typename _Tp
>
2470 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2473 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2475 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2478 // concept requirements
2479 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2480 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType
, _Tp
>)
2481 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
2483 _DistanceType __len
= std::distance(__first
, __last
);
2484 _DistanceType __half
;
2485 _ForwardIterator __middle
;
2489 __half
= __len
>> 1;
2491 std::advance(__middle
, __half
);
2492 if (*__middle
< __val
)
2496 __len
= __len
- __half
- 1;
2505 * @brief Finds the first position in which @a val could be inserted
2506 * without changing the ordering.
2507 * @ingroup binary_search_algorithms
2508 * @param first An iterator.
2509 * @param last Another iterator.
2510 * @param val The search term.
2511 * @param comp A functor to use for comparisons.
2512 * @return An iterator pointing to the first element "not less than" @a val,
2513 * or end() if every element is less than @a val.
2514 * @ingroup binary_search_algorithms
2516 * The comparison function should have the same effects on ordering as
2517 * the function used for the initial sort.
2519 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2521 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2522 const _Tp
& __val
, _Compare __comp
)
2524 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2526 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2529 // concept requirements
2530 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2531 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2533 __glibcxx_requires_partitioned_lower_pred(__first
, __last
,
2536 _DistanceType __len
= std::distance(__first
, __last
);
2537 _DistanceType __half
;
2538 _ForwardIterator __middle
;
2542 __half
= __len
>> 1;
2544 std::advance(__middle
, __half
);
2545 if (__comp(*__middle
, __val
))
2549 __len
= __len
- __half
- 1;
2558 * @brief Finds the last position in which @a val could be inserted
2559 * without changing the ordering.
2560 * @ingroup binary_search_algorithms
2561 * @param first An iterator.
2562 * @param last Another iterator.
2563 * @param val The search term.
2564 * @return An iterator pointing to the first element greater than @a val,
2565 * or end() if no elements are greater than @a val.
2566 * @ingroup binary_search_algorithms
2568 template<typename _ForwardIterator
, typename _Tp
>
2570 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2573 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2575 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2578 // concept requirements
2579 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2580 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
2581 __glibcxx_requires_partitioned_upper(__first
, __last
, __val
);
2583 _DistanceType __len
= std::distance(__first
, __last
);
2584 _DistanceType __half
;
2585 _ForwardIterator __middle
;
2589 __half
= __len
>> 1;
2591 std::advance(__middle
, __half
);
2592 if (__val
< *__middle
)
2598 __len
= __len
- __half
- 1;
2605 * @brief Finds the last position in which @a val could be inserted
2606 * without changing the ordering.
2607 * @ingroup binary_search_algorithms
2608 * @param first An iterator.
2609 * @param last Another iterator.
2610 * @param val The search term.
2611 * @param comp A functor to use for comparisons.
2612 * @return An iterator pointing to the first element greater than @a val,
2613 * or end() if no elements are greater than @a val.
2614 * @ingroup binary_search_algorithms
2616 * The comparison function should have the same effects on ordering as
2617 * the function used for the initial sort.
2619 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2621 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2622 const _Tp
& __val
, _Compare __comp
)
2624 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2626 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2629 // concept requirements
2630 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2631 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2633 __glibcxx_requires_partitioned_upper_pred(__first
, __last
,
2636 _DistanceType __len
= std::distance(__first
, __last
);
2637 _DistanceType __half
;
2638 _ForwardIterator __middle
;
2642 __half
= __len
>> 1;
2644 std::advance(__middle
, __half
);
2645 if (__comp(__val
, *__middle
))
2651 __len
= __len
- __half
- 1;
2658 * @brief Finds the largest subrange in which @a val could be inserted
2659 * at any place in it without changing the ordering.
2660 * @ingroup binary_search_algorithms
2661 * @param first An iterator.
2662 * @param last Another iterator.
2663 * @param val The search term.
2664 * @return An pair of iterators defining the subrange.
2665 * @ingroup binary_search_algorithms
2667 * This is equivalent to
2669 * std::make_pair(lower_bound(first, last, val),
2670 * upper_bound(first, last, val))
2672 * but does not actually call those functions.
2674 template<typename _ForwardIterator
, typename _Tp
>
2675 pair
<_ForwardIterator
, _ForwardIterator
>
2676 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
2679 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2681 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2684 // concept requirements
2685 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2686 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType
, _Tp
>)
2687 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
2688 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
2689 __glibcxx_requires_partitioned_upper(__first
, __last
, __val
);
2691 _DistanceType __len
= std::distance(__first
, __last
);
2692 _DistanceType __half
;
2693 _ForwardIterator __middle
, __left
, __right
;
2697 __half
= __len
>> 1;
2699 std::advance(__middle
, __half
);
2700 if (*__middle
< __val
)
2704 __len
= __len
- __half
- 1;
2706 else if (__val
< *__middle
)
2710 __left
= std::lower_bound(__first
, __middle
, __val
);
2711 std::advance(__first
, __len
);
2712 __right
= std::upper_bound(++__middle
, __first
, __val
);
2713 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
2716 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
2720 * @brief Finds the largest subrange in which @a val could be inserted
2721 * at any place in it without changing the ordering.
2722 * @param first An iterator.
2723 * @param last Another iterator.
2724 * @param val The search term.
2725 * @param comp A functor to use for comparisons.
2726 * @return An pair of iterators defining the subrange.
2727 * @ingroup binary_search_algorithms
2729 * This is equivalent to
2731 * std::make_pair(lower_bound(first, last, val, comp),
2732 * upper_bound(first, last, val, comp))
2734 * but does not actually call those functions.
2736 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2737 pair
<_ForwardIterator
, _ForwardIterator
>
2738 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
2742 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2744 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2747 // concept requirements
2748 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2749 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2751 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2753 __glibcxx_requires_partitioned_lower_pred(__first
, __last
,
2755 __glibcxx_requires_partitioned_upper_pred(__first
, __last
,
2758 _DistanceType __len
= std::distance(__first
, __last
);
2759 _DistanceType __half
;
2760 _ForwardIterator __middle
, __left
, __right
;
2764 __half
= __len
>> 1;
2766 std::advance(__middle
, __half
);
2767 if (__comp(*__middle
, __val
))
2771 __len
= __len
- __half
- 1;
2773 else if (__comp(__val
, *__middle
))
2777 __left
= std::lower_bound(__first
, __middle
, __val
, __comp
);
2778 std::advance(__first
, __len
);
2779 __right
= std::upper_bound(++__middle
, __first
, __val
, __comp
);
2780 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
2783 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
2787 * @brief Determines whether an element exists in a range.
2788 * @ingroup binary_search_algorithms
2789 * @param first An iterator.
2790 * @param last Another iterator.
2791 * @param val The search term.
2792 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2794 * Note that this does not actually return an iterator to @a val. For
2795 * that, use std::find or a container's specialized find member functions.
2797 template<typename _ForwardIterator
, typename _Tp
>
2799 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
2802 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2805 // concept requirements
2806 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2807 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
2808 __glibcxx_requires_partitioned_lower(__first
, __last
, __val
);
2809 __glibcxx_requires_partitioned_upper(__first
, __last
, __val
);
2811 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
);
2812 return __i
!= __last
&& !(__val
< *__i
);
2816 * @brief Determines whether an element exists in a range.
2817 * @ingroup binary_search_algorithms
2818 * @param first An iterator.
2819 * @param last Another iterator.
2820 * @param val The search term.
2821 * @param comp A functor to use for comparisons.
2822 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2824 * Note that this does not actually return an iterator to @a val. For
2825 * that, use std::find or a container's specialized find member functions.
2827 * The comparison function should have the same effects on ordering as
2828 * the function used for the initial sort.
2830 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2832 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
2833 const _Tp
& __val
, _Compare __comp
)
2835 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2838 // concept requirements
2839 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2840 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2842 __glibcxx_requires_partitioned_lower_pred(__first
, __last
,
2844 __glibcxx_requires_partitioned_upper_pred(__first
, __last
,
2847 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
, __comp
);
2848 return __i
!= __last
&& !bool(__comp(__val
, *__i
));
2853 /// This is a helper function for the merge routines.
2854 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
2855 typename _BidirectionalIterator3
>
2856 _BidirectionalIterator3
2857 __merge_backward(_BidirectionalIterator1 __first1
,
2858 _BidirectionalIterator1 __last1
,
2859 _BidirectionalIterator2 __first2
,
2860 _BidirectionalIterator2 __last2
,
2861 _BidirectionalIterator3 __result
)
2863 if (__first1
== __last1
)
2864 return std::copy_backward(__first2
, __last2
, __result
);
2865 if (__first2
== __last2
)
2866 return std::copy_backward(__first1
, __last1
, __result
);
2871 if (*__last2
< *__last1
)
2873 *--__result
= *__last1
;
2874 if (__first1
== __last1
)
2875 return std::copy_backward(__first2
, ++__last2
, __result
);
2880 *--__result
= *__last2
;
2881 if (__first2
== __last2
)
2882 return std::copy_backward(__first1
, ++__last1
, __result
);
2888 /// This is a helper function for the merge routines.
2889 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
2890 typename _BidirectionalIterator3
, typename _Compare
>
2891 _BidirectionalIterator3
2892 __merge_backward(_BidirectionalIterator1 __first1
,
2893 _BidirectionalIterator1 __last1
,
2894 _BidirectionalIterator2 __first2
,
2895 _BidirectionalIterator2 __last2
,
2896 _BidirectionalIterator3 __result
,
2899 if (__first1
== __last1
)
2900 return std::copy_backward(__first2
, __last2
, __result
);
2901 if (__first2
== __last2
)
2902 return std::copy_backward(__first1
, __last1
, __result
);
2907 if (__comp(*__last2
, *__last1
))
2909 *--__result
= *__last1
;
2910 if (__first1
== __last1
)
2911 return std::copy_backward(__first2
, ++__last2
, __result
);
2916 *--__result
= *__last2
;
2917 if (__first2
== __last2
)
2918 return std::copy_backward(__first1
, ++__last1
, __result
);
2924 /// This is a helper function for the merge routines.
2925 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
2927 _BidirectionalIterator1
2928 __rotate_adaptive(_BidirectionalIterator1 __first
,
2929 _BidirectionalIterator1 __middle
,
2930 _BidirectionalIterator1 __last
,
2931 _Distance __len1
, _Distance __len2
,
2932 _BidirectionalIterator2 __buffer
,
2933 _Distance __buffer_size
)
2935 _BidirectionalIterator2 __buffer_end
;
2936 if (__len1
> __len2
&& __len2
<= __buffer_size
)
2938 __buffer_end
= _GLIBCXX_MOVE3(__middle
, __last
, __buffer
);
2939 _GLIBCXX_MOVE_BACKWARD3(__first
, __middle
, __last
);
2940 return _GLIBCXX_MOVE3(__buffer
, __buffer_end
, __first
);
2942 else if (__len1
<= __buffer_size
)
2944 __buffer_end
= _GLIBCXX_MOVE3(__first
, __middle
, __buffer
);
2945 _GLIBCXX_MOVE3(__middle
, __last
, __first
);
2946 return _GLIBCXX_MOVE_BACKWARD3(__buffer
, __buffer_end
, __last
);
2950 std::rotate(__first
, __middle
, __last
);
2951 std::advance(__first
, std::distance(__middle
, __last
));
2956 /// This is a helper function for the merge routines.
2957 template<typename _BidirectionalIterator
, typename _Distance
,
2960 __merge_adaptive(_BidirectionalIterator __first
,
2961 _BidirectionalIterator __middle
,
2962 _BidirectionalIterator __last
,
2963 _Distance __len1
, _Distance __len2
,
2964 _Pointer __buffer
, _Distance __buffer_size
)
2966 if (__len1
<= __len2
&& __len1
<= __buffer_size
)
2968 _Pointer __buffer_end
= _GLIBCXX_MOVE3(__first
, __middle
, __buffer
);
2969 _GLIBCXX_STD_P::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer
),
2970 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end
),
2971 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle
),
2972 _GLIBCXX_MAKE_MOVE_ITERATOR(__last
),
2975 else if (__len2
<= __buffer_size
)
2977 _Pointer __buffer_end
= _GLIBCXX_MOVE3(__middle
, __last
, __buffer
);
2978 std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first
),
2979 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle
),
2980 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer
),
2981 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end
),
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 _GLIBCXX_STD_P::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__buffer
),
3033 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end
),
3034 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle
),
3035 _GLIBCXX_MAKE_MOVE_ITERATOR(__last
),
3038 else if (__len2
<= __buffer_size
)
3040 _Pointer __buffer_end
= _GLIBCXX_MOVE3(__middle
, __last
, __buffer
);
3041 std::__merge_backward(_GLIBCXX_MAKE_MOVE_ITERATOR(__first
),
3042 _GLIBCXX_MAKE_MOVE_ITERATOR(__middle
),
3043 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer
),
3044 _GLIBCXX_MAKE_MOVE_ITERATOR(__buffer_end
),
3049 _BidirectionalIterator __first_cut
= __first
;
3050 _BidirectionalIterator __second_cut
= __middle
;
3051 _Distance __len11
= 0;
3052 _Distance __len22
= 0;
3053 if (__len1
> __len2
)
3055 __len11
= __len1
/ 2;
3056 std::advance(__first_cut
, __len11
);
3057 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
3059 __len22
= std::distance(__middle
, __second_cut
);
3063 __len22
= __len2
/ 2;
3064 std::advance(__second_cut
, __len22
);
3065 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
3067 __len11
= std::distance(__first
, __first_cut
);
3069 _BidirectionalIterator __new_middle
=
3070 std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
3071 __len1
- __len11
, __len22
, __buffer
,
3073 std::__merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
3074 __len22
, __buffer
, __buffer_size
, __comp
);
3075 std::__merge_adaptive(__new_middle
, __second_cut
, __last
,
3077 __len2
- __len22
, __buffer
,
3078 __buffer_size
, __comp
);
3082 /// This is a helper function for the merge routines.
3083 template<typename _BidirectionalIterator
, typename _Distance
>
3085 __merge_without_buffer(_BidirectionalIterator __first
,
3086 _BidirectionalIterator __middle
,
3087 _BidirectionalIterator __last
,
3088 _Distance __len1
, _Distance __len2
)
3090 if (__len1
== 0 || __len2
== 0)
3092 if (__len1
+ __len2
== 2)
3094 if (*__middle
< *__first
)
3095 std::iter_swap(__first
, __middle
);
3098 _BidirectionalIterator __first_cut
= __first
;
3099 _BidirectionalIterator __second_cut
= __middle
;
3100 _Distance __len11
= 0;
3101 _Distance __len22
= 0;
3102 if (__len1
> __len2
)
3104 __len11
= __len1
/ 2;
3105 std::advance(__first_cut
, __len11
);
3106 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
);
3107 __len22
= std::distance(__middle
, __second_cut
);
3111 __len22
= __len2
/ 2;
3112 std::advance(__second_cut
, __len22
);
3113 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
);
3114 __len11
= std::distance(__first
, __first_cut
);
3116 std::rotate(__first_cut
, __middle
, __second_cut
);
3117 _BidirectionalIterator __new_middle
= __first_cut
;
3118 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
3119 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
3121 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
3122 __len1
- __len11
, __len2
- __len22
);
3125 /// This is a helper function for the merge routines.
3126 template<typename _BidirectionalIterator
, typename _Distance
,
3129 __merge_without_buffer(_BidirectionalIterator __first
,
3130 _BidirectionalIterator __middle
,
3131 _BidirectionalIterator __last
,
3132 _Distance __len1
, _Distance __len2
,
3135 if (__len1
== 0 || __len2
== 0)
3137 if (__len1
+ __len2
== 2)
3139 if (__comp(*__middle
, *__first
))
3140 std::iter_swap(__first
, __middle
);
3143 _BidirectionalIterator __first_cut
= __first
;
3144 _BidirectionalIterator __second_cut
= __middle
;
3145 _Distance __len11
= 0;
3146 _Distance __len22
= 0;
3147 if (__len1
> __len2
)
3149 __len11
= __len1
/ 2;
3150 std::advance(__first_cut
, __len11
);
3151 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
3153 __len22
= std::distance(__middle
, __second_cut
);
3157 __len22
= __len2
/ 2;
3158 std::advance(__second_cut
, __len22
);
3159 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
3161 __len11
= std::distance(__first
, __first_cut
);
3163 std::rotate(__first_cut
, __middle
, __second_cut
);
3164 _BidirectionalIterator __new_middle
= __first_cut
;
3165 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
3166 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
3167 __len11
, __len22
, __comp
);
3168 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
3169 __len1
- __len11
, __len2
- __len22
, __comp
);
3173 * @brief Merges two sorted ranges in place.
3174 * @ingroup sorting_algorithms
3175 * @param first An iterator.
3176 * @param middle Another iterator.
3177 * @param last Another iterator.
3180 * Merges two sorted and consecutive ranges, [first,middle) and
3181 * [middle,last), and puts the result in [first,last). The output will
3182 * be sorted. The sort is @e stable, that is, for equivalent
3183 * elements in the two ranges, elements from the first range will always
3184 * come before elements from the second.
3186 * If enough additional memory is available, this takes (last-first)-1
3187 * comparisons. Otherwise an NlogN algorithm is used, where N is
3188 * distance(first,last).
3190 template<typename _BidirectionalIterator
>
3192 inplace_merge(_BidirectionalIterator __first
,
3193 _BidirectionalIterator __middle
,
3194 _BidirectionalIterator __last
)
3196 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3198 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3201 // concept requirements
3202 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3203 _BidirectionalIterator
>)
3204 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3205 __glibcxx_requires_sorted(__first
, __middle
);
3206 __glibcxx_requires_sorted(__middle
, __last
);
3208 if (__first
== __middle
|| __middle
== __last
)
3211 _DistanceType __len1
= std::distance(__first
, __middle
);
3212 _DistanceType __len2
= std::distance(__middle
, __last
);
3214 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3216 if (__buf
.begin() == 0)
3217 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
, __len2
);
3219 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3220 __buf
.begin(), _DistanceType(__buf
.size()));
3224 * @brief Merges two sorted ranges in place.
3225 * @ingroup sorting_algorithms
3226 * @param first An iterator.
3227 * @param middle Another iterator.
3228 * @param last Another iterator.
3229 * @param comp A functor to use for comparisons.
3232 * Merges two sorted and consecutive ranges, [first,middle) and
3233 * [middle,last), and puts the result in [first,last). The output will
3234 * be sorted. The sort is @e stable, that is, for equivalent
3235 * elements in the two ranges, elements from the first range will always
3236 * come before elements from the second.
3238 * If enough additional memory is available, this takes (last-first)-1
3239 * comparisons. Otherwise an NlogN algorithm is used, where N is
3240 * distance(first,last).
3242 * The comparison function should have the same effects on ordering as
3243 * the function used for the initial sort.
3245 template<typename _BidirectionalIterator
, typename _Compare
>
3247 inplace_merge(_BidirectionalIterator __first
,
3248 _BidirectionalIterator __middle
,
3249 _BidirectionalIterator __last
,
3252 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3254 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3257 // concept requirements
3258 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3259 _BidirectionalIterator
>)
3260 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3261 _ValueType
, _ValueType
>)
3262 __glibcxx_requires_sorted_pred(__first
, __middle
, __comp
);
3263 __glibcxx_requires_sorted_pred(__middle
, __last
, __comp
);
3265 if (__first
== __middle
|| __middle
== __last
)
3268 const _DistanceType __len1
= std::distance(__first
, __middle
);
3269 const _DistanceType __len2
= std::distance(__middle
, __last
);
3271 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3273 if (__buf
.begin() == 0)
3274 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
,
3277 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3278 __buf
.begin(), _DistanceType(__buf
.size()),
3282 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3285 __merge_sort_loop(_RandomAccessIterator1 __first
,
3286 _RandomAccessIterator1 __last
,
3287 _RandomAccessIterator2 __result
,
3288 _Distance __step_size
)
3290 const _Distance __two_step
= 2 * __step_size
;
3292 while (__last
- __first
>= __two_step
)
3294 __result
= _GLIBCXX_STD_P::merge(
3295 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
),
3296 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+ __step_size
),
3297 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+ __step_size
),
3298 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+ __two_step
),
3300 __first
+= __two_step
;
3303 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3304 _GLIBCXX_STD_P::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first
),
3305 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+
3307 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+
3309 _GLIBCXX_MAKE_MOVE_ITERATOR(__last
),
3313 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3314 typename _Distance
, typename _Compare
>
3316 __merge_sort_loop(_RandomAccessIterator1 __first
,
3317 _RandomAccessIterator1 __last
,
3318 _RandomAccessIterator2 __result
, _Distance __step_size
,
3321 const _Distance __two_step
= 2 * __step_size
;
3323 while (__last
- __first
>= __two_step
)
3325 __result
= _GLIBCXX_STD_P::merge(
3326 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
),
3327 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+ __step_size
),
3328 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+ __step_size
),
3329 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+ __two_step
),
3331 __first
+= __two_step
;
3333 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3335 _GLIBCXX_STD_P::merge(_GLIBCXX_MAKE_MOVE_ITERATOR(__first
),
3336 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+
3338 _GLIBCXX_MAKE_MOVE_ITERATOR(__first
+
3340 _GLIBCXX_MAKE_MOVE_ITERATOR(__last
),
3344 template<typename _RandomAccessIterator
, typename _Distance
>
3346 __chunk_insertion_sort(_RandomAccessIterator __first
,
3347 _RandomAccessIterator __last
,
3348 _Distance __chunk_size
)
3350 while (__last
- __first
>= __chunk_size
)
3352 std::__insertion_sort(__first
, __first
+ __chunk_size
);
3353 __first
+= __chunk_size
;
3355 std::__insertion_sort(__first
, __last
);
3358 template<typename _RandomAccessIterator
, typename _Distance
,
3361 __chunk_insertion_sort(_RandomAccessIterator __first
,
3362 _RandomAccessIterator __last
,
3363 _Distance __chunk_size
, _Compare __comp
)
3365 while (__last
- __first
>= __chunk_size
)
3367 std::__insertion_sort(__first
, __first
+ __chunk_size
, __comp
);
3368 __first
+= __chunk_size
;
3370 std::__insertion_sort(__first
, __last
, __comp
);
3373 enum { _S_chunk_size
= 7 };
3375 template<typename _RandomAccessIterator
, typename _Pointer
>
3377 __merge_sort_with_buffer(_RandomAccessIterator __first
,
3378 _RandomAccessIterator __last
,
3381 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3384 const _Distance __len
= __last
- __first
;
3385 const _Pointer __buffer_last
= __buffer
+ __len
;
3387 _Distance __step_size
= _S_chunk_size
;
3388 std::__chunk_insertion_sort(__first
, __last
, __step_size
);
3390 while (__step_size
< __len
)
3392 std::__merge_sort_loop(__first
, __last
, __buffer
, __step_size
);
3394 std::__merge_sort_loop(__buffer
, __buffer_last
, __first
, __step_size
);
3399 template<typename _RandomAccessIterator
, typename _Pointer
, typename _Compare
>
3401 __merge_sort_with_buffer(_RandomAccessIterator __first
,
3402 _RandomAccessIterator __last
,
3403 _Pointer __buffer
, _Compare __comp
)
3405 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3408 const _Distance __len
= __last
- __first
;
3409 const _Pointer __buffer_last
= __buffer
+ __len
;
3411 _Distance __step_size
= _S_chunk_size
;
3412 std::__chunk_insertion_sort(__first
, __last
, __step_size
, __comp
);
3414 while (__step_size
< __len
)
3416 std::__merge_sort_loop(__first
, __last
, __buffer
,
3417 __step_size
, __comp
);
3419 std::__merge_sort_loop(__buffer
, __buffer_last
, __first
,
3420 __step_size
, __comp
);
3425 template<typename _RandomAccessIterator
, typename _Pointer
,
3428 __stable_sort_adaptive(_RandomAccessIterator __first
,
3429 _RandomAccessIterator __last
,
3430 _Pointer __buffer
, _Distance __buffer_size
)
3432 const _Distance __len
= (__last
- __first
+ 1) / 2;
3433 const _RandomAccessIterator __middle
= __first
+ __len
;
3434 if (__len
> __buffer_size
)
3436 std::__stable_sort_adaptive(__first
, __middle
,
3437 __buffer
, __buffer_size
);
3438 std::__stable_sort_adaptive(__middle
, __last
,
3439 __buffer
, __buffer_size
);
3443 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
);
3444 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
);
3446 std::__merge_adaptive(__first
, __middle
, __last
,
3447 _Distance(__middle
- __first
),
3448 _Distance(__last
- __middle
),
3449 __buffer
, __buffer_size
);
3452 template<typename _RandomAccessIterator
, typename _Pointer
,
3453 typename _Distance
, typename _Compare
>
3455 __stable_sort_adaptive(_RandomAccessIterator __first
,
3456 _RandomAccessIterator __last
,
3457 _Pointer __buffer
, _Distance __buffer_size
,
3460 const _Distance __len
= (__last
- __first
+ 1) / 2;
3461 const _RandomAccessIterator __middle
= __first
+ __len
;
3462 if (__len
> __buffer_size
)
3464 std::__stable_sort_adaptive(__first
, __middle
, __buffer
,
3465 __buffer_size
, __comp
);
3466 std::__stable_sort_adaptive(__middle
, __last
, __buffer
,
3467 __buffer_size
, __comp
);
3471 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
, __comp
);
3472 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
, __comp
);
3474 std::__merge_adaptive(__first
, __middle
, __last
,
3475 _Distance(__middle
- __first
),
3476 _Distance(__last
- __middle
),
3477 __buffer
, __buffer_size
,
3481 /// This is a helper function for the stable sorting routines.
3482 template<typename _RandomAccessIterator
>
3484 __inplace_stable_sort(_RandomAccessIterator __first
,
3485 _RandomAccessIterator __last
)
3487 if (__last
- __first
< 15)
3489 std::__insertion_sort(__first
, __last
);
3492 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
3493 std::__inplace_stable_sort(__first
, __middle
);
3494 std::__inplace_stable_sort(__middle
, __last
);
3495 std::__merge_without_buffer(__first
, __middle
, __last
,
3500 /// This is a helper function for the stable sorting routines.
3501 template<typename _RandomAccessIterator
, typename _Compare
>
3503 __inplace_stable_sort(_RandomAccessIterator __first
,
3504 _RandomAccessIterator __last
, _Compare __comp
)
3506 if (__last
- __first
< 15)
3508 std::__insertion_sort(__first
, __last
, __comp
);
3511 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
3512 std::__inplace_stable_sort(__first
, __middle
, __comp
);
3513 std::__inplace_stable_sort(__middle
, __last
, __comp
);
3514 std::__merge_without_buffer(__first
, __middle
, __last
,
3522 // Set algorithms: includes, set_union, set_intersection, set_difference,
3523 // set_symmetric_difference. All of these algorithms have the precondition
3524 // that their input ranges are sorted and the postcondition that their output
3525 // ranges are sorted.
3528 * @brief Determines whether all elements of a sequence exists in a range.
3529 * @param first1 Start of search range.
3530 * @param last1 End of search range.
3531 * @param first2 Start of sequence
3532 * @param last2 End of sequence.
3533 * @return True if each element in [first2,last2) is contained in order
3534 * within [first1,last1). False otherwise.
3535 * @ingroup set_algorithms
3537 * This operation expects both [first1,last1) and [first2,last2) to be
3538 * sorted. Searches for the presence of each element in [first2,last2)
3539 * within [first1,last1). The iterators over each range only move forward,
3540 * so this is a linear algorithm. If an element in [first2,last2) is not
3541 * found before the search iterator reaches @a last2, false is returned.
3543 template<typename _InputIterator1
, typename _InputIterator2
>
3545 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
3546 _InputIterator2 __first2
, _InputIterator2 __last2
)
3548 typedef typename iterator_traits
<_InputIterator1
>::value_type
3550 typedef typename iterator_traits
<_InputIterator2
>::value_type
3553 // concept requirements
3554 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3555 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3556 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
3557 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
3558 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
3559 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
3561 while (__first1
!= __last1
&& __first2
!= __last2
)
3562 if (*__first2
< *__first1
)
3564 else if(*__first1
< *__first2
)
3567 ++__first1
, ++__first2
;
3569 return __first2
== __last2
;
3573 * @brief Determines whether all elements of a sequence exists in a range
3575 * @ingroup set_algorithms
3576 * @param first1 Start of search range.
3577 * @param last1 End of search range.
3578 * @param first2 Start of sequence
3579 * @param last2 End of sequence.
3580 * @param comp Comparison function to use.
3581 * @return True if each element in [first2,last2) is contained in order
3582 * within [first1,last1) according to comp. False otherwise.
3583 * @ingroup set_algorithms
3585 * This operation expects both [first1,last1) and [first2,last2) to be
3586 * sorted. Searches for the presence of each element in [first2,last2)
3587 * within [first1,last1), using comp to decide. The iterators over each
3588 * range only move forward, so this is a linear algorithm. If an element
3589 * in [first2,last2) is not found before the search iterator reaches @a
3590 * last2, false is returned.
3592 template<typename _InputIterator1
, typename _InputIterator2
,
3595 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
3596 _InputIterator2 __first2
, _InputIterator2 __last2
,
3599 typedef typename iterator_traits
<_InputIterator1
>::value_type
3601 typedef typename iterator_traits
<_InputIterator2
>::value_type
3604 // concept requirements
3605 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3606 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3607 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3608 _ValueType1
, _ValueType2
>)
3609 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3610 _ValueType2
, _ValueType1
>)
3611 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
3612 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
3614 while (__first1
!= __last1
&& __first2
!= __last2
)
3615 if (__comp(*__first2
, *__first1
))
3617 else if(__comp(*__first1
, *__first2
))
3620 ++__first1
, ++__first2
;
3622 return __first2
== __last2
;
3631 // set_symmetric_difference
3636 * @brief Permute range into the next "dictionary" ordering.
3637 * @ingroup sorting_algorithms
3638 * @param first Start of range.
3639 * @param last End of range.
3640 * @return False if wrapped to first permutation, true otherwise.
3642 * Treats all permutations of the range as a set of "dictionary" sorted
3643 * sequences. Permutes the current sequence into the next one of this set.
3644 * Returns true if there are more sequences to generate. If the sequence
3645 * is the largest of the set, the smallest is generated and false returned.
3647 template<typename _BidirectionalIterator
>
3649 next_permutation(_BidirectionalIterator __first
,
3650 _BidirectionalIterator __last
)
3652 // concept requirements
3653 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
3654 _BidirectionalIterator
>)
3655 __glibcxx_function_requires(_LessThanComparableConcept
<
3656 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
3657 __glibcxx_requires_valid_range(__first
, __last
);
3659 if (__first
== __last
)
3661 _BidirectionalIterator __i
= __first
;
3670 _BidirectionalIterator __ii
= __i
;
3674 _BidirectionalIterator __j
= __last
;
3675 while (!(*__i
< *--__j
))
3677 std::iter_swap(__i
, __j
);
3678 std::reverse(__ii
, __last
);
3683 std::reverse(__first
, __last
);
3690 * @brief Permute range into the next "dictionary" ordering using
3691 * comparison functor.
3692 * @ingroup sorting_algorithms
3693 * @param first Start of range.
3694 * @param last End of range.
3695 * @param comp A comparison functor.
3696 * @return False if wrapped to first permutation, true otherwise.
3698 * Treats all permutations of the range [first,last) as a set of
3699 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3700 * sequence into the next one of this set. Returns true if there are more
3701 * sequences to generate. If the sequence is the largest of the set, the
3702 * smallest is generated and false returned.
3704 template<typename _BidirectionalIterator
, typename _Compare
>
3706 next_permutation(_BidirectionalIterator __first
,
3707 _BidirectionalIterator __last
, _Compare __comp
)
3709 // concept requirements
3710 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
3711 _BidirectionalIterator
>)
3712 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3713 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
3714 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
3715 __glibcxx_requires_valid_range(__first
, __last
);
3717 if (__first
== __last
)
3719 _BidirectionalIterator __i
= __first
;
3728 _BidirectionalIterator __ii
= __i
;
3730 if (__comp(*__i
, *__ii
))
3732 _BidirectionalIterator __j
= __last
;
3733 while (!bool(__comp(*__i
, *--__j
)))
3735 std::iter_swap(__i
, __j
);
3736 std::reverse(__ii
, __last
);
3741 std::reverse(__first
, __last
);
3748 * @brief Permute range into the previous "dictionary" ordering.
3749 * @ingroup sorting_algorithms
3750 * @param first Start of range.
3751 * @param last End of range.
3752 * @return False if wrapped to last permutation, true otherwise.
3754 * Treats all permutations of the range as a set of "dictionary" sorted
3755 * sequences. Permutes the current sequence into the previous one of this
3756 * set. Returns true if there are more sequences to generate. If the
3757 * sequence is the smallest of the set, the largest is generated and false
3760 template<typename _BidirectionalIterator
>
3762 prev_permutation(_BidirectionalIterator __first
,
3763 _BidirectionalIterator __last
)
3765 // concept requirements
3766 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
3767 _BidirectionalIterator
>)
3768 __glibcxx_function_requires(_LessThanComparableConcept
<
3769 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
3770 __glibcxx_requires_valid_range(__first
, __last
);
3772 if (__first
== __last
)
3774 _BidirectionalIterator __i
= __first
;
3783 _BidirectionalIterator __ii
= __i
;
3787 _BidirectionalIterator __j
= __last
;
3788 while (!(*--__j
< *__i
))
3790 std::iter_swap(__i
, __j
);
3791 std::reverse(__ii
, __last
);
3796 std::reverse(__first
, __last
);
3803 * @brief Permute range into the previous "dictionary" ordering using
3804 * comparison functor.
3805 * @ingroup sorting_algorithms
3806 * @param first Start of range.
3807 * @param last End of range.
3808 * @param comp A comparison functor.
3809 * @return False if wrapped to last permutation, true otherwise.
3811 * Treats all permutations of the range [first,last) as a set of
3812 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3813 * sequence into the previous one of this set. Returns true if there are
3814 * more sequences to generate. If the sequence is the smallest of the set,
3815 * the largest is generated and false returned.
3817 template<typename _BidirectionalIterator
, typename _Compare
>
3819 prev_permutation(_BidirectionalIterator __first
,
3820 _BidirectionalIterator __last
, _Compare __comp
)
3822 // concept requirements
3823 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
3824 _BidirectionalIterator
>)
3825 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3826 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
3827 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
3828 __glibcxx_requires_valid_range(__first
, __last
);
3830 if (__first
== __last
)
3832 _BidirectionalIterator __i
= __first
;
3841 _BidirectionalIterator __ii
= __i
;
3843 if (__comp(*__ii
, *__i
))
3845 _BidirectionalIterator __j
= __last
;
3846 while (!bool(__comp(*--__j
, *__i
)))
3848 std::iter_swap(__i
, __j
);
3849 std::reverse(__ii
, __last
);
3854 std::reverse(__first
, __last
);
3864 * @brief Copy a sequence, replacing each element of one value with another
3866 * @param first An input iterator.
3867 * @param last An input iterator.
3868 * @param result An output iterator.
3869 * @param old_value The value to be replaced.
3870 * @param new_value The replacement value.
3871 * @return The end of the output sequence, @p result+(last-first).
3873 * Copies each element in the input range @p [first,last) to the
3874 * output range @p [result,result+(last-first)) replacing elements
3875 * equal to @p old_value with @p new_value.
3877 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
3879 replace_copy(_InputIterator __first
, _InputIterator __last
,
3880 _OutputIterator __result
,
3881 const _Tp
& __old_value
, const _Tp
& __new_value
)
3883 // concept requirements
3884 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3885 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3886 typename iterator_traits
<_InputIterator
>::value_type
>)
3887 __glibcxx_function_requires(_EqualOpConcept
<
3888 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
3889 __glibcxx_requires_valid_range(__first
, __last
);
3891 for (; __first
!= __last
; ++__first
, ++__result
)
3892 if (*__first
== __old_value
)
3893 *__result
= __new_value
;
3895 *__result
= *__first
;
3900 * @brief Copy a sequence, replacing each value for which a predicate
3901 * returns true with another value.
3902 * @ingroup mutating_algorithms
3903 * @param first An input iterator.
3904 * @param last An input iterator.
3905 * @param result An output iterator.
3906 * @param pred A predicate.
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 range @p [first,last) to the range
3911 * @p [result,result+(last-first)) replacing elements for which
3912 * @p pred returns true with @p new_value.
3914 template<typename _InputIterator
, typename _OutputIterator
,
3915 typename _Predicate
, typename _Tp
>
3917 replace_copy_if(_InputIterator __first
, _InputIterator __last
,
3918 _OutputIterator __result
,
3919 _Predicate __pred
, const _Tp
& __new_value
)
3921 // concept requirements
3922 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
3923 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3924 typename iterator_traits
<_InputIterator
>::value_type
>)
3925 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
3926 typename iterator_traits
<_InputIterator
>::value_type
>)
3927 __glibcxx_requires_valid_range(__first
, __last
);
3929 for (; __first
!= __last
; ++__first
, ++__result
)
3930 if (__pred(*__first
))
3931 *__result
= __new_value
;
3933 *__result
= *__first
;
3937 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3939 * @brief Determines whether the elements of a sequence are sorted.
3940 * @ingroup sorting_algorithms
3941 * @param first An iterator.
3942 * @param last Another iterator.
3943 * @return True if the elements are sorted, false otherwise.
3945 template<typename _ForwardIterator
>
3947 is_sorted(_ForwardIterator __first
, _ForwardIterator __last
)
3948 { return std::is_sorted_until(__first
, __last
) == __last
; }
3951 * @brief Determines whether the elements of a sequence are sorted
3952 * according to a comparison functor.
3953 * @ingroup sorting_algorithms
3954 * @param first An iterator.
3955 * @param last Another iterator.
3956 * @param comp A comparison functor.
3957 * @return True if the elements are sorted, false otherwise.
3959 template<typename _ForwardIterator
, typename _Compare
>
3961 is_sorted(_ForwardIterator __first
, _ForwardIterator __last
,
3963 { return std::is_sorted_until(__first
, __last
, __comp
) == __last
; }
3966 * @brief Determines the end of a sorted sequence.
3967 * @ingroup sorting_algorithms
3968 * @param first An iterator.
3969 * @param last Another iterator.
3970 * @return An iterator pointing to the last iterator i in [first, last)
3971 * for which the range [first, i) is sorted.
3973 template<typename _ForwardIterator
>
3975 is_sorted_until(_ForwardIterator __first
, _ForwardIterator __last
)
3977 // concept requirements
3978 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3979 __glibcxx_function_requires(_LessThanComparableConcept
<
3980 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3981 __glibcxx_requires_valid_range(__first
, __last
);
3983 if (__first
== __last
)
3986 _ForwardIterator __next
= __first
;
3987 for (++__next
; __next
!= __last
; __first
= __next
, ++__next
)
3988 if (*__next
< *__first
)
3994 * @brief Determines the end of a sorted sequence using comparison functor.
3995 * @ingroup sorting_algorithms
3996 * @param first An iterator.
3997 * @param last Another iterator.
3998 * @param comp A comparison functor.
3999 * @return An iterator pointing to the last iterator i in [first, last)
4000 * for which the range [first, i) is sorted.
4002 template<typename _ForwardIterator
, typename _Compare
>
4004 is_sorted_until(_ForwardIterator __first
, _ForwardIterator __last
,
4007 // concept requirements
4008 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4009 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4010 typename iterator_traits
<_ForwardIterator
>::value_type
,
4011 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4012 __glibcxx_requires_valid_range(__first
, __last
);
4014 if (__first
== __last
)
4017 _ForwardIterator __next
= __first
;
4018 for (++__next
; __next
!= __last
; __first
= __next
, ++__next
)
4019 if (__comp(*__next
, *__first
))
4025 * @brief Determines min and max at once as an ordered pair.
4026 * @ingroup sorting_algorithms
4027 * @param a A thing of arbitrary type.
4028 * @param b Another thing of arbitrary type.
4029 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
4031 template<typename _Tp
>
4032 inline pair
<const _Tp
&, const _Tp
&>
4033 minmax(const _Tp
& __a
, const _Tp
& __b
)
4035 // concept requirements
4036 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
4038 return __b
< __a
? pair
<const _Tp
&, const _Tp
&>(__b
, __a
)
4039 : pair
<const _Tp
&, const _Tp
&>(__a
, __b
);
4043 * @brief Determines min and max at once as an ordered pair.
4044 * @ingroup sorting_algorithms
4045 * @param a A thing of arbitrary type.
4046 * @param b Another thing of arbitrary type.
4047 * @param comp A @link comparison_functor comparison functor@endlink.
4048 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
4050 template<typename _Tp
, typename _Compare
>
4051 inline pair
<const _Tp
&, const _Tp
&>
4052 minmax(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
)
4054 return __comp(__b
, __a
) ? pair
<const _Tp
&, const _Tp
&>(__b
, __a
)
4055 : pair
<const _Tp
&, const _Tp
&>(__a
, __b
);
4059 * @brief Return a pair of iterators pointing to the minimum and maximum
4060 * elements in a range.
4061 * @ingroup sorting_algorithms
4062 * @param first Start of range.
4063 * @param last End of range.
4064 * @return make_pair(m, M), where m is the first iterator i in
4065 * [first, last) such that no other element in the range is
4066 * smaller, and where M is the last iterator i in [first, last)
4067 * such that no other element in the range is larger.
4069 template<typename _ForwardIterator
>
4070 pair
<_ForwardIterator
, _ForwardIterator
>
4071 minmax_element(_ForwardIterator __first
, _ForwardIterator __last
)
4073 // concept requirements
4074 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4075 __glibcxx_function_requires(_LessThanComparableConcept
<
4076 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4077 __glibcxx_requires_valid_range(__first
, __last
);
4079 _ForwardIterator __next
= __first
;
4080 if (__first
== __last
4081 || ++__next
== __last
)
4082 return std::make_pair(__first
, __first
);
4084 _ForwardIterator __min
, __max
;
4085 if (*__next
< *__first
)
4099 while (__first
!= __last
)
4102 if (++__next
== __last
)
4104 if (*__first
< *__min
)
4106 else if (!(*__first
< *__max
))
4111 if (*__next
< *__first
)
4113 if (*__next
< *__min
)
4115 if (!(*__first
< *__max
))
4120 if (*__first
< *__min
)
4122 if (!(*__next
< *__max
))
4130 return std::make_pair(__min
, __max
);
4134 * @brief Return a pair of iterators pointing to the minimum and maximum
4135 * elements in a range.
4136 * @ingroup sorting_algorithms
4137 * @param first Start of range.
4138 * @param last End of range.
4139 * @param comp Comparison functor.
4140 * @return make_pair(m, M), where m is the first iterator i in
4141 * [first, last) such that no other element in the range is
4142 * smaller, and where M is the last iterator i in [first, last)
4143 * such that no other element in the range is larger.
4145 template<typename _ForwardIterator
, typename _Compare
>
4146 pair
<_ForwardIterator
, _ForwardIterator
>
4147 minmax_element(_ForwardIterator __first
, _ForwardIterator __last
,
4150 // concept requirements
4151 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4152 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4153 typename iterator_traits
<_ForwardIterator
>::value_type
,
4154 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4155 __glibcxx_requires_valid_range(__first
, __last
);
4157 _ForwardIterator __next
= __first
;
4158 if (__first
== __last
4159 || ++__next
== __last
)
4160 return std::make_pair(__first
, __first
);
4162 _ForwardIterator __min
, __max
;
4163 if (__comp(*__next
, *__first
))
4177 while (__first
!= __last
)
4180 if (++__next
== __last
)
4182 if (__comp(*__first
, *__min
))
4184 else if (!__comp(*__first
, *__max
))
4189 if (__comp(*__next
, *__first
))
4191 if (__comp(*__next
, *__min
))
4193 if (!__comp(*__first
, *__max
))
4198 if (__comp(*__first
, *__min
))
4200 if (!__comp(*__next
, *__max
))
4208 return std::make_pair(__min
, __max
);
4212 template<typename _Tp
>
4214 min(initializer_list
<_Tp
> __l
)
4215 { return *std::min_element(__l
.begin(), __l
.end()); }
4217 template<typename _Tp
, typename _Compare
>
4219 min(initializer_list
<_Tp
> __l
, _Compare __comp
)
4220 { return *std::min_element(__l
.begin(), __l
.end(), __comp
); }
4222 template<typename _Tp
>
4224 max(initializer_list
<_Tp
> __l
)
4225 { return *std::max_element(__l
.begin(), __l
.end()); }
4227 template<typename _Tp
, typename _Compare
>
4229 max(initializer_list
<_Tp
> __l
, _Compare __comp
)
4230 { return *std::max_element(__l
.begin(), __l
.end(), __comp
); }
4232 template<typename _Tp
>
4233 inline pair
<_Tp
, _Tp
>
4234 minmax(initializer_list
<_Tp
> __l
)
4236 pair
<const _Tp
*, const _Tp
*> __p
=
4237 std::minmax_element(__l
.begin(), __l
.end());
4238 return std::make_pair(*__p
.first
, *__p
.second
);
4241 template<typename _Tp
, typename _Compare
>
4242 inline pair
<_Tp
, _Tp
>
4243 minmax(initializer_list
<_Tp
> __l
, _Compare __comp
)
4245 pair
<const _Tp
*, const _Tp
*> __p
=
4246 std::minmax_element(__l
.begin(), __l
.end(), __comp
);
4247 return std::make_pair(*__p
.first
, *__p
.second
);
4249 #endif // __GXX_EXPERIMENTAL_CXX0X__
4251 _GLIBCXX_END_NAMESPACE
4253 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std
, _GLIBCXX_STD_P
)
4256 * @brief Apply a function to every element of a sequence.
4257 * @ingroup non_mutating_algorithms
4258 * @param first An input iterator.
4259 * @param last An input iterator.
4260 * @param f A unary function object.
4263 * Applies the function object @p f to each element in the range
4264 * @p [first,last). @p f must not modify the order of the sequence.
4265 * If @p f has a return value it is ignored.
4267 template<typename _InputIterator
, typename _Function
>
4269 for_each(_InputIterator __first
, _InputIterator __last
, _Function __f
)
4271 // concept requirements
4272 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4273 __glibcxx_requires_valid_range(__first
, __last
);
4274 for (; __first
!= __last
; ++__first
)
4280 * @brief Find the first occurrence of a value in a sequence.
4281 * @ingroup non_mutating_algorithms
4282 * @param first An input iterator.
4283 * @param last An input iterator.
4284 * @param val The value to find.
4285 * @return The first iterator @c i in the range @p [first,last)
4286 * such that @c *i == @p val, or @p last if no such iterator exists.
4288 template<typename _InputIterator
, typename _Tp
>
4289 inline _InputIterator
4290 find(_InputIterator __first
, _InputIterator __last
,
4293 // concept requirements
4294 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4295 __glibcxx_function_requires(_EqualOpConcept
<
4296 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
4297 __glibcxx_requires_valid_range(__first
, __last
);
4298 return std::__find(__first
, __last
, __val
,
4299 std::__iterator_category(__first
));
4303 * @brief Find the first element in a sequence for which a
4304 * predicate is true.
4305 * @ingroup non_mutating_algorithms
4306 * @param first An input iterator.
4307 * @param last An input iterator.
4308 * @param pred A predicate.
4309 * @return The first iterator @c i in the range @p [first,last)
4310 * such that @p pred(*i) is true, or @p last if no such iterator exists.
4312 template<typename _InputIterator
, typename _Predicate
>
4313 inline _InputIterator
4314 find_if(_InputIterator __first
, _InputIterator __last
,
4317 // concept requirements
4318 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4319 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
4320 typename iterator_traits
<_InputIterator
>::value_type
>)
4321 __glibcxx_requires_valid_range(__first
, __last
);
4322 return std::__find_if(__first
, __last
, __pred
,
4323 std::__iterator_category(__first
));
4327 * @brief Find element from a set in a sequence.
4328 * @ingroup non_mutating_algorithms
4329 * @param first1 Start of range to search.
4330 * @param last1 End of range to search.
4331 * @param first2 Start of match candidates.
4332 * @param last2 End of match candidates.
4333 * @return The first iterator @c i in the range
4334 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
4335 * iterator in [first2,last2), or @p last1 if no such iterator exists.
4337 * Searches the range @p [first1,last1) for an element that is equal to
4338 * some element in the range [first2,last2). If found, returns an iterator
4339 * in the range [first1,last1), otherwise returns @p last1.
4341 template<typename _InputIterator
, typename _ForwardIterator
>
4343 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
4344 _ForwardIterator __first2
, _ForwardIterator __last2
)
4346 // concept requirements
4347 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4348 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4349 __glibcxx_function_requires(_EqualOpConcept
<
4350 typename iterator_traits
<_InputIterator
>::value_type
,
4351 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4352 __glibcxx_requires_valid_range(__first1
, __last1
);
4353 __glibcxx_requires_valid_range(__first2
, __last2
);
4355 for (; __first1
!= __last1
; ++__first1
)
4356 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
4357 if (*__first1
== *__iter
)
4363 * @brief Find element from a set in a sequence using a predicate.
4364 * @ingroup non_mutating_algorithms
4365 * @param first1 Start of range to search.
4366 * @param last1 End of range to search.
4367 * @param first2 Start of match candidates.
4368 * @param last2 End of match candidates.
4369 * @param comp Predicate to use.
4370 * @return The first iterator @c i in the range
4371 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
4372 * iterator in [first2,last2), or @p last1 if no such iterator exists.
4375 * Searches the range @p [first1,last1) for an element that is
4376 * equal to some element in the range [first2,last2). If found,
4377 * returns an iterator in the range [first1,last1), otherwise
4380 template<typename _InputIterator
, typename _ForwardIterator
,
4381 typename _BinaryPredicate
>
4383 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
4384 _ForwardIterator __first2
, _ForwardIterator __last2
,
4385 _BinaryPredicate __comp
)
4387 // concept requirements
4388 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4389 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4390 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4391 typename iterator_traits
<_InputIterator
>::value_type
,
4392 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4393 __glibcxx_requires_valid_range(__first1
, __last1
);
4394 __glibcxx_requires_valid_range(__first2
, __last2
);
4396 for (; __first1
!= __last1
; ++__first1
)
4397 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
4398 if (__comp(*__first1
, *__iter
))
4404 * @brief Find two adjacent values in a sequence that are equal.
4405 * @ingroup non_mutating_algorithms
4406 * @param first A forward iterator.
4407 * @param last A forward iterator.
4408 * @return The first iterator @c i such that @c i and @c i+1 are both
4409 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
4410 * or @p last if no such iterator exists.
4412 template<typename _ForwardIterator
>
4414 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
)
4416 // concept requirements
4417 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4418 __glibcxx_function_requires(_EqualityComparableConcept
<
4419 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4420 __glibcxx_requires_valid_range(__first
, __last
);
4421 if (__first
== __last
)
4423 _ForwardIterator __next
= __first
;
4424 while(++__next
!= __last
)
4426 if (*__first
== *__next
)
4434 * @brief Find two adjacent values in a sequence using a predicate.
4435 * @ingroup non_mutating_algorithms
4436 * @param first A forward iterator.
4437 * @param last A forward iterator.
4438 * @param binary_pred A binary predicate.
4439 * @return The first iterator @c i such that @c i and @c i+1 are both
4440 * valid iterators in @p [first,last) and such that
4441 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
4444 template<typename _ForwardIterator
, typename _BinaryPredicate
>
4446 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
,
4447 _BinaryPredicate __binary_pred
)
4449 // concept requirements
4450 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4451 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4452 typename iterator_traits
<_ForwardIterator
>::value_type
,
4453 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4454 __glibcxx_requires_valid_range(__first
, __last
);
4455 if (__first
== __last
)
4457 _ForwardIterator __next
= __first
;
4458 while(++__next
!= __last
)
4460 if (__binary_pred(*__first
, *__next
))
4468 * @brief Count the number of copies of a value in a sequence.
4469 * @ingroup non_mutating_algorithms
4470 * @param first An input iterator.
4471 * @param last An input iterator.
4472 * @param value The value to be counted.
4473 * @return The number of iterators @c i in the range @p [first,last)
4474 * for which @c *i == @p value
4476 template<typename _InputIterator
, typename _Tp
>
4477 typename iterator_traits
<_InputIterator
>::difference_type
4478 count(_InputIterator __first
, _InputIterator __last
, const _Tp
& __value
)
4480 // concept requirements
4481 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4482 __glibcxx_function_requires(_EqualOpConcept
<
4483 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
4484 __glibcxx_requires_valid_range(__first
, __last
);
4485 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
4486 for (; __first
!= __last
; ++__first
)
4487 if (*__first
== __value
)
4493 * @brief Count the elements of a sequence for which a predicate is true.
4494 * @ingroup non_mutating_algorithms
4495 * @param first An input iterator.
4496 * @param last An input iterator.
4497 * @param pred A predicate.
4498 * @return The number of iterators @c i in the range @p [first,last)
4499 * for which @p pred(*i) is true.
4501 template<typename _InputIterator
, typename _Predicate
>
4502 typename iterator_traits
<_InputIterator
>::difference_type
4503 count_if(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
4505 // concept requirements
4506 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4507 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
4508 typename iterator_traits
<_InputIterator
>::value_type
>)
4509 __glibcxx_requires_valid_range(__first
, __last
);
4510 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
4511 for (; __first
!= __last
; ++__first
)
4512 if (__pred(*__first
))
4518 * @brief Search a sequence for a matching sub-sequence.
4519 * @ingroup non_mutating_algorithms
4520 * @param first1 A forward iterator.
4521 * @param last1 A forward iterator.
4522 * @param first2 A forward iterator.
4523 * @param last2 A forward iterator.
4524 * @return The first iterator @c i in the range
4525 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
4526 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
4527 * such iterator exists.
4529 * Searches the range @p [first1,last1) for a sub-sequence that compares
4530 * equal value-by-value with the sequence given by @p [first2,last2) and
4531 * returns an iterator to the first element of the sub-sequence, or
4532 * @p last1 if the sub-sequence is not found.
4534 * Because the sub-sequence must lie completely within the range
4535 * @p [first1,last1) it must start at a position less than
4536 * @p last1-(last2-first2) where @p last2-first2 is the length of the
4538 * This means that the returned iterator @c i will be in the range
4539 * @p [first1,last1-(last2-first2))
4541 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
4543 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
4544 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
4546 // concept requirements
4547 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
4548 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
4549 __glibcxx_function_requires(_EqualOpConcept
<
4550 typename iterator_traits
<_ForwardIterator1
>::value_type
,
4551 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
4552 __glibcxx_requires_valid_range(__first1
, __last1
);
4553 __glibcxx_requires_valid_range(__first2
, __last2
);
4555 // Test for empty ranges
4556 if (__first1
== __last1
|| __first2
== __last2
)
4559 // Test for a pattern of length 1.
4560 _ForwardIterator2
__p1(__first2
);
4561 if (++__p1
== __last2
)
4562 return _GLIBCXX_STD_P::find(__first1
, __last1
, *__first2
);
4565 _ForwardIterator2 __p
;
4566 _ForwardIterator1 __current
= __first1
;
4570 __first1
= _GLIBCXX_STD_P::find(__first1
, __last1
, *__first2
);
4571 if (__first1
== __last1
)
4575 __current
= __first1
;
4576 if (++__current
== __last1
)
4579 while (*__current
== *__p
)
4581 if (++__p
== __last2
)
4583 if (++__current
== __last1
)
4592 * @brief Search a sequence for a matching sub-sequence using a predicate.
4593 * @ingroup non_mutating_algorithms
4594 * @param first1 A forward iterator.
4595 * @param last1 A forward iterator.
4596 * @param first2 A forward iterator.
4597 * @param last2 A forward iterator.
4598 * @param predicate A binary predicate.
4599 * @return The first iterator @c i in the range
4600 * @p [first1,last1-(last2-first2)) such that
4601 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
4602 * @p [0,last2-first2), or @p last1 if no such iterator exists.
4604 * Searches the range @p [first1,last1) for a sub-sequence that compares
4605 * equal value-by-value with the sequence given by @p [first2,last2),
4606 * using @p predicate to determine equality, and returns an iterator
4607 * to the first element of the sub-sequence, or @p last1 if no such
4610 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4612 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
4613 typename _BinaryPredicate
>
4615 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
4616 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
4617 _BinaryPredicate __predicate
)
4619 // concept requirements
4620 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
4621 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
4622 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4623 typename iterator_traits
<_ForwardIterator1
>::value_type
,
4624 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
4625 __glibcxx_requires_valid_range(__first1
, __last1
);
4626 __glibcxx_requires_valid_range(__first2
, __last2
);
4628 // Test for empty ranges
4629 if (__first1
== __last1
|| __first2
== __last2
)
4632 // Test for a pattern of length 1.
4633 _ForwardIterator2
__p1(__first2
);
4634 if (++__p1
== __last2
)
4636 while (__first1
!= __last1
4637 && !bool(__predicate(*__first1
, *__first2
)))
4643 _ForwardIterator2 __p
;
4644 _ForwardIterator1 __current
= __first1
;
4648 while (__first1
!= __last1
4649 && !bool(__predicate(*__first1
, *__first2
)))
4651 if (__first1
== __last1
)
4655 __current
= __first1
;
4656 if (++__current
== __last1
)
4659 while (__predicate(*__current
, *__p
))
4661 if (++__p
== __last2
)
4663 if (++__current
== __last1
)
4673 * @brief Search a sequence for a number of consecutive values.
4674 * @ingroup non_mutating_algorithms
4675 * @param first A forward iterator.
4676 * @param last A forward iterator.
4677 * @param count The number of consecutive values.
4678 * @param val The value to find.
4679 * @return The first iterator @c i in the range @p [first,last-count)
4680 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
4681 * or @p last if no such iterator exists.
4683 * Searches the range @p [first,last) for @p count consecutive elements
4686 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
4688 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
4689 _Integer __count
, const _Tp
& __val
)
4691 // concept requirements
4692 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4693 __glibcxx_function_requires(_EqualOpConcept
<
4694 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
4695 __glibcxx_requires_valid_range(__first
, __last
);
4700 return _GLIBCXX_STD_P::find(__first
, __last
, __val
);
4701 return std::__search_n(__first
, __last
, __count
, __val
,
4702 std::__iterator_category(__first
));
4707 * @brief Search a sequence for a number of consecutive values using a
4709 * @ingroup non_mutating_algorithms
4710 * @param first A forward iterator.
4711 * @param last A forward iterator.
4712 * @param count The number of consecutive values.
4713 * @param val The value to find.
4714 * @param binary_pred A binary predicate.
4715 * @return The first iterator @c i in the range @p [first,last-count)
4716 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
4717 * range @p [0,count), or @p last if no such iterator exists.
4719 * Searches the range @p [first,last) for @p count consecutive elements
4720 * for which the predicate returns true.
4722 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
4723 typename _BinaryPredicate
>
4725 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
4726 _Integer __count
, const _Tp
& __val
,
4727 _BinaryPredicate __binary_pred
)
4729 // concept requirements
4730 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4731 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4732 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
4733 __glibcxx_requires_valid_range(__first
, __last
);
4739 while (__first
!= __last
&& !bool(__binary_pred(*__first
, __val
)))
4743 return std::__search_n(__first
, __last
, __count
, __val
, __binary_pred
,
4744 std::__iterator_category(__first
));
4749 * @brief Perform an operation on a sequence.
4750 * @ingroup mutating_algorithms
4751 * @param first An input iterator.
4752 * @param last An input iterator.
4753 * @param result An output iterator.
4754 * @param unary_op A unary operator.
4755 * @return An output iterator equal to @p result+(last-first).
4757 * Applies the operator to each element in the input range and assigns
4758 * the results to successive elements of the output sequence.
4759 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
4760 * range @p [0,last-first).
4762 * @p unary_op must not alter its argument.
4764 template<typename _InputIterator
, typename _OutputIterator
,
4765 typename _UnaryOperation
>
4767 transform(_InputIterator __first
, _InputIterator __last
,
4768 _OutputIterator __result
, _UnaryOperation __unary_op
)
4770 // concept requirements
4771 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4772 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4773 // "the type returned by a _UnaryOperation"
4774 __typeof__(__unary_op(*__first
))>)
4775 __glibcxx_requires_valid_range(__first
, __last
);
4777 for (; __first
!= __last
; ++__first
, ++__result
)
4778 *__result
= __unary_op(*__first
);
4783 * @brief Perform an operation on corresponding elements of two sequences.
4784 * @ingroup mutating_algorithms
4785 * @param first1 An input iterator.
4786 * @param last1 An input iterator.
4787 * @param first2 An input iterator.
4788 * @param result An output iterator.
4789 * @param binary_op A binary operator.
4790 * @return An output iterator equal to @p result+(last-first).
4792 * Applies the operator to the corresponding elements in the two
4793 * input ranges and assigns the results to successive elements of the
4795 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
4796 * @c N in the range @p [0,last1-first1).
4798 * @p binary_op must not alter either of its arguments.
4800 template<typename _InputIterator1
, typename _InputIterator2
,
4801 typename _OutputIterator
, typename _BinaryOperation
>
4803 transform(_InputIterator1 __first1
, _InputIterator1 __last1
,
4804 _InputIterator2 __first2
, _OutputIterator __result
,
4805 _BinaryOperation __binary_op
)
4807 // concept requirements
4808 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4809 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4810 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4811 // "the type returned by a _BinaryOperation"
4812 __typeof__(__binary_op(*__first1
,*__first2
))>)
4813 __glibcxx_requires_valid_range(__first1
, __last1
);
4815 for (; __first1
!= __last1
; ++__first1
, ++__first2
, ++__result
)
4816 *__result
= __binary_op(*__first1
, *__first2
);
4821 * @brief Replace each occurrence of one value in a sequence with another
4823 * @ingroup mutating_algorithms
4824 * @param first A forward iterator.
4825 * @param last A forward iterator.
4826 * @param old_value The value to be replaced.
4827 * @param new_value The replacement value.
4828 * @return replace() returns no value.
4830 * For each iterator @c i in the range @p [first,last) if @c *i ==
4831 * @p old_value then the assignment @c *i = @p new_value is performed.
4833 template<typename _ForwardIterator
, typename _Tp
>
4835 replace(_ForwardIterator __first
, _ForwardIterator __last
,
4836 const _Tp
& __old_value
, const _Tp
& __new_value
)
4838 // concept requirements
4839 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
4841 __glibcxx_function_requires(_EqualOpConcept
<
4842 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
4843 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
4844 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4845 __glibcxx_requires_valid_range(__first
, __last
);
4847 for (; __first
!= __last
; ++__first
)
4848 if (*__first
== __old_value
)
4849 *__first
= __new_value
;
4853 * @brief Replace each value in a sequence for which a predicate returns
4854 * true with another value.
4855 * @ingroup mutating_algorithms
4856 * @param first A forward iterator.
4857 * @param last A forward iterator.
4858 * @param pred A predicate.
4859 * @param new_value The replacement value.
4860 * @return replace_if() returns no value.
4862 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
4863 * is true then the assignment @c *i = @p new_value is performed.
4865 template<typename _ForwardIterator
, typename _Predicate
, typename _Tp
>
4867 replace_if(_ForwardIterator __first
, _ForwardIterator __last
,
4868 _Predicate __pred
, const _Tp
& __new_value
)
4870 // concept requirements
4871 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
4873 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
4874 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4875 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
4876 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4877 __glibcxx_requires_valid_range(__first
, __last
);
4879 for (; __first
!= __last
; ++__first
)
4880 if (__pred(*__first
))
4881 *__first
= __new_value
;
4885 * @brief Assign the result of a function object to each value in a
4887 * @ingroup mutating_algorithms
4888 * @param first A forward iterator.
4889 * @param last A forward iterator.
4890 * @param gen A function object taking no arguments and returning
4891 * std::iterator_traits<_ForwardIterator>::value_type
4892 * @return generate() returns no value.
4894 * Performs the assignment @c *i = @p gen() for each @c i in the range
4897 template<typename _ForwardIterator
, typename _Generator
>
4899 generate(_ForwardIterator __first
, _ForwardIterator __last
,
4902 // concept requirements
4903 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4904 __glibcxx_function_requires(_GeneratorConcept
<_Generator
,
4905 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4906 __glibcxx_requires_valid_range(__first
, __last
);
4908 for (; __first
!= __last
; ++__first
)
4913 * @brief Assign the result of a function object to each value in a
4915 * @ingroup mutating_algorithms
4916 * @param first A forward iterator.
4917 * @param n The length of the sequence.
4918 * @param gen A function object taking no arguments and returning
4919 * std::iterator_traits<_ForwardIterator>::value_type
4920 * @return The end of the sequence, @p first+n
4922 * Performs the assignment @c *i = @p gen() for each @c i in the range
4923 * @p [first,first+n).
4925 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4926 * DR 865. More algorithms that throw away information
4928 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
4930 generate_n(_OutputIterator __first
, _Size __n
, _Generator __gen
)
4932 // concept requirements
4933 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4934 // "the type returned by a _Generator"
4935 __typeof__(__gen())>)
4937 for (; __n
> 0; --__n
, ++__first
)
4944 * @brief Copy a sequence, removing consecutive duplicate values.
4945 * @ingroup mutating_algorithms
4946 * @param first An input iterator.
4947 * @param last An input iterator.
4948 * @param result An output iterator.
4949 * @return An iterator designating the end of the resulting sequence.
4951 * Copies each element in the range @p [first,last) to the range
4952 * beginning at @p result, except that only the first element is copied
4953 * from groups of consecutive elements that compare equal.
4954 * unique_copy() is stable, so the relative order of elements that are
4955 * copied is unchanged.
4957 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4958 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4960 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4961 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4964 template<typename _InputIterator
, typename _OutputIterator
>
4965 inline _OutputIterator
4966 unique_copy(_InputIterator __first
, _InputIterator __last
,
4967 _OutputIterator __result
)
4969 // concept requirements
4970 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4971 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4972 typename iterator_traits
<_InputIterator
>::value_type
>)
4973 __glibcxx_function_requires(_EqualityComparableConcept
<
4974 typename iterator_traits
<_InputIterator
>::value_type
>)
4975 __glibcxx_requires_valid_range(__first
, __last
);
4977 if (__first
== __last
)
4979 return std::__unique_copy(__first
, __last
, __result
,
4980 std::__iterator_category(__first
),
4981 std::__iterator_category(__result
));
4985 * @brief Copy a sequence, removing consecutive values using a predicate.
4986 * @ingroup mutating_algorithms
4987 * @param first An input iterator.
4988 * @param last An input iterator.
4989 * @param result An output iterator.
4990 * @param binary_pred A binary predicate.
4991 * @return An iterator designating the end of the resulting sequence.
4993 * Copies each element in the range @p [first,last) to the range
4994 * beginning at @p result, except that only the first element is copied
4995 * from groups of consecutive elements for which @p binary_pred returns
4997 * unique_copy() is stable, so the relative order of elements that are
4998 * copied is unchanged.
5000 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5001 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5003 template<typename _InputIterator
, typename _OutputIterator
,
5004 typename _BinaryPredicate
>
5005 inline _OutputIterator
5006 unique_copy(_InputIterator __first
, _InputIterator __last
,
5007 _OutputIterator __result
,
5008 _BinaryPredicate __binary_pred
)
5010 // concept requirements -- predicates checked later
5011 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
5012 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5013 typename iterator_traits
<_InputIterator
>::value_type
>)
5014 __glibcxx_requires_valid_range(__first
, __last
);
5016 if (__first
== __last
)
5018 return std::__unique_copy(__first
, __last
, __result
, __binary_pred
,
5019 std::__iterator_category(__first
),
5020 std::__iterator_category(__result
));
5025 * @brief Randomly shuffle the elements of a sequence.
5026 * @ingroup mutating_algorithms
5027 * @param first A forward iterator.
5028 * @param last A forward iterator.
5031 * Reorder the elements in the range @p [first,last) using a random
5032 * distribution, so that every possible ordering of the sequence is
5035 template<typename _RandomAccessIterator
>
5037 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
5039 // concept requirements
5040 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5041 _RandomAccessIterator
>)
5042 __glibcxx_requires_valid_range(__first
, __last
);
5044 if (__first
!= __last
)
5045 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
5046 std::iter_swap(__i
, __first
+ (std::rand() % ((__i
- __first
) + 1)));
5050 * @brief Shuffle the elements of a sequence using a random number
5052 * @ingroup mutating_algorithms
5053 * @param first A forward iterator.
5054 * @param last A forward iterator.
5055 * @param rand The RNG functor or function.
5058 * Reorders the elements in the range @p [first,last) using @p rand to
5059 * provide a random distribution. Calling @p rand(N) for a positive
5060 * integer @p N should return a randomly chosen integer from the
5063 template<typename _RandomAccessIterator
, typename _RandomNumberGenerator
>
5065 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
5066 _RandomNumberGenerator
& __rand
)
5068 // concept requirements
5069 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5070 _RandomAccessIterator
>)
5071 __glibcxx_requires_valid_range(__first
, __last
);
5073 if (__first
== __last
)
5075 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
5076 std::iter_swap(__i
, __first
+ __rand((__i
- __first
) + 1));
5081 * @brief Move elements for which a predicate is true to the beginning
5083 * @ingroup mutating_algorithms
5084 * @param first A forward iterator.
5085 * @param last A forward iterator.
5086 * @param pred A predicate functor.
5087 * @return An iterator @p middle such that @p pred(i) is true for each
5088 * iterator @p i in the range @p [first,middle) and false for each @p i
5089 * in the range @p [middle,last).
5091 * @p pred must not modify its operand. @p partition() does not preserve
5092 * the relative ordering of elements in each group, use
5093 * @p stable_partition() if this is needed.
5095 template<typename _ForwardIterator
, typename _Predicate
>
5096 inline _ForwardIterator
5097 partition(_ForwardIterator __first
, _ForwardIterator __last
,
5100 // concept requirements
5101 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
5103 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
5104 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5105 __glibcxx_requires_valid_range(__first
, __last
);
5107 return std::__partition(__first
, __last
, __pred
,
5108 std::__iterator_category(__first
));
5114 * @brief Sort the smallest elements of a sequence.
5115 * @ingroup sorting_algorithms
5116 * @param first An iterator.
5117 * @param middle Another iterator.
5118 * @param last Another iterator.
5121 * Sorts the smallest @p (middle-first) elements in the range
5122 * @p [first,last) and moves them to the range @p [first,middle). The
5123 * order of the remaining elements in the range @p [middle,last) is
5125 * After the sort if @p i and @j are iterators in the range
5126 * @p [first,middle) such that @i precedes @j and @k is an iterator in
5127 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
5129 template<typename _RandomAccessIterator
>
5131 partial_sort(_RandomAccessIterator __first
,
5132 _RandomAccessIterator __middle
,
5133 _RandomAccessIterator __last
)
5135 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5138 // concept requirements
5139 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5140 _RandomAccessIterator
>)
5141 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
5142 __glibcxx_requires_valid_range(__first
, __middle
);
5143 __glibcxx_requires_valid_range(__middle
, __last
);
5145 std::__heap_select(__first
, __middle
, __last
);
5146 std::sort_heap(__first
, __middle
);
5150 * @brief Sort the smallest elements of a sequence using a predicate
5152 * @ingroup sorting_algorithms
5153 * @param first An iterator.
5154 * @param middle Another iterator.
5155 * @param last Another iterator.
5156 * @param comp A comparison functor.
5159 * Sorts the smallest @p (middle-first) elements in the range
5160 * @p [first,last) and moves them to the range @p [first,middle). The
5161 * order of the remaining elements in the range @p [middle,last) is
5163 * After the sort if @p i and @j are iterators in the range
5164 * @p [first,middle) such that @i precedes @j and @k is an iterator in
5165 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
5168 template<typename _RandomAccessIterator
, typename _Compare
>
5170 partial_sort(_RandomAccessIterator __first
,
5171 _RandomAccessIterator __middle
,
5172 _RandomAccessIterator __last
,
5175 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5178 // concept requirements
5179 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5180 _RandomAccessIterator
>)
5181 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5182 _ValueType
, _ValueType
>)
5183 __glibcxx_requires_valid_range(__first
, __middle
);
5184 __glibcxx_requires_valid_range(__middle
, __last
);
5186 std::__heap_select(__first
, __middle
, __last
, __comp
);
5187 std::sort_heap(__first
, __middle
, __comp
);
5191 * @brief Sort a sequence just enough to find a particular position.
5192 * @ingroup sorting_algorithms
5193 * @param first An iterator.
5194 * @param nth Another iterator.
5195 * @param last Another iterator.
5198 * Rearranges the elements in the range @p [first,last) so that @p *nth
5199 * is the same element that would have been in that position had the
5200 * whole sequence been sorted.
5201 * whole sequence been sorted. The elements either side of @p *nth are
5202 * not completely sorted, but for any iterator @i in the range
5203 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5204 * holds that @p *j<*i is false.
5206 template<typename _RandomAccessIterator
>
5208 nth_element(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
5209 _RandomAccessIterator __last
)
5211 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5214 // concept requirements
5215 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5216 _RandomAccessIterator
>)
5217 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
5218 __glibcxx_requires_valid_range(__first
, __nth
);
5219 __glibcxx_requires_valid_range(__nth
, __last
);
5221 if (__first
== __last
|| __nth
== __last
)
5224 std::__introselect(__first
, __nth
, __last
,
5225 std::__lg(__last
- __first
) * 2);
5229 * @brief Sort a sequence just enough to find a particular position
5230 * using a predicate for comparison.
5231 * @ingroup sorting_algorithms
5232 * @param first An iterator.
5233 * @param nth Another iterator.
5234 * @param last Another iterator.
5235 * @param comp A comparison functor.
5238 * Rearranges the elements in the range @p [first,last) so that @p *nth
5239 * is the same element that would have been in that position had the
5240 * whole sequence been sorted. The elements either side of @p *nth are
5241 * not completely sorted, but for any iterator @i in the range
5242 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5243 * holds that @p comp(*j,*i) is false.
5245 template<typename _RandomAccessIterator
, typename _Compare
>
5247 nth_element(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
5248 _RandomAccessIterator __last
, _Compare __comp
)
5250 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5253 // concept requirements
5254 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5255 _RandomAccessIterator
>)
5256 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5257 _ValueType
, _ValueType
>)
5258 __glibcxx_requires_valid_range(__first
, __nth
);
5259 __glibcxx_requires_valid_range(__nth
, __last
);
5261 if (__first
== __last
|| __nth
== __last
)
5264 std::__introselect(__first
, __nth
, __last
,
5265 std::__lg(__last
- __first
) * 2, __comp
);
5270 * @brief Sort the elements of a sequence.
5271 * @ingroup sorting_algorithms
5272 * @param first An iterator.
5273 * @param last Another iterator.
5276 * Sorts the elements in the range @p [first,last) in ascending order,
5277 * such that @p *(i+1)<*i is false for each iterator @p i in the range
5278 * @p [first,last-1).
5280 * The relative ordering of equivalent elements is not preserved, use
5281 * @p stable_sort() if this is needed.
5283 template<typename _RandomAccessIterator
>
5285 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
5287 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5290 // concept requirements
5291 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5292 _RandomAccessIterator
>)
5293 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
5294 __glibcxx_requires_valid_range(__first
, __last
);
5296 if (__first
!= __last
)
5298 std::__introsort_loop(__first
, __last
,
5299 std::__lg(__last
- __first
) * 2);
5300 std::__final_insertion_sort(__first
, __last
);
5305 * @brief Sort the elements of a sequence using a predicate for comparison.
5306 * @ingroup sorting_algorithms
5307 * @param first An iterator.
5308 * @param last Another iterator.
5309 * @param comp A comparison functor.
5312 * Sorts the elements in the range @p [first,last) in ascending order,
5313 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
5314 * range @p [first,last-1).
5316 * The relative ordering of equivalent elements is not preserved, use
5317 * @p stable_sort() if this is needed.
5319 template<typename _RandomAccessIterator
, typename _Compare
>
5321 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
5324 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5327 // concept requirements
5328 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5329 _RandomAccessIterator
>)
5330 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
, _ValueType
,
5332 __glibcxx_requires_valid_range(__first
, __last
);
5334 if (__first
!= __last
)
5336 std::__introsort_loop(__first
, __last
,
5337 std::__lg(__last
- __first
) * 2, __comp
);
5338 std::__final_insertion_sort(__first
, __last
, __comp
);
5343 * @brief Merges two sorted ranges.
5344 * @ingroup sorting_algorithms
5345 * @param first1 An iterator.
5346 * @param first2 Another iterator.
5347 * @param last1 Another iterator.
5348 * @param last2 Another iterator.
5349 * @param result An iterator pointing to the end of the merged range.
5350 * @return An iterator pointing to the first element "not less
5353 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5354 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5355 * must be sorted, and the output range must not overlap with either of
5356 * the input ranges. The sort is @e stable, that is, for equivalent
5357 * elements in the two ranges, elements from the first range will always
5358 * come before elements from the second.
5360 template<typename _InputIterator1
, typename _InputIterator2
,
5361 typename _OutputIterator
>
5363 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
5364 _InputIterator2 __first2
, _InputIterator2 __last2
,
5365 _OutputIterator __result
)
5367 typedef typename iterator_traits
<_InputIterator1
>::value_type
5369 typedef typename iterator_traits
<_InputIterator2
>::value_type
5372 // concept requirements
5373 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5374 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5375 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5377 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5379 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
5380 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5381 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5383 while (__first1
!= __last1
&& __first2
!= __last2
)
5385 if (*__first2
< *__first1
)
5387 *__result
= *__first2
;
5392 *__result
= *__first1
;
5397 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
5402 * @brief Merges two sorted ranges.
5403 * @ingroup sorting_algorithms
5404 * @param first1 An iterator.
5405 * @param first2 Another iterator.
5406 * @param last1 Another iterator.
5407 * @param last2 Another iterator.
5408 * @param result An iterator pointing to the end of the merged range.
5409 * @param comp A functor to use for comparisons.
5410 * @return An iterator pointing to the first element "not less
5413 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5414 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5415 * must be sorted, and the output range must not overlap with either of
5416 * the input ranges. The sort is @e stable, that is, for equivalent
5417 * elements in the two ranges, elements from the first range will always
5418 * come before elements from the second.
5420 * The comparison function should have the same effects on ordering as
5421 * the function used for the initial sort.
5423 template<typename _InputIterator1
, typename _InputIterator2
,
5424 typename _OutputIterator
, typename _Compare
>
5426 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
5427 _InputIterator2 __first2
, _InputIterator2 __last2
,
5428 _OutputIterator __result
, _Compare __comp
)
5430 typedef typename iterator_traits
<_InputIterator1
>::value_type
5432 typedef typename iterator_traits
<_InputIterator2
>::value_type
5435 // concept requirements
5436 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5437 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5438 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5440 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5442 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5443 _ValueType2
, _ValueType1
>)
5444 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5445 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5447 while (__first1
!= __last1
&& __first2
!= __last2
)
5449 if (__comp(*__first2
, *__first1
))
5451 *__result
= *__first2
;
5456 *__result
= *__first1
;
5461 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
5467 * @brief Sort the elements of a sequence, preserving the relative order
5468 * of equivalent elements.
5469 * @ingroup sorting_algorithms
5470 * @param first An iterator.
5471 * @param last Another iterator.
5474 * Sorts the elements in the range @p [first,last) in ascending order,
5475 * such that @p *(i+1)<*i is false for each iterator @p i in the range
5476 * @p [first,last-1).
5478 * The relative ordering of equivalent elements is preserved, so any two
5479 * elements @p x and @p y in the range @p [first,last) such that
5480 * @p x<y is false and @p y<x is false will have the same relative
5481 * ordering after calling @p stable_sort().
5483 template<typename _RandomAccessIterator
>
5485 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
5487 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5489 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
5492 // concept requirements
5493 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5494 _RandomAccessIterator
>)
5495 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
5496 __glibcxx_requires_valid_range(__first
, __last
);
5498 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
> __buf(__first
,
5500 if (__buf
.begin() == 0)
5501 std::__inplace_stable_sort(__first
, __last
);
5503 std::__stable_sort_adaptive(__first
, __last
, __buf
.begin(),
5504 _DistanceType(__buf
.size()));
5508 * @brief Sort the elements of a sequence using a predicate for comparison,
5509 * preserving the relative order of equivalent elements.
5510 * @ingroup sorting_algorithms
5511 * @param first An iterator.
5512 * @param last Another iterator.
5513 * @param comp A comparison functor.
5516 * Sorts the elements in the range @p [first,last) in ascending order,
5517 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
5518 * range @p [first,last-1).
5520 * The relative ordering of equivalent elements is preserved, so any two
5521 * elements @p x and @p y in the range @p [first,last) such that
5522 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
5523 * relative ordering after calling @p stable_sort().
5525 template<typename _RandomAccessIterator
, typename _Compare
>
5527 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
5530 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
5532 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
5535 // concept requirements
5536 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
5537 _RandomAccessIterator
>)
5538 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5541 __glibcxx_requires_valid_range(__first
, __last
);
5543 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
> __buf(__first
,
5545 if (__buf
.begin() == 0)
5546 std::__inplace_stable_sort(__first
, __last
, __comp
);
5548 std::__stable_sort_adaptive(__first
, __last
, __buf
.begin(),
5549 _DistanceType(__buf
.size()), __comp
);
5554 * @brief Return the union of two sorted ranges.
5555 * @ingroup set_algorithms
5556 * @param first1 Start of first range.
5557 * @param last1 End of first range.
5558 * @param first2 Start of second range.
5559 * @param last2 End of second range.
5560 * @return End of the output range.
5561 * @ingroup set_algorithms
5563 * This operation iterates over both ranges, copying elements present in
5564 * each range in order to the output range. Iterators increment for each
5565 * range. When the current element of one range is less than the other,
5566 * that element is copied and the iterator advanced. If an element is
5567 * contained in both ranges, the element from the first range is copied and
5568 * both ranges advance. The output range may not overlap either input
5571 template<typename _InputIterator1
, typename _InputIterator2
,
5572 typename _OutputIterator
>
5574 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
5575 _InputIterator2 __first2
, _InputIterator2 __last2
,
5576 _OutputIterator __result
)
5578 typedef typename iterator_traits
<_InputIterator1
>::value_type
5580 typedef typename iterator_traits
<_InputIterator2
>::value_type
5583 // concept requirements
5584 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5585 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5586 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5588 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5590 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
5591 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
5592 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5593 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5595 while (__first1
!= __last1
&& __first2
!= __last2
)
5597 if (*__first1
< *__first2
)
5599 *__result
= *__first1
;
5602 else if (*__first2
< *__first1
)
5604 *__result
= *__first2
;
5609 *__result
= *__first1
;
5615 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
5620 * @brief Return the union of two sorted ranges using a comparison functor.
5621 * @ingroup set_algorithms
5622 * @param first1 Start of first range.
5623 * @param last1 End of first range.
5624 * @param first2 Start of second range.
5625 * @param last2 End of second range.
5626 * @param comp The comparison functor.
5627 * @return End of the output range.
5628 * @ingroup set_algorithms
5630 * This operation iterates over both ranges, copying elements present in
5631 * each range in order to the output range. Iterators increment for each
5632 * range. When the current element of one range is less than the other
5633 * according to @a comp, that element is copied and the iterator advanced.
5634 * If an equivalent element according to @a comp is contained in both
5635 * ranges, the element from the first range is copied and both ranges
5636 * advance. The output range may not overlap either input range.
5638 template<typename _InputIterator1
, typename _InputIterator2
,
5639 typename _OutputIterator
, typename _Compare
>
5641 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
5642 _InputIterator2 __first2
, _InputIterator2 __last2
,
5643 _OutputIterator __result
, _Compare __comp
)
5645 typedef typename iterator_traits
<_InputIterator1
>::value_type
5647 typedef typename iterator_traits
<_InputIterator2
>::value_type
5650 // concept requirements
5651 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5652 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5653 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5655 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5657 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5658 _ValueType1
, _ValueType2
>)
5659 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5660 _ValueType2
, _ValueType1
>)
5661 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5662 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5664 while (__first1
!= __last1
&& __first2
!= __last2
)
5666 if (__comp(*__first1
, *__first2
))
5668 *__result
= *__first1
;
5671 else if (__comp(*__first2
, *__first1
))
5673 *__result
= *__first2
;
5678 *__result
= *__first1
;
5684 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
5689 * @brief Return the intersection of two sorted ranges.
5690 * @ingroup set_algorithms
5691 * @param first1 Start of first range.
5692 * @param last1 End of first range.
5693 * @param first2 Start of second range.
5694 * @param last2 End of second range.
5695 * @return End of the output range.
5696 * @ingroup set_algorithms
5698 * This operation iterates over both ranges, copying elements present in
5699 * both ranges in order to the output range. Iterators increment for each
5700 * range. When the current element of one range is less than the other,
5701 * that iterator advances. If an element is contained in both ranges, the
5702 * element from the first range is copied and both ranges advance. The
5703 * output range may not overlap either input range.
5705 template<typename _InputIterator1
, typename _InputIterator2
,
5706 typename _OutputIterator
>
5708 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
5709 _InputIterator2 __first2
, _InputIterator2 __last2
,
5710 _OutputIterator __result
)
5712 typedef typename iterator_traits
<_InputIterator1
>::value_type
5714 typedef typename iterator_traits
<_InputIterator2
>::value_type
5717 // concept requirements
5718 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5719 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5720 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5722 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
5723 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
5724 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5725 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5727 while (__first1
!= __last1
&& __first2
!= __last2
)
5728 if (*__first1
< *__first2
)
5730 else if (*__first2
< *__first1
)
5734 *__result
= *__first1
;
5743 * @brief Return the intersection of two sorted ranges using comparison
5745 * @ingroup set_algorithms
5746 * @param first1 Start of first range.
5747 * @param last1 End of first range.
5748 * @param first2 Start of second range.
5749 * @param last2 End of second range.
5750 * @param comp The comparison functor.
5751 * @return End of the output range.
5752 * @ingroup set_algorithms
5754 * This operation iterates over both ranges, copying elements present in
5755 * both ranges in order to the output range. Iterators increment for each
5756 * range. When the current element of one range is less than the other
5757 * according to @a comp, that iterator advances. If an element is
5758 * contained in both ranges according to @a comp, the element from the
5759 * first range is copied and both ranges advance. The output range may not
5760 * overlap either input range.
5762 template<typename _InputIterator1
, typename _InputIterator2
,
5763 typename _OutputIterator
, typename _Compare
>
5765 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
5766 _InputIterator2 __first2
, _InputIterator2 __last2
,
5767 _OutputIterator __result
, _Compare __comp
)
5769 typedef typename iterator_traits
<_InputIterator1
>::value_type
5771 typedef typename iterator_traits
<_InputIterator2
>::value_type
5774 // concept requirements
5775 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5776 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5777 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5779 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5780 _ValueType1
, _ValueType2
>)
5781 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5782 _ValueType2
, _ValueType1
>)
5783 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5784 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5786 while (__first1
!= __last1
&& __first2
!= __last2
)
5787 if (__comp(*__first1
, *__first2
))
5789 else if (__comp(*__first2
, *__first1
))
5793 *__result
= *__first1
;
5802 * @brief Return the difference of two sorted ranges.
5803 * @ingroup set_algorithms
5804 * @param first1 Start of first range.
5805 * @param last1 End of first range.
5806 * @param first2 Start of second range.
5807 * @param last2 End of second range.
5808 * @return End of the output range.
5809 * @ingroup set_algorithms
5811 * This operation iterates over both ranges, copying elements present in
5812 * the first range but not the second in order to the output range.
5813 * Iterators increment for each range. When the current element of the
5814 * first range is less than the second, that element is copied and the
5815 * iterator advances. If the current element of the second range is less,
5816 * the iterator advances, but no element is copied. If an element is
5817 * contained in both ranges, no elements are copied and both ranges
5818 * advance. The output range may not overlap either input range.
5820 template<typename _InputIterator1
, typename _InputIterator2
,
5821 typename _OutputIterator
>
5823 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5824 _InputIterator2 __first2
, _InputIterator2 __last2
,
5825 _OutputIterator __result
)
5827 typedef typename iterator_traits
<_InputIterator1
>::value_type
5829 typedef typename iterator_traits
<_InputIterator2
>::value_type
5832 // concept requirements
5833 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5834 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5835 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5837 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
5838 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
5839 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5840 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5842 while (__first1
!= __last1
&& __first2
!= __last2
)
5843 if (*__first1
< *__first2
)
5845 *__result
= *__first1
;
5849 else if (*__first2
< *__first1
)
5856 return std::copy(__first1
, __last1
, __result
);
5860 * @brief Return the difference of two sorted ranges using comparison
5862 * @ingroup set_algorithms
5863 * @param first1 Start of first range.
5864 * @param last1 End of first range.
5865 * @param first2 Start of second range.
5866 * @param last2 End of second range.
5867 * @param comp The comparison functor.
5868 * @return End of the output range.
5869 * @ingroup set_algorithms
5871 * This operation iterates over both ranges, copying elements present in
5872 * the first range but not the second in order to the output range.
5873 * Iterators increment for each range. When the current element of the
5874 * first range is less than the second according to @a comp, that element
5875 * is copied and the iterator advances. If the current element of the
5876 * second range is less, no element is copied and the iterator advances.
5877 * If an element is contained in both ranges according to @a comp, no
5878 * elements are copied and both ranges advance. The output range may not
5879 * overlap either input range.
5881 template<typename _InputIterator1
, typename _InputIterator2
,
5882 typename _OutputIterator
, typename _Compare
>
5884 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5885 _InputIterator2 __first2
, _InputIterator2 __last2
,
5886 _OutputIterator __result
, _Compare __comp
)
5888 typedef typename iterator_traits
<_InputIterator1
>::value_type
5890 typedef typename iterator_traits
<_InputIterator2
>::value_type
5893 // concept requirements
5894 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5895 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5896 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5898 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5899 _ValueType1
, _ValueType2
>)
5900 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5901 _ValueType2
, _ValueType1
>)
5902 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
5903 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
5905 while (__first1
!= __last1
&& __first2
!= __last2
)
5906 if (__comp(*__first1
, *__first2
))
5908 *__result
= *__first1
;
5912 else if (__comp(*__first2
, *__first1
))
5919 return std::copy(__first1
, __last1
, __result
);
5923 * @brief Return the symmetric difference of two sorted ranges.
5924 * @ingroup set_algorithms
5925 * @param first1 Start of first range.
5926 * @param last1 End of first range.
5927 * @param first2 Start of second range.
5928 * @param last2 End of second range.
5929 * @return End of the output range.
5930 * @ingroup set_algorithms
5932 * This operation iterates over both ranges, copying elements present in
5933 * one range but not the other in order to the output range. Iterators
5934 * increment for each range. When the current element of one range is less
5935 * than the other, that element is copied and the iterator advances. If an
5936 * element is contained in both ranges, no elements are copied and both
5937 * ranges advance. The output range may not overlap either input range.
5939 template<typename _InputIterator1
, typename _InputIterator2
,
5940 typename _OutputIterator
>
5942 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
5943 _InputIterator2 __first2
, _InputIterator2 __last2
,
5944 _OutputIterator __result
)
5946 typedef typename iterator_traits
<_InputIterator1
>::value_type
5948 typedef typename iterator_traits
<_InputIterator2
>::value_type
5951 // concept requirements
5952 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
5953 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
5954 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5956 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
5958 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
5959 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
5960 __glibcxx_requires_sorted_set(__first1
, __last1
, __first2
);
5961 __glibcxx_requires_sorted_set(__first2
, __last2
, __first1
);
5963 while (__first1
!= __last1
&& __first2
!= __last2
)
5964 if (*__first1
< *__first2
)
5966 *__result
= *__first1
;
5970 else if (*__first2
< *__first1
)
5972 *__result
= *__first2
;
5981 return std::copy(__first2
, __last2
, std::copy(__first1
,
5982 __last1
, __result
));
5986 * @brief Return the symmetric difference of two sorted ranges using
5987 * comparison functor.
5988 * @ingroup set_algorithms
5989 * @param first1 Start of first range.
5990 * @param last1 End of first range.
5991 * @param first2 Start of second range.
5992 * @param last2 End of second range.
5993 * @param comp The comparison functor.
5994 * @return End of the output range.
5995 * @ingroup set_algorithms
5997 * This operation iterates over both ranges, copying elements present in
5998 * one range but not the other in order to the output range. Iterators
5999 * increment for each range. When the current element of one range is less
6000 * than the other according to @a comp, that element is copied and the
6001 * iterator advances. If an element is contained in both ranges according
6002 * to @a comp, no elements are copied and both ranges advance. The output
6003 * range may not overlap either input range.
6005 template<typename _InputIterator1
, typename _InputIterator2
,
6006 typename _OutputIterator
, typename _Compare
>
6008 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
6009 _InputIterator2 __first2
, _InputIterator2 __last2
,
6010 _OutputIterator __result
,
6013 typedef typename iterator_traits
<_InputIterator1
>::value_type
6015 typedef typename iterator_traits
<_InputIterator2
>::value_type
6018 // concept requirements
6019 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
6020 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
6021 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
6023 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
6025 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
6026 _ValueType1
, _ValueType2
>)
6027 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
6028 _ValueType2
, _ValueType1
>)
6029 __glibcxx_requires_sorted_set_pred(__first1
, __last1
, __first2
, __comp
);
6030 __glibcxx_requires_sorted_set_pred(__first2
, __last2
, __first1
, __comp
);
6032 while (__first1
!= __last1
&& __first2
!= __last2
)
6033 if (__comp(*__first1
, *__first2
))
6035 *__result
= *__first1
;
6039 else if (__comp(*__first2
, *__first1
))
6041 *__result
= *__first2
;
6050 return std::copy(__first2
, __last2
,
6051 std::copy(__first1
, __last1
, __result
));
6056 * @brief Return the minimum element in a range.
6057 * @ingroup sorting_algorithms
6058 * @param first Start of range.
6059 * @param last End of range.
6060 * @return Iterator referencing the first instance of the smallest value.
6062 template<typename _ForwardIterator
>
6064 min_element(_ForwardIterator __first
, _ForwardIterator __last
)
6066 // concept requirements
6067 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
6068 __glibcxx_function_requires(_LessThanComparableConcept
<
6069 typename iterator_traits
<_ForwardIterator
>::value_type
>)
6070 __glibcxx_requires_valid_range(__first
, __last
);
6072 if (__first
== __last
)
6074 _ForwardIterator __result
= __first
;
6075 while (++__first
!= __last
)
6076 if (*__first
< *__result
)
6082 * @brief Return the minimum element in a range using comparison functor.
6083 * @ingroup sorting_algorithms
6084 * @param first Start of range.
6085 * @param last End of range.
6086 * @param comp Comparison functor.
6087 * @return Iterator referencing the first instance of the smallest value
6088 * according to comp.
6090 template<typename _ForwardIterator
, typename _Compare
>
6092 min_element(_ForwardIterator __first
, _ForwardIterator __last
,
6095 // concept requirements
6096 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
6097 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
6098 typename iterator_traits
<_ForwardIterator
>::value_type
,
6099 typename iterator_traits
<_ForwardIterator
>::value_type
>)
6100 __glibcxx_requires_valid_range(__first
, __last
);
6102 if (__first
== __last
)
6104 _ForwardIterator __result
= __first
;
6105 while (++__first
!= __last
)
6106 if (__comp(*__first
, *__result
))
6112 * @brief Return the maximum element in a range.
6113 * @ingroup sorting_algorithms
6114 * @param first Start of range.
6115 * @param last End of range.
6116 * @return Iterator referencing the first instance of the largest value.
6118 template<typename _ForwardIterator
>
6120 max_element(_ForwardIterator __first
, _ForwardIterator __last
)
6122 // concept requirements
6123 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
6124 __glibcxx_function_requires(_LessThanComparableConcept
<
6125 typename iterator_traits
<_ForwardIterator
>::value_type
>)
6126 __glibcxx_requires_valid_range(__first
, __last
);
6128 if (__first
== __last
)
6130 _ForwardIterator __result
= __first
;
6131 while (++__first
!= __last
)
6132 if (*__result
< *__first
)
6138 * @brief Return the maximum element in a range using comparison functor.
6139 * @ingroup sorting_algorithms
6140 * @param first Start of range.
6141 * @param last End of range.
6142 * @param comp Comparison functor.
6143 * @return Iterator referencing the first instance of the largest value
6144 * according to comp.
6146 template<typename _ForwardIterator
, typename _Compare
>
6148 max_element(_ForwardIterator __first
, _ForwardIterator __last
,
6151 // concept requirements
6152 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
6153 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
6154 typename iterator_traits
<_ForwardIterator
>::value_type
,
6155 typename iterator_traits
<_ForwardIterator
>::value_type
>)
6156 __glibcxx_requires_valid_range(__first
, __last
);
6158 if (__first
== __last
) return __first
;
6159 _ForwardIterator __result
= __first
;
6160 while (++__first
!= __last
)
6161 if (__comp(*__result
, *__first
))
6166 _GLIBCXX_END_NESTED_NAMESPACE
6168 #endif /* _STL_ALGO_H */