1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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
,
173 while (__first
!= __last
&& !(*__first
== __val
))
180 * This is an overload used by find_if() for the Input Iterator case.
183 template<typename _InputIterator
, typename _Predicate
>
184 inline _InputIterator
185 find_if(_InputIterator __first
, _InputIterator __last
,
189 while (__first
!= __last
&& !__pred(*__first
))
196 * This is an overload used by find() for the RAI case.
199 template<typename _RandomAccessIterator
, typename _Tp
>
200 _RandomAccessIterator
201 find(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
203 random_access_iterator_tag
)
205 typename iterator_traits
<_RandomAccessIterator
>::difference_type
206 __trip_count
= (__last
- __first
) >> 2;
208 for ( ; __trip_count
> 0 ; --__trip_count
)
210 if (*__first
== __val
)
214 if (*__first
== __val
)
218 if (*__first
== __val
)
222 if (*__first
== __val
)
227 switch (__last
- __first
)
230 if (*__first
== __val
)
234 if (*__first
== __val
)
238 if (*__first
== __val
)
249 * This is an overload used by find_if() for the RAI case.
252 template<typename _RandomAccessIterator
, typename _Predicate
>
253 _RandomAccessIterator
254 find_if(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
256 random_access_iterator_tag
)
258 typename iterator_traits
<_RandomAccessIterator
>::difference_type
259 __trip_count
= (__last
- __first
) >> 2;
261 for ( ; __trip_count
> 0 ; --__trip_count
)
263 if (__pred(*__first
))
267 if (__pred(*__first
))
271 if (__pred(*__first
))
275 if (__pred(*__first
))
280 switch (__last
- __first
)
283 if (__pred(*__first
))
287 if (__pred(*__first
))
291 if (__pred(*__first
))
301 * @brief Find the first occurrence of a value in a sequence.
302 * @param first An input iterator.
303 * @param last An input iterator.
304 * @param val The value to find.
305 * @return The first iterator @c i in the range @p [first,last)
306 * such that @c *i == @p val, or @p last if no such iterator exists.
308 template<typename _InputIterator
, typename _Tp
>
309 inline _InputIterator
310 find(_InputIterator __first
, _InputIterator __last
,
313 // concept requirements
314 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
315 __glibcxx_function_requires(_EqualOpConcept
<
316 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
317 __glibcxx_requires_valid_range(__first
, __last
);
318 return std::find(__first
, __last
, __val
,
319 std::__iterator_category(__first
));
323 * @brief Find the first element in a sequence for which a predicate is true.
324 * @param first An input iterator.
325 * @param last An input iterator.
326 * @param pred A predicate.
327 * @return The first iterator @c i in the range @p [first,last)
328 * such that @p pred(*i) is true, or @p last if no such iterator exists.
330 template<typename _InputIterator
, typename _Predicate
>
331 inline _InputIterator
332 find_if(_InputIterator __first
, _InputIterator __last
,
335 // concept requirements
336 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
337 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
338 typename iterator_traits
<_InputIterator
>::value_type
>)
339 __glibcxx_requires_valid_range(__first
, __last
);
340 return std::find_if(__first
, __last
, __pred
,
341 std::__iterator_category(__first
));
345 * @brief Find two adjacent values in a sequence that are equal.
346 * @param first A forward iterator.
347 * @param last A forward iterator.
348 * @return The first iterator @c i such that @c i and @c i+1 are both
349 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
350 * or @p last if no such iterator exists.
352 template<typename _ForwardIterator
>
354 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
)
356 // concept requirements
357 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
358 __glibcxx_function_requires(_EqualityComparableConcept
<
359 typename iterator_traits
<_ForwardIterator
>::value_type
>)
360 __glibcxx_requires_valid_range(__first
, __last
);
361 if (__first
== __last
)
363 _ForwardIterator __next
= __first
;
364 while(++__next
!= __last
)
366 if (*__first
== *__next
)
374 * @brief Find two adjacent values in a sequence using a predicate.
375 * @param first A forward iterator.
376 * @param last A forward iterator.
377 * @param binary_pred A binary predicate.
378 * @return The first iterator @c i such that @c i and @c i+1 are both
379 * valid iterators in @p [first,last) and such that
380 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
383 template<typename _ForwardIterator
, typename _BinaryPredicate
>
385 adjacent_find(_ForwardIterator __first
, _ForwardIterator __last
,
386 _BinaryPredicate __binary_pred
)
388 // concept requirements
389 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
390 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
391 typename iterator_traits
<_ForwardIterator
>::value_type
,
392 typename iterator_traits
<_ForwardIterator
>::value_type
>)
393 __glibcxx_requires_valid_range(__first
, __last
);
394 if (__first
== __last
)
396 _ForwardIterator __next
= __first
;
397 while(++__next
!= __last
)
399 if (__binary_pred(*__first
, *__next
))
407 * @brief Count the number of copies of a value in a sequence.
408 * @param first An input iterator.
409 * @param last An input iterator.
410 * @param value The value to be counted.
411 * @return The number of iterators @c i in the range @p [first,last)
412 * for which @c *i == @p value
414 template<typename _InputIterator
, typename _Tp
>
415 typename iterator_traits
<_InputIterator
>::difference_type
416 count(_InputIterator __first
, _InputIterator __last
, const _Tp
& __value
)
418 // concept requirements
419 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
420 __glibcxx_function_requires(_EqualityComparableConcept
<
421 typename iterator_traits
<_InputIterator
>::value_type
>)
422 __glibcxx_function_requires(_EqualityComparableConcept
<_Tp
>)
423 __glibcxx_requires_valid_range(__first
, __last
);
424 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
425 for ( ; __first
!= __last
; ++__first
)
426 if (*__first
== __value
)
432 * @brief Count the elements of a sequence for which a predicate is true.
433 * @param first An input iterator.
434 * @param last An input iterator.
435 * @param pred A predicate.
436 * @return The number of iterators @c i in the range @p [first,last)
437 * for which @p pred(*i) is true.
439 template<typename _InputIterator
, typename _Predicate
>
440 typename iterator_traits
<_InputIterator
>::difference_type
441 count_if(_InputIterator __first
, _InputIterator __last
, _Predicate __pred
)
443 // concept requirements
444 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
445 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
446 typename iterator_traits
<_InputIterator
>::value_type
>)
447 __glibcxx_requires_valid_range(__first
, __last
);
448 typename iterator_traits
<_InputIterator
>::difference_type __n
= 0;
449 for ( ; __first
!= __last
; ++__first
)
450 if (__pred(*__first
))
456 * @brief Search a sequence for a matching sub-sequence.
457 * @param first1 A forward iterator.
458 * @param last1 A forward iterator.
459 * @param first2 A forward iterator.
460 * @param last2 A forward iterator.
461 * @return The first iterator @c i in the range
462 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
463 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
464 * such iterator exists.
466 * Searches the range @p [first1,last1) for a sub-sequence that compares
467 * equal value-by-value with the sequence given by @p [first2,last2) and
468 * returns an iterator to the first element of the sub-sequence, or
469 * @p last1 if the sub-sequence is not found.
471 * Because the sub-sequence must lie completely within the range
472 * @p [first1,last1) it must start at a position less than
473 * @p last1-(last2-first2) where @p last2-first2 is the length of the
475 * This means that the returned iterator @c i will be in the range
476 * @p [first1,last1-(last2-first2))
478 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
480 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
481 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
483 // concept requirements
484 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
485 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
486 __glibcxx_function_requires(_EqualOpConcept
<
487 typename iterator_traits
<_ForwardIterator1
>::value_type
,
488 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
489 __glibcxx_requires_valid_range(__first1
, __last1
);
490 __glibcxx_requires_valid_range(__first2
, __last2
);
491 // Test for empty ranges
492 if (__first1
== __last1
|| __first2
== __last2
)
495 // Test for a pattern of length 1.
496 _ForwardIterator2
__tmp(__first2
);
498 if (__tmp
== __last2
)
499 return std::find(__first1
, __last1
, *__first2
);
502 _ForwardIterator2 __p1
, __p
;
503 __p1
= __first2
; ++__p1
;
504 _ForwardIterator1 __current
= __first1
;
506 while (__first1
!= __last1
)
508 __first1
= std::find(__first1
, __last1
, *__first2
);
509 if (__first1
== __last1
)
513 __current
= __first1
;
514 if (++__current
== __last1
)
517 while (*__current
== *__p
)
519 if (++__p
== __last2
)
521 if (++__current
== __last1
)
530 * @brief Search a sequence for a matching sub-sequence using a predicate.
531 * @param first1 A forward iterator.
532 * @param last1 A forward iterator.
533 * @param first2 A forward iterator.
534 * @param last2 A forward iterator.
535 * @param predicate A binary predicate.
536 * @return The first iterator @c i in the range
537 * @p [first1,last1-(last2-first2)) such that
538 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
539 * @p [0,last2-first2), or @p last1 if no such iterator exists.
541 * Searches the range @p [first1,last1) for a sub-sequence that compares
542 * equal value-by-value with the sequence given by @p [first2,last2),
543 * using @p predicate to determine equality, and returns an iterator
544 * to the first element of the sub-sequence, or @p last1 if no such
547 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
549 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
550 typename _BinaryPredicate
>
552 search(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
553 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
554 _BinaryPredicate __predicate
)
556 // concept requirements
557 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
558 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
559 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
560 typename iterator_traits
<_ForwardIterator1
>::value_type
,
561 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
562 __glibcxx_requires_valid_range(__first1
, __last1
);
563 __glibcxx_requires_valid_range(__first2
, __last2
);
565 // Test for empty ranges
566 if (__first1
== __last1
|| __first2
== __last2
)
569 // Test for a pattern of length 1.
570 _ForwardIterator2
__tmp(__first2
);
572 if (__tmp
== __last2
)
574 while (__first1
!= __last1
&& !__predicate(*__first1
, *__first2
))
580 _ForwardIterator2 __p1
, __p
;
581 __p1
= __first2
; ++__p1
;
582 _ForwardIterator1 __current
= __first1
;
584 while (__first1
!= __last1
)
586 while (__first1
!= __last1
)
588 if (__predicate(*__first1
, *__first2
))
592 while (__first1
!= __last1
&& !__predicate(*__first1
, *__first2
))
594 if (__first1
== __last1
)
598 __current
= __first1
;
599 if (++__current
== __last1
)
602 while (__predicate(*__current
, *__p
))
604 if (++__p
== __last2
)
606 if (++__current
== __last1
)
615 * @brief Search a sequence for a number of consecutive values.
616 * @param first A forward iterator.
617 * @param last A forward iterator.
618 * @param count The number of consecutive values.
619 * @param val The value to find.
620 * @return The first iterator @c i in the range @p [first,last-count)
621 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
622 * or @p last if no such iterator exists.
624 * Searches the range @p [first,last) for @p count consecutive elements
627 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
>
629 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
630 _Integer __count
, const _Tp
& __val
)
632 // concept requirements
633 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
634 __glibcxx_function_requires(_EqualityComparableConcept
<
635 typename iterator_traits
<_ForwardIterator
>::value_type
>)
636 __glibcxx_function_requires(_EqualityComparableConcept
<_Tp
>)
637 __glibcxx_requires_valid_range(__first
, __last
);
643 __first
= std::find(__first
, __last
, __val
);
644 while (__first
!= __last
)
646 typename iterator_traits
<_ForwardIterator
>::difference_type
648 _ForwardIterator __i
= __first
;
650 while (__i
!= __last
&& __n
!= 1 && *__i
== __val
)
658 __first
= std::find(__i
, __last
, __val
);
665 * @brief Search a sequence for a number of consecutive values using a
667 * @param first A forward iterator.
668 * @param last A forward iterator.
669 * @param count The number of consecutive values.
670 * @param val The value to find.
671 * @param binary_pred A binary predicate.
672 * @return The first iterator @c i in the range @p [first,last-count)
673 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
674 * range @p [0,count), or @p last if no such iterator exists.
676 * Searches the range @p [first,last) for @p count consecutive elements
677 * for which the predicate returns true.
679 template<typename _ForwardIterator
, typename _Integer
, typename _Tp
,
680 typename _BinaryPredicate
>
682 search_n(_ForwardIterator __first
, _ForwardIterator __last
,
683 _Integer __count
, const _Tp
& __val
,
684 _BinaryPredicate __binary_pred
)
686 // concept requirements
687 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
688 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
689 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
690 __glibcxx_requires_valid_range(__first
, __last
);
696 while (__first
!= __last
)
698 if (__binary_pred(*__first
, __val
))
702 while (__first
!= __last
)
704 typename iterator_traits
<_ForwardIterator
>::difference_type
706 _ForwardIterator __i
= __first
;
708 while (__i
!= __last
&& __n
!= 1 && __binary_pred(*__i
, __val
))
717 while (__i
!= __last
)
719 if (__binary_pred(*__i
, __val
))
731 * @brief Swap the elements of two sequences.
732 * @param first1 A forward iterator.
733 * @param last1 A forward iterator.
734 * @param first2 A forward iterator.
735 * @return An iterator equal to @p first2+(last1-first1).
737 * Swaps each element in the range @p [first1,last1) with the
738 * corresponding element in the range @p [first2,(last1-first1)).
739 * The ranges must not overlap.
741 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
743 swap_ranges(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
744 _ForwardIterator2 __first2
)
746 // concept requirements
747 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
749 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
751 __glibcxx_function_requires(_ConvertibleConcept
<
752 typename iterator_traits
<_ForwardIterator1
>::value_type
,
753 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
754 __glibcxx_function_requires(_ConvertibleConcept
<
755 typename iterator_traits
<_ForwardIterator2
>::value_type
,
756 typename iterator_traits
<_ForwardIterator1
>::value_type
>)
757 __glibcxx_requires_valid_range(__first1
, __last1
);
759 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
760 std::iter_swap(__first1
, __first2
);
765 * @brief Perform an operation on a sequence.
766 * @param first An input iterator.
767 * @param last An input iterator.
768 * @param result An output iterator.
769 * @param unary_op A unary operator.
770 * @return An output iterator equal to @p result+(last-first).
772 * Applies the operator to each element in the input range and assigns
773 * the results to successive elements of the output sequence.
774 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
775 * range @p [0,last-first).
777 * @p unary_op must not alter its argument.
779 template<typename _InputIterator
, typename _OutputIterator
,
780 typename _UnaryOperation
>
782 transform(_InputIterator __first
, _InputIterator __last
,
783 _OutputIterator __result
, _UnaryOperation __unary_op
)
785 // concept requirements
786 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
787 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
788 // "the type returned by a _UnaryOperation"
789 __typeof__(__unary_op(*__first
))>)
790 __glibcxx_requires_valid_range(__first
, __last
);
792 for ( ; __first
!= __last
; ++__first
, ++__result
)
793 *__result
= __unary_op(*__first
);
798 * @brief Perform an operation on corresponding elements of two sequences.
799 * @param first1 An input iterator.
800 * @param last1 An input iterator.
801 * @param first2 An input iterator.
802 * @param result An output iterator.
803 * @param binary_op A binary operator.
804 * @return An output iterator equal to @p result+(last-first).
806 * Applies the operator to the corresponding elements in the two
807 * input ranges and assigns the results to successive elements of the
809 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
810 * @c N in the range @p [0,last1-first1).
812 * @p binary_op must not alter either of its arguments.
814 template<typename _InputIterator1
, typename _InputIterator2
,
815 typename _OutputIterator
, typename _BinaryOperation
>
817 transform(_InputIterator1 __first1
, _InputIterator1 __last1
,
818 _InputIterator2 __first2
, _OutputIterator __result
,
819 _BinaryOperation __binary_op
)
821 // concept requirements
822 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
823 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
824 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
825 // "the type returned by a _BinaryOperation"
826 __typeof__(__binary_op(*__first1
,*__first2
))>)
827 __glibcxx_requires_valid_range(__first1
, __last1
);
829 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
, ++__result
)
830 *__result
= __binary_op(*__first1
, *__first2
);
835 * @brief Replace each occurrence of one value in a sequence with another
837 * @param first A forward iterator.
838 * @param last A forward iterator.
839 * @param old_value The value to be replaced.
840 * @param new_value The replacement value.
841 * @return replace() returns no value.
843 * For each iterator @c i in the range @p [first,last) if @c *i ==
844 * @p old_value then the assignment @c *i = @p new_value is performed.
846 template<typename _ForwardIterator
, typename _Tp
>
848 replace(_ForwardIterator __first
, _ForwardIterator __last
,
849 const _Tp
& __old_value
, const _Tp
& __new_value
)
851 // concept requirements
852 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
854 __glibcxx_function_requires(_EqualOpConcept
<
855 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
856 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
857 typename iterator_traits
<_ForwardIterator
>::value_type
>)
858 __glibcxx_requires_valid_range(__first
, __last
);
860 for ( ; __first
!= __last
; ++__first
)
861 if (*__first
== __old_value
)
862 *__first
= __new_value
;
866 * @brief Replace each value in a sequence for which a predicate returns
867 * true with another value.
868 * @param first A forward iterator.
869 * @param last A forward iterator.
870 * @param pred A predicate.
871 * @param new_value The replacement value.
872 * @return replace_if() returns no value.
874 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
875 * is true then the assignment @c *i = @p new_value is performed.
877 template<typename _ForwardIterator
, typename _Predicate
, typename _Tp
>
879 replace_if(_ForwardIterator __first
, _ForwardIterator __last
,
880 _Predicate __pred
, const _Tp
& __new_value
)
882 // concept requirements
883 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
885 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
886 typename iterator_traits
<_ForwardIterator
>::value_type
>)
887 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
888 typename iterator_traits
<_ForwardIterator
>::value_type
>)
889 __glibcxx_requires_valid_range(__first
, __last
);
891 for ( ; __first
!= __last
; ++__first
)
892 if (__pred(*__first
))
893 *__first
= __new_value
;
897 * @brief Copy a sequence, replacing each element of one value with another
899 * @param first An input iterator.
900 * @param last An input iterator.
901 * @param result An output iterator.
902 * @param old_value The value to be replaced.
903 * @param new_value The replacement value.
904 * @return The end of the output sequence, @p result+(last-first).
906 * Copies each element in the input range @p [first,last) to the
907 * output range @p [result,result+(last-first)) replacing elements
908 * equal to @p old_value with @p new_value.
910 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
912 replace_copy(_InputIterator __first
, _InputIterator __last
,
913 _OutputIterator __result
,
914 const _Tp
& __old_value
, const _Tp
& __new_value
)
916 // concept requirements
917 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
918 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
919 typename iterator_traits
<_InputIterator
>::value_type
>)
920 __glibcxx_function_requires(_EqualOpConcept
<
921 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
922 __glibcxx_requires_valid_range(__first
, __last
);
924 for ( ; __first
!= __last
; ++__first
, ++__result
)
925 *__result
= *__first
== __old_value
? __new_value
: *__first
;
930 * @brief Copy a sequence, replacing each value for which a predicate
931 * returns true with another value.
932 * @param first An input iterator.
933 * @param last An input iterator.
934 * @param result An output iterator.
935 * @param pred A predicate.
936 * @param new_value The replacement value.
937 * @return The end of the output sequence, @p result+(last-first).
939 * Copies each element in the range @p [first,last) to the range
940 * @p [result,result+(last-first)) replacing elements for which
941 * @p pred returns true with @p new_value.
943 template<typename _InputIterator
, typename _OutputIterator
,
944 typename _Predicate
, typename _Tp
>
946 replace_copy_if(_InputIterator __first
, _InputIterator __last
,
947 _OutputIterator __result
,
948 _Predicate __pred
, const _Tp
& __new_value
)
950 // concept requirements
951 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
952 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
953 typename iterator_traits
<_InputIterator
>::value_type
>)
954 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
955 typename iterator_traits
<_InputIterator
>::value_type
>)
956 __glibcxx_requires_valid_range(__first
, __last
);
958 for ( ; __first
!= __last
; ++__first
, ++__result
)
959 *__result
= __pred(*__first
) ? __new_value
: *__first
;
964 * @brief Assign the result of a function object to each value in a
966 * @param first A forward iterator.
967 * @param last A forward iterator.
968 * @param gen A function object taking no arguments.
969 * @return generate() returns no value.
971 * Performs the assignment @c *i = @p gen() for each @c i in the range
974 template<typename _ForwardIterator
, typename _Generator
>
976 generate(_ForwardIterator __first
, _ForwardIterator __last
,
979 // concept requirements
980 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
981 __glibcxx_function_requires(_GeneratorConcept
<_Generator
,
982 typename iterator_traits
<_ForwardIterator
>::value_type
>)
983 __glibcxx_requires_valid_range(__first
, __last
);
985 for ( ; __first
!= __last
; ++__first
)
990 * @brief Assign the result of a function object to each value in a
992 * @param first A forward iterator.
993 * @param n The length of the sequence.
994 * @param gen A function object taking no arguments.
995 * @return The end of the sequence, @p first+n
997 * Performs the assignment @c *i = @p gen() for each @c i in the range
998 * @p [first,first+n).
1000 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1002 generate_n(_OutputIterator __first
, _Size __n
, _Generator __gen
)
1004 // concept requirements
1005 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1006 // "the type returned by a _Generator"
1007 __typeof__(__gen())>)
1009 for ( ; __n
> 0; --__n
, ++__first
)
1015 * @brief Copy a sequence, removing elements of a given value.
1016 * @param first An input iterator.
1017 * @param last An input iterator.
1018 * @param result An output iterator.
1019 * @param value The value to be removed.
1020 * @return An iterator designating the end of the resulting sequence.
1022 * Copies each element in the range @p [first,last) not equal to @p value
1023 * to the range beginning at @p result.
1024 * remove_copy() is stable, so the relative order of elements that are
1025 * copied is unchanged.
1027 template<typename _InputIterator
, typename _OutputIterator
, typename _Tp
>
1029 remove_copy(_InputIterator __first
, _InputIterator __last
,
1030 _OutputIterator __result
, const _Tp
& __value
)
1032 // concept requirements
1033 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1034 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1035 typename iterator_traits
<_InputIterator
>::value_type
>)
1036 __glibcxx_function_requires(_EqualOpConcept
<
1037 typename iterator_traits
<_InputIterator
>::value_type
, _Tp
>)
1038 __glibcxx_requires_valid_range(__first
, __last
);
1040 for ( ; __first
!= __last
; ++__first
)
1041 if (!(*__first
== __value
))
1043 *__result
= *__first
;
1050 * @brief Copy a sequence, removing elements for which a predicate is true.
1051 * @param first An input iterator.
1052 * @param last An input iterator.
1053 * @param result An output iterator.
1054 * @param pred A predicate.
1055 * @return An iterator designating the end of the resulting sequence.
1057 * Copies each element in the range @p [first,last) for which
1058 * @p pred returns true to the range beginning at @p result.
1060 * remove_copy_if() is stable, so the relative order of elements that are
1061 * copied is unchanged.
1063 template<typename _InputIterator
, typename _OutputIterator
,
1064 typename _Predicate
>
1066 remove_copy_if(_InputIterator __first
, _InputIterator __last
,
1067 _OutputIterator __result
, _Predicate __pred
)
1069 // concept requirements
1070 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1071 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1072 typename iterator_traits
<_InputIterator
>::value_type
>)
1073 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1074 typename iterator_traits
<_InputIterator
>::value_type
>)
1075 __glibcxx_requires_valid_range(__first
, __last
);
1077 for ( ; __first
!= __last
; ++__first
)
1078 if (!__pred(*__first
))
1080 *__result
= *__first
;
1087 * @brief Remove elements from a sequence.
1088 * @param first An input iterator.
1089 * @param last An input iterator.
1090 * @param value The value to be removed.
1091 * @return An iterator designating the end of the resulting sequence.
1093 * All elements equal to @p value are removed from the range
1096 * remove() is stable, so the relative order of elements that are
1097 * not removed is unchanged.
1099 * Elements between the end of the resulting sequence and @p last
1100 * are still present, but their value is unspecified.
1102 template<typename _ForwardIterator
, typename _Tp
>
1104 remove(_ForwardIterator __first
, _ForwardIterator __last
,
1107 // concept requirements
1108 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1110 __glibcxx_function_requires(_ConvertibleConcept
<_Tp
,
1111 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1112 __glibcxx_function_requires(_EqualOpConcept
<
1113 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
1114 __glibcxx_requires_valid_range(__first
, __last
);
1116 __first
= std::find(__first
, __last
, __value
);
1117 _ForwardIterator __i
= __first
;
1118 return __first
== __last
? __first
1119 : std::remove_copy(++__i
, __last
,
1124 * @brief Remove elements from a sequence using a predicate.
1125 * @param first A forward iterator.
1126 * @param last A forward iterator.
1127 * @param pred A predicate.
1128 * @return An iterator designating the end of the resulting sequence.
1130 * All elements for which @p pred returns true are removed from the range
1133 * remove_if() is stable, so the relative order of elements that are
1134 * not removed is unchanged.
1136 * Elements between the end of the resulting sequence and @p last
1137 * are still present, but their value is unspecified.
1139 template<typename _ForwardIterator
, typename _Predicate
>
1141 remove_if(_ForwardIterator __first
, _ForwardIterator __last
,
1144 // concept requirements
1145 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1147 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1148 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1149 __glibcxx_requires_valid_range(__first
, __last
);
1151 __first
= std::find_if(__first
, __last
, __pred
);
1152 _ForwardIterator __i
= __first
;
1153 return __first
== __last
? __first
1154 : std::remove_copy_if(++__i
, __last
,
1160 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1162 * overloaded for output iterators.
1165 template<typename _InputIterator
, typename _OutputIterator
>
1167 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1168 _OutputIterator __result
,
1169 output_iterator_tag
)
1171 // concept requirements -- taken care of in dispatching function
1172 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1173 *__result
= __value
;
1174 while (++__first
!= __last
)
1175 if (!(__value
== *__first
))
1178 *++__result
= __value
;
1185 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1187 * overloaded for forward iterators.
1190 template<typename _InputIterator
, typename _ForwardIterator
>
1192 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1193 _ForwardIterator __result
,
1194 forward_iterator_tag
)
1196 // concept requirements -- taken care of in dispatching function
1197 *__result
= *__first
;
1198 while (++__first
!= __last
)
1199 if (!(*__result
== *__first
))
1200 *++__result
= *__first
;
1206 * This is an uglified
1207 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1209 * overloaded for output iterators.
1212 template<typename _InputIterator
, typename _OutputIterator
,
1213 typename _BinaryPredicate
>
1215 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1216 _OutputIterator __result
,
1217 _BinaryPredicate __binary_pred
,
1218 output_iterator_tag
)
1220 // concept requirements -- iterators already checked
1221 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1222 typename iterator_traits
<_InputIterator
>::value_type
,
1223 typename iterator_traits
<_InputIterator
>::value_type
>)
1225 typename iterator_traits
<_InputIterator
>::value_type __value
= *__first
;
1226 *__result
= __value
;
1227 while (++__first
!= __last
)
1228 if (!__binary_pred(__value
, *__first
))
1231 *++__result
= __value
;
1238 * This is an uglified
1239 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1241 * overloaded for forward iterators.
1244 template<typename _InputIterator
, typename _ForwardIterator
,
1245 typename _BinaryPredicate
>
1247 __unique_copy(_InputIterator __first
, _InputIterator __last
,
1248 _ForwardIterator __result
,
1249 _BinaryPredicate __binary_pred
,
1250 forward_iterator_tag
)
1252 // concept requirements -- iterators already checked
1253 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1254 typename iterator_traits
<_ForwardIterator
>::value_type
,
1255 typename iterator_traits
<_InputIterator
>::value_type
>)
1257 *__result
= *__first
;
1258 while (++__first
!= __last
)
1259 if (!__binary_pred(*__result
, *__first
)) *++__result
= *__first
;
1264 * @brief Copy a sequence, removing consecutive duplicate values.
1265 * @param first An input iterator.
1266 * @param last An input iterator.
1267 * @param result An output iterator.
1268 * @return An iterator designating the end of the resulting sequence.
1270 * Copies each element in the range @p [first,last) to the range
1271 * beginning at @p result, except that only the first element is copied
1272 * from groups of consecutive elements that compare equal.
1273 * unique_copy() is stable, so the relative order of elements that are
1274 * copied is unchanged.
1276 template<typename _InputIterator
, typename _OutputIterator
>
1277 inline _OutputIterator
1278 unique_copy(_InputIterator __first
, _InputIterator __last
,
1279 _OutputIterator __result
)
1281 // concept requirements
1282 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1283 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1284 typename iterator_traits
<_InputIterator
>::value_type
>)
1285 __glibcxx_function_requires(_EqualityComparableConcept
<
1286 typename iterator_traits
<_InputIterator
>::value_type
>)
1287 __glibcxx_requires_valid_range(__first
, __last
);
1289 typedef typename iterator_traits
<_OutputIterator
>::iterator_category
1292 if (__first
== __last
) return __result
;
1293 return std::__unique_copy(__first
, __last
, __result
, _IterType());
1297 * @brief Copy a sequence, removing consecutive values using a predicate.
1298 * @param first An input iterator.
1299 * @param last An input iterator.
1300 * @param result An output iterator.
1301 * @param binary_pred A binary predicate.
1302 * @return An iterator designating the end of the resulting sequence.
1304 * Copies each element in the range @p [first,last) to the range
1305 * beginning at @p result, except that only the first element is copied
1306 * from groups of consecutive elements for which @p binary_pred returns
1308 * unique_copy() is stable, so the relative order of elements that are
1309 * copied is unchanged.
1311 template<typename _InputIterator
, typename _OutputIterator
,
1312 typename _BinaryPredicate
>
1313 inline _OutputIterator
1314 unique_copy(_InputIterator __first
, _InputIterator __last
,
1315 _OutputIterator __result
,
1316 _BinaryPredicate __binary_pred
)
1318 // concept requirements -- predicates checked later
1319 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
1320 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1321 typename iterator_traits
<_InputIterator
>::value_type
>)
1322 __glibcxx_requires_valid_range(__first
, __last
);
1324 typedef typename iterator_traits
<_OutputIterator
>::iterator_category
1327 if (__first
== __last
) return __result
;
1328 return std::__unique_copy(__first
, __last
, __result
,
1329 __binary_pred
, _IterType());
1333 * @brief Remove consecutive duplicate values from a sequence.
1334 * @param first A forward iterator.
1335 * @param last A forward iterator.
1336 * @return An iterator designating the end of the resulting sequence.
1338 * Removes all but the first element from each group of consecutive
1339 * values that compare equal.
1340 * unique() is stable, so the relative order of elements that are
1341 * not removed is unchanged.
1342 * Elements between the end of the resulting sequence and @p last
1343 * are still present, but their value is unspecified.
1345 template<typename _ForwardIterator
>
1347 unique(_ForwardIterator __first
, _ForwardIterator __last
)
1349 // concept requirements
1350 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1352 __glibcxx_function_requires(_EqualityComparableConcept
<
1353 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1354 __glibcxx_requires_valid_range(__first
, __last
);
1356 // Skip the beginning, if already unique.
1357 __first
= std::adjacent_find(__first
, __last
);
1358 if (__first
== __last
)
1361 // Do the real copy work.
1362 _ForwardIterator __dest
= __first
;
1364 while (++__first
!= __last
)
1365 if (!(*__dest
== *__first
))
1366 *++__dest
= *__first
;
1371 * @brief Remove consecutive values from a sequence using a predicate.
1372 * @param first A forward iterator.
1373 * @param last A forward iterator.
1374 * @param binary_pred A binary predicate.
1375 * @return An iterator designating the end of the resulting sequence.
1377 * Removes all but the first element from each group of consecutive
1378 * values for which @p binary_pred returns true.
1379 * unique() is stable, so the relative order of elements that are
1380 * not removed is unchanged.
1381 * Elements between the end of the resulting sequence and @p last
1382 * are still present, but their value is unspecified.
1384 template<typename _ForwardIterator
, typename _BinaryPredicate
>
1386 unique(_ForwardIterator __first
, _ForwardIterator __last
,
1387 _BinaryPredicate __binary_pred
)
1389 // concept requirements
1390 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1392 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
1393 typename iterator_traits
<_ForwardIterator
>::value_type
,
1394 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1395 __glibcxx_requires_valid_range(__first
, __last
);
1397 // Skip the beginning, if already unique.
1398 __first
= std::adjacent_find(__first
, __last
, __binary_pred
);
1399 if (__first
== __last
)
1402 // Do the real copy work.
1403 _ForwardIterator __dest
= __first
;
1405 while (++__first
!= __last
)
1406 if (!__binary_pred(*__dest
, *__first
))
1407 *++__dest
= *__first
;
1413 * This is an uglified reverse(_BidirectionalIterator,
1414 * _BidirectionalIterator)
1415 * overloaded for bidirectional iterators.
1418 template<typename _BidirectionalIterator
>
1420 __reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1421 bidirectional_iterator_tag
)
1424 if (__first
== __last
|| __first
== --__last
)
1427 std::iter_swap(__first
++, __last
);
1432 * This is an uglified reverse(_BidirectionalIterator,
1433 * _BidirectionalIterator)
1434 * overloaded for bidirectional iterators.
1437 template<typename _RandomAccessIterator
>
1439 __reverse(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1440 random_access_iterator_tag
)
1442 while (__first
< __last
)
1443 std::iter_swap(__first
++, --__last
);
1447 * @brief Reverse a sequence.
1448 * @param first A bidirectional iterator.
1449 * @param last A bidirectional iterator.
1450 * @return reverse() returns no value.
1452 * Reverses the order of the elements in the range @p [first,last),
1453 * so that the first element becomes the last etc.
1454 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1455 * swaps @p *(first+i) and @p *(last-(i+1))
1457 template<typename _BidirectionalIterator
>
1459 reverse(_BidirectionalIterator __first
, _BidirectionalIterator __last
)
1461 // concept requirements
1462 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1463 _BidirectionalIterator
>)
1464 __glibcxx_requires_valid_range(__first
, __last
);
1465 std::__reverse(__first
, __last
, std::__iterator_category(__first
));
1469 * @brief Copy a sequence, reversing its elements.
1470 * @param first A bidirectional iterator.
1471 * @param last A bidirectional iterator.
1472 * @param result An output iterator.
1473 * @return An iterator designating the end of the resulting sequence.
1475 * Copies the elements in the range @p [first,last) to the range
1476 * @p [result,result+(last-first)) such that the order of the
1477 * elements is reversed.
1478 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1479 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1480 * The ranges @p [first,last) and @p [result,result+(last-first))
1483 template<typename _BidirectionalIterator
, typename _OutputIterator
>
1485 reverse_copy(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1486 _OutputIterator __result
)
1488 // concept requirements
1489 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
1490 _BidirectionalIterator
>)
1491 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1492 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
1493 __glibcxx_requires_valid_range(__first
, __last
);
1495 while (__first
!= __last
)
1498 *__result
= *__last
;
1507 * This is a helper function for the rotate algorithm specialized on RAIs.
1508 * It returns the greatest common divisor of two integer values.
1511 template<typename _EuclideanRingElement
>
1512 _EuclideanRingElement
1513 __gcd(_EuclideanRingElement __m
, _EuclideanRingElement __n
)
1517 _EuclideanRingElement __t
= __m
% __n
;
1526 * This is a helper function for the rotate algorithm.
1529 template<typename _ForwardIterator
>
1531 __rotate(_ForwardIterator __first
,
1532 _ForwardIterator __middle
,
1533 _ForwardIterator __last
,
1534 forward_iterator_tag
)
1536 if ((__first
== __middle
) || (__last
== __middle
))
1539 _ForwardIterator __first2
= __middle
;
1542 swap(*__first
++, *__first2
++);
1543 if (__first
== __middle
)
1544 __middle
= __first2
;
1546 while (__first2
!= __last
);
1548 __first2
= __middle
;
1550 while (__first2
!= __last
)
1552 swap(*__first
++, *__first2
++);
1553 if (__first
== __middle
)
1554 __middle
= __first2
;
1555 else if (__first2
== __last
)
1556 __first2
= __middle
;
1562 * This is a helper function for the rotate algorithm.
1565 template<typename _BidirectionalIterator
>
1567 __rotate(_BidirectionalIterator __first
,
1568 _BidirectionalIterator __middle
,
1569 _BidirectionalIterator __last
,
1570 bidirectional_iterator_tag
)
1572 // concept requirements
1573 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
1574 _BidirectionalIterator
>)
1576 if ((__first
== __middle
) || (__last
== __middle
))
1579 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1580 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1582 while (__first
!= __middle
&& __middle
!= __last
)
1583 swap(*__first
++, *--__last
);
1585 if (__first
== __middle
)
1586 std::__reverse(__middle
, __last
, bidirectional_iterator_tag());
1588 std::__reverse(__first
, __middle
, bidirectional_iterator_tag());
1593 * This is a helper function for the rotate algorithm.
1596 template<typename _RandomAccessIterator
>
1598 __rotate(_RandomAccessIterator __first
,
1599 _RandomAccessIterator __middle
,
1600 _RandomAccessIterator __last
,
1601 random_access_iterator_tag
)
1603 // concept requirements
1604 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1605 _RandomAccessIterator
>)
1607 if ((__first
== __middle
) || (__last
== __middle
))
1610 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
1612 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
1615 const _Distance __n
= __last
- __first
;
1616 const _Distance __k
= __middle
- __first
;
1617 const _Distance __l
= __n
- __k
;
1621 std::swap_ranges(__first
, __middle
, __middle
);
1625 const _Distance __d
= __gcd(__n
, __k
);
1627 for (_Distance __i
= 0; __i
< __d
; __i
++)
1629 const _ValueType __tmp
= *__first
;
1630 _RandomAccessIterator __p
= __first
;
1634 for (_Distance __j
= 0; __j
< __l
/ __d
; __j
++)
1636 if (__p
> __first
+ __l
)
1638 *__p
= *(__p
- __l
);
1642 *__p
= *(__p
+ __k
);
1648 for (_Distance __j
= 0; __j
< __k
/ __d
- 1; __j
++)
1650 if (__p
< __last
- __k
)
1652 *__p
= *(__p
+ __k
);
1655 *__p
= * (__p
- __l
);
1666 * @brief Rotate the elements of a sequence.
1667 * @param first A forward iterator.
1668 * @param middle A forward iterator.
1669 * @param last A forward iterator.
1672 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1673 * positions so that the element at @p middle is moved to @p first, the
1674 * element at @p middle+1 is moved to @first+1 and so on for each element
1675 * in the range @p [first,last).
1677 * This effectively swaps the ranges @p [first,middle) and
1680 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1681 * each @p n in the range @p [0,last-first).
1683 template<typename _ForwardIterator
>
1685 rotate(_ForwardIterator __first
, _ForwardIterator __middle
,
1686 _ForwardIterator __last
)
1688 // concept requirements
1689 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1691 __glibcxx_requires_valid_range(__first
, __middle
);
1692 __glibcxx_requires_valid_range(__middle
, __last
);
1694 typedef typename iterator_traits
<_ForwardIterator
>::iterator_category
1696 std::__rotate(__first
, __middle
, __last
, _IterType());
1700 * @brief Copy a sequence, rotating its elements.
1701 * @param first A forward iterator.
1702 * @param middle A forward iterator.
1703 * @param last A forward iterator.
1704 * @param result An output iterator.
1705 * @return An iterator designating the end of the resulting sequence.
1707 * Copies the elements of the range @p [first,last) to the range
1708 * beginning at @result, rotating the copied elements by @p (middle-first)
1709 * positions so that the element at @p middle is moved to @p result, the
1710 * element at @p middle+1 is moved to @result+1 and so on for each element
1711 * in the range @p [first,last).
1713 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1714 * each @p n in the range @p [0,last-first).
1716 template<typename _ForwardIterator
, typename _OutputIterator
>
1718 rotate_copy(_ForwardIterator __first
, _ForwardIterator __middle
,
1719 _ForwardIterator __last
, _OutputIterator __result
)
1721 // concept requirements
1722 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
1723 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
1724 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1725 __glibcxx_requires_valid_range(__first
, __middle
);
1726 __glibcxx_requires_valid_range(__middle
, __last
);
1728 return std::copy(__first
, __middle
, copy(__middle
, __last
, __result
));
1732 * @brief Randomly shuffle the elements of a sequence.
1733 * @param first A forward iterator.
1734 * @param last A forward iterator.
1737 * Reorder the elements in the range @p [first,last) using a random
1738 * distribution, so that every possible ordering of the sequence is
1741 template<typename _RandomAccessIterator
>
1743 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
1745 // concept requirements
1746 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1747 _RandomAccessIterator
>)
1748 __glibcxx_requires_valid_range(__first
, __last
);
1750 if (__first
!= __last
)
1751 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
1752 std::iter_swap(__i
, __first
+ (std::rand() % ((__i
- __first
) + 1)));
1756 * @brief Shuffle the elements of a sequence using a random number
1758 * @param first A forward iterator.
1759 * @param last A forward iterator.
1760 * @param rand The RNG functor or function.
1763 * Reorders the elements in the range @p [first,last) using @p rand to
1764 * provide a random distribution. Calling @p rand(N) for a positive
1765 * integer @p N should return a randomly chosen integer from the
1768 template<typename _RandomAccessIterator
, typename _RandomNumberGenerator
>
1770 random_shuffle(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
1771 _RandomNumberGenerator
& __rand
)
1773 // concept requirements
1774 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
1775 _RandomAccessIterator
>)
1776 __glibcxx_requires_valid_range(__first
, __last
);
1778 if (__first
== __last
)
1780 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
1781 std::iter_swap(__i
, __first
+ __rand((__i
- __first
) + 1));
1787 * This is a helper function...
1790 template<typename _ForwardIterator
, typename _Predicate
>
1792 __partition(_ForwardIterator __first
, _ForwardIterator __last
,
1794 forward_iterator_tag
)
1796 if (__first
== __last
)
1799 while (__pred(*__first
))
1800 if (++__first
== __last
)
1803 _ForwardIterator __next
= __first
;
1805 while (++__next
!= __last
)
1806 if (__pred(*__next
))
1808 swap(*__first
, *__next
);
1817 * This is a helper function...
1820 template<typename _BidirectionalIterator
, typename _Predicate
>
1821 _BidirectionalIterator
1822 __partition(_BidirectionalIterator __first
, _BidirectionalIterator __last
,
1824 bidirectional_iterator_tag
)
1829 if (__first
== __last
)
1831 else if (__pred(*__first
))
1837 if (__first
== __last
)
1839 else if (!__pred(*__last
))
1843 std::iter_swap(__first
, __last
);
1849 * @brief Move elements for which a predicate is true to the beginning
1851 * @param first A forward iterator.
1852 * @param last A forward iterator.
1853 * @param pred A predicate functor.
1854 * @return An iterator @p middle such that @p pred(i) is true for each
1855 * iterator @p i in the range @p [first,middle) and false for each @p i
1856 * in the range @p [middle,last).
1858 * @p pred must not modify its operand. @p partition() does not preserve
1859 * the relative ordering of elements in each group, use
1860 * @p stable_partition() if this is needed.
1862 template<typename _ForwardIterator
, typename _Predicate
>
1863 inline _ForwardIterator
1864 partition(_ForwardIterator __first
, _ForwardIterator __last
,
1867 // concept requirements
1868 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1870 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1871 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1872 __glibcxx_requires_valid_range(__first
, __last
);
1874 return std::__partition(__first
, __last
, __pred
,
1875 std::__iterator_category(__first
));
1881 * This is a helper function...
1884 template<typename _ForwardIterator
, typename _Predicate
, typename _Distance
>
1886 __inplace_stable_partition(_ForwardIterator __first
,
1887 _ForwardIterator __last
,
1888 _Predicate __pred
, _Distance __len
)
1891 return __pred(*__first
) ? __last
: __first
;
1892 _ForwardIterator __middle
= __first
;
1893 std::advance(__middle
, __len
/ 2);
1894 _ForwardIterator __begin
= std::__inplace_stable_partition(__first
,
1898 _ForwardIterator __end
= std::__inplace_stable_partition(__middle
, __last
,
1902 std::rotate(__begin
, __middle
, __end
);
1903 std::advance(__begin
, std::distance(__middle
, __end
));
1909 * This is a helper function...
1912 template<typename _ForwardIterator
, typename _Pointer
, typename _Predicate
,
1915 __stable_partition_adaptive(_ForwardIterator __first
,
1916 _ForwardIterator __last
,
1917 _Predicate __pred
, _Distance __len
,
1919 _Distance __buffer_size
)
1921 if (__len
<= __buffer_size
)
1923 _ForwardIterator __result1
= __first
;
1924 _Pointer __result2
= __buffer
;
1925 for ( ; __first
!= __last
; ++__first
)
1926 if (__pred(*__first
))
1928 *__result1
= *__first
;
1933 *__result2
= *__first
;
1936 std::copy(__buffer
, __result2
, __result1
);
1941 _ForwardIterator __middle
= __first
;
1942 std::advance(__middle
, __len
/ 2);
1943 _ForwardIterator __begin
=
1944 std::__stable_partition_adaptive(__first
, __middle
, __pred
,
1945 __len
/ 2, __buffer
,
1947 _ForwardIterator __end
=
1948 std::__stable_partition_adaptive(__middle
, __last
, __pred
,
1950 __buffer
, __buffer_size
);
1951 std::rotate(__begin
, __middle
, __end
);
1952 std::advance(__begin
, std::distance(__middle
, __end
));
1958 * @brief Move elements for which a predicate is true to the beginning
1959 * of a sequence, preserving relative ordering.
1960 * @param first A forward iterator.
1961 * @param last A forward iterator.
1962 * @param pred A predicate functor.
1963 * @return An iterator @p middle such that @p pred(i) is true for each
1964 * iterator @p i in the range @p [first,middle) and false for each @p i
1965 * in the range @p [middle,last).
1967 * Performs the same function as @p partition() with the additional
1968 * guarantee that the relative ordering of elements in each group is
1969 * preserved, so any two elements @p x and @p y in the range
1970 * @p [first,last) such that @p pred(x)==pred(y) will have the same
1971 * relative ordering after calling @p stable_partition().
1973 template<typename _ForwardIterator
, typename _Predicate
>
1975 stable_partition(_ForwardIterator __first
, _ForwardIterator __last
,
1978 // concept requirements
1979 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept
<
1981 __glibcxx_function_requires(_UnaryPredicateConcept
<_Predicate
,
1982 typename iterator_traits
<_ForwardIterator
>::value_type
>)
1983 __glibcxx_requires_valid_range(__first
, __last
);
1985 if (__first
== __last
)
1989 typedef typename iterator_traits
<_ForwardIterator
>::value_type
1991 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
1994 _Temporary_buffer
<_ForwardIterator
, _ValueType
> __buf(__first
,
1996 if (__buf
.size() > 0)
1998 std::__stable_partition_adaptive(__first
, __last
, __pred
,
1999 _DistanceType(__buf
.requested_size()),
2000 __buf
.begin(), __buf
.size());
2003 std::__inplace_stable_partition(__first
, __last
, __pred
,
2004 _DistanceType(__buf
.requested_size()));
2010 * This is a helper function...
2013 template<typename _RandomAccessIterator
, typename _Tp
>
2014 _RandomAccessIterator
2015 __unguarded_partition(_RandomAccessIterator __first
,
2016 _RandomAccessIterator __last
, _Tp __pivot
)
2020 while (*__first
< __pivot
)
2023 while (__pivot
< *__last
)
2025 if (!(__first
< __last
))
2027 std::iter_swap(__first
, __last
);
2034 * This is a helper function...
2037 template<typename _RandomAccessIterator
, typename _Tp
, typename _Compare
>
2038 _RandomAccessIterator
2039 __unguarded_partition(_RandomAccessIterator __first
,
2040 _RandomAccessIterator __last
,
2041 _Tp __pivot
, _Compare __comp
)
2045 while (__comp(*__first
, __pivot
))
2048 while (__comp(__pivot
, *__last
))
2050 if (!(__first
< __last
))
2052 std::iter_swap(__first
, __last
);
2060 * This controls some aspect of the sort routines.
2063 enum { _S_threshold
= 16 };
2067 * This is a helper function for the sort routine.
2070 template<typename _RandomAccessIterator
, typename _Tp
>
2072 __unguarded_linear_insert(_RandomAccessIterator __last
, _Tp __val
)
2074 _RandomAccessIterator __next
= __last
;
2076 while (__val
< *__next
)
2087 * This is a helper function for the sort routine.
2090 template<typename _RandomAccessIterator
, typename _Tp
, typename _Compare
>
2092 __unguarded_linear_insert(_RandomAccessIterator __last
, _Tp __val
,
2095 _RandomAccessIterator __next
= __last
;
2097 while (__comp(__val
, *__next
))
2108 * This is a helper function for the sort routine.
2111 template<typename _RandomAccessIterator
>
2113 __insertion_sort(_RandomAccessIterator __first
,
2114 _RandomAccessIterator __last
)
2116 if (__first
== __last
)
2119 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2121 typename iterator_traits
<_RandomAccessIterator
>::value_type
2123 if (__val
< *__first
)
2125 std::copy_backward(__first
, __i
, __i
+ 1);
2129 std::__unguarded_linear_insert(__i
, __val
);
2135 * This is a helper function for the sort routine.
2138 template<typename _RandomAccessIterator
, typename _Compare
>
2140 __insertion_sort(_RandomAccessIterator __first
,
2141 _RandomAccessIterator __last
, _Compare __comp
)
2143 if (__first
== __last
) return;
2145 for (_RandomAccessIterator __i
= __first
+ 1; __i
!= __last
; ++__i
)
2147 typename iterator_traits
<_RandomAccessIterator
>::value_type
2149 if (__comp(__val
, *__first
))
2151 std::copy_backward(__first
, __i
, __i
+ 1);
2155 std::__unguarded_linear_insert(__i
, __val
, __comp
);
2161 * This is a helper function for the sort routine.
2164 template<typename _RandomAccessIterator
>
2166 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2167 _RandomAccessIterator __last
)
2169 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2172 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2173 std::__unguarded_linear_insert(__i
, _ValueType(*__i
));
2178 * This is a helper function for the sort routine.
2181 template<typename _RandomAccessIterator
, typename _Compare
>
2183 __unguarded_insertion_sort(_RandomAccessIterator __first
,
2184 _RandomAccessIterator __last
, _Compare __comp
)
2186 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2189 for (_RandomAccessIterator __i
= __first
; __i
!= __last
; ++__i
)
2190 std::__unguarded_linear_insert(__i
, _ValueType(*__i
), __comp
);
2195 * This is a helper function for the sort routine.
2198 template<typename _RandomAccessIterator
>
2200 __final_insertion_sort(_RandomAccessIterator __first
,
2201 _RandomAccessIterator __last
)
2203 if (__last
- __first
> _S_threshold
)
2205 std::__insertion_sort(__first
, __first
+ _S_threshold
);
2206 std::__unguarded_insertion_sort(__first
+ _S_threshold
, __last
);
2209 std::__insertion_sort(__first
, __last
);
2214 * This is a helper function for the sort routine.
2217 template<typename _RandomAccessIterator
, typename _Compare
>
2219 __final_insertion_sort(_RandomAccessIterator __first
,
2220 _RandomAccessIterator __last
, _Compare __comp
)
2222 if (__last
- __first
> _S_threshold
)
2224 std::__insertion_sort(__first
, __first
+ _S_threshold
, __comp
);
2225 std::__unguarded_insertion_sort(__first
+ _S_threshold
, __last
,
2229 std::__insertion_sort(__first
, __last
, __comp
);
2234 * This is a helper function for the sort routine.
2237 template<typename _Size
>
2242 for (__k
= 0; __n
!= 1; __n
>>= 1)
2248 * @brief Sort the smallest elements of a sequence.
2249 * @param first An iterator.
2250 * @param middle Another iterator.
2251 * @param last Another iterator.
2254 * Sorts the smallest @p (middle-first) elements in the range
2255 * @p [first,last) and moves them to the range @p [first,middle). The
2256 * order of the remaining elements in the range @p [middle,last) is
2258 * After the sort if @p i and @j are iterators in the range
2259 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2260 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2262 template<typename _RandomAccessIterator
>
2264 partial_sort(_RandomAccessIterator __first
,
2265 _RandomAccessIterator __middle
,
2266 _RandomAccessIterator __last
)
2268 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2271 // concept requirements
2272 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2273 _RandomAccessIterator
>)
2274 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
2275 __glibcxx_requires_valid_range(__first
, __middle
);
2276 __glibcxx_requires_valid_range(__middle
, __last
);
2278 std::make_heap(__first
, __middle
);
2279 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
2280 if (*__i
< *__first
)
2281 std::__pop_heap(__first
, __middle
, __i
, _ValueType(*__i
));
2282 std::sort_heap(__first
, __middle
);
2286 * @brief Sort the smallest elements of a sequence using a predicate
2288 * @param first An iterator.
2289 * @param middle Another iterator.
2290 * @param last Another iterator.
2291 * @param comp A comparison functor.
2294 * Sorts the smallest @p (middle-first) elements in the range
2295 * @p [first,last) and moves them to the range @p [first,middle). The
2296 * order of the remaining elements in the range @p [middle,last) is
2298 * After the sort if @p i and @j are iterators in the range
2299 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2300 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2303 template<typename _RandomAccessIterator
, typename _Compare
>
2305 partial_sort(_RandomAccessIterator __first
,
2306 _RandomAccessIterator __middle
,
2307 _RandomAccessIterator __last
,
2310 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2313 // concept requirements
2314 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2315 _RandomAccessIterator
>)
2316 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2317 _ValueType
, _ValueType
>)
2318 __glibcxx_requires_valid_range(__first
, __middle
);
2319 __glibcxx_requires_valid_range(__middle
, __last
);
2321 std::make_heap(__first
, __middle
, __comp
);
2322 for (_RandomAccessIterator __i
= __middle
; __i
< __last
; ++__i
)
2323 if (__comp(*__i
, *__first
))
2324 std::__pop_heap(__first
, __middle
, __i
, _ValueType(*__i
), __comp
);
2325 std::sort_heap(__first
, __middle
, __comp
);
2329 * @brief Copy the smallest elements of a sequence.
2330 * @param first An iterator.
2331 * @param last Another iterator.
2332 * @param result_first A random-access iterator.
2333 * @param result_last Another random-access iterator.
2334 * @return An iterator indicating the end of the resulting sequence.
2336 * Copies and sorts the smallest N values from the range @p [first,last)
2337 * to the range beginning at @p result_first, where the number of
2338 * elements to be copied, @p N, is the smaller of @p (last-first) and
2339 * @p (result_last-result_first).
2340 * After the sort if @p i and @j are iterators in the range
2341 * @p [result_first,result_first+N) such that @i precedes @j then
2342 * @p *j<*i is false.
2343 * The value returned is @p result_first+N.
2345 template<typename _InputIterator
, typename _RandomAccessIterator
>
2346 _RandomAccessIterator
2347 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2348 _RandomAccessIterator __result_first
,
2349 _RandomAccessIterator __result_last
)
2351 typedef typename iterator_traits
<_InputIterator
>::value_type
2353 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2355 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2358 // concept requirements
2359 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2360 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2362 __glibcxx_function_requires(_LessThanComparableConcept
<_OutputValueType
>)
2363 __glibcxx_function_requires(_LessThanComparableConcept
<_InputValueType
>)
2364 __glibcxx_requires_valid_range(__first
, __last
);
2365 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2367 if (__result_first
== __result_last
)
2368 return __result_last
;
2369 _RandomAccessIterator __result_real_last
= __result_first
;
2370 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2372 *__result_real_last
= *__first
;
2373 ++__result_real_last
;
2376 std::make_heap(__result_first
, __result_real_last
);
2377 while (__first
!= __last
)
2379 if (*__first
< *__result_first
)
2380 std::__adjust_heap(__result_first
, _DistanceType(0),
2381 _DistanceType(__result_real_last
2383 _InputValueType(*__first
));
2386 std::sort_heap(__result_first
, __result_real_last
);
2387 return __result_real_last
;
2391 * @brief Copy the smallest elements of a sequence using a predicate for
2393 * @param first An input iterator.
2394 * @param last Another input iterator.
2395 * @param result_first A random-access iterator.
2396 * @param result_last Another random-access iterator.
2397 * @param comp A comparison functor.
2398 * @return An iterator indicating the end of the resulting sequence.
2400 * Copies and sorts the smallest N values from the range @p [first,last)
2401 * to the range beginning at @p result_first, where the number of
2402 * elements to be copied, @p N, is the smaller of @p (last-first) and
2403 * @p (result_last-result_first).
2404 * After the sort if @p i and @j are iterators in the range
2405 * @p [result_first,result_first+N) such that @i precedes @j then
2406 * @p comp(*j,*i) is false.
2407 * The value returned is @p result_first+N.
2409 template<typename _InputIterator
, typename _RandomAccessIterator
, typename _Compare
>
2410 _RandomAccessIterator
2411 partial_sort_copy(_InputIterator __first
, _InputIterator __last
,
2412 _RandomAccessIterator __result_first
,
2413 _RandomAccessIterator __result_last
,
2416 typedef typename iterator_traits
<_InputIterator
>::value_type
2418 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2420 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
2423 // concept requirements
2424 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
2425 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2426 _RandomAccessIterator
>)
2427 __glibcxx_function_requires(_ConvertibleConcept
<_InputValueType
,
2429 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2430 _OutputValueType
, _OutputValueType
>)
2431 __glibcxx_requires_valid_range(__first
, __last
);
2432 __glibcxx_requires_valid_range(__result_first
, __result_last
);
2434 if (__result_first
== __result_last
)
2435 return __result_last
;
2436 _RandomAccessIterator __result_real_last
= __result_first
;
2437 while(__first
!= __last
&& __result_real_last
!= __result_last
)
2439 *__result_real_last
= *__first
;
2440 ++__result_real_last
;
2443 std::make_heap(__result_first
, __result_real_last
, __comp
);
2444 while (__first
!= __last
)
2446 if (__comp(*__first
, *__result_first
))
2447 std::__adjust_heap(__result_first
, _DistanceType(0),
2448 _DistanceType(__result_real_last
2450 _InputValueType(*__first
),
2454 std::sort_heap(__result_first
, __result_real_last
, __comp
);
2455 return __result_real_last
;
2460 * This is a helper function for the sort routine.
2463 template<typename _RandomAccessIterator
, typename _Size
>
2465 __introsort_loop(_RandomAccessIterator __first
,
2466 _RandomAccessIterator __last
,
2467 _Size __depth_limit
)
2469 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2472 while (__last
- __first
> _S_threshold
)
2474 if (__depth_limit
== 0)
2476 std::partial_sort(__first
, __last
, __last
);
2480 _RandomAccessIterator __cut
=
2481 std::__unguarded_partition(__first
, __last
,
2482 _ValueType(std::__median(*__first
,
2489 std::__introsort_loop(__cut
, __last
, __depth_limit
);
2496 * This is a helper function for the sort routine.
2499 template<typename _RandomAccessIterator
, typename _Size
, typename _Compare
>
2501 __introsort_loop(_RandomAccessIterator __first
,
2502 _RandomAccessIterator __last
,
2503 _Size __depth_limit
, _Compare __comp
)
2505 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2508 while (__last
- __first
> _S_threshold
)
2510 if (__depth_limit
== 0)
2512 std::partial_sort(__first
, __last
, __last
, __comp
);
2516 _RandomAccessIterator __cut
=
2517 std::__unguarded_partition(__first
, __last
,
2518 _ValueType(std::__median(*__first
,
2526 std::__introsort_loop(__cut
, __last
, __depth_limit
, __comp
);
2532 * @brief Sort the elements of a sequence.
2533 * @param first An iterator.
2534 * @param last Another iterator.
2537 * Sorts the elements in the range @p [first,last) in ascending order,
2538 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2539 * @p [first,last-1).
2541 * The relative ordering of equivalent elements is not preserved, use
2542 * @p stable_sort() if this is needed.
2544 template<typename _RandomAccessIterator
>
2546 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
2548 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2551 // concept requirements
2552 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2553 _RandomAccessIterator
>)
2554 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
2555 __glibcxx_requires_valid_range(__first
, __last
);
2557 if (__first
!= __last
)
2559 std::__introsort_loop(__first
, __last
, __lg(__last
- __first
) * 2);
2560 std::__final_insertion_sort(__first
, __last
);
2565 * @brief Sort the elements of a sequence using a predicate for comparison.
2566 * @param first An iterator.
2567 * @param last Another iterator.
2568 * @param comp A comparison functor.
2571 * Sorts the elements in the range @p [first,last) in ascending order,
2572 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2573 * range @p [first,last-1).
2575 * The relative ordering of equivalent elements is not preserved, use
2576 * @p stable_sort() if this is needed.
2578 template<typename _RandomAccessIterator
, typename _Compare
>
2580 sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
2583 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
2586 // concept requirements
2587 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
2588 _RandomAccessIterator
>)
2589 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
, _ValueType
,
2591 __glibcxx_requires_valid_range(__first
, __last
);
2593 if (__first
!= __last
)
2595 std::__introsort_loop(__first
, __last
, __lg(__last
- __first
) * 2,
2597 std::__final_insertion_sort(__first
, __last
, __comp
);
2602 * @brief Finds the first position in which @a val could be inserted
2603 * without changing the ordering.
2604 * @param first An iterator.
2605 * @param last Another iterator.
2606 * @param val The search term.
2607 * @return An iterator pointing to the first element "not less than" @a val,
2608 * or end() if every element is less than @a val.
2609 * @ingroup binarysearch
2611 template<typename _ForwardIterator
, typename _Tp
>
2613 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2616 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2618 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2621 // concept requirements
2622 // Note that these are slightly stricter than those of the 4-argument
2623 // version, defined next. The difference is in the strictness of the
2624 // comparison operations... so for looser checking, define your own
2625 // comparison function, as was intended.
2626 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2627 __glibcxx_function_requires(_SameTypeConcept
<_Tp
, _ValueType
>)
2628 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
2629 __glibcxx_requires_partitioned(__first
, __last
, __val
);
2631 _DistanceType __len
= std::distance(__first
, __last
);
2632 _DistanceType __half
;
2633 _ForwardIterator __middle
;
2637 __half
= __len
>> 1;
2639 std::advance(__middle
, __half
);
2640 if (*__middle
< __val
)
2644 __len
= __len
- __half
- 1;
2653 * @brief Finds the first position in which @a val could be inserted
2654 * without changing the ordering.
2655 * @param first An iterator.
2656 * @param last Another iterator.
2657 * @param val The search term.
2658 * @param comp A functor to use for comparisons.
2659 * @return An iterator pointing to the first element "not less than" @a val,
2660 * or end() if every element is less than @a val.
2661 * @ingroup binarysearch
2663 * The comparison function should have the same effects on ordering as
2664 * the function used for the initial sort.
2666 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2668 lower_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2669 const _Tp
& __val
, _Compare __comp
)
2671 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2673 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2676 // concept requirements
2677 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2678 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2680 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
2682 _DistanceType __len
= std::distance(__first
, __last
);
2683 _DistanceType __half
;
2684 _ForwardIterator __middle
;
2688 __half
= __len
>> 1;
2690 std::advance(__middle
, __half
);
2691 if (__comp(*__middle
, __val
))
2695 __len
= __len
- __half
- 1;
2704 * @brief Finds the last position in which @a val could be inserted
2705 * without changing the ordering.
2706 * @param first An iterator.
2707 * @param last Another iterator.
2708 * @param val The search term.
2709 * @return An iterator pointing to the first element greater than @a val,
2710 * or end() if no elements are greater than @a val.
2711 * @ingroup binarysearch
2713 template<typename _ForwardIterator
, typename _Tp
>
2715 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2718 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2720 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2723 // concept requirements
2724 // See comments on lower_bound.
2725 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2726 __glibcxx_function_requires(_SameTypeConcept
<_Tp
, _ValueType
>)
2727 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
2728 __glibcxx_requires_partitioned(__first
, __last
, __val
);
2730 _DistanceType __len
= std::distance(__first
, __last
);
2731 _DistanceType __half
;
2732 _ForwardIterator __middle
;
2736 __half
= __len
>> 1;
2738 std::advance(__middle
, __half
);
2739 if (__val
< *__middle
)
2745 __len
= __len
- __half
- 1;
2752 * @brief Finds the last position in which @a val could be inserted
2753 * without changing the ordering.
2754 * @param first An iterator.
2755 * @param last Another iterator.
2756 * @param val The search term.
2757 * @param comp A functor to use for comparisons.
2758 * @return An iterator pointing to the first element greater than @a val,
2759 * or end() if no elements are greater than @a val.
2760 * @ingroup binarysearch
2762 * The comparison function should have the same effects on ordering as
2763 * the function used for the initial sort.
2765 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
2767 upper_bound(_ForwardIterator __first
, _ForwardIterator __last
,
2768 const _Tp
& __val
, _Compare __comp
)
2770 typedef typename iterator_traits
<_ForwardIterator
>::value_type
2772 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
2775 // concept requirements
2776 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
2777 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
2779 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
2781 _DistanceType __len
= std::distance(__first
, __last
);
2782 _DistanceType __half
;
2783 _ForwardIterator __middle
;
2787 __half
= __len
>> 1;
2789 std::advance(__middle
, __half
);
2790 if (__comp(__val
, *__middle
))
2796 __len
= __len
- __half
- 1;
2804 * This is a helper function for the merge routines.
2807 template<typename _BidirectionalIterator
, typename _Distance
>
2809 __merge_without_buffer(_BidirectionalIterator __first
,
2810 _BidirectionalIterator __middle
,
2811 _BidirectionalIterator __last
,
2812 _Distance __len1
, _Distance __len2
)
2814 if (__len1
== 0 || __len2
== 0)
2816 if (__len1
+ __len2
== 2)
2818 if (*__middle
< *__first
)
2819 std::iter_swap(__first
, __middle
);
2822 _BidirectionalIterator __first_cut
= __first
;
2823 _BidirectionalIterator __second_cut
= __middle
;
2824 _Distance __len11
= 0;
2825 _Distance __len22
= 0;
2826 if (__len1
> __len2
)
2828 __len11
= __len1
/ 2;
2829 std::advance(__first_cut
, __len11
);
2830 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
);
2831 __len22
= std::distance(__middle
, __second_cut
);
2835 __len22
= __len2
/ 2;
2836 std::advance(__second_cut
, __len22
);
2837 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
);
2838 __len11
= std::distance(__first
, __first_cut
);
2840 std::rotate(__first_cut
, __middle
, __second_cut
);
2841 _BidirectionalIterator __new_middle
= __first_cut
;
2842 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
2843 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
2845 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
2846 __len1
- __len11
, __len2
- __len22
);
2851 * This is a helper function for the merge routines.
2854 template<typename _BidirectionalIterator
, typename _Distance
,
2857 __merge_without_buffer(_BidirectionalIterator __first
,
2858 _BidirectionalIterator __middle
,
2859 _BidirectionalIterator __last
,
2860 _Distance __len1
, _Distance __len2
,
2863 if (__len1
== 0 || __len2
== 0)
2865 if (__len1
+ __len2
== 2)
2867 if (__comp(*__middle
, *__first
))
2868 std::iter_swap(__first
, __middle
);
2871 _BidirectionalIterator __first_cut
= __first
;
2872 _BidirectionalIterator __second_cut
= __middle
;
2873 _Distance __len11
= 0;
2874 _Distance __len22
= 0;
2875 if (__len1
> __len2
)
2877 __len11
= __len1
/ 2;
2878 std::advance(__first_cut
, __len11
);
2879 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
2881 __len22
= std::distance(__middle
, __second_cut
);
2885 __len22
= __len2
/ 2;
2886 std::advance(__second_cut
, __len22
);
2887 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
2889 __len11
= std::distance(__first
, __first_cut
);
2891 std::rotate(__first_cut
, __middle
, __second_cut
);
2892 _BidirectionalIterator __new_middle
= __first_cut
;
2893 std::advance(__new_middle
, std::distance(__middle
, __second_cut
));
2894 std::__merge_without_buffer(__first
, __first_cut
, __new_middle
,
2895 __len11
, __len22
, __comp
);
2896 std::__merge_without_buffer(__new_middle
, __second_cut
, __last
,
2897 __len1
- __len11
, __len2
- __len22
, __comp
);
2902 * This is a helper function for the stable sorting routines.
2905 template<typename _RandomAccessIterator
>
2907 __inplace_stable_sort(_RandomAccessIterator __first
,
2908 _RandomAccessIterator __last
)
2910 if (__last
- __first
< 15)
2912 std::__insertion_sort(__first
, __last
);
2915 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
2916 std::__inplace_stable_sort(__first
, __middle
);
2917 std::__inplace_stable_sort(__middle
, __last
);
2918 std::__merge_without_buffer(__first
, __middle
, __last
,
2925 * This is a helper function for the stable sorting routines.
2928 template<typename _RandomAccessIterator
, typename _Compare
>
2930 __inplace_stable_sort(_RandomAccessIterator __first
,
2931 _RandomAccessIterator __last
, _Compare __comp
)
2933 if (__last
- __first
< 15)
2935 std::__insertion_sort(__first
, __last
, __comp
);
2938 _RandomAccessIterator __middle
= __first
+ (__last
- __first
) / 2;
2939 std::__inplace_stable_sort(__first
, __middle
, __comp
);
2940 std::__inplace_stable_sort(__middle
, __last
, __comp
);
2941 std::__merge_without_buffer(__first
, __middle
, __last
,
2948 * @brief Merges two sorted ranges.
2949 * @param first1 An iterator.
2950 * @param first2 Another iterator.
2951 * @param last1 Another iterator.
2952 * @param last2 Another iterator.
2953 * @param result An iterator pointing to the end of the merged range.
2954 * @return An iterator pointing to the first element "not less than" @a val.
2956 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
2957 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
2958 * must be sorted, and the output range must not overlap with either of
2959 * the input ranges. The sort is @e stable, that is, for equivalent
2960 * elements in the two ranges, elements from the first range will always
2961 * come before elements from the second.
2963 template<typename _InputIterator1
, typename _InputIterator2
,
2964 typename _OutputIterator
>
2966 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
2967 _InputIterator2 __first2
, _InputIterator2 __last2
,
2968 _OutputIterator __result
)
2970 // concept requirements
2971 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
2972 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
2973 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
2974 typename iterator_traits
<_InputIterator1
>::value_type
>)
2975 __glibcxx_function_requires(_SameTypeConcept
<
2976 typename iterator_traits
<_InputIterator1
>::value_type
,
2977 typename iterator_traits
<_InputIterator2
>::value_type
>)
2978 __glibcxx_function_requires(_LessThanComparableConcept
<
2979 typename iterator_traits
<_InputIterator1
>::value_type
>)
2980 __glibcxx_requires_sorted(__first1
, __last1
);
2981 __glibcxx_requires_sorted(__first2
, __last2
);
2983 while (__first1
!= __last1
&& __first2
!= __last2
)
2985 if (*__first2
< *__first1
)
2987 *__result
= *__first2
;
2992 *__result
= *__first1
;
2997 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
3002 * @brief Merges two sorted ranges.
3003 * @param first1 An iterator.
3004 * @param first2 Another iterator.
3005 * @param last1 Another iterator.
3006 * @param last2 Another iterator.
3007 * @param result An iterator pointing to the end of the merged range.
3008 * @param comp A functor to use for comparisons.
3009 * @return An iterator pointing to the first element "not less than" @a val.
3011 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3012 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3013 * must be sorted, and the output range must not overlap with either of
3014 * the input ranges. The sort is @e stable, that is, for equivalent
3015 * elements in the two ranges, elements from the first range will always
3016 * come before elements from the second.
3018 * The comparison function should have the same effects on ordering as
3019 * the function used for the initial sort.
3021 template<typename _InputIterator1
, typename _InputIterator2
,
3022 typename _OutputIterator
, typename _Compare
>
3024 merge(_InputIterator1 __first1
, _InputIterator1 __last1
,
3025 _InputIterator2 __first2
, _InputIterator2 __last2
,
3026 _OutputIterator __result
, _Compare __comp
)
3028 // concept requirements
3029 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3030 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3031 __glibcxx_function_requires(_SameTypeConcept
<
3032 typename iterator_traits
<_InputIterator1
>::value_type
,
3033 typename iterator_traits
<_InputIterator2
>::value_type
>)
3034 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
3035 typename iterator_traits
<_InputIterator1
>::value_type
>)
3036 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3037 typename iterator_traits
<_InputIterator1
>::value_type
,
3038 typename iterator_traits
<_InputIterator2
>::value_type
>)
3039 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
3040 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
3042 while (__first1
!= __last1
&& __first2
!= __last2
)
3044 if (__comp(*__first2
, *__first1
))
3046 *__result
= *__first2
;
3051 *__result
= *__first1
;
3056 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
3060 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3063 __merge_sort_loop(_RandomAccessIterator1 __first
,
3064 _RandomAccessIterator1 __last
,
3065 _RandomAccessIterator2 __result
,
3066 _Distance __step_size
)
3068 const _Distance __two_step
= 2 * __step_size
;
3070 while (__last
- __first
>= __two_step
)
3072 __result
= std::merge(__first
, __first
+ __step_size
,
3073 __first
+ __step_size
, __first
+ __two_step
,
3075 __first
+= __two_step
;
3078 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3079 std::merge(__first
, __first
+ __step_size
, __first
+ __step_size
, __last
,
3083 template<typename _RandomAccessIterator1
, typename _RandomAccessIterator2
,
3084 typename _Distance
, typename _Compare
>
3086 __merge_sort_loop(_RandomAccessIterator1 __first
,
3087 _RandomAccessIterator1 __last
,
3088 _RandomAccessIterator2 __result
, _Distance __step_size
,
3091 const _Distance __two_step
= 2 * __step_size
;
3093 while (__last
- __first
>= __two_step
)
3095 __result
= std::merge(__first
, __first
+ __step_size
,
3096 __first
+ __step_size
, __first
+ __two_step
,
3099 __first
+= __two_step
;
3101 __step_size
= std::min(_Distance(__last
- __first
), __step_size
);
3103 std::merge(__first
, __first
+ __step_size
,
3104 __first
+ __step_size
, __last
,
3109 enum { _S_chunk_size
= 7 };
3111 template<typename _RandomAccessIterator
, typename _Distance
>
3113 __chunk_insertion_sort(_RandomAccessIterator __first
,
3114 _RandomAccessIterator __last
,
3115 _Distance __chunk_size
)
3117 while (__last
- __first
>= __chunk_size
)
3119 std::__insertion_sort(__first
, __first
+ __chunk_size
);
3120 __first
+= __chunk_size
;
3122 std::__insertion_sort(__first
, __last
);
3125 template<typename _RandomAccessIterator
, typename _Distance
, typename _Compare
>
3127 __chunk_insertion_sort(_RandomAccessIterator __first
,
3128 _RandomAccessIterator __last
,
3129 _Distance __chunk_size
, _Compare __comp
)
3131 while (__last
- __first
>= __chunk_size
)
3133 std::__insertion_sort(__first
, __first
+ __chunk_size
, __comp
);
3134 __first
+= __chunk_size
;
3136 std::__insertion_sort(__first
, __last
, __comp
);
3139 template<typename _RandomAccessIterator
, typename _Pointer
>
3141 __merge_sort_with_buffer(_RandomAccessIterator __first
,
3142 _RandomAccessIterator __last
,
3145 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3148 const _Distance __len
= __last
- __first
;
3149 const _Pointer __buffer_last
= __buffer
+ __len
;
3151 _Distance __step_size
= _S_chunk_size
;
3152 std::__chunk_insertion_sort(__first
, __last
, __step_size
);
3154 while (__step_size
< __len
)
3156 std::__merge_sort_loop(__first
, __last
, __buffer
, __step_size
);
3158 std::__merge_sort_loop(__buffer
, __buffer_last
, __first
, __step_size
);
3163 template<typename _RandomAccessIterator
, typename _Pointer
, typename _Compare
>
3165 __merge_sort_with_buffer(_RandomAccessIterator __first
,
3166 _RandomAccessIterator __last
,
3167 _Pointer __buffer
, _Compare __comp
)
3169 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3172 const _Distance __len
= __last
- __first
;
3173 const _Pointer __buffer_last
= __buffer
+ __len
;
3175 _Distance __step_size
= _S_chunk_size
;
3176 std::__chunk_insertion_sort(__first
, __last
, __step_size
, __comp
);
3178 while (__step_size
< __len
)
3180 std::__merge_sort_loop(__first
, __last
, __buffer
,
3181 __step_size
, __comp
);
3183 std::__merge_sort_loop(__buffer
, __buffer_last
, __first
,
3184 __step_size
, __comp
);
3191 * This is a helper function for the merge routines.
3194 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3195 typename _BidirectionalIterator3
>
3196 _BidirectionalIterator3
3197 __merge_backward(_BidirectionalIterator1 __first1
,
3198 _BidirectionalIterator1 __last1
,
3199 _BidirectionalIterator2 __first2
,
3200 _BidirectionalIterator2 __last2
,
3201 _BidirectionalIterator3 __result
)
3203 if (__first1
== __last1
)
3204 return std::copy_backward(__first2
, __last2
, __result
);
3205 if (__first2
== __last2
)
3206 return std::copy_backward(__first1
, __last1
, __result
);
3211 if (*__last2
< *__last1
)
3213 *--__result
= *__last1
;
3214 if (__first1
== __last1
)
3215 return std::copy_backward(__first2
, ++__last2
, __result
);
3220 *--__result
= *__last2
;
3221 if (__first2
== __last2
)
3222 return std::copy_backward(__first1
, ++__last1
, __result
);
3230 * This is a helper function for the merge routines.
3233 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3234 typename _BidirectionalIterator3
, typename _Compare
>
3235 _BidirectionalIterator3
3236 __merge_backward(_BidirectionalIterator1 __first1
,
3237 _BidirectionalIterator1 __last1
,
3238 _BidirectionalIterator2 __first2
,
3239 _BidirectionalIterator2 __last2
,
3240 _BidirectionalIterator3 __result
,
3243 if (__first1
== __last1
)
3244 return std::copy_backward(__first2
, __last2
, __result
);
3245 if (__first2
== __last2
)
3246 return std::copy_backward(__first1
, __last1
, __result
);
3251 if (__comp(*__last2
, *__last1
))
3253 *--__result
= *__last1
;
3254 if (__first1
== __last1
)
3255 return std::copy_backward(__first2
, ++__last2
, __result
);
3260 *--__result
= *__last2
;
3261 if (__first2
== __last2
)
3262 return std::copy_backward(__first1
, ++__last1
, __result
);
3270 * This is a helper function for the merge routines.
3273 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
3275 _BidirectionalIterator1
3276 __rotate_adaptive(_BidirectionalIterator1 __first
,
3277 _BidirectionalIterator1 __middle
,
3278 _BidirectionalIterator1 __last
,
3279 _Distance __len1
, _Distance __len2
,
3280 _BidirectionalIterator2 __buffer
,
3281 _Distance __buffer_size
)
3283 _BidirectionalIterator2 __buffer_end
;
3284 if (__len1
> __len2
&& __len2
<= __buffer_size
)
3286 __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3287 std::copy_backward(__first
, __middle
, __last
);
3288 return std::copy(__buffer
, __buffer_end
, __first
);
3290 else if (__len1
<= __buffer_size
)
3292 __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3293 std::copy(__middle
, __last
, __first
);
3294 return std::copy_backward(__buffer
, __buffer_end
, __last
);
3298 std::rotate(__first
, __middle
, __last
);
3299 std::advance(__first
, std::distance(__middle
, __last
));
3306 * This is a helper function for the merge routines.
3309 template<typename _BidirectionalIterator
, typename _Distance
,
3312 __merge_adaptive(_BidirectionalIterator __first
,
3313 _BidirectionalIterator __middle
,
3314 _BidirectionalIterator __last
,
3315 _Distance __len1
, _Distance __len2
,
3316 _Pointer __buffer
, _Distance __buffer_size
)
3318 if (__len1
<= __len2
&& __len1
<= __buffer_size
)
3320 _Pointer __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3321 std::merge(__buffer
, __buffer_end
, __middle
, __last
, __first
);
3323 else if (__len2
<= __buffer_size
)
3325 _Pointer __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3326 std::__merge_backward(__first
, __middle
, __buffer
,
3327 __buffer_end
, __last
);
3331 _BidirectionalIterator __first_cut
= __first
;
3332 _BidirectionalIterator __second_cut
= __middle
;
3333 _Distance __len11
= 0;
3334 _Distance __len22
= 0;
3335 if (__len1
> __len2
)
3337 __len11
= __len1
/ 2;
3338 std::advance(__first_cut
, __len11
);
3339 __second_cut
= std::lower_bound(__middle
, __last
,
3341 __len22
= std::distance(__middle
, __second_cut
);
3345 __len22
= __len2
/ 2;
3346 std::advance(__second_cut
, __len22
);
3347 __first_cut
= std::upper_bound(__first
, __middle
,
3349 __len11
= std::distance(__first
, __first_cut
);
3351 _BidirectionalIterator __new_middle
=
3352 std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
3353 __len1
- __len11
, __len22
, __buffer
,
3355 std::__merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
3356 __len22
, __buffer
, __buffer_size
);
3357 std::__merge_adaptive(__new_middle
, __second_cut
, __last
,
3359 __len2
- __len22
, __buffer
, __buffer_size
);
3365 * This is a helper function for the merge routines.
3368 template<typename _BidirectionalIterator
, typename _Distance
, typename _Pointer
,
3371 __merge_adaptive(_BidirectionalIterator __first
,
3372 _BidirectionalIterator __middle
,
3373 _BidirectionalIterator __last
,
3374 _Distance __len1
, _Distance __len2
,
3375 _Pointer __buffer
, _Distance __buffer_size
,
3378 if (__len1
<= __len2
&& __len1
<= __buffer_size
)
3380 _Pointer __buffer_end
= std::copy(__first
, __middle
, __buffer
);
3381 std::merge(__buffer
, __buffer_end
, __middle
, __last
, __first
, __comp
);
3383 else if (__len2
<= __buffer_size
)
3385 _Pointer __buffer_end
= std::copy(__middle
, __last
, __buffer
);
3386 std::__merge_backward(__first
, __middle
, __buffer
, __buffer_end
,
3391 _BidirectionalIterator __first_cut
= __first
;
3392 _BidirectionalIterator __second_cut
= __middle
;
3393 _Distance __len11
= 0;
3394 _Distance __len22
= 0;
3395 if (__len1
> __len2
)
3397 __len11
= __len1
/ 2;
3398 std::advance(__first_cut
, __len11
);
3399 __second_cut
= std::lower_bound(__middle
, __last
, *__first_cut
,
3401 __len22
= std::distance(__middle
, __second_cut
);
3405 __len22
= __len2
/ 2;
3406 std::advance(__second_cut
, __len22
);
3407 __first_cut
= std::upper_bound(__first
, __middle
, *__second_cut
,
3409 __len11
= std::distance(__first
, __first_cut
);
3411 _BidirectionalIterator __new_middle
=
3412 std::__rotate_adaptive(__first_cut
, __middle
, __second_cut
,
3413 __len1
- __len11
, __len22
, __buffer
,
3415 std::__merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
3416 __len22
, __buffer
, __buffer_size
, __comp
);
3417 std::__merge_adaptive(__new_middle
, __second_cut
, __last
,
3419 __len2
- __len22
, __buffer
,
3420 __buffer_size
, __comp
);
3425 * @brief Merges two sorted ranges in place.
3426 * @param first An iterator.
3427 * @param middle Another iterator.
3428 * @param last Another iterator.
3431 * Merges two sorted and consecutive ranges, [first,middle) and
3432 * [middle,last), and puts the result in [first,last). The output will
3433 * be sorted. The sort is @e stable, that is, for equivalent
3434 * elements in the two ranges, elements from the first range will always
3435 * come before elements from the second.
3437 * If enough additional memory is available, this takes (last-first)-1
3438 * comparisons. Otherwise an NlogN algorithm is used, where N is
3439 * distance(first,last).
3441 template<typename _BidirectionalIterator
>
3443 inplace_merge(_BidirectionalIterator __first
,
3444 _BidirectionalIterator __middle
,
3445 _BidirectionalIterator __last
)
3447 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3449 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3452 // concept requirements
3453 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3454 _BidirectionalIterator
>)
3455 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3456 __glibcxx_requires_sorted(__first
, __middle
);
3457 __glibcxx_requires_sorted(__middle
, __last
);
3459 if (__first
== __middle
|| __middle
== __last
)
3462 _DistanceType __len1
= std::distance(__first
, __middle
);
3463 _DistanceType __len2
= std::distance(__middle
, __last
);
3465 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3467 if (__buf
.begin() == 0)
3468 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
, __len2
);
3470 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3471 __buf
.begin(), _DistanceType(__buf
.size()));
3475 * @brief Merges two sorted ranges in place.
3476 * @param first An iterator.
3477 * @param middle Another iterator.
3478 * @param last Another iterator.
3479 * @param comp A functor to use for comparisons.
3482 * Merges two sorted and consecutive ranges, [first,middle) and
3483 * [middle,last), and puts the result in [first,last). The output will
3484 * be sorted. The sort is @e stable, that is, for equivalent
3485 * elements in the two ranges, elements from the first range will always
3486 * come before elements from the second.
3488 * If enough additional memory is available, this takes (last-first)-1
3489 * comparisons. Otherwise an NlogN algorithm is used, where N is
3490 * distance(first,last).
3492 * The comparison function should have the same effects on ordering as
3493 * the function used for the initial sort.
3495 template<typename _BidirectionalIterator
, typename _Compare
>
3497 inplace_merge(_BidirectionalIterator __first
,
3498 _BidirectionalIterator __middle
,
3499 _BidirectionalIterator __last
,
3502 typedef typename iterator_traits
<_BidirectionalIterator
>::value_type
3504 typedef typename iterator_traits
<_BidirectionalIterator
>::difference_type
3507 // concept requirements
3508 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept
<
3509 _BidirectionalIterator
>)
3510 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3511 _ValueType
, _ValueType
>)
3512 __glibcxx_requires_sorted_pred(__first
, __middle
, __comp
);
3513 __glibcxx_requires_sorted_pred(__middle
, __last
, __comp
);
3515 if (__first
== __middle
|| __middle
== __last
)
3518 const _DistanceType __len1
= std::distance(__first
, __middle
);
3519 const _DistanceType __len2
= std::distance(__middle
, __last
);
3521 _Temporary_buffer
<_BidirectionalIterator
, _ValueType
> __buf(__first
,
3523 if (__buf
.begin() == 0)
3524 std::__merge_without_buffer(__first
, __middle
, __last
, __len1
,
3527 std::__merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
3528 __buf
.begin(), _DistanceType(__buf
.size()),
3532 template<typename _RandomAccessIterator
, typename _Pointer
,
3535 __stable_sort_adaptive(_RandomAccessIterator __first
,
3536 _RandomAccessIterator __last
,
3537 _Pointer __buffer
, _Distance __buffer_size
)
3539 const _Distance __len
= (__last
- __first
+ 1) / 2;
3540 const _RandomAccessIterator __middle
= __first
+ __len
;
3541 if (__len
> __buffer_size
)
3543 std::__stable_sort_adaptive(__first
, __middle
,
3544 __buffer
, __buffer_size
);
3545 std::__stable_sort_adaptive(__middle
, __last
,
3546 __buffer
, __buffer_size
);
3550 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
);
3551 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
);
3553 std::__merge_adaptive(__first
, __middle
, __last
,
3554 _Distance(__middle
- __first
),
3555 _Distance(__last
- __middle
),
3556 __buffer
, __buffer_size
);
3559 template<typename _RandomAccessIterator
, typename _Pointer
,
3560 typename _Distance
, typename _Compare
>
3562 __stable_sort_adaptive(_RandomAccessIterator __first
,
3563 _RandomAccessIterator __last
,
3564 _Pointer __buffer
, _Distance __buffer_size
,
3567 const _Distance __len
= (__last
- __first
+ 1) / 2;
3568 const _RandomAccessIterator __middle
= __first
+ __len
;
3569 if (__len
> __buffer_size
)
3571 std::__stable_sort_adaptive(__first
, __middle
, __buffer
,
3572 __buffer_size
, __comp
);
3573 std::__stable_sort_adaptive(__middle
, __last
, __buffer
,
3574 __buffer_size
, __comp
);
3578 std::__merge_sort_with_buffer(__first
, __middle
, __buffer
, __comp
);
3579 std::__merge_sort_with_buffer(__middle
, __last
, __buffer
, __comp
);
3581 std::__merge_adaptive(__first
, __middle
, __last
,
3582 _Distance(__middle
- __first
),
3583 _Distance(__last
- __middle
),
3584 __buffer
, __buffer_size
,
3589 * @brief Sort the elements of a sequence, preserving the relative order
3590 * of equivalent elements.
3591 * @param first An iterator.
3592 * @param last Another iterator.
3595 * Sorts the elements in the range @p [first,last) in ascending order,
3596 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3597 * @p [first,last-1).
3599 * The relative ordering of equivalent elements is preserved, so any two
3600 * elements @p x and @p y in the range @p [first,last) such that
3601 * @p x<y is false and @p y<x is false will have the same relative
3602 * ordering after calling @p stable_sort().
3604 template<typename _RandomAccessIterator
>
3606 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
3608 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3610 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3613 // concept requirements
3614 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3615 _RandomAccessIterator
>)
3616 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3617 __glibcxx_requires_valid_range(__first
, __last
);
3619 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
>
3620 buf(__first
, __last
);
3621 if (buf
.begin() == 0)
3622 std::__inplace_stable_sort(__first
, __last
);
3624 std::__stable_sort_adaptive(__first
, __last
, buf
.begin(),
3625 _DistanceType(buf
.size()));
3629 * @brief Sort the elements of a sequence using a predicate for comparison,
3630 * preserving the relative order of equivalent elements.
3631 * @param first An iterator.
3632 * @param last Another iterator.
3633 * @param comp A comparison functor.
3636 * Sorts the elements in the range @p [first,last) in ascending order,
3637 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3638 * range @p [first,last-1).
3640 * The relative ordering of equivalent elements is preserved, so any two
3641 * elements @p x and @p y in the range @p [first,last) such that
3642 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
3643 * relative ordering after calling @p stable_sort().
3645 template<typename _RandomAccessIterator
, typename _Compare
>
3647 stable_sort(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
3650 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3652 typedef typename iterator_traits
<_RandomAccessIterator
>::difference_type
3655 // concept requirements
3656 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3657 _RandomAccessIterator
>)
3658 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3661 __glibcxx_requires_valid_range(__first
, __last
);
3663 _Temporary_buffer
<_RandomAccessIterator
, _ValueType
> buf(__first
, __last
);
3664 if (buf
.begin() == 0)
3665 std::__inplace_stable_sort(__first
, __last
, __comp
);
3667 std::__stable_sort_adaptive(__first
, __last
, buf
.begin(),
3668 _DistanceType(buf
.size()), __comp
);
3672 * @brief Sort a sequence just enough to find a particular position.
3673 * @param first An iterator.
3674 * @param nth Another iterator.
3675 * @param last Another iterator.
3678 * Rearranges the elements in the range @p [first,last) so that @p *nth
3679 * is the same element that would have been in that position had the
3680 * whole sequence been sorted.
3681 * whole sequence been sorted. The elements either side of @p *nth are
3682 * not completely sorted, but for any iterator @i in the range
3683 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3684 * holds that @p *j<*i is false.
3686 template<typename _RandomAccessIterator
>
3688 nth_element(_RandomAccessIterator __first
,
3689 _RandomAccessIterator __nth
,
3690 _RandomAccessIterator __last
)
3692 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3695 // concept requirements
3696 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3697 _RandomAccessIterator
>)
3698 __glibcxx_function_requires(_LessThanComparableConcept
<_ValueType
>)
3699 __glibcxx_requires_valid_range(__first
, __nth
);
3700 __glibcxx_requires_valid_range(__nth
, __last
);
3702 while (__last
- __first
> 3)
3704 _RandomAccessIterator __cut
=
3705 std::__unguarded_partition(__first
, __last
,
3706 _ValueType(std::__median(*__first
,
3718 std::__insertion_sort(__first
, __last
);
3722 * @brief Sort a sequence just enough to find a particular position
3723 * using a predicate for comparison.
3724 * @param first An iterator.
3725 * @param nth Another iterator.
3726 * @param last Another iterator.
3727 * @param comp A comparison functor.
3730 * Rearranges the elements in the range @p [first,last) so that @p *nth
3731 * is the same element that would have been in that position had the
3732 * whole sequence been sorted. The elements either side of @p *nth are
3733 * not completely sorted, but for any iterator @i in the range
3734 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3735 * holds that @p comp(*j,*i) is false.
3737 template<typename _RandomAccessIterator
, typename _Compare
>
3739 nth_element(_RandomAccessIterator __first
,
3740 _RandomAccessIterator __nth
,
3741 _RandomAccessIterator __last
,
3744 typedef typename iterator_traits
<_RandomAccessIterator
>::value_type
3747 // concept requirements
3748 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept
<
3749 _RandomAccessIterator
>)
3750 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3751 _ValueType
, _ValueType
>)
3752 __glibcxx_requires_valid_range(__first
, __nth
);
3753 __glibcxx_requires_valid_range(__nth
, __last
);
3755 while (__last
- __first
> 3)
3757 _RandomAccessIterator __cut
=
3758 std::__unguarded_partition(__first
, __last
,
3759 _ValueType(std::__median(*__first
,
3771 std::__insertion_sort(__first
, __last
, __comp
);
3775 * @brief Finds the largest subrange in which @a val could be inserted
3776 * at any place in it without changing the ordering.
3777 * @param first An iterator.
3778 * @param last Another iterator.
3779 * @param val The search term.
3780 * @return An pair of iterators defining the subrange.
3781 * @ingroup binarysearch
3783 * This is equivalent to
3785 * std::make_pair(lower_bound(first, last, val),
3786 * upper_bound(first, last, val))
3788 * but does not actually call those functions.
3790 template<typename _ForwardIterator
, typename _Tp
>
3791 pair
<_ForwardIterator
, _ForwardIterator
>
3792 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
3795 typedef typename iterator_traits
<_ForwardIterator
>::value_type
3797 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
3800 // concept requirements
3801 // See comments on lower_bound.
3802 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3803 __glibcxx_function_requires(_SameTypeConcept
<_Tp
, _ValueType
>)
3804 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
3805 __glibcxx_requires_partitioned(__first
, __last
, __val
);
3807 _DistanceType __len
= std::distance(__first
, __last
);
3808 _DistanceType __half
;
3809 _ForwardIterator __middle
, __left
, __right
;
3813 __half
= __len
>> 1;
3815 std::advance(__middle
, __half
);
3816 if (*__middle
< __val
)
3820 __len
= __len
- __half
- 1;
3822 else if (__val
< *__middle
)
3826 __left
= std::lower_bound(__first
, __middle
, __val
);
3827 std::advance(__first
, __len
);
3828 __right
= std::upper_bound(++__middle
, __first
, __val
);
3829 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
3832 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
3836 * @brief Finds the largest subrange in which @a val could be inserted
3837 * at any place in it without changing the ordering.
3838 * @param first An iterator.
3839 * @param last Another iterator.
3840 * @param val The search term.
3841 * @param comp A functor to use for comparisons.
3842 * @return An pair of iterators defining the subrange.
3843 * @ingroup binarysearch
3845 * This is equivalent to
3847 * std::make_pair(lower_bound(first, last, val, comp),
3848 * upper_bound(first, last, val, comp))
3850 * but does not actually call those functions.
3852 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
3853 pair
<_ForwardIterator
, _ForwardIterator
>
3854 equal_range(_ForwardIterator __first
, _ForwardIterator __last
,
3858 typedef typename iterator_traits
<_ForwardIterator
>::value_type
3860 typedef typename iterator_traits
<_ForwardIterator
>::difference_type
3863 // concept requirements
3864 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3865 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3867 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3869 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
3871 _DistanceType __len
= std::distance(__first
, __last
);
3872 _DistanceType __half
;
3873 _ForwardIterator __middle
, __left
, __right
;
3877 __half
= __len
>> 1;
3879 std::advance(__middle
, __half
);
3880 if (__comp(*__middle
, __val
))
3884 __len
= __len
- __half
- 1;
3886 else if (__comp(__val
, *__middle
))
3890 __left
= std::lower_bound(__first
, __middle
, __val
, __comp
);
3891 std::advance(__first
, __len
);
3892 __right
= std::upper_bound(++__middle
, __first
, __val
, __comp
);
3893 return pair
<_ForwardIterator
, _ForwardIterator
>(__left
, __right
);
3896 return pair
<_ForwardIterator
, _ForwardIterator
>(__first
, __first
);
3900 * @brief Determines whether an element exists in a range.
3901 * @param first An iterator.
3902 * @param last Another iterator.
3903 * @param val The search term.
3904 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3905 * @ingroup binarysearch
3907 * Note that this does not actually return an iterator to @a val. For
3908 * that, use std::find or a container's specialized find member functions.
3910 template<typename _ForwardIterator
, typename _Tp
>
3912 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
3915 // concept requirements
3916 // See comments on lower_bound.
3917 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3918 __glibcxx_function_requires(_SameTypeConcept
<_Tp
,
3919 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3920 __glibcxx_function_requires(_LessThanComparableConcept
<_Tp
>)
3921 __glibcxx_requires_partitioned(__first
, __last
, __val
);
3923 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
);
3924 return __i
!= __last
&& !(__val
< *__i
);
3928 * @brief Determines whether an element exists in a range.
3929 * @param first An iterator.
3930 * @param last Another iterator.
3931 * @param val The search term.
3932 * @param comp A functor to use for comparisons.
3933 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3934 * @ingroup binarysearch
3936 * Note that this does not actually return an iterator to @a val. For
3937 * that, use std::find or a container's specialized find member functions.
3939 * The comparison function should have the same effects on ordering as
3940 * the function used for the initial sort.
3942 template<typename _ForwardIterator
, typename _Tp
, typename _Compare
>
3944 binary_search(_ForwardIterator __first
, _ForwardIterator __last
,
3945 const _Tp
& __val
, _Compare __comp
)
3947 // concept requirements
3948 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
3949 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
3950 typename iterator_traits
<_ForwardIterator
>::value_type
, _Tp
>)
3951 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
, _Tp
,
3952 typename iterator_traits
<_ForwardIterator
>::value_type
>)
3953 __glibcxx_requires_partitioned_pred(__first
, __last
, __val
, __comp
);
3955 _ForwardIterator __i
= std::lower_bound(__first
, __last
, __val
, __comp
);
3956 return __i
!= __last
&& !__comp(__val
, *__i
);
3959 // Set algorithms: includes, set_union, set_intersection, set_difference,
3960 // set_symmetric_difference. All of these algorithms have the precondition
3961 // that their input ranges are sorted and the postcondition that their output
3962 // ranges are sorted.
3965 * @brief Determines whether all elements of a sequence exists in a range.
3966 * @param first1 Start of search range.
3967 * @param last1 End of search range.
3968 * @param first2 Start of sequence
3969 * @param last2 End of sequence.
3970 * @return True if each element in [first2,last2) is contained in order
3971 * within [first1,last1). False otherwise.
3972 * @ingroup setoperations
3974 * This operation expects both [first1,last1) and [first2,last2) to be
3975 * sorted. Searches for the presence of each element in [first2,last2)
3976 * within [first1,last1). The iterators over each range only move forward,
3977 * so this is a linear algorithm. If an element in [first2,last2) is not
3978 * found before the search iterator reaches @a last2, false is returned.
3980 template<typename _InputIterator1
, typename _InputIterator2
>
3982 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
3983 _InputIterator2 __first2
, _InputIterator2 __last2
)
3985 // concept requirements
3986 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
3987 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
3988 __glibcxx_function_requires(_SameTypeConcept
<
3989 typename iterator_traits
<_InputIterator1
>::value_type
,
3990 typename iterator_traits
<_InputIterator2
>::value_type
>)
3991 __glibcxx_function_requires(_LessThanComparableConcept
<
3992 typename iterator_traits
<_InputIterator1
>::value_type
>)
3993 __glibcxx_requires_sorted(__first1
, __last1
);
3994 __glibcxx_requires_sorted(__first2
, __last2
);
3996 while (__first1
!= __last1
&& __first2
!= __last2
)
3997 if (*__first2
< *__first1
)
3999 else if(*__first1
< *__first2
)
4002 ++__first1
, ++__first2
;
4004 return __first2
== __last2
;
4008 * @brief Determines whether all elements of a sequence exists in a range
4010 * @param first1 Start of search range.
4011 * @param last1 End of search range.
4012 * @param first2 Start of sequence
4013 * @param last2 End of sequence.
4014 * @param comp Comparison function to use.
4015 * @return True if each element in [first2,last2) is contained in order
4016 * within [first1,last1) according to comp. False otherwise.
4017 * @ingroup setoperations
4019 * This operation expects both [first1,last1) and [first2,last2) to be
4020 * sorted. Searches for the presence of each element in [first2,last2)
4021 * within [first1,last1), using comp to decide. The iterators over each
4022 * range only move forward, so this is a linear algorithm. If an element
4023 * in [first2,last2) is not found before the search iterator reaches @a
4024 * last2, false is returned.
4026 template<typename _InputIterator1
, typename _InputIterator2
,
4029 includes(_InputIterator1 __first1
, _InputIterator1 __last1
,
4030 _InputIterator2 __first2
, _InputIterator2 __last2
, _Compare __comp
)
4032 // concept requirements
4033 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4034 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4035 __glibcxx_function_requires(_SameTypeConcept
<
4036 typename iterator_traits
<_InputIterator1
>::value_type
,
4037 typename iterator_traits
<_InputIterator2
>::value_type
>)
4038 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4039 typename iterator_traits
<_InputIterator1
>::value_type
,
4040 typename iterator_traits
<_InputIterator2
>::value_type
>)
4041 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4042 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4044 while (__first1
!= __last1
&& __first2
!= __last2
)
4045 if (__comp(*__first2
, *__first1
))
4047 else if(__comp(*__first1
, *__first2
))
4050 ++__first1
, ++__first2
;
4052 return __first2
== __last2
;
4056 * @brief Return the union of two sorted ranges.
4057 * @param first1 Start of first range.
4058 * @param last1 End of first range.
4059 * @param first2 Start of second range.
4060 * @param last2 End of second range.
4061 * @return End of the output range.
4062 * @ingroup setoperations
4064 * This operation iterates over both ranges, copying elements present in
4065 * each range in order to the output range. Iterators increment for each
4066 * range. When the current element of one range is less than the other,
4067 * that element is copied and the iterator advanced. If an element is
4068 * contained in both ranges, the element from the first range is copied and
4069 * both ranges advance. The output range may not overlap either input
4072 template<typename _InputIterator1
, typename _InputIterator2
,
4073 typename _OutputIterator
>
4075 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
4076 _InputIterator2 __first2
, _InputIterator2 __last2
,
4077 _OutputIterator __result
)
4079 // concept requirements
4080 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4081 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4082 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4083 typename iterator_traits
<_InputIterator1
>::value_type
>)
4084 __glibcxx_function_requires(_SameTypeConcept
<
4085 typename iterator_traits
<_InputIterator1
>::value_type
,
4086 typename iterator_traits
<_InputIterator2
>::value_type
>)
4087 __glibcxx_function_requires(_LessThanComparableConcept
<
4088 typename iterator_traits
<_InputIterator1
>::value_type
>)
4089 __glibcxx_requires_sorted(__first1
, __last1
);
4090 __glibcxx_requires_sorted(__first2
, __last2
);
4092 while (__first1
!= __last1
&& __first2
!= __last2
)
4094 if (*__first1
< *__first2
)
4096 *__result
= *__first1
;
4099 else if (*__first2
< *__first1
)
4101 *__result
= *__first2
;
4106 *__result
= *__first1
;
4112 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
4117 * @brief Return the union of two sorted ranges using a comparison functor.
4118 * @param first1 Start of first range.
4119 * @param last1 End of first range.
4120 * @param first2 Start of second range.
4121 * @param last2 End of second range.
4122 * @param comp The comparison functor.
4123 * @return End of the output range.
4124 * @ingroup setoperations
4126 * This operation iterates over both ranges, copying elements present in
4127 * each range in order to the output range. Iterators increment for each
4128 * range. When the current element of one range is less than the other
4129 * according to @a comp, that element is copied and the iterator advanced.
4130 * If an equivalent element according to @a comp is contained in both
4131 * ranges, the element from the first range is copied and both ranges
4132 * advance. The output range may not overlap either input range.
4134 template<typename _InputIterator1
, typename _InputIterator2
,
4135 typename _OutputIterator
, typename _Compare
>
4137 set_union(_InputIterator1 __first1
, _InputIterator1 __last1
,
4138 _InputIterator2 __first2
, _InputIterator2 __last2
,
4139 _OutputIterator __result
, _Compare __comp
)
4141 // concept requirements
4142 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4143 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4144 __glibcxx_function_requires(_SameTypeConcept
<
4145 typename iterator_traits
<_InputIterator1
>::value_type
,
4146 typename iterator_traits
<_InputIterator2
>::value_type
>)
4147 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4148 typename iterator_traits
<_InputIterator1
>::value_type
>)
4149 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4150 typename iterator_traits
<_InputIterator1
>::value_type
,
4151 typename iterator_traits
<_InputIterator2
>::value_type
>)
4152 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4153 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4155 while (__first1
!= __last1
&& __first2
!= __last2
)
4157 if (__comp(*__first1
, *__first2
))
4159 *__result
= *__first1
;
4162 else if (__comp(*__first2
, *__first1
))
4164 *__result
= *__first2
;
4169 *__result
= *__first1
;
4175 return std::copy(__first2
, __last2
, std::copy(__first1
, __last1
,
4180 * @brief Return the intersection of two sorted ranges.
4181 * @param first1 Start of first range.
4182 * @param last1 End of first range.
4183 * @param first2 Start of second range.
4184 * @param last2 End of second range.
4185 * @return End of the output range.
4186 * @ingroup setoperations
4188 * This operation iterates over both ranges, copying elements present in
4189 * both ranges in order to the output range. Iterators increment for each
4190 * range. When the current element of one range is less than the other,
4191 * that iterator advances. If an element is contained in both ranges, the
4192 * element from the first range is copied and both ranges advance. The
4193 * output range may not overlap either input range.
4195 template<typename _InputIterator1
, typename _InputIterator2
,
4196 typename _OutputIterator
>
4198 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
4199 _InputIterator2 __first2
, _InputIterator2 __last2
,
4200 _OutputIterator __result
)
4202 // concept requirements
4203 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4204 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4205 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4206 typename iterator_traits
<_InputIterator1
>::value_type
>)
4207 __glibcxx_function_requires(_SameTypeConcept
<
4208 typename iterator_traits
<_InputIterator1
>::value_type
,
4209 typename iterator_traits
<_InputIterator2
>::value_type
>)
4210 __glibcxx_function_requires(_LessThanComparableConcept
<
4211 typename iterator_traits
<_InputIterator1
>::value_type
>)
4212 __glibcxx_requires_sorted(__first1
, __last1
);
4213 __glibcxx_requires_sorted(__first2
, __last2
);
4215 while (__first1
!= __last1
&& __first2
!= __last2
)
4216 if (*__first1
< *__first2
)
4218 else if (*__first2
< *__first1
)
4222 *__result
= *__first1
;
4231 * @brief Return the intersection of two sorted ranges using comparison
4233 * @param first1 Start of first range.
4234 * @param last1 End of first range.
4235 * @param first2 Start of second range.
4236 * @param last2 End of second range.
4237 * @param comp The comparison functor.
4238 * @return End of the output range.
4239 * @ingroup setoperations
4241 * This operation iterates over both ranges, copying elements present in
4242 * both ranges in order to the output range. Iterators increment for each
4243 * range. When the current element of one range is less than the other
4244 * according to @a comp, that iterator advances. If an element is
4245 * contained in both ranges according to @a comp, the element from the
4246 * first range is copied and both ranges advance. The output range may not
4247 * overlap either input range.
4249 template<typename _InputIterator1
, typename _InputIterator2
,
4250 typename _OutputIterator
, typename _Compare
>
4252 set_intersection(_InputIterator1 __first1
, _InputIterator1 __last1
,
4253 _InputIterator2 __first2
, _InputIterator2 __last2
,
4254 _OutputIterator __result
, _Compare __comp
)
4256 // concept requirements
4257 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4258 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4259 __glibcxx_function_requires(_SameTypeConcept
<
4260 typename iterator_traits
<_InputIterator1
>::value_type
,
4261 typename iterator_traits
<_InputIterator2
>::value_type
>)
4262 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4263 typename iterator_traits
<_InputIterator1
>::value_type
>)
4264 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4265 typename iterator_traits
<_InputIterator1
>::value_type
,
4266 typename iterator_traits
<_InputIterator2
>::value_type
>)
4267 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4268 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4270 while (__first1
!= __last1
&& __first2
!= __last2
)
4271 if (__comp(*__first1
, *__first2
))
4273 else if (__comp(*__first2
, *__first1
))
4277 *__result
= *__first1
;
4286 * @brief Return the difference of two sorted ranges.
4287 * @param first1 Start of first range.
4288 * @param last1 End of first range.
4289 * @param first2 Start of second range.
4290 * @param last2 End of second range.
4291 * @return End of the output range.
4292 * @ingroup setoperations
4294 * This operation iterates over both ranges, copying elements present in
4295 * the first range but not the second in order to the output range.
4296 * Iterators increment for each range. When the current element of the
4297 * first range is less than the second, that element is copied and the
4298 * iterator advances. If the current element of the second range is less,
4299 * the iterator advances, but no element is copied. If an element is
4300 * contained in both ranges, no elements are copied and both ranges
4301 * advance. The output range may not overlap either input range.
4303 template<typename _InputIterator1
, typename _InputIterator2
,
4304 typename _OutputIterator
>
4306 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4307 _InputIterator2 __first2
, _InputIterator2 __last2
,
4308 _OutputIterator __result
)
4310 // concept requirements
4311 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4312 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4313 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4314 typename iterator_traits
<_InputIterator1
>::value_type
>)
4315 __glibcxx_function_requires(_SameTypeConcept
<
4316 typename iterator_traits
<_InputIterator1
>::value_type
,
4317 typename iterator_traits
<_InputIterator2
>::value_type
>)
4318 __glibcxx_function_requires(_LessThanComparableConcept
<
4319 typename iterator_traits
<_InputIterator1
>::value_type
>)
4320 __glibcxx_requires_sorted(__first1
, __last1
);
4321 __glibcxx_requires_sorted(__first2
, __last2
);
4323 while (__first1
!= __last1
&& __first2
!= __last2
)
4324 if (*__first1
< *__first2
)
4326 *__result
= *__first1
;
4330 else if (*__first2
< *__first1
)
4337 return std::copy(__first1
, __last1
, __result
);
4341 * @brief Return the difference of two sorted ranges using comparison
4343 * @param first1 Start of first range.
4344 * @param last1 End of first range.
4345 * @param first2 Start of second range.
4346 * @param last2 End of second range.
4347 * @param comp The comparison functor.
4348 * @return End of the output range.
4349 * @ingroup setoperations
4351 * This operation iterates over both ranges, copying elements present in
4352 * the first range but not the second in order to the output range.
4353 * Iterators increment for each range. When the current element of the
4354 * first range is less than the second according to @a comp, that element
4355 * is copied and the iterator advances. If the current element of the
4356 * second range is less, no element is copied and the iterator advances.
4357 * If an element is contained in both ranges according to @a comp, no
4358 * elements are copied and both ranges advance. The output range may not
4359 * overlap either input range.
4361 template<typename _InputIterator1
, typename _InputIterator2
,
4362 typename _OutputIterator
, typename _Compare
>
4364 set_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4365 _InputIterator2 __first2
, _InputIterator2 __last2
,
4366 _OutputIterator __result
, _Compare __comp
)
4368 // concept requirements
4369 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4370 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4371 __glibcxx_function_requires(_SameTypeConcept
<
4372 typename iterator_traits
<_InputIterator1
>::value_type
,
4373 typename iterator_traits
<_InputIterator2
>::value_type
>)
4374 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4375 typename iterator_traits
<_InputIterator1
>::value_type
>)
4376 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4377 typename iterator_traits
<_InputIterator1
>::value_type
,
4378 typename iterator_traits
<_InputIterator2
>::value_type
>)
4379 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4380 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4382 while (__first1
!= __last1
&& __first2
!= __last2
)
4383 if (__comp(*__first1
, *__first2
))
4385 *__result
= *__first1
;
4389 else if (__comp(*__first2
, *__first1
))
4396 return std::copy(__first1
, __last1
, __result
);
4400 * @brief Return the symmetric difference of two sorted ranges.
4401 * @param first1 Start of first range.
4402 * @param last1 End of first range.
4403 * @param first2 Start of second range.
4404 * @param last2 End of second range.
4405 * @return End of the output range.
4406 * @ingroup setoperations
4408 * This operation iterates over both ranges, copying elements present in
4409 * one range but not the other in order to the output range. Iterators
4410 * increment for each range. When the current element of one range is less
4411 * than the other, that element is copied and the iterator advances. If an
4412 * element is contained in both ranges, no elements are copied and both
4413 * ranges advance. The output range may not overlap either input range.
4415 template<typename _InputIterator1
, typename _InputIterator2
,
4416 typename _OutputIterator
>
4418 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4419 _InputIterator2 __first2
, _InputIterator2 __last2
,
4420 _OutputIterator __result
)
4422 // concept requirements
4423 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4424 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4425 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4426 typename iterator_traits
<_InputIterator1
>::value_type
>)
4427 __glibcxx_function_requires(_SameTypeConcept
<
4428 typename iterator_traits
<_InputIterator1
>::value_type
,
4429 typename iterator_traits
<_InputIterator2
>::value_type
>)
4430 __glibcxx_function_requires(_LessThanComparableConcept
<
4431 typename iterator_traits
<_InputIterator1
>::value_type
>)
4432 __glibcxx_requires_sorted(__first1
, __last1
);
4433 __glibcxx_requires_sorted(__first2
, __last2
);
4435 while (__first1
!= __last1
&& __first2
!= __last2
)
4436 if (*__first1
< *__first2
)
4438 *__result
= *__first1
;
4442 else if (*__first2
< *__first1
)
4444 *__result
= *__first2
;
4453 return std::copy(__first2
, __last2
, std::copy(__first1
,
4454 __last1
, __result
));
4458 * @brief Return the symmetric difference of two sorted ranges using
4459 * comparison functor.
4460 * @param first1 Start of first range.
4461 * @param last1 End of first range.
4462 * @param first2 Start of second range.
4463 * @param last2 End of second range.
4464 * @param comp The comparison functor.
4465 * @return End of the output range.
4466 * @ingroup setoperations
4468 * This operation iterates over both ranges, copying elements present in
4469 * one range but not the other in order to the output range. Iterators
4470 * increment for each range. When the current element of one range is less
4471 * than the other according to @a comp, that element is copied and the
4472 * iterator advances. If an element is contained in both ranges according
4473 * to @a comp, no elements are copied and both ranges advance. The output
4474 * range may not overlap either input range.
4476 template<typename _InputIterator1
, typename _InputIterator2
,
4477 typename _OutputIterator
, typename _Compare
>
4479 set_symmetric_difference(_InputIterator1 __first1
, _InputIterator1 __last1
,
4480 _InputIterator2 __first2
, _InputIterator2 __last2
,
4481 _OutputIterator __result
,
4484 // concept requirements
4485 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator1
>)
4486 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator2
>)
4487 __glibcxx_function_requires(_SameTypeConcept
<
4488 typename iterator_traits
<_InputIterator1
>::value_type
,
4489 typename iterator_traits
<_InputIterator2
>::value_type
>)
4490 __glibcxx_function_requires(_OutputIteratorConcept
<_OutputIterator
,
4491 typename iterator_traits
<_InputIterator1
>::value_type
>)
4492 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4493 typename iterator_traits
<_InputIterator1
>::value_type
,
4494 typename iterator_traits
<_InputIterator2
>::value_type
>)
4495 __glibcxx_requires_sorted_pred(__first1
, __last1
, __comp
);
4496 __glibcxx_requires_sorted_pred(__first2
, __last2
, __comp
);
4498 while (__first1
!= __last1
&& __first2
!= __last2
)
4499 if (__comp(*__first1
, *__first2
))
4501 *__result
= *__first1
;
4505 else if (__comp(*__first2
, *__first1
))
4507 *__result
= *__first2
;
4516 return std::copy(__first2
, __last2
, std::copy(__first1
,
4517 __last1
, __result
));
4520 // min_element and max_element, with and without an explicitly supplied
4521 // comparison function.
4524 * @brief Return the maximum element in a range.
4525 * @param first Start of range.
4526 * @param last End of range.
4527 * @return Iterator referencing the first instance of the largest value.
4529 template<typename _ForwardIterator
>
4531 max_element(_ForwardIterator __first
, _ForwardIterator __last
)
4533 // concept requirements
4534 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4535 __glibcxx_function_requires(_LessThanComparableConcept
<
4536 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4537 __glibcxx_requires_valid_range(__first
, __last
);
4539 if (__first
== __last
)
4541 _ForwardIterator __result
= __first
;
4542 while (++__first
!= __last
)
4543 if (*__result
< *__first
)
4549 * @brief Return the maximum element in a range using comparison functor.
4550 * @param first Start of range.
4551 * @param last End of range.
4552 * @param comp Comparison functor.
4553 * @return Iterator referencing the first instance of the largest value
4554 * according to comp.
4556 template<typename _ForwardIterator
, typename _Compare
>
4558 max_element(_ForwardIterator __first
, _ForwardIterator __last
,
4561 // concept requirements
4562 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4563 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4564 typename iterator_traits
<_ForwardIterator
>::value_type
,
4565 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4566 __glibcxx_requires_valid_range(__first
, __last
);
4568 if (__first
== __last
) return __first
;
4569 _ForwardIterator __result
= __first
;
4570 while (++__first
!= __last
)
4571 if (__comp(*__result
, *__first
)) __result
= __first
;
4576 * @brief Return the minimum element in a range.
4577 * @param first Start of range.
4578 * @param last End of range.
4579 * @return Iterator referencing the first instance of the smallest value.
4581 template<typename _ForwardIterator
>
4583 min_element(_ForwardIterator __first
, _ForwardIterator __last
)
4585 // concept requirements
4586 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4587 __glibcxx_function_requires(_LessThanComparableConcept
<
4588 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4589 __glibcxx_requires_valid_range(__first
, __last
);
4591 if (__first
== __last
)
4593 _ForwardIterator __result
= __first
;
4594 while (++__first
!= __last
)
4595 if (*__first
< *__result
)
4601 * @brief Return the minimum element in a range using comparison functor.
4602 * @param first Start of range.
4603 * @param last End of range.
4604 * @param comp Comparison functor.
4605 * @return Iterator referencing the first instance of the smallest value
4606 * according to comp.
4608 template<typename _ForwardIterator
, typename _Compare
>
4610 min_element(_ForwardIterator __first
, _ForwardIterator __last
,
4613 // concept requirements
4614 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4615 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4616 typename iterator_traits
<_ForwardIterator
>::value_type
,
4617 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4618 __glibcxx_requires_valid_range(__first
, __last
);
4620 if (__first
== __last
)
4622 _ForwardIterator __result
= __first
;
4623 while (++__first
!= __last
)
4624 if (__comp(*__first
, *__result
))
4629 // next_permutation and prev_permutation, with and without an explicitly
4630 // supplied comparison function.
4633 * @brief Permute range into the next "dictionary" ordering.
4634 * @param first Start of range.
4635 * @param last End of range.
4636 * @return False if wrapped to first permutation, true otherwise.
4638 * Treats all permutations of the range as a set of "dictionary" sorted
4639 * sequences. Permutes the current sequence into the next one of this set.
4640 * Returns true if there are more sequences to generate. If the sequence
4641 * is the largest of the set, the smallest is generated and false returned.
4643 template<typename _BidirectionalIterator
>
4645 next_permutation(_BidirectionalIterator __first
,
4646 _BidirectionalIterator __last
)
4648 // concept requirements
4649 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
4650 _BidirectionalIterator
>)
4651 __glibcxx_function_requires(_LessThanComparableConcept
<
4652 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
4653 __glibcxx_requires_valid_range(__first
, __last
);
4655 if (__first
== __last
)
4657 _BidirectionalIterator __i
= __first
;
4666 _BidirectionalIterator __ii
= __i
;
4670 _BidirectionalIterator __j
= __last
;
4671 while (!(*__i
< *--__j
))
4673 std::iter_swap(__i
, __j
);
4674 std::reverse(__ii
, __last
);
4679 std::reverse(__first
, __last
);
4686 * @brief Permute range into the next "dictionary" ordering using
4687 * comparison functor.
4688 * @param first Start of range.
4689 * @param last End of range.
4691 * @return False if wrapped to first permutation, true otherwise.
4693 * Treats all permutations of the range [first,last) as a set of
4694 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4695 * sequence into the next one of this set. Returns true if there are more
4696 * sequences to generate. If the sequence is the largest of the set, the
4697 * smallest is generated and false returned.
4699 template<typename _BidirectionalIterator
, typename _Compare
>
4701 next_permutation(_BidirectionalIterator __first
,
4702 _BidirectionalIterator __last
, _Compare __comp
)
4704 // concept requirements
4705 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
4706 _BidirectionalIterator
>)
4707 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4708 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
4709 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
4710 __glibcxx_requires_valid_range(__first
, __last
);
4712 if (__first
== __last
)
4714 _BidirectionalIterator __i
= __first
;
4723 _BidirectionalIterator __ii
= __i
;
4725 if (__comp(*__i
, *__ii
))
4727 _BidirectionalIterator __j
= __last
;
4728 while (!__comp(*__i
, *--__j
))
4730 std::iter_swap(__i
, __j
);
4731 std::reverse(__ii
, __last
);
4736 std::reverse(__first
, __last
);
4743 * @brief Permute range into the previous "dictionary" ordering.
4744 * @param first Start of range.
4745 * @param last End of range.
4746 * @return False if wrapped to last permutation, true otherwise.
4748 * Treats all permutations of the range as a set of "dictionary" sorted
4749 * sequences. Permutes the current sequence into the previous one of this
4750 * set. Returns true if there are more sequences to generate. If the
4751 * sequence is the smallest of the set, the largest is generated and false
4754 template<typename _BidirectionalIterator
>
4756 prev_permutation(_BidirectionalIterator __first
,
4757 _BidirectionalIterator __last
)
4759 // concept requirements
4760 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
4761 _BidirectionalIterator
>)
4762 __glibcxx_function_requires(_LessThanComparableConcept
<
4763 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
4764 __glibcxx_requires_valid_range(__first
, __last
);
4766 if (__first
== __last
)
4768 _BidirectionalIterator __i
= __first
;
4777 _BidirectionalIterator __ii
= __i
;
4781 _BidirectionalIterator __j
= __last
;
4782 while (!(*--__j
< *__i
))
4784 std::iter_swap(__i
, __j
);
4785 std::reverse(__ii
, __last
);
4790 std::reverse(__first
, __last
);
4797 * @brief Permute range into the previous "dictionary" ordering using
4798 * comparison functor.
4799 * @param first Start of range.
4800 * @param last End of range.
4802 * @return False if wrapped to last permutation, true otherwise.
4804 * Treats all permutations of the range [first,last) as a set of
4805 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4806 * sequence into the previous one of this set. Returns true if there are
4807 * more sequences to generate. If the sequence is the smallest of the set,
4808 * the largest is generated and false returned.
4810 template<typename _BidirectionalIterator
, typename _Compare
>
4812 prev_permutation(_BidirectionalIterator __first
,
4813 _BidirectionalIterator __last
, _Compare __comp
)
4815 // concept requirements
4816 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
4817 _BidirectionalIterator
>)
4818 __glibcxx_function_requires(_BinaryPredicateConcept
<_Compare
,
4819 typename iterator_traits
<_BidirectionalIterator
>::value_type
,
4820 typename iterator_traits
<_BidirectionalIterator
>::value_type
>)
4821 __glibcxx_requires_valid_range(__first
, __last
);
4823 if (__first
== __last
)
4825 _BidirectionalIterator __i
= __first
;
4834 _BidirectionalIterator __ii
= __i
;
4836 if (__comp(*__ii
, *__i
))
4838 _BidirectionalIterator __j
= __last
;
4839 while (!__comp(*--__j
, *__i
))
4841 std::iter_swap(__i
, __j
);
4842 std::reverse(__ii
, __last
);
4847 std::reverse(__first
, __last
);
4853 // find_first_of, with and without an explicitly supplied comparison function.
4856 * @brief Find element from a set in a sequence.
4857 * @param first1 Start of range to search.
4858 * @param last1 End of range to search.
4859 * @param first2 Start of match candidates.
4860 * @param last2 End of match candidates.
4861 * @return The first iterator @c i in the range
4862 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
4863 * interator in [first2,last2), or @p last1 if no such iterator exists.
4865 * Searches the range @p [first1,last1) for an element that is equal to
4866 * some element in the range [first2,last2). If found, returns an iterator
4867 * in the range [first1,last1), otherwise returns @p last1.
4869 template<typename _InputIterator
, typename _ForwardIterator
>
4871 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
4872 _ForwardIterator __first2
, _ForwardIterator __last2
)
4874 // concept requirements
4875 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4876 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4877 __glibcxx_function_requires(_EqualOpConcept
<
4878 typename iterator_traits
<_InputIterator
>::value_type
,
4879 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4880 __glibcxx_requires_valid_range(__first1
, __last1
);
4881 __glibcxx_requires_valid_range(__first2
, __last2
);
4883 for ( ; __first1
!= __last1
; ++__first1
)
4884 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
4885 if (*__first1
== *__iter
)
4891 * @brief Find element from a set in a sequence using a predicate.
4892 * @param first1 Start of range to search.
4893 * @param last1 End of range to search.
4894 * @param first2 Start of match candidates.
4895 * @param last2 End of match candidates.
4896 * @param comp Predicate to use.
4897 * @return The first iterator @c i in the range
4898 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
4899 * interator in [first2,last2), or @p last1 if no such iterator exists.
4901 * Searches the range @p [first1,last1) for an element that is equal to
4902 * some element in the range [first2,last2). If found, returns an iterator in
4903 * the range [first1,last1), otherwise returns @p last1.
4905 template<typename _InputIterator
, typename _ForwardIterator
,
4906 typename _BinaryPredicate
>
4908 find_first_of(_InputIterator __first1
, _InputIterator __last1
,
4909 _ForwardIterator __first2
, _ForwardIterator __last2
,
4910 _BinaryPredicate __comp
)
4912 // concept requirements
4913 __glibcxx_function_requires(_InputIteratorConcept
<_InputIterator
>)
4914 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator
>)
4915 __glibcxx_function_requires(_EqualOpConcept
<
4916 typename iterator_traits
<_InputIterator
>::value_type
,
4917 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4918 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
4919 typename iterator_traits
<_InputIterator
>::value_type
,
4920 typename iterator_traits
<_ForwardIterator
>::value_type
>)
4921 __glibcxx_requires_valid_range(__first1
, __last1
);
4922 __glibcxx_requires_valid_range(__first2
, __last2
);
4924 for ( ; __first1
!= __last1
; ++__first1
)
4925 for (_ForwardIterator __iter
= __first2
; __iter
!= __last2
; ++__iter
)
4926 if (__comp(*__first1
, *__iter
))
4932 // find_end, with and without an explicitly supplied comparison function.
4933 // Search [first2, last2) as a subsequence in [first1, last1), and return
4934 // the *last* possible match. Note that find_end for bidirectional iterators
4935 // is much faster than for forward iterators.
4937 // find_end for forward iterators.
4938 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
4940 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
4941 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
4942 forward_iterator_tag
, forward_iterator_tag
)
4944 if (__first2
== __last2
)
4948 _ForwardIterator1 __result
= __last1
;
4951 _ForwardIterator1 __new_result
4952 = std::search(__first1
, __last1
, __first2
, __last2
);
4953 if (__new_result
== __last1
)
4957 __result
= __new_result
;
4958 __first1
= __new_result
;
4965 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
4966 typename _BinaryPredicate
>
4968 __find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
4969 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
4970 forward_iterator_tag
, forward_iterator_tag
,
4971 _BinaryPredicate __comp
)
4973 if (__first2
== __last2
)
4977 _ForwardIterator1 __result
= __last1
;
4980 _ForwardIterator1 __new_result
4981 = std::search(__first1
, __last1
, __first2
, __last2
, __comp
);
4982 if (__new_result
== __last1
)
4986 __result
= __new_result
;
4987 __first1
= __new_result
;
4994 // find_end for bidirectional iterators. Requires partial specialization.
4995 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
>
4996 _BidirectionalIterator1
4997 __find_end(_BidirectionalIterator1 __first1
,
4998 _BidirectionalIterator1 __last1
,
4999 _BidirectionalIterator2 __first2
,
5000 _BidirectionalIterator2 __last2
,
5001 bidirectional_iterator_tag
, bidirectional_iterator_tag
)
5003 // concept requirements
5004 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5005 _BidirectionalIterator1
>)
5006 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5007 _BidirectionalIterator2
>)
5009 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
5010 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
5012 _RevIterator1
__rlast1(__first1
);
5013 _RevIterator2
__rlast2(__first2
);
5014 _RevIterator1 __rresult
= std::search(_RevIterator1(__last1
), __rlast1
,
5015 _RevIterator2(__last2
), __rlast2
);
5017 if (__rresult
== __rlast1
)
5021 _BidirectionalIterator1 __result
= __rresult
.base();
5022 std::advance(__result
, -std::distance(__first2
, __last2
));
5027 template<typename _BidirectionalIterator1
, typename _BidirectionalIterator2
,
5028 typename _BinaryPredicate
>
5029 _BidirectionalIterator1
5030 __find_end(_BidirectionalIterator1 __first1
,
5031 _BidirectionalIterator1 __last1
,
5032 _BidirectionalIterator2 __first2
,
5033 _BidirectionalIterator2 __last2
,
5034 bidirectional_iterator_tag
, bidirectional_iterator_tag
,
5035 _BinaryPredicate __comp
)
5037 // concept requirements
5038 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5039 _BidirectionalIterator1
>)
5040 __glibcxx_function_requires(_BidirectionalIteratorConcept
<
5041 _BidirectionalIterator2
>)
5043 typedef reverse_iterator
<_BidirectionalIterator1
> _RevIterator1
;
5044 typedef reverse_iterator
<_BidirectionalIterator2
> _RevIterator2
;
5046 _RevIterator1
__rlast1(__first1
);
5047 _RevIterator2
__rlast2(__first2
);
5048 _RevIterator1 __rresult
= std::search(_RevIterator1(__last1
), __rlast1
,
5049 _RevIterator2(__last2
), __rlast2
,
5052 if (__rresult
== __rlast1
)
5056 _BidirectionalIterator1 __result
= __rresult
.base();
5057 std::advance(__result
, -std::distance(__first2
, __last2
));
5062 // Dispatching functions for find_end.
5065 * @brief Find last matching subsequence in a sequence.
5066 * @param first1 Start of range to search.
5067 * @param last1 End of range to search.
5068 * @param first2 Start of sequence to match.
5069 * @param last2 End of sequence to match.
5070 * @return The last iterator @c i in the range
5071 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5072 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
5073 * such iterator exists.
5075 * Searches the range @p [first1,last1) for a sub-sequence that compares
5076 * equal value-by-value with the sequence given by @p [first2,last2) and
5077 * returns an iterator to the first element of the sub-sequence, or
5078 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
5079 * last such subsequence contained in [first,last1).
5081 * Because the sub-sequence must lie completely within the range
5082 * @p [first1,last1) it must start at a position less than
5083 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5085 * This means that the returned iterator @c i will be in the range
5086 * @p [first1,last1-(last2-first2))
5088 template<typename _ForwardIterator1
, typename _ForwardIterator2
>
5089 inline _ForwardIterator1
5090 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5091 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
)
5093 // concept requirements
5094 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
5095 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
5096 __glibcxx_function_requires(_EqualOpConcept
<
5097 typename iterator_traits
<_ForwardIterator1
>::value_type
,
5098 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
5099 __glibcxx_requires_valid_range(__first1
, __last1
);
5100 __glibcxx_requires_valid_range(__first2
, __last2
);
5102 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
5103 std::__iterator_category(__first1
),
5104 std::__iterator_category(__first2
));
5108 * @brief Find last matching subsequence in a sequence using a predicate.
5109 * @param first1 Start of range to search.
5110 * @param last1 End of range to search.
5111 * @param first2 Start of sequence to match.
5112 * @param last2 End of sequence to match.
5113 * @param comp The predicate to use.
5114 * @return The last iterator @c i in the range
5115 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5116 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5117 * @p last1 if no such iterator exists.
5119 * Searches the range @p [first1,last1) for a sub-sequence that compares
5120 * equal value-by-value with the sequence given by @p [first2,last2) using
5121 * comp as a predicate and returns an iterator to the first element of the
5122 * sub-sequence, or @p last1 if the sub-sequence is not found. The
5123 * sub-sequence will be the last such subsequence contained in
5126 * Because the sub-sequence must lie completely within the range
5127 * @p [first1,last1) it must start at a position less than
5128 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5130 * This means that the returned iterator @c i will be in the range
5131 * @p [first1,last1-(last2-first2))
5133 template<typename _ForwardIterator1
, typename _ForwardIterator2
,
5134 typename _BinaryPredicate
>
5135 inline _ForwardIterator1
5136 find_end(_ForwardIterator1 __first1
, _ForwardIterator1 __last1
,
5137 _ForwardIterator2 __first2
, _ForwardIterator2 __last2
,
5138 _BinaryPredicate __comp
)
5140 // concept requirements
5141 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator1
>)
5142 __glibcxx_function_requires(_ForwardIteratorConcept
<_ForwardIterator2
>)
5143 __glibcxx_function_requires(_BinaryPredicateConcept
<_BinaryPredicate
,
5144 typename iterator_traits
<_ForwardIterator1
>::value_type
,
5145 typename iterator_traits
<_ForwardIterator2
>::value_type
>)
5146 __glibcxx_requires_valid_range(__first1
, __last1
);
5147 __glibcxx_requires_valid_range(__first2
, __last2
);
5149 return std::__find_end(__first1
, __last1
, __first2
, __last2
,
5150 std::__iterator_category(__first1
),
5151 std::__iterator_category(__first2
),
5157 #endif /* _ALGO_H */