1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
33 * Hewlett-Packard Company
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
45 * Silicon Graphics Computer Systems, Inc.
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
64 #include <bits/stl_heap.h>
65 #include <bits/stl_tempbuf.h> // for _Temporary_buffer
66 #include <debug/debug.h>
68 // See concept_check.h for the __glibcxx_*_requires macros.
73 * @brief Find the median of three values.
77 * @return One of @p a, @p b or @p c.
79 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
80 * then the value returned will be @c m.
81 * This is an SGI extension.
82 * @ingroup SGIextensions
84 template<typename _Tp
>
86 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
)
88 // concept requirements
89 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
106 * @brief Find the median of three values using a predicate for comparison.
110 * @param comp A binary predicate.
111 * @return One of @p a, @p b or @p c.
113 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
114 * and @p comp(m,n) are both true then the value returned will be @c m.
115 * This is an SGI extension.
116 * @ingroup SGIextensions
118 template<typename _Tp
, typename _Compare
>
120 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
, _Compare __comp
)
122 // concept requirements
123 __glibcxx_function_requires(_BinaryFunctionConcept
<_Compare
,bool,_Tp
,_Tp
>)
124 if (__comp(__a
, __b
))
125 if (__comp(__b
, __c
))
127 else if (__comp(__a
, __c
))
131 else if (__comp(__a
, __c
))
133 else if (__comp(__b
, __c
))
140 * @brief Apply a function to every element of a sequence.
141 * @param first An input iterator.
142 * @param last An input iterator.
143 * @param f A unary function object.
146 * Applies the function object @p f to each element in the range
147 * @p [first,last). @p f must not modify the order of the sequence.
148 * If @p f has a return value it is ignored.
150 template<typename _InputIterator
, typename _Function
>
152 for_each(_InputIterator __first
, _InputIterator __last
, _Function __f
)
154 // concept requirements
155 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
156 __glibcxx_requires_valid_range(__first
, __last
);
157 for ( ; __first
!= __last
; ++__first
)
164 * This is an overload used by find() for the Input Iterator case.
167 template<typename _InputIterator
, typename _Tp
>
168 inline _InputIterator
169 __find(_InputIterator __first
, _InputIterator __last
,
170 const _Tp
& __val
, input_iterator_tag
)
172 while (__first
!= __last
&& !(*__first
== __val
))
179 * This is an overload used by find_if() for the Input Iterator case.
182 template<typename _InputIterator
, typename _Predicate
>
183 inline _InputIterator
184 __find_if(_InputIterator __first
, _InputIterator __last
,
185 _Predicate __pred
, input_iterator_tag
)
187 while (__first
!= __last
&& !__pred(*__first
))
194 * This is an overload used by find() for the RAI case.
197 template<typename _RandomAccessIterator
, typename _Tp
>
198 _RandomAccessIterator
199 __find(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
200 const _Tp
& __val
, random_access_iterator_tag
)
202 typename iterator_traits
<_RandomAccessIterator
>::difference_type
203 __trip_count
= (__last
- __first
) >> 2;
205 for ( ; __trip_count
> 0 ; --__trip_count
)
207 if (*__first
== __val
)
211 if (*__first
== __val
)
215 if (*__first
== __val
)
219 if (*__first
== __val
)
224 switch (__last
- __first
)
227 if (*__first
== __val
)
231 if (*__first
== __val
)
235 if (*__first
== __val
)
246 * This is an overload used by find_if() for the RAI case.
249 template<typename _RandomAccessIterator
, typename _Predicate
>
250 _RandomAccessIterator
251 __find_if(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
252 _Predicate __pred
, random_access_iterator_tag
)
254 typename iterator_traits
<_RandomAccessIterator
>::difference_type
255 __trip_count
= (__last
- __first
) >> 2;
257 for ( ; __trip_count
> 0 ; --__trip_count
)
259 if (__pred(*__first
))
263 if (__pred(*__first
))
267 if (__pred(*__first
))
271 if (__pred(*__first
))
276 switch (__last
- __first
)
279 if (__pred(*__first
))
283 if (__pred(*__first
))
287 if (__pred(*__first
))
297 * @brief Find the first occurrence of a value in a sequence.
298 * @param first An input iterator.
299 * @param last An input iterator.
300 * @param val The value to find.
301 * @return The first iterator @c i in the range @p [first,last)
302 * such that @c *i == @p val, or @p last if no such iterator exists.
304 template<typename _InputIterator
, typename _Tp
>
305 inline _InputIterator
306 find(_InputIterator __first
, _InputIterator __last
,
309 // concept requirements
310 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
311 __glibcxx_function_requires(_EqualOpConcept
<
312 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
313 __glibcxx_requires_valid_range(__first
, __last
);
314 return std::__find(__first
, __last
, __val
,
315 std::__iterator_category(__first
));
319 * @brief Find the first element in a sequence for which a predicate is true.
320 * @param first An input iterator.
321 * @param last An input iterator.
322 * @param pred A predicate.
323 * @return The first iterator @c i in the range @p [first,last)
324 * such that @p pred(*i) is true, or @p last if no such iterator exists.
326 template<typename _InputIterator
, typename _Predicate
>
327 inline _InputIterator
328 find_if(_InputIterator __first
, _InputIterator __last
,
331 // concept requirements
332 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
333 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
334 typename iterator_traits
<_InputIterator
>::value_type
>)
335 __glibcxx_requires_valid_range(__first
, __last
);
336 return std::__find_if(__first
, __last
, __pred
,
337 std::__iterator_category(__first
));
341 * @brief Find two adjacent values in a sequence that are equal.
342 * @param first A forward iterator.
343 * @param last A forward iterator.
344 * @return The first iterator @c i such that @c i and @c i+1 are both
345 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
346 * or @p last if no such iterator exists.
348 template<typename _ForwardIterator
>
350 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
)
352 // concept requirements
353 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
354 __glibcxx_function_requires(_EqualityComparableConcept
<
355 typename iterator_traits
<_ForwardIterator
>::value_type
>)
356 __glibcxx_requires_valid_range(__first
, __last
);
357 if (__first
== __last
)
359 _ForwardIterator __next
= __first
;
360 while(++__next
!= __last
)
362 if (*__first
== *__next
)
370 * @brief Find two adjacent values in a sequence using a predicate.
371 * @param first A forward iterator.
372 * @param last A forward iterator.
373 * @param binary_pred A binary predicate.
374 * @return The first iterator @c i such that @c i and @c i+1 are both
375 * valid iterators in @p [first,last) and such that
376 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
379 template<typename _ForwardIterator
, typename _BinaryPredicate
>
381 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
,
382 _BinaryPredicate __binary_pred
)
384 // concept requirements
385 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
386 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
387 typename iterator_traits
<_ForwardIterator
>::value_type
,
388 typename iterator_traits
<_ForwardIterator
>::value_type
>)
389 __glibcxx_requires_valid_range(__first
, __last
);
390 if (__first
== __last
)
392 _ForwardIterator __next
= __first
;
393 while(++__next
!= __last
)
395 if (__binary_pred(*__first
, *__next
))
403 * @brief Count the number of copies of a value in a sequence.
404 * @param first An input iterator.
405 * @param last An input iterator.
406 * @param value The value to be counted.
407 * @return The number of iterators @c i in the range @p [first,last)
408 * for which @c *i == @p value
410 template<typename _InputIterator
, typename _Tp
>
411 typename iterator_traits
<_InputIterator
>::difference_type
412 count(_InputIterator __first
, _InputIterator __last
, const _Tp
& __value
)
414 // concept requirements
415 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
416 __glibcxx_function_requires(_EqualOpConcept
<
417 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
418 __glibcxx_requires_valid_range(__first
, __last
);
419 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
420 for ( ; __first
!= __last
; ++__first
)
421 if (*__first
== __value
)
427 * @brief Count the elements of a sequence for which a predicate is true.
428 * @param first An input iterator.
429 * @param last An input iterator.
430 * @param pred A predicate.
431 * @return The number of iterators @c i in the range @p [first,last)
432 * for which @p pred(*i) is true.
434 template<typename _InputIterator
, typename _Predicate
>
435 typename iterator_traits
<_InputIterator
>::difference_type
436 count_if(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
438 // concept requirements
439 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
440 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
441 typename iterator_traits
<_InputIterator
>::value_type
>)
442 __glibcxx_requires_valid_range(__first
, __last
);
443 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
444 for ( ; __first
!= __last
; ++__first
)
445 if (__pred(*__first
))
451 * @brief Search a sequence for a matching sub-sequence.
452 * @param first1 A forward iterator.
453 * @param last1 A forward iterator.
454 * @param first2 A forward iterator.
455 * @param last2 A forward iterator.
456 * @return The first iterator @c i in the range
457 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
458 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
459 * such iterator exists.
461 * Searches the range @p [first1,last1) for a sub-sequence that compares
462 * equal value-by-value with the sequence given by @p [first2,last2) and
463 * returns an iterator to the first element of the sub-sequence, or
464 * @p last1 if the sub-sequence is not found.
466 * Because the sub-sequence must lie completely within the range
467 * @p [first1,last1) it must start at a position less than
468 * @p last1-(last2-first2) where @p last2-first2 is the length of the
470 * This means that the returned iterator @c i will be in the range
471 * @p [first1,last1-(last2-first2))
473 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
475 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
476 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
478 // concept requirements
479 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
480 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
481 __glibcxx_function_requires(_EqualOpConcept
<
482 typename iterator_traits
<_ForwardIterator1
>::value_type
,
483 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
484 __glibcxx_requires_valid_range(__first1
, __last1
);
485 __glibcxx_requires_valid_range(__first2
, __last2
);
486 // Test for empty ranges
487 if (__first1
== __last1
|| __first2
== __last2
)
490 // Test for a pattern of length 1.
491 _ForwardIterator2
__tmp(__first2
);
493 if (__tmp
== __last2
)
494 return std::find(__first1
, __last1
, *__first2
);
497 _ForwardIterator2 __p1
, __p
;
498 __p1
= __first2
; ++__p1
;
499 _ForwardIterator1 __current
= __first1
;
501 while (__first1
!= __last1
)
503 __first1
= std::find(__first1
, __last1
, *__first2
);
504 if (__first1
== __last1
)
508 __current
= __first1
;
509 if (++__current
== __last1
)
512 while (*__current
== *__p
)
514 if (++__p
== __last2
)
516 if (++__current
== __last1
)
525 * @brief Search a sequence for a matching sub-sequence using a predicate.
526 * @param first1 A forward iterator.
527 * @param last1 A forward iterator.
528 * @param first2 A forward iterator.
529 * @param last2 A forward iterator.
530 * @param predicate A binary predicate.
531 * @return The first iterator @c i in the range
532 * @p [first1,last1-(last2-first2)) such that
533 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
534 * @p [0,last2-first2), or @p last1 if no such iterator exists.
536 * Searches the range @p [first1,last1) for a sub-sequence that compares
537 * equal value-by-value with the sequence given by @p [first2,last2),
538 * using @p predicate to determine equality, and returns an iterator
539 * to the first element of the sub-sequence, or @p last1 if no such
542 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
544 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
545 typename _BinaryPredicate
>
547 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
548 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
549 _BinaryPredicate __predicate
)
551 // concept requirements
552 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
553 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
554 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
555 typename iterator_traits
<_ForwardIterator1
>::value_type
,
556 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
557 __glibcxx_requires_valid_range(__first1
, __last1
);
558 __glibcxx_requires_valid_range(__first2
, __last2
);
560 // Test for empty ranges
561 if (__first1
== __last1
|| __first2
== __last2
)
564 // Test for a pattern of length 1.
565 _ForwardIterator2
__tmp(__first2
);
567 if (__tmp
== __last2
)
569 while (__first1
!= __last1
&& !__predicate(*__first1
, *__first2
))
575 _ForwardIterator2 __p1
, __p
;
576 __p1
= __first2
; ++__p1
;
577 _ForwardIterator1 __current
= __first1
;
579 while (__first1
!= __last1
)
581 while (__first1
!= __last1
)
583 if (__predicate(*__first1
, *__first2
))
587 while (__first1
!= __last1
&& !__predicate(*__first1
, *__first2
))
589 if (__first1
== __last1
)
593 __current
= __first1
;
594 if (++__current
== __last1
)
597 while (__predicate(*__current
, *__p
))
599 if (++__p
== __last2
)
601 if (++__current
== __last1
)
611 * This is an uglified
612 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
613 * overloaded for forward iterators.
616 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
618 __search_n(_ForwardIterator __first
, _ForwardIterator __last
,
619 _Integer __count
, const _Tp
& __val
,
620 std::forward_iterator_tag
)
622 __first
= std::find(__first
, __last
, __val
);
623 while (__first
!= __last
)
625 typename iterator_traits
<_ForwardIterator
>::difference_type
627 _ForwardIterator __i
= __first
;
629 while (__i
!= __last
&& __n
!= 1 && *__i
== __val
)
638 __first
= std::find(++__i
, __last
, __val
);
645 * This is an uglified
646 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
647 * overloaded for random access iterators.
650 template<typename _RandomAccessIter
, typename _Integer
, typename _Tp
>
652 __search_n(_RandomAccessIter __first
, _RandomAccessIter __last
,
653 _Integer __count
, const _Tp
& __val
,
654 std::random_access_iterator_tag
)
657 typedef typename
std::iterator_traits
<_RandomAccessIter
>::difference_type
660 _DistanceType __tailSize
= __last
- __first
;
661 const _DistanceType __pattSize
= __count
;
663 if (__tailSize
< __pattSize
)
666 const _DistanceType __skipOffset
= __pattSize
- 1;
667 _RandomAccessIter __lookAhead
= __first
+ __skipOffset
;
668 __tailSize
-= __pattSize
;
670 while (1) // the main loop...
672 // __lookAhead here is always pointing to the last element of next
674 while (!(*__lookAhead
== __val
)) // the skip loop...
676 if (__tailSize
< __pattSize
)
677 return __last
; // Failure
678 __lookAhead
+= __pattSize
;
679 __tailSize
-= __pattSize
;
681 _DistanceType __remainder
= __skipOffset
;
682 for (_RandomAccessIter __backTrack
= __lookAhead
- 1;
683 *__backTrack
== __val
; --__backTrack
)
685 if (--__remainder
== 0)
686 return (__lookAhead
- __skipOffset
); // Success
688 if (__remainder
> __tailSize
)
689 return __last
; // Failure
690 __lookAhead
+= __remainder
;
691 __tailSize
-= __remainder
;
696 * @brief Search a sequence for a number of consecutive values.
697 * @param first A forward iterator.
698 * @param last A forward iterator.
699 * @param count The number of consecutive values.
700 * @param val The value to find.
701 * @return The first iterator @c i in the range @p [first,last-count)
702 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
703 * or @p last if no such iterator exists.
705 * Searches the range @p [first,last) for @p count consecutive elements
708 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
710 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
711 _Integer __count
, const _Tp
& __val
)
713 // concept requirements
714 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
715 __glibcxx_function_requires(_EqualOpConcept
<
716 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
717 __glibcxx_requires_valid_range(__first
, __last
);
722 return std::find(__first
, __last
, __val
);
723 return std::__search_n(__first
, __last
, __count
, __val
,
724 std::__iterator_category(__first
));
729 * This is an uglified
730 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
732 * overloaded for forward iterators.
735 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
736 typename _BinaryPredicate
>
738 __search_n(_ForwardIterator __first
, _ForwardIterator __last
,
739 _Integer __count
, const _Tp
& __val
,
740 _BinaryPredicate __binary_pred
, std::forward_iterator_tag
)
742 while (__first
!= __last
&& !__binary_pred(*__first
, __val
))
745 while (__first
!= __last
)
747 typename iterator_traits
<_ForwardIterator
>::difference_type
749 _ForwardIterator __i
= __first
;
751 while (__i
!= __last
&& __n
!= 1 && *__i
== __val
)
761 while (__first
!= __last
&& !__binary_pred(*__first
, __val
))
769 * This is an uglified
770 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
772 * overloaded for random access iterators.
775 template<typename _RandomAccessIter
, typename _Integer
, typename _Tp
,
776 typename _BinaryPredicate
>
778 __search_n(_RandomAccessIter __first
, _RandomAccessIter __last
,
779 _Integer __count
, const _Tp
& __val
,
780 _BinaryPredicate __binary_pred
, std::random_access_iterator_tag
)
783 typedef typename
std::iterator_traits
<_RandomAccessIter
>::difference_type
786 _DistanceType __tailSize
= __last
- __first
;
787 const _DistanceType __pattSize
= __count
;
789 if (__tailSize
< __pattSize
)
792 const _DistanceType __skipOffset
= __pattSize
- 1;
793 _RandomAccessIter __lookAhead
= __first
+ __skipOffset
;
794 __tailSize
-= __pattSize
;
796 while (1) // the main loop...
798 // __lookAhead here is always pointing to the last element of next
800 while (!__binary_pred(*__lookAhead
, __val
)) // the skip loop...
802 if (__tailSize
< __pattSize
)
803 return __last
; // Failure
804 __lookAhead
+= __pattSize
;
805 __tailSize
-= __pattSize
;
807 _DistanceType __remainder
= __skipOffset
;
808 for (_RandomAccessIter __backTrack
= __lookAhead
- 1;
809 __binary_pred(*__backTrack
, __val
); --__backTrack
)
811 if (--__remainder
== 0)
812 return (__lookAhead
- __skipOffset
); // Success
814 if (__remainder
> __tailSize
)
815 return __last
; // Failure
816 __lookAhead
+= __remainder
;
817 __tailSize
-= __remainder
;
822 * @brief Search a sequence for a number of consecutive values using a
824 * @param first A forward iterator.
825 * @param last A forward iterator.
826 * @param count The number of consecutive values.
827 * @param val The value to find.
828 * @param binary_pred A binary predicate.
829 * @return The first iterator @c i in the range @p [first,last-count)
830 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
831 * range @p [0,count), or @p last if no such iterator exists.
833 * Searches the range @p [first,last) for @p count consecutive elements
834 * for which the predicate returns true.
836 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
837 typename _BinaryPredicate
>
839 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
840 _Integer __count
, const _Tp
& __val
,
841 _BinaryPredicate __binary_pred
)
843 // concept requirements
844 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
845 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
846 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
847 __glibcxx_requires_valid_range(__first
, __last
);
853 while (__first
!= __last
&& !__binary_pred(*__first
, __val
))
857 return std::__search_n(__first
, __last
, __count
, __val
, __binary_pred
,
858 std::__iterator_category(__first
));
862 * @brief Swap the elements of two sequences.
863 * @param first1 A forward iterator.
864 * @param last1 A forward iterator.
865 * @param first2 A forward iterator.
866 * @return An iterator equal to @p first2+(last1-first1).
868 * Swaps each element in the range @p [first1,last1) with the
869 * corresponding element in the range @p [first2,(last1-first1)).
870 * The ranges must not overlap.
872 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
874 swap_ranges(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
875 _ForwardIterator2 __first2
)
877 // concept requirements
878 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
880 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
882 __glibcxx_function_requires(_ConvertibleConcept
<
883 typename iterator_traits
<_ForwardIterator1
>::value_type
,
884 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
885 __glibcxx_function_requires(_ConvertibleConcept
<
886 typename iterator_traits
<_ForwardIterator2
>::value_type
,
887 typename iterator_traits
<_ForwardIterator1
>::value_type
>)
888 __glibcxx_requires_valid_range(__first1
, __last1
);
890 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
891 std::iter_swap(__first1
, __first2
);
896 * @brief Perform an operation on a sequence.
897 * @param first An input iterator.
898 * @param last An input iterator.
899 * @param result An output iterator.
900 * @param unary_op A unary operator.
901 * @return An output iterator equal to @p result+(last-first).
903 * Applies the operator to each element in the input range and assigns
904 * the results to successive elements of the output sequence.
905 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
906 * range @p [0,last-first).
908 * @p unary_op must not alter its argument.
910 template<typename _InputIterator
, typename _OutputIterator
,
911 typename _UnaryOperation
>
913 transform(_InputIterator __first
, _InputIterator __last
,
914 _OutputIterator __result
, _UnaryOperation __unary_op
)
916 // concept requirements
917 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
918 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
919 // "the type returned by a _UnaryOperation"
920 __typeof__(__unary_op(*__first
))>)
921 __glibcxx_requires_valid_range(__first
, __last
);
923 for ( ; __first
!= __last
; ++__first
, ++__result
)
924 *__result
= __unary_op(*__first
);
929 * @brief Perform an operation on corresponding elements of two sequences.
930 * @param first1 An input iterator.
931 * @param last1 An input iterator.
932 * @param first2 An input iterator.
933 * @param result An output iterator.
934 * @param binary_op A binary operator.
935 * @return An output iterator equal to @p result+(last-first).
937 * Applies the operator to the corresponding elements in the two
938 * input ranges and assigns the results to successive elements of the
940 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
941 * @c N in the range @p [0,last1-first1).
943 * @p binary_op must not alter either of its arguments.
945 template<typename _InputIterator1
, typename _InputIterator2
,
946 typename _OutputIterator
, typename _BinaryOperation
>
948 transform(_InputIterator1 __first1
, _InputIterator1 __last1
,
949 _InputIterator2 __first2
, _OutputIterator __result
,
950 _BinaryOperation __binary_op
)
952 // concept requirements
953 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
954 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
955 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
956 // "the type returned by a _BinaryOperation"
957 __typeof__(__binary_op(*__first1
,*__first2
))>)
958 __glibcxx_requires_valid_range(__first1
, __last1
);
960 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
, ++__result
)
961 *__result
= __binary_op(*__first1
, *__first2
);
966 * @brief Replace each occurrence of one value in a sequence with another
968 * @param first A forward iterator.
969 * @param last A forward iterator.
970 * @param old_value The value to be replaced.
971 * @param new_value The replacement value.
972 * @return replace() returns no value.
974 * For each iterator @c i in the range @p [first,last) if @c *i ==
975 * @p old_value then the assignment @c *i = @p new_value is performed.
977 template<typename _ForwardIterator
, typename _Tp
>
979 replace(_ForwardIterator __first
, _ForwardIterator __last
,
980 const _Tp
& __old_value
, const _Tp
& __new_value
)
982 // concept requirements
983 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
985 __glibcxx_function_requires(_EqualOpConcept
<
986 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
987 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
988 typename iterator_traits
<_ForwardIterator
>::value_type
>)
989 __glibcxx_requires_valid_range(__first
, __last
);
991 for ( ; __first
!= __last
; ++__first
)
992 if (*__first
== __old_value
)
993 *__first
= __new_value
;
997 * @brief Replace each value in a sequence for which a predicate returns
998 * true with another value.
999 * @param first A forward iterator.
1000 * @param last A forward iterator.
1001 * @param pred A predicate.
1002 * @param new_value The replacement value.
1003 * @return replace_if() returns no value.
1005 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
1006 * is true then the assignment @c *i = @p new_value is performed.
1008 template<typename _ForwardIterator
, typename _Predicate
, typename _Tp
>
1010 replace_if(_ForwardIterator __first
, _ForwardIterator __last
,
1011 _Predicate __pred
, const _Tp
& __new_value
)
1013 // concept requirements
1014 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1016 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
1017 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1018 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1019 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1020 __glibcxx_requires_valid_range(__first
, __last
);
1022 for ( ; __first
!= __last
; ++__first
)
1023 if (__pred(*__first
))
1024 *__first
= __new_value
;
1028 * @brief Copy a sequence, replacing each element of one value with another
1030 * @param first An input iterator.
1031 * @param last An input iterator.
1032 * @param result An output iterator.
1033 * @param old_value The value to be replaced.
1034 * @param new_value The replacement value.
1035 * @return The end of the output sequence, @p result+(last-first).
1037 * Copies each element in the input range @p [first,last) to the
1038 * output range @p [result,result+(last-first)) replacing elements
1039 * equal to @p old_value with @p new_value.
1041 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
1043 replace_copy(_InputIterator __first
, _InputIterator __last
,
1044 _OutputIterator __result
,
1045 const _Tp
& __old_value
, const _Tp
& __new_value
)
1047 // concept requirements
1048 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1049 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1050 typename iterator_traits
<_InputIterator
>::value_type
>)
1051 __glibcxx_function_requires(_EqualOpConcept
<
1052 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
1053 __glibcxx_requires_valid_range(__first
, __last
);
1055 for ( ; __first
!= __last
; ++__first
, ++__result
)
1056 if (*__first
== __old_value
)
1057 *__result
= __new_value
;
1059 *__result
= *__first
;
1064 * @brief Copy a sequence, replacing each value for which a predicate
1065 * returns true with another value.
1066 * @param first An input iterator.
1067 * @param last An input iterator.
1068 * @param result An output iterator.
1069 * @param pred A predicate.
1070 * @param new_value The replacement value.
1071 * @return The end of the output sequence, @p result+(last-first).
1073 * Copies each element in the range @p [first,last) to the range
1074 * @p [result,result+(last-first)) replacing elements for which
1075 * @p pred returns true with @p new_value.
1077 template<typename _InputIterator
, typename _OutputIterator
,
1078 typename _Predicate
, typename _Tp
>
1080 replace_copy_if(_InputIterator __first
, _InputIterator __last
,
1081 _OutputIterator __result
,
1082 _Predicate __pred
, const _Tp
& __new_value
)
1084 // concept requirements
1085 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1086 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1087 typename iterator_traits
<_InputIterator
>::value_type
>)
1088 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1089 typename iterator_traits
<_InputIterator
>::value_type
>)
1090 __glibcxx_requires_valid_range(__first
, __last
);
1092 for ( ; __first
!= __last
; ++__first
, ++__result
)
1093 if (__pred(*__first
))
1094 *__result
= __new_value
;
1096 *__result
= *__first
;
1101 * @brief Assign the result of a function object to each value in a
1103 * @param first A forward iterator.
1104 * @param last A forward iterator.
1105 * @param gen A function object taking no arguments.
1106 * @return generate() returns no value.
1108 * Performs the assignment @c *i = @p gen() for each @c i in the range
1111 template<typename _ForwardIterator
, typename _Generator
>
1113 generate(_ForwardIterator __first
, _ForwardIterator __last
,
1116 // concept requirements
1117 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1118 __glibcxx_function_requires(_GeneratorConcept
<_Generator
,
1119 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1120 __glibcxx_requires_valid_range(__first
, __last
);
1122 for ( ; __first
!= __last
; ++__first
)
1127 * @brief Assign the result of a function object to each value in a
1129 * @param first A forward iterator.
1130 * @param n The length of the sequence.
1131 * @param gen A function object taking no arguments.
1132 * @return The end of the sequence, @p first+n
1134 * Performs the assignment @c *i = @p gen() for each @c i in the range
1135 * @p [first,first+n).
1137 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1139 generate_n(_OutputIterator __first
, _Size __n
, _Generator __gen
)
1141 // concept requirements
1142 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1143 // "the type returned by a _Generator"
1144 __typeof__(__gen())>)
1146 for ( ; __n
> 0; --__n
, ++__first
)
1152 * @brief Copy a sequence, removing elements of a given value.
1153 * @param first An input iterator.
1154 * @param last An input iterator.
1155 * @param result An output iterator.
1156 * @param value The value to be removed.
1157 * @return An iterator designating the end of the resulting sequence.
1159 * Copies each element in the range @p [first,last) not equal to @p value
1160 * to the range beginning at @p result.
1161 * remove_copy() is stable, so the relative order of elements that are
1162 * copied is unchanged.
1164 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
1166 remove_copy(_InputIterator __first
, _InputIterator __last
,
1167 _OutputIterator __result
, const _Tp
& __value
)
1169 // concept requirements
1170 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1171 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1172 typename iterator_traits
<_InputIterator
>::value_type
>)
1173 __glibcxx_function_requires(_EqualOpConcept
<
1174 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
1175 __glibcxx_requires_valid_range(__first
, __last
);
1177 for ( ; __first
!= __last
; ++__first
)
1178 if (!(*__first
== __value
))
1180 *__result
= *__first
;
1187 * @brief Copy a sequence, removing elements for which a predicate is true.
1188 * @param first An input iterator.
1189 * @param last An input iterator.
1190 * @param result An output iterator.
1191 * @param pred A predicate.
1192 * @return An iterator designating the end of the resulting sequence.
1194 * Copies each element in the range @p [first,last) for which
1195 * @p pred returns true to the range beginning at @p result.
1197 * remove_copy_if() is stable, so the relative order of elements that are
1198 * copied is unchanged.
1200 template<typename _InputIterator
, typename _OutputIterator
,
1201 typename _Predicate
>
1203 remove_copy_if(_InputIterator __first
, _InputIterator __last
,
1204 _OutputIterator __result
, _Predicate __pred
)
1206 // concept requirements
1207 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1208 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1209 typename iterator_traits
<_InputIterator
>::value_type
>)
1210 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1211 typename iterator_traits
<_InputIterator
>::value_type
>)
1212 __glibcxx_requires_valid_range(__first
, __last
);
1214 for ( ; __first
!= __last
; ++__first
)
1215 if (!__pred(*__first
))
1217 *__result
= *__first
;
1224 * @brief Remove elements from a sequence.
1225 * @param first An input iterator.
1226 * @param last An input iterator.
1227 * @param value The value to be removed.
1228 * @return An iterator designating the end of the resulting sequence.
1230 * All elements equal to @p value are removed from the range
1233 * remove() is stable, so the relative order of elements that are
1234 * not removed is unchanged.
1236 * Elements between the end of the resulting sequence and @p last
1237 * are still present, but their value is unspecified.
1239 template<typename _ForwardIterator
, typename _Tp
>
1241 remove(_ForwardIterator __first
, _ForwardIterator __last
,
1244 // concept requirements
1245 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1247 __glibcxx_function_requires(_EqualOpConcept
<
1248 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
1249 __glibcxx_requires_valid_range(__first
, __last
);
1251 __first
= std::find(__first
, __last
, __value
);
1252 _ForwardIterator __i
= __first
;
1253 return __first
== __last
? __first
1254 : std::remove_copy(++__i
, __last
,
1259 * @brief Remove elements from a sequence using a predicate.
1260 * @param first A forward iterator.
1261 * @param last A forward iterator.
1262 * @param pred A predicate.
1263 * @return An iterator designating the end of the resulting sequence.
1265 * All elements for which @p pred returns true are removed from the range
1268 * remove_if() is stable, so the relative order of elements that are
1269 * not removed is unchanged.
1271 * Elements between the end of the resulting sequence and @p last
1272 * are still present, but their value is unspecified.
1274 template<typename _ForwardIterator
, typename _Predicate
>
1276 remove_if(_ForwardIterator __first
, _ForwardIterator __last
,
1279 // concept requirements
1280 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1282 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1283 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1284 __glibcxx_requires_valid_range(__first
, __last
);
1286 __first
= std::find_if(__first
, __last
, __pred
);
1287 _ForwardIterator __i
= __first
;
1288 return __first
== __last
? __first
1289 : std::remove_copy_if(++__i
, __last
,
1295 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1297 * overloaded for output iterators.
1300 template<typename _InputIterator
, typename _OutputIterator
>
1302 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1303 _OutputIterator __result
,
1304 output_iterator_tag
)
1306 // concept requirements -- taken care of in dispatching function
1307 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1308 *__result
= __value
;
1309 while (++__first
!= __last
)
1310 if (!(__value
== *__first
))
1313 *++__result
= __value
;
1320 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1322 * overloaded for forward iterators.
1325 template<typename _InputIterator
, typename _ForwardIterator
>
1327 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1328 _ForwardIterator __result
,
1329 forward_iterator_tag
)
1331 // concept requirements -- taken care of in dispatching function
1332 *__result
= *__first
;
1333 while (++__first
!= __last
)
1334 if (!(*__result
== *__first
))
1335 *++__result
= *__first
;
1341 * This is an uglified
1342 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1344 * overloaded for output iterators.
1347 template<typename _InputIterator
, typename _OutputIterator
,
1348 typename _BinaryPredicate
>
1350 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1351 _OutputIterator __result
,
1352 _BinaryPredicate __binary_pred
,
1353 output_iterator_tag
)
1355 // concept requirements -- iterators already checked
1356 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1357 typename iterator_traits
<_InputIterator
>::value_type
,
1358 typename iterator_traits
<_InputIterator
>::value_type
>)
1360 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1361 *__result
= __value
;
1362 while (++__first
!= __last
)
1363 if (!__binary_pred(__value
, *__first
))
1366 *++__result
= __value
;
1373 * This is an uglified
1374 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1376 * overloaded for forward iterators.
1379 template<typename _InputIterator
, typename _ForwardIterator
,
1380 typename _BinaryPredicate
>
1382 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1383 _ForwardIterator __result
,
1384 _BinaryPredicate __binary_pred
,
1385 forward_iterator_tag
)
1387 // concept requirements -- iterators already checked
1388 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1389 typename iterator_traits
<_ForwardIterator
>::value_type
,
1390 typename iterator_traits
<_InputIterator
>::value_type
>)
1392 *__result
= *__first
;
1393 while (++__first
!= __last
)
1394 if (!__binary_pred(*__result
, *__first
)) *++__result
= *__first
;
1399 * @brief Copy a sequence, removing consecutive duplicate values.
1400 * @param first An input iterator.
1401 * @param last An input iterator.
1402 * @param result An output iterator.
1403 * @return An iterator designating the end of the resulting sequence.
1405 * Copies each element in the range @p [first,last) to the range
1406 * beginning at @p result, except that only the first element is copied
1407 * from groups of consecutive elements that compare equal.
1408 * unique_copy() is stable, so the relative order of elements that are
1409 * copied is unchanged.
1411 template<typename _InputIterator
, typename _OutputIterator
>
1412 inline _OutputIterator
1413 unique_copy(_InputIterator __first
, _InputIterator __last
,
1414 _OutputIterator __result
)
1416 // concept requirements
1417 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1418 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1419 typename iterator_traits
<_InputIterator
>::value_type
>)
1420 __glibcxx_function_requires(_EqualityComparableConcept
<
1421 typename iterator_traits
<_InputIterator
>::value_type
>)
1422 __glibcxx_requires_valid_range(__first
, __last
);
1424 typedef typename iterator_traits
<_OutputIterator
>::iterator_category
1427 if (__first
== __last
) return __result
;
1428 return std::__unique_copy(__first
, __last
, __result
, _IterType());
1432 * @brief Copy a sequence, removing consecutive values using a predicate.
1433 * @param first An input iterator.
1434 * @param last An input iterator.
1435 * @param result An output iterator.
1436 * @param binary_pred A binary predicate.
1437 * @return An iterator designating the end of the resulting sequence.
1439 * Copies each element in the range @p [first,last) to the range
1440 * beginning at @p result, except that only the first element is copied
1441 * from groups of consecutive elements for which @p binary_pred returns
1443 * unique_copy() is stable, so the relative order of elements that are
1444 * copied is unchanged.
1446 template<typename _InputIterator
, typename _OutputIterator
,
1447 typename _BinaryPredicate
>
1448 inline _OutputIterator
1449 unique_copy(_InputIterator __first
, _InputIterator __last
,
1450 _OutputIterator __result
,
1451 _BinaryPredicate __binary_pred
)
1453 // concept requirements -- predicates checked later
1454 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1455 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1456 typename iterator_traits
<_InputIterator
>::value_type
>)
1457 __glibcxx_requires_valid_range(__first
, __last
);
1459 typedef typename iterator_traits
<_OutputIterator
>::iterator_category
1462 if (__first
== __last
) return __result
;
1463 return std::__unique_copy(__first
, __last
, __result
,
1464 __binary_pred
, _IterType());
1468 * @brief Remove consecutive duplicate values from a sequence.
1469 * @param first A forward iterator.
1470 * @param last A forward iterator.
1471 * @return An iterator designating the end of the resulting sequence.
1473 * Removes all but the first element from each group of consecutive
1474 * values that compare equal.
1475 * unique() is stable, so the relative order of elements that are
1476 * not removed is unchanged.
1477 * Elements between the end of the resulting sequence and @p last
1478 * are still present, but their value is unspecified.
1480 template<typename _ForwardIterator
>
1482 unique(_ForwardIterator __first
, _ForwardIterator __last
)
1484 // concept requirements
1485 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1487 __glibcxx_function_requires(_EqualityComparableConcept
<
1488 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1489 __glibcxx_requires_valid_range(__first
, __last
);
1491 // Skip the beginning, if already unique.
1492 __first
= std::adjacent_find(__first
, __last
);
1493 if (__first
== __last
)
1496 // Do the real copy work.
1497 _ForwardIterator __dest
= __first
;
1499 while (++__first
!= __last
)
1500 if (!(*__dest
== *__first
))
1501 *++__dest
= *__first
;
1506 * @brief Remove consecutive values from a sequence using a predicate.
1507 * @param first A forward iterator.
1508 * @param last A forward iterator.
1509 * @param binary_pred A binary predicate.
1510 * @return An iterator designating the end of the resulting sequence.
1512 * Removes all but the first element from each group of consecutive
1513 * values for which @p binary_pred returns true.
1514 * unique() is stable, so the relative order of elements that are
1515 * not removed is unchanged.
1516 * Elements between the end of the resulting sequence and @p last
1517 * are still present, but their value is unspecified.
1519 template<typename _ForwardIterator
, typename _BinaryPredicate
>
1521 unique(_ForwardIterator __first
, _ForwardIterator __last
,
1522 _BinaryPredicate __binary_pred
)
1524 // concept requirements
1525 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1527 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1528 typename iterator_traits
<_ForwardIterator
>::value_type
,
1529 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1530 __glibcxx_requires_valid_range(__first
, __last
);
1532 // Skip the beginning, if already unique.
1533 __first
= std::adjacent_find(__first
, __last
, __binary_pred
);
1534 if (__first
== __last
)
1537 // Do the real copy work.
1538 _ForwardIterator __dest
= __first
;
1540 while (++__first
!= __last
)
1541 if (!__binary_pred(*__dest
, *__first
))
1542 *++__dest
= *__first
;
1548 * This is an uglified reverse(_BidirectionalIterator,
1549 * _BidirectionalIterator)
1550 * overloaded for bidirectional iterators.
1553 template<typename _BidirectionalIterator
>
1555 __reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1556 bidirectional_iterator_tag
)
1559 if (__first
== __last
|| __first
== --__last
)
1563 std::iter_swap(__first
, __last
);
1570 * This is an uglified reverse(_BidirectionalIterator,
1571 * _BidirectionalIterator)
1572 * overloaded for random access iterators.
1575 template<typename _RandomAccessIterator
>
1577 __reverse(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1578 random_access_iterator_tag
)
1580 if (__first
== __last
)
1583 while (__first
< __last
)
1585 std::iter_swap(__first
, __last
);
1592 * @brief Reverse a sequence.
1593 * @param first A bidirectional iterator.
1594 * @param last A bidirectional iterator.
1595 * @return reverse() returns no value.
1597 * Reverses the order of the elements in the range @p [first,last),
1598 * so that the first element becomes the last etc.
1599 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1600 * swaps @p *(first+i) and @p *(last-(i+1))
1602 template<typename _BidirectionalIterator
>
1604 reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
)
1606 // concept requirements
1607 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1608 _BidirectionalIterator
>)
1609 __glibcxx_requires_valid_range(__first
, __last
);
1610 std::__reverse(__first
, __last
, std::__iterator_category(__first
));
1614 * @brief Copy a sequence, reversing its elements.
1615 * @param first A bidirectional iterator.
1616 * @param last A bidirectional iterator.
1617 * @param result An output iterator.
1618 * @return An iterator designating the end of the resulting sequence.
1620 * Copies the elements in the range @p [first,last) to the range
1621 * @p [result,result+(last-first)) such that the order of the
1622 * elements is reversed.
1623 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1624 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1625 * The ranges @p [first,last) and @p [result,result+(last-first))
1628 template<typename _BidirectionalIterator
, typename _OutputIterator
>
1630 reverse_copy(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1631 _OutputIterator __result
)
1633 // concept requirements
1634 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
1635 _BidirectionalIterator
>)
1636 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1637 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
1638 __glibcxx_requires_valid_range(__first
, __last
);
1640 while (__first
!= __last
)
1643 *__result
= *__last
;
1652 * This is a helper function for the rotate algorithm specialized on RAIs.
1653 * It returns the greatest common divisor of two integer values.
1656 template<typename _EuclideanRingElement
>
1657 _EuclideanRingElement
1658 __gcd(_EuclideanRingElement __m
, _EuclideanRingElement __n
)
1662 _EuclideanRingElement __t
= __m
% __n
;
1671 * This is a helper function for the rotate algorithm.
1674 template<typename _ForwardIterator
>
1676 __rotate(_ForwardIterator __first
,
1677 _ForwardIterator __middle
,
1678 _ForwardIterator __last
,
1679 forward_iterator_tag
)
1681 if (__first
== __middle
|| __last
== __middle
)
1684 _ForwardIterator __first2
= __middle
;
1687 swap(*__first
, *__first2
);
1690 if (__first
== __middle
)
1691 __middle
= __first2
;
1693 while (__first2
!= __last
);
1695 __first2
= __middle
;
1697 while (__first2
!= __last
)
1699 swap(*__first
, *__first2
);
1702 if (__first
== __middle
)
1703 __middle
= __first2
;
1704 else if (__first2
== __last
)
1705 __first2
= __middle
;
1711 * This is a helper function for the rotate algorithm.
1714 template<typename _BidirectionalIterator
>
1716 __rotate(_BidirectionalIterator __first
,
1717 _BidirectionalIterator __middle
,
1718 _BidirectionalIterator __last
,
1719 bidirectional_iterator_tag
)
1721 // concept requirements
1722 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1723 _BidirectionalIterator
>)
1725 if (__first
== __middle
|| __last
== __middle
)
1728 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1729 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1731 while (__first
!= __middle
&& __middle
!= __last
)
1733 swap(*__first
, *--__last
);
1737 if (__first
== __middle
)
1738 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1740 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1745 * This is a helper function for the rotate algorithm.
1748 template<typename _RandomAccessIterator
>
1750 __rotate(_RandomAccessIterator __first
,
1751 _RandomAccessIterator __middle
,
1752 _RandomAccessIterator __last
,
1753 random_access_iterator_tag
)
1755 // concept requirements
1756 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1757 _RandomAccessIterator
>)
1759 if (__first
== __middle
|| __last
== __middle
)
1762 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
1764 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
1767 const _Distance __n
= __last
- __first
;
1768 const _Distance __k
= __middle
- __first
;
1769 const _Distance __l
= __n
- __k
;
1773 std::swap_ranges(__first
, __middle
, __middle
);
1777 const _Distance __d
= __gcd(__n
, __k
);
1779 for (_Distance __i
= 0; __i
< __d
; __i
++)
1781 _ValueType __tmp
= *__first
;
1782 _RandomAccessIterator __p
= __first
;
1786 for (_Distance __j
= 0; __j
< __l
/ __d
; __j
++)
1788 if (__p
> __first
+ __l
)
1790 *__p
= *(__p
- __l
);
1794 *__p
= *(__p
+ __k
);
1800 for (_Distance __j
= 0; __j
< __k
/ __d
- 1; __j
++)
1802 if (__p
< __last
- __k
)
1804 *__p
= *(__p
+ __k
);
1807 *__p
= * (__p
- __l
);
1818 * @brief Rotate the elements of a sequence.
1819 * @param first A forward iterator.
1820 * @param middle A forward iterator.
1821 * @param last A forward iterator.
1824 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1825 * positions so that the element at @p middle is moved to @p first, the
1826 * element at @p middle+1 is moved to @first+1 and so on for each element
1827 * in the range @p [first,last).
1829 * This effectively swaps the ranges @p [first,middle) and
1832 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1833 * each @p n in the range @p [0,last-first).
1835 template<typename _ForwardIterator
>
1837 rotate(_ForwardIterator __first
, _ForwardIterator __middle
,
1838 _ForwardIterator __last
)
1840 // concept requirements
1841 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1843 __glibcxx_requires_valid_range(__first
, __middle
);
1844 __glibcxx_requires_valid_range(__middle
, __last
);
1846 typedef typename iterator_traits
<_ForwardIterator
>::iterator_category
1848 std::__rotate(__first
, __middle
, __last
, _IterType());
1852 * @brief Copy a sequence, rotating its elements.
1853 * @param first A forward iterator.
1854 * @param middle A forward iterator.
1855 * @param last A forward iterator.
1856 * @param result An output iterator.
1857 * @return An iterator designating the end of the resulting sequence.
1859 * Copies the elements of the range @p [first,last) to the range
1860 * beginning at @result, rotating the copied elements by @p (middle-first)
1861 * positions so that the element at @p middle is moved to @p result, the
1862 * element at @p middle+1 is moved to @result+1 and so on for each element
1863 * in the range @p [first,last).
1865 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1866 * each @p n in the range @p [0,last-first).
1868 template<typename _ForwardIterator
, typename _OutputIterator
>
1870 rotate_copy(_ForwardIterator __first
, _ForwardIterator __middle
,
1871 _ForwardIterator __last
, _OutputIterator __result
)
1873 // concept requirements
1874 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1875 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1876 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1877 __glibcxx_requires_valid_range(__first
, __middle
);
1878 __glibcxx_requires_valid_range(__middle
, __last
);
1880 return std::copy(__first
, __middle
,
1881 std::copy(__middle
, __last
, __result
));
1885 * @brief Randomly shuffle the elements of a sequence.
1886 * @param first A forward iterator.
1887 * @param last A forward iterator.
1890 * Reorder the elements in the range @p [first,last) using a random
1891 * distribution, so that every possible ordering of the sequence is
1894 template<typename _RandomAccessIterator
>
1896 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
1898 // concept requirements
1899 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1900 _RandomAccessIterator
>)
1901 __glibcxx_requires_valid_range(__first
, __last
);
1903 if (__first
!= __last
)
1904 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
1905 std::iter_swap(__i
, __first
+ (std::rand() % ((__i
- __first
) + 1)));
1909 * @brief Shuffle the elements of a sequence using a random number
1911 * @param first A forward iterator.
1912 * @param last A forward iterator.
1913 * @param rand The RNG functor or function.
1916 * Reorders the elements in the range @p [first,last) using @p rand to
1917 * provide a random distribution. Calling @p rand(N) for a positive
1918 * integer @p N should return a randomly chosen integer from the
1921 template<typename _RandomAccessIterator
, typename _RandomNumberGenerator
>
1923 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1924 _RandomNumberGenerator
& __rand
)
1926 // concept requirements
1927 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1928 _RandomAccessIterator
>)
1929 __glibcxx_requires_valid_range(__first
, __last
);
1931 if (__first
== __last
)
1933 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
1934 std::iter_swap(__i
, __first
+ __rand((__i
- __first
) + 1));
1940 * This is a helper function...
1943 template<typename _ForwardIterator
, typename _Predicate
>
1945 __partition(_ForwardIterator __first
, _ForwardIterator __last
,
1947 forward_iterator_tag
)
1949 if (__first
== __last
)
1952 while (__pred(*__first
))
1953 if (++__first
== __last
)
1956 _ForwardIterator __next
= __first
;
1958 while (++__next
!= __last
)
1959 if (__pred(*__next
))
1961 swap(*__first
, *__next
);
1970 * This is a helper function...
1973 template<typename _BidirectionalIterator
, typename _Predicate
>
1974 _BidirectionalIterator
1975 __partition(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1977 bidirectional_iterator_tag
)
1982 if (__first
== __last
)
1984 else if (__pred(*__first
))
1990 if (__first
== __last
)
1992 else if (!__pred(*__last
))
1996 std::iter_swap(__first
, __last
);
2002 * @brief Move elements for which a predicate is true to the beginning
2004 * @param first A forward iterator.
2005 * @param last A forward iterator.
2006 * @param pred A predicate functor.
2007 * @return An iterator @p middle such that @p pred(i) is true for each
2008 * iterator @p i in the range @p [first,middle) and false for each @p i
2009 * in the range @p [middle,last).
2011 * @p pred must not modify its operand. @p partition() does not preserve
2012 * the relative ordering of elements in each group, use
2013 * @p stable_partition() if this is needed.
2015 template<typename _ForwardIterator
, typename _Predicate
>
2016 inline _ForwardIterator
2017 partition(_ForwardIterator __first
, _ForwardIterator __last
,
2020 // concept requirements
2021 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
2023 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
2024 typename iterator_traits
<_ForwardIterator
>::value_type
>)
2025 __glibcxx_requires_valid_range(__first
, __last
);
2027 return std::__partition(__first
, __last
, __pred
,
2028 std::__iterator_category(__first
));
2034 * This is a helper function...
2037 template<typename _ForwardIterator
, typename _Predicate
, typename _Distance
>
2039 __inplace_stable_partition(_ForwardIterator __first
,
2040 _ForwardIterator __last
,
2041 _Predicate __pred
, _Distance __len
)
2044 return __pred(*__first
) ? __last
: __first
;
2045 _ForwardIterator __middle
= __first
;
2046 std::advance(__middle
, __len
/ 2);
2047 _ForwardIterator __begin
= std::__inplace_stable_partition(__first
,
2051 _ForwardIterator __end
= std::__inplace_stable_partition(__middle
, __last
,
2055 std::rotate(__begin
, __middle
, __end
);
2056 std::advance(__begin
, std::distance(__middle
, __end
));
2062 * This is a helper function...
2065 template<typename _ForwardIterator
, typename _Pointer
, typename _Predicate
,
2068 __stable_partition_adaptive(_ForwardIterator __first
,
2069 _ForwardIterator __last
,
2070 _Predicate __pred
, _Distance __len
,
2072 _Distance __buffer_size
)
2074 if (__len
<= __buffer_size
)
2076 _ForwardIterator __result1
= __first
;
2077 _Pointer __result2
= __buffer
;
2078 for ( ; __first
!= __last
; ++__first
)
2079 if (__pred(*__first
))
2081 *__result1
= *__first
;
2086 *__result2
= *__first
;
2089 std::copy(__buffer
, __result2
, __result1
);
2094 _ForwardIterator __middle
= __first
;
2095 std::advance(__middle
, __len
/ 2);
2096 _ForwardIterator __begin
=
2097 std::__stable_partition_adaptive(__first
, __middle
, __pred
,
2098 __len
/ 2, __buffer
,
2100 _ForwardIterator __end
=
2101 std::__stable_partition_adaptive(__middle
, __last
, __pred
,
2103 __buffer
, __buffer_size
);
2104 std::rotate(__begin
, __middle
, __end
);
2105 std::advance(__begin
, std::distance(__middle
, __end
));
2111 * @brief Move elements for which a predicate is true to the beginning
2112 * of a sequence, preserving relative ordering.
2113 * @param first A forward iterator.
2114 * @param last A forward iterator.
2115 * @param pred A predicate functor.
2116 * @return An iterator @p middle such that @p pred(i) is true for each
2117 * iterator @p i in the range @p [first,middle) and false for each @p i
2118 * in the range @p [middle,last).
2120 * Performs the same function as @p partition() with the additional
2121 * guarantee that the relative ordering of elements in each group is
2122 * preserved, so any two elements @p x and @p y in the range
2123 * @p [first,last) such that @p pred(x)==pred(y) will have the same
2124 * relative ordering after calling @p stable_partition().
2126 template<typename _ForwardIterator
, typename _Predicate
>
2128 stable_partition(_ForwardIterator __first
, _ForwardIterator __last
,
2131 // concept requirements
2132 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
2134 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
2135 typename iterator_traits
<_ForwardIterator
>::value_type
>)
2136 __glibcxx_requires_valid_range(__first
, __last
);
2138 if (__first
== __last
)
2142 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2144 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2147 _Temporary_buffer
<_ForwardIterator
, _ValueType
> __buf(__first
,
2149 if (__buf
.size() > 0)
2151 std::__stable_partition_adaptive(__first
, __last
, __pred
,
2152 _DistanceType(__buf
.requested_size()),
2153 __buf
.begin(), __buf
.size());
2156 std::__inplace_stable_partition(__first
, __last
, __pred
,
2157 _DistanceType(__buf
.requested_size()));
2163 * This is a helper function...
2166 template<typename _RandomAccessIterator
, typename _Tp
>
2167 _RandomAccessIterator
2168 __unguarded_partition(_RandomAccessIterator __first
,
2169 _RandomAccessIterator __last
, _Tp __pivot
)
2173 while (*__first
< __pivot
)
2176 while (__pivot
< *__last
)
2178 if (!(__first
< __last
))
2180 std::iter_swap(__first
, __last
);
2187 * This is a helper function...
2190 template<typename _RandomAccessIterator
, typename _Tp
, typename _Compare
>
2191 _RandomAccessIterator
2192 __unguarded_partition(_RandomAccessIterator __first
,
2193 _RandomAccessIterator __last
,
2194 _Tp __pivot
, _Compare __comp
)
2198 while (__comp(*__first
, __pivot
))
2201 while (__comp(__pivot
, *__last
))
2203 if (!(__first
< __last
))
2205 std::iter_swap(__first
, __last
);
2213 * This controls some aspect of the sort routines.
2216 enum { _S_threshold
= 16 };
2220 * This is a helper function for the sort routine.
2223 template<typename _RandomAccessIterator
, typename _Tp
>
2225 __unguarded_linear_insert(_RandomAccessIterator __last
, _Tp __val
)
2227 _RandomAccessIterator __next
= __last
;
2229 while (__val
< *__next
)
2240 * This is a helper function for the sort routine.
2243 template<typename _RandomAccessIterator
, typename _Tp
, typename _Compare
>
2245 __unguarded_linear_insert(_RandomAccessIterator __last
, _Tp __val
,
2248 _RandomAccessIterator __next
= __last
;
2250 while (__comp(__val
, *__next
))
2261 * This is a helper function for the sort routine.
2264 template<typename _RandomAccessIterator
>
2266 __insertion_sort(_RandomAccessIterator __first
,
2267 _RandomAccessIterator __last
)
2269 if (__first
== __last
)
2272 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2274 typename iterator_traits
<_RandomAccessIterator
>::value_type
2276 if (__val
< *__first
)
2278 std::copy_backward(__first
, __i
, __i
+ 1);
2282 std::__unguarded_linear_insert(__i
, __val
);
2288 * This is a helper function for the sort routine.
2291 template<typename _RandomAccessIterator
, typename _Compare
>
2293 __insertion_sort(_RandomAccessIterator __first
,
2294 _RandomAccessIterator __last
, _Compare __comp
)
2296 if (__first
== __last
) return;
2298 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2300 typename iterator_traits
<_RandomAccessIterator
>::value_type
2302 if (__comp(__val
, *__first
))
2304 std::copy_backward(__first
, __i
, __i
+ 1);
2308 std::__unguarded_linear_insert(__i
, __val
, __comp
);
2314 * This is a helper function for the sort routine.
2317 template<typename _RandomAccessIterator
>
2319 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2320 _RandomAccessIterator __last
)
2322 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2325 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2326 std::__unguarded_linear_insert(__i
, _ValueType(*__i
));
2331 * This is a helper function for the sort routine.
2334 template<typename _RandomAccessIterator
, typename _Compare
>
2336 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2337 _RandomAccessIterator __last
, _Compare __comp
)
2339 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2342 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2343 std::__unguarded_linear_insert(__i
, _ValueType(*__i
), __comp
);
2348 * This is a helper function for the sort routine.
2351 template<typename _RandomAccessIterator
>
2353 __final_insertion_sort(_RandomAccessIterator __first
,
2354 _RandomAccessIterator __last
)
2356 if (__last
- __first
> int(_S_threshold
))
2358 std::__insertion_sort(__first
, __first
+ int(_S_threshold
));
2359 std::__unguarded_insertion_sort(__first
+ int(_S_threshold
), __last
);
2362 std::__insertion_sort(__first
, __last
);
2367 * This is a helper function for the sort routine.
2370 template<typename _RandomAccessIterator
, typename _Compare
>
2372 __final_insertion_sort(_RandomAccessIterator __first
,
2373 _RandomAccessIterator __last
, _Compare __comp
)
2375 if (__last
- __first
> int(_S_threshold
))
2377 std::__insertion_sort(__first
, __first
+ int(_S_threshold
), __comp
);
2378 std::__unguarded_insertion_sort(__first
+ int(_S_threshold
), __last
,
2382 std::__insertion_sort(__first
, __last
, __comp
);
2387 * This is a helper function for the sort routine.
2390 template<typename _Size
>
2395 for (__k
= 0; __n
!= 1; __n
>>= 1)
2401 * @brief Sort the smallest elements of a sequence.
2402 * @param first An iterator.
2403 * @param middle Another iterator.
2404 * @param last Another iterator.
2407 * Sorts the smallest @p (middle-first) elements in the range
2408 * @p [first,last) and moves them to the range @p [first,middle). The
2409 * order of the remaining elements in the range @p [middle,last) is
2411 * After the sort if @p i and @j are iterators in the range
2412 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2413 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2415 template<typename _RandomAccessIterator
>
2417 partial_sort(_RandomAccessIterator __first
,
2418 _RandomAccessIterator __middle
,
2419 _RandomAccessIterator __last
)
2421 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2424 // concept requirements
2425 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2426 _RandomAccessIterator
>)
2427 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
2428 __glibcxx_requires_valid_range(__first
, __middle
);
2429 __glibcxx_requires_valid_range(__middle
, __last
);
2431 std::make_heap(__first
, __middle
);
2432 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
2433 if (*__i
< *__first
)
2434 std::__pop_heap(__first
, __middle
, __i
, _ValueType(*__i
));
2435 std::sort_heap(__first
, __middle
);
2439 * @brief Sort the smallest elements of a sequence using a predicate
2441 * @param first An iterator.
2442 * @param middle Another iterator.
2443 * @param last Another iterator.
2444 * @param comp A comparison functor.
2447 * Sorts the smallest @p (middle-first) elements in the range
2448 * @p [first,last) and moves them to the range @p [first,middle). The
2449 * order of the remaining elements in the range @p [middle,last) is
2451 * After the sort if @p i and @j are iterators in the range
2452 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2453 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2456 template<typename _RandomAccessIterator
, typename _Compare
>
2458 partial_sort(_RandomAccessIterator __first
,
2459 _RandomAccessIterator __middle
,
2460 _RandomAccessIterator __last
,
2463 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2466 // concept requirements
2467 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2468 _RandomAccessIterator
>)
2469 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2470 _ValueType
, _ValueType
>)
2471 __glibcxx_requires_valid_range(__first
, __middle
);
2472 __glibcxx_requires_valid_range(__middle
, __last
);
2474 std::make_heap(__first
, __middle
, __comp
);
2475 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
2476 if (__comp(*__i
, *__first
))
2477 std::__pop_heap(__first
, __middle
, __i
, _ValueType(*__i
), __comp
);
2478 std::sort_heap(__first
, __middle
, __comp
);
2482 * @brief Copy the smallest elements of a sequence.
2483 * @param first An iterator.
2484 * @param last Another iterator.
2485 * @param result_first A random-access iterator.
2486 * @param result_last Another random-access iterator.
2487 * @return An iterator indicating the end of the resulting sequence.
2489 * Copies and sorts the smallest N values from the range @p [first,last)
2490 * to the range beginning at @p result_first, where the number of
2491 * elements to be copied, @p N, is the smaller of @p (last-first) and
2492 * @p (result_last-result_first).
2493 * After the sort if @p i and @j are iterators in the range
2494 * @p [result_first,result_first+N) such that @i precedes @j then
2495 * @p *j<*i is false.
2496 * The value returned is @p result_first+N.
2498 template<typename _InputIterator
, typename _RandomAccessIterator
>
2499 _RandomAccessIterator
2500 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2501 _RandomAccessIterator __result_first
,
2502 _RandomAccessIterator __result_last
)
2504 typedef typename iterator_traits
<_InputIterator
>::value_type
2506 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2508 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2511 // concept requirements
2512 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2513 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2515 __glibcxx_function_requires(_LessThanOpConcept
<_InputValueType
,
2517 __glibcxx_function_requires(_LessThanComparableConcept
<_OutputValueType
>)
2518 __glibcxx_requires_valid_range(__first
, __last
);
2519 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2521 if (__result_first
== __result_last
)
2522 return __result_last
;
2523 _RandomAccessIterator __result_real_last
= __result_first
;
2524 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2526 *__result_real_last
= *__first
;
2527 ++__result_real_last
;
2530 std::make_heap(__result_first
, __result_real_last
);
2531 while (__first
!= __last
)
2533 if (*__first
< *__result_first
)
2534 std::__adjust_heap(__result_first
, _DistanceType(0),
2535 _DistanceType(__result_real_last
2537 _InputValueType(*__first
));
2540 std::sort_heap(__result_first
, __result_real_last
);
2541 return __result_real_last
;
2545 * @brief Copy the smallest elements of a sequence using a predicate for
2547 * @param first An input iterator.
2548 * @param last Another input iterator.
2549 * @param result_first A random-access iterator.
2550 * @param result_last Another random-access iterator.
2551 * @param comp A comparison functor.
2552 * @return An iterator indicating the end of the resulting sequence.
2554 * Copies and sorts the smallest N values from the range @p [first,last)
2555 * to the range beginning at @p result_first, where the number of
2556 * elements to be copied, @p N, is the smaller of @p (last-first) and
2557 * @p (result_last-result_first).
2558 * After the sort if @p i and @j are iterators in the range
2559 * @p [result_first,result_first+N) such that @i precedes @j then
2560 * @p comp(*j,*i) is false.
2561 * The value returned is @p result_first+N.
2563 template<typename _InputIterator
, typename _RandomAccessIterator
, typename _Compare
>
2564 _RandomAccessIterator
2565 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2566 _RandomAccessIterator __result_first
,
2567 _RandomAccessIterator __result_last
,
2570 typedef typename iterator_traits
<_InputIterator
>::value_type
2572 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2574 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2577 // concept requirements
2578 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2579 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2580 _RandomAccessIterator
>)
2581 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2583 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2584 _InputValueType
, _OutputValueType
>)
2585 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2586 _OutputValueType
, _OutputValueType
>)
2587 __glibcxx_requires_valid_range(__first
, __last
);
2588 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2590 if (__result_first
== __result_last
)
2591 return __result_last
;
2592 _RandomAccessIterator __result_real_last
= __result_first
;
2593 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2595 *__result_real_last
= *__first
;
2596 ++__result_real_last
;
2599 std::make_heap(__result_first
, __result_real_last
, __comp
);
2600 while (__first
!= __last
)
2602 if (__comp(*__first
, *__result_first
))
2603 std::__adjust_heap(__result_first
, _DistanceType(0),
2604 _DistanceType(__result_real_last
2606 _InputValueType(*__first
),
2610 std::sort_heap(__result_first
, __result_real_last
, __comp
);
2611 return __result_real_last
;
2616 * This is a helper function for the sort routine.
2619 template<typename _RandomAccessIterator
, typename _Size
>
2621 __introsort_loop(_RandomAccessIterator __first
,
2622 _RandomAccessIterator __last
,
2623 _Size __depth_limit
)
2625 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2628 while (__last
- __first
> int(_S_threshold
))
2630 if (__depth_limit
== 0)
2632 std::partial_sort(__first
, __last
, __last
);
2636 _RandomAccessIterator __cut
=
2637 std::__unguarded_partition(__first
, __last
,
2638 _ValueType(std::__median(*__first
,
2645 std::__introsort_loop(__cut
, __last
, __depth_limit
);
2652 * This is a helper function for the sort routine.
2655 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
2657 __introsort_loop(_RandomAccessIterator __first
,
2658 _RandomAccessIterator __last
,
2659 _Size __depth_limit
, _Compare __comp
)
2661 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2664 while (__last
- __first
> int(_S_threshold
))
2666 if (__depth_limit
== 0)
2668 std::partial_sort(__first
, __last
, __last
, __comp
);
2672 _RandomAccessIterator __cut
=
2673 std::__unguarded_partition(__first
, __last
,
2674 _ValueType(std::__median(*__first
,
2682 std::__introsort_loop(__cut
, __last
, __depth_limit
, __comp
);
2688 * @brief Sort the elements of a sequence.
2689 * @param first An iterator.
2690 * @param last Another iterator.
2693 * Sorts the elements in the range @p [first,last) in ascending order,
2694 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2695 * @p [first,last-1).
2697 * The relative ordering of equivalent elements is not preserved, use
2698 * @p stable_sort() if this is needed.
2700 template<typename _RandomAccessIterator
>
2702 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
2704 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2707 // concept requirements
2708 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2709 _RandomAccessIterator
>)
2710 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
2711 __glibcxx_requires_valid_range(__first
, __last
);
2713 if (__first
!= __last
)
2715 std::__introsort_loop(__first
, __last
, __lg(__last
- __first
) * 2);
2716 std::__final_insertion_sort(__first
, __last
);
2721 * @brief Sort the elements of a sequence using a predicate for comparison.
2722 * @param first An iterator.
2723 * @param last Another iterator.
2724 * @param comp A comparison functor.
2727 * Sorts the elements in the range @p [first,last) in ascending order,
2728 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2729 * range @p [first,last-1).
2731 * The relative ordering of equivalent elements is not preserved, use
2732 * @p stable_sort() if this is needed.
2734 template<typename _RandomAccessIterator
, typename _Compare
>
2736 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
2739 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2742 // concept requirements
2743 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2744 _RandomAccessIterator
>)
2745 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
, _ValueType
,
2747 __glibcxx_requires_valid_range(__first
, __last
);
2749 if (__first
!= __last
)
2751 std::__introsort_loop(__first
, __last
, __lg(__last
- __first
) * 2,
2753 std::__final_insertion_sort(__first
, __last
, __comp
);
2758 * @brief Finds the first position in which @a val could be inserted
2759 * without changing the ordering.
2760 * @param first An iterator.
2761 * @param last Another iterator.
2762 * @param val The search term.
2763 * @return An iterator pointing to the first element "not less than" @a val,
2764 * or end() if every element is less than @a val.
2765 * @ingroup binarysearch
2767 template<typename _ForwardIterator
, typename _Tp
>
2769 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2772 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2774 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2777 // concept requirements
2778 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2779 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType
, _Tp
>)
2780 __glibcxx_requires_partitioned(__first
, __last
, __val
);
2782 _DistanceType __len
= std::distance(__first
, __last
);
2783 _DistanceType __half
;
2784 _ForwardIterator __middle
;
2788 __half
= __len
>> 1;
2790 std::advance(__middle
, __half
);
2791 if (*__middle
< __val
)
2795 __len
= __len
- __half
- 1;
2804 * @brief Finds the first position in which @a val could be inserted
2805 * without changing the ordering.
2806 * @param first An iterator.
2807 * @param last Another iterator.
2808 * @param val The search term.
2809 * @param comp A functor to use for comparisons.
2810 * @return An iterator pointing to the first element "not less than" @a val,
2811 * or end() if every element is less than @a val.
2812 * @ingroup binarysearch
2814 * The comparison function should have the same effects on ordering as
2815 * the function used for the initial sort.
2817 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2819 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2820 const _Tp
& __val
, _Compare __comp
)
2822 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2824 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2827 // concept requirements
2828 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2829 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2831 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
2833 _DistanceType __len
= std::distance(__first
, __last
);
2834 _DistanceType __half
;
2835 _ForwardIterator __middle
;
2839 __half
= __len
>> 1;
2841 std::advance(__middle
, __half
);
2842 if (__comp(*__middle
, __val
))
2846 __len
= __len
- __half
- 1;
2855 * @brief Finds the last position in which @a val could be inserted
2856 * without changing the ordering.
2857 * @param first An iterator.
2858 * @param last Another iterator.
2859 * @param val The search term.
2860 * @return An iterator pointing to the first element greater than @a val,
2861 * or end() if no elements are greater than @a val.
2862 * @ingroup binarysearch
2864 template<typename _ForwardIterator
, typename _Tp
>
2866 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2869 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2871 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2874 // concept requirements
2875 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2876 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
2877 __glibcxx_requires_partitioned(__first
, __last
, __val
);
2879 _DistanceType __len
= std::distance(__first
, __last
);
2880 _DistanceType __half
;
2881 _ForwardIterator __middle
;
2885 __half
= __len
>> 1;
2887 std::advance(__middle
, __half
);
2888 if (__val
< *__middle
)
2894 __len
= __len
- __half
- 1;
2901 * @brief Finds the last position in which @a val could be inserted
2902 * without changing the ordering.
2903 * @param first An iterator.
2904 * @param last Another iterator.
2905 * @param val The search term.
2906 * @param comp A functor to use for comparisons.
2907 * @return An iterator pointing to the first element greater than @a val,
2908 * or end() if no elements are greater than @a val.
2909 * @ingroup binarysearch
2911 * The comparison function should have the same effects on ordering as
2912 * the function used for the initial sort.
2914 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2916 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2917 const _Tp
& __val
, _Compare __comp
)
2919 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2921 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2924 // concept requirements
2925 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2926 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2928 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
2930 _DistanceType __len
= std::distance(__first
, __last
);
2931 _DistanceType __half
;
2932 _ForwardIterator __middle
;
2936 __half
= __len
>> 1;
2938 std::advance(__middle
, __half
);
2939 if (__comp(__val
, *__middle
))
2945 __len
= __len
- __half
- 1;
2953 * This is a helper function for the merge routines.
2956 template<typename _BidirectionalIterator
, typename _Distance
>
2958 __merge_without_buffer(_BidirectionalIterator __first
,
2959 _BidirectionalIterator __middle
,
2960 _BidirectionalIterator __last
,
2961 _Distance __len1
, _Distance __len2
)
2963 if (__len1
== 0 || __len2
== 0)
2965 if (__len1
+ __len2
== 2)
2967 if (*__middle
< *__first
)
2968 std::iter_swap(__first
, __middle
);
2971 _BidirectionalIterator __first_cut
= __first
;
2972 _BidirectionalIterator __second_cut
= __middle
;
2973 _Distance __len11
= 0;
2974 _Distance __len22
= 0;
2975 if (__len1
> __len2
)
2977 __len11
= __len1
/ 2;
2978 std::advance(__first_cut
, __len11
);
2979 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
);
2980 __len22
= std::distance(__middle
, __second_cut
);
2984 __len22
= __len2
/ 2;
2985 std::advance(__second_cut
, __len22
);
2986 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
);
2987 __len11
= std::distance(__first
, __first_cut
);
2989 std::rotate(__first_cut
, __middle
, __second_cut
);
2990 _BidirectionalIterator __new_middle
= __first_cut
;
2991 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
2992 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
2994 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
2995 __len1
- __len11
, __len2
- __len22
);
3000 * This is a helper function for the merge routines.
3003 template<typename _BidirectionalIterator
, typename _Distance
,
3006 __merge_without_buffer(_BidirectionalIterator __first
,
3007 _BidirectionalIterator __middle
,
3008 _BidirectionalIterator __last
,
3009 _Distance __len1
, _Distance __len2
,
3012 if (__len1
== 0 || __len2
== 0)
3014 if (__len1
+ __len2
== 2)
3016 if (__comp(*__middle
, *__first
))
3017 std::iter_swap(__first
, __middle
);
3020 _BidirectionalIterator __first_cut
= __first
;
3021 _BidirectionalIterator __second_cut
= __middle
;
3022 _Distance __len11
= 0;
3023 _Distance __len22
= 0;
3024 if (__len1
> __len2
)
3026 __len11
= __len1
/ 2;
3027 std::advance(__first_cut
, __len11
);
3028 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
3030 __len22
= std::distance(__middle
, __second_cut
);
3034 __len22
= __len2
/ 2;
3035 std::advance(__second_cut
, __len22
);
3036 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
3038 __len11
= std::distance(__first
, __first_cut
);
3040 std::rotate(__first_cut
, __middle
, __second_cut
);
3041 _BidirectionalIterator __new_middle
= __first_cut
;
3042 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
3043 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
3044 __len11
, __len22
, __comp
);
3045 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
3046 __len1
- __len11
, __len2
- __len22
, __comp
);
3051 * This is a helper function for the stable sorting routines.
3054 template<typename _RandomAccessIterator
>
3056 __inplace_stable_sort(_RandomAccessIterator __first
,
3057 _RandomAccessIterator __last
)
3059 if (__last
- __first
< 15)
3061 std::__insertion_sort(__first
, __last
);
3064 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
3065 std::__inplace_stable_sort(__first
, __middle
);
3066 std::__inplace_stable_sort(__middle
, __last
);
3067 std::__merge_without_buffer(__first
, __middle
, __last
,
3074 * This is a helper function for the stable sorting routines.
3077 template<typename _RandomAccessIterator
, typename _Compare
>
3079 __inplace_stable_sort(_RandomAccessIterator __first
,
3080 _RandomAccessIterator __last
, _Compare __comp
)
3082 if (__last
- __first
< 15)
3084 std::__insertion_sort(__first
, __last
, __comp
);
3087 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
3088 std::__inplace_stable_sort(__first
, __middle
, __comp
);
3089 std::__inplace_stable_sort(__middle
, __last
, __comp
);
3090 std::__merge_without_buffer(__first
, __middle
, __last
,
3097 * @brief Merges two sorted ranges.
3098 * @param first1 An iterator.
3099 * @param first2 Another iterator.
3100 * @param last1 Another iterator.
3101 * @param last2 Another iterator.
3102 * @param result An iterator pointing to the end of the merged range.
3103 * @return An iterator pointing to the first element "not less than" @a val.
3105 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3106 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3107 * must be sorted, and the output range must not overlap with either of
3108 * the input ranges. The sort is @e stable, that is, for equivalent
3109 * elements in the two ranges, elements from the first range will always
3110 * come before elements from the second.
3112 template<typename _InputIterator1
, typename _InputIterator2
,
3113 typename _OutputIterator
>
3115 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
3116 _InputIterator2 __first2
, _InputIterator2 __last2
,
3117 _OutputIterator __result
)
3119 typedef typename iterator_traits
<_InputIterator1
>::value_type
3121 typedef typename iterator_traits
<_InputIterator2
>::value_type
3124 // concept requirements
3125 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3126 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3127 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3129 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3131 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
3132 __glibcxx_requires_sorted(__first1
, __last1
);
3133 __glibcxx_requires_sorted(__first2
, __last2
);
3135 while (__first1
!= __last1
&& __first2
!= __last2
)
3137 if (*__first2
< *__first1
)
3139 *__result
= *__first2
;
3144 *__result
= *__first1
;
3149 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
3154 * @brief Merges two sorted ranges.
3155 * @param first1 An iterator.
3156 * @param first2 Another iterator.
3157 * @param last1 Another iterator.
3158 * @param last2 Another iterator.
3159 * @param result An iterator pointing to the end of the merged range.
3160 * @param comp A functor to use for comparisons.
3161 * @return An iterator pointing to the first element "not less than" @a val.
3163 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3164 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3165 * must be sorted, and the output range must not overlap with either of
3166 * the input ranges. The sort is @e stable, that is, for equivalent
3167 * elements in the two ranges, elements from the first range will always
3168 * come before elements from the second.
3170 * The comparison function should have the same effects on ordering as
3171 * the function used for the initial sort.
3173 template<typename _InputIterator1
, typename _InputIterator2
,
3174 typename _OutputIterator
, typename _Compare
>
3176 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
3177 _InputIterator2 __first2
, _InputIterator2 __last2
,
3178 _OutputIterator __result
, _Compare __comp
)
3180 typedef typename iterator_traits
<_InputIterator1
>::value_type
3182 typedef typename iterator_traits
<_InputIterator2
>::value_type
3185 // concept requirements
3186 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3187 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3188 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3190 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3192 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3193 _ValueType2
, _ValueType1
>)
3194 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
3195 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
3197 while (__first1
!= __last1
&& __first2
!= __last2
)
3199 if (__comp(*__first2
, *__first1
))
3201 *__result
= *__first2
;
3206 *__result
= *__first1
;
3211 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
3215 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3218 __merge_sort_loop(_RandomAccessIterator1 __first
,
3219 _RandomAccessIterator1 __last
,
3220 _RandomAccessIterator2 __result
,
3221 _Distance __step_size
)
3223 const _Distance __two_step
= 2 * __step_size
;
3225 while (__last
- __first
>= __two_step
)
3227 __result
= std::merge(__first
, __first
+ __step_size
,
3228 __first
+ __step_size
, __first
+ __two_step
,
3230 __first
+= __two_step
;
3233 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3234 std::merge(__first
, __first
+ __step_size
, __first
+ __step_size
, __last
,
3238 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3239 typename _Distance
, typename _Compare
>
3241 __merge_sort_loop(_RandomAccessIterator1 __first
,
3242 _RandomAccessIterator1 __last
,
3243 _RandomAccessIterator2 __result
, _Distance __step_size
,
3246 const _Distance __two_step
= 2 * __step_size
;
3248 while (__last
- __first
>= __two_step
)
3250 __result
= std::merge(__first
, __first
+ __step_size
,
3251 __first
+ __step_size
, __first
+ __two_step
,
3254 __first
+= __two_step
;
3256 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3258 std::merge(__first
, __first
+ __step_size
,
3259 __first
+ __step_size
, __last
,
3264 enum { _S_chunk_size
= 7 };
3266 template<typename _RandomAccessIterator
, typename _Distance
>
3268 __chunk_insertion_sort(_RandomAccessIterator __first
,
3269 _RandomAccessIterator __last
,
3270 _Distance __chunk_size
)
3272 while (__last
- __first
>= __chunk_size
)
3274 std::__insertion_sort(__first
, __first
+ __chunk_size
);
3275 __first
+= __chunk_size
;
3277 std::__insertion_sort(__first
, __last
);
3280 template<typename _RandomAccessIterator
, typename _Distance
, typename _Compare
>
3282 __chunk_insertion_sort(_RandomAccessIterator __first
,
3283 _RandomAccessIterator __last
,
3284 _Distance __chunk_size
, _Compare __comp
)
3286 while (__last
- __first
>= __chunk_size
)
3288 std::__insertion_sort(__first
, __first
+ __chunk_size
, __comp
);
3289 __first
+= __chunk_size
;
3291 std::__insertion_sort(__first
, __last
, __comp
);
3294 template<typename _RandomAccessIterator
, typename _Pointer
>
3296 __merge_sort_with_buffer(_RandomAccessIterator __first
,
3297 _RandomAccessIterator __last
,
3300 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3303 const _Distance __len
= __last
- __first
;
3304 const _Pointer __buffer_last
= __buffer
+ __len
;
3306 _Distance __step_size
= _S_chunk_size
;
3307 std::__chunk_insertion_sort(__first
, __last
, __step_size
);
3309 while (__step_size
< __len
)
3311 std::__merge_sort_loop(__first
, __last
, __buffer
, __step_size
);
3313 std::__merge_sort_loop(__buffer
, __buffer_last
, __first
, __step_size
);
3318 template<typename _RandomAccessIterator
, typename _Pointer
, typename _Compare
>
3320 __merge_sort_with_buffer(_RandomAccessIterator __first
,
3321 _RandomAccessIterator __last
,
3322 _Pointer __buffer
, _Compare __comp
)
3324 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3327 const _Distance __len
= __last
- __first
;
3328 const _Pointer __buffer_last
= __buffer
+ __len
;
3330 _Distance __step_size
= _S_chunk_size
;
3331 std::__chunk_insertion_sort(__first
, __last
, __step_size
, __comp
);
3333 while (__step_size
< __len
)
3335 std::__merge_sort_loop(__first
, __last
, __buffer
,
3336 __step_size
, __comp
);
3338 std::__merge_sort_loop(__buffer
, __buffer_last
, __first
,
3339 __step_size
, __comp
);
3346 * This is a helper function for the merge routines.
3349 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3350 typename _BidirectionalIterator3
>
3351 _BidirectionalIterator3
3352 __merge_backward(_BidirectionalIterator1 __first1
,
3353 _BidirectionalIterator1 __last1
,
3354 _BidirectionalIterator2 __first2
,
3355 _BidirectionalIterator2 __last2
,
3356 _BidirectionalIterator3 __result
)
3358 if (__first1
== __last1
)
3359 return std::copy_backward(__first2
, __last2
, __result
);
3360 if (__first2
== __last2
)
3361 return std::copy_backward(__first1
, __last1
, __result
);
3366 if (*__last2
< *__last1
)
3368 *--__result
= *__last1
;
3369 if (__first1
== __last1
)
3370 return std::copy_backward(__first2
, ++__last2
, __result
);
3375 *--__result
= *__last2
;
3376 if (__first2
== __last2
)
3377 return std::copy_backward(__first1
, ++__last1
, __result
);
3385 * This is a helper function for the merge routines.
3388 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3389 typename _BidirectionalIterator3
, typename _Compare
>
3390 _BidirectionalIterator3
3391 __merge_backward(_BidirectionalIterator1 __first1
,
3392 _BidirectionalIterator1 __last1
,
3393 _BidirectionalIterator2 __first2
,
3394 _BidirectionalIterator2 __last2
,
3395 _BidirectionalIterator3 __result
,
3398 if (__first1
== __last1
)
3399 return std::copy_backward(__first2
, __last2
, __result
);
3400 if (__first2
== __last2
)
3401 return std::copy_backward(__first1
, __last1
, __result
);
3406 if (__comp(*__last2
, *__last1
))
3408 *--__result
= *__last1
;
3409 if (__first1
== __last1
)
3410 return std::copy_backward(__first2
, ++__last2
, __result
);
3415 *--__result
= *__last2
;
3416 if (__first2
== __last2
)
3417 return std::copy_backward(__first1
, ++__last1
, __result
);
3425 * This is a helper function for the merge routines.
3428 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3430 _BidirectionalIterator1
3431 __rotate_adaptive(_BidirectionalIterator1 __first
,
3432 _BidirectionalIterator1 __middle
,
3433 _BidirectionalIterator1 __last
,
3434 _Distance __len1
, _Distance __len2
,
3435 _BidirectionalIterator2 __buffer
,
3436 _Distance __buffer_size
)
3438 _BidirectionalIterator2 __buffer_end
;
3439 if (__len1
> __len2
&& __len2
<= __buffer_size
)
3441 __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3442 std::copy_backward(__first
, __middle
, __last
);
3443 return std::copy(__buffer
, __buffer_end
, __first
);
3445 else if (__len1
<= __buffer_size
)
3447 __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3448 std::copy(__middle
, __last
, __first
);
3449 return std::copy_backward(__buffer
, __buffer_end
, __last
);
3453 std::rotate(__first
, __middle
, __last
);
3454 std::advance(__first
, std::distance(__middle
, __last
));
3461 * This is a helper function for the merge routines.
3464 template<typename _BidirectionalIterator
, typename _Distance
,
3467 __merge_adaptive(_BidirectionalIterator __first
,
3468 _BidirectionalIterator __middle
,
3469 _BidirectionalIterator __last
,
3470 _Distance __len1
, _Distance __len2
,
3471 _Pointer __buffer
, _Distance __buffer_size
)
3473 if (__len1
<= __len2
&& __len1
<= __buffer_size
)
3475 _Pointer __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3476 std::merge(__buffer
, __buffer_end
, __middle
, __last
, __first
);
3478 else if (__len2
<= __buffer_size
)
3480 _Pointer __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3481 std::__merge_backward(__first
, __middle
, __buffer
,
3482 __buffer_end
, __last
);
3486 _BidirectionalIterator __first_cut
= __first
;
3487 _BidirectionalIterator __second_cut
= __middle
;
3488 _Distance __len11
= 0;
3489 _Distance __len22
= 0;
3490 if (__len1
> __len2
)
3492 __len11
= __len1
/ 2;
3493 std::advance(__first_cut
, __len11
);
3494 __second_cut
= std::lower_bound(__middle
, __last
,
3496 __len22
= std::distance(__middle
, __second_cut
);
3500 __len22
= __len2
/ 2;
3501 std::advance(__second_cut
, __len22
);
3502 __first_cut
= std::upper_bound(__first
, __middle
,
3504 __len11
= std::distance(__first
, __first_cut
);
3506 _BidirectionalIterator __new_middle
=
3507 std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
3508 __len1
- __len11
, __len22
, __buffer
,
3510 std::__merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
3511 __len22
, __buffer
, __buffer_size
);
3512 std::__merge_adaptive(__new_middle
, __second_cut
, __last
,
3514 __len2
- __len22
, __buffer
, __buffer_size
);
3520 * This is a helper function for the merge routines.
3523 template<typename _BidirectionalIterator
, typename _Distance
, typename _Pointer
,
3526 __merge_adaptive(_BidirectionalIterator __first
,
3527 _BidirectionalIterator __middle
,
3528 _BidirectionalIterator __last
,
3529 _Distance __len1
, _Distance __len2
,
3530 _Pointer __buffer
, _Distance __buffer_size
,
3533 if (__len1
<= __len2
&& __len1
<= __buffer_size
)
3535 _Pointer __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3536 std::merge(__buffer
, __buffer_end
, __middle
, __last
, __first
, __comp
);
3538 else if (__len2
<= __buffer_size
)
3540 _Pointer __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3541 std::__merge_backward(__first
, __middle
, __buffer
, __buffer_end
,
3546 _BidirectionalIterator __first_cut
= __first
;
3547 _BidirectionalIterator __second_cut
= __middle
;
3548 _Distance __len11
= 0;
3549 _Distance __len22
= 0;
3550 if (__len1
> __len2
)
3552 __len11
= __len1
/ 2;
3553 std::advance(__first_cut
, __len11
);
3554 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
3556 __len22
= std::distance(__middle
, __second_cut
);
3560 __len22
= __len2
/ 2;
3561 std::advance(__second_cut
, __len22
);
3562 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
3564 __len11
= std::distance(__first
, __first_cut
);
3566 _BidirectionalIterator __new_middle
=
3567 std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
3568 __len1
- __len11
, __len22
, __buffer
,
3570 std::__merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
3571 __len22
, __buffer
, __buffer_size
, __comp
);
3572 std::__merge_adaptive(__new_middle
, __second_cut
, __last
,
3574 __len2
- __len22
, __buffer
,
3575 __buffer_size
, __comp
);
3580 * @brief Merges two sorted ranges in place.
3581 * @param first An iterator.
3582 * @param middle Another iterator.
3583 * @param last Another iterator.
3586 * Merges two sorted and consecutive ranges, [first,middle) and
3587 * [middle,last), and puts the result in [first,last). The output will
3588 * be sorted. The sort is @e stable, that is, for equivalent
3589 * elements in the two ranges, elements from the first range will always
3590 * come before elements from the second.
3592 * If enough additional memory is available, this takes (last-first)-1
3593 * comparisons. Otherwise an NlogN algorithm is used, where N is
3594 * distance(first,last).
3596 template<typename _BidirectionalIterator
>
3598 inplace_merge(_BidirectionalIterator __first
,
3599 _BidirectionalIterator __middle
,
3600 _BidirectionalIterator __last
)
3602 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3604 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3607 // concept requirements
3608 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3609 _BidirectionalIterator
>)
3610 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3611 __glibcxx_requires_sorted(__first
, __middle
);
3612 __glibcxx_requires_sorted(__middle
, __last
);
3614 if (__first
== __middle
|| __middle
== __last
)
3617 _DistanceType __len1
= std::distance(__first
, __middle
);
3618 _DistanceType __len2
= std::distance(__middle
, __last
);
3620 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3622 if (__buf
.begin() == 0)
3623 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
, __len2
);
3625 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3626 __buf
.begin(), _DistanceType(__buf
.size()));
3630 * @brief Merges two sorted ranges in place.
3631 * @param first An iterator.
3632 * @param middle Another iterator.
3633 * @param last Another iterator.
3634 * @param comp A functor to use for comparisons.
3637 * Merges two sorted and consecutive ranges, [first,middle) and
3638 * [middle,last), and puts the result in [first,last). The output will
3639 * be sorted. The sort is @e stable, that is, for equivalent
3640 * elements in the two ranges, elements from the first range will always
3641 * come before elements from the second.
3643 * If enough additional memory is available, this takes (last-first)-1
3644 * comparisons. Otherwise an NlogN algorithm is used, where N is
3645 * distance(first,last).
3647 * The comparison function should have the same effects on ordering as
3648 * the function used for the initial sort.
3650 template<typename _BidirectionalIterator
, typename _Compare
>
3652 inplace_merge(_BidirectionalIterator __first
,
3653 _BidirectionalIterator __middle
,
3654 _BidirectionalIterator __last
,
3657 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3659 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3662 // concept requirements
3663 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3664 _BidirectionalIterator
>)
3665 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3666 _ValueType
, _ValueType
>)
3667 __glibcxx_requires_sorted_pred(__first
, __middle
, __comp
);
3668 __glibcxx_requires_sorted_pred(__middle
, __last
, __comp
);
3670 if (__first
== __middle
|| __middle
== __last
)
3673 const _DistanceType __len1
= std::distance(__first
, __middle
);
3674 const _DistanceType __len2
= std::distance(__middle
, __last
);
3676 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3678 if (__buf
.begin() == 0)
3679 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
,
3682 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3683 __buf
.begin(), _DistanceType(__buf
.size()),
3687 template<typename _RandomAccessIterator
, typename _Pointer
,
3690 __stable_sort_adaptive(_RandomAccessIterator __first
,
3691 _RandomAccessIterator __last
,
3692 _Pointer __buffer
, _Distance __buffer_size
)
3694 const _Distance __len
= (__last
- __first
+ 1) / 2;
3695 const _RandomAccessIterator __middle
= __first
+ __len
;
3696 if (__len
> __buffer_size
)
3698 std::__stable_sort_adaptive(__first
, __middle
,
3699 __buffer
, __buffer_size
);
3700 std::__stable_sort_adaptive(__middle
, __last
,
3701 __buffer
, __buffer_size
);
3705 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
);
3706 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
);
3708 std::__merge_adaptive(__first
, __middle
, __last
,
3709 _Distance(__middle
- __first
),
3710 _Distance(__last
- __middle
),
3711 __buffer
, __buffer_size
);
3714 template<typename _RandomAccessIterator
, typename _Pointer
,
3715 typename _Distance
, typename _Compare
>
3717 __stable_sort_adaptive(_RandomAccessIterator __first
,
3718 _RandomAccessIterator __last
,
3719 _Pointer __buffer
, _Distance __buffer_size
,
3722 const _Distance __len
= (__last
- __first
+ 1) / 2;
3723 const _RandomAccessIterator __middle
= __first
+ __len
;
3724 if (__len
> __buffer_size
)
3726 std::__stable_sort_adaptive(__first
, __middle
, __buffer
,
3727 __buffer_size
, __comp
);
3728 std::__stable_sort_adaptive(__middle
, __last
, __buffer
,
3729 __buffer_size
, __comp
);
3733 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
, __comp
);
3734 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
, __comp
);
3736 std::__merge_adaptive(__first
, __middle
, __last
,
3737 _Distance(__middle
- __first
),
3738 _Distance(__last
- __middle
),
3739 __buffer
, __buffer_size
,
3744 * @brief Sort the elements of a sequence, preserving the relative order
3745 * of equivalent elements.
3746 * @param first An iterator.
3747 * @param last Another iterator.
3750 * Sorts the elements in the range @p [first,last) in ascending order,
3751 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3752 * @p [first,last-1).
3754 * The relative ordering of equivalent elements is preserved, so any two
3755 * elements @p x and @p y in the range @p [first,last) such that
3756 * @p x<y is false and @p y<x is false will have the same relative
3757 * ordering after calling @p stable_sort().
3759 template<typename _RandomAccessIterator
>
3761 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
3763 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3765 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3768 // concept requirements
3769 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3770 _RandomAccessIterator
>)
3771 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3772 __glibcxx_requires_valid_range(__first
, __last
);
3774 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
>
3775 buf(__first
, __last
);
3776 if (buf
.begin() == 0)
3777 std::__inplace_stable_sort(__first
, __last
);
3779 std::__stable_sort_adaptive(__first
, __last
, buf
.begin(),
3780 _DistanceType(buf
.size()));
3784 * @brief Sort the elements of a sequence using a predicate for comparison,
3785 * preserving the relative order of equivalent elements.
3786 * @param first An iterator.
3787 * @param last Another iterator.
3788 * @param comp A comparison functor.
3791 * Sorts the elements in the range @p [first,last) in ascending order,
3792 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3793 * range @p [first,last-1).
3795 * The relative ordering of equivalent elements is preserved, so any two
3796 * elements @p x and @p y in the range @p [first,last) such that
3797 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
3798 * relative ordering after calling @p stable_sort().
3800 template<typename _RandomAccessIterator
, typename _Compare
>
3802 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
3805 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3807 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3810 // concept requirements
3811 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3812 _RandomAccessIterator
>)
3813 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3816 __glibcxx_requires_valid_range(__first
, __last
);
3818 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
> buf(__first
, __last
);
3819 if (buf
.begin() == 0)
3820 std::__inplace_stable_sort(__first
, __last
, __comp
);
3822 std::__stable_sort_adaptive(__first
, __last
, buf
.begin(),
3823 _DistanceType(buf
.size()), __comp
);
3827 * @brief Sort a sequence just enough to find a particular position.
3828 * @param first An iterator.
3829 * @param nth Another iterator.
3830 * @param last Another iterator.
3833 * Rearranges the elements in the range @p [first,last) so that @p *nth
3834 * is the same element that would have been in that position had the
3835 * whole sequence been sorted.
3836 * whole sequence been sorted. The elements either side of @p *nth are
3837 * not completely sorted, but for any iterator @i in the range
3838 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3839 * holds that @p *j<*i is false.
3841 template<typename _RandomAccessIterator
>
3843 nth_element(_RandomAccessIterator __first
,
3844 _RandomAccessIterator __nth
,
3845 _RandomAccessIterator __last
)
3847 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3850 // concept requirements
3851 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3852 _RandomAccessIterator
>)
3853 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3854 __glibcxx_requires_valid_range(__first
, __nth
);
3855 __glibcxx_requires_valid_range(__nth
, __last
);
3857 while (__last
- __first
> 3)
3859 _RandomAccessIterator __cut
=
3860 std::__unguarded_partition(__first
, __last
,
3861 _ValueType(std::__median(*__first
,
3873 std::__insertion_sort(__first
, __last
);
3877 * @brief Sort a sequence just enough to find a particular position
3878 * using a predicate for comparison.
3879 * @param first An iterator.
3880 * @param nth Another iterator.
3881 * @param last Another iterator.
3882 * @param comp A comparison functor.
3885 * Rearranges the elements in the range @p [first,last) so that @p *nth
3886 * is the same element that would have been in that position had the
3887 * whole sequence been sorted. The elements either side of @p *nth are
3888 * not completely sorted, but for any iterator @i in the range
3889 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3890 * holds that @p comp(*j,*i) is false.
3892 template<typename _RandomAccessIterator
, typename _Compare
>
3894 nth_element(_RandomAccessIterator __first
,
3895 _RandomAccessIterator __nth
,
3896 _RandomAccessIterator __last
,
3899 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3902 // concept requirements
3903 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3904 _RandomAccessIterator
>)
3905 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3906 _ValueType
, _ValueType
>)
3907 __glibcxx_requires_valid_range(__first
, __nth
);
3908 __glibcxx_requires_valid_range(__nth
, __last
);
3910 while (__last
- __first
> 3)
3912 _RandomAccessIterator __cut
=
3913 std::__unguarded_partition(__first
, __last
,
3914 _ValueType(std::__median(*__first
,
3926 std::__insertion_sort(__first
, __last
, __comp
);
3930 * @brief Finds the largest subrange in which @a val could be inserted
3931 * at any place in it without changing the ordering.
3932 * @param first An iterator.
3933 * @param last Another iterator.
3934 * @param val The search term.
3935 * @return An pair of iterators defining the subrange.
3936 * @ingroup binarysearch
3938 * This is equivalent to
3940 * std::make_pair(lower_bound(first, last, val),
3941 * upper_bound(first, last, val))
3943 * but does not actually call those functions.
3945 template<typename _ForwardIterator
, typename _Tp
>
3946 pair
<_ForwardIterator
, _ForwardIterator
>
3947 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
3950 typedef typename iterator_traits
<_ForwardIterator
>::value_type
3952 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
3955 // concept requirements
3956 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3957 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType
, _Tp
>)
3958 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
3959 __glibcxx_requires_partitioned(__first
, __last
, __val
);
3961 _DistanceType __len
= std::distance(__first
, __last
);
3962 _DistanceType __half
;
3963 _ForwardIterator __middle
, __left
, __right
;
3967 __half
= __len
>> 1;
3969 std::advance(__middle
, __half
);
3970 if (*__middle
< __val
)
3974 __len
= __len
- __half
- 1;
3976 else if (__val
< *__middle
)
3980 __left
= std::lower_bound(__first
, __middle
, __val
);
3981 std::advance(__first
, __len
);
3982 __right
= std::upper_bound(++__middle
, __first
, __val
);
3983 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
3986 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
3990 * @brief Finds the largest subrange in which @a val could be inserted
3991 * at any place in it without changing the ordering.
3992 * @param first An iterator.
3993 * @param last Another iterator.
3994 * @param val The search term.
3995 * @param comp A functor to use for comparisons.
3996 * @return An pair of iterators defining the subrange.
3997 * @ingroup binarysearch
3999 * This is equivalent to
4001 * std::make_pair(lower_bound(first, last, val, comp),
4002 * upper_bound(first, last, val, comp))
4004 * but does not actually call those functions.
4006 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
4007 pair
<_ForwardIterator
, _ForwardIterator
>
4008 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
4012 typedef typename iterator_traits
<_ForwardIterator
>::value_type
4014 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
4017 // concept requirements
4018 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4019 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4021 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4023 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
4025 _DistanceType __len
= std::distance(__first
, __last
);
4026 _DistanceType __half
;
4027 _ForwardIterator __middle
, __left
, __right
;
4031 __half
= __len
>> 1;
4033 std::advance(__middle
, __half
);
4034 if (__comp(*__middle
, __val
))
4038 __len
= __len
- __half
- 1;
4040 else if (__comp(__val
, *__middle
))
4044 __left
= std::lower_bound(__first
, __middle
, __val
, __comp
);
4045 std::advance(__first
, __len
);
4046 __right
= std::upper_bound(++__middle
, __first
, __val
, __comp
);
4047 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
4050 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
4054 * @brief Determines whether an element exists in a range.
4055 * @param first An iterator.
4056 * @param last Another iterator.
4057 * @param val The search term.
4058 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4059 * @ingroup binarysearch
4061 * Note that this does not actually return an iterator to @a val. For
4062 * that, use std::find or a container's specialized find member functions.
4064 template<typename _ForwardIterator
, typename _Tp
>
4066 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
4069 typedef typename iterator_traits
<_ForwardIterator
>::value_type
4072 // concept requirements
4073 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4074 __glibcxx_function_requires(_LessThanOpConcept
<_Tp
, _ValueType
>)
4075 __glibcxx_requires_partitioned(__first
, __last
, __val
);
4077 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
);
4078 return __i
!= __last
&& !(__val
< *__i
);
4082 * @brief Determines whether an element exists in a range.
4083 * @param first An iterator.
4084 * @param last Another iterator.
4085 * @param val The search term.
4086 * @param comp A functor to use for comparisons.
4087 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4088 * @ingroup binarysearch
4090 * Note that this does not actually return an iterator to @a val. For
4091 * that, use std::find or a container's specialized find member functions.
4093 * The comparison function should have the same effects on ordering as
4094 * the function used for the initial sort.
4096 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
4098 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
4099 const _Tp
& __val
, _Compare __comp
)
4101 typedef typename iterator_traits
<_ForwardIterator
>::value_type
4104 // concept requirements
4105 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4106 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4108 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
4110 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
, __comp
);
4111 return __i
!= __last
&& !__comp(__val
, *__i
);
4114 // Set algorithms: includes, set_union, set_intersection, set_difference,
4115 // set_symmetric_difference. All of these algorithms have the precondition
4116 // that their input ranges are sorted and the postcondition that their output
4117 // ranges are sorted.
4120 * @brief Determines whether all elements of a sequence exists in a range.
4121 * @param first1 Start of search range.
4122 * @param last1 End of search range.
4123 * @param first2 Start of sequence
4124 * @param last2 End of sequence.
4125 * @return True if each element in [first2,last2) is contained in order
4126 * within [first1,last1). False otherwise.
4127 * @ingroup setoperations
4129 * This operation expects both [first1,last1) and [first2,last2) to be
4130 * sorted. Searches for the presence of each element in [first2,last2)
4131 * within [first1,last1). The iterators over each range only move forward,
4132 * so this is a linear algorithm. If an element in [first2,last2) is not
4133 * found before the search iterator reaches @a last2, false is returned.
4135 template<typename _InputIterator1
, typename _InputIterator2
>
4137 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
4138 _InputIterator2 __first2
, _InputIterator2 __last2
)
4140 typedef typename iterator_traits
<_InputIterator1
>::value_type
4142 typedef typename iterator_traits
<_InputIterator2
>::value_type
4145 // concept requirements
4146 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4147 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4148 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4149 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4150 __glibcxx_requires_sorted(__first1
, __last1
);
4151 __glibcxx_requires_sorted(__first2
, __last2
);
4153 while (__first1
!= __last1
&& __first2
!= __last2
)
4154 if (*__first2
< *__first1
)
4156 else if(*__first1
< *__first2
)
4159 ++__first1
, ++__first2
;
4161 return __first2
== __last2
;
4165 * @brief Determines whether all elements of a sequence exists in a range
4167 * @param first1 Start of search range.
4168 * @param last1 End of search range.
4169 * @param first2 Start of sequence
4170 * @param last2 End of sequence.
4171 * @param comp Comparison function to use.
4172 * @return True if each element in [first2,last2) is contained in order
4173 * within [first1,last1) according to comp. False otherwise.
4174 * @ingroup setoperations
4176 * This operation expects both [first1,last1) and [first2,last2) to be
4177 * sorted. Searches for the presence of each element in [first2,last2)
4178 * within [first1,last1), using comp to decide. The iterators over each
4179 * range only move forward, so this is a linear algorithm. If an element
4180 * in [first2,last2) is not found before the search iterator reaches @a
4181 * last2, false is returned.
4183 template<typename _InputIterator1
, typename _InputIterator2
,
4186 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
4187 _InputIterator2 __first2
, _InputIterator2 __last2
, _Compare __comp
)
4189 typedef typename iterator_traits
<_InputIterator1
>::value_type
4191 typedef typename iterator_traits
<_InputIterator2
>::value_type
4194 // concept requirements
4195 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4196 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4197 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4198 _ValueType1
, _ValueType2
>)
4199 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4200 _ValueType2
, _ValueType1
>)
4201 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4202 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4204 while (__first1
!= __last1
&& __first2
!= __last2
)
4205 if (__comp(*__first2
, *__first1
))
4207 else if(__comp(*__first1
, *__first2
))
4210 ++__first1
, ++__first2
;
4212 return __first2
== __last2
;
4216 * @brief Return the union of two sorted ranges.
4217 * @param first1 Start of first range.
4218 * @param last1 End of first range.
4219 * @param first2 Start of second range.
4220 * @param last2 End of second range.
4221 * @return End of the output range.
4222 * @ingroup setoperations
4224 * This operation iterates over both ranges, copying elements present in
4225 * each range in order to the output range. Iterators increment for each
4226 * range. When the current element of one range is less than the other,
4227 * that element is copied and the iterator advanced. If an element is
4228 * contained in both ranges, the element from the first range is copied and
4229 * both ranges advance. The output range may not overlap either input
4232 template<typename _InputIterator1
, typename _InputIterator2
,
4233 typename _OutputIterator
>
4235 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
4236 _InputIterator2 __first2
, _InputIterator2 __last2
,
4237 _OutputIterator __result
)
4239 typedef typename iterator_traits
<_InputIterator1
>::value_type
4241 typedef typename iterator_traits
<_InputIterator2
>::value_type
4244 // concept requirements
4245 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4246 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4247 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4249 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4251 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4252 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4253 __glibcxx_requires_sorted(__first1
, __last1
);
4254 __glibcxx_requires_sorted(__first2
, __last2
);
4256 while (__first1
!= __last1
&& __first2
!= __last2
)
4258 if (*__first1
< *__first2
)
4260 *__result
= *__first1
;
4263 else if (*__first2
< *__first1
)
4265 *__result
= *__first2
;
4270 *__result
= *__first1
;
4276 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
4281 * @brief Return the union of two sorted ranges using a comparison functor.
4282 * @param first1 Start of first range.
4283 * @param last1 End of first range.
4284 * @param first2 Start of second range.
4285 * @param last2 End of second range.
4286 * @param comp The comparison functor.
4287 * @return End of the output range.
4288 * @ingroup setoperations
4290 * This operation iterates over both ranges, copying elements present in
4291 * each range in order to the output range. Iterators increment for each
4292 * range. When the current element of one range is less than the other
4293 * according to @a comp, that element is copied and the iterator advanced.
4294 * If an equivalent element according to @a comp is contained in both
4295 * ranges, the element from the first range is copied and both ranges
4296 * advance. The output range may not overlap either input range.
4298 template<typename _InputIterator1
, typename _InputIterator2
,
4299 typename _OutputIterator
, typename _Compare
>
4301 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
4302 _InputIterator2 __first2
, _InputIterator2 __last2
,
4303 _OutputIterator __result
, _Compare __comp
)
4305 typedef typename iterator_traits
<_InputIterator1
>::value_type
4307 typedef typename iterator_traits
<_InputIterator2
>::value_type
4310 // concept requirements
4311 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4312 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4313 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4315 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4317 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4318 _ValueType1
, _ValueType2
>)
4319 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4320 _ValueType2
, _ValueType1
>)
4321 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4322 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4324 while (__first1
!= __last1
&& __first2
!= __last2
)
4326 if (__comp(*__first1
, *__first2
))
4328 *__result
= *__first1
;
4331 else if (__comp(*__first2
, *__first1
))
4333 *__result
= *__first2
;
4338 *__result
= *__first1
;
4344 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
4349 * @brief Return the intersection of two sorted ranges.
4350 * @param first1 Start of first range.
4351 * @param last1 End of first range.
4352 * @param first2 Start of second range.
4353 * @param last2 End of second range.
4354 * @return End of the output range.
4355 * @ingroup setoperations
4357 * This operation iterates over both ranges, copying elements present in
4358 * both ranges in order to the output range. Iterators increment for each
4359 * range. When the current element of one range is less than the other,
4360 * that iterator advances. If an element is contained in both ranges, the
4361 * element from the first range is copied and both ranges advance. The
4362 * output range may not overlap either input range.
4364 template<typename _InputIterator1
, typename _InputIterator2
,
4365 typename _OutputIterator
>
4367 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
4368 _InputIterator2 __first2
, _InputIterator2 __last2
,
4369 _OutputIterator __result
)
4371 typedef typename iterator_traits
<_InputIterator1
>::value_type
4373 typedef typename iterator_traits
<_InputIterator2
>::value_type
4376 // concept requirements
4377 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4378 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4379 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4381 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4382 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4383 __glibcxx_requires_sorted(__first1
, __last1
);
4384 __glibcxx_requires_sorted(__first2
, __last2
);
4386 while (__first1
!= __last1
&& __first2
!= __last2
)
4387 if (*__first1
< *__first2
)
4389 else if (*__first2
< *__first1
)
4393 *__result
= *__first1
;
4402 * @brief Return the intersection of two sorted ranges using comparison
4404 * @param first1 Start of first range.
4405 * @param last1 End of first range.
4406 * @param first2 Start of second range.
4407 * @param last2 End of second range.
4408 * @param comp The comparison functor.
4409 * @return End of the output range.
4410 * @ingroup setoperations
4412 * This operation iterates over both ranges, copying elements present in
4413 * both ranges in order to the output range. Iterators increment for each
4414 * range. When the current element of one range is less than the other
4415 * according to @a comp, that iterator advances. If an element is
4416 * contained in both ranges according to @a comp, the element from the
4417 * first range is copied and both ranges advance. The output range may not
4418 * overlap either input range.
4420 template<typename _InputIterator1
, typename _InputIterator2
,
4421 typename _OutputIterator
, typename _Compare
>
4423 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
4424 _InputIterator2 __first2
, _InputIterator2 __last2
,
4425 _OutputIterator __result
, _Compare __comp
)
4427 typedef typename iterator_traits
<_InputIterator1
>::value_type
4429 typedef typename iterator_traits
<_InputIterator2
>::value_type
4432 // concept requirements
4433 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4434 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4435 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4437 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4438 _ValueType1
, _ValueType2
>)
4439 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4440 _ValueType2
, _ValueType1
>)
4441 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4442 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4444 while (__first1
!= __last1
&& __first2
!= __last2
)
4445 if (__comp(*__first1
, *__first2
))
4447 else if (__comp(*__first2
, *__first1
))
4451 *__result
= *__first1
;
4460 * @brief Return the difference of two sorted ranges.
4461 * @param first1 Start of first range.
4462 * @param last1 End of first range.
4463 * @param first2 Start of second range.
4464 * @param last2 End of second range.
4465 * @return End of the output range.
4466 * @ingroup setoperations
4468 * This operation iterates over both ranges, copying elements present in
4469 * the first range but not the second in order to the output range.
4470 * Iterators increment for each range. When the current element of the
4471 * first range is less than the second, that element is copied and the
4472 * iterator advances. If the current element of the second range is less,
4473 * the iterator advances, but no element is copied. If an element is
4474 * contained in both ranges, no elements are copied and both ranges
4475 * advance. The output range may not overlap either input range.
4477 template<typename _InputIterator1
, typename _InputIterator2
,
4478 typename _OutputIterator
>
4480 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4481 _InputIterator2 __first2
, _InputIterator2 __last2
,
4482 _OutputIterator __result
)
4484 typedef typename iterator_traits
<_InputIterator1
>::value_type
4486 typedef typename iterator_traits
<_InputIterator2
>::value_type
4489 // concept requirements
4490 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4491 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4492 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4494 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4495 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4496 __glibcxx_requires_sorted(__first1
, __last1
);
4497 __glibcxx_requires_sorted(__first2
, __last2
);
4499 while (__first1
!= __last1
&& __first2
!= __last2
)
4500 if (*__first1
< *__first2
)
4502 *__result
= *__first1
;
4506 else if (*__first2
< *__first1
)
4513 return std::copy(__first1
, __last1
, __result
);
4517 * @brief Return the difference of two sorted ranges using comparison
4519 * @param first1 Start of first range.
4520 * @param last1 End of first range.
4521 * @param first2 Start of second range.
4522 * @param last2 End of second range.
4523 * @param comp The comparison functor.
4524 * @return End of the output range.
4525 * @ingroup setoperations
4527 * This operation iterates over both ranges, copying elements present in
4528 * the first range but not the second in order to the output range.
4529 * Iterators increment for each range. When the current element of the
4530 * first range is less than the second according to @a comp, that element
4531 * is copied and the iterator advances. If the current element of the
4532 * second range is less, no element is copied and the iterator advances.
4533 * If an element is contained in both ranges according to @a comp, no
4534 * elements are copied and both ranges advance. The output range may not
4535 * overlap either input range.
4537 template<typename _InputIterator1
, typename _InputIterator2
,
4538 typename _OutputIterator
, typename _Compare
>
4540 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4541 _InputIterator2 __first2
, _InputIterator2 __last2
,
4542 _OutputIterator __result
, _Compare __comp
)
4544 typedef typename iterator_traits
<_InputIterator1
>::value_type
4546 typedef typename iterator_traits
<_InputIterator2
>::value_type
4549 // concept requirements
4550 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4551 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4552 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4554 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4555 _ValueType1
, _ValueType2
>)
4556 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4557 _ValueType2
, _ValueType1
>)
4558 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4559 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4561 while (__first1
!= __last1
&& __first2
!= __last2
)
4562 if (__comp(*__first1
, *__first2
))
4564 *__result
= *__first1
;
4568 else if (__comp(*__first2
, *__first1
))
4575 return std::copy(__first1
, __last1
, __result
);
4579 * @brief Return the symmetric difference of two sorted ranges.
4580 * @param first1 Start of first range.
4581 * @param last1 End of first range.
4582 * @param first2 Start of second range.
4583 * @param last2 End of second range.
4584 * @return End of the output range.
4585 * @ingroup setoperations
4587 * This operation iterates over both ranges, copying elements present in
4588 * one range but not the other in order to the output range. Iterators
4589 * increment for each range. When the current element of one range is less
4590 * than the other, that element is copied and the iterator advances. If an
4591 * element is contained in both ranges, no elements are copied and both
4592 * ranges advance. The output range may not overlap either input range.
4594 template<typename _InputIterator1
, typename _InputIterator2
,
4595 typename _OutputIterator
>
4597 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4598 _InputIterator2 __first2
, _InputIterator2 __last2
,
4599 _OutputIterator __result
)
4601 typedef typename iterator_traits
<_InputIterator1
>::value_type
4603 typedef typename iterator_traits
<_InputIterator2
>::value_type
4606 // concept requirements
4607 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4608 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4609 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4611 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4613 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType1
, _ValueType2
>)
4614 __glibcxx_function_requires(_LessThanOpConcept
<_ValueType2
, _ValueType1
>)
4615 __glibcxx_requires_sorted(__first1
, __last1
);
4616 __glibcxx_requires_sorted(__first2
, __last2
);
4618 while (__first1
!= __last1
&& __first2
!= __last2
)
4619 if (*__first1
< *__first2
)
4621 *__result
= *__first1
;
4625 else if (*__first2
< *__first1
)
4627 *__result
= *__first2
;
4636 return std::copy(__first2
, __last2
, std::copy(__first1
,
4637 __last1
, __result
));
4641 * @brief Return the symmetric difference of two sorted ranges using
4642 * comparison functor.
4643 * @param first1 Start of first range.
4644 * @param last1 End of first range.
4645 * @param first2 Start of second range.
4646 * @param last2 End of second range.
4647 * @param comp The comparison functor.
4648 * @return End of the output range.
4649 * @ingroup setoperations
4651 * This operation iterates over both ranges, copying elements present in
4652 * one range but not the other in order to the output range. Iterators
4653 * increment for each range. When the current element of one range is less
4654 * than the other according to @a comp, that element is copied and the
4655 * iterator advances. If an element is contained in both ranges according
4656 * to @a comp, no elements are copied and both ranges advance. The output
4657 * range may not overlap either input range.
4659 template<typename _InputIterator1
, typename _InputIterator2
,
4660 typename _OutputIterator
, typename _Compare
>
4662 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4663 _InputIterator2 __first2
, _InputIterator2 __last2
,
4664 _OutputIterator __result
,
4667 typedef typename iterator_traits
<_InputIterator1
>::value_type
4669 typedef typename iterator_traits
<_InputIterator2
>::value_type
4672 // concept requirements
4673 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4674 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4675 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4677 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4679 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4680 _ValueType1
, _ValueType2
>)
4681 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4682 _ValueType2
, _ValueType1
>)
4683 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4684 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4686 while (__first1
!= __last1
&& __first2
!= __last2
)
4687 if (__comp(*__first1
, *__first2
))
4689 *__result
= *__first1
;
4693 else if (__comp(*__first2
, *__first1
))
4695 *__result
= *__first2
;
4704 return std::copy(__first2
, __last2
, std::copy(__first1
,
4705 __last1
, __result
));
4708 // min_element and max_element, with and without an explicitly supplied
4709 // comparison function.
4712 * @brief Return the maximum element in a range.
4713 * @param first Start of range.
4714 * @param last End of range.
4715 * @return Iterator referencing the first instance of the largest value.
4717 template<typename _ForwardIterator
>
4719 max_element(_ForwardIterator __first
, _ForwardIterator __last
)
4721 // concept requirements
4722 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4723 __glibcxx_function_requires(_LessThanComparableConcept
<
4724 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4725 __glibcxx_requires_valid_range(__first
, __last
);
4727 if (__first
== __last
)
4729 _ForwardIterator __result
= __first
;
4730 while (++__first
!= __last
)
4731 if (*__result
< *__first
)
4737 * @brief Return the maximum element in a range using comparison functor.
4738 * @param first Start of range.
4739 * @param last End of range.
4740 * @param comp Comparison functor.
4741 * @return Iterator referencing the first instance of the largest value
4742 * according to comp.
4744 template<typename _ForwardIterator
, typename _Compare
>
4746 max_element(_ForwardIterator __first
, _ForwardIterator __last
,
4749 // concept requirements
4750 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4751 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4752 typename iterator_traits
<_ForwardIterator
>::value_type
,
4753 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4754 __glibcxx_requires_valid_range(__first
, __last
);
4756 if (__first
== __last
) return __first
;
4757 _ForwardIterator __result
= __first
;
4758 while (++__first
!= __last
)
4759 if (__comp(*__result
, *__first
)) __result
= __first
;
4764 * @brief Return the minimum element in a range.
4765 * @param first Start of range.
4766 * @param last End of range.
4767 * @return Iterator referencing the first instance of the smallest value.
4769 template<typename _ForwardIterator
>
4771 min_element(_ForwardIterator __first
, _ForwardIterator __last
)
4773 // concept requirements
4774 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4775 __glibcxx_function_requires(_LessThanComparableConcept
<
4776 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4777 __glibcxx_requires_valid_range(__first
, __last
);
4779 if (__first
== __last
)
4781 _ForwardIterator __result
= __first
;
4782 while (++__first
!= __last
)
4783 if (*__first
< *__result
)
4789 * @brief Return the minimum element in a range using comparison functor.
4790 * @param first Start of range.
4791 * @param last End of range.
4792 * @param comp Comparison functor.
4793 * @return Iterator referencing the first instance of the smallest value
4794 * according to comp.
4796 template<typename _ForwardIterator
, typename _Compare
>
4798 min_element(_ForwardIterator __first
, _ForwardIterator __last
,
4801 // concept requirements
4802 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4803 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4804 typename iterator_traits
<_ForwardIterator
>::value_type
,
4805 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4806 __glibcxx_requires_valid_range(__first
, __last
);
4808 if (__first
== __last
)
4810 _ForwardIterator __result
= __first
;
4811 while (++__first
!= __last
)
4812 if (__comp(*__first
, *__result
))
4817 // next_permutation and prev_permutation, with and without an explicitly
4818 // supplied comparison function.
4821 * @brief Permute range into the next "dictionary" ordering.
4822 * @param first Start of range.
4823 * @param last End of range.
4824 * @return False if wrapped to first permutation, true otherwise.
4826 * Treats all permutations of the range as a set of "dictionary" sorted
4827 * sequences. Permutes the current sequence into the next one of this set.
4828 * Returns true if there are more sequences to generate. If the sequence
4829 * is the largest of the set, the smallest is generated and false returned.
4831 template<typename _BidirectionalIterator
>
4833 next_permutation(_BidirectionalIterator __first
,
4834 _BidirectionalIterator __last
)
4836 // concept requirements
4837 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
4838 _BidirectionalIterator
>)
4839 __glibcxx_function_requires(_LessThanComparableConcept
<
4840 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
4841 __glibcxx_requires_valid_range(__first
, __last
);
4843 if (__first
== __last
)
4845 _BidirectionalIterator __i
= __first
;
4854 _BidirectionalIterator __ii
= __i
;
4858 _BidirectionalIterator __j
= __last
;
4859 while (!(*__i
< *--__j
))
4861 std::iter_swap(__i
, __j
);
4862 std::reverse(__ii
, __last
);
4867 std::reverse(__first
, __last
);
4874 * @brief Permute range into the next "dictionary" ordering using
4875 * comparison functor.
4876 * @param first Start of range.
4877 * @param last End of range.
4879 * @return False if wrapped to first permutation, true otherwise.
4881 * Treats all permutations of the range [first,last) as a set of
4882 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4883 * sequence into the next one of this set. Returns true if there are more
4884 * sequences to generate. If the sequence is the largest of the set, the
4885 * smallest is generated and false returned.
4887 template<typename _BidirectionalIterator
, typename _Compare
>
4889 next_permutation(_BidirectionalIterator __first
,
4890 _BidirectionalIterator __last
, _Compare __comp
)
4892 // concept requirements
4893 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
4894 _BidirectionalIterator
>)
4895 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4896 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
4897 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
4898 __glibcxx_requires_valid_range(__first
, __last
);
4900 if (__first
== __last
)
4902 _BidirectionalIterator __i
= __first
;
4911 _BidirectionalIterator __ii
= __i
;
4913 if (__comp(*__i
, *__ii
))
4915 _BidirectionalIterator __j
= __last
;
4916 while (!__comp(*__i
, *--__j
))
4918 std::iter_swap(__i
, __j
);
4919 std::reverse(__ii
, __last
);
4924 std::reverse(__first
, __last
);
4931 * @brief Permute range into the previous "dictionary" ordering.
4932 * @param first Start of range.
4933 * @param last End of range.
4934 * @return False if wrapped to last permutation, true otherwise.
4936 * Treats all permutations of the range as a set of "dictionary" sorted
4937 * sequences. Permutes the current sequence into the previous one of this
4938 * set. Returns true if there are more sequences to generate. If the
4939 * sequence is the smallest of the set, the largest is generated and false
4942 template<typename _BidirectionalIterator
>
4944 prev_permutation(_BidirectionalIterator __first
,
4945 _BidirectionalIterator __last
)
4947 // concept requirements
4948 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
4949 _BidirectionalIterator
>)
4950 __glibcxx_function_requires(_LessThanComparableConcept
<
4951 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
4952 __glibcxx_requires_valid_range(__first
, __last
);
4954 if (__first
== __last
)
4956 _BidirectionalIterator __i
= __first
;
4965 _BidirectionalIterator __ii
= __i
;
4969 _BidirectionalIterator __j
= __last
;
4970 while (!(*--__j
< *__i
))
4972 std::iter_swap(__i
, __j
);
4973 std::reverse(__ii
, __last
);
4978 std::reverse(__first
, __last
);
4985 * @brief Permute range into the previous "dictionary" ordering using
4986 * comparison functor.
4987 * @param first Start of range.
4988 * @param last End of range.
4990 * @return False if wrapped to last permutation, true otherwise.
4992 * Treats all permutations of the range [first,last) as a set of
4993 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4994 * sequence into the previous one of this set. Returns true if there are
4995 * more sequences to generate. If the sequence is the smallest of the set,
4996 * the largest is generated and false returned.
4998 template<typename _BidirectionalIterator
, typename _Compare
>
5000 prev_permutation(_BidirectionalIterator __first
,
5001 _BidirectionalIterator __last
, _Compare __comp
)
5003 // concept requirements
5004 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5005 _BidirectionalIterator
>)
5006 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
5007 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
5008 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
5009 __glibcxx_requires_valid_range(__first
, __last
);
5011 if (__first
== __last
)
5013 _BidirectionalIterator __i
= __first
;
5022 _BidirectionalIterator __ii
= __i
;
5024 if (__comp(*__ii
, *__i
))
5026 _BidirectionalIterator __j
= __last
;
5027 while (!__comp(*--__j
, *__i
))
5029 std::iter_swap(__i
, __j
);
5030 std::reverse(__ii
, __last
);
5035 std::reverse(__first
, __last
);
5041 // find_first_of, with and without an explicitly supplied comparison function.
5044 * @brief Find element from a set in a sequence.
5045 * @param first1 Start of range to search.
5046 * @param last1 End of range to search.
5047 * @param first2 Start of match candidates.
5048 * @param last2 End of match candidates.
5049 * @return The first iterator @c i in the range
5050 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
5051 * interator in [first2,last2), or @p last1 if no such iterator exists.
5053 * Searches the range @p [first1,last1) for an element that is equal to
5054 * some element in the range [first2,last2). If found, returns an iterator
5055 * in the range [first1,last1), otherwise returns @p last1.
5057 template<typename _InputIterator
, typename _ForwardIterator
>
5059 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
5060 _ForwardIterator __first2
, _ForwardIterator __last2
)
5062 // concept requirements
5063 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
5064 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5065 __glibcxx_function_requires(_EqualOpConcept
<
5066 typename iterator_traits
<_InputIterator
>::value_type
,
5067 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5068 __glibcxx_requires_valid_range(__first1
, __last1
);
5069 __glibcxx_requires_valid_range(__first2
, __last2
);
5071 for ( ; __first1
!= __last1
; ++__first1
)
5072 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
5073 if (*__first1
== *__iter
)
5079 * @brief Find element from a set in a sequence using a predicate.
5080 * @param first1 Start of range to search.
5081 * @param last1 End of range to search.
5082 * @param first2 Start of match candidates.
5083 * @param last2 End of match candidates.
5084 * @param comp Predicate to use.
5085 * @return The first iterator @c i in the range
5086 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
5087 * interator in [first2,last2), or @p last1 if no such iterator exists.
5089 * Searches the range @p [first1,last1) for an element that is equal to
5090 * some element in the range [first2,last2). If found, returns an iterator in
5091 * the range [first1,last1), otherwise returns @p last1.
5093 template<typename _InputIterator
, typename _ForwardIterator
,
5094 typename _BinaryPredicate
>
5096 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
5097 _ForwardIterator __first2
, _ForwardIterator __last2
,
5098 _BinaryPredicate __comp
)
5100 // concept requirements
5101 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
5102 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
5103 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
5104 typename iterator_traits
<_InputIterator
>::value_type
,
5105 typename iterator_traits
<_ForwardIterator
>::value_type
>)
5106 __glibcxx_requires_valid_range(__first1
, __last1
);
5107 __glibcxx_requires_valid_range(__first2
, __last2
);
5109 for ( ; __first1
!= __last1
; ++__first1
)
5110 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
5111 if (__comp(*__first1
, *__iter
))
5117 // find_end, with and without an explicitly supplied comparison function.
5118 // Search [first2, last2) as a subsequence in [first1, last1), and return
5119 // the *last* possible match. Note that find_end for bidirectional iterators
5120 // is much faster than for forward iterators.
5122 // find_end for forward iterators.
5123 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
5125 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5126 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
5127 forward_iterator_tag
, forward_iterator_tag
)
5129 if (__first2
== __last2
)
5133 _ForwardIterator1 __result
= __last1
;
5136 _ForwardIterator1 __new_result
5137 = std::search(__first1
, __last1
, __first2
, __last2
);
5138 if (__new_result
== __last1
)
5142 __result
= __new_result
;
5143 __first1
= __new_result
;
5150 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
5151 typename _BinaryPredicate
>
5153 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5154 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
5155 forward_iterator_tag
, forward_iterator_tag
,
5156 _BinaryPredicate __comp
)
5158 if (__first2
== __last2
)
5162 _ForwardIterator1 __result
= __last1
;
5165 _ForwardIterator1 __new_result
5166 = std::search(__first1
, __last1
, __first2
, __last2
, __comp
);
5167 if (__new_result
== __last1
)
5171 __result
= __new_result
;
5172 __first1
= __new_result
;
5179 // find_end for bidirectional iterators. Requires partial specialization.
5180 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
>
5181 _BidirectionalIterator1
5182 __find_end(_BidirectionalIterator1 __first1
,
5183 _BidirectionalIterator1 __last1
,
5184 _BidirectionalIterator2 __first2
,
5185 _BidirectionalIterator2 __last2
,
5186 bidirectional_iterator_tag
, bidirectional_iterator_tag
)
5188 // concept requirements
5189 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5190 _BidirectionalIterator1
>)
5191 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5192 _BidirectionalIterator2
>)
5194 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
5195 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
5197 _RevIterator1
__rlast1(__first1
);
5198 _RevIterator2
__rlast2(__first2
);
5199 _RevIterator1 __rresult
= std::search(_RevIterator1(__last1
), __rlast1
,
5200 _RevIterator2(__last2
), __rlast2
);
5202 if (__rresult
== __rlast1
)
5206 _BidirectionalIterator1 __result
= __rresult
.base();
5207 std::advance(__result
, -std::distance(__first2
, __last2
));
5212 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
5213 typename _BinaryPredicate
>
5214 _BidirectionalIterator1
5215 __find_end(_BidirectionalIterator1 __first1
,
5216 _BidirectionalIterator1 __last1
,
5217 _BidirectionalIterator2 __first2
,
5218 _BidirectionalIterator2 __last2
,
5219 bidirectional_iterator_tag
, bidirectional_iterator_tag
,
5220 _BinaryPredicate __comp
)
5222 // concept requirements
5223 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5224 _BidirectionalIterator1
>)
5225 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5226 _BidirectionalIterator2
>)
5228 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
5229 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
5231 _RevIterator1
__rlast1(__first1
);
5232 _RevIterator2
__rlast2(__first2
);
5233 _RevIterator1 __rresult
= std::search(_RevIterator1(__last1
), __rlast1
,
5234 _RevIterator2(__last2
), __rlast2
,
5237 if (__rresult
== __rlast1
)
5241 _BidirectionalIterator1 __result
= __rresult
.base();
5242 std::advance(__result
, -std::distance(__first2
, __last2
));
5247 // Dispatching functions for find_end.
5250 * @brief Find last matching subsequence in a sequence.
5251 * @param first1 Start of range to search.
5252 * @param last1 End of range to search.
5253 * @param first2 Start of sequence to match.
5254 * @param last2 End of sequence to match.
5255 * @return The last iterator @c i in the range
5256 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5257 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
5258 * such iterator exists.
5260 * Searches the range @p [first1,last1) for a sub-sequence that compares
5261 * equal value-by-value with the sequence given by @p [first2,last2) and
5262 * returns an iterator to the first element of the sub-sequence, or
5263 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
5264 * last such subsequence contained in [first,last1).
5266 * Because the sub-sequence must lie completely within the range
5267 * @p [first1,last1) it must start at a position less than
5268 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5270 * This means that the returned iterator @c i will be in the range
5271 * @p [first1,last1-(last2-first2))
5273 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
5274 inline _ForwardIterator1
5275 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5276 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
5278 // concept requirements
5279 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
5280 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
5281 __glibcxx_function_requires(_EqualOpConcept
<
5282 typename iterator_traits
<_ForwardIterator1
>::value_type
,
5283 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
5284 __glibcxx_requires_valid_range(__first1
, __last1
);
5285 __glibcxx_requires_valid_range(__first2
, __last2
);
5287 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
5288 std::__iterator_category(__first1
),
5289 std::__iterator_category(__first2
));
5293 * @brief Find last matching subsequence in a sequence using a predicate.
5294 * @param first1 Start of range to search.
5295 * @param last1 End of range to search.
5296 * @param first2 Start of sequence to match.
5297 * @param last2 End of sequence to match.
5298 * @param comp The predicate to use.
5299 * @return The last iterator @c i in the range
5300 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5301 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5302 * @p last1 if no such iterator exists.
5304 * Searches the range @p [first1,last1) for a sub-sequence that compares
5305 * equal value-by-value with the sequence given by @p [first2,last2) using
5306 * comp as a predicate and returns an iterator to the first element of the
5307 * sub-sequence, or @p last1 if the sub-sequence is not found. The
5308 * sub-sequence will be the last such subsequence contained in
5311 * Because the sub-sequence must lie completely within the range
5312 * @p [first1,last1) it must start at a position less than
5313 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5315 * This means that the returned iterator @c i will be in the range
5316 * @p [first1,last1-(last2-first2))
5318 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
5319 typename _BinaryPredicate
>
5320 inline _ForwardIterator1
5321 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5322 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
5323 _BinaryPredicate __comp
)
5325 // concept requirements
5326 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
5327 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
5328 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
5329 typename iterator_traits
<_ForwardIterator1
>::value_type
,
5330 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
5331 __glibcxx_requires_valid_range(__first1
, __last1
);
5332 __glibcxx_requires_valid_range(__first2
, __last2
);
5334 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
5335 std::__iterator_category(__first1
),
5336 std::__iterator_category(__first2
),
5342 #endif /* _ALGO_H */