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