1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
34 * Hewlett-Packard Company
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
46 * Silicon Graphics Computer Systems, Inc.
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
58 * This is an internal header file, included by other library headers.
59 * You should not attempt to use it directly.
65 #include <bits/stl_heap.h>
66 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
67 #include <debug/debug.h>
69 // See concept_check.h for the __glibcxx_*_requires macros.
71 _GLIBCXX_BEGIN_NAMESPACE(std
)
74 * @brief Find the median of three values.
78 * @return One of @p a, @p b or @p c.
80 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
81 * then the value returned will be @c m.
82 * This is an SGI extension.
83 * @ingroup SGIextensions
85 template<typename _Tp
>
87 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
)
89 // concept requirements
90 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
107 * @brief Find the median of three values using a predicate for comparison.
111 * @param comp A binary predicate.
112 * @return One of @p a, @p b or @p c.
114 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
115 * and @p comp(m,n) are both true then the value returned will be @c m.
116 * This is an SGI extension.
117 * @ingroup SGIextensions
119 template<typename _Tp
, typename _Compare
>
121 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
, _Compare __comp
)
123 // concept requirements
124 __glibcxx_function_requires(_BinaryFunctionConcept
<_Compare
,bool,_Tp
,_Tp
>)
125 if (__comp(__a
, __b
))
126 if (__comp(__b
, __c
))
128 else if (__comp(__a
, __c
))
132 else if (__comp(__a
, __c
))
134 else if (__comp(__b
, __c
))
141 * @brief Apply a function to every element of a sequence.
142 * @param first An input iterator.
143 * @param last An input iterator.
144 * @param f A unary function object.
147 * Applies the function object @p f to each element in the range
148 * @p [first,last). @p f must not modify the order of the sequence.
149 * If @p f has a return value it is ignored.
151 template<typename _InputIterator
, typename _Function
>
153 for_each(_InputIterator __first
, _InputIterator __last
, _Function __f
)
155 // concept requirements
156 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
157 __glibcxx_requires_valid_range(__first
, __last
);
158 for ( ; __first
!= __last
; ++__first
)
165 * This is an overload used by find() for the Input Iterator case.
168 template<typename _InputIterator
, typename _Tp
>
169 inline _InputIterator
170 __find(_InputIterator __first
, _InputIterator __last
,
171 const _Tp
& __val
, input_iterator_tag
)
173 while (__first
!= __last
&& !(*__first
== __val
))
180 * This is an overload used by find_if() for the Input Iterator case.
183 template<typename _InputIterator
, typename _Predicate
>
184 inline _InputIterator
185 __find_if(_InputIterator __first
, _InputIterator __last
,
186 _Predicate __pred
, input_iterator_tag
)
188 while (__first
!= __last
&& !__pred(*__first
))
195 * This is an overload used by find() for the RAI case.
198 template<typename _RandomAccessIterator
, typename _Tp
>
199 _RandomAccessIterator
200 __find(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
201 const _Tp
& __val
, random_access_iterator_tag
)
203 typename iterator_traits
<_RandomAccessIterator
>::difference_type
204 __trip_count
= (__last
- __first
) >> 2;
206 for ( ; __trip_count
> 0 ; --__trip_count
)
208 if (*__first
== __val
)
212 if (*__first
== __val
)
216 if (*__first
== __val
)
220 if (*__first
== __val
)
225 switch (__last
- __first
)
228 if (*__first
== __val
)
232 if (*__first
== __val
)
236 if (*__first
== __val
)
247 * This is an overload used by find_if() for the RAI case.
250 template<typename _RandomAccessIterator
, typename _Predicate
>
251 _RandomAccessIterator
252 __find_if(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
253 _Predicate __pred
, random_access_iterator_tag
)
255 typename iterator_traits
<_RandomAccessIterator
>::difference_type
256 __trip_count
= (__last
- __first
) >> 2;
258 for ( ; __trip_count
> 0 ; --__trip_count
)
260 if (__pred(*__first
))
264 if (__pred(*__first
))
268 if (__pred(*__first
))
272 if (__pred(*__first
))
277 switch (__last
- __first
)
280 if (__pred(*__first
))
284 if (__pred(*__first
))
288 if (__pred(*__first
))
299 * This is an overload of find() for streambuf iterators.
302 template<typename _CharT
>
303 typename
__gnu_cxx::__enable_if
<__is_char
<_CharT
>::__value
,
304 istreambuf_iterator
<_CharT
> >::__type
305 find(istreambuf_iterator
<_CharT
>, istreambuf_iterator
<_CharT
>,
309 * @brief Find the first occurrence of a value in a sequence.
310 * @param first An input iterator.
311 * @param last An input iterator.
312 * @param val The value to find.
313 * @return The first iterator @c i in the range @p [first,last)
314 * such that @c *i == @p val, or @p last if no such iterator exists.
316 template<typename _InputIterator
, typename _Tp
>
317 inline _InputIterator
318 find(_InputIterator __first
, _InputIterator __last
,
321 // concept requirements
322 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
323 __glibcxx_function_requires(_EqualOpConcept
<
324 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
325 __glibcxx_requires_valid_range(__first
, __last
);
326 return std::__find(__first
, __last
, __val
,
327 std::__iterator_category(__first
));
331 * @brief Find the first element in a sequence for which a predicate is true.
332 * @param first An input iterator.
333 * @param last An input iterator.
334 * @param pred A predicate.
335 * @return The first iterator @c i in the range @p [first,last)
336 * such that @p pred(*i) is true, or @p last if no such iterator exists.
338 template<typename _InputIterator
, typename _Predicate
>
339 inline _InputIterator
340 find_if(_InputIterator __first
, _InputIterator __last
,
343 // concept requirements
344 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
345 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
346 typename iterator_traits
<_InputIterator
>::value_type
>)
347 __glibcxx_requires_valid_range(__first
, __last
);
348 return std::__find_if(__first
, __last
, __pred
,
349 std::__iterator_category(__first
));
353 * @brief Find two adjacent values in a sequence that are equal.
354 * @param first A forward iterator.
355 * @param last A forward iterator.
356 * @return The first iterator @c i such that @c i and @c i+1 are both
357 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
358 * or @p last if no such iterator exists.
360 template<typename _ForwardIterator
>
362 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
)
364 // concept requirements
365 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
366 __glibcxx_function_requires(_EqualityComparableConcept
<
367 typename iterator_traits
<_ForwardIterator
>::value_type
>)
368 __glibcxx_requires_valid_range(__first
, __last
);
369 if (__first
== __last
)
371 _ForwardIterator __next
= __first
;
372 while(++__next
!= __last
)
374 if (*__first
== *__next
)
382 * @brief Find two adjacent values in a sequence using a predicate.
383 * @param first A forward iterator.
384 * @param last A forward iterator.
385 * @param binary_pred A binary predicate.
386 * @return The first iterator @c i such that @c i and @c i+1 are both
387 * valid iterators in @p [first,last) and such that
388 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
391 template<typename _ForwardIterator
, typename _BinaryPredicate
>
393 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
,
394 _BinaryPredicate __binary_pred
)
396 // concept requirements
397 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
398 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
399 typename iterator_traits
<_ForwardIterator
>::value_type
,
400 typename iterator_traits
<_ForwardIterator
>::value_type
>)
401 __glibcxx_requires_valid_range(__first
, __last
);
402 if (__first
== __last
)
404 _ForwardIterator __next
= __first
;
405 while(++__next
!= __last
)
407 if (__binary_pred(*__first
, *__next
))
415 * @brief Count the number of copies of a value in a sequence.
416 * @param first An input iterator.
417 * @param last An input iterator.
418 * @param value The value to be counted.
419 * @return The number of iterators @c i in the range @p [first,last)
420 * for which @c *i == @p value
422 template<typename _InputIterator
, typename _Tp
>
423 typename iterator_traits
<_InputIterator
>::difference_type
424 count(_InputIterator __first
, _InputIterator __last
, const _Tp
& __value
)
426 // concept requirements
427 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
428 __glibcxx_function_requires(_EqualOpConcept
<
429 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
430 __glibcxx_requires_valid_range(__first
, __last
);
431 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
432 for ( ; __first
!= __last
; ++__first
)
433 if (*__first
== __value
)
439 * @brief Count the elements of a sequence for which a predicate is true.
440 * @param first An input iterator.
441 * @param last An input iterator.
442 * @param pred A predicate.
443 * @return The number of iterators @c i in the range @p [first,last)
444 * for which @p pred(*i) is true.
446 template<typename _InputIterator
, typename _Predicate
>
447 typename iterator_traits
<_InputIterator
>::difference_type
448 count_if(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
450 // concept requirements
451 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
452 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
453 typename iterator_traits
<_InputIterator
>::value_type
>)
454 __glibcxx_requires_valid_range(__first
, __last
);
455 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
456 for ( ; __first
!= __last
; ++__first
)
457 if (__pred(*__first
))
463 * @brief Search a sequence for a matching sub-sequence.
464 * @param first1 A forward iterator.
465 * @param last1 A forward iterator.
466 * @param first2 A forward iterator.
467 * @param last2 A forward iterator.
468 * @return The first iterator @c i in the range
469 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
470 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
471 * such iterator exists.
473 * Searches the range @p [first1,last1) for a sub-sequence that compares
474 * equal value-by-value with the sequence given by @p [first2,last2) and
475 * returns an iterator to the first element of the sub-sequence, or
476 * @p last1 if the sub-sequence is not found.
478 * Because the sub-sequence must lie completely within the range
479 * @p [first1,last1) it must start at a position less than
480 * @p last1-(last2-first2) where @p last2-first2 is the length of the
482 * This means that the returned iterator @c i will be in the range
483 * @p [first1,last1-(last2-first2))
485 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
487 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
488 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
490 // concept requirements
491 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
492 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
493 __glibcxx_function_requires(_EqualOpConcept
<
494 typename iterator_traits
<_ForwardIterator1
>::value_type
,
495 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
496 __glibcxx_requires_valid_range(__first1
, __last1
);
497 __glibcxx_requires_valid_range(__first2
, __last2
);
498 // Test for empty ranges
499 if (__first1
== __last1
|| __first2
== __last2
)
502 // Test for a pattern of length 1.
503 _ForwardIterator2
__tmp(__first2
);
505 if (__tmp
== __last2
)
506 return std::find(__first1
, __last1
, *__first2
);
509 _ForwardIterator2 __p1
, __p
;
510 __p1
= __first2
; ++__p1
;
511 _ForwardIterator1 __current
= __first1
;
513 while (__first1
!= __last1
)
515 __first1
= std::find(__first1
, __last1
, *__first2
);
516 if (__first1
== __last1
)
520 __current
= __first1
;
521 if (++__current
== __last1
)
524 while (*__current
== *__p
)
526 if (++__p
== __last2
)
528 if (++__current
== __last1
)
537 * @brief Search a sequence for a matching sub-sequence using a predicate.
538 * @param first1 A forward iterator.
539 * @param last1 A forward iterator.
540 * @param first2 A forward iterator.
541 * @param last2 A forward iterator.
542 * @param predicate A binary predicate.
543 * @return The first iterator @c i in the range
544 * @p [first1,last1-(last2-first2)) such that
545 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
546 * @p [0,last2-first2), or @p last1 if no such iterator exists.
548 * Searches the range @p [first1,last1) for a sub-sequence that compares
549 * equal value-by-value with the sequence given by @p [first2,last2),
550 * using @p predicate to determine equality, and returns an iterator
551 * to the first element of the sub-sequence, or @p last1 if no such
554 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
556 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
557 typename _BinaryPredicate
>
559 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
560 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
561 _BinaryPredicate __predicate
)
563 // concept requirements
564 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
565 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
566 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
567 typename iterator_traits
<_ForwardIterator1
>::value_type
,
568 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
569 __glibcxx_requires_valid_range(__first1
, __last1
);
570 __glibcxx_requires_valid_range(__first2
, __last2
);
572 // Test for empty ranges
573 if (__first1
== __last1
|| __first2
== __last2
)
576 // Test for a pattern of length 1.
577 _ForwardIterator2
__tmp(__first2
);
579 if (__tmp
== __last2
)
581 while (__first1
!= __last1
&& !__predicate(*__first1
, *__first2
))
587 _ForwardIterator2 __p1
, __p
;
588 __p1
= __first2
; ++__p1
;
589 _ForwardIterator1 __current
= __first1
;
591 while (__first1
!= __last1
)
593 while (__first1
!= __last1
)
595 if (__predicate(*__first1
, *__first2
))
599 while (__first1
!= __last1
&& !__predicate(*__first1
, *__first2
))
601 if (__first1
== __last1
)
605 __current
= __first1
;
606 if (++__current
== __last1
)
609 while (__predicate(*__current
, *__p
))
611 if (++__p
== __last2
)
613 if (++__current
== __last1
)
623 * This is an uglified
624 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
625 * overloaded for forward iterators.
628 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
630 __search_n(_ForwardIterator __first
, _ForwardIterator __last
,
631 _Integer __count
, const _Tp
& __val
,
632 std::forward_iterator_tag
)
634 __first
= std::find(__first
, __last
, __val
);
635 while (__first
!= __last
)
637 typename iterator_traits
<_ForwardIterator
>::difference_type
639 _ForwardIterator __i
= __first
;
641 while (__i
!= __last
&& __n
!= 1 && *__i
== __val
)
650 __first
= std::find(++__i
, __last
, __val
);
657 * This is an uglified
658 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
659 * overloaded for random access iterators.
662 template<typename _RandomAccessIter
, typename _Integer
, typename _Tp
>
664 __search_n(_RandomAccessIter __first
, _RandomAccessIter __last
,
665 _Integer __count
, const _Tp
& __val
,
666 std::random_access_iterator_tag
)
669 typedef typename
std::iterator_traits
<_RandomAccessIter
>::difference_type
672 _DistanceType __tailSize
= __last
- __first
;
673 const _DistanceType __pattSize
= __count
;
675 if (__tailSize
< __pattSize
)
678 const _DistanceType __skipOffset
= __pattSize
- 1;
679 _RandomAccessIter __lookAhead
= __first
+ __skipOffset
;
680 __tailSize
-= __pattSize
;
682 while (1) // the main loop...
684 // __lookAhead here is always pointing to the last element of next
686 while (!(*__lookAhead
== __val
)) // the skip loop...
688 if (__tailSize
< __pattSize
)
689 return __last
; // Failure
690 __lookAhead
+= __pattSize
;
691 __tailSize
-= __pattSize
;
693 _DistanceType __remainder
= __skipOffset
;
694 for (_RandomAccessIter __backTrack
= __lookAhead
- 1;
695 *__backTrack
== __val
; --__backTrack
)
697 if (--__remainder
== 0)
698 return (__lookAhead
- __skipOffset
); // Success
700 if (__remainder
> __tailSize
)
701 return __last
; // Failure
702 __lookAhead
+= __remainder
;
703 __tailSize
-= __remainder
;
708 * @brief Search a sequence for a number of consecutive values.
709 * @param first A forward iterator.
710 * @param last A forward iterator.
711 * @param count The number of consecutive values.
712 * @param val The value to find.
713 * @return The first iterator @c i in the range @p [first,last-count)
714 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
715 * or @p last if no such iterator exists.
717 * Searches the range @p [first,last) for @p count consecutive elements
720 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
722 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
723 _Integer __count
, const _Tp
& __val
)
725 // concept requirements
726 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
727 __glibcxx_function_requires(_EqualOpConcept
<
728 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
729 __glibcxx_requires_valid_range(__first
, __last
);
734 return std::find(__first
, __last
, __val
);
735 return std::__search_n(__first
, __last
, __count
, __val
,
736 std::__iterator_category(__first
));
741 * This is an uglified
742 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
744 * overloaded for forward iterators.
747 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
748 typename _BinaryPredicate
>
750 __search_n(_ForwardIterator __first
, _ForwardIterator __last
,
751 _Integer __count
, const _Tp
& __val
,
752 _BinaryPredicate __binary_pred
, std::forward_iterator_tag
)
754 while (__first
!= __last
&& !__binary_pred(*__first
, __val
))
757 while (__first
!= __last
)
759 typename iterator_traits
<_ForwardIterator
>::difference_type
761 _ForwardIterator __i
= __first
;
763 while (__i
!= __last
&& __n
!= 1 && __binary_pred(*__i
, __val
))
773 while (__first
!= __last
&& !__binary_pred(*__first
, __val
))
781 * This is an uglified
782 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
784 * overloaded for random access iterators.
787 template<typename _RandomAccessIter
, typename _Integer
, typename _Tp
,
788 typename _BinaryPredicate
>
790 __search_n(_RandomAccessIter __first
, _RandomAccessIter __last
,
791 _Integer __count
, const _Tp
& __val
,
792 _BinaryPredicate __binary_pred
, std::random_access_iterator_tag
)
795 typedef typename
std::iterator_traits
<_RandomAccessIter
>::difference_type
798 _DistanceType __tailSize
= __last
- __first
;
799 const _DistanceType __pattSize
= __count
;
801 if (__tailSize
< __pattSize
)
804 const _DistanceType __skipOffset
= __pattSize
- 1;
805 _RandomAccessIter __lookAhead
= __first
+ __skipOffset
;
806 __tailSize
-= __pattSize
;
808 while (1) // the main loop...
810 // __lookAhead here is always pointing to the last element of next
812 while (!__binary_pred(*__lookAhead
, __val
)) // the skip loop...
814 if (__tailSize
< __pattSize
)
815 return __last
; // Failure
816 __lookAhead
+= __pattSize
;
817 __tailSize
-= __pattSize
;
819 _DistanceType __remainder
= __skipOffset
;
820 for (_RandomAccessIter __backTrack
= __lookAhead
- 1;
821 __binary_pred(*__backTrack
, __val
); --__backTrack
)
823 if (--__remainder
== 0)
824 return (__lookAhead
- __skipOffset
); // Success
826 if (__remainder
> __tailSize
)
827 return __last
; // Failure
828 __lookAhead
+= __remainder
;
829 __tailSize
-= __remainder
;
834 * @brief Search a sequence for a number of consecutive values using a
836 * @param first A forward iterator.
837 * @param last A forward iterator.
838 * @param count The number of consecutive values.
839 * @param val The value to find.
840 * @param binary_pred A binary predicate.
841 * @return The first iterator @c i in the range @p [first,last-count)
842 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
843 * range @p [0,count), or @p last if no such iterator exists.
845 * Searches the range @p [first,last) for @p count consecutive elements
846 * for which the predicate returns true.
848 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
849 typename _BinaryPredicate
>
851 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
852 _Integer __count
, const _Tp
& __val
,
853 _BinaryPredicate __binary_pred
)
855 // concept requirements
856 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
857 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
858 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
859 __glibcxx_requires_valid_range(__first
, __last
);
865 while (__first
!= __last
&& !__binary_pred(*__first
, __val
))
869 return std::__search_n(__first
, __last
, __count
, __val
, __binary_pred
,
870 std::__iterator_category(__first
));
874 * @brief Swap the elements of two sequences.
875 * @param first1 A forward iterator.
876 * @param last1 A forward iterator.
877 * @param first2 A forward iterator.
878 * @return An iterator equal to @p first2+(last1-first1).
880 * Swaps each element in the range @p [first1,last1) with the
881 * corresponding element in the range @p [first2,(last1-first1)).
882 * The ranges must not overlap.
884 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
886 swap_ranges(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
887 _ForwardIterator2 __first2
)
889 // concept requirements
890 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
892 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
894 __glibcxx_function_requires(_ConvertibleConcept
<
895 typename iterator_traits
<_ForwardIterator1
>::value_type
,
896 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
897 __glibcxx_function_requires(_ConvertibleConcept
<
898 typename iterator_traits
<_ForwardIterator2
>::value_type
,
899 typename iterator_traits
<_ForwardIterator1
>::value_type
>)
900 __glibcxx_requires_valid_range(__first1
, __last1
);
902 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
903 std::iter_swap(__first1
, __first2
);
908 * @brief Perform an operation on a sequence.
909 * @param first An input iterator.
910 * @param last An input iterator.
911 * @param result An output iterator.
912 * @param unary_op A unary operator.
913 * @return An output iterator equal to @p result+(last-first).
915 * Applies the operator to each element in the input range and assigns
916 * the results to successive elements of the output sequence.
917 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
918 * range @p [0,last-first).
920 * @p unary_op must not alter its argument.
922 template<typename _InputIterator
, typename _OutputIterator
,
923 typename _UnaryOperation
>
925 transform(_InputIterator __first
, _InputIterator __last
,
926 _OutputIterator __result
, _UnaryOperation __unary_op
)
928 // concept requirements
929 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
930 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
931 // "the type returned by a _UnaryOperation"
932 __typeof__(__unary_op(*__first
))>)
933 __glibcxx_requires_valid_range(__first
, __last
);
935 for ( ; __first
!= __last
; ++__first
, ++__result
)
936 *__result
= __unary_op(*__first
);
941 * @brief Perform an operation on corresponding elements of two sequences.
942 * @param first1 An input iterator.
943 * @param last1 An input iterator.
944 * @param first2 An input iterator.
945 * @param result An output iterator.
946 * @param binary_op A binary operator.
947 * @return An output iterator equal to @p result+(last-first).
949 * Applies the operator to the corresponding elements in the two
950 * input ranges and assigns the results to successive elements of the
952 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
953 * @c N in the range @p [0,last1-first1).
955 * @p binary_op must not alter either of its arguments.
957 template<typename _InputIterator1
, typename _InputIterator2
,
958 typename _OutputIterator
, typename _BinaryOperation
>
960 transform(_InputIterator1 __first1
, _InputIterator1 __last1
,
961 _InputIterator2 __first2
, _OutputIterator __result
,
962 _BinaryOperation __binary_op
)
964 // concept requirements
965 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
966 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
967 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
968 // "the type returned by a _BinaryOperation"
969 __typeof__(__binary_op(*__first1
,*__first2
))>)
970 __glibcxx_requires_valid_range(__first1
, __last1
);
972 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
, ++__result
)
973 *__result
= __binary_op(*__first1
, *__first2
);
978 * @brief Replace each occurrence of one value in a sequence with another
980 * @param first A forward iterator.
981 * @param last A forward iterator.
982 * @param old_value The value to be replaced.
983 * @param new_value The replacement value.
984 * @return replace() returns no value.
986 * For each iterator @c i in the range @p [first,last) if @c *i ==
987 * @p old_value then the assignment @c *i = @p new_value is performed.
989 template<typename _ForwardIterator
, typename _Tp
>
991 replace(_ForwardIterator __first
, _ForwardIterator __last
,
992 const _Tp
& __old_value
, const _Tp
& __new_value
)
994 // concept requirements
995 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
997 __glibcxx_function_requires(_EqualOpConcept
<
998 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
999 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
1000 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1001 __glibcxx_requires_valid_range(__first
, __last
);
1003 for ( ; __first
!= __last
; ++__first
)
1004 if (*__first
== __old_value
)
1005 *__first
= __new_value
;
1009 * @brief Replace each value in a sequence for which a predicate returns
1010 * true with another value.
1011 * @param first A forward iterator.
1012 * @param last A forward iterator.
1013 * @param pred A predicate.
1014 * @param new_value The replacement value.
1015 * @return replace_if() returns no value.
1017 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
1018 * is true then the assignment @c *i = @p new_value is performed.
1020 template<typename _ForwardIterator
, typename _Predicate
, typename _Tp
>
1022 replace_if(_ForwardIterator __first
, _ForwardIterator __last
,
1023 _Predicate __pred
, const _Tp
& __new_value
)
1025 // concept requirements
1026 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1028 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
1029 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1030 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1031 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1032 __glibcxx_requires_valid_range(__first
, __last
);
1034 for ( ; __first
!= __last
; ++__first
)
1035 if (__pred(*__first
))
1036 *__first
= __new_value
;
1040 * @brief Copy a sequence, replacing each element of one value with another
1042 * @param first An input iterator.
1043 * @param last An input iterator.
1044 * @param result An output iterator.
1045 * @param old_value The value to be replaced.
1046 * @param new_value The replacement value.
1047 * @return The end of the output sequence, @p result+(last-first).
1049 * Copies each element in the input range @p [first,last) to the
1050 * output range @p [result,result+(last-first)) replacing elements
1051 * equal to @p old_value with @p new_value.
1053 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
1055 replace_copy(_InputIterator __first
, _InputIterator __last
,
1056 _OutputIterator __result
,
1057 const _Tp
& __old_value
, const _Tp
& __new_value
)
1059 // concept requirements
1060 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1061 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1062 typename iterator_traits
<_InputIterator
>::value_type
>)
1063 __glibcxx_function_requires(_EqualOpConcept
<
1064 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
1065 __glibcxx_requires_valid_range(__first
, __last
);
1067 for ( ; __first
!= __last
; ++__first
, ++__result
)
1068 if (*__first
== __old_value
)
1069 *__result
= __new_value
;
1071 *__result
= *__first
;
1076 * @brief Copy a sequence, replacing each value for which a predicate
1077 * returns true with another value.
1078 * @param first An input iterator.
1079 * @param last An input iterator.
1080 * @param result An output iterator.
1081 * @param pred A predicate.
1082 * @param new_value The replacement value.
1083 * @return The end of the output sequence, @p result+(last-first).
1085 * Copies each element in the range @p [first,last) to the range
1086 * @p [result,result+(last-first)) replacing elements for which
1087 * @p pred returns true with @p new_value.
1089 template<typename _InputIterator
, typename _OutputIterator
,
1090 typename _Predicate
, typename _Tp
>
1092 replace_copy_if(_InputIterator __first
, _InputIterator __last
,
1093 _OutputIterator __result
,
1094 _Predicate __pred
, const _Tp
& __new_value
)
1096 // concept requirements
1097 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1098 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1099 typename iterator_traits
<_InputIterator
>::value_type
>)
1100 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1101 typename iterator_traits
<_InputIterator
>::value_type
>)
1102 __glibcxx_requires_valid_range(__first
, __last
);
1104 for ( ; __first
!= __last
; ++__first
, ++__result
)
1105 if (__pred(*__first
))
1106 *__result
= __new_value
;
1108 *__result
= *__first
;
1113 * @brief Assign the result of a function object to each value in a
1115 * @param first A forward iterator.
1116 * @param last A forward iterator.
1117 * @param gen A function object taking no arguments.
1118 * @return generate() returns no value.
1120 * Performs the assignment @c *i = @p gen() for each @c i in the range
1123 template<typename _ForwardIterator
, typename _Generator
>
1125 generate(_ForwardIterator __first
, _ForwardIterator __last
,
1128 // concept requirements
1129 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1130 __glibcxx_function_requires(_GeneratorConcept
<_Generator
,
1131 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1132 __glibcxx_requires_valid_range(__first
, __last
);
1134 for ( ; __first
!= __last
; ++__first
)
1139 * @brief Assign the result of a function object to each value in a
1141 * @param first A forward iterator.
1142 * @param n The length of the sequence.
1143 * @param gen A function object taking no arguments.
1144 * @return The end of the sequence, @p first+n
1146 * Performs the assignment @c *i = @p gen() for each @c i in the range
1147 * @p [first,first+n).
1149 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1151 generate_n(_OutputIterator __first
, _Size __n
, _Generator __gen
)
1153 // concept requirements
1154 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1155 // "the type returned by a _Generator"
1156 __typeof__(__gen())>)
1158 for ( ; __n
> 0; --__n
, ++__first
)
1164 * @brief Copy a sequence, removing elements of a given value.
1165 * @param first An input iterator.
1166 * @param last An input iterator.
1167 * @param result An output iterator.
1168 * @param value The value to be removed.
1169 * @return An iterator designating the end of the resulting sequence.
1171 * Copies each element in the range @p [first,last) not equal to @p value
1172 * to the range beginning at @p result.
1173 * remove_copy() is stable, so the relative order of elements that are
1174 * copied is unchanged.
1176 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
1178 remove_copy(_InputIterator __first
, _InputIterator __last
,
1179 _OutputIterator __result
, const _Tp
& __value
)
1181 // concept requirements
1182 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1183 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1184 typename iterator_traits
<_InputIterator
>::value_type
>)
1185 __glibcxx_function_requires(_EqualOpConcept
<
1186 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
1187 __glibcxx_requires_valid_range(__first
, __last
);
1189 for ( ; __first
!= __last
; ++__first
)
1190 if (!(*__first
== __value
))
1192 *__result
= *__first
;
1199 * @brief Copy a sequence, removing elements for which a predicate is true.
1200 * @param first An input iterator.
1201 * @param last An input iterator.
1202 * @param result An output iterator.
1203 * @param pred A predicate.
1204 * @return An iterator designating the end of the resulting sequence.
1206 * Copies each element in the range @p [first,last) for which
1207 * @p pred returns true to the range beginning at @p result.
1209 * remove_copy_if() is stable, so the relative order of elements that are
1210 * copied is unchanged.
1212 template<typename _InputIterator
, typename _OutputIterator
,
1213 typename _Predicate
>
1215 remove_copy_if(_InputIterator __first
, _InputIterator __last
,
1216 _OutputIterator __result
, _Predicate __pred
)
1218 // concept requirements
1219 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1220 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1221 typename iterator_traits
<_InputIterator
>::value_type
>)
1222 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1223 typename iterator_traits
<_InputIterator
>::value_type
>)
1224 __glibcxx_requires_valid_range(__first
, __last
);
1226 for ( ; __first
!= __last
; ++__first
)
1227 if (!__pred(*__first
))
1229 *__result
= *__first
;
1236 * @brief Remove elements from a sequence.
1237 * @param first An input iterator.
1238 * @param last An input iterator.
1239 * @param value The value to be removed.
1240 * @return An iterator designating the end of the resulting sequence.
1242 * All elements equal to @p value are removed from the range
1245 * remove() is stable, so the relative order of elements that are
1246 * not removed is unchanged.
1248 * Elements between the end of the resulting sequence and @p last
1249 * are still present, but their value is unspecified.
1251 template<typename _ForwardIterator
, typename _Tp
>
1253 remove(_ForwardIterator __first
, _ForwardIterator __last
,
1256 // concept requirements
1257 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1259 __glibcxx_function_requires(_EqualOpConcept
<
1260 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
1261 __glibcxx_requires_valid_range(__first
, __last
);
1263 __first
= std::find(__first
, __last
, __value
);
1264 _ForwardIterator __i
= __first
;
1265 return __first
== __last
? __first
1266 : std::remove_copy(++__i
, __last
,
1271 * @brief Remove elements from a sequence using a predicate.
1272 * @param first A forward iterator.
1273 * @param last A forward iterator.
1274 * @param pred A predicate.
1275 * @return An iterator designating the end of the resulting sequence.
1277 * All elements for which @p pred returns true are removed from the range
1280 * remove_if() is stable, so the relative order of elements that are
1281 * not removed is unchanged.
1283 * Elements between the end of the resulting sequence and @p last
1284 * are still present, but their value is unspecified.
1286 template<typename _ForwardIterator
, typename _Predicate
>
1288 remove_if(_ForwardIterator __first
, _ForwardIterator __last
,
1291 // concept requirements
1292 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1294 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1295 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1296 __glibcxx_requires_valid_range(__first
, __last
);
1298 __first
= std::find_if(__first
, __last
, __pred
);
1299 _ForwardIterator __i
= __first
;
1300 return __first
== __last
? __first
1301 : std::remove_copy_if(++__i
, __last
,
1307 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1309 * overloaded for forward iterators and output iterator as result.
1312 template<typename _ForwardIterator
, typename _OutputIterator
>
1314 __unique_copy(_ForwardIterator __first
, _ForwardIterator __last
,
1315 _OutputIterator __result
,
1316 forward_iterator_tag
, output_iterator_tag
)
1318 // concept requirements -- taken care of in dispatching function
1319 _ForwardIterator __next
= __first
;
1320 *__result
= *__first
;
1321 while (++__next
!= __last
)
1322 if (!(*__first
== *__next
))
1325 *++__result
= *__first
;
1332 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1334 * overloaded for input iterators and output iterator as result.
1337 template<typename _InputIterator
, typename _OutputIterator
>
1339 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1340 _OutputIterator __result
,
1341 input_iterator_tag
, output_iterator_tag
)
1343 // concept requirements -- taken care of in dispatching function
1344 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1345 *__result
= __value
;
1346 while (++__first
!= __last
)
1347 if (!(__value
== *__first
))
1350 *++__result
= __value
;
1357 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1359 * overloaded for input iterators and forward iterator as result.
1362 template<typename _InputIterator
, typename _ForwardIterator
>
1364 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1365 _ForwardIterator __result
,
1366 input_iterator_tag
, forward_iterator_tag
)
1368 // concept requirements -- taken care of in dispatching function
1369 *__result
= *__first
;
1370 while (++__first
!= __last
)
1371 if (!(*__result
== *__first
))
1372 *++__result
= *__first
;
1378 * This is an uglified
1379 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1381 * overloaded for forward iterators and output iterator as result.
1384 template<typename _ForwardIterator
, typename _OutputIterator
,
1385 typename _BinaryPredicate
>
1387 __unique_copy(_ForwardIterator __first
, _ForwardIterator __last
,
1388 _OutputIterator __result
, _BinaryPredicate __binary_pred
,
1389 forward_iterator_tag
, output_iterator_tag
)
1391 // concept requirements -- iterators already checked
1392 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1393 typename iterator_traits
<_ForwardIterator
>::value_type
,
1394 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1396 _ForwardIterator __next
= __first
;
1397 *__result
= *__first
;
1398 while (++__next
!= __last
)
1399 if (!__binary_pred(*__first
, *__next
))
1402 *++__result
= *__first
;
1409 * This is an uglified
1410 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1412 * overloaded for input iterators and output iterator as result.
1415 template<typename _InputIterator
, typename _OutputIterator
,
1416 typename _BinaryPredicate
>
1418 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1419 _OutputIterator __result
, _BinaryPredicate __binary_pred
,
1420 input_iterator_tag
, output_iterator_tag
)
1422 // concept requirements -- iterators already checked
1423 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1424 typename iterator_traits
<_InputIterator
>::value_type
,
1425 typename iterator_traits
<_InputIterator
>::value_type
>)
1427 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1428 *__result
= __value
;
1429 while (++__first
!= __last
)
1430 if (!__binary_pred(__value
, *__first
))
1433 *++__result
= __value
;
1440 * This is an uglified
1441 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1443 * overloaded for input iterators and forward iterator as result.
1446 template<typename _InputIterator
, typename _ForwardIterator
,
1447 typename _BinaryPredicate
>
1449 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1450 _ForwardIterator __result
, _BinaryPredicate __binary_pred
,
1451 input_iterator_tag
, forward_iterator_tag
)
1453 // concept requirements -- iterators already checked
1454 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1455 typename iterator_traits
<_ForwardIterator
>::value_type
,
1456 typename iterator_traits
<_InputIterator
>::value_type
>)
1458 *__result
= *__first
;
1459 while (++__first
!= __last
)
1460 if (!__binary_pred(*__result
, *__first
))
1461 *++__result
= *__first
;
1466 * @brief Copy a sequence, removing consecutive duplicate values.
1467 * @param first An input iterator.
1468 * @param last An input iterator.
1469 * @param result An output iterator.
1470 * @return An iterator designating the end of the resulting sequence.
1472 * Copies each element in the range @p [first,last) to the range
1473 * beginning at @p result, except that only the first element is copied
1474 * from groups of consecutive elements that compare equal.
1475 * unique_copy() is stable, so the relative order of elements that are
1476 * copied is unchanged.
1479 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1480 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1482 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1483 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
1487 template<typename _InputIterator
, typename _OutputIterator
>
1488 inline _OutputIterator
1489 unique_copy(_InputIterator __first
, _InputIterator __last
,
1490 _OutputIterator __result
)
1492 // concept requirements
1493 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1494 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1495 typename iterator_traits
<_InputIterator
>::value_type
>)
1496 __glibcxx_function_requires(_EqualityComparableConcept
<
1497 typename iterator_traits
<_InputIterator
>::value_type
>)
1498 __glibcxx_requires_valid_range(__first
, __last
);
1500 if (__first
== __last
)
1502 return std::__unique_copy(__first
, __last
, __result
,
1503 std::__iterator_category(__first
),
1504 std::__iterator_category(__result
));
1508 * @brief Copy a sequence, removing consecutive values using a predicate.
1509 * @param first An input iterator.
1510 * @param last An input iterator.
1511 * @param result An output iterator.
1512 * @param binary_pred A binary predicate.
1513 * @return An iterator designating the end of the resulting sequence.
1515 * Copies each element in the range @p [first,last) to the range
1516 * beginning at @p result, except that only the first element is copied
1517 * from groups of consecutive elements for which @p binary_pred returns
1519 * unique_copy() is stable, so the relative order of elements that are
1520 * copied is unchanged.
1523 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1524 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1527 template<typename _InputIterator
, typename _OutputIterator
,
1528 typename _BinaryPredicate
>
1529 inline _OutputIterator
1530 unique_copy(_InputIterator __first
, _InputIterator __last
,
1531 _OutputIterator __result
,
1532 _BinaryPredicate __binary_pred
)
1534 // concept requirements -- predicates checked later
1535 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1536 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1537 typename iterator_traits
<_InputIterator
>::value_type
>)
1538 __glibcxx_requires_valid_range(__first
, __last
);
1540 if (__first
== __last
)
1542 return std::__unique_copy(__first
, __last
, __result
, __binary_pred
,
1543 std::__iterator_category(__first
),
1544 std::__iterator_category(__result
));
1548 * @brief Remove consecutive duplicate values from a sequence.
1549 * @param first A forward iterator.
1550 * @param last A forward iterator.
1551 * @return An iterator designating the end of the resulting sequence.
1553 * Removes all but the first element from each group of consecutive
1554 * values that compare equal.
1555 * unique() is stable, so the relative order of elements that are
1556 * not removed is unchanged.
1557 * Elements between the end of the resulting sequence and @p last
1558 * are still present, but their value is unspecified.
1560 template<typename _ForwardIterator
>
1562 unique(_ForwardIterator __first
, _ForwardIterator __last
)
1564 // concept requirements
1565 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1567 __glibcxx_function_requires(_EqualityComparableConcept
<
1568 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1569 __glibcxx_requires_valid_range(__first
, __last
);
1571 // Skip the beginning, if already unique.
1572 __first
= std::adjacent_find(__first
, __last
);
1573 if (__first
== __last
)
1576 // Do the real copy work.
1577 _ForwardIterator __dest
= __first
;
1579 while (++__first
!= __last
)
1580 if (!(*__dest
== *__first
))
1581 *++__dest
= *__first
;
1586 * @brief Remove consecutive values from a sequence using a predicate.
1587 * @param first A forward iterator.
1588 * @param last A forward iterator.
1589 * @param binary_pred A binary predicate.
1590 * @return An iterator designating the end of the resulting sequence.
1592 * Removes all but the first element from each group of consecutive
1593 * values for which @p binary_pred returns true.
1594 * unique() is stable, so the relative order of elements that are
1595 * not removed is unchanged.
1596 * Elements between the end of the resulting sequence and @p last
1597 * are still present, but their value is unspecified.
1599 template<typename _ForwardIterator
, typename _BinaryPredicate
>
1601 unique(_ForwardIterator __first
, _ForwardIterator __last
,
1602 _BinaryPredicate __binary_pred
)
1604 // concept requirements
1605 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1607 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1608 typename iterator_traits
<_ForwardIterator
>::value_type
,
1609 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1610 __glibcxx_requires_valid_range(__first
, __last
);
1612 // Skip the beginning, if already unique.
1613 __first
= std::adjacent_find(__first
, __last
, __binary_pred
);
1614 if (__first
== __last
)
1617 // Do the real copy work.
1618 _ForwardIterator __dest
= __first
;
1620 while (++__first
!= __last
)
1621 if (!__binary_pred(*__dest
, *__first
))
1622 *++__dest
= *__first
;
1628 * This is an uglified reverse(_BidirectionalIterator,
1629 * _BidirectionalIterator)
1630 * overloaded for bidirectional iterators.
1633 template<typename _BidirectionalIterator
>
1635 __reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1636 bidirectional_iterator_tag
)
1639 if (__first
== __last
|| __first
== --__last
)
1643 std::iter_swap(__first
, __last
);
1650 * This is an uglified reverse(_BidirectionalIterator,
1651 * _BidirectionalIterator)
1652 * overloaded for random access iterators.
1655 template<typename _RandomAccessIterator
>
1657 __reverse(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1658 random_access_iterator_tag
)
1660 if (__first
== __last
)
1663 while (__first
< __last
)
1665 std::iter_swap(__first
, __last
);
1672 * @brief Reverse a sequence.
1673 * @param first A bidirectional iterator.
1674 * @param last A bidirectional iterator.
1675 * @return reverse() returns no value.
1677 * Reverses the order of the elements in the range @p [first,last),
1678 * so that the first element becomes the last etc.
1679 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1680 * swaps @p *(first+i) and @p *(last-(i+1))
1682 template<typename _BidirectionalIterator
>
1684 reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
)
1686 // concept requirements
1687 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1688 _BidirectionalIterator
>)
1689 __glibcxx_requires_valid_range(__first
, __last
);
1690 std::__reverse(__first
, __last
, std::__iterator_category(__first
));
1694 * @brief Copy a sequence, reversing its elements.
1695 * @param first A bidirectional iterator.
1696 * @param last A bidirectional iterator.
1697 * @param result An output iterator.
1698 * @return An iterator designating the end of the resulting sequence.
1700 * Copies the elements in the range @p [first,last) to the range
1701 * @p [result,result+(last-first)) such that the order of the
1702 * elements is reversed.
1703 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1704 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1705 * The ranges @p [first,last) and @p [result,result+(last-first))
1708 template<typename _BidirectionalIterator
, typename _OutputIterator
>
1710 reverse_copy(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1711 _OutputIterator __result
)
1713 // concept requirements
1714 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
1715 _BidirectionalIterator
>)
1716 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1717 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
1718 __glibcxx_requires_valid_range(__first
, __last
);
1720 while (__first
!= __last
)
1723 *__result
= *__last
;
1732 * This is a helper function for the rotate algorithm specialized on RAIs.
1733 * It returns the greatest common divisor of two integer values.
1736 template<typename _EuclideanRingElement
>
1737 _EuclideanRingElement
1738 __gcd(_EuclideanRingElement __m
, _EuclideanRingElement __n
)
1742 _EuclideanRingElement __t
= __m
% __n
;
1751 * This is a helper function for the rotate algorithm.
1754 template<typename _ForwardIterator
>
1756 __rotate(_ForwardIterator __first
,
1757 _ForwardIterator __middle
,
1758 _ForwardIterator __last
,
1759 forward_iterator_tag
)
1761 if (__first
== __middle
|| __last
== __middle
)
1764 _ForwardIterator __first2
= __middle
;
1767 swap(*__first
, *__first2
);
1770 if (__first
== __middle
)
1771 __middle
= __first2
;
1773 while (__first2
!= __last
);
1775 __first2
= __middle
;
1777 while (__first2
!= __last
)
1779 swap(*__first
, *__first2
);
1782 if (__first
== __middle
)
1783 __middle
= __first2
;
1784 else if (__first2
== __last
)
1785 __first2
= __middle
;
1791 * This is a helper function for the rotate algorithm.
1794 template<typename _BidirectionalIterator
>
1796 __rotate(_BidirectionalIterator __first
,
1797 _BidirectionalIterator __middle
,
1798 _BidirectionalIterator __last
,
1799 bidirectional_iterator_tag
)
1801 // concept requirements
1802 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1803 _BidirectionalIterator
>)
1805 if (__first
== __middle
|| __last
== __middle
)
1808 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1809 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1811 while (__first
!= __middle
&& __middle
!= __last
)
1813 swap(*__first
, *--__last
);
1817 if (__first
== __middle
)
1818 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1820 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1825 * This is a helper function for the rotate algorithm.
1828 template<typename _RandomAccessIterator
>
1830 __rotate(_RandomAccessIterator __first
,
1831 _RandomAccessIterator __middle
,
1832 _RandomAccessIterator __last
,
1833 random_access_iterator_tag
)
1835 // concept requirements
1836 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1837 _RandomAccessIterator
>)
1839 if (__first
== __middle
|| __last
== __middle
)
1842 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
1844 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
1847 const _Distance __n
= __last
- __first
;
1848 const _Distance __k
= __middle
- __first
;
1849 const _Distance __l
= __n
- __k
;
1853 std::swap_ranges(__first
, __middle
, __middle
);
1857 const _Distance __d
= __gcd(__n
, __k
);
1859 for (_Distance __i
= 0; __i
< __d
; __i
++)
1861 _ValueType __tmp
= *__first
;
1862 _RandomAccessIterator __p
= __first
;
1866 for (_Distance __j
= 0; __j
< __l
/ __d
; __j
++)
1868 if (__p
> __first
+ __l
)
1870 *__p
= *(__p
- __l
);
1874 *__p
= *(__p
+ __k
);
1880 for (_Distance __j
= 0; __j
< __k
/ __d
- 1; __j
++)
1882 if (__p
< __last
- __k
)
1884 *__p
= *(__p
+ __k
);
1887 *__p
= * (__p
- __l
);
1898 * @brief Rotate the elements of a sequence.
1899 * @param first A forward iterator.
1900 * @param middle A forward iterator.
1901 * @param last A forward iterator.
1904 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1905 * positions so that the element at @p middle is moved to @p first, the
1906 * element at @p middle+1 is moved to @first+1 and so on for each element
1907 * in the range @p [first,last).
1909 * This effectively swaps the ranges @p [first,middle) and
1912 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1913 * each @p n in the range @p [0,last-first).
1915 template<typename _ForwardIterator
>
1917 rotate(_ForwardIterator __first
, _ForwardIterator __middle
,
1918 _ForwardIterator __last
)
1920 // concept requirements
1921 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1923 __glibcxx_requires_valid_range(__first
, __middle
);
1924 __glibcxx_requires_valid_range(__middle
, __last
);
1926 typedef typename iterator_traits
<_ForwardIterator
>::iterator_category
1928 std::__rotate(__first
, __middle
, __last
, _IterType());
1932 * @brief Copy a sequence, rotating its elements.
1933 * @param first A forward iterator.
1934 * @param middle A forward iterator.
1935 * @param last A forward iterator.
1936 * @param result An output iterator.
1937 * @return An iterator designating the end of the resulting sequence.
1939 * Copies the elements of the range @p [first,last) to the range
1940 * beginning at @result, rotating the copied elements by @p (middle-first)
1941 * positions so that the element at @p middle is moved to @p result, the
1942 * element at @p middle+1 is moved to @result+1 and so on for each element
1943 * in the range @p [first,last).
1945 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1946 * each @p n in the range @p [0,last-first).
1948 template<typename _ForwardIterator
, typename _OutputIterator
>
1950 rotate_copy(_ForwardIterator __first
, _ForwardIterator __middle
,
1951 _ForwardIterator __last
, _OutputIterator __result
)
1953 // concept requirements
1954 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1955 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1956 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1957 __glibcxx_requires_valid_range(__first
, __middle
);
1958 __glibcxx_requires_valid_range(__middle
, __last
);
1960 return std::copy(__first
, __middle
,
1961 std::copy(__middle
, __last
, __result
));
1965 * @brief Randomly shuffle the elements of a sequence.
1966 * @param first A forward iterator.
1967 * @param last A forward iterator.
1970 * Reorder the elements in the range @p [first,last) using a random
1971 * distribution, so that every possible ordering of the sequence is
1974 template<typename _RandomAccessIterator
>
1976 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
1978 // concept requirements
1979 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1980 _RandomAccessIterator
>)
1981 __glibcxx_requires_valid_range(__first
, __last
);
1983 if (__first
!= __last
)
1984 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
1985 std::iter_swap(__i
, __first
+ (std::rand() % ((__i
- __first
) + 1)));
1989 * @brief Shuffle the elements of a sequence using a random number
1991 * @param first A forward iterator.
1992 * @param last A forward iterator.
1993 * @param rand The RNG functor or function.
1996 * Reorders the elements in the range @p [first,last) using @p rand to
1997 * provide a random distribution. Calling @p rand(N) for a positive
1998 * integer @p N should return a randomly chosen integer from the
2001 template<typename _RandomAccessIterator
, typename _RandomNumberGenerator
>
2003 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
2004 _RandomNumberGenerator
& __rand
)
2006 // concept requirements
2007 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2008 _RandomAccessIterator
>)
2009 __glibcxx_requires_valid_range(__first
, __last
);
2011 if (__first
== __last
)
2013 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2014 std::iter_swap(__i
, __first
+ __rand((__i
- __first
) + 1));
2020 * This is a helper function...
2023 template<typename _ForwardIterator
, typename _Predicate
>
2025 __partition(_ForwardIterator __first
, _ForwardIterator __last
,
2027 forward_iterator_tag
)
2029 if (__first
== __last
)
2032 while (__pred(*__first
))
2033 if (++__first
== __last
)
2036 _ForwardIterator __next
= __first
;
2038 while (++__next
!= __last
)
2039 if (__pred(*__next
))
2041 swap(*__first
, *__next
);
2050 * This is a helper function...
2053 template<typename _BidirectionalIterator
, typename _Predicate
>
2054 _BidirectionalIterator
2055 __partition(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
2057 bidirectional_iterator_tag
)
2062 if (__first
== __last
)
2064 else if (__pred(*__first
))
2070 if (__first
== __last
)
2072 else if (!__pred(*__last
))
2076 std::iter_swap(__first
, __last
);
2082 * @brief Move elements for which a predicate is true to the beginning
2084 * @param first A forward iterator.
2085 * @param last A forward iterator.
2086 * @param pred A predicate functor.
2087 * @return An iterator @p middle such that @p pred(i) is true for each
2088 * iterator @p i in the range @p [first,middle) and false for each @p i
2089 * in the range @p [middle,last).
2091 * @p pred must not modify its operand. @p partition() does not preserve
2092 * the relative ordering of elements in each group, use
2093 * @p stable_partition() if this is needed.
2095 template<typename _ForwardIterator
, typename _Predicate
>
2096 inline _ForwardIterator
2097 partition(_ForwardIterator __first
, _ForwardIterator __last
,
2100 // concept requirements
2101 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
2103 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
2104 typename iterator_traits
<_ForwardIterator
>::value_type
>)
2105 __glibcxx_requires_valid_range(__first
, __last
);
2107 return std::__partition(__first
, __last
, __pred
,
2108 std::__iterator_category(__first
));
2114 * This is a helper function...
2117 template<typename _ForwardIterator
, typename _Predicate
, typename _Distance
>
2119 __inplace_stable_partition(_ForwardIterator __first
,
2120 _ForwardIterator __last
,
2121 _Predicate __pred
, _Distance __len
)
2124 return __pred(*__first
) ? __last
: __first
;
2125 _ForwardIterator __middle
= __first
;
2126 std::advance(__middle
, __len
/ 2);
2127 _ForwardIterator __begin
= std::__inplace_stable_partition(__first
,
2131 _ForwardIterator __end
= std::__inplace_stable_partition(__middle
, __last
,
2135 std::rotate(__begin
, __middle
, __end
);
2136 std::advance(__begin
, std::distance(__middle
, __end
));
2142 * This is a helper function...
2145 template<typename _ForwardIterator
, typename _Pointer
, typename _Predicate
,
2148 __stable_partition_adaptive(_ForwardIterator __first
,
2149 _ForwardIterator __last
,
2150 _Predicate __pred
, _Distance __len
,
2152 _Distance __buffer_size
)
2154 if (__len
<= __buffer_size
)
2156 _ForwardIterator __result1
= __first
;
2157 _Pointer __result2
= __buffer
;
2158 for ( ; __first
!= __last
; ++__first
)
2159 if (__pred(*__first
))
2161 *__result1
= *__first
;
2166 *__result2
= *__first
;
2169 std::copy(__buffer
, __result2
, __result1
);
2174 _ForwardIterator __middle
= __first
;
2175 std::advance(__middle
, __len
/ 2);
2176 _ForwardIterator __begin
=
2177 std::__stable_partition_adaptive(__first
, __middle
, __pred
,
2178 __len
/ 2, __buffer
,
2180 _ForwardIterator __end
=
2181 std::__stable_partition_adaptive(__middle
, __last
, __pred
,
2183 __buffer
, __buffer_size
);
2184 std::rotate(__begin
, __middle
, __end
);
2185 std::advance(__begin
, std::distance(__middle
, __end
));
2191 * @brief Move elements for which a predicate is true to the beginning
2192 * of a sequence, preserving relative ordering.
2193 * @param first A forward iterator.
2194 * @param last A forward iterator.
2195 * @param pred A predicate functor.
2196 * @return An iterator @p middle such that @p pred(i) is true for each
2197 * iterator @p i in the range @p [first,middle) and false for each @p i
2198 * in the range @p [middle,last).
2200 * Performs the same function as @p partition() with the additional
2201 * guarantee that the relative ordering of elements in each group is
2202 * preserved, so any two elements @p x and @p y in the range
2203 * @p [first,last) such that @p pred(x)==pred(y) will have the same
2204 * relative ordering after calling @p stable_partition().
2206 template<typename _ForwardIterator
, typename _Predicate
>
2208 stable_partition(_ForwardIterator __first
, _ForwardIterator __last
,
2211 // concept requirements
2212 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
2214 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
2215 typename iterator_traits
<_ForwardIterator
>::value_type
>)
2216 __glibcxx_requires_valid_range(__first
, __last
);
2218 if (__first
== __last
)
2222 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2224 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2227 _Temporary_buffer
<_ForwardIterator
, _ValueType
> __buf(__first
,
2229 if (__buf
.size() > 0)
2231 std::__stable_partition_adaptive(__first
, __last
, __pred
,
2232 _DistanceType(__buf
.requested_size()),
2233 __buf
.begin(), __buf
.size());
2236 std::__inplace_stable_partition(__first
, __last
, __pred
,
2237 _DistanceType(__buf
.requested_size()));
2243 * This is a helper function...
2246 template<typename _RandomAccessIterator
, typename _Tp
>
2247 _RandomAccessIterator
2248 __unguarded_partition(_RandomAccessIterator __first
,
2249 _RandomAccessIterator __last
, _Tp __pivot
)
2253 while (*__first
< __pivot
)
2256 while (__pivot
< *__last
)
2258 if (!(__first
< __last
))
2260 std::iter_swap(__first
, __last
);
2267 * This is a helper function...
2270 template<typename _RandomAccessIterator
, typename _Tp
, typename _Compare
>
2271 _RandomAccessIterator
2272 __unguarded_partition(_RandomAccessIterator __first
,
2273 _RandomAccessIterator __last
,
2274 _Tp __pivot
, _Compare __comp
)
2278 while (__comp(*__first
, __pivot
))
2281 while (__comp(__pivot
, *__last
))
2283 if (!(__first
< __last
))
2285 std::iter_swap(__first
, __last
);
2293 * This controls some aspect of the sort routines.
2296 enum { _S_threshold
= 16 };
2300 * This is a helper function for the sort routine.
2303 template<typename _RandomAccessIterator
, typename _Tp
>
2305 __unguarded_linear_insert(_RandomAccessIterator __last
, _Tp __val
)
2307 _RandomAccessIterator __next
= __last
;
2309 while (__val
< *__next
)
2320 * This is a helper function for the sort routine.
2323 template<typename _RandomAccessIterator
, typename _Tp
, typename _Compare
>
2325 __unguarded_linear_insert(_RandomAccessIterator __last
, _Tp __val
,
2328 _RandomAccessIterator __next
= __last
;
2330 while (__comp(__val
, *__next
))
2341 * This is a helper function for the sort routine.
2344 template<typename _RandomAccessIterator
>
2346 __insertion_sort(_RandomAccessIterator __first
,
2347 _RandomAccessIterator __last
)
2349 if (__first
== __last
)
2352 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2354 typename iterator_traits
<_RandomAccessIterator
>::value_type
2356 if (__val
< *__first
)
2358 std::copy_backward(__first
, __i
, __i
+ 1);
2362 std::__unguarded_linear_insert(__i
, __val
);
2368 * This is a helper function for the sort routine.
2371 template<typename _RandomAccessIterator
, typename _Compare
>
2373 __insertion_sort(_RandomAccessIterator __first
,
2374 _RandomAccessIterator __last
, _Compare __comp
)
2376 if (__first
== __last
) return;
2378 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2380 typename iterator_traits
<_RandomAccessIterator
>::value_type
2382 if (__comp(__val
, *__first
))
2384 std::copy_backward(__first
, __i
, __i
+ 1);
2388 std::__unguarded_linear_insert(__i
, __val
, __comp
);
2394 * This is a helper function for the sort routine.
2397 template<typename _RandomAccessIterator
>
2399 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2400 _RandomAccessIterator __last
)
2402 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2405 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2406 std::__unguarded_linear_insert(__i
, _ValueType(*__i
));
2411 * This is a helper function for the sort routine.
2414 template<typename _RandomAccessIterator
, typename _Compare
>
2416 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2417 _RandomAccessIterator __last
, _Compare __comp
)
2419 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2422 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2423 std::__unguarded_linear_insert(__i
, _ValueType(*__i
), __comp
);
2428 * This is a helper function for the sort routine.
2431 template<typename _RandomAccessIterator
>
2433 __final_insertion_sort(_RandomAccessIterator __first
,
2434 _RandomAccessIterator __last
)
2436 if (__last
- __first
> int(_S_threshold
))
2438 std::__insertion_sort(__first
, __first
+ int(_S_threshold
));
2439 std::__unguarded_insertion_sort(__first
+ int(_S_threshold
), __last
);
2442 std::__insertion_sort(__first
, __last
);
2447 * This is a helper function for the sort routine.
2450 template<typename _RandomAccessIterator
, typename _Compare
>
2452 __final_insertion_sort(_RandomAccessIterator __first
,
2453 _RandomAccessIterator __last
, _Compare __comp
)
2455 if (__last
- __first
> int(_S_threshold
))
2457 std::__insertion_sort(__first
, __first
+ int(_S_threshold
), __comp
);
2458 std::__unguarded_insertion_sort(__first
+ int(_S_threshold
), __last
,
2462 std::__insertion_sort(__first
, __last
, __comp
);
2467 * This is a helper function for the sort routines.
2470 template<typename _RandomAccessIterator
>
2472 __heap_select(_RandomAccessIterator __first
,
2473 _RandomAccessIterator __middle
,
2474 _RandomAccessIterator __last
)
2476 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2479 std::make_heap(__first
, __middle
);
2480 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
2481 if (*__i
< *__first
)
2482 std::__pop_heap(__first
, __middle
, __i
, _ValueType(*__i
));
2487 * This is a helper function for the sort routines.
2490 template<typename _RandomAccessIterator
, typename _Compare
>
2492 __heap_select(_RandomAccessIterator __first
,
2493 _RandomAccessIterator __middle
,
2494 _RandomAccessIterator __last
, _Compare __comp
)
2496 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2499 std::make_heap(__first
, __middle
, __comp
);
2500 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
2501 if (__comp(*__i
, *__first
))
2502 std::__pop_heap(__first
, __middle
, __i
, _ValueType(*__i
), __comp
);
2507 * This is a helper function for the sort routines.
2510 template<typename _Size
>
2515 for (__k
= 0; __n
!= 1; __n
>>= 1)
2521 * @brief Sort the smallest elements of a sequence.
2522 * @param first An iterator.
2523 * @param middle Another iterator.
2524 * @param last Another iterator.
2527 * Sorts the smallest @p (middle-first) elements in the range
2528 * @p [first,last) and moves them to the range @p [first,middle). The
2529 * order of the remaining elements in the range @p [middle,last) is
2531 * After the sort if @p i and @j are iterators in the range
2532 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2533 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2535 template<typename _RandomAccessIterator
>
2537 partial_sort(_RandomAccessIterator __first
,
2538 _RandomAccessIterator __middle
,
2539 _RandomAccessIterator __last
)
2541 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2544 // concept requirements
2545 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2546 _RandomAccessIterator
>)
2547 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
2548 __glibcxx_requires_valid_range(__first
, __middle
);
2549 __glibcxx_requires_valid_range(__middle
, __last
);
2551 std::__heap_select(__first
, __middle
, __last
);
2552 std::sort_heap(__first
, __middle
);
2556 * @brief Sort the smallest elements of a sequence using a predicate
2558 * @param first An iterator.
2559 * @param middle Another iterator.
2560 * @param last Another iterator.
2561 * @param comp A comparison functor.
2564 * Sorts the smallest @p (middle-first) elements in the range
2565 * @p [first,last) and moves them to the range @p [first,middle). The
2566 * order of the remaining elements in the range @p [middle,last) is
2568 * After the sort if @p i and @j are iterators in the range
2569 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2570 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2573 template<typename _RandomAccessIterator
, typename _Compare
>
2575 partial_sort(_RandomAccessIterator __first
,
2576 _RandomAccessIterator __middle
,
2577 _RandomAccessIterator __last
,
2580 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2583 // concept requirements
2584 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2585 _RandomAccessIterator
>)
2586 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2587 _ValueType
, _ValueType
>)
2588 __glibcxx_requires_valid_range(__first
, __middle
);
2589 __glibcxx_requires_valid_range(__middle
, __last
);
2591 std::__heap_select(__first
, __middle
, __last
, __comp
);
2592 std::sort_heap(__first
, __middle
, __comp
);
2596 * @brief Copy the smallest elements of a sequence.
2597 * @param first An iterator.
2598 * @param last Another iterator.
2599 * @param result_first A random-access iterator.
2600 * @param result_last Another random-access iterator.
2601 * @return An iterator indicating the end of the resulting sequence.
2603 * Copies and sorts the smallest N values from the range @p [first,last)
2604 * to the range beginning at @p result_first, where the number of
2605 * elements to be copied, @p N, is the smaller of @p (last-first) and
2606 * @p (result_last-result_first).
2607 * After the sort if @p i and @j are iterators in the range
2608 * @p [result_first,result_first+N) such that @i precedes @j then
2609 * @p *j<*i is false.
2610 * The value returned is @p result_first+N.
2612 template<typename _InputIterator
, typename _RandomAccessIterator
>
2613 _RandomAccessIterator
2614 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2615 _RandomAccessIterator __result_first
,
2616 _RandomAccessIterator __result_last
)
2618 typedef typename iterator_traits
<_InputIterator
>::value_type
2620 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2622 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2625 // concept requirements
2626 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2627 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2629 __glibcxx_function_requires(_LessThanOpConcept
<_InputValueType
,
2631 __glibcxx_function_requires(_LessThanComparableConcept
<_OutputValueType
>)
2632 __glibcxx_requires_valid_range(__first
, __last
);
2633 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2635 if (__result_first
== __result_last
)
2636 return __result_last
;
2637 _RandomAccessIterator __result_real_last
= __result_first
;
2638 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2640 *__result_real_last
= *__first
;
2641 ++__result_real_last
;
2644 std::make_heap(__result_first
, __result_real_last
);
2645 while (__first
!= __last
)
2647 if (*__first
< *__result_first
)
2648 std::__adjust_heap(__result_first
, _DistanceType(0),
2649 _DistanceType(__result_real_last
2651 _InputValueType(*__first
));
2654 std::sort_heap(__result_first
, __result_real_last
);
2655 return __result_real_last
;
2659 * @brief Copy the smallest elements of a sequence using a predicate for
2661 * @param first An input iterator.
2662 * @param last Another input iterator.
2663 * @param result_first A random-access iterator.
2664 * @param result_last Another random-access iterator.
2665 * @param comp A comparison functor.
2666 * @return An iterator indicating the end of the resulting sequence.
2668 * Copies and sorts the smallest N values from the range @p [first,last)
2669 * to the range beginning at @p result_first, where the number of
2670 * elements to be copied, @p N, is the smaller of @p (last-first) and
2671 * @p (result_last-result_first).
2672 * After the sort if @p i and @j are iterators in the range
2673 * @p [result_first,result_first+N) such that @i precedes @j then
2674 * @p comp(*j,*i) is false.
2675 * The value returned is @p result_first+N.
2677 template<typename _InputIterator
, typename _RandomAccessIterator
, typename _Compare
>
2678 _RandomAccessIterator
2679 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2680 _RandomAccessIterator __result_first
,
2681 _RandomAccessIterator __result_last
,
2684 typedef typename iterator_traits
<_InputIterator
>::value_type
2686 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2688 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2691 // concept requirements
2692 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2693 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2694 _RandomAccessIterator
>)
2695 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2697 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2698 _InputValueType
, _OutputValueType
>)
2699 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2700 _OutputValueType
, _OutputValueType
>)
2701 __glibcxx_requires_valid_range(__first
, __last
);
2702 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2704 if (__result_first
== __result_last
)
2705 return __result_last
;
2706 _RandomAccessIterator __result_real_last
= __result_first
;
2707 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2709 *__result_real_last
= *__first
;
2710 ++__result_real_last
;
2713 std::make_heap(__result_first
, __result_real_last
, __comp
);
2714 while (__first
!= __last
)
2716 if (__comp(*__first
, *__result_first
))
2717 std::__adjust_heap(__result_first
, _DistanceType(0),
2718 _DistanceType(__result_real_last
2720 _InputValueType(*__first
),
2724 std::sort_heap(__result_first
, __result_real_last
, __comp
);
2725 return __result_real_last
;
2730 * This is a helper function for the sort routine.
2733 template<typename _RandomAccessIterator
, typename _Size
>
2735 __introsort_loop(_RandomAccessIterator __first
,
2736 _RandomAccessIterator __last
,
2737 _Size __depth_limit
)
2739 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2742 while (__last
- __first
> int(_S_threshold
))
2744 if (__depth_limit
== 0)
2746 std::partial_sort(__first
, __last
, __last
);
2750 _RandomAccessIterator __cut
=
2751 std::__unguarded_partition(__first
, __last
,
2752 _ValueType(std::__median(*__first
,
2759 std::__introsort_loop(__cut
, __last
, __depth_limit
);
2766 * This is a helper function for the sort routine.
2769 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
2771 __introsort_loop(_RandomAccessIterator __first
,
2772 _RandomAccessIterator __last
,
2773 _Size __depth_limit
, _Compare __comp
)
2775 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2778 while (__last
- __first
> int(_S_threshold
))
2780 if (__depth_limit
== 0)
2782 std::partial_sort(__first
, __last
, __last
, __comp
);
2786 _RandomAccessIterator __cut
=
2787 std::__unguarded_partition(__first
, __last
,
2788 _ValueType(std::__median(*__first
,
2796 std::__introsort_loop(__cut
, __last
, __depth_limit
, __comp
);
2802 * @brief Sort the elements of a sequence.
2803 * @param first An iterator.
2804 * @param last Another iterator.
2807 * Sorts the elements in the range @p [first,last) in ascending order,
2808 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2809 * @p [first,last-1).
2811 * The relative ordering of equivalent elements is not preserved, use
2812 * @p stable_sort() if this is needed.
2814 template<typename _RandomAccessIterator
>
2816 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
2818 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2821 // concept requirements
2822 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2823 _RandomAccessIterator
>)
2824 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
2825 __glibcxx_requires_valid_range(__first
, __last
);
2827 if (__first
!= __last
)
2829 std::__introsort_loop(__first
, __last
,
2830 std::__lg(__last
- __first
) * 2);
2831 std::__final_insertion_sort(__first
, __last
);
2836 * @brief Sort the elements of a sequence using a predicate for comparison.
2837 * @param first An iterator.
2838 * @param last Another iterator.
2839 * @param comp A comparison functor.
2842 * Sorts the elements in the range @p [first,last) in ascending order,
2843 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2844 * range @p [first,last-1).
2846 * The relative ordering of equivalent elements is not preserved, use
2847 * @p stable_sort() if this is needed.
2849 template<typename _RandomAccessIterator
, typename _Compare
>
2851 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
2854 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2857 // concept requirements
2858 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2859 _RandomAccessIterator
>)
2860 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
, _ValueType
,
2862 __glibcxx_requires_valid_range(__first
, __last
);
2864 if (__first
!= __last
)
2866 std::__introsort_loop(__first
, __last
,
2867 std::__lg(__last
- __first
) * 2, __comp
);
2868 std::__final_insertion_sort(__first
, __last
, __comp
);
2873 * @brief Finds the first position in which @a val could be inserted
2874 * without changing the ordering.
2875 * @param first An iterator.
2876 * @param last Another iterator.
2877 * @param val The search term.
2878 * @return An iterator pointing to the first element "not less than" @a val,
2879 * or end() if every element is less than @a val.
2880 * @ingroup binarysearch
2882 template<typename _ForwardIterator
, typename _Tp
>
2884 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2887 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2889 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2892 // concept requirements
2893 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2894 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType
, _Tp
>)
2895 __glibcxx_requires_partitioned(__first
, __last
, __val
);
2897 _DistanceType __len
= std::distance(__first
, __last
);
2898 _DistanceType __half
;
2899 _ForwardIterator __middle
;
2903 __half
= __len
>> 1;
2905 std::advance(__middle
, __half
);
2906 if (*__middle
< __val
)
2910 __len
= __len
- __half
- 1;
2919 * @brief Finds the first position in which @a val could be inserted
2920 * without changing the ordering.
2921 * @param first An iterator.
2922 * @param last Another iterator.
2923 * @param val The search term.
2924 * @param comp A functor to use for comparisons.
2925 * @return An iterator pointing to the first element "not less than" @a val,
2926 * or end() if every element is less than @a val.
2927 * @ingroup binarysearch
2929 * The comparison function should have the same effects on ordering as
2930 * the function used for the initial sort.
2932 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2934 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2935 const _Tp
& __val
, _Compare __comp
)
2937 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2939 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2942 // concept requirements
2943 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2944 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2946 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
2948 _DistanceType __len
= std::distance(__first
, __last
);
2949 _DistanceType __half
;
2950 _ForwardIterator __middle
;
2954 __half
= __len
>> 1;
2956 std::advance(__middle
, __half
);
2957 if (__comp(*__middle
, __val
))
2961 __len
= __len
- __half
- 1;
2970 * @brief Finds the last position in which @a val could be inserted
2971 * without changing the ordering.
2972 * @param first An iterator.
2973 * @param last Another iterator.
2974 * @param val The search term.
2975 * @return An iterator pointing to the first element greater than @a val,
2976 * or end() if no elements are greater than @a val.
2977 * @ingroup binarysearch
2979 template<typename _ForwardIterator
, typename _Tp
>
2981 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2984 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2986 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2989 // concept requirements
2990 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2991 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
2992 __glibcxx_requires_partitioned(__first
, __last
, __val
);
2994 _DistanceType __len
= std::distance(__first
, __last
);
2995 _DistanceType __half
;
2996 _ForwardIterator __middle
;
3000 __half
= __len
>> 1;
3002 std::advance(__middle
, __half
);
3003 if (__val
< *__middle
)
3009 __len
= __len
- __half
- 1;
3016 * @brief Finds the last position in which @a val could be inserted
3017 * without changing the ordering.
3018 * @param first An iterator.
3019 * @param last Another iterator.
3020 * @param val The search term.
3021 * @param comp A functor to use for comparisons.
3022 * @return An iterator pointing to the first element greater than @a val,
3023 * or end() if no elements are greater than @a val.
3024 * @ingroup binarysearch
3026 * The comparison function should have the same effects on ordering as
3027 * the function used for the initial sort.
3029 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
3031 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
3032 const _Tp
& __val
, _Compare __comp
)
3034 typedef typename iterator_traits
<_ForwardIterator
>::value_type
3036 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
3039 // concept requirements
3040 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3041 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3043 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
3045 _DistanceType __len
= std::distance(__first
, __last
);
3046 _DistanceType __half
;
3047 _ForwardIterator __middle
;
3051 __half
= __len
>> 1;
3053 std::advance(__middle
, __half
);
3054 if (__comp(__val
, *__middle
))
3060 __len
= __len
- __half
- 1;
3068 * This is a helper function for the merge routines.
3071 template<typename _BidirectionalIterator
, typename _Distance
>
3073 __merge_without_buffer(_BidirectionalIterator __first
,
3074 _BidirectionalIterator __middle
,
3075 _BidirectionalIterator __last
,
3076 _Distance __len1
, _Distance __len2
)
3078 if (__len1
== 0 || __len2
== 0)
3080 if (__len1
+ __len2
== 2)
3082 if (*__middle
< *__first
)
3083 std::iter_swap(__first
, __middle
);
3086 _BidirectionalIterator __first_cut
= __first
;
3087 _BidirectionalIterator __second_cut
= __middle
;
3088 _Distance __len11
= 0;
3089 _Distance __len22
= 0;
3090 if (__len1
> __len2
)
3092 __len11
= __len1
/ 2;
3093 std::advance(__first_cut
, __len11
);
3094 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
);
3095 __len22
= std::distance(__middle
, __second_cut
);
3099 __len22
= __len2
/ 2;
3100 std::advance(__second_cut
, __len22
);
3101 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
);
3102 __len11
= std::distance(__first
, __first_cut
);
3104 std::rotate(__first_cut
, __middle
, __second_cut
);
3105 _BidirectionalIterator __new_middle
= __first_cut
;
3106 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
3107 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
3109 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
3110 __len1
- __len11
, __len2
- __len22
);
3115 * This is a helper function for the merge routines.
3118 template<typename _BidirectionalIterator
, typename _Distance
,
3121 __merge_without_buffer(_BidirectionalIterator __first
,
3122 _BidirectionalIterator __middle
,
3123 _BidirectionalIterator __last
,
3124 _Distance __len1
, _Distance __len2
,
3127 if (__len1
== 0 || __len2
== 0)
3129 if (__len1
+ __len2
== 2)
3131 if (__comp(*__middle
, *__first
))
3132 std::iter_swap(__first
, __middle
);
3135 _BidirectionalIterator __first_cut
= __first
;
3136 _BidirectionalIterator __second_cut
= __middle
;
3137 _Distance __len11
= 0;
3138 _Distance __len22
= 0;
3139 if (__len1
> __len2
)
3141 __len11
= __len1
/ 2;
3142 std::advance(__first_cut
, __len11
);
3143 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
3145 __len22
= std::distance(__middle
, __second_cut
);
3149 __len22
= __len2
/ 2;
3150 std::advance(__second_cut
, __len22
);
3151 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
3153 __len11
= std::distance(__first
, __first_cut
);
3155 std::rotate(__first_cut
, __middle
, __second_cut
);
3156 _BidirectionalIterator __new_middle
= __first_cut
;
3157 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
3158 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
3159 __len11
, __len22
, __comp
);
3160 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
3161 __len1
- __len11
, __len2
- __len22
, __comp
);
3166 * This is a helper function for the stable sorting routines.
3169 template<typename _RandomAccessIterator
>
3171 __inplace_stable_sort(_RandomAccessIterator __first
,
3172 _RandomAccessIterator __last
)
3174 if (__last
- __first
< 15)
3176 std::__insertion_sort(__first
, __last
);
3179 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
3180 std::__inplace_stable_sort(__first
, __middle
);
3181 std::__inplace_stable_sort(__middle
, __last
);
3182 std::__merge_without_buffer(__first
, __middle
, __last
,
3189 * This is a helper function for the stable sorting routines.
3192 template<typename _RandomAccessIterator
, typename _Compare
>
3194 __inplace_stable_sort(_RandomAccessIterator __first
,
3195 _RandomAccessIterator __last
, _Compare __comp
)
3197 if (__last
- __first
< 15)
3199 std::__insertion_sort(__first
, __last
, __comp
);
3202 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
3203 std::__inplace_stable_sort(__first
, __middle
, __comp
);
3204 std::__inplace_stable_sort(__middle
, __last
, __comp
);
3205 std::__merge_without_buffer(__first
, __middle
, __last
,
3212 * @brief Merges two sorted ranges.
3213 * @param first1 An iterator.
3214 * @param first2 Another iterator.
3215 * @param last1 Another iterator.
3216 * @param last2 Another iterator.
3217 * @param result An iterator pointing to the end of the merged range.
3218 * @return An iterator pointing to the first element "not less than" @a val.
3220 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3221 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3222 * must be sorted, and the output range must not overlap with either of
3223 * the input ranges. The sort is @e stable, that is, for equivalent
3224 * elements in the two ranges, elements from the first range will always
3225 * come before elements from the second.
3227 template<typename _InputIterator1
, typename _InputIterator2
,
3228 typename _OutputIterator
>
3230 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
3231 _InputIterator2 __first2
, _InputIterator2 __last2
,
3232 _OutputIterator __result
)
3234 typedef typename iterator_traits
<_InputIterator1
>::value_type
3236 typedef typename iterator_traits
<_InputIterator2
>::value_type
3239 // concept requirements
3240 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3241 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3242 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3244 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3246 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
3247 __glibcxx_requires_sorted(__first1
, __last1
);
3248 __glibcxx_requires_sorted(__first2
, __last2
);
3250 while (__first1
!= __last1
&& __first2
!= __last2
)
3252 if (*__first2
< *__first1
)
3254 *__result
= *__first2
;
3259 *__result
= *__first1
;
3264 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
3269 * @brief Merges two sorted ranges.
3270 * @param first1 An iterator.
3271 * @param first2 Another iterator.
3272 * @param last1 Another iterator.
3273 * @param last2 Another iterator.
3274 * @param result An iterator pointing to the end of the merged range.
3275 * @param comp A functor to use for comparisons.
3276 * @return An iterator pointing to the first element "not less than" @a val.
3278 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3279 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3280 * must be sorted, and the output range must not overlap with either of
3281 * the input ranges. The sort is @e stable, that is, for equivalent
3282 * elements in the two ranges, elements from the first range will always
3283 * come before elements from the second.
3285 * The comparison function should have the same effects on ordering as
3286 * the function used for the initial sort.
3288 template<typename _InputIterator1
, typename _InputIterator2
,
3289 typename _OutputIterator
, typename _Compare
>
3291 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
3292 _InputIterator2 __first2
, _InputIterator2 __last2
,
3293 _OutputIterator __result
, _Compare __comp
)
3295 typedef typename iterator_traits
<_InputIterator1
>::value_type
3297 typedef typename iterator_traits
<_InputIterator2
>::value_type
3300 // concept requirements
3301 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3302 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3303 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3305 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3307 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3308 _ValueType2
, _ValueType1
>)
3309 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
3310 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
3312 while (__first1
!= __last1
&& __first2
!= __last2
)
3314 if (__comp(*__first2
, *__first1
))
3316 *__result
= *__first2
;
3321 *__result
= *__first1
;
3326 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
3330 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3333 __merge_sort_loop(_RandomAccessIterator1 __first
,
3334 _RandomAccessIterator1 __last
,
3335 _RandomAccessIterator2 __result
,
3336 _Distance __step_size
)
3338 const _Distance __two_step
= 2 * __step_size
;
3340 while (__last
- __first
>= __two_step
)
3342 __result
= std::merge(__first
, __first
+ __step_size
,
3343 __first
+ __step_size
, __first
+ __two_step
,
3345 __first
+= __two_step
;
3348 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3349 std::merge(__first
, __first
+ __step_size
, __first
+ __step_size
, __last
,
3353 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3354 typename _Distance
, typename _Compare
>
3356 __merge_sort_loop(_RandomAccessIterator1 __first
,
3357 _RandomAccessIterator1 __last
,
3358 _RandomAccessIterator2 __result
, _Distance __step_size
,
3361 const _Distance __two_step
= 2 * __step_size
;
3363 while (__last
- __first
>= __two_step
)
3365 __result
= std::merge(__first
, __first
+ __step_size
,
3366 __first
+ __step_size
, __first
+ __two_step
,
3369 __first
+= __two_step
;
3371 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3373 std::merge(__first
, __first
+ __step_size
,
3374 __first
+ __step_size
, __last
,
3379 enum { _S_chunk_size
= 7 };
3381 template<typename _RandomAccessIterator
, typename _Distance
>
3383 __chunk_insertion_sort(_RandomAccessIterator __first
,
3384 _RandomAccessIterator __last
,
3385 _Distance __chunk_size
)
3387 while (__last
- __first
>= __chunk_size
)
3389 std::__insertion_sort(__first
, __first
+ __chunk_size
);
3390 __first
+= __chunk_size
;
3392 std::__insertion_sort(__first
, __last
);
3395 template<typename _RandomAccessIterator
, typename _Distance
, typename _Compare
>
3397 __chunk_insertion_sort(_RandomAccessIterator __first
,
3398 _RandomAccessIterator __last
,
3399 _Distance __chunk_size
, _Compare __comp
)
3401 while (__last
- __first
>= __chunk_size
)
3403 std::__insertion_sort(__first
, __first
+ __chunk_size
, __comp
);
3404 __first
+= __chunk_size
;
3406 std::__insertion_sort(__first
, __last
, __comp
);
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
);
3461 * This is a helper function for the merge routines.
3464 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3465 typename _BidirectionalIterator3
>
3466 _BidirectionalIterator3
3467 __merge_backward(_BidirectionalIterator1 __first1
,
3468 _BidirectionalIterator1 __last1
,
3469 _BidirectionalIterator2 __first2
,
3470 _BidirectionalIterator2 __last2
,
3471 _BidirectionalIterator3 __result
)
3473 if (__first1
== __last1
)
3474 return std::copy_backward(__first2
, __last2
, __result
);
3475 if (__first2
== __last2
)
3476 return std::copy_backward(__first1
, __last1
, __result
);
3481 if (*__last2
< *__last1
)
3483 *--__result
= *__last1
;
3484 if (__first1
== __last1
)
3485 return std::copy_backward(__first2
, ++__last2
, __result
);
3490 *--__result
= *__last2
;
3491 if (__first2
== __last2
)
3492 return std::copy_backward(__first1
, ++__last1
, __result
);
3500 * This is a helper function for the merge routines.
3503 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3504 typename _BidirectionalIterator3
, typename _Compare
>
3505 _BidirectionalIterator3
3506 __merge_backward(_BidirectionalIterator1 __first1
,
3507 _BidirectionalIterator1 __last1
,
3508 _BidirectionalIterator2 __first2
,
3509 _BidirectionalIterator2 __last2
,
3510 _BidirectionalIterator3 __result
,
3513 if (__first1
== __last1
)
3514 return std::copy_backward(__first2
, __last2
, __result
);
3515 if (__first2
== __last2
)
3516 return std::copy_backward(__first1
, __last1
, __result
);
3521 if (__comp(*__last2
, *__last1
))
3523 *--__result
= *__last1
;
3524 if (__first1
== __last1
)
3525 return std::copy_backward(__first2
, ++__last2
, __result
);
3530 *--__result
= *__last2
;
3531 if (__first2
== __last2
)
3532 return std::copy_backward(__first1
, ++__last1
, __result
);
3540 * This is a helper function for the merge routines.
3543 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3545 _BidirectionalIterator1
3546 __rotate_adaptive(_BidirectionalIterator1 __first
,
3547 _BidirectionalIterator1 __middle
,
3548 _BidirectionalIterator1 __last
,
3549 _Distance __len1
, _Distance __len2
,
3550 _BidirectionalIterator2 __buffer
,
3551 _Distance __buffer_size
)
3553 _BidirectionalIterator2 __buffer_end
;
3554 if (__len1
> __len2
&& __len2
<= __buffer_size
)
3556 __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3557 std::copy_backward(__first
, __middle
, __last
);
3558 return std::copy(__buffer
, __buffer_end
, __first
);
3560 else if (__len1
<= __buffer_size
)
3562 __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3563 std::copy(__middle
, __last
, __first
);
3564 return std::copy_backward(__buffer
, __buffer_end
, __last
);
3568 std::rotate(__first
, __middle
, __last
);
3569 std::advance(__first
, std::distance(__middle
, __last
));
3576 * This is a helper function for the merge routines.
3579 template<typename _BidirectionalIterator
, typename _Distance
,
3582 __merge_adaptive(_BidirectionalIterator __first
,
3583 _BidirectionalIterator __middle
,
3584 _BidirectionalIterator __last
,
3585 _Distance __len1
, _Distance __len2
,
3586 _Pointer __buffer
, _Distance __buffer_size
)
3588 if (__len1
<= __len2
&& __len1
<= __buffer_size
)
3590 _Pointer __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3591 std::merge(__buffer
, __buffer_end
, __middle
, __last
, __first
);
3593 else if (__len2
<= __buffer_size
)
3595 _Pointer __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3596 std::__merge_backward(__first
, __middle
, __buffer
,
3597 __buffer_end
, __last
);
3601 _BidirectionalIterator __first_cut
= __first
;
3602 _BidirectionalIterator __second_cut
= __middle
;
3603 _Distance __len11
= 0;
3604 _Distance __len22
= 0;
3605 if (__len1
> __len2
)
3607 __len11
= __len1
/ 2;
3608 std::advance(__first_cut
, __len11
);
3609 __second_cut
= std::lower_bound(__middle
, __last
,
3611 __len22
= std::distance(__middle
, __second_cut
);
3615 __len22
= __len2
/ 2;
3616 std::advance(__second_cut
, __len22
);
3617 __first_cut
= std::upper_bound(__first
, __middle
,
3619 __len11
= std::distance(__first
, __first_cut
);
3621 _BidirectionalIterator __new_middle
=
3622 std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
3623 __len1
- __len11
, __len22
, __buffer
,
3625 std::__merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
3626 __len22
, __buffer
, __buffer_size
);
3627 std::__merge_adaptive(__new_middle
, __second_cut
, __last
,
3629 __len2
- __len22
, __buffer
, __buffer_size
);
3635 * This is a helper function for the merge routines.
3638 template<typename _BidirectionalIterator
, typename _Distance
, typename _Pointer
,
3641 __merge_adaptive(_BidirectionalIterator __first
,
3642 _BidirectionalIterator __middle
,
3643 _BidirectionalIterator __last
,
3644 _Distance __len1
, _Distance __len2
,
3645 _Pointer __buffer
, _Distance __buffer_size
,
3648 if (__len1
<= __len2
&& __len1
<= __buffer_size
)
3650 _Pointer __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3651 std::merge(__buffer
, __buffer_end
, __middle
, __last
, __first
, __comp
);
3653 else if (__len2
<= __buffer_size
)
3655 _Pointer __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3656 std::__merge_backward(__first
, __middle
, __buffer
, __buffer_end
,
3661 _BidirectionalIterator __first_cut
= __first
;
3662 _BidirectionalIterator __second_cut
= __middle
;
3663 _Distance __len11
= 0;
3664 _Distance __len22
= 0;
3665 if (__len1
> __len2
)
3667 __len11
= __len1
/ 2;
3668 std::advance(__first_cut
, __len11
);
3669 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
3671 __len22
= std::distance(__middle
, __second_cut
);
3675 __len22
= __len2
/ 2;
3676 std::advance(__second_cut
, __len22
);
3677 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
3679 __len11
= std::distance(__first
, __first_cut
);
3681 _BidirectionalIterator __new_middle
=
3682 std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
3683 __len1
- __len11
, __len22
, __buffer
,
3685 std::__merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
3686 __len22
, __buffer
, __buffer_size
, __comp
);
3687 std::__merge_adaptive(__new_middle
, __second_cut
, __last
,
3689 __len2
- __len22
, __buffer
,
3690 __buffer_size
, __comp
);
3695 * @brief Merges two sorted ranges in place.
3696 * @param first An iterator.
3697 * @param middle Another iterator.
3698 * @param last Another iterator.
3701 * Merges two sorted and consecutive ranges, [first,middle) and
3702 * [middle,last), and puts the result in [first,last). The output will
3703 * be sorted. The sort is @e stable, that is, for equivalent
3704 * elements in the two ranges, elements from the first range will always
3705 * come before elements from the second.
3707 * If enough additional memory is available, this takes (last-first)-1
3708 * comparisons. Otherwise an NlogN algorithm is used, where N is
3709 * distance(first,last).
3711 template<typename _BidirectionalIterator
>
3713 inplace_merge(_BidirectionalIterator __first
,
3714 _BidirectionalIterator __middle
,
3715 _BidirectionalIterator __last
)
3717 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3719 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3722 // concept requirements
3723 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3724 _BidirectionalIterator
>)
3725 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3726 __glibcxx_requires_sorted(__first
, __middle
);
3727 __glibcxx_requires_sorted(__middle
, __last
);
3729 if (__first
== __middle
|| __middle
== __last
)
3732 _DistanceType __len1
= std::distance(__first
, __middle
);
3733 _DistanceType __len2
= std::distance(__middle
, __last
);
3735 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3737 if (__buf
.begin() == 0)
3738 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
, __len2
);
3740 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3741 __buf
.begin(), _DistanceType(__buf
.size()));
3745 * @brief Merges two sorted ranges in place.
3746 * @param first An iterator.
3747 * @param middle Another iterator.
3748 * @param last Another iterator.
3749 * @param comp A functor to use for comparisons.
3752 * Merges two sorted and consecutive ranges, [first,middle) and
3753 * [middle,last), and puts the result in [first,last). The output will
3754 * be sorted. The sort is @e stable, that is, for equivalent
3755 * elements in the two ranges, elements from the first range will always
3756 * come before elements from the second.
3758 * If enough additional memory is available, this takes (last-first)-1
3759 * comparisons. Otherwise an NlogN algorithm is used, where N is
3760 * distance(first,last).
3762 * The comparison function should have the same effects on ordering as
3763 * the function used for the initial sort.
3765 template<typename _BidirectionalIterator
, typename _Compare
>
3767 inplace_merge(_BidirectionalIterator __first
,
3768 _BidirectionalIterator __middle
,
3769 _BidirectionalIterator __last
,
3772 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3774 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3777 // concept requirements
3778 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3779 _BidirectionalIterator
>)
3780 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3781 _ValueType
, _ValueType
>)
3782 __glibcxx_requires_sorted_pred(__first
, __middle
, __comp
);
3783 __glibcxx_requires_sorted_pred(__middle
, __last
, __comp
);
3785 if (__first
== __middle
|| __middle
== __last
)
3788 const _DistanceType __len1
= std::distance(__first
, __middle
);
3789 const _DistanceType __len2
= std::distance(__middle
, __last
);
3791 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3793 if (__buf
.begin() == 0)
3794 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
,
3797 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3798 __buf
.begin(), _DistanceType(__buf
.size()),
3802 template<typename _RandomAccessIterator
, typename _Pointer
,
3805 __stable_sort_adaptive(_RandomAccessIterator __first
,
3806 _RandomAccessIterator __last
,
3807 _Pointer __buffer
, _Distance __buffer_size
)
3809 const _Distance __len
= (__last
- __first
+ 1) / 2;
3810 const _RandomAccessIterator __middle
= __first
+ __len
;
3811 if (__len
> __buffer_size
)
3813 std::__stable_sort_adaptive(__first
, __middle
,
3814 __buffer
, __buffer_size
);
3815 std::__stable_sort_adaptive(__middle
, __last
,
3816 __buffer
, __buffer_size
);
3820 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
);
3821 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
);
3823 std::__merge_adaptive(__first
, __middle
, __last
,
3824 _Distance(__middle
- __first
),
3825 _Distance(__last
- __middle
),
3826 __buffer
, __buffer_size
);
3829 template<typename _RandomAccessIterator
, typename _Pointer
,
3830 typename _Distance
, typename _Compare
>
3832 __stable_sort_adaptive(_RandomAccessIterator __first
,
3833 _RandomAccessIterator __last
,
3834 _Pointer __buffer
, _Distance __buffer_size
,
3837 const _Distance __len
= (__last
- __first
+ 1) / 2;
3838 const _RandomAccessIterator __middle
= __first
+ __len
;
3839 if (__len
> __buffer_size
)
3841 std::__stable_sort_adaptive(__first
, __middle
, __buffer
,
3842 __buffer_size
, __comp
);
3843 std::__stable_sort_adaptive(__middle
, __last
, __buffer
,
3844 __buffer_size
, __comp
);
3848 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
, __comp
);
3849 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
, __comp
);
3851 std::__merge_adaptive(__first
, __middle
, __last
,
3852 _Distance(__middle
- __first
),
3853 _Distance(__last
- __middle
),
3854 __buffer
, __buffer_size
,
3859 * @brief Sort the elements of a sequence, preserving the relative order
3860 * of equivalent elements.
3861 * @param first An iterator.
3862 * @param last Another iterator.
3865 * Sorts the elements in the range @p [first,last) in ascending order,
3866 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3867 * @p [first,last-1).
3869 * The relative ordering of equivalent elements is preserved, so any two
3870 * elements @p x and @p y in the range @p [first,last) such that
3871 * @p x<y is false and @p y<x is false will have the same relative
3872 * ordering after calling @p stable_sort().
3874 template<typename _RandomAccessIterator
>
3876 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
3878 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3880 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3883 // concept requirements
3884 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3885 _RandomAccessIterator
>)
3886 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3887 __glibcxx_requires_valid_range(__first
, __last
);
3889 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
> __buf(__first
,
3891 if (__buf
.begin() == 0)
3892 std::__inplace_stable_sort(__first
, __last
);
3894 std::__stable_sort_adaptive(__first
, __last
, __buf
.begin(),
3895 _DistanceType(__buf
.size()));
3899 * @brief Sort the elements of a sequence using a predicate for comparison,
3900 * preserving the relative order of equivalent elements.
3901 * @param first An iterator.
3902 * @param last Another iterator.
3903 * @param comp A comparison functor.
3906 * Sorts the elements in the range @p [first,last) in ascending order,
3907 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3908 * range @p [first,last-1).
3910 * The relative ordering of equivalent elements is preserved, so any two
3911 * elements @p x and @p y in the range @p [first,last) such that
3912 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
3913 * relative ordering after calling @p stable_sort().
3915 template<typename _RandomAccessIterator
, typename _Compare
>
3917 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
3920 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3922 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3925 // concept requirements
3926 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3927 _RandomAccessIterator
>)
3928 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3931 __glibcxx_requires_valid_range(__first
, __last
);
3933 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
> __buf(__first
,
3935 if (__buf
.begin() == 0)
3936 std::__inplace_stable_sort(__first
, __last
, __comp
);
3938 std::__stable_sort_adaptive(__first
, __last
, __buf
.begin(),
3939 _DistanceType(__buf
.size()), __comp
);
3943 template<typename _RandomAccessIterator
, typename _Size
>
3945 __introselect(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
3946 _RandomAccessIterator __last
, _Size __depth_limit
)
3948 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3951 while (__last
- __first
> 3)
3953 if (__depth_limit
== 0)
3955 std::__heap_select(__first
, __nth
+ 1, __last
);
3956 // Place the nth largest element in its final position.
3957 std::iter_swap(__first
, __nth
);
3961 _RandomAccessIterator __cut
=
3962 std::__unguarded_partition(__first
, __last
,
3963 _ValueType(std::__median(*__first
,
3975 std::__insertion_sort(__first
, __last
);
3978 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
3980 __introselect(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
3981 _RandomAccessIterator __last
, _Size __depth_limit
,
3984 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3987 while (__last
- __first
> 3)
3989 if (__depth_limit
== 0)
3991 std::__heap_select(__first
, __nth
+ 1, __last
, __comp
);
3992 // Place the nth largest element in its final position.
3993 std::iter_swap(__first
, __nth
);
3997 _RandomAccessIterator __cut
=
3998 std::__unguarded_partition(__first
, __last
,
3999 _ValueType(std::__median(*__first
,
4012 std::__insertion_sort(__first
, __last
, __comp
);
4016 * @brief Sort a sequence just enough to find a particular position.
4017 * @param first An iterator.
4018 * @param nth Another iterator.
4019 * @param last Another iterator.
4022 * Rearranges the elements in the range @p [first,last) so that @p *nth
4023 * is the same element that would have been in that position had the
4024 * whole sequence been sorted.
4025 * whole sequence been sorted. The elements either side of @p *nth are
4026 * not completely sorted, but for any iterator @i in the range
4027 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
4028 * holds that @p *j<*i is false.
4030 template<typename _RandomAccessIterator
>
4032 nth_element(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
4033 _RandomAccessIterator __last
)
4035 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
4038 // concept requirements
4039 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4040 _RandomAccessIterator
>)
4041 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
4042 __glibcxx_requires_valid_range(__first
, __nth
);
4043 __glibcxx_requires_valid_range(__nth
, __last
);
4045 if (__first
== __last
|| __nth
== __last
)
4048 std::__introselect(__first
, __nth
, __last
,
4049 std::__lg(__last
- __first
) * 2);
4053 * @brief Sort a sequence just enough to find a particular position
4054 * using a predicate for comparison.
4055 * @param first An iterator.
4056 * @param nth Another iterator.
4057 * @param last Another iterator.
4058 * @param comp A comparison functor.
4061 * Rearranges the elements in the range @p [first,last) so that @p *nth
4062 * is the same element that would have been in that position had the
4063 * whole sequence been sorted. The elements either side of @p *nth are
4064 * not completely sorted, but for any iterator @i in the range
4065 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
4066 * holds that @p comp(*j,*i) is false.
4068 template<typename _RandomAccessIterator
, typename _Compare
>
4070 nth_element(_RandomAccessIterator __first
, _RandomAccessIterator __nth
,
4071 _RandomAccessIterator __last
, _Compare __comp
)
4073 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
4076 // concept requirements
4077 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
4078 _RandomAccessIterator
>)
4079 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4080 _ValueType
, _ValueType
>)
4081 __glibcxx_requires_valid_range(__first
, __nth
);
4082 __glibcxx_requires_valid_range(__nth
, __last
);
4084 if (__first
== __last
|| __nth
== __last
)
4087 std::__introselect(__first
, __nth
, __last
,
4088 std::__lg(__last
- __first
) * 2, __comp
);
4092 * @brief Finds the largest subrange in which @a val could be inserted
4093 * at any place in it without changing the ordering.
4094 * @param first An iterator.
4095 * @param last Another iterator.
4096 * @param val The search term.
4097 * @return An pair of iterators defining the subrange.
4098 * @ingroup binarysearch
4100 * This is equivalent to
4102 * std::make_pair(lower_bound(first, last, val),
4103 * upper_bound(first, last, val))
4105 * but does not actually call those functions.
4107 template<typename _ForwardIterator
, typename _Tp
>
4108 pair
<_ForwardIterator
, _ForwardIterator
>
4109 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
4112 typedef typename iterator_traits
<_ForwardIterator
>::value_type
4114 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
4117 // concept requirements
4118 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4119 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType
, _Tp
>)
4120 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
4121 __glibcxx_requires_partitioned(__first
, __last
, __val
);
4123 _DistanceType __len
= std::distance(__first
, __last
);
4124 _DistanceType __half
;
4125 _ForwardIterator __middle
, __left
, __right
;
4129 __half
= __len
>> 1;
4131 std::advance(__middle
, __half
);
4132 if (*__middle
< __val
)
4136 __len
= __len
- __half
- 1;
4138 else if (__val
< *__middle
)
4142 __left
= std::lower_bound(__first
, __middle
, __val
);
4143 std::advance(__first
, __len
);
4144 __right
= std::upper_bound(++__middle
, __first
, __val
);
4145 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
4148 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
4152 * @brief Finds the largest subrange in which @a val could be inserted
4153 * at any place in it without changing the ordering.
4154 * @param first An iterator.
4155 * @param last Another iterator.
4156 * @param val The search term.
4157 * @param comp A functor to use for comparisons.
4158 * @return An pair of iterators defining the subrange.
4159 * @ingroup binarysearch
4161 * This is equivalent to
4163 * std::make_pair(lower_bound(first, last, val, comp),
4164 * upper_bound(first, last, val, comp))
4166 * but does not actually call those functions.
4168 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
4169 pair
<_ForwardIterator
, _ForwardIterator
>
4170 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
4174 typedef typename iterator_traits
<_ForwardIterator
>::value_type
4176 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
4179 // concept requirements
4180 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4181 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4183 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4185 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
4187 _DistanceType __len
= std::distance(__first
, __last
);
4188 _DistanceType __half
;
4189 _ForwardIterator __middle
, __left
, __right
;
4193 __half
= __len
>> 1;
4195 std::advance(__middle
, __half
);
4196 if (__comp(*__middle
, __val
))
4200 __len
= __len
- __half
- 1;
4202 else if (__comp(__val
, *__middle
))
4206 __left
= std::lower_bound(__first
, __middle
, __val
, __comp
);
4207 std::advance(__first
, __len
);
4208 __right
= std::upper_bound(++__middle
, __first
, __val
, __comp
);
4209 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
4212 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
4216 * @brief Determines whether an element exists in a range.
4217 * @param first An iterator.
4218 * @param last Another iterator.
4219 * @param val The search term.
4220 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4221 * @ingroup binarysearch
4223 * Note that this does not actually return an iterator to @a val. For
4224 * that, use std::find or a container's specialized find member functions.
4226 template<typename _ForwardIterator
, typename _Tp
>
4228 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
4231 typedef typename iterator_traits
<_ForwardIterator
>::value_type
4234 // concept requirements
4235 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4236 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
4237 __glibcxx_requires_partitioned(__first
, __last
, __val
);
4239 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
);
4240 return __i
!= __last
&& !(__val
< *__i
);
4244 * @brief Determines whether an element exists in a range.
4245 * @param first An iterator.
4246 * @param last Another iterator.
4247 * @param val The search term.
4248 * @param comp A functor to use for comparisons.
4249 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4250 * @ingroup binarysearch
4252 * Note that this does not actually return an iterator to @a val. For
4253 * that, use std::find or a container's specialized find member functions.
4255 * The comparison function should have the same effects on ordering as
4256 * the function used for the initial sort.
4258 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
4260 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
4261 const _Tp
& __val
, _Compare __comp
)
4263 typedef typename iterator_traits
<_ForwardIterator
>::value_type
4266 // concept requirements
4267 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4268 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4270 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
4272 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
, __comp
);
4273 return __i
!= __last
&& !__comp(__val
, *__i
);
4276 // Set algorithms: includes, set_union, set_intersection, set_difference,
4277 // set_symmetric_difference. All of these algorithms have the precondition
4278 // that their input ranges are sorted and the postcondition that their output
4279 // ranges are sorted.
4282 * @brief Determines whether all elements of a sequence exists in a range.
4283 * @param first1 Start of search range.
4284 * @param last1 End of search range.
4285 * @param first2 Start of sequence
4286 * @param last2 End of sequence.
4287 * @return True if each element in [first2,last2) is contained in order
4288 * within [first1,last1). False otherwise.
4289 * @ingroup setoperations
4291 * This operation expects both [first1,last1) and [first2,last2) to be
4292 * sorted. Searches for the presence of each element in [first2,last2)
4293 * within [first1,last1). The iterators over each range only move forward,
4294 * so this is a linear algorithm. If an element in [first2,last2) is not
4295 * found before the search iterator reaches @a last2, false is returned.
4297 template<typename _InputIterator1
, typename _InputIterator2
>
4299 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
4300 _InputIterator2 __first2
, _InputIterator2 __last2
)
4302 typedef typename iterator_traits
<_InputIterator1
>::value_type
4304 typedef typename iterator_traits
<_InputIterator2
>::value_type
4307 // concept requirements
4308 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4309 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4310 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4311 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4312 __glibcxx_requires_sorted(__first1
, __last1
);
4313 __glibcxx_requires_sorted(__first2
, __last2
);
4315 while (__first1
!= __last1
&& __first2
!= __last2
)
4316 if (*__first2
< *__first1
)
4318 else if(*__first1
< *__first2
)
4321 ++__first1
, ++__first2
;
4323 return __first2
== __last2
;
4327 * @brief Determines whether all elements of a sequence exists in a range
4329 * @param first1 Start of search range.
4330 * @param last1 End of search range.
4331 * @param first2 Start of sequence
4332 * @param last2 End of sequence.
4333 * @param comp Comparison function to use.
4334 * @return True if each element in [first2,last2) is contained in order
4335 * within [first1,last1) according to comp. False otherwise.
4336 * @ingroup setoperations
4338 * This operation expects both [first1,last1) and [first2,last2) to be
4339 * sorted. Searches for the presence of each element in [first2,last2)
4340 * within [first1,last1), using comp to decide. The iterators over each
4341 * range only move forward, so this is a linear algorithm. If an element
4342 * in [first2,last2) is not found before the search iterator reaches @a
4343 * last2, false is returned.
4345 template<typename _InputIterator1
, typename _InputIterator2
,
4348 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
4349 _InputIterator2 __first2
, _InputIterator2 __last2
, _Compare __comp
)
4351 typedef typename iterator_traits
<_InputIterator1
>::value_type
4353 typedef typename iterator_traits
<_InputIterator2
>::value_type
4356 // concept requirements
4357 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4358 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4359 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4360 _ValueType1
, _ValueType2
>)
4361 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4362 _ValueType2
, _ValueType1
>)
4363 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4364 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4366 while (__first1
!= __last1
&& __first2
!= __last2
)
4367 if (__comp(*__first2
, *__first1
))
4369 else if(__comp(*__first1
, *__first2
))
4372 ++__first1
, ++__first2
;
4374 return __first2
== __last2
;
4378 * @brief Return the union of two sorted ranges.
4379 * @param first1 Start of first range.
4380 * @param last1 End of first range.
4381 * @param first2 Start of second range.
4382 * @param last2 End of second range.
4383 * @return End of the output range.
4384 * @ingroup setoperations
4386 * This operation iterates over both ranges, copying elements present in
4387 * each range in order to the output range. Iterators increment for each
4388 * range. When the current element of one range is less than the other,
4389 * that element is copied and the iterator advanced. If an element is
4390 * contained in both ranges, the element from the first range is copied and
4391 * both ranges advance. The output range may not overlap either input
4394 template<typename _InputIterator1
, typename _InputIterator2
,
4395 typename _OutputIterator
>
4397 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
4398 _InputIterator2 __first2
, _InputIterator2 __last2
,
4399 _OutputIterator __result
)
4401 typedef typename iterator_traits
<_InputIterator1
>::value_type
4403 typedef typename iterator_traits
<_InputIterator2
>::value_type
4406 // concept requirements
4407 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4408 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4409 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4411 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4413 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4414 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4415 __glibcxx_requires_sorted(__first1
, __last1
);
4416 __glibcxx_requires_sorted(__first2
, __last2
);
4418 while (__first1
!= __last1
&& __first2
!= __last2
)
4420 if (*__first1
< *__first2
)
4422 *__result
= *__first1
;
4425 else if (*__first2
< *__first1
)
4427 *__result
= *__first2
;
4432 *__result
= *__first1
;
4438 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
4443 * @brief Return the union of two sorted ranges using a comparison functor.
4444 * @param first1 Start of first range.
4445 * @param last1 End of first range.
4446 * @param first2 Start of second range.
4447 * @param last2 End of second range.
4448 * @param comp The comparison functor.
4449 * @return End of the output range.
4450 * @ingroup setoperations
4452 * This operation iterates over both ranges, copying elements present in
4453 * each range in order to the output range. Iterators increment for each
4454 * range. When the current element of one range is less than the other
4455 * according to @a comp, that element is copied and the iterator advanced.
4456 * If an equivalent element according to @a comp is contained in both
4457 * ranges, the element from the first range is copied and both ranges
4458 * advance. The output range may not overlap either input range.
4460 template<typename _InputIterator1
, typename _InputIterator2
,
4461 typename _OutputIterator
, typename _Compare
>
4463 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
4464 _InputIterator2 __first2
, _InputIterator2 __last2
,
4465 _OutputIterator __result
, _Compare __comp
)
4467 typedef typename iterator_traits
<_InputIterator1
>::value_type
4469 typedef typename iterator_traits
<_InputIterator2
>::value_type
4472 // concept requirements
4473 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4474 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4475 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4477 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4479 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4480 _ValueType1
, _ValueType2
>)
4481 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4482 _ValueType2
, _ValueType1
>)
4483 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4484 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4486 while (__first1
!= __last1
&& __first2
!= __last2
)
4488 if (__comp(*__first1
, *__first2
))
4490 *__result
= *__first1
;
4493 else if (__comp(*__first2
, *__first1
))
4495 *__result
= *__first2
;
4500 *__result
= *__first1
;
4506 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
4511 * @brief Return the intersection of two sorted ranges.
4512 * @param first1 Start of first range.
4513 * @param last1 End of first range.
4514 * @param first2 Start of second range.
4515 * @param last2 End of second range.
4516 * @return End of the output range.
4517 * @ingroup setoperations
4519 * This operation iterates over both ranges, copying elements present in
4520 * both ranges in order to the output range. Iterators increment for each
4521 * range. When the current element of one range is less than the other,
4522 * that iterator advances. If an element is contained in both ranges, the
4523 * element from the first range is copied and both ranges advance. The
4524 * output range may not overlap either input range.
4526 template<typename _InputIterator1
, typename _InputIterator2
,
4527 typename _OutputIterator
>
4529 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
4530 _InputIterator2 __first2
, _InputIterator2 __last2
,
4531 _OutputIterator __result
)
4533 typedef typename iterator_traits
<_InputIterator1
>::value_type
4535 typedef typename iterator_traits
<_InputIterator2
>::value_type
4538 // concept requirements
4539 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4540 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4541 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4543 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4544 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4545 __glibcxx_requires_sorted(__first1
, __last1
);
4546 __glibcxx_requires_sorted(__first2
, __last2
);
4548 while (__first1
!= __last1
&& __first2
!= __last2
)
4549 if (*__first1
< *__first2
)
4551 else if (*__first2
< *__first1
)
4555 *__result
= *__first1
;
4564 * @brief Return the intersection of two sorted ranges using comparison
4566 * @param first1 Start of first range.
4567 * @param last1 End of first range.
4568 * @param first2 Start of second range.
4569 * @param last2 End of second range.
4570 * @param comp The comparison functor.
4571 * @return End of the output range.
4572 * @ingroup setoperations
4574 * This operation iterates over both ranges, copying elements present in
4575 * both ranges in order to the output range. Iterators increment for each
4576 * range. When the current element of one range is less than the other
4577 * according to @a comp, that iterator advances. If an element is
4578 * contained in both ranges according to @a comp, the element from the
4579 * first range is copied and both ranges advance. The output range may not
4580 * overlap either input range.
4582 template<typename _InputIterator1
, typename _InputIterator2
,
4583 typename _OutputIterator
, typename _Compare
>
4585 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
4586 _InputIterator2 __first2
, _InputIterator2 __last2
,
4587 _OutputIterator __result
, _Compare __comp
)
4589 typedef typename iterator_traits
<_InputIterator1
>::value_type
4591 typedef typename iterator_traits
<_InputIterator2
>::value_type
4594 // concept requirements
4595 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4596 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4597 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4599 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4600 _ValueType1
, _ValueType2
>)
4601 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4602 _ValueType2
, _ValueType1
>)
4603 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4604 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4606 while (__first1
!= __last1
&& __first2
!= __last2
)
4607 if (__comp(*__first1
, *__first2
))
4609 else if (__comp(*__first2
, *__first1
))
4613 *__result
= *__first1
;
4622 * @brief Return the difference of two sorted ranges.
4623 * @param first1 Start of first range.
4624 * @param last1 End of first range.
4625 * @param first2 Start of second range.
4626 * @param last2 End of second range.
4627 * @return End of the output range.
4628 * @ingroup setoperations
4630 * This operation iterates over both ranges, copying elements present in
4631 * the first range but not the second in order to the output range.
4632 * Iterators increment for each range. When the current element of the
4633 * first range is less than the second, that element is copied and the
4634 * iterator advances. If the current element of the second range is less,
4635 * the iterator advances, but no element is copied. If an element is
4636 * contained in both ranges, no elements are copied and both ranges
4637 * advance. The output range may not overlap either input range.
4639 template<typename _InputIterator1
, typename _InputIterator2
,
4640 typename _OutputIterator
>
4642 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4643 _InputIterator2 __first2
, _InputIterator2 __last2
,
4644 _OutputIterator __result
)
4646 typedef typename iterator_traits
<_InputIterator1
>::value_type
4648 typedef typename iterator_traits
<_InputIterator2
>::value_type
4651 // concept requirements
4652 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4653 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4654 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4656 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4657 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4658 __glibcxx_requires_sorted(__first1
, __last1
);
4659 __glibcxx_requires_sorted(__first2
, __last2
);
4661 while (__first1
!= __last1
&& __first2
!= __last2
)
4662 if (*__first1
< *__first2
)
4664 *__result
= *__first1
;
4668 else if (*__first2
< *__first1
)
4675 return std::copy(__first1
, __last1
, __result
);
4679 * @brief Return the difference of two sorted ranges using comparison
4681 * @param first1 Start of first range.
4682 * @param last1 End of first range.
4683 * @param first2 Start of second range.
4684 * @param last2 End of second range.
4685 * @param comp The comparison functor.
4686 * @return End of the output range.
4687 * @ingroup setoperations
4689 * This operation iterates over both ranges, copying elements present in
4690 * the first range but not the second in order to the output range.
4691 * Iterators increment for each range. When the current element of the
4692 * first range is less than the second according to @a comp, that element
4693 * is copied and the iterator advances. If the current element of the
4694 * second range is less, no element is copied and the iterator advances.
4695 * If an element is contained in both ranges according to @a comp, no
4696 * elements are copied and both ranges advance. The output range may not
4697 * overlap either input range.
4699 template<typename _InputIterator1
, typename _InputIterator2
,
4700 typename _OutputIterator
, typename _Compare
>
4702 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4703 _InputIterator2 __first2
, _InputIterator2 __last2
,
4704 _OutputIterator __result
, _Compare __comp
)
4706 typedef typename iterator_traits
<_InputIterator1
>::value_type
4708 typedef typename iterator_traits
<_InputIterator2
>::value_type
4711 // concept requirements
4712 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4713 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4714 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4716 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4717 _ValueType1
, _ValueType2
>)
4718 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4719 _ValueType2
, _ValueType1
>)
4720 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4721 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4723 while (__first1
!= __last1
&& __first2
!= __last2
)
4724 if (__comp(*__first1
, *__first2
))
4726 *__result
= *__first1
;
4730 else if (__comp(*__first2
, *__first1
))
4737 return std::copy(__first1
, __last1
, __result
);
4741 * @brief Return the symmetric difference of two sorted ranges.
4742 * @param first1 Start of first range.
4743 * @param last1 End of first range.
4744 * @param first2 Start of second range.
4745 * @param last2 End of second range.
4746 * @return End of the output range.
4747 * @ingroup setoperations
4749 * This operation iterates over both ranges, copying elements present in
4750 * one range but not the other in order to the output range. Iterators
4751 * increment for each range. When the current element of one range is less
4752 * than the other, that element is copied and the iterator advances. If an
4753 * element is contained in both ranges, no elements are copied and both
4754 * ranges advance. The output range may not overlap either input range.
4756 template<typename _InputIterator1
, typename _InputIterator2
,
4757 typename _OutputIterator
>
4759 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4760 _InputIterator2 __first2
, _InputIterator2 __last2
,
4761 _OutputIterator __result
)
4763 typedef typename iterator_traits
<_InputIterator1
>::value_type
4765 typedef typename iterator_traits
<_InputIterator2
>::value_type
4768 // concept requirements
4769 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4770 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4771 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4773 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4775 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4776 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4777 __glibcxx_requires_sorted(__first1
, __last1
);
4778 __glibcxx_requires_sorted(__first2
, __last2
);
4780 while (__first1
!= __last1
&& __first2
!= __last2
)
4781 if (*__first1
< *__first2
)
4783 *__result
= *__first1
;
4787 else if (*__first2
< *__first1
)
4789 *__result
= *__first2
;
4798 return std::copy(__first2
, __last2
, std::copy(__first1
,
4799 __last1
, __result
));
4803 * @brief Return the symmetric difference of two sorted ranges using
4804 * comparison functor.
4805 * @param first1 Start of first range.
4806 * @param last1 End of first range.
4807 * @param first2 Start of second range.
4808 * @param last2 End of second range.
4809 * @param comp The comparison functor.
4810 * @return End of the output range.
4811 * @ingroup setoperations
4813 * This operation iterates over both ranges, copying elements present in
4814 * one range but not the other in order to the output range. Iterators
4815 * increment for each range. When the current element of one range is less
4816 * than the other according to @a comp, that element is copied and the
4817 * iterator advances. If an element is contained in both ranges according
4818 * to @a comp, no elements are copied and both ranges advance. The output
4819 * range may not overlap either input range.
4821 template<typename _InputIterator1
, typename _InputIterator2
,
4822 typename _OutputIterator
, typename _Compare
>
4824 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4825 _InputIterator2 __first2
, _InputIterator2 __last2
,
4826 _OutputIterator __result
,
4829 typedef typename iterator_traits
<_InputIterator1
>::value_type
4831 typedef typename iterator_traits
<_InputIterator2
>::value_type
4834 // concept requirements
4835 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4836 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4837 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4839 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4841 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4842 _ValueType1
, _ValueType2
>)
4843 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4844 _ValueType2
, _ValueType1
>)
4845 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4846 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4848 while (__first1
!= __last1
&& __first2
!= __last2
)
4849 if (__comp(*__first1
, *__first2
))
4851 *__result
= *__first1
;
4855 else if (__comp(*__first2
, *__first1
))
4857 *__result
= *__first2
;
4866 return std::copy(__first2
, __last2
, std::copy(__first1
,
4867 __last1
, __result
));
4870 // min_element and max_element, with and without an explicitly supplied
4871 // comparison function.
4874 * @brief Return the maximum element in a range.
4875 * @param first Start of range.
4876 * @param last End of range.
4877 * @return Iterator referencing the first instance of the largest value.
4879 template<typename _ForwardIterator
>
4881 max_element(_ForwardIterator __first
, _ForwardIterator __last
)
4883 // concept requirements
4884 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4885 __glibcxx_function_requires(_LessThanComparableConcept
<
4886 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4887 __glibcxx_requires_valid_range(__first
, __last
);
4889 if (__first
== __last
)
4891 _ForwardIterator __result
= __first
;
4892 while (++__first
!= __last
)
4893 if (*__result
< *__first
)
4899 * @brief Return the maximum element in a range using comparison functor.
4900 * @param first Start of range.
4901 * @param last End of range.
4902 * @param comp Comparison functor.
4903 * @return Iterator referencing the first instance of the largest value
4904 * according to comp.
4906 template<typename _ForwardIterator
, typename _Compare
>
4908 max_element(_ForwardIterator __first
, _ForwardIterator __last
,
4911 // concept requirements
4912 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4913 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4914 typename iterator_traits
<_ForwardIterator
>::value_type
,
4915 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4916 __glibcxx_requires_valid_range(__first
, __last
);
4918 if (__first
== __last
) return __first
;
4919 _ForwardIterator __result
= __first
;
4920 while (++__first
!= __last
)
4921 if (__comp(*__result
, *__first
)) __result
= __first
;
4926 * @brief Return the minimum element in a range.
4927 * @param first Start of range.
4928 * @param last End of range.
4929 * @return Iterator referencing the first instance of the smallest value.
4931 template<typename _ForwardIterator
>
4933 min_element(_ForwardIterator __first
, _ForwardIterator __last
)
4935 // concept requirements
4936 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4937 __glibcxx_function_requires(_LessThanComparableConcept
<
4938 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4939 __glibcxx_requires_valid_range(__first
, __last
);
4941 if (__first
== __last
)
4943 _ForwardIterator __result
= __first
;
4944 while (++__first
!= __last
)
4945 if (*__first
< *__result
)
4951 * @brief Return the minimum element in a range using comparison functor.
4952 * @param first Start of range.
4953 * @param last End of range.
4954 * @param comp Comparison functor.
4955 * @return Iterator referencing the first instance of the smallest value
4956 * according to comp.
4958 template<typename _ForwardIterator
, typename _Compare
>
4960 min_element(_ForwardIterator __first
, _ForwardIterator __last
,
4963 // concept requirements
4964 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4965 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4966 typename iterator_traits
<_ForwardIterator
>::value_type
,
4967 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4968 __glibcxx_requires_valid_range(__first
, __last
);
4970 if (__first
== __last
)
4972 _ForwardIterator __result
= __first
;
4973 while (++__first
!= __last
)
4974 if (__comp(*__first
, *__result
))
4979 // next_permutation and prev_permutation, with and without an explicitly
4980 // supplied comparison function.
4983 * @brief Permute range into the next "dictionary" ordering.
4984 * @param first Start of range.
4985 * @param last End of range.
4986 * @return False if wrapped to first permutation, true otherwise.
4988 * Treats all permutations of the range as a set of "dictionary" sorted
4989 * sequences. Permutes the current sequence into the next one of this set.
4990 * Returns true if there are more sequences to generate. If the sequence
4991 * is the largest of the set, the smallest is generated and false returned.
4993 template<typename _BidirectionalIterator
>
4995 next_permutation(_BidirectionalIterator __first
,
4996 _BidirectionalIterator __last
)
4998 // concept requirements
4999 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5000 _BidirectionalIterator
>)
5001 __glibcxx_function_requires(_LessThanComparableConcept
<
5002 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
5003 __glibcxx_requires_valid_range(__first
, __last
);
5005 if (__first
== __last
)
5007 _BidirectionalIterator __i
= __first
;
5016 _BidirectionalIterator __ii
= __i
;
5020 _BidirectionalIterator __j
= __last
;
5021 while (!(*__i
< *--__j
))
5023 std::iter_swap(__i
, __j
);
5024 std::reverse(__ii
, __last
);
5029 std::reverse(__first
, __last
);
5036 * @brief Permute range into the next "dictionary" ordering using
5037 * comparison functor.
5038 * @param first Start of range.
5039 * @param last End of range.
5041 * @return False if wrapped to first permutation, true otherwise.
5043 * Treats all permutations of the range [first,last) as a set of
5044 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
5045 * sequence into the next one of this set. Returns true if there are more
5046 * sequences to generate. If the sequence is the largest of the set, the
5047 * smallest is generated and false returned.
5049 template<typename _BidirectionalIterator
, typename _Compare
>
5051 next_permutation(_BidirectionalIterator __first
,
5052 _BidirectionalIterator __last
, _Compare __comp
)
5054 // concept requirements
5055 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5056 _BidirectionalIterator
>)
5057 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5058 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
5059 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
5060 __glibcxx_requires_valid_range(__first
, __last
);
5062 if (__first
== __last
)
5064 _BidirectionalIterator __i
= __first
;
5073 _BidirectionalIterator __ii
= __i
;
5075 if (__comp(*__i
, *__ii
))
5077 _BidirectionalIterator __j
= __last
;
5078 while (!__comp(*__i
, *--__j
))
5080 std::iter_swap(__i
, __j
);
5081 std::reverse(__ii
, __last
);
5086 std::reverse(__first
, __last
);
5093 * @brief Permute range into the previous "dictionary" ordering.
5094 * @param first Start of range.
5095 * @param last End of range.
5096 * @return False if wrapped to last permutation, true otherwise.
5098 * Treats all permutations of the range as a set of "dictionary" sorted
5099 * sequences. Permutes the current sequence into the previous one of this
5100 * set. Returns true if there are more sequences to generate. If the
5101 * sequence is the smallest of the set, the largest is generated and false
5104 template<typename _BidirectionalIterator
>
5106 prev_permutation(_BidirectionalIterator __first
,
5107 _BidirectionalIterator __last
)
5109 // concept requirements
5110 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5111 _BidirectionalIterator
>)
5112 __glibcxx_function_requires(_LessThanComparableConcept
<
5113 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
5114 __glibcxx_requires_valid_range(__first
, __last
);
5116 if (__first
== __last
)
5118 _BidirectionalIterator __i
= __first
;
5127 _BidirectionalIterator __ii
= __i
;
5131 _BidirectionalIterator __j
= __last
;
5132 while (!(*--__j
< *__i
))
5134 std::iter_swap(__i
, __j
);
5135 std::reverse(__ii
, __last
);
5140 std::reverse(__first
, __last
);
5147 * @brief Permute range into the previous "dictionary" ordering using
5148 * comparison functor.
5149 * @param first Start of range.
5150 * @param last End of range.
5152 * @return False if wrapped to last permutation, true otherwise.
5154 * Treats all permutations of the range [first,last) as a set of
5155 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
5156 * sequence into the previous one of this set. Returns true if there are
5157 * more sequences to generate. If the sequence is the smallest of the set,
5158 * the largest is generated and false returned.
5160 template<typename _BidirectionalIterator
, typename _Compare
>
5162 prev_permutation(_BidirectionalIterator __first
,
5163 _BidirectionalIterator __last
, _Compare __comp
)
5165 // concept requirements
5166 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5167 _BidirectionalIterator
>)
5168 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5169 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
5170 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
5171 __glibcxx_requires_valid_range(__first
, __last
);
5173 if (__first
== __last
)
5175 _BidirectionalIterator __i
= __first
;
5184 _BidirectionalIterator __ii
= __i
;
5186 if (__comp(*__ii
, *__i
))
5188 _BidirectionalIterator __j
= __last
;
5189 while (!__comp(*--__j
, *__i
))
5191 std::iter_swap(__i
, __j
);
5192 std::reverse(__ii
, __last
);
5197 std::reverse(__first
, __last
);
5203 // find_first_of, with and without an explicitly supplied comparison function.
5206 * @brief Find element from a set in a sequence.
5207 * @param first1 Start of range to search.
5208 * @param last1 End of range to search.
5209 * @param first2 Start of match candidates.
5210 * @param last2 End of match candidates.
5211 * @return The first iterator @c i in the range
5212 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
5213 * interator in [first2,last2), or @p last1 if no such iterator exists.
5215 * Searches the range @p [first1,last1) for an element that is equal to
5216 * some element in the range [first2,last2). If found, returns an iterator
5217 * in the range [first1,last1), otherwise returns @p last1.
5219 template<typename _InputIterator
, typename _ForwardIterator
>
5221 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
5222 _ForwardIterator __first2
, _ForwardIterator __last2
)
5224 // concept requirements
5225 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
5226 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5227 __glibcxx_function_requires(_EqualOpConcept
<
5228 typename iterator_traits
<_InputIterator
>::value_type
,
5229 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5230 __glibcxx_requires_valid_range(__first1
, __last1
);
5231 __glibcxx_requires_valid_range(__first2
, __last2
);
5233 for ( ; __first1
!= __last1
; ++__first1
)
5234 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
5235 if (*__first1
== *__iter
)
5241 * @brief Find element from a set in a sequence using a predicate.
5242 * @param first1 Start of range to search.
5243 * @param last1 End of range to search.
5244 * @param first2 Start of match candidates.
5245 * @param last2 End of match candidates.
5246 * @param comp Predicate to use.
5247 * @return The first iterator @c i in the range
5248 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
5249 * interator in [first2,last2), or @p last1 if no such iterator exists.
5251 * Searches the range @p [first1,last1) for an element that is equal to
5252 * some element in the range [first2,last2). If found, returns an iterator in
5253 * the range [first1,last1), otherwise returns @p last1.
5255 template<typename _InputIterator
, typename _ForwardIterator
,
5256 typename _BinaryPredicate
>
5258 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
5259 _ForwardIterator __first2
, _ForwardIterator __last2
,
5260 _BinaryPredicate __comp
)
5262 // concept requirements
5263 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
5264 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5265 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
5266 typename iterator_traits
<_InputIterator
>::value_type
,
5267 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5268 __glibcxx_requires_valid_range(__first1
, __last1
);
5269 __glibcxx_requires_valid_range(__first2
, __last2
);
5271 for ( ; __first1
!= __last1
; ++__first1
)
5272 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
5273 if (__comp(*__first1
, *__iter
))
5279 // find_end, with and without an explicitly supplied comparison function.
5280 // Search [first2, last2) as a subsequence in [first1, last1), and return
5281 // the *last* possible match. Note that find_end for bidirectional iterators
5282 // is much faster than for forward iterators.
5284 // find_end for forward iterators.
5285 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
5287 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5288 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
5289 forward_iterator_tag
, forward_iterator_tag
)
5291 if (__first2
== __last2
)
5295 _ForwardIterator1 __result
= __last1
;
5298 _ForwardIterator1 __new_result
5299 = std::search(__first1
, __last1
, __first2
, __last2
);
5300 if (__new_result
== __last1
)
5304 __result
= __new_result
;
5305 __first1
= __new_result
;
5312 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
5313 typename _BinaryPredicate
>
5315 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5316 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
5317 forward_iterator_tag
, forward_iterator_tag
,
5318 _BinaryPredicate __comp
)
5320 if (__first2
== __last2
)
5324 _ForwardIterator1 __result
= __last1
;
5327 _ForwardIterator1 __new_result
5328 = std::search(__first1
, __last1
, __first2
, __last2
, __comp
);
5329 if (__new_result
== __last1
)
5333 __result
= __new_result
;
5334 __first1
= __new_result
;
5341 // find_end for bidirectional iterators. Requires partial specialization.
5342 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
>
5343 _BidirectionalIterator1
5344 __find_end(_BidirectionalIterator1 __first1
,
5345 _BidirectionalIterator1 __last1
,
5346 _BidirectionalIterator2 __first2
,
5347 _BidirectionalIterator2 __last2
,
5348 bidirectional_iterator_tag
, bidirectional_iterator_tag
)
5350 // concept requirements
5351 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5352 _BidirectionalIterator1
>)
5353 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5354 _BidirectionalIterator2
>)
5356 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
5357 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
5359 _RevIterator1
__rlast1(__first1
);
5360 _RevIterator2
__rlast2(__first2
);
5361 _RevIterator1 __rresult
= std::search(_RevIterator1(__last1
), __rlast1
,
5362 _RevIterator2(__last2
), __rlast2
);
5364 if (__rresult
== __rlast1
)
5368 _BidirectionalIterator1 __result
= __rresult
.base();
5369 std::advance(__result
, -std::distance(__first2
, __last2
));
5374 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
5375 typename _BinaryPredicate
>
5376 _BidirectionalIterator1
5377 __find_end(_BidirectionalIterator1 __first1
,
5378 _BidirectionalIterator1 __last1
,
5379 _BidirectionalIterator2 __first2
,
5380 _BidirectionalIterator2 __last2
,
5381 bidirectional_iterator_tag
, bidirectional_iterator_tag
,
5382 _BinaryPredicate __comp
)
5384 // concept requirements
5385 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5386 _BidirectionalIterator1
>)
5387 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5388 _BidirectionalIterator2
>)
5390 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
5391 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
5393 _RevIterator1
__rlast1(__first1
);
5394 _RevIterator2
__rlast2(__first2
);
5395 _RevIterator1 __rresult
= std::search(_RevIterator1(__last1
), __rlast1
,
5396 _RevIterator2(__last2
), __rlast2
,
5399 if (__rresult
== __rlast1
)
5403 _BidirectionalIterator1 __result
= __rresult
.base();
5404 std::advance(__result
, -std::distance(__first2
, __last2
));
5409 // Dispatching functions for find_end.
5412 * @brief Find last matching subsequence in a sequence.
5413 * @param first1 Start of range to search.
5414 * @param last1 End of range to search.
5415 * @param first2 Start of sequence to match.
5416 * @param last2 End of sequence to match.
5417 * @return The last iterator @c i in the range
5418 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5419 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
5420 * such iterator exists.
5422 * Searches the range @p [first1,last1) for a sub-sequence that compares
5423 * equal value-by-value with the sequence given by @p [first2,last2) and
5424 * returns an iterator to the first element of the sub-sequence, or
5425 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
5426 * last such subsequence contained in [first,last1).
5428 * Because the sub-sequence must lie completely within the range
5429 * @p [first1,last1) it must start at a position less than
5430 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5432 * This means that the returned iterator @c i will be in the range
5433 * @p [first1,last1-(last2-first2))
5435 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
5436 inline _ForwardIterator1
5437 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5438 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
5440 // concept requirements
5441 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
5442 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
5443 __glibcxx_function_requires(_EqualOpConcept
<
5444 typename iterator_traits
<_ForwardIterator1
>::value_type
,
5445 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
5446 __glibcxx_requires_valid_range(__first1
, __last1
);
5447 __glibcxx_requires_valid_range(__first2
, __last2
);
5449 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
5450 std::__iterator_category(__first1
),
5451 std::__iterator_category(__first2
));
5455 * @brief Find last matching subsequence in a sequence using a predicate.
5456 * @param first1 Start of range to search.
5457 * @param last1 End of range to search.
5458 * @param first2 Start of sequence to match.
5459 * @param last2 End of sequence to match.
5460 * @param comp The predicate to use.
5461 * @return The last iterator @c i in the range
5462 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5463 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5464 * @p last1 if no such iterator exists.
5466 * Searches the range @p [first1,last1) for a sub-sequence that compares
5467 * equal value-by-value with the sequence given by @p [first2,last2) using
5468 * comp as a predicate and returns an iterator to the first element of the
5469 * sub-sequence, or @p last1 if the sub-sequence is not found. The
5470 * sub-sequence will be the last such subsequence contained in
5473 * Because the sub-sequence must lie completely within the range
5474 * @p [first1,last1) it must start at a position less than
5475 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5477 * This means that the returned iterator @c i will be in the range
5478 * @p [first1,last1-(last2-first2))
5480 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
5481 typename _BinaryPredicate
>
5482 inline _ForwardIterator1
5483 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5484 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
5485 _BinaryPredicate __comp
)
5487 // concept requirements
5488 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
5489 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
5490 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
5491 typename iterator_traits
<_ForwardIterator1
>::value_type
,
5492 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
5493 __glibcxx_requires_valid_range(__first1
, __last1
);
5494 __glibcxx_requires_valid_range(__first2
, __last2
);
5496 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
5497 std::__iterator_category(__first1
),
5498 std::__iterator_category(__first2
),
5502 _GLIBCXX_END_NAMESPACE
5504 #endif /* _ALGO_H */