4 * Hewlett-Packard Company
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
16 * Silicon Graphics Computer Systems, Inc.
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
31 #ifndef __SGI_STL_INTERNAL_ALGO_H
32 #define __SGI_STL_INTERNAL_ALGO_H
38 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
42 // __median (an extension, not present in the C++ standard).
45 inline const _Tp
& __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
) {
61 template <class _Tp
, class _Compare
>
63 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
, _Compare __comp
) {
67 else if (__comp(__a
, __c
))
71 else if (__comp(__a
, __c
))
73 else if (__comp(__b
, __c
))
79 // for_each. Apply a function to every element of a range.
80 template <class _InputIter
, class _Function
>
81 _Function
for_each(_InputIter __first
, _InputIter __last
, _Function __f
) {
82 for ( ; __first
!= __last
; ++__first
)
89 template <class _InputIter
, class _Tp
>
90 inline _InputIter
find(_InputIter __first
, _InputIter __last
,
94 while (__first
!= __last
&& *__first
!= __val
)
99 template <class _InputIter
, class _Predicate
>
100 inline _InputIter
find_if(_InputIter __first
, _InputIter __last
,
104 while (__first
!= __last
&& !__pred(*__first
))
109 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
111 template <class _RandomAccessIter
, class _Tp
>
112 _RandomAccessIter
find(_RandomAccessIter __first
, _RandomAccessIter __last
,
114 random_access_iterator_tag
)
116 typename iterator_traits
<_RandomAccessIter
>::difference_type __trip_count
117 = (__last
- __first
) >> 2;
119 for ( ; __trip_count
> 0 ; --__trip_count
) {
120 if (*__first
== __val
) return __first
;
123 if (*__first
== __val
) return __first
;
126 if (*__first
== __val
) return __first
;
129 if (*__first
== __val
) return __first
;
133 switch(__last
- __first
) {
135 if (*__first
== __val
) return __first
;
138 if (*__first
== __val
) return __first
;
141 if (*__first
== __val
) return __first
;
149 template <class _RandomAccessIter
, class _Predicate
>
150 _RandomAccessIter
find_if(_RandomAccessIter __first
, _RandomAccessIter __last
,
152 random_access_iterator_tag
)
154 typename iterator_traits
<_RandomAccessIter
>::difference_type __trip_count
155 = (__last
- __first
) >> 2;
157 for ( ; __trip_count
> 0 ; --__trip_count
) {
158 if (__pred(*__first
)) return __first
;
161 if (__pred(*__first
)) return __first
;
164 if (__pred(*__first
)) return __first
;
167 if (__pred(*__first
)) return __first
;
171 switch(__last
- __first
) {
173 if (__pred(*__first
)) return __first
;
176 if (__pred(*__first
)) return __first
;
179 if (__pred(*__first
)) return __first
;
187 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
189 template <class _InputIter
, class _Tp
>
190 inline _InputIter
find(_InputIter __first
, _InputIter __last
,
193 return find(__first
, __last
, __val
, __ITERATOR_CATEGORY(__first
));
196 template <class _InputIter
, class _Predicate
>
197 inline _InputIter
find_if(_InputIter __first
, _InputIter __last
,
199 return find_if(__first
, __last
, __pred
, __ITERATOR_CATEGORY(__first
));
204 template <class _ForwardIter
>
205 _ForwardIter
adjacent_find(_ForwardIter __first
, _ForwardIter __last
) {
206 if (__first
== __last
)
208 _ForwardIter __next
= __first
;
209 while(++__next
!= __last
) {
210 if (*__first
== *__next
)
217 template <class _ForwardIter
, class _BinaryPredicate
>
218 _ForwardIter
adjacent_find(_ForwardIter __first
, _ForwardIter __last
,
219 _BinaryPredicate __binary_pred
) {
220 if (__first
== __last
)
222 _ForwardIter __next
= __first
;
223 while(++__next
!= __last
) {
224 if (__binary_pred(*__first
, *__next
))
231 // count and count_if. There are two version of each, one whose return type
232 // type is void and one (present only if we have partial specialization)
233 // whose return type is iterator_traits<_InputIter>::difference_type. The
234 // C++ standard only has the latter version, but the former, which was present
235 // in the HP STL, is retained for backward compatibility.
237 template <class _InputIter
, class _Tp
, class _Size
>
238 void count(_InputIter __first
, _InputIter __last
, const _Tp
& __value
,
240 for ( ; __first
!= __last
; ++__first
)
241 if (*__first
== __value
)
245 template <class _InputIter
, class _Predicate
, class _Size
>
246 void count_if(_InputIter __first
, _InputIter __last
, _Predicate __pred
,
248 for ( ; __first
!= __last
; ++__first
)
249 if (__pred(*__first
))
253 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
255 template <class _InputIter
, class _Tp
>
256 typename iterator_traits
<_InputIter
>::difference_type
257 count(_InputIter __first
, _InputIter __last
, const _Tp
& __value
) {
258 typename iterator_traits
<_InputIter
>::difference_type __n
= 0;
259 for ( ; __first
!= __last
; ++__first
)
260 if (*__first
== __value
)
265 template <class _InputIter
, class _Predicate
>
266 typename iterator_traits
<_InputIter
>::difference_type
267 count_if(_InputIter __first
, _InputIter __last
, _Predicate __pred
) {
268 typename iterator_traits
<_InputIter
>::difference_type __n
= 0;
269 for ( ; __first
!= __last
; ++__first
)
270 if (__pred(*__first
))
276 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
280 template <class _ForwardIter1
, class _ForwardIter2
>
281 _ForwardIter1
search(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
282 _ForwardIter2 __first2
, _ForwardIter2 __last2
)
284 // Test for empty ranges
285 if (__first1
== __last1
|| __first2
== __last2
)
288 // Test for a pattern of length 1.
289 _ForwardIter2
__tmp(__first2
);
291 if (__tmp
== __last2
)
292 return find(__first1
, __last1
, *__first2
);
296 _ForwardIter2 __p1
, __p
;
298 __p1
= __first2
; ++__p1
;
300 _ForwardIter1 __current
= __first1
;
302 while (__first1
!= __last1
) {
303 __first1
= find(__first1
, __last1
, *__first2
);
304 if (__first1
== __last1
)
308 __current
= __first1
;
309 if (++__current
== __last1
)
312 while (*__current
== *__p
) {
313 if (++__p
== __last2
)
315 if (++__current
== __last1
)
324 template <class _ForwardIter1
, class _ForwardIter2
, class _BinaryPred
>
325 _ForwardIter1
search(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
326 _ForwardIter2 __first2
, _ForwardIter2 __last2
,
327 _BinaryPred __predicate
)
329 // Test for empty ranges
330 if (__first1
== __last1
|| __first2
== __last2
)
333 // Test for a pattern of length 1.
334 _ForwardIter2
__tmp(__first2
);
336 if (__tmp
== __last2
)
337 return find(__first1
, __last1
, *__first2
);
341 _ForwardIter2 __p1
, __p
;
343 __p1
= __first2
; ++__p1
;
345 _ForwardIter1 __current
= __first1
;
347 while (__first1
!= __last1
) {
348 while (__first1
!= __last1
) {
349 if (__predicate(*__first1
, *__first2
))
353 while (__first1
!= __last1
&& !__predicate(*__first1
, *__first2
))
355 if (__first1
== __last1
)
359 __current
= __first1
;
360 if (++__current
== __last1
) return __last1
;
362 while (__predicate(*__current
, *__p
)) {
363 if (++__p
== __last2
)
365 if (++__current
== __last1
)
374 // search_n. Search for __count consecutive copies of __val.
376 template <class _ForwardIter
, class _Integer
, class _Tp
>
377 _ForwardIter
search_n(_ForwardIter __first
, _ForwardIter __last
,
378 _Integer __count
, const _Tp
& __val
) {
382 __first
= find(__first
, __last
, __val
);
383 while (__first
!= __last
) {
384 _Integer __n
= __count
- 1;
385 _ForwardIter __i
= __first
;
387 while (__i
!= __last
&& __n
!= 0 && *__i
== __val
) {
394 __first
= find(__i
, __last
, __val
);
400 template <class _ForwardIter
, class _Integer
, class _Tp
, class _BinaryPred
>
401 _ForwardIter
search_n(_ForwardIter __first
, _ForwardIter __last
,
402 _Integer __count
, const _Tp
& __val
,
403 _BinaryPred __binary_pred
) {
407 while (__first
!= __last
) {
408 if (__binary_pred(*__first
, __val
))
412 while (__first
!= __last
) {
413 _Integer __n
= __count
- 1;
414 _ForwardIter __i
= __first
;
416 while (__i
!= __last
&& __n
!= 0 && __binary_pred(*__i
, __val
)) {
423 while (__i
!= __last
) {
424 if (__binary_pred(*__i
, __val
))
437 template <class _ForwardIter1
, class _ForwardIter2
>
438 _ForwardIter2
swap_ranges(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
439 _ForwardIter2 __first2
) {
440 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
441 iter_swap(__first1
, __first2
);
447 template <class _InputIter
, class _OutputIter
, class _UnaryOperation
>
448 _OutputIter
transform(_InputIter __first
, _InputIter __last
,
449 _OutputIter __result
, _UnaryOperation __oper
) {
450 for ( ; __first
!= __last
; ++__first
, ++__result
)
451 *__result
= __oper(*__first
);
455 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
456 class _BinaryOperation
>
457 _OutputIter
transform(_InputIter1 __first1
, _InputIter1 __last1
,
458 _InputIter2 __first2
, _OutputIter __result
,
459 _BinaryOperation __binary_op
) {
460 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
, ++__result
)
461 *__result
= __binary_op(*__first1
, *__first2
);
465 // replace, replace_if, replace_copy, replace_copy_if
467 template <class _ForwardIter
, class _Tp
>
468 void replace(_ForwardIter __first
, _ForwardIter __last
,
469 const _Tp
& __old_value
, const _Tp
& __new_value
) {
470 for ( ; __first
!= __last
; ++__first
)
471 if (*__first
== __old_value
)
472 *__first
= __new_value
;
475 template <class _ForwardIter
, class _Predicate
, class _Tp
>
476 void replace_if(_ForwardIter __first
, _ForwardIter __last
,
477 _Predicate __pred
, const _Tp
& __new_value
) {
478 for ( ; __first
!= __last
; ++__first
)
479 if (__pred(*__first
))
480 *__first
= __new_value
;
483 template <class _InputIter
, class _OutputIter
, class _Tp
>
484 _OutputIter
replace_copy(_InputIter __first
, _InputIter __last
,
485 _OutputIter __result
,
486 const _Tp
& __old_value
, const _Tp
& __new_value
) {
487 for ( ; __first
!= __last
; ++__first
, ++__result
)
488 *__result
= *__first
== __old_value
? __new_value
: *__first
;
492 template <class Iterator
, class _OutputIter
, class _Predicate
, class _Tp
>
493 _OutputIter
replace_copy_if(Iterator __first
, Iterator __last
,
494 _OutputIter __result
,
495 _Predicate __pred
, const _Tp
& __new_value
) {
496 for ( ; __first
!= __last
; ++__first
, ++__result
)
497 *__result
= __pred(*__first
) ? __new_value
: *__first
;
501 // generate and generate_n
503 template <class _ForwardIter
, class _Generator
>
504 void generate(_ForwardIter __first
, _ForwardIter __last
, _Generator __gen
) {
505 for ( ; __first
!= __last
; ++__first
)
509 template <class _OutputIter
, class _Size
, class _Generator
>
510 _OutputIter
generate_n(_OutputIter __first
, _Size __n
, _Generator __gen
) {
511 for ( ; __n
> 0; --__n
, ++__first
)
516 // remove, remove_if, remove_copy, remove_copy_if
518 template <class _InputIter
, class _OutputIter
, class _Tp
>
519 _OutputIter
remove_copy(_InputIter __first
, _InputIter __last
,
520 _OutputIter __result
, const _Tp
& __value
) {
521 for ( ; __first
!= __last
; ++__first
)
522 if (*__first
!= __value
) {
523 *__result
= *__first
;
529 template <class _InputIter
, class _OutputIter
, class _Predicate
>
530 _OutputIter
remove_copy_if(_InputIter __first
, _InputIter __last
,
531 _OutputIter __result
, _Predicate __pred
) {
532 for ( ; __first
!= __last
; ++__first
)
533 if (!__pred(*__first
)) {
534 *__result
= *__first
;
540 template <class _ForwardIter
, class _Tp
>
541 _ForwardIter
remove(_ForwardIter __first
, _ForwardIter __last
,
542 const _Tp
& __value
) {
543 __first
= find(__first
, __last
, __value
);
544 _ForwardIter __i
= __first
;
545 return __first
== __last
? __first
546 : remove_copy(++__i
, __last
, __first
, __value
);
549 template <class _ForwardIter
, class _Predicate
>
550 _ForwardIter
remove_if(_ForwardIter __first
, _ForwardIter __last
,
552 __first
= find_if(__first
, __last
, __pred
);
553 _ForwardIter __i
= __first
;
554 return __first
== __last
? __first
555 : remove_copy_if(++__i
, __last
, __first
, __pred
);
558 // unique and unique_copy
560 template <class _InputIter
, class _OutputIter
, class _Tp
>
561 _OutputIter
__unique_copy(_InputIter __first
, _InputIter __last
,
562 _OutputIter __result
, _Tp
*) {
563 _Tp __value
= *__first
;
565 while (++__first
!= __last
)
566 if (__value
!= *__first
) {
568 *++__result
= __value
;
573 template <class _InputIter
, class _OutputIter
>
574 inline _OutputIter
__unique_copy(_InputIter __first
, _InputIter __last
,
575 _OutputIter __result
,
576 output_iterator_tag
) {
577 return __unique_copy(__first
, __last
, __result
, __VALUE_TYPE(__first
));
580 template <class _InputIter
, class _ForwardIter
>
581 _ForwardIter
__unique_copy(_InputIter __first
, _InputIter __last
,
582 _ForwardIter __result
, forward_iterator_tag
) {
583 *__result
= *__first
;
584 while (++__first
!= __last
)
585 if (*__result
!= *__first
) *++__result
= *__first
;
589 template <class _InputIter
, class _OutputIter
>
590 inline _OutputIter
unique_copy(_InputIter __first
, _InputIter __last
,
591 _OutputIter __result
) {
592 if (__first
== __last
) return __result
;
593 return __unique_copy(__first
, __last
, __result
,
594 __ITERATOR_CATEGORY(__result
));
597 template <class _InputIter
, class _OutputIter
, class _BinaryPredicate
,
599 _OutputIter
__unique_copy(_InputIter __first
, _InputIter __last
,
600 _OutputIter __result
,
601 _BinaryPredicate __binary_pred
, _Tp
*) {
602 _Tp __value
= *__first
;
604 while (++__first
!= __last
)
605 if (!__binary_pred(__value
, *__first
)) {
607 *++__result
= __value
;
612 template <class _InputIter
, class _OutputIter
, class _BinaryPredicate
>
613 inline _OutputIter
__unique_copy(_InputIter __first
, _InputIter __last
,
614 _OutputIter __result
,
615 _BinaryPredicate __binary_pred
,
616 output_iterator_tag
) {
617 return __unique_copy(__first
, __last
, __result
, __binary_pred
,
618 __VALUE_TYPE(__first
));
621 template <class _InputIter
, class _ForwardIter
, class _BinaryPredicate
>
622 _ForwardIter
__unique_copy(_InputIter __first
, _InputIter __last
,
623 _ForwardIter __result
,
624 _BinaryPredicate __binary_pred
,
625 forward_iterator_tag
) {
626 *__result
= *__first
;
627 while (++__first
!= __last
)
628 if (!__binary_pred(*__result
, *__first
)) *++__result
= *__first
;
632 template <class _InputIter
, class _OutputIter
, class _BinaryPredicate
>
633 inline _OutputIter
unique_copy(_InputIter __first
, _InputIter __last
,
634 _OutputIter __result
,
635 _BinaryPredicate __binary_pred
) {
636 if (__first
== __last
) return __result
;
637 return __unique_copy(__first
, __last
, __result
, __binary_pred
,
638 __ITERATOR_CATEGORY(__result
));
641 template <class _ForwardIter
>
642 _ForwardIter
unique(_ForwardIter __first
, _ForwardIter __last
) {
643 __first
= adjacent_find(__first
, __last
);
644 return unique_copy(__first
, __last
, __first
);
647 template <class _ForwardIter
, class _BinaryPredicate
>
648 _ForwardIter
unique(_ForwardIter __first
, _ForwardIter __last
,
649 _BinaryPredicate __binary_pred
) {
650 __first
= adjacent_find(__first
, __last
, __binary_pred
);
651 return unique_copy(__first
, __last
, __first
, __binary_pred
);
654 // reverse and reverse_copy, and their auxiliary functions
656 template <class _BidirectionalIter
>
657 void __reverse(_BidirectionalIter __first
, _BidirectionalIter __last
,
658 bidirectional_iterator_tag
) {
660 if (__first
== __last
|| __first
== --__last
)
663 iter_swap(__first
++, __last
);
666 template <class _RandomAccessIter
>
667 void __reverse(_RandomAccessIter __first
, _RandomAccessIter __last
,
668 random_access_iterator_tag
) {
669 while (__first
< __last
)
670 iter_swap(__first
++, --__last
);
673 template <class _BidirectionalIter
>
674 inline void reverse(_BidirectionalIter __first
, _BidirectionalIter __last
) {
675 __reverse(__first
, __last
, __ITERATOR_CATEGORY(__first
));
678 template <class _BidirectionalIter
, class _OutputIter
>
679 _OutputIter
reverse_copy(_BidirectionalIter __first
,
680 _BidirectionalIter __last
,
681 _OutputIter __result
) {
682 while (__first
!= __last
) {
690 // rotate and rotate_copy, and their auxiliary functions
692 template <class _EuclideanRingElement
>
693 _EuclideanRingElement
__gcd(_EuclideanRingElement __m
,
694 _EuclideanRingElement __n
)
697 _EuclideanRingElement __t
= __m
% __n
;
704 template <class _ForwardIter
, class _Distance
>
705 _ForwardIter
__rotate(_ForwardIter __first
,
706 _ForwardIter __middle
,
709 forward_iterator_tag
) {
710 if (__first
== __middle
)
712 if (__last
== __middle
)
715 _ForwardIter __first2
= __middle
;
717 swap(*__first
++, *__first2
++);
718 if (__first
== __middle
)
720 } while (__first2
!= __last
);
722 _ForwardIter __new_middle
= __first
;
726 while (__first2
!= __last
) {
727 swap (*__first
++, *__first2
++);
728 if (__first
== __middle
)
730 else if (__first2
== __last
)
738 template <class _BidirectionalIter
, class _Distance
>
739 _BidirectionalIter
__rotate(_BidirectionalIter __first
,
740 _BidirectionalIter __middle
,
741 _BidirectionalIter __last
,
743 bidirectional_iterator_tag
) {
744 if (__first
== __middle
)
746 if (__last
== __middle
)
749 __reverse(__first
, __middle
, bidirectional_iterator_tag());
750 __reverse(__middle
, __last
, bidirectional_iterator_tag());
752 while (__first
!= __middle
&& __middle
!= __last
)
753 swap (*__first
++, *--__last
);
755 if (__first
== __middle
) {
756 __reverse(__middle
, __last
, bidirectional_iterator_tag());
760 __reverse(__first
, __middle
, bidirectional_iterator_tag());
765 template <class _RandomAccessIter
, class _Distance
, class _Tp
>
766 _RandomAccessIter
__rotate(_RandomAccessIter __first
,
767 _RandomAccessIter __middle
,
768 _RandomAccessIter __last
,
769 _Distance
*, _Tp
*) {
771 _Distance __n
= __last
- __first
;
772 _Distance __k
= __middle
- __first
;
773 _Distance __l
= __n
- __k
;
774 _RandomAccessIter __result
= __first
+ (__last
- __middle
);
777 swap_ranges(__first
, __middle
, __middle
);
781 _Distance __d
= __gcd(__n
, __k
);
783 for (_Distance __i
= 0; __i
< __d
; __i
++) {
784 _Tp __tmp
= *__first
;
785 _RandomAccessIter __p
= __first
;
788 for (_Distance __j
= 0; __j
< __l
/__d
; __j
++) {
789 if (__p
> __first
+ __l
) {
800 for (_Distance __j
= 0; __j
< __k
/__d
- 1; __j
++) {
801 if (__p
< __last
- __k
) {
806 *__p
= * (__p
- __l
);
818 template <class _ForwardIter
>
819 inline _ForwardIter
rotate(_ForwardIter __first
, _ForwardIter __middle
,
820 _ForwardIter __last
) {
821 return __rotate(__first
, __middle
, __last
,
822 __DISTANCE_TYPE(__first
),
823 __ITERATOR_CATEGORY(__first
));
826 template <class _ForwardIter
, class _OutputIter
>
827 _OutputIter
rotate_copy(_ForwardIter __first
, _ForwardIter __middle
,
828 _ForwardIter __last
, _OutputIter __result
) {
829 return copy(__first
, __middle
, copy(__middle
, __last
, __result
));
832 // Return a random number in the range [0, __n). This function encapsulates
833 // whether we're using rand (part of the standard C library) or lrand48
834 // (not standard, but a much better choice whenever it's available).
836 template <class _Distance
>
837 inline _Distance
__random_number(_Distance __n
) {
838 #ifdef __STL_NO_DRAND48
841 return lrand48() % __n
;
847 template <class _RandomAccessIter
>
848 inline void random_shuffle(_RandomAccessIter __first
,
849 _RandomAccessIter __last
) {
850 if (__first
== __last
) return;
851 for (_RandomAccessIter __i
= __first
+ 1; __i
!= __last
; ++__i
)
852 iter_swap(__i
, __first
+ __random_number((__i
- __first
) + 1));
855 template <class _RandomAccessIter
, class _RandomNumberGenerator
>
856 void random_shuffle(_RandomAccessIter __first
, _RandomAccessIter __last
,
857 _RandomNumberGenerator
& __rand
) {
858 if (__first
== __last
) return;
859 for (_RandomAccessIter __i
= __first
+ 1; __i
!= __last
; ++__i
)
860 iter_swap(__i
, __first
+ __rand((__i
- __first
) + 1));
863 // random_sample and random_sample_n (extensions, not part of the standard).
865 template <class _ForwardIter
, class _OutputIter
, class _Distance
>
866 _OutputIter
random_sample_n(_ForwardIter __first
, _ForwardIter __last
,
867 _OutputIter __out
, const _Distance __n
)
869 _Distance __remaining
= 0;
870 distance(__first
, __last
, __remaining
);
871 _Distance __m
= min(__n
, __remaining
);
874 if (__random_number(__remaining
) < __m
) {
886 template <class _ForwardIter
, class _OutputIter
, class _Distance
,
887 class _RandomNumberGenerator
>
888 _OutputIter
random_sample_n(_ForwardIter __first
, _ForwardIter __last
,
889 _OutputIter __out
, const _Distance __n
,
890 _RandomNumberGenerator
& __rand
)
892 _Distance __remaining
= 0;
893 distance(__first
, __last
, __remaining
);
894 _Distance __m
= min(__n
, __remaining
);
897 if (__rand(__remaining
) < __m
) {
909 template <class _InputIter
, class _RandomAccessIter
, class _Distance
>
910 _RandomAccessIter
__random_sample(_InputIter __first
, _InputIter __last
,
911 _RandomAccessIter __out
,
916 for ( ; __first
!= __last
&& __m
< __n
; ++__m
, ++__first
)
917 __out
[__m
] = *__first
;
919 while (__first
!= __last
) {
921 _Distance __M
= __random_number(__t
);
923 __out
[__M
] = *__first
;
930 template <class _InputIter
, class _RandomAccessIter
,
931 class _RandomNumberGenerator
, class _Distance
>
932 _RandomAccessIter
__random_sample(_InputIter __first
, _InputIter __last
,
933 _RandomAccessIter __out
,
934 _RandomNumberGenerator
& __rand
,
939 for ( ; __first
!= __last
&& __m
< __n
; ++__m
, ++__first
)
940 __out
[__m
] = *__first
;
942 while (__first
!= __last
) {
944 _Distance __M
= __rand(__t
);
946 __out
[__M
] = *__first
;
953 template <class _InputIter
, class _RandomAccessIter
>
954 inline _RandomAccessIter
955 random_sample(_InputIter __first
, _InputIter __last
,
956 _RandomAccessIter __out_first
, _RandomAccessIter __out_last
)
958 return __random_sample(__first
, __last
,
959 __out_first
, __out_last
- __out_first
);
963 template <class _InputIter
, class _RandomAccessIter
,
964 class _RandomNumberGenerator
>
965 inline _RandomAccessIter
966 random_sample(_InputIter __first
, _InputIter __last
,
967 _RandomAccessIter __out_first
, _RandomAccessIter __out_last
,
968 _RandomNumberGenerator
& __rand
)
970 return __random_sample(__first
, __last
,
972 __out_last
- __out_first
);
975 // partition, stable_partition, and their auxiliary functions
977 template <class _ForwardIter
, class _Predicate
>
978 _ForwardIter
__partition(_ForwardIter __first
,
981 forward_iterator_tag
) {
982 if (__first
== __last
) return __first
;
984 while (__pred(*__first
))
985 if (++__first
== __last
) return __first
;
987 _ForwardIter __next
= __first
;
989 while (++__next
!= __last
)
990 if (__pred(*__next
)) {
991 swap(*__first
, *__next
);
998 template <class _BidirectionalIter
, class _Predicate
>
999 _BidirectionalIter
__partition(_BidirectionalIter __first
,
1000 _BidirectionalIter __last
,
1002 bidirectional_iterator_tag
) {
1005 if (__first
== __last
)
1007 else if (__pred(*__first
))
1013 if (__first
== __last
)
1015 else if (!__pred(*__last
))
1019 iter_swap(__first
, __last
);
1024 template <class _ForwardIter
, class _Predicate
>
1025 inline _ForwardIter
partition(_ForwardIter __first
,
1026 _ForwardIter __last
,
1027 _Predicate __pred
) {
1028 return __partition(__first
, __last
, __pred
, __ITERATOR_CATEGORY(__first
));
1032 template <class _ForwardIter
, class _Predicate
, class _Distance
>
1033 _ForwardIter
__inplace_stable_partition(_ForwardIter __first
,
1034 _ForwardIter __last
,
1035 _Predicate __pred
, _Distance __len
) {
1037 return __pred(*__first
) ? __last
: __first
;
1038 _ForwardIter __middle
= __first
;
1039 advance(__middle
, __len
/ 2);
1040 return rotate(__inplace_stable_partition(__first
, __middle
, __pred
,
1043 __inplace_stable_partition(__middle
, __last
, __pred
,
1044 __len
- __len
/ 2));
1047 template <class _ForwardIter
, class _Pointer
, class _Predicate
,
1049 _ForwardIter
__stable_partition_adaptive(_ForwardIter __first
,
1050 _ForwardIter __last
,
1051 _Predicate __pred
, _Distance __len
,
1053 _Distance __buffer_size
)
1055 if (__len
<= __buffer_size
) {
1056 _ForwardIter __result1
= __first
;
1057 _Pointer __result2
= __buffer
;
1058 for ( ; __first
!= __last
; ++__first
)
1059 if (__pred(*__first
)) {
1060 *__result1
= *__first
;
1064 *__result2
= *__first
;
1067 copy(__buffer
, __result2
, __result1
);
1071 _ForwardIter __middle
= __first
;
1072 advance(__middle
, __len
/ 2);
1073 return rotate(__stable_partition_adaptive(
1074 __first
, __middle
, __pred
,
1075 __len
/ 2, __buffer
, __buffer_size
),
1077 __stable_partition_adaptive(
1078 __middle
, __last
, __pred
,
1079 __len
- __len
/ 2, __buffer
, __buffer_size
));
1083 template <class _ForwardIter
, class _Predicate
, class _Tp
, class _Distance
>
1085 __stable_partition_aux(_ForwardIter __first
, _ForwardIter __last
,
1086 _Predicate __pred
, _Tp
*, _Distance
*)
1088 _Temporary_buffer
<_ForwardIter
, _Tp
> __buf(__first
, __last
);
1089 if (__buf
.size() > 0)
1090 return __stable_partition_adaptive(__first
, __last
, __pred
,
1091 _Distance(__buf
.requested_size()),
1092 __buf
.begin(), __buf
.size());
1094 return __inplace_stable_partition(__first
, __last
, __pred
,
1095 _Distance(__buf
.requested_size()));
1098 template <class _ForwardIter
, class _Predicate
>
1099 inline _ForwardIter
stable_partition(_ForwardIter __first
,
1100 _ForwardIter __last
,
1101 _Predicate __pred
) {
1102 if (__first
== __last
)
1105 return __stable_partition_aux(__first
, __last
, __pred
,
1106 __VALUE_TYPE(__first
),
1107 __DISTANCE_TYPE(__first
));
1110 template <class _RandomAccessIter
, class _Tp
>
1111 _RandomAccessIter
__unguarded_partition(_RandomAccessIter __first
,
1112 _RandomAccessIter __last
,
1116 while (*__first
< __pivot
)
1119 while (__pivot
< *__last
)
1121 if (!(__first
< __last
))
1123 iter_swap(__first
, __last
);
1128 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1129 _RandomAccessIter
__unguarded_partition(_RandomAccessIter __first
,
1130 _RandomAccessIter __last
,
1131 _Tp __pivot
, _Compare __comp
)
1134 while (__comp(*__first
, __pivot
))
1137 while (__comp(__pivot
, *__last
))
1139 if (!(__first
< __last
))
1141 iter_swap(__first
, __last
);
1146 const int __stl_threshold
= 16;
1148 // sort() and its auxiliary functions.
1150 template <class _RandomAccessIter
, class _Tp
>
1151 void __unguarded_linear_insert(_RandomAccessIter __last
, _Tp __val
) {
1152 _RandomAccessIter __next
= __last
;
1154 while (__val
< *__next
) {
1162 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1163 void __unguarded_linear_insert(_RandomAccessIter __last
, _Tp __val
,
1165 _RandomAccessIter __next
= __last
;
1167 while (__comp(__val
, *__next
)) {
1175 template <class _RandomAccessIter
, class _Tp
>
1176 inline void __linear_insert(_RandomAccessIter __first
,
1177 _RandomAccessIter __last
, _Tp
*) {
1178 _Tp __val
= *__last
;
1179 if (__val
< *__first
) {
1180 copy_backward(__first
, __last
, __last
+ 1);
1184 __unguarded_linear_insert(__last
, __val
);
1187 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1188 inline void __linear_insert(_RandomAccessIter __first
,
1189 _RandomAccessIter __last
, _Tp
*, _Compare __comp
) {
1190 _Tp __val
= *__last
;
1191 if (__comp(__val
, *__first
)) {
1192 copy_backward(__first
, __last
, __last
+ 1);
1196 __unguarded_linear_insert(__last
, __val
, __comp
);
1199 template <class _RandomAccessIter
>
1200 void __insertion_sort(_RandomAccessIter __first
, _RandomAccessIter __last
) {
1201 if (__first
== __last
) return;
1202 for (_RandomAccessIter __i
= __first
+ 1; __i
!= __last
; ++__i
)
1203 __linear_insert(__first
, __i
, __VALUE_TYPE(__first
));
1206 template <class _RandomAccessIter
, class _Compare
>
1207 void __insertion_sort(_RandomAccessIter __first
,
1208 _RandomAccessIter __last
, _Compare __comp
) {
1209 if (__first
== __last
) return;
1210 for (_RandomAccessIter __i
= __first
+ 1; __i
!= __last
; ++__i
)
1211 __linear_insert(__first
, __i
, __VALUE_TYPE(__first
), __comp
);
1214 template <class _RandomAccessIter
, class _Tp
>
1215 void __unguarded_insertion_sort_aux(_RandomAccessIter __first
,
1216 _RandomAccessIter __last
, _Tp
*) {
1217 for (_RandomAccessIter __i
= __first
; __i
!= __last
; ++__i
)
1218 __unguarded_linear_insert(__i
, _Tp(*__i
));
1221 template <class _RandomAccessIter
>
1222 inline void __unguarded_insertion_sort(_RandomAccessIter __first
,
1223 _RandomAccessIter __last
) {
1224 __unguarded_insertion_sort_aux(__first
, __last
, __VALUE_TYPE(__first
));
1227 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1228 void __unguarded_insertion_sort_aux(_RandomAccessIter __first
,
1229 _RandomAccessIter __last
,
1230 _Tp
*, _Compare __comp
) {
1231 for (_RandomAccessIter __i
= __first
; __i
!= __last
; ++__i
)
1232 __unguarded_linear_insert(__i
, _Tp(*__i
), __comp
);
1235 template <class _RandomAccessIter
, class _Compare
>
1236 inline void __unguarded_insertion_sort(_RandomAccessIter __first
,
1237 _RandomAccessIter __last
,
1239 __unguarded_insertion_sort_aux(__first
, __last
, __VALUE_TYPE(__first
),
1243 template <class _RandomAccessIter
>
1244 void __final_insertion_sort(_RandomAccessIter __first
,
1245 _RandomAccessIter __last
) {
1246 if (__last
- __first
> __stl_threshold
) {
1247 __insertion_sort(__first
, __first
+ __stl_threshold
);
1248 __unguarded_insertion_sort(__first
+ __stl_threshold
, __last
);
1251 __insertion_sort(__first
, __last
);
1254 template <class _RandomAccessIter
, class _Compare
>
1255 void __final_insertion_sort(_RandomAccessIter __first
,
1256 _RandomAccessIter __last
, _Compare __comp
) {
1257 if (__last
- __first
> __stl_threshold
) {
1258 __insertion_sort(__first
, __first
+ __stl_threshold
, __comp
);
1259 __unguarded_insertion_sort(__first
+ __stl_threshold
, __last
, __comp
);
1262 __insertion_sort(__first
, __last
, __comp
);
1265 template <class _Size
>
1266 inline _Size
__lg(_Size __n
) {
1268 for (__k
= 0; __n
!= 1; __n
>>= 1) ++__k
;
1272 template <class _RandomAccessIter
, class _Tp
, class _Size
>
1273 void __introsort_loop(_RandomAccessIter __first
,
1274 _RandomAccessIter __last
, _Tp
*,
1275 _Size __depth_limit
)
1277 while (__last
- __first
> __stl_threshold
) {
1278 if (__depth_limit
== 0) {
1279 partial_sort(__first
, __last
, __last
);
1283 _RandomAccessIter __cut
=
1284 __unguarded_partition(__first
, __last
,
1285 _Tp(__median(*__first
,
1286 *(__first
+ (__last
- __first
)/2),
1288 __introsort_loop(__cut
, __last
, (_Tp
*) 0, __depth_limit
);
1293 template <class _RandomAccessIter
, class _Tp
, class _Size
, class _Compare
>
1294 void __introsort_loop(_RandomAccessIter __first
,
1295 _RandomAccessIter __last
, _Tp
*,
1296 _Size __depth_limit
, _Compare __comp
)
1298 while (__last
- __first
> __stl_threshold
) {
1299 if (__depth_limit
== 0) {
1300 partial_sort(__first
, __last
, __last
, __comp
);
1304 _RandomAccessIter __cut
=
1305 __unguarded_partition(__first
, __last
,
1306 _Tp(__median(*__first
,
1307 *(__first
+ (__last
- __first
)/2),
1308 *(__last
- 1), __comp
)),
1310 __introsort_loop(__cut
, __last
, (_Tp
*) 0, __depth_limit
, __comp
);
1315 template <class _RandomAccessIter
>
1316 inline void sort(_RandomAccessIter __first
, _RandomAccessIter __last
) {
1317 if (__first
!= __last
) {
1318 __introsort_loop(__first
, __last
,
1319 __VALUE_TYPE(__first
),
1320 __lg(__last
- __first
) * 2);
1321 __final_insertion_sort(__first
, __last
);
1325 template <class _RandomAccessIter
, class _Compare
>
1326 inline void sort(_RandomAccessIter __first
, _RandomAccessIter __last
,
1328 if (__first
!= __last
) {
1329 __introsort_loop(__first
, __last
,
1330 __VALUE_TYPE(__first
),
1331 __lg(__last
- __first
) * 2,
1333 __final_insertion_sort(__first
, __last
, __comp
);
1337 // stable_sort() and its auxiliary functions.
1339 template <class _RandomAccessIter
>
1340 void __inplace_stable_sort(_RandomAccessIter __first
,
1341 _RandomAccessIter __last
) {
1342 if (__last
- __first
< 15) {
1343 __insertion_sort(__first
, __last
);
1346 _RandomAccessIter __middle
= __first
+ (__last
- __first
) / 2;
1347 __inplace_stable_sort(__first
, __middle
);
1348 __inplace_stable_sort(__middle
, __last
);
1349 __merge_without_buffer(__first
, __middle
, __last
,
1354 template <class _RandomAccessIter
, class _Compare
>
1355 void __inplace_stable_sort(_RandomAccessIter __first
,
1356 _RandomAccessIter __last
, _Compare __comp
) {
1357 if (__last
- __first
< 15) {
1358 __insertion_sort(__first
, __last
, __comp
);
1361 _RandomAccessIter __middle
= __first
+ (__last
- __first
) / 2;
1362 __inplace_stable_sort(__first
, __middle
, __comp
);
1363 __inplace_stable_sort(__middle
, __last
, __comp
);
1364 __merge_without_buffer(__first
, __middle
, __last
,
1370 template <class _RandomAccessIter1
, class _RandomAccessIter2
,
1372 void __merge_sort_loop(_RandomAccessIter1 __first
,
1373 _RandomAccessIter1 __last
,
1374 _RandomAccessIter2 __result
, _Distance __step_size
) {
1375 _Distance __two_step
= 2 * __step_size
;
1377 while (__last
- __first
>= __two_step
) {
1378 __result
= merge(__first
, __first
+ __step_size
,
1379 __first
+ __step_size
, __first
+ __two_step
,
1381 __first
+= __two_step
;
1384 __step_size
= min(_Distance(__last
- __first
), __step_size
);
1385 merge(__first
, __first
+ __step_size
, __first
+ __step_size
, __last
,
1389 template <class _RandomAccessIter1
, class _RandomAccessIter2
,
1390 class _Distance
, class _Compare
>
1391 void __merge_sort_loop(_RandomAccessIter1 __first
,
1392 _RandomAccessIter1 __last
,
1393 _RandomAccessIter2 __result
, _Distance __step_size
,
1395 _Distance __two_step
= 2 * __step_size
;
1397 while (__last
- __first
>= __two_step
) {
1398 __result
= merge(__first
, __first
+ __step_size
,
1399 __first
+ __step_size
, __first
+ __two_step
,
1402 __first
+= __two_step
;
1404 __step_size
= min(_Distance(__last
- __first
), __step_size
);
1406 merge(__first
, __first
+ __step_size
,
1407 __first
+ __step_size
, __last
,
1412 const int __stl_chunk_size
= 7;
1414 template <class _RandomAccessIter
, class _Distance
>
1415 void __chunk_insertion_sort(_RandomAccessIter __first
,
1416 _RandomAccessIter __last
, _Distance __chunk_size
)
1418 while (__last
- __first
>= __chunk_size
) {
1419 __insertion_sort(__first
, __first
+ __chunk_size
);
1420 __first
+= __chunk_size
;
1422 __insertion_sort(__first
, __last
);
1425 template <class _RandomAccessIter
, class _Distance
, class _Compare
>
1426 void __chunk_insertion_sort(_RandomAccessIter __first
,
1427 _RandomAccessIter __last
,
1428 _Distance __chunk_size
, _Compare __comp
)
1430 while (__last
- __first
>= __chunk_size
) {
1431 __insertion_sort(__first
, __first
+ __chunk_size
, __comp
);
1432 __first
+= __chunk_size
;
1434 __insertion_sort(__first
, __last
, __comp
);
1437 template <class _RandomAccessIter
, class _Pointer
, class _Distance
>
1438 void __merge_sort_with_buffer(_RandomAccessIter __first
,
1439 _RandomAccessIter __last
,
1440 _Pointer __buffer
, _Distance
*) {
1441 _Distance __len
= __last
- __first
;
1442 _Pointer __buffer_last
= __buffer
+ __len
;
1444 _Distance __step_size
= __stl_chunk_size
;
1445 __chunk_insertion_sort(__first
, __last
, __step_size
);
1447 while (__step_size
< __len
) {
1448 __merge_sort_loop(__first
, __last
, __buffer
, __step_size
);
1450 __merge_sort_loop(__buffer
, __buffer_last
, __first
, __step_size
);
1455 template <class _RandomAccessIter
, class _Pointer
, class _Distance
,
1457 void __merge_sort_with_buffer(_RandomAccessIter __first
,
1458 _RandomAccessIter __last
, _Pointer __buffer
,
1459 _Distance
*, _Compare __comp
) {
1460 _Distance __len
= __last
- __first
;
1461 _Pointer __buffer_last
= __buffer
+ __len
;
1463 _Distance __step_size
= __stl_chunk_size
;
1464 __chunk_insertion_sort(__first
, __last
, __step_size
, __comp
);
1466 while (__step_size
< __len
) {
1467 __merge_sort_loop(__first
, __last
, __buffer
, __step_size
, __comp
);
1469 __merge_sort_loop(__buffer
, __buffer_last
, __first
, __step_size
, __comp
);
1474 template <class _RandomAccessIter
, class _Pointer
, class _Distance
>
1475 void __stable_sort_adaptive(_RandomAccessIter __first
,
1476 _RandomAccessIter __last
, _Pointer __buffer
,
1477 _Distance __buffer_size
) {
1478 _Distance __len
= (__last
- __first
+ 1) / 2;
1479 _RandomAccessIter __middle
= __first
+ __len
;
1480 if (__len
> __buffer_size
) {
1481 __stable_sort_adaptive(__first
, __middle
, __buffer
, __buffer_size
);
1482 __stable_sort_adaptive(__middle
, __last
, __buffer
, __buffer_size
);
1485 __merge_sort_with_buffer(__first
, __middle
, __buffer
, (_Distance
*)0);
1486 __merge_sort_with_buffer(__middle
, __last
, __buffer
, (_Distance
*)0);
1488 __merge_adaptive(__first
, __middle
, __last
, _Distance(__middle
- __first
),
1489 _Distance(__last
- __middle
), __buffer
, __buffer_size
);
1492 template <class _RandomAccessIter
, class _Pointer
, class _Distance
,
1494 void __stable_sort_adaptive(_RandomAccessIter __first
,
1495 _RandomAccessIter __last
, _Pointer __buffer
,
1496 _Distance __buffer_size
, _Compare __comp
) {
1497 _Distance __len
= (__last
- __first
+ 1) / 2;
1498 _RandomAccessIter __middle
= __first
+ __len
;
1499 if (__len
> __buffer_size
) {
1500 __stable_sort_adaptive(__first
, __middle
, __buffer
, __buffer_size
,
1502 __stable_sort_adaptive(__middle
, __last
, __buffer
, __buffer_size
,
1506 __merge_sort_with_buffer(__first
, __middle
, __buffer
, (_Distance
*)0,
1508 __merge_sort_with_buffer(__middle
, __last
, __buffer
, (_Distance
*)0,
1511 __merge_adaptive(__first
, __middle
, __last
, _Distance(__middle
- __first
),
1512 _Distance(__last
- __middle
), __buffer
, __buffer_size
,
1516 template <class _RandomAccessIter
, class _Tp
, class _Distance
>
1517 inline void __stable_sort_aux(_RandomAccessIter __first
,
1518 _RandomAccessIter __last
, _Tp
*, _Distance
*) {
1519 _Temporary_buffer
<_RandomAccessIter
, _Tp
> buf(__first
, __last
);
1520 if (buf
.begin() == 0)
1521 __inplace_stable_sort(__first
, __last
);
1523 __stable_sort_adaptive(__first
, __last
, buf
.begin(),
1524 _Distance(buf
.size()));
1527 template <class _RandomAccessIter
, class _Tp
, class _Distance
, class _Compare
>
1528 inline void __stable_sort_aux(_RandomAccessIter __first
,
1529 _RandomAccessIter __last
, _Tp
*, _Distance
*,
1531 _Temporary_buffer
<_RandomAccessIter
, _Tp
> buf(__first
, __last
);
1532 if (buf
.begin() == 0)
1533 __inplace_stable_sort(__first
, __last
, __comp
);
1535 __stable_sort_adaptive(__first
, __last
, buf
.begin(),
1536 _Distance(buf
.size()),
1540 template <class _RandomAccessIter
>
1541 inline void stable_sort(_RandomAccessIter __first
,
1542 _RandomAccessIter __last
) {
1543 __stable_sort_aux(__first
, __last
,
1544 __VALUE_TYPE(__first
),
1545 __DISTANCE_TYPE(__first
));
1548 template <class _RandomAccessIter
, class _Compare
>
1549 inline void stable_sort(_RandomAccessIter __first
,
1550 _RandomAccessIter __last
, _Compare __comp
) {
1551 __stable_sort_aux(__first
, __last
,
1552 __VALUE_TYPE(__first
),
1553 __DISTANCE_TYPE(__first
),
1557 // partial_sort, partial_sort_copy, and auxiliary functions.
1559 template <class _RandomAccessIter
, class _Tp
>
1560 void __partial_sort(_RandomAccessIter __first
, _RandomAccessIter __middle
,
1561 _RandomAccessIter __last
, _Tp
*) {
1562 make_heap(__first
, __middle
);
1563 for (_RandomAccessIter __i
= __middle
; __i
< __last
; ++__i
)
1564 if (*__i
< *__first
)
1565 __pop_heap(__first
, __middle
, __i
, _Tp(*__i
),
1566 __DISTANCE_TYPE(__first
));
1567 sort_heap(__first
, __middle
);
1570 template <class _RandomAccessIter
>
1571 inline void partial_sort(_RandomAccessIter __first
,
1572 _RandomAccessIter __middle
,
1573 _RandomAccessIter __last
) {
1574 __partial_sort(__first
, __middle
, __last
, __VALUE_TYPE(__first
));
1577 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1578 void __partial_sort(_RandomAccessIter __first
, _RandomAccessIter __middle
,
1579 _RandomAccessIter __last
, _Tp
*, _Compare __comp
) {
1580 make_heap(__first
, __middle
, __comp
);
1581 for (_RandomAccessIter __i
= __middle
; __i
< __last
; ++__i
)
1582 if (__comp(*__i
, *__first
))
1583 __pop_heap(__first
, __middle
, __i
, _Tp(*__i
), __comp
,
1584 __DISTANCE_TYPE(__first
));
1585 sort_heap(__first
, __middle
, __comp
);
1588 template <class _RandomAccessIter
, class _Compare
>
1589 inline void partial_sort(_RandomAccessIter __first
,
1590 _RandomAccessIter __middle
,
1591 _RandomAccessIter __last
, _Compare __comp
) {
1592 __partial_sort(__first
, __middle
, __last
, __VALUE_TYPE(__first
), __comp
);
1595 template <class _InputIter
, class _RandomAccessIter
, class _Distance
,
1597 _RandomAccessIter
__partial_sort_copy(_InputIter __first
,
1599 _RandomAccessIter __result_first
,
1600 _RandomAccessIter __result_last
,
1602 if (__result_first
== __result_last
) return __result_last
;
1603 _RandomAccessIter __result_real_last
= __result_first
;
1604 while(__first
!= __last
&& __result_real_last
!= __result_last
) {
1605 *__result_real_last
= *__first
;
1606 ++__result_real_last
;
1609 make_heap(__result_first
, __result_real_last
);
1610 while (__first
!= __last
) {
1611 if (*__first
< *__result_first
)
1612 __adjust_heap(__result_first
, _Distance(0),
1613 _Distance(__result_real_last
- __result_first
),
1617 sort_heap(__result_first
, __result_real_last
);
1618 return __result_real_last
;
1621 template <class _InputIter
, class _RandomAccessIter
>
1622 inline _RandomAccessIter
1623 partial_sort_copy(_InputIter __first
, _InputIter __last
,
1624 _RandomAccessIter __result_first
,
1625 _RandomAccessIter __result_last
) {
1626 return __partial_sort_copy(__first
, __last
, __result_first
, __result_last
,
1627 __DISTANCE_TYPE(__result_first
),
1628 __VALUE_TYPE(__first
));
1631 template <class _InputIter
, class _RandomAccessIter
, class _Compare
,
1632 class _Distance
, class _Tp
>
1633 _RandomAccessIter
__partial_sort_copy(_InputIter __first
,
1635 _RandomAccessIter __result_first
,
1636 _RandomAccessIter __result_last
,
1637 _Compare __comp
, _Distance
*, _Tp
*) {
1638 if (__result_first
== __result_last
) return __result_last
;
1639 _RandomAccessIter __result_real_last
= __result_first
;
1640 while(__first
!= __last
&& __result_real_last
!= __result_last
) {
1641 *__result_real_last
= *__first
;
1642 ++__result_real_last
;
1645 make_heap(__result_first
, __result_real_last
, __comp
);
1646 while (__first
!= __last
) {
1647 if (__comp(*__first
, *__result_first
))
1648 __adjust_heap(__result_first
, _Distance(0),
1649 _Distance(__result_real_last
- __result_first
),
1654 sort_heap(__result_first
, __result_real_last
, __comp
);
1655 return __result_real_last
;
1658 template <class _InputIter
, class _RandomAccessIter
, class _Compare
>
1659 inline _RandomAccessIter
1660 partial_sort_copy(_InputIter __first
, _InputIter __last
,
1661 _RandomAccessIter __result_first
,
1662 _RandomAccessIter __result_last
, _Compare __comp
) {
1663 return __partial_sort_copy(__first
, __last
, __result_first
, __result_last
,
1665 __DISTANCE_TYPE(__result_first
),
1666 __VALUE_TYPE(__first
));
1669 // nth_element() and its auxiliary functions.
1671 template <class _RandomAccessIter
, class _Tp
>
1672 void __nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
1673 _RandomAccessIter __last
, _Tp
*) {
1674 while (__last
- __first
> 3) {
1675 _RandomAccessIter __cut
=
1676 __unguarded_partition(__first
, __last
,
1677 _Tp(__median(*__first
,
1678 *(__first
+ (__last
- __first
)/2),
1685 __insertion_sort(__first
, __last
);
1688 template <class _RandomAccessIter
>
1689 inline void nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
1690 _RandomAccessIter __last
) {
1691 __nth_element(__first
, __nth
, __last
, __VALUE_TYPE(__first
));
1694 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1695 void __nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
1696 _RandomAccessIter __last
, _Tp
*, _Compare __comp
) {
1697 while (__last
- __first
> 3) {
1698 _RandomAccessIter __cut
=
1699 __unguarded_partition(__first
, __last
,
1700 _Tp(__median(*__first
,
1701 *(__first
+ (__last
- __first
)/2),
1710 __insertion_sort(__first
, __last
, __comp
);
1713 template <class _RandomAccessIter
, class _Compare
>
1714 inline void nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
1715 _RandomAccessIter __last
, _Compare __comp
) {
1716 __nth_element(__first
, __nth
, __last
, __VALUE_TYPE(__first
), __comp
);
1720 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
1722 template <class _ForwardIter
, class _Tp
, class _Distance
>
1723 _ForwardIter
__lower_bound(_ForwardIter __first
, _ForwardIter __last
,
1724 const _Tp
& __val
, _Distance
*)
1726 _Distance __len
= 0;
1727 distance(__first
, __last
, __len
);
1729 _ForwardIter __middle
;
1732 __half
= __len
>> 1;
1734 advance(__middle
, __half
);
1735 if (*__middle
< __val
) {
1738 __len
= __len
- __half
- 1;
1746 template <class _ForwardIter
, class _Tp
>
1747 inline _ForwardIter
lower_bound(_ForwardIter __first
, _ForwardIter __last
,
1749 return __lower_bound(__first
, __last
, __val
,
1750 __DISTANCE_TYPE(__first
));
1753 template <class _ForwardIter
, class _Tp
, class _Compare
, class _Distance
>
1754 _ForwardIter
__lower_bound(_ForwardIter __first
, _ForwardIter __last
,
1755 const _Tp
& __val
, _Compare __comp
, _Distance
*)
1757 _Distance __len
= 0;
1758 distance(__first
, __last
, __len
);
1760 _ForwardIter __middle
;
1763 __half
= __len
>> 1;
1765 advance(__middle
, __half
);
1766 if (__comp(*__middle
, __val
)) {
1769 __len
= __len
- __half
- 1;
1777 template <class _ForwardIter
, class _Tp
, class _Compare
>
1778 inline _ForwardIter
lower_bound(_ForwardIter __first
, _ForwardIter __last
,
1779 const _Tp
& __val
, _Compare __comp
) {
1780 return __lower_bound(__first
, __last
, __val
, __comp
,
1781 __DISTANCE_TYPE(__first
));
1784 template <class _ForwardIter
, class _Tp
, class _Distance
>
1785 _ForwardIter
__upper_bound(_ForwardIter __first
, _ForwardIter __last
,
1786 const _Tp
& __val
, _Distance
*)
1788 _Distance __len
= 0;
1789 distance(__first
, __last
, __len
);
1791 _ForwardIter __middle
;
1794 __half
= __len
>> 1;
1796 advance(__middle
, __half
);
1797 if (__val
< *__middle
)
1802 __len
= __len
- __half
- 1;
1808 template <class _ForwardIter
, class _Tp
>
1809 inline _ForwardIter
upper_bound(_ForwardIter __first
, _ForwardIter __last
,
1811 return __upper_bound(__first
, __last
, __val
,
1812 __DISTANCE_TYPE(__first
));
1815 template <class _ForwardIter
, class _Tp
, class _Compare
, class _Distance
>
1816 _ForwardIter
__upper_bound(_ForwardIter __first
, _ForwardIter __last
,
1817 const _Tp
& __val
, _Compare __comp
, _Distance
*)
1819 _Distance __len
= 0;
1820 distance(__first
, __last
, __len
);
1822 _ForwardIter __middle
;
1825 __half
= __len
>> 1;
1827 advance(__middle
, __half
);
1828 if (__comp(__val
, *__middle
))
1833 __len
= __len
- __half
- 1;
1839 template <class _ForwardIter
, class _Tp
, class _Compare
>
1840 inline _ForwardIter
upper_bound(_ForwardIter __first
, _ForwardIter __last
,
1841 const _Tp
& __val
, _Compare __comp
) {
1842 return __upper_bound(__first
, __last
, __val
, __comp
,
1843 __DISTANCE_TYPE(__first
));
1846 template <class _ForwardIter
, class _Tp
, class _Distance
>
1847 pair
<_ForwardIter
, _ForwardIter
>
1848 __equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
1851 _Distance __len
= 0;
1852 distance(__first
, __last
, __len
);
1854 _ForwardIter __middle
, __left
, __right
;
1857 __half
= __len
>> 1;
1859 advance(__middle
, __half
);
1860 if (*__middle
< __val
) {
1863 __len
= __len
- __half
- 1;
1865 else if (__val
< *__middle
)
1868 __left
= lower_bound(__first
, __middle
, __val
);
1869 advance(__first
, __len
);
1870 __right
= upper_bound(++__middle
, __first
, __val
);
1871 return pair
<_ForwardIter
, _ForwardIter
>(__left
, __right
);
1874 return pair
<_ForwardIter
, _ForwardIter
>(__first
, __first
);
1877 template <class _ForwardIter
, class _Tp
>
1878 inline pair
<_ForwardIter
, _ForwardIter
>
1879 equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
) {
1880 return __equal_range(__first
, __last
, __val
,
1881 __DISTANCE_TYPE(__first
));
1884 template <class _ForwardIter
, class _Tp
, class _Compare
, class _Distance
>
1885 pair
<_ForwardIter
, _ForwardIter
>
1886 __equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
1887 _Compare __comp
, _Distance
*)
1889 _Distance __len
= 0;
1890 distance(__first
, __last
, __len
);
1892 _ForwardIter __middle
, __left
, __right
;
1895 __half
= __len
>> 1;
1897 advance(__middle
, __half
);
1898 if (__comp(*__middle
, __val
)) {
1901 __len
= __len
- __half
- 1;
1903 else if (__comp(__val
, *__middle
))
1906 __left
= lower_bound(__first
, __middle
, __val
, __comp
);
1907 advance(__first
, __len
);
1908 __right
= upper_bound(++__middle
, __first
, __val
, __comp
);
1909 return pair
<_ForwardIter
, _ForwardIter
>(__left
, __right
);
1912 return pair
<_ForwardIter
, _ForwardIter
>(__first
, __first
);
1915 template <class _ForwardIter
, class _Tp
, class _Compare
>
1916 inline pair
<_ForwardIter
, _ForwardIter
>
1917 equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
1919 return __equal_range(__first
, __last
, __val
, __comp
,
1920 __DISTANCE_TYPE(__first
));
1923 template <class _ForwardIter
, class _Tp
>
1924 bool binary_search(_ForwardIter __first
, _ForwardIter __last
,
1926 _ForwardIter __i
= lower_bound(__first
, __last
, __val
);
1927 return __i
!= __last
&& !(__val
< *__i
);
1930 template <class _ForwardIter
, class _Tp
, class _Compare
>
1931 bool binary_search(_ForwardIter __first
, _ForwardIter __last
,
1934 _ForwardIter __i
= lower_bound(__first
, __last
, __val
, __comp
);
1935 return __i
!= __last
&& !__comp(__val
, *__i
);
1938 // merge, with and without an explicitly supplied comparison function.
1940 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
1941 _OutputIter
merge(_InputIter1 __first1
, _InputIter1 __last1
,
1942 _InputIter2 __first2
, _InputIter2 __last2
,
1943 _OutputIter __result
) {
1944 while (__first1
!= __last1
&& __first2
!= __last2
) {
1945 if (*__first2
< *__first1
) {
1946 *__result
= *__first2
;
1950 *__result
= *__first1
;
1955 return copy(__first2
, __last2
, copy(__first1
, __last1
, __result
));
1958 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1960 _OutputIter
merge(_InputIter1 __first1
, _InputIter1 __last1
,
1961 _InputIter2 __first2
, _InputIter2 __last2
,
1962 _OutputIter __result
, _Compare __comp
) {
1963 while (__first1
!= __last1
&& __first2
!= __last2
) {
1964 if (__comp(*__first2
, *__first1
)) {
1965 *__result
= *__first2
;
1969 *__result
= *__first1
;
1974 return copy(__first2
, __last2
, copy(__first1
, __last1
, __result
));
1977 // inplace_merge and its auxiliary functions.
1979 template <class _BidirectionalIter
, class _Distance
>
1980 void __merge_without_buffer(_BidirectionalIter __first
,
1981 _BidirectionalIter __middle
,
1982 _BidirectionalIter __last
,
1983 _Distance __len1
, _Distance __len2
) {
1984 if (__len1
== 0 || __len2
== 0)
1986 if (__len1
+ __len2
== 2) {
1987 if (*__middle
< *__first
)
1988 iter_swap(__first
, __middle
);
1991 _BidirectionalIter __first_cut
= __first
;
1992 _BidirectionalIter __second_cut
= __middle
;
1993 _Distance __len11
= 0;
1994 _Distance __len22
= 0;
1995 if (__len1
> __len2
) {
1996 __len11
= __len1
/ 2;
1997 advance(__first_cut
, __len11
);
1998 __second_cut
= lower_bound(__middle
, __last
, *__first_cut
);
1999 distance(__middle
, __second_cut
, __len22
);
2002 __len22
= __len2
/ 2;
2003 advance(__second_cut
, __len22
);
2004 __first_cut
= upper_bound(__first
, __middle
, *__second_cut
);
2005 distance(__first
, __first_cut
, __len11
);
2007 _BidirectionalIter __new_middle
2008 = rotate(__first_cut
, __middle
, __second_cut
);
2009 __merge_without_buffer(__first
, __first_cut
, __new_middle
,
2011 __merge_without_buffer(__new_middle
, __second_cut
, __last
, __len1
- __len11
,
2015 template <class _BidirectionalIter
, class _Distance
, class _Compare
>
2016 void __merge_without_buffer(_BidirectionalIter __first
,
2017 _BidirectionalIter __middle
,
2018 _BidirectionalIter __last
,
2019 _Distance __len1
, _Distance __len2
,
2021 if (__len1
== 0 || __len2
== 0)
2023 if (__len1
+ __len2
== 2) {
2024 if (__comp(*__middle
, *__first
))
2025 iter_swap(__first
, __middle
);
2028 _BidirectionalIter __first_cut
= __first
;
2029 _BidirectionalIter __second_cut
= __middle
;
2030 _Distance __len11
= 0;
2031 _Distance __len22
= 0;
2032 if (__len1
> __len2
) {
2033 __len11
= __len1
/ 2;
2034 advance(__first_cut
, __len11
);
2035 __second_cut
= lower_bound(__middle
, __last
, *__first_cut
, __comp
);
2036 distance(__middle
, __second_cut
, __len22
);
2039 __len22
= __len2
/ 2;
2040 advance(__second_cut
, __len22
);
2041 __first_cut
= upper_bound(__first
, __middle
, *__second_cut
, __comp
);
2042 distance(__first
, __first_cut
, __len11
);
2044 _BidirectionalIter __new_middle
2045 = rotate(__first_cut
, __middle
, __second_cut
);
2046 __merge_without_buffer(__first
, __first_cut
, __new_middle
, __len11
, __len22
,
2048 __merge_without_buffer(__new_middle
, __second_cut
, __last
, __len1
- __len11
,
2049 __len2
- __len22
, __comp
);
2052 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
2054 _BidirectionalIter1
__rotate_adaptive(_BidirectionalIter1 __first
,
2055 _BidirectionalIter1 __middle
,
2056 _BidirectionalIter1 __last
,
2057 _Distance __len1
, _Distance __len2
,
2058 _BidirectionalIter2 __buffer
,
2059 _Distance __buffer_size
) {
2060 _BidirectionalIter2 __buffer_end
;
2061 if (__len1
> __len2
&& __len2
<= __buffer_size
) {
2062 __buffer_end
= copy(__middle
, __last
, __buffer
);
2063 copy_backward(__first
, __middle
, __last
);
2064 return copy(__buffer
, __buffer_end
, __first
);
2066 else if (__len1
<= __buffer_size
) {
2067 __buffer_end
= copy(__first
, __middle
, __buffer
);
2068 copy(__middle
, __last
, __first
);
2069 return copy_backward(__buffer
, __buffer_end
, __last
);
2072 return rotate(__first
, __middle
, __last
);
2075 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
2076 class _BidirectionalIter3
>
2077 _BidirectionalIter3
__merge_backward(_BidirectionalIter1 __first1
,
2078 _BidirectionalIter1 __last1
,
2079 _BidirectionalIter2 __first2
,
2080 _BidirectionalIter2 __last2
,
2081 _BidirectionalIter3 __result
) {
2082 if (__first1
== __last1
)
2083 return copy_backward(__first2
, __last2
, __result
);
2084 if (__first2
== __last2
)
2085 return copy_backward(__first1
, __last1
, __result
);
2089 if (*__last2
< *__last1
) {
2090 *--__result
= *__last1
;
2091 if (__first1
== __last1
)
2092 return copy_backward(__first2
, ++__last2
, __result
);
2096 *--__result
= *__last2
;
2097 if (__first2
== __last2
)
2098 return copy_backward(__first1
, ++__last1
, __result
);
2104 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
2105 class _BidirectionalIter3
, class _Compare
>
2106 _BidirectionalIter3
__merge_backward(_BidirectionalIter1 __first1
,
2107 _BidirectionalIter1 __last1
,
2108 _BidirectionalIter2 __first2
,
2109 _BidirectionalIter2 __last2
,
2110 _BidirectionalIter3 __result
,
2112 if (__first1
== __last1
)
2113 return copy_backward(__first2
, __last2
, __result
);
2114 if (__first2
== __last2
)
2115 return copy_backward(__first1
, __last1
, __result
);
2119 if (__comp(*__last2
, *__last1
)) {
2120 *--__result
= *__last1
;
2121 if (__first1
== __last1
)
2122 return copy_backward(__first2
, ++__last2
, __result
);
2126 *--__result
= *__last2
;
2127 if (__first2
== __last2
)
2128 return copy_backward(__first1
, ++__last1
, __result
);
2134 template <class _BidirectionalIter
, class _Distance
, class _Pointer
>
2135 void __merge_adaptive(_BidirectionalIter __first
,
2136 _BidirectionalIter __middle
,
2137 _BidirectionalIter __last
,
2138 _Distance __len1
, _Distance __len2
,
2139 _Pointer __buffer
, _Distance __buffer_size
) {
2140 if (__len1
<= __len2
&& __len1
<= __buffer_size
) {
2141 _Pointer __buffer_end
= copy(__first
, __middle
, __buffer
);
2142 merge(__buffer
, __buffer_end
, __middle
, __last
, __first
);
2144 else if (__len2
<= __buffer_size
) {
2145 _Pointer __buffer_end
= copy(__middle
, __last
, __buffer
);
2146 __merge_backward(__first
, __middle
, __buffer
, __buffer_end
, __last
);
2149 _BidirectionalIter __first_cut
= __first
;
2150 _BidirectionalIter __second_cut
= __middle
;
2151 _Distance __len11
= 0;
2152 _Distance __len22
= 0;
2153 if (__len1
> __len2
) {
2154 __len11
= __len1
/ 2;
2155 advance(__first_cut
, __len11
);
2156 __second_cut
= lower_bound(__middle
, __last
, *__first_cut
);
2157 distance(__middle
, __second_cut
, __len22
);
2160 __len22
= __len2
/ 2;
2161 advance(__second_cut
, __len22
);
2162 __first_cut
= upper_bound(__first
, __middle
, *__second_cut
);
2163 distance(__first
, __first_cut
, __len11
);
2165 _BidirectionalIter __new_middle
=
2166 __rotate_adaptive(__first_cut
, __middle
, __second_cut
, __len1
- __len11
,
2167 __len22
, __buffer
, __buffer_size
);
2168 __merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
2169 __len22
, __buffer
, __buffer_size
);
2170 __merge_adaptive(__new_middle
, __second_cut
, __last
, __len1
- __len11
,
2171 __len2
- __len22
, __buffer
, __buffer_size
);
2175 template <class _BidirectionalIter
, class _Distance
, class _Pointer
,
2177 void __merge_adaptive(_BidirectionalIter __first
,
2178 _BidirectionalIter __middle
,
2179 _BidirectionalIter __last
,
2180 _Distance __len1
, _Distance __len2
,
2181 _Pointer __buffer
, _Distance __buffer_size
,
2183 if (__len1
<= __len2
&& __len1
<= __buffer_size
) {
2184 _Pointer __buffer_end
= copy(__first
, __middle
, __buffer
);
2185 merge(__buffer
, __buffer_end
, __middle
, __last
, __first
, __comp
);
2187 else if (__len2
<= __buffer_size
) {
2188 _Pointer __buffer_end
= copy(__middle
, __last
, __buffer
);
2189 __merge_backward(__first
, __middle
, __buffer
, __buffer_end
, __last
,
2193 _BidirectionalIter __first_cut
= __first
;
2194 _BidirectionalIter __second_cut
= __middle
;
2195 _Distance __len11
= 0;
2196 _Distance __len22
= 0;
2197 if (__len1
> __len2
) {
2198 __len11
= __len1
/ 2;
2199 advance(__first_cut
, __len11
);
2200 __second_cut
= lower_bound(__middle
, __last
, *__first_cut
, __comp
);
2201 distance(__middle
, __second_cut
, __len22
);
2204 __len22
= __len2
/ 2;
2205 advance(__second_cut
, __len22
);
2206 __first_cut
= upper_bound(__first
, __middle
, *__second_cut
, __comp
);
2207 distance(__first
, __first_cut
, __len11
);
2209 _BidirectionalIter __new_middle
=
2210 __rotate_adaptive(__first_cut
, __middle
, __second_cut
, __len1
- __len11
,
2211 __len22
, __buffer
, __buffer_size
);
2212 __merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
2213 __len22
, __buffer
, __buffer_size
, __comp
);
2214 __merge_adaptive(__new_middle
, __second_cut
, __last
, __len1
- __len11
,
2215 __len2
- __len22
, __buffer
, __buffer_size
, __comp
);
2219 template <class _BidirectionalIter
, class _Tp
, class _Distance
>
2220 inline void __inplace_merge_aux(_BidirectionalIter __first
,
2221 _BidirectionalIter __middle
,
2222 _BidirectionalIter __last
, _Tp
*, _Distance
*) {
2223 _Distance __len1
= 0;
2224 distance(__first
, __middle
, __len1
);
2225 _Distance __len2
= 0;
2226 distance(__middle
, __last
, __len2
);
2228 _Temporary_buffer
<_BidirectionalIter
, _Tp
> __buf(__first
, __last
);
2229 if (__buf
.begin() == 0)
2230 __merge_without_buffer(__first
, __middle
, __last
, __len1
, __len2
);
2232 __merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
2233 __buf
.begin(), _Distance(__buf
.size()));
2236 template <class _BidirectionalIter
, class _Tp
,
2237 class _Distance
, class _Compare
>
2238 inline void __inplace_merge_aux(_BidirectionalIter __first
,
2239 _BidirectionalIter __middle
,
2240 _BidirectionalIter __last
, _Tp
*, _Distance
*,
2242 _Distance __len1
= 0;
2243 distance(__first
, __middle
, __len1
);
2244 _Distance __len2
= 0;
2245 distance(__middle
, __last
, __len2
);
2247 _Temporary_buffer
<_BidirectionalIter
, _Tp
> __buf(__first
, __last
);
2248 if (__buf
.begin() == 0)
2249 __merge_without_buffer(__first
, __middle
, __last
, __len1
, __len2
, __comp
);
2251 __merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
2252 __buf
.begin(), _Distance(__buf
.size()),
2256 template <class _BidirectionalIter
>
2257 inline void inplace_merge(_BidirectionalIter __first
,
2258 _BidirectionalIter __middle
,
2259 _BidirectionalIter __last
) {
2260 if (__first
== __middle
|| __middle
== __last
)
2262 __inplace_merge_aux(__first
, __middle
, __last
,
2263 __VALUE_TYPE(__first
), __DISTANCE_TYPE(__first
));
2266 template <class _BidirectionalIter
, class _Compare
>
2267 inline void inplace_merge(_BidirectionalIter __first
,
2268 _BidirectionalIter __middle
,
2269 _BidirectionalIter __last
, _Compare __comp
) {
2270 if (__first
== __middle
|| __middle
== __last
)
2272 __inplace_merge_aux(__first
, __middle
, __last
,
2273 __VALUE_TYPE(__first
), __DISTANCE_TYPE(__first
),
2277 // Set algorithms: includes, set_union, set_intersection, set_difference,
2278 // set_symmetric_difference. All of these algorithms have the precondition
2279 // that their input ranges are sorted and the postcondition that their output
2280 // ranges are sorted.
2282 template <class _InputIter1
, class _InputIter2
>
2283 bool includes(_InputIter1 __first1
, _InputIter1 __last1
,
2284 _InputIter2 __first2
, _InputIter2 __last2
) {
2285 while (__first1
!= __last1
&& __first2
!= __last2
)
2286 if (*__first2
< *__first1
)
2288 else if(*__first1
< *__first2
)
2291 ++__first1
, ++__first2
;
2293 return __first2
== __last2
;
2296 template <class _InputIter1
, class _InputIter2
, class _Compare
>
2297 bool includes(_InputIter1 __first1
, _InputIter1 __last1
,
2298 _InputIter2 __first2
, _InputIter2 __last2
, _Compare __comp
) {
2299 while (__first1
!= __last1
&& __first2
!= __last2
)
2300 if (__comp(*__first2
, *__first1
))
2302 else if(__comp(*__first1
, *__first2
))
2305 ++__first1
, ++__first2
;
2307 return __first2
== __last2
;
2310 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
2311 _OutputIter
set_union(_InputIter1 __first1
, _InputIter1 __last1
,
2312 _InputIter2 __first2
, _InputIter2 __last2
,
2313 _OutputIter __result
) {
2314 while (__first1
!= __last1
&& __first2
!= __last2
) {
2315 if (*__first1
< *__first2
) {
2316 *__result
= *__first1
;
2319 else if (*__first2
< *__first1
) {
2320 *__result
= *__first2
;
2324 *__result
= *__first1
;
2330 return copy(__first2
, __last2
, copy(__first1
, __last1
, __result
));
2333 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
2335 _OutputIter
set_union(_InputIter1 __first1
, _InputIter1 __last1
,
2336 _InputIter2 __first2
, _InputIter2 __last2
,
2337 _OutputIter __result
, _Compare __comp
) {
2338 while (__first1
!= __last1
&& __first2
!= __last2
) {
2339 if (__comp(*__first1
, *__first2
)) {
2340 *__result
= *__first1
;
2343 else if (__comp(*__first2
, *__first1
)) {
2344 *__result
= *__first2
;
2348 *__result
= *__first1
;
2354 return copy(__first2
, __last2
, copy(__first1
, __last1
, __result
));
2357 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
2358 _OutputIter
set_intersection(_InputIter1 __first1
, _InputIter1 __last1
,
2359 _InputIter2 __first2
, _InputIter2 __last2
,
2360 _OutputIter __result
) {
2361 while (__first1
!= __last1
&& __first2
!= __last2
)
2362 if (*__first1
< *__first2
)
2364 else if (*__first2
< *__first1
)
2367 *__result
= *__first1
;
2375 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
2377 _OutputIter
set_intersection(_InputIter1 __first1
, _InputIter1 __last1
,
2378 _InputIter2 __first2
, _InputIter2 __last2
,
2379 _OutputIter __result
, _Compare __comp
) {
2380 while (__first1
!= __last1
&& __first2
!= __last2
)
2381 if (__comp(*__first1
, *__first2
))
2383 else if (__comp(*__first2
, *__first1
))
2386 *__result
= *__first1
;
2394 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
2395 _OutputIter
set_difference(_InputIter1 __first1
, _InputIter1 __last1
,
2396 _InputIter2 __first2
, _InputIter2 __last2
,
2397 _OutputIter __result
) {
2398 while (__first1
!= __last1
&& __first2
!= __last2
)
2399 if (*__first1
< *__first2
) {
2400 *__result
= *__first1
;
2404 else if (*__first2
< *__first1
)
2410 return copy(__first1
, __last1
, __result
);
2413 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
2415 _OutputIter
set_difference(_InputIter1 __first1
, _InputIter1 __last1
,
2416 _InputIter2 __first2
, _InputIter2 __last2
,
2417 _OutputIter __result
, _Compare __comp
) {
2418 while (__first1
!= __last1
&& __first2
!= __last2
)
2419 if (__comp(*__first1
, *__first2
)) {
2420 *__result
= *__first1
;
2424 else if (__comp(*__first2
, *__first1
))
2430 return copy(__first1
, __last1
, __result
);
2433 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
2435 set_symmetric_difference(_InputIter1 __first1
, _InputIter1 __last1
,
2436 _InputIter2 __first2
, _InputIter2 __last2
,
2437 _OutputIter __result
) {
2438 while (__first1
!= __last1
&& __first2
!= __last2
)
2439 if (*__first1
< *__first2
) {
2440 *__result
= *__first1
;
2444 else if (*__first2
< *__first1
) {
2445 *__result
= *__first2
;
2453 return copy(__first2
, __last2
, copy(__first1
, __last1
, __result
));
2456 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
2459 set_symmetric_difference(_InputIter1 __first1
, _InputIter1 __last1
,
2460 _InputIter2 __first2
, _InputIter2 __last2
,
2461 _OutputIter __result
,
2463 while (__first1
!= __last1
&& __first2
!= __last2
)
2464 if (__comp(*__first1
, *__first2
)) {
2465 *__result
= *__first1
;
2469 else if (__comp(*__first2
, *__first1
)) {
2470 *__result
= *__first2
;
2478 return copy(__first2
, __last2
, copy(__first1
, __last1
, __result
));
2481 // min_element and max_element, with and without an explicitly supplied
2482 // comparison function.
2484 template <class _ForwardIter
>
2485 _ForwardIter
max_element(_ForwardIter __first
, _ForwardIter __last
) {
2486 if (__first
== __last
) return __first
;
2487 _ForwardIter __result
= __first
;
2488 while (++__first
!= __last
)
2489 if (*__result
< *__first
)
2494 template <class _ForwardIter
, class _Compare
>
2495 _ForwardIter
max_element(_ForwardIter __first
, _ForwardIter __last
,
2497 if (__first
== __last
) return __first
;
2498 _ForwardIter __result
= __first
;
2499 while (++__first
!= __last
)
2500 if (__comp(*__result
, *__first
)) __result
= __first
;
2504 template <class _ForwardIter
>
2505 _ForwardIter
min_element(_ForwardIter __first
, _ForwardIter __last
) {
2506 if (__first
== __last
) return __first
;
2507 _ForwardIter __result
= __first
;
2508 while (++__first
!= __last
)
2509 if (*__first
< *__result
)
2514 template <class _ForwardIter
, class _Compare
>
2515 _ForwardIter
min_element(_ForwardIter __first
, _ForwardIter __last
,
2517 if (__first
== __last
) return __first
;
2518 _ForwardIter __result
= __first
;
2519 while (++__first
!= __last
)
2520 if (__comp(*__first
, *__result
))
2525 // next_permutation and prev_permutation, with and without an explicitly
2526 // supplied comparison function.
2528 template <class _BidirectionalIter
>
2529 bool next_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
) {
2530 if (__first
== __last
)
2532 _BidirectionalIter __i
= __first
;
2540 _BidirectionalIter __ii
= __i
;
2543 _BidirectionalIter __j
= __last
;
2544 while (!(*__i
< *--__j
))
2546 iter_swap(__i
, __j
);
2547 reverse(__ii
, __last
);
2550 if (__i
== __first
) {
2551 reverse(__first
, __last
);
2557 template <class _BidirectionalIter
, class _Compare
>
2558 bool next_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
2560 if (__first
== __last
)
2562 _BidirectionalIter __i
= __first
;
2570 _BidirectionalIter __ii
= __i
;
2572 if (__comp(*__i
, *__ii
)) {
2573 _BidirectionalIter __j
= __last
;
2574 while (!__comp(*__i
, *--__j
))
2576 iter_swap(__i
, __j
);
2577 reverse(__ii
, __last
);
2580 if (__i
== __first
) {
2581 reverse(__first
, __last
);
2587 template <class _BidirectionalIter
>
2588 bool prev_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
) {
2589 if (__first
== __last
)
2591 _BidirectionalIter __i
= __first
;
2599 _BidirectionalIter __ii
= __i
;
2602 _BidirectionalIter __j
= __last
;
2603 while (!(*--__j
< *__i
))
2605 iter_swap(__i
, __j
);
2606 reverse(__ii
, __last
);
2609 if (__i
== __first
) {
2610 reverse(__first
, __last
);
2616 template <class _BidirectionalIter
, class _Compare
>
2617 bool prev_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
2619 if (__first
== __last
)
2621 _BidirectionalIter __i
= __first
;
2629 _BidirectionalIter __ii
= __i
;
2631 if (__comp(*__ii
, *__i
)) {
2632 _BidirectionalIter __j
= __last
;
2633 while (!__comp(*--__j
, *__i
))
2635 iter_swap(__i
, __j
);
2636 reverse(__ii
, __last
);
2639 if (__i
== __first
) {
2640 reverse(__first
, __last
);
2646 // find_first_of, with and without an explicitly supplied comparison function.
2648 template <class _InputIter
, class _ForwardIter
>
2649 _InputIter
find_first_of(_InputIter __first1
, _InputIter __last1
,
2650 _ForwardIter __first2
, _ForwardIter __last2
)
2652 for ( ; __first1
!= __last1
; ++__first1
)
2653 for (_ForwardIter __iter
= __first2
; __iter
!= __last2
; ++__iter
)
2654 if (*__first1
== *__iter
)
2659 template <class _InputIter
, class _ForwardIter
, class _BinaryPredicate
>
2660 _InputIter
find_first_of(_InputIter __first1
, _InputIter __last1
,
2661 _ForwardIter __first2
, _ForwardIter __last2
,
2662 _BinaryPredicate __comp
)
2664 for ( ; __first1
!= __last1
; ++__first1
)
2665 for (_ForwardIter __iter
= __first2
; __iter
!= __last2
; ++__iter
)
2666 if (__comp(*__first1
, *__iter
))
2672 // find_end, with and without an explicitly supplied comparison function.
2673 // Search [first2, last2) as a subsequence in [first1, last1), and return
2674 // the *last* possible match. Note that find_end for bidirectional iterators
2675 // is much faster than for forward iterators.
2677 // find_end for forward iterators.
2678 template <class _ForwardIter1
, class _ForwardIter2
>
2679 _ForwardIter1
__find_end(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
2680 _ForwardIter2 __first2
, _ForwardIter2 __last2
,
2681 forward_iterator_tag
, forward_iterator_tag
)
2683 if (__first2
== __last2
)
2686 _ForwardIter1 __result
= __last1
;
2688 _ForwardIter1 __new_result
2689 = search(__first1
, __last1
, __first2
, __last2
);
2690 if (__new_result
== __last1
)
2693 __result
= __new_result
;
2694 __first1
= __new_result
;
2701 template <class _ForwardIter1
, class _ForwardIter2
,
2702 class _BinaryPredicate
>
2703 _ForwardIter1
__find_end(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
2704 _ForwardIter2 __first2
, _ForwardIter2 __last2
,
2705 forward_iterator_tag
, forward_iterator_tag
,
2706 _BinaryPredicate __comp
)
2708 if (__first2
== __last2
)
2711 _ForwardIter1 __result
= __last1
;
2713 _ForwardIter1 __new_result
2714 = search(__first1
, __last1
, __first2
, __last2
, __comp
);
2715 if (__new_result
== __last1
)
2718 __result
= __new_result
;
2719 __first1
= __new_result
;
2726 // find_end for bidirectional iterators. Requires partial specialization.
2727 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
2729 template <class _BidirectionalIter1
, class _BidirectionalIter2
>
2731 __find_end(_BidirectionalIter1 __first1
, _BidirectionalIter1 __last1
,
2732 _BidirectionalIter2 __first2
, _BidirectionalIter2 __last2
,
2733 bidirectional_iterator_tag
, bidirectional_iterator_tag
)
2735 typedef reverse_iterator
<_BidirectionalIter1
> _RevIter1
;
2736 typedef reverse_iterator
<_BidirectionalIter2
> _RevIter2
;
2738 _RevIter1
__rlast1(__first1
);
2739 _RevIter2
__rlast2(__first2
);
2740 _RevIter1 __rresult
= search(_RevIter1(__last1
), __rlast1
,
2741 _RevIter2(__last2
), __rlast2
);
2743 if (__rresult
== __rlast1
)
2746 _BidirectionalIter1 __result
= __rresult
.base();
2747 advance(__result
, -distance(__first2
, __last2
));
2752 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
2753 class _BinaryPredicate
>
2755 __find_end(_BidirectionalIter1 __first1
, _BidirectionalIter1 __last1
,
2756 _BidirectionalIter2 __first2
, _BidirectionalIter2 __last2
,
2757 bidirectional_iterator_tag
, bidirectional_iterator_tag
,
2758 _BinaryPredicate __comp
)
2760 typedef reverse_iterator
<_BidirectionalIter1
> _RevIter1
;
2761 typedef reverse_iterator
<_BidirectionalIter2
> _RevIter2
;
2763 _RevIter1
__rlast1(__first1
);
2764 _RevIter2
__rlast2(__first2
);
2765 _RevIter1 __rresult
= search(_RevIter1(__last1
), __rlast1
,
2766 _RevIter2(__last2
), __rlast2
,
2769 if (__rresult
== __rlast1
)
2772 _BidirectionalIter1 __result
= __rresult
.base();
2773 advance(__result
, -distance(__first2
, __last2
));
2777 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
2779 // Dispatching functions for find_end.
2781 template <class _ForwardIter1
, class _ForwardIter2
>
2782 inline _ForwardIter1
2783 find_end(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
2784 _ForwardIter2 __first2
, _ForwardIter2 __last2
)
2786 return __find_end(__first1
, __last1
, __first2
, __last2
,
2787 __ITERATOR_CATEGORY(__first1
),
2788 __ITERATOR_CATEGORY(__first2
));
2791 template <class _ForwardIter1
, class _ForwardIter2
,
2792 class _BinaryPredicate
>
2793 inline _ForwardIter1
2794 find_end(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
2795 _ForwardIter2 __first2
, _ForwardIter2 __last2
,
2796 _BinaryPredicate __comp
)
2798 return __find_end(__first1
, __last1
, __first2
, __last2
,
2799 __ITERATOR_CATEGORY(__first1
),
2800 __ITERATOR_CATEGORY(__first2
),
2804 // is_heap, a predicate testing whether or not a range is
2805 // a heap. This function is an extension, not part of the C++
2808 template <class _RandomAccessIter
, class _Distance
>
2809 bool __is_heap(_RandomAccessIter __first
, _Distance __n
)
2811 _Distance __parent
= 0;
2812 for (_Distance __child
= 1; __child
< __n
; ++__child
) {
2813 if (__first
[__parent
] < __first
[__child
])
2815 if ((__child
& 1) == 0)
2821 template <class _RandomAccessIter
, class _Distance
, class _StrictWeakOrdering
>
2822 bool __is_heap(_RandomAccessIter __first
, _StrictWeakOrdering __comp
,
2825 _Distance __parent
= 0;
2826 for (_Distance __child
= 1; __child
< __n
; ++__child
) {
2827 if (__comp(__first
[__parent
], __first
[__child
]))
2829 if ((__child
& 1) == 0)
2835 template <class _RandomAccessIter
>
2836 inline bool is_heap(_RandomAccessIter __first
, _RandomAccessIter __last
)
2838 return __is_heap(__first
, __last
- __first
);
2842 template <class _RandomAccessIter
, class _StrictWeakOrdering
>
2843 inline bool is_heap(_RandomAccessIter __first
, _RandomAccessIter __last
,
2844 _StrictWeakOrdering __comp
)
2846 return __is_heap(__first
, __comp
, __last
- __first
);
2849 // is_sorted, a predicated testing whether a range is sorted in
2850 // nondescending order. This is an extension, not part of the C++
2853 template <class _ForwardIter
>
2854 bool is_sorted(_ForwardIter __first
, _ForwardIter __last
)
2856 if (__first
== __last
)
2859 _ForwardIter __next
= __first
;
2860 for (++__next
; __next
!= __last
; __first
= __next
, ++__next
) {
2861 if (*__next
< *__first
)
2868 template <class _ForwardIter
, class _StrictWeakOrdering
>
2869 bool is_sorted(_ForwardIter __first
, _ForwardIter __last
,
2870 _StrictWeakOrdering __comp
)
2872 if (__first
== __last
)
2875 _ForwardIter __next
= __first
;
2876 for (++__next
; __next
!= __last
; __first
= __next
, ++__next
) {
2877 if (__comp(*__next
, *__first
))
2884 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
2885 #pragma reset woff 1209
2890 #endif /* __SGI_STL_INTERNAL_ALGO_H */