4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
29 #if !defined (_STLP_INTERNAL_ALGO_H)
30 # include <stl/_algo.h>
33 #ifndef _STLP_INTERNAL_TEMPBUF_H
34 # include <stl/_tempbuf.h>
39 _STLP_MOVE_TO_PRIV_NAMESPACE
41 template <class _BidirectionalIter
, class _Distance
, class _Compare
>
42 void __merge_without_buffer(_BidirectionalIter __first
,
43 _BidirectionalIter __middle
,
44 _BidirectionalIter __last
,
45 _Distance __len1
, _Distance __len2
,
49 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
50 class _BidirectionalIter3
, class _Compare
>
51 _BidirectionalIter3
__merge_backward(_BidirectionalIter1 __first1
,
52 _BidirectionalIter1 __last1
,
53 _BidirectionalIter2 __first2
,
54 _BidirectionalIter2 __last2
,
55 _BidirectionalIter3 __result
,
59 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
62 const _Tp
& __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
) {
78 template <class _Tp
, class _Compare
>
79 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
83 __median(const _Tp
& __a
, const _Tp
& __b
, const _Tp
& __c
, _Compare __comp
) {
84 if (__comp(__a
, __b
)) {
85 _STLP_VERBOSE_ASSERT(!__comp(__b
, __a
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
86 if (__comp(__b
, __c
)) {
87 _STLP_VERBOSE_ASSERT(!__comp(__c
, __b
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
90 else if (__comp(__a
, __c
)) {
91 _STLP_VERBOSE_ASSERT(!__comp(__c
, __a
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
97 else if (__comp(__a
, __c
)) {
98 _STLP_VERBOSE_ASSERT(!__comp(__c
, __a
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
101 else if (__comp(__b
, __c
)) {
102 _STLP_VERBOSE_ASSERT(!__comp(__c
, __b
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
109 _STLP_MOVE_TO_STD_NAMESPACE
111 template <class _ForwardIter1
, class _ForwardIter2
>
112 _ForwardIter1
search(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
113 _ForwardIter2 __first2
, _ForwardIter2 __last2
) {
114 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
115 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
116 // Test for empty ranges
117 if (__first1
== __last1
|| __first2
== __last2
)
120 // Test for a pattern of length 1.
121 _ForwardIter2
__p1(__first2
);
123 if ( ++__p1
== __last2
)
124 return find(__first1
, __last1
, *__first2
);
128 for ( ; ; ) { // __first1 != __last1 will be checked in find below
129 __first1
= find(__first1
, __last1
, *__first2
);
130 if (__first1
== __last1
)
133 _ForwardIter2 __p
= __p1
;
134 _ForwardIter1 __current
= __first1
;
135 if (++__current
== __last1
)
138 while (*__current
== *__p
) {
139 if (++__p
== __last2
)
141 if (++__current
== __last1
)
150 _STLP_MOVE_TO_PRIV_NAMESPACE
152 template <class _RandomAccessIter
, class _Integer
, class _Tp
,
153 class _BinaryPred
, class _Distance
>
154 _RandomAccessIter
__search_n(_RandomAccessIter __first
, _RandomAccessIter __last
,
155 _Integer __count
, const _Tp
& __val
, _BinaryPred __pred
,
156 _Distance
*, const random_access_iterator_tag
&)
158 _Distance __tailSize
= __last
- __first
;
159 const _Distance __pattSize
= __count
;
160 const _Distance __skipOffset
= __pattSize
- 1;
161 _RandomAccessIter __backTrack
;
162 _Distance __remainder
, __prevRemainder
;
164 for ( _RandomAccessIter __lookAhead
= __first
+ __skipOffset
; __tailSize
>= __pattSize
; __lookAhead
+= __pattSize
) { // the main loop...
165 //__lookAhead here is always pointing to the last element of next possible match.
166 __tailSize
-= __pattSize
;
168 while ( !__pred(*__lookAhead
, __val
) ) { // the skip loop...
169 if (__tailSize
< __pattSize
)
172 __lookAhead
+= __pattSize
;
173 __tailSize
-= __pattSize
;
176 if ( __skipOffset
== 0 ) {
177 return (__lookAhead
- __skipOffset
); //Success
180 __remainder
= __skipOffset
;
182 for (__backTrack
= __lookAhead
; __pred(*--__backTrack
, __val
); ) {
183 if (--__remainder
== 0)
184 return (__lookAhead
- __skipOffset
); //Success
187 if (__remainder
> __tailSize
)
188 return __last
; //failure
190 __lookAhead
+= __remainder
;
191 __tailSize
-= __remainder
;
193 while ( __pred(*__lookAhead
, __val
) ) {
194 __prevRemainder
= __remainder
;
195 __backTrack
= __lookAhead
;
198 if (--__remainder
== 0)
199 return (__lookAhead
- __skipOffset
); //Success
200 } while (__pred(*--__backTrack
, __val
));
202 //adjust remainder for next comparison
203 __remainder
+= __pattSize
- __prevRemainder
;
205 if (__remainder
> __tailSize
)
206 return __last
; //failure
208 __lookAhead
+= __remainder
;
209 __tailSize
-= __remainder
;
212 //__lookAhead here is always pointing to the element of the last mismatch.
215 return __last
; //failure
218 template <class _ForwardIter
, class _Integer
, class _Tp
,
219 class _Distance
, class _BinaryPred
>
220 _ForwardIter
__search_n(_ForwardIter __first
, _ForwardIter __last
,
221 _Integer __count
, const _Tp
& __val
, _BinaryPred __pred
,
222 _Distance
*, const forward_iterator_tag
&) {
223 for (; (__first
!= __last
) && !__pred(*__first
, __val
); ++__first
) {}
224 while (__first
!= __last
) {
225 _Integer __n
= __count
- 1;
226 _ForwardIter __i
= __first
;
228 while (__i
!= __last
&& __n
!= 0 && __pred(*__i
, __val
)) {
234 else if (__i
!= __last
)
235 for (__first
= ++__i
; (__first
!= __last
) && !__pred(*__first
, __val
); ++__first
) {}
242 _STLP_MOVE_TO_STD_NAMESPACE
244 // search_n. Search for __count consecutive copies of __val.
245 template <class _ForwardIter
, class _Integer
, class _Tp
>
246 _ForwardIter
search_n(_ForwardIter __first
, _ForwardIter __last
,
247 _Integer __count
, const _Tp
& __val
) {
248 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
252 //We use find when __count == 1 to use potential find overload.
253 return find(__first
, __last
, __val
);
254 return _STLP_PRIV
__search_n(__first
, __last
, __count
, __val
, equal_to
<_Tp
>(),
255 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
),
256 _STLP_ITERATOR_CATEGORY(__first
, _ForwardIter
));
259 template <class _ForwardIter
, class _Integer
, class _Tp
, class _BinaryPred
>
260 _ForwardIter
search_n(_ForwardIter __first
, _ForwardIter __last
,
261 _Integer __count
, const _Tp
& __val
,
262 _BinaryPred __binary_pred
) {
263 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
266 return _STLP_PRIV
__search_n(__first
, __last
, __count
, __val
, __binary_pred
,
267 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
),
268 _STLP_ITERATOR_CATEGORY(__first
, _ForwardIter
));
271 template <class _ForwardIter1
, class _ForwardIter2
>
273 find_end(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
274 _ForwardIter2 __first2
, _ForwardIter2 __last2
) {
275 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
276 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
277 return _STLP_PRIV
__find_end(__first1
, __last1
, __first2
, __last2
,
278 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
279 _STLP_ITERATOR_CATEGORY(__first1
, _ForwardIter1
),
280 _STLP_ITERATOR_CATEGORY(__first2
, _ForwardIter2
),
282 forward_iterator_tag(),
283 forward_iterator_tag(),
285 _STLP_PRIV
__equal_to(_STLP_VALUE_TYPE(__first1
, _ForwardIter1
))
289 // unique and unique_copy
290 _STLP_MOVE_TO_PRIV_NAMESPACE
292 template <class _InputIterator
, class _OutputIterator
, class _BinaryPredicate
,
294 _STLP_INLINE_LOOP _OutputIterator
295 __unique_copy(_InputIterator __first
, _InputIterator __last
,
296 _OutputIterator __result
,
297 _BinaryPredicate __binary_pred
, _Tp
*) {
298 _Tp __val
= *__first
;
300 while (++__first
!= __last
)
301 if (!__binary_pred(__val
, *__first
)) {
308 template <class _InputIter
, class _OutputIter
, class _BinaryPredicate
>
310 __unique_copy(_InputIter __first
, _InputIter __last
,_OutputIter __result
,
311 _BinaryPredicate __binary_pred
, const output_iterator_tag
&) {
312 return _STLP_PRIV
__unique_copy(__first
, __last
, __result
, __binary_pred
,
313 _STLP_VALUE_TYPE(__first
, _InputIter
));
316 template <class _InputIter
, class _ForwardIter
, class _BinaryPredicate
>
317 _STLP_INLINE_LOOP _ForwardIter
318 __unique_copy(_InputIter __first
, _InputIter __last
, _ForwardIter __result
,
319 _BinaryPredicate __binary_pred
, const forward_iterator_tag
&) {
320 *__result
= *__first
;
321 while (++__first
!= __last
)
322 if (!__binary_pred(*__result
, *__first
)) *++__result
= *__first
;
326 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
327 template <class _InputIterator
, class _BidirectionalIterator
, class _BinaryPredicate
>
328 inline _BidirectionalIterator
329 __unique_copy(_InputIterator __first
, _InputIterator __last
,
330 _BidirectionalIterator __result
, _BinaryPredicate __binary_pred
,
331 const bidirectional_iterator_tag
&) {
332 return _STLP_PRIV
__unique_copy(__first
, __last
, __result
, __binary_pred
, forward_iterator_tag());
335 template <class _InputIterator
, class _RandomAccessIterator
, class _BinaryPredicate
>
336 inline _RandomAccessIterator
337 __unique_copy(_InputIterator __first
, _InputIterator __last
,
338 _RandomAccessIterator __result
, _BinaryPredicate __binary_pred
,
339 const random_access_iterator_tag
&) {
340 return _STLP_PRIV
__unique_copy(__first
, __last
, __result
, __binary_pred
, forward_iterator_tag());
342 #endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
344 _STLP_MOVE_TO_STD_NAMESPACE
346 template <class _InputIter
, class _OutputIter
>
348 unique_copy(_InputIter __first
, _InputIter __last
, _OutputIter __result
) {
349 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
350 if (__first
== __last
) return __result
;
351 return _STLP_PRIV
__unique_copy(__first
, __last
, __result
,
352 _STLP_PRIV
__equal_to(_STLP_VALUE_TYPE(__first
, _InputIter
)),
353 _STLP_ITERATOR_CATEGORY(__result
, _OutputIter
));
356 template <class _InputIter
, class _OutputIter
, class _BinaryPredicate
>
358 unique_copy(_InputIter __first
, _InputIter __last
,_OutputIter __result
,
359 _BinaryPredicate __binary_pred
) {
360 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
361 if (__first
== __last
) return __result
;
362 return _STLP_PRIV
__unique_copy(__first
, __last
, __result
, __binary_pred
,
363 _STLP_ITERATOR_CATEGORY(__result
, _OutputIter
));
366 // rotate and rotate_copy, and their auxiliary functions
367 _STLP_MOVE_TO_PRIV_NAMESPACE
369 template <class _ForwardIter
, class _Distance
>
370 _ForwardIter
__rotate_aux(_ForwardIter __first
,
371 _ForwardIter __middle
,
374 const forward_iterator_tag
&) {
375 if (__first
== __middle
)
377 if (__last
== __middle
)
380 _ForwardIter __first2
= __middle
;
382 _STLP_STD::swap(*__first
++, *__first2
++);
383 if (__first
== __middle
)
385 } while (__first2
!= __last
);
387 _ForwardIter __new_middle
= __first
;
391 while (__first2
!= __last
) {
392 _STLP_STD::swap (*__first
++, *__first2
++);
393 if (__first
== __middle
)
395 else if (__first2
== __last
)
402 template <class _BidirectionalIter
, class _Distance
>
403 _BidirectionalIter
__rotate_aux(_BidirectionalIter __first
,
404 _BidirectionalIter __middle
,
405 _BidirectionalIter __last
,
407 const bidirectional_iterator_tag
&) {
408 if (__first
== __middle
)
410 if (__last
== __middle
)
413 _STLP_PRIV
__reverse(__first
, __middle
, bidirectional_iterator_tag());
414 _STLP_PRIV
__reverse(__middle
, __last
, bidirectional_iterator_tag());
416 while (__first
!= __middle
&& __middle
!= __last
)
417 _STLP_STD::swap(*__first
++, *--__last
);
419 if (__first
== __middle
) {
420 _STLP_PRIV
__reverse(__middle
, __last
, bidirectional_iterator_tag());
424 _STLP_PRIV
__reverse(__first
, __middle
, bidirectional_iterator_tag());
429 // rotate and rotate_copy, and their auxiliary functions
430 template <class _EuclideanRingElement
>
432 _EuclideanRingElement
__gcd(_EuclideanRingElement __m
,
433 _EuclideanRingElement __n
) {
435 _EuclideanRingElement __t
= __m
% __n
;
442 template <class _RandomAccessIter
, class _Distance
, class _Tp
>
443 _RandomAccessIter
__rotate_aux(_RandomAccessIter __first
,
444 _RandomAccessIter __middle
,
445 _RandomAccessIter __last
,
446 _Distance
*, _Tp
*) {
448 _Distance __n
= __last
- __first
;
449 _Distance __k
= __middle
- __first
;
450 _Distance __l
= __n
- __k
;
451 _RandomAccessIter __result
= __first
+ (__last
- __middle
);
453 if (__k
== 0) /* __first == middle */
457 _STLP_STD::swap_ranges(__first
, __middle
, __middle
);
461 _Distance __d
= _STLP_PRIV
__gcd(__n
, __k
);
463 for (_Distance __i
= 0; __i
< __d
; __i
++) {
464 _Tp __tmp
= *__first
;
465 _RandomAccessIter __p
= __first
;
468 for (_Distance __j
= 0; __j
< __l
/__d
; __j
++) {
469 if (__p
> __first
+ __l
) {
480 for (_Distance __j
= 0; __j
< __k
/__d
- 1; __j
++) {
481 if (__p
< __last
- __k
) {
486 *__p
= * (__p
- __l
);
498 template <class _RandomAccessIter
, class _Distance
>
499 inline _RandomAccessIter
500 __rotate_aux(_RandomAccessIter __first
, _RandomAccessIter __middle
, _RandomAccessIter __last
,
501 _Distance
* __dis
, const random_access_iterator_tag
&) {
502 return _STLP_PRIV
__rotate_aux(__first
, __middle
, __last
,
503 __dis
, _STLP_VALUE_TYPE(__first
, _RandomAccessIter
));
506 template <class _ForwardIter
>
508 __rotate(_ForwardIter __first
, _ForwardIter __middle
, _ForwardIter __last
) {
509 _STLP_DEBUG_CHECK(__check_range(__first
, __middle
))
510 _STLP_DEBUG_CHECK(__check_range(__middle
, __last
))
511 return __rotate_aux(__first
, __middle
, __last
,
512 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
),
513 _STLP_ITERATOR_CATEGORY(__first
, _ForwardIter
));
516 _STLP_MOVE_TO_STD_NAMESPACE
518 template <class _ForwardIter
>
519 void rotate(_ForwardIter __first
, _ForwardIter __middle
, _ForwardIter __last
) {
520 _STLP_PRIV
__rotate(__first
, __middle
, __last
);
523 // Return a random number in the range [0, __n). This function encapsulates
524 // whether we're using rand (part of the standard C library) or lrand48
525 // (not standard, but a much better choice whenever it's available).
526 _STLP_MOVE_TO_PRIV_NAMESPACE
528 template <class _Distance
>
529 inline _Distance
__random_number(_Distance __n
) {
530 #ifdef _STLP_NO_DRAND48
533 return lrand48() % __n
;
537 _STLP_MOVE_TO_STD_NAMESPACE
539 template <class _RandomAccessIter
>
540 void random_shuffle(_RandomAccessIter __first
,
541 _RandomAccessIter __last
) {
542 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
543 if (__first
== __last
) return;
544 for (_RandomAccessIter __i
= __first
+ 1; __i
!= __last
; ++__i
)
545 iter_swap(__i
, __first
+ _STLP_PRIV
__random_number((__i
- __first
) + 1));
548 template <class _RandomAccessIter
, class _RandomNumberGenerator
>
549 void random_shuffle(_RandomAccessIter __first
, _RandomAccessIter __last
,
550 _RandomNumberGenerator
&__rand
) {
551 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
552 if (__first
== __last
) return;
553 for (_RandomAccessIter __i
= __first
+ 1; __i
!= __last
; ++__i
)
554 iter_swap(__i
, __first
+ __rand((__i
- __first
) + 1));
557 #if !defined (_STLP_NO_EXTENSIONS)
558 // random_sample and random_sample_n (extensions, not part of the standard).
559 template <class _ForwardIter
, class _OutputIter
, class _Distance
>
560 _OutputIter
random_sample_n(_ForwardIter __first
, _ForwardIter __last
,
561 _OutputIter __out_ite
, const _Distance __n
) {
562 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
563 _Distance __remaining
= _STLP_STD::distance(__first
, __last
);
564 _Distance __m
= (min
) (__n
, __remaining
);
567 if (_STLP_PRIV
__random_number(__remaining
) < __m
) {
568 *__out_ite
= *__first
;
580 template <class _ForwardIter
, class _OutputIter
, class _Distance
,
581 class _RandomNumberGenerator
>
582 _OutputIter
random_sample_n(_ForwardIter __first
, _ForwardIter __last
,
583 _OutputIter __out_ite
, const _Distance __n
,
584 _RandomNumberGenerator
& __rand
) {
585 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
586 _Distance __remaining
= _STLP_STD::distance(__first
, __last
);
587 _Distance __m
= (min
) (__n
, __remaining
);
590 if (__rand(__remaining
) < __m
) {
591 *__out_ite
= *__first
;
602 _STLP_MOVE_TO_PRIV_NAMESPACE
604 template <class _InputIter
, class _RandomAccessIter
, class _Distance
>
605 _RandomAccessIter
__random_sample(_InputIter __first
, _InputIter __last
,
606 _RandomAccessIter __out_ite
,
607 const _Distance __n
) {
610 for ( ; __first
!= __last
&& __m
< __n
; ++__m
, ++__first
)
611 __out_ite
[__m
] = *__first
;
613 while (__first
!= __last
) {
615 _Distance __M
= __random_number(__t
);
617 __out_ite
[__M
] = *__first
;
621 return __out_ite
+ __m
;
624 template <class _InputIter
, class _RandomAccessIter
,
625 class _RandomNumberGenerator
, class _Distance
>
626 _RandomAccessIter
__random_sample(_InputIter __first
, _InputIter __last
,
627 _RandomAccessIter __out_ite
,
628 _RandomNumberGenerator
& __rand
,
629 const _Distance __n
) {
632 for ( ; __first
!= __last
&& __m
< __n
; ++__m
, ++__first
)
633 __out_ite
[__m
] = *__first
;
635 while (__first
!= __last
) {
637 _Distance __M
= __rand(__t
);
639 __out_ite
[__M
] = *__first
;
643 return __out_ite
+ __m
;
646 _STLP_MOVE_TO_STD_NAMESPACE
648 template <class _InputIter
, class _RandomAccessIter
>
650 random_sample(_InputIter __first
, _InputIter __last
,
651 _RandomAccessIter __out_first
, _RandomAccessIter __out_last
) {
652 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
653 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__out_first
, __out_last
))
654 return _STLP_PRIV
__random_sample(__first
, __last
,
655 __out_first
, __out_last
- __out_first
);
658 template <class _InputIter
, class _RandomAccessIter
, class _RandomNumberGenerator
>
660 random_sample(_InputIter __first
, _InputIter __last
,
661 _RandomAccessIter __out_first
, _RandomAccessIter __out_last
,
662 _RandomNumberGenerator
& __rand
) {
663 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
664 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__out_first
, __out_last
))
665 return _STLP_PRIV
__random_sample(__first
, __last
,
667 __out_last
- __out_first
);
670 #endif /* _STLP_NO_EXTENSIONS */
672 // partition, stable_partition, and their auxiliary functions
673 _STLP_MOVE_TO_PRIV_NAMESPACE
675 template <class _ForwardIter
, class _Predicate
>
676 _STLP_INLINE_LOOP _ForwardIter
__partition(_ForwardIter __first
,
679 const forward_iterator_tag
&) {
680 if (__first
== __last
) return __first
;
682 while (__pred(*__first
))
683 if (++__first
== __last
) return __first
;
685 _ForwardIter __next
= __first
;
687 while (++__next
!= __last
) {
688 if (__pred(*__next
)) {
689 _STLP_STD::swap(*__first
, *__next
);
696 template <class _BidirectionalIter
, class _Predicate
>
697 _STLP_INLINE_LOOP _BidirectionalIter
__partition(_BidirectionalIter __first
,
698 _BidirectionalIter __last
,
700 const bidirectional_iterator_tag
&) {
703 if (__first
== __last
)
705 else if (__pred(*__first
))
712 if (__first
== __last
)
714 else if (!__pred(*__last
))
719 iter_swap(__first
, __last
);
724 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
725 template <class _BidirectionalIter
, class _Predicate
>
727 _BidirectionalIter
__partition(_BidirectionalIter __first
,
728 _BidirectionalIter __last
,
730 const random_access_iterator_tag
&) {
731 return __partition(__first
, __last
, __pred
, bidirectional_iterator_tag());
735 _STLP_MOVE_TO_STD_NAMESPACE
737 template <class _ForwardIter
, class _Predicate
>
738 _ForwardIter
partition(_ForwardIter __first
, _ForwardIter __last
, _Predicate __pred
) {
739 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
740 return _STLP_PRIV
__partition(__first
, __last
, __pred
, _STLP_ITERATOR_CATEGORY(__first
, _ForwardIter
));
744 /* __pred_of_first: false if we know that __pred(*__first) is false,
745 * true when we don't know the result of __pred(*__first).
746 * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,
747 * false when we don't know the result of __pred(*--__last).
749 _STLP_MOVE_TO_PRIV_NAMESPACE
751 template <class _ForwardIter
, class _Predicate
, class _Distance
>
752 _ForwardIter
__inplace_stable_partition(_ForwardIter __first
,
754 _Predicate __pred
, _Distance __len
,
755 bool __pred_of_first
, bool __pred_of_before_last
) {
757 return (__pred_of_first
&& (__pred_of_before_last
|| __pred(*__first
))) ? __last
: __first
;
758 _ForwardIter __middle
= __first
;
759 _Distance __half_len
= __len
/ 2;
760 _STLP_STD::advance(__middle
, __half_len
);
761 return _STLP_PRIV
__rotate(_STLP_PRIV
__inplace_stable_partition(__first
, __middle
, __pred
, __half_len
, __pred_of_first
, false),
763 _STLP_PRIV
__inplace_stable_partition(__middle
, __last
, __pred
, __len
- __half_len
, true, __pred_of_before_last
));
766 template <class _ForwardIter
, class _Pointer
, class _Predicate
,
768 _ForwardIter
__stable_partition_adaptive(_ForwardIter __first
,
770 _Predicate __pred
, _Distance __len
,
771 _Pointer __buffer
, _Distance __buffer_size
,
772 bool __pred_of_first
, bool __pred_of_before_last
) {
773 if (__len
<= __buffer_size
) {
774 _ForwardIter __result1
= __first
;
775 _Pointer __result2
= __buffer
;
776 if ((__first
!= __last
) && (!__pred_of_first
|| __pred(*__first
))) {
777 *__result2
= *__first
;
778 ++__result2
; ++__first
; --__len
;
780 for (; __first
!= __last
; ++__first
, --__len
) {
781 if (((__len
== 1) && (__pred_of_before_last
|| __pred(*__first
))) ||
782 ((__len
!= 1) && __pred(*__first
))){
783 *__result1
= *__first
;
787 *__result2
= *__first
;
791 _STLP_STD::copy(__buffer
, __result2
, __result1
);
795 _ForwardIter __middle
= __first
;
796 _Distance __half_len
= __len
/ 2;
797 _STLP_STD::advance(__middle
, __half_len
);
798 return _STLP_PRIV
__rotate(_STLP_PRIV
__stable_partition_adaptive(__first
, __middle
, __pred
,
799 __half_len
, __buffer
, __buffer_size
,
800 __pred_of_first
, false),
802 _STLP_PRIV
__stable_partition_adaptive(__middle
, __last
, __pred
,
803 __len
- __half_len
, __buffer
, __buffer_size
,
804 true, __pred_of_before_last
));
808 template <class _ForwardIter
, class _Predicate
, class _Tp
, class _Distance
>
810 __stable_partition_aux_aux(_ForwardIter __first
, _ForwardIter __last
,
811 _Predicate __pred
, _Tp
*, _Distance
*, bool __pred_of_before_last
) {
812 _Temporary_buffer
<_ForwardIter
, _Tp
> __buf(__first
, __last
);
813 _STLP_MPWFIX_TRY
//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
814 return (__buf
.size() > 0) ?
815 __stable_partition_adaptive(__first
, __last
, __pred
,
816 _Distance(__buf
.requested_size()),
817 __buf
.begin(), __buf
.size(),
818 false, __pred_of_before_last
) :
819 __inplace_stable_partition(__first
, __last
, __pred
,
820 _Distance(__buf
.requested_size()),
821 false, __pred_of_before_last
);
822 _STLP_MPWFIX_CATCH
//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
825 template <class _ForwardIter
, class _Predicate
>
827 __stable_partition_aux(_ForwardIter __first
, _ForwardIter __last
, _Predicate __pred
,
828 const forward_iterator_tag
&) {
829 return __stable_partition_aux_aux(__first
, __last
, __pred
,
830 _STLP_VALUE_TYPE(__first
, _ForwardIter
),
831 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
), false);
834 template <class _BidirectIter
, class _Predicate
>
836 __stable_partition_aux(_BidirectIter __first
, _BidirectIter __last
, _Predicate __pred
,
837 const bidirectional_iterator_tag
&) {
839 if (__first
== __last
)
841 else if (!__pred(*__last
))
847 //Here we know that __pred(*--__last) is true
848 return __stable_partition_aux_aux(__first
, __last
, __pred
,
849 _STLP_VALUE_TYPE(__first
, _BidirectIter
),
850 _STLP_DISTANCE_TYPE(__first
, _BidirectIter
), true);
853 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
854 template <class _BidirectIter
, class _Predicate
>
856 __stable_partition_aux(_BidirectIter __first
, _BidirectIter __last
, _Predicate __pred
,
857 const random_access_iterator_tag
&) {
858 return __stable_partition_aux(__first
, __last
, __pred
, bidirectional_iterator_tag());
862 _STLP_MOVE_TO_STD_NAMESPACE
864 template <class _ForwardIter
, class _Predicate
>
866 stable_partition(_ForwardIter __first
, _ForwardIter __last
, _Predicate __pred
) {
867 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
869 if (__first
== __last
)
871 else if (__pred(*__first
))
876 return _STLP_PRIV
__stable_partition_aux(__first
, __last
, __pred
,
877 _STLP_ITERATOR_CATEGORY(__first
, _ForwardIter
));
880 _STLP_MOVE_TO_PRIV_NAMESPACE
882 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
883 _RandomAccessIter
__unguarded_partition(_RandomAccessIter __first
,
884 _RandomAccessIter __last
,
885 _Tp __pivot
, _Compare __comp
) {
887 while (__comp(*__first
, __pivot
)) {
888 _STLP_VERBOSE_ASSERT(!__comp(__pivot
, *__first
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
892 while (__comp(__pivot
, *__last
)) {
893 _STLP_VERBOSE_ASSERT(!__comp(*__last
, __pivot
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
896 if (!(__first
< __last
))
898 iter_swap(__first
, __last
);
903 // sort() and its auxiliary functions.
904 #define __stl_threshold 16
906 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
907 void __unguarded_linear_insert(_RandomAccessIter __last
, _Tp __val
,
909 _RandomAccessIter __next
= __last
;
911 while (__comp(__val
, *__next
)) {
912 _STLP_VERBOSE_ASSERT(!__comp(*__next
, __val
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
920 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
921 inline void __linear_insert(_RandomAccessIter __first
,
922 _RandomAccessIter __last
, _Tp __val
, _Compare __comp
) {
923 //*TY 12/26/1998 - added __val as a paramter
924 // _Tp __val = *__last; //*TY 12/26/1998 - __val supplied by caller
925 if (__comp(__val
, *__first
)) {
926 _STLP_VERBOSE_ASSERT(!__comp(*__first
, __val
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
927 copy_backward(__first
, __last
, __last
+ 1);
931 __unguarded_linear_insert(__last
, __val
, __comp
);
934 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
935 void __insertion_sort(_RandomAccessIter __first
,
936 _RandomAccessIter __last
,
937 _Tp
*, _Compare __comp
) {
938 if (__first
== __last
) return;
939 for (_RandomAccessIter __i
= __first
+ 1; __i
!= __last
; ++__i
)
940 __linear_insert
<_RandomAccessIter
, _Tp
, _Compare
>(__first
, __i
, *__i
, __comp
); //*TY 12/26/1998 - supply *__i as __val
943 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
944 void __unguarded_insertion_sort_aux(_RandomAccessIter __first
,
945 _RandomAccessIter __last
,
946 _Tp
*, _Compare __comp
) {
947 for (_RandomAccessIter __i
= __first
; __i
!= __last
; ++__i
)
948 __unguarded_linear_insert
<_RandomAccessIter
, _Tp
, _Compare
>(__i
, *__i
, __comp
);
951 template <class _RandomAccessIter
, class _Compare
>
952 inline void __unguarded_insertion_sort(_RandomAccessIter __first
,
953 _RandomAccessIter __last
,
955 __unguarded_insertion_sort_aux(__first
, __last
, _STLP_VALUE_TYPE(__first
, _RandomAccessIter
), __comp
);
958 template <class _RandomAccessIter
, class _Compare
>
959 void __final_insertion_sort(_RandomAccessIter __first
,
960 _RandomAccessIter __last
, _Compare __comp
) {
961 if (__last
- __first
> __stl_threshold
) {
962 __insertion_sort(__first
, __first
+ __stl_threshold
, _STLP_VALUE_TYPE(__first
,_RandomAccessIter
), __comp
);
963 __unguarded_insertion_sort(__first
+ __stl_threshold
, __last
, __comp
);
966 __insertion_sort(__first
, __last
, _STLP_VALUE_TYPE(__first
,_RandomAccessIter
), __comp
);
969 template <class _RandomAccessIter
, class _Tp
, class _Size
, class _Compare
>
970 void __introsort_loop(_RandomAccessIter __first
,
971 _RandomAccessIter __last
, _Tp
*,
972 _Size __depth_limit
, _Compare __comp
) {
973 while (__last
- __first
> __stl_threshold
) {
974 if (__depth_limit
== 0) {
975 partial_sort(__first
, __last
, __last
, __comp
);
979 _RandomAccessIter __cut
=
980 __unguarded_partition(__first
, __last
,
981 _Tp(__median(*__first
,
982 *(__first
+ (__last
- __first
)/2),
983 *(__last
- 1), __comp
)),
985 __introsort_loop(__cut
, __last
, (_Tp
*) 0, __depth_limit
, __comp
);
990 _STLP_MOVE_TO_STD_NAMESPACE
992 template <class _RandomAccessIter
>
993 void sort(_RandomAccessIter __first
, _RandomAccessIter __last
) {
994 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
995 if (__first
!= __last
) {
996 _STLP_PRIV
__introsort_loop(__first
, __last
,
997 _STLP_VALUE_TYPE(__first
, _RandomAccessIter
),
998 _STLP_PRIV
__lg(__last
- __first
) * 2,
999 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _RandomAccessIter
)));
1000 _STLP_PRIV
__final_insertion_sort(__first
, __last
,
1001 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _RandomAccessIter
)));
1005 template <class _RandomAccessIter
, class _Compare
>
1006 void sort(_RandomAccessIter __first
, _RandomAccessIter __last
, _Compare __comp
) {
1007 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1008 if (__first
!= __last
) {
1009 _STLP_PRIV
__introsort_loop(__first
, __last
,
1010 _STLP_VALUE_TYPE(__first
, _RandomAccessIter
),
1011 _STLP_PRIV
__lg(__last
- __first
) * 2, __comp
);
1012 _STLP_PRIV
__final_insertion_sort(__first
, __last
, __comp
);
1016 // stable_sort() and its auxiliary functions.
1017 _STLP_MOVE_TO_PRIV_NAMESPACE
1019 template <class _RandomAccessIter
, class _Compare
>
1020 void __inplace_stable_sort(_RandomAccessIter __first
,
1021 _RandomAccessIter __last
, _Compare __comp
) {
1022 if (__last
- __first
< 15) {
1023 __insertion_sort(__first
, __last
, _STLP_VALUE_TYPE(__first
,_RandomAccessIter
), __comp
);
1026 _RandomAccessIter __middle
= __first
+ (__last
- __first
) / 2;
1027 __inplace_stable_sort(__first
, __middle
, __comp
);
1028 __inplace_stable_sort(__middle
, __last
, __comp
);
1029 __merge_without_buffer(__first
, __middle
, __last
,
1035 template <class _RandomAccessIter1
, class _RandomAccessIter2
,
1036 class _Distance
, class _Compare
>
1037 void __merge_sort_loop(_RandomAccessIter1 __first
,
1038 _RandomAccessIter1 __last
,
1039 _RandomAccessIter2 __result
, _Distance __step_size
,
1041 _Distance __two_step
= 2 * __step_size
;
1043 while (__last
- __first
>= __two_step
) {
1044 __result
= merge(__first
, __first
+ __step_size
,
1045 __first
+ __step_size
, __first
+ __two_step
,
1048 __first
+= __two_step
;
1050 __step_size
= (min
) (_Distance(__last
- __first
), __step_size
);
1052 merge(__first
, __first
+ __step_size
,
1053 __first
+ __step_size
, __last
,
1058 const int __stl_chunk_size
= 7;
1060 template <class _RandomAccessIter
, class _Distance
, class _Compare
>
1061 void __chunk_insertion_sort(_RandomAccessIter __first
,
1062 _RandomAccessIter __last
,
1063 _Distance __chunk_size
, _Compare __comp
) {
1064 while (__last
- __first
>= __chunk_size
) {
1065 __insertion_sort(__first
, __first
+ __chunk_size
,
1066 _STLP_VALUE_TYPE(__first
,_RandomAccessIter
), __comp
);
1067 __first
+= __chunk_size
;
1069 __insertion_sort(__first
, __last
, _STLP_VALUE_TYPE(__first
,_RandomAccessIter
), __comp
);
1072 template <class _RandomAccessIter
, class _Pointer
, class _Distance
,
1074 void __merge_sort_with_buffer(_RandomAccessIter __first
,
1075 _RandomAccessIter __last
, _Pointer __buffer
,
1076 _Distance
*, _Compare __comp
) {
1077 _Distance __len
= __last
- __first
;
1078 _Pointer __buffer_last
= __buffer
+ __len
;
1080 _Distance __step_size
= __stl_chunk_size
;
1081 __chunk_insertion_sort(__first
, __last
, __step_size
, __comp
);
1083 while (__step_size
< __len
) {
1084 __merge_sort_loop(__first
, __last
, __buffer
, __step_size
, __comp
);
1086 __merge_sort_loop(__buffer
, __buffer_last
, __first
, __step_size
, __comp
);
1091 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
1093 _BidirectionalIter1
__rotate_adaptive(_BidirectionalIter1 __first
,
1094 _BidirectionalIter1 __middle
,
1095 _BidirectionalIter1 __last
,
1096 _Distance __len1
, _Distance __len2
,
1097 _BidirectionalIter2 __buffer
,
1098 _Distance __buffer_size
) {
1099 if (__len1
> __len2
&& __len2
<= __buffer_size
) {
1100 _BidirectionalIter2 __buffer_end
= _STLP_STD::copy(__middle
, __last
, __buffer
);
1101 _STLP_STD::copy_backward(__first
, __middle
, __last
);
1102 return _STLP_STD::copy(__buffer
, __buffer_end
, __first
);
1104 else if (__len1
<= __buffer_size
) {
1105 _BidirectionalIter2 __buffer_end
= _STLP_STD::copy(__first
, __middle
, __buffer
);
1106 _STLP_STD::copy(__middle
, __last
, __first
);
1107 return _STLP_STD::copy_backward(__buffer
, __buffer_end
, __last
);
1110 return _STLP_PRIV
__rotate(__first
, __middle
, __last
);
1113 template <class _BidirectionalIter
, class _Distance
, class _Pointer
,
1115 void __merge_adaptive(_BidirectionalIter __first
,
1116 _BidirectionalIter __middle
,
1117 _BidirectionalIter __last
,
1118 _Distance __len1
, _Distance __len2
,
1119 _Pointer __buffer
, _Distance __buffer_size
,
1121 if (__len1
<= __len2
&& __len1
<= __buffer_size
) {
1122 _Pointer __buffer_end
= _STLP_STD::copy(__first
, __middle
, __buffer
);
1123 _STLP_STD::merge(__buffer
, __buffer_end
, __middle
, __last
, __first
, __comp
);
1125 else if (__len2
<= __buffer_size
) {
1126 _Pointer __buffer_end
= _STLP_STD::copy(__middle
, __last
, __buffer
);
1127 _STLP_PRIV
__merge_backward(__first
, __middle
, __buffer
, __buffer_end
, __last
,
1131 _BidirectionalIter __first_cut
= __first
;
1132 _BidirectionalIter __second_cut
= __middle
;
1133 _Distance __len11
= 0;
1134 _Distance __len22
= 0;
1135 if (__len1
> __len2
) {
1136 __len11
= __len1
/ 2;
1137 _STLP_STD::advance(__first_cut
, __len11
);
1138 __second_cut
= _STLP_STD::lower_bound(__middle
, __last
, *__first_cut
, __comp
);
1139 __len22
+= _STLP_STD::distance(__middle
, __second_cut
);
1142 __len22
= __len2
/ 2;
1143 _STLP_STD::advance(__second_cut
, __len22
);
1144 __first_cut
= _STLP_STD::upper_bound(__first
, __middle
, *__second_cut
, __comp
);
1145 __len11
+= _STLP_STD::distance(__first
, __first_cut
);
1147 _BidirectionalIter __new_middle
=
1148 __rotate_adaptive(__first_cut
, __middle
, __second_cut
, __len1
- __len11
,
1149 __len22
, __buffer
, __buffer_size
);
1150 __merge_adaptive(__first
, __first_cut
, __new_middle
, __len11
,
1151 __len22
, __buffer
, __buffer_size
, __comp
);
1152 __merge_adaptive(__new_middle
, __second_cut
, __last
, __len1
- __len11
,
1153 __len2
- __len22
, __buffer
, __buffer_size
, __comp
);
1157 template <class _RandomAccessIter
, class _Pointer
, class _Distance
,
1159 void __stable_sort_adaptive(_RandomAccessIter __first
,
1160 _RandomAccessIter __last
, _Pointer __buffer
,
1161 _Distance __buffer_size
, _Compare __comp
) {
1162 _Distance __len
= (__last
- __first
+ 1) / 2;
1163 _RandomAccessIter __middle
= __first
+ __len
;
1164 if (__len
> __buffer_size
) {
1165 __stable_sort_adaptive(__first
, __middle
, __buffer
, __buffer_size
,
1167 __stable_sort_adaptive(__middle
, __last
, __buffer
, __buffer_size
,
1171 __merge_sort_with_buffer(__first
, __middle
, __buffer
, (_Distance
*)0,
1173 __merge_sort_with_buffer(__middle
, __last
, __buffer
, (_Distance
*)0,
1176 __merge_adaptive(__first
, __middle
, __last
, _Distance(__middle
- __first
),
1177 _Distance(__last
- __middle
), __buffer
, __buffer_size
,
1181 template <class _RandomAccessIter
, class _Tp
, class _Distance
, class _Compare
>
1182 void __stable_sort_aux(_RandomAccessIter __first
,
1183 _RandomAccessIter __last
, _Tp
*, _Distance
*,
1185 _Temporary_buffer
<_RandomAccessIter
, _Tp
> buf(__first
, __last
);
1186 if (buf
.begin() == 0)
1187 __inplace_stable_sort(__first
, __last
, __comp
);
1189 __stable_sort_adaptive(__first
, __last
, buf
.begin(),
1190 _Distance(buf
.size()),
1194 _STLP_MOVE_TO_STD_NAMESPACE
1196 template <class _RandomAccessIter
>
1197 void stable_sort(_RandomAccessIter __first
,
1198 _RandomAccessIter __last
) {
1199 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1200 _STLP_PRIV
__stable_sort_aux(__first
, __last
,
1201 _STLP_VALUE_TYPE(__first
, _RandomAccessIter
),
1202 _STLP_DISTANCE_TYPE(__first
, _RandomAccessIter
),
1203 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _RandomAccessIter
)));
1206 template <class _RandomAccessIter
, class _Compare
>
1207 void stable_sort(_RandomAccessIter __first
,
1208 _RandomAccessIter __last
, _Compare __comp
) {
1209 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1210 _STLP_PRIV
__stable_sort_aux(__first
, __last
,
1211 _STLP_VALUE_TYPE(__first
, _RandomAccessIter
),
1212 _STLP_DISTANCE_TYPE(__first
, _RandomAccessIter
),
1216 // partial_sort, partial_sort_copy, and auxiliary functions.
1217 _STLP_MOVE_TO_PRIV_NAMESPACE
1219 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1220 void __partial_sort(_RandomAccessIter __first
, _RandomAccessIter __middle
,
1221 _RandomAccessIter __last
, _Tp
*, _Compare __comp
) {
1222 make_heap(__first
, __middle
, __comp
);
1223 for (_RandomAccessIter __i
= __middle
; __i
< __last
; ++__i
) {
1224 if (__comp(*__i
, *__first
)) {
1225 _STLP_VERBOSE_ASSERT(!__comp(*__first
, *__i
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1226 __pop_heap(__first
, __middle
, __i
, _Tp(*__i
), __comp
,
1227 _STLP_DISTANCE_TYPE(__first
, _RandomAccessIter
));
1230 sort_heap(__first
, __middle
, __comp
);
1233 _STLP_MOVE_TO_STD_NAMESPACE
1235 template <class _RandomAccessIter
>
1236 void partial_sort(_RandomAccessIter __first
,_RandomAccessIter __middle
,
1237 _RandomAccessIter __last
) {
1238 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __middle
))
1239 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__middle
, __last
))
1240 _STLP_PRIV
__partial_sort(__first
, __middle
, __last
, _STLP_VALUE_TYPE(__first
, _RandomAccessIter
),
1241 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _RandomAccessIter
)));
1244 template <class _RandomAccessIter
, class _Compare
>
1245 void partial_sort(_RandomAccessIter __first
,_RandomAccessIter __middle
,
1246 _RandomAccessIter __last
, _Compare __comp
) {
1247 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __middle
))
1248 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__middle
, __last
))
1249 _STLP_PRIV
__partial_sort(__first
, __middle
, __last
, _STLP_VALUE_TYPE(__first
, _RandomAccessIter
), __comp
);
1252 _STLP_MOVE_TO_PRIV_NAMESPACE
1254 template <class _InputIter
, class _RandomAccessIter
, class _Compare
,
1255 class _Distance
, class _Tp
>
1256 _RandomAccessIter
__partial_sort_copy(_InputIter __first
,
1258 _RandomAccessIter __result_first
,
1259 _RandomAccessIter __result_last
,
1260 _Compare __comp
, _Distance
*, _Tp
*) {
1261 if (__result_first
== __result_last
) return __result_last
;
1262 _RandomAccessIter __result_real_last
= __result_first
;
1263 while(__first
!= __last
&& __result_real_last
!= __result_last
) {
1264 *__result_real_last
= *__first
;
1265 ++__result_real_last
;
1268 make_heap(__result_first
, __result_real_last
, __comp
);
1269 while (__first
!= __last
) {
1270 if (__comp(*__first
, *__result_first
)) {
1271 _STLP_VERBOSE_ASSERT(!__comp(*__result_first
, *__first
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1272 __adjust_heap(__result_first
, _Distance(0),
1273 _Distance(__result_real_last
- __result_first
),
1279 sort_heap(__result_first
, __result_real_last
, __comp
);
1280 return __result_real_last
;
1283 _STLP_MOVE_TO_STD_NAMESPACE
1285 template <class _InputIter
, class _RandomAccessIter
>
1287 partial_sort_copy(_InputIter __first
, _InputIter __last
,
1288 _RandomAccessIter __result_first
, _RandomAccessIter __result_last
) {
1289 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1290 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__result_first
, __result_last
))
1291 return _STLP_PRIV
__partial_sort_copy(__first
, __last
, __result_first
, __result_last
,
1292 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _InputIter
)),
1293 _STLP_DISTANCE_TYPE(__result_first
, _RandomAccessIter
),
1294 _STLP_VALUE_TYPE(__first
, _InputIter
));
1297 template <class _InputIter
, class _RandomAccessIter
, class _Compare
>
1299 partial_sort_copy(_InputIter __first
, _InputIter __last
,
1300 _RandomAccessIter __result_first
,
1301 _RandomAccessIter __result_last
, _Compare __comp
) {
1302 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1303 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__result_first
, __result_last
))
1304 return _STLP_PRIV
__partial_sort_copy(__first
, __last
, __result_first
, __result_last
,
1306 _STLP_DISTANCE_TYPE(__result_first
, _RandomAccessIter
),
1307 _STLP_VALUE_TYPE(__first
, _InputIter
));
1310 // nth_element() and its auxiliary functions.
1311 _STLP_MOVE_TO_PRIV_NAMESPACE
1313 template <class _RandomAccessIter
, class _Tp
, class _Compare
>
1314 void __nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
1315 _RandomAccessIter __last
, _Tp
*, _Compare __comp
) {
1316 while (__last
- __first
> 3) {
1317 _RandomAccessIter __cut
=
1318 __unguarded_partition(__first
, __last
,
1319 _Tp(__median(*__first
,
1320 *(__first
+ (__last
- __first
)/2),
1329 __insertion_sort(__first
, __last
, _STLP_VALUE_TYPE(__first
,_RandomAccessIter
), __comp
);
1332 _STLP_MOVE_TO_STD_NAMESPACE
1334 template <class _RandomAccessIter
>
1335 void nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
1336 _RandomAccessIter __last
) {
1337 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __nth
))
1338 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__nth
, __last
))
1339 _STLP_PRIV
__nth_element(__first
, __nth
, __last
, _STLP_VALUE_TYPE(__first
, _RandomAccessIter
),
1340 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _RandomAccessIter
)));
1343 template <class _RandomAccessIter
, class _Compare
>
1344 void nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
1345 _RandomAccessIter __last
, _Compare __comp
) {
1346 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __nth
))
1347 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__nth
, __last
))
1348 _STLP_PRIV
__nth_element(__first
, __nth
, __last
, _STLP_VALUE_TYPE(__first
, _RandomAccessIter
), __comp
);
1351 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
1352 _STLP_MOVE_TO_PRIV_NAMESPACE
1354 template <class _ForwardIter
, class _Tp
,
1355 class _Compare1
, class _Compare2
, class _Distance
>
1356 _ForwardIter
__upper_bound(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
1357 _Compare1 __comp1
, _Compare2 __comp2
, _Distance
*) {
1358 _Distance __len
= _STLP_STD::distance(__first
, __last
);
1362 __half
= __len
>> 1;
1363 _ForwardIter __middle
= __first
;
1364 _STLP_STD::advance(__middle
, __half
);
1365 if (__comp2(__val
, *__middle
)) {
1366 _STLP_VERBOSE_ASSERT(!__comp1(*__middle
, __val
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1372 __len
= __len
- __half
- 1;
1378 template <class _ForwardIter
, class _Tp
,
1379 class _Compare1
, class _Compare2
, class _Distance
>
1380 pair
<_ForwardIter
, _ForwardIter
>
1381 __equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
1382 _Compare1 __comp1
, _Compare2 __comp2
, _Distance
* __dist
) {
1383 _Distance __len
= _STLP_STD::distance(__first
, __last
);
1387 __half
= __len
>> 1;
1388 _ForwardIter __middle
= __first
;
1389 _STLP_STD::advance(__middle
, __half
);
1390 if (__comp1(*__middle
, __val
)) {
1391 _STLP_VERBOSE_ASSERT(!__comp2(__val
, *__middle
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1394 __len
= __len
- __half
- 1;
1396 else if (__comp2(__val
, *__middle
)) {
1397 _STLP_VERBOSE_ASSERT(!__comp1(*__middle
, __val
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1401 _ForwardIter __left
= _STLP_PRIV
__lower_bound(__first
, __middle
, __val
, __comp1
, __comp2
, __dist
);
1402 //Small optim: If lower_bound haven't found an equivalent value
1403 //there is no need to call upper_bound.
1404 if (__comp1(*__left
, __val
)) {
1405 _STLP_VERBOSE_ASSERT(!__comp2(__val
, *__left
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1406 return pair
<_ForwardIter
, _ForwardIter
>(__left
, __left
);
1408 _STLP_STD::advance(__first
, __len
);
1409 _ForwardIter __right
= _STLP_PRIV
__upper_bound(++__middle
, __first
, __val
, __comp1
, __comp2
, __dist
);
1410 return pair
<_ForwardIter
, _ForwardIter
>(__left
, __right
);
1413 return pair
<_ForwardIter
, _ForwardIter
>(__first
, __first
);
1416 _STLP_MOVE_TO_STD_NAMESPACE
1418 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
1419 _OutputIter
merge(_InputIter1 __first1
, _InputIter1 __last1
,
1420 _InputIter2 __first2
, _InputIter2 __last2
,
1421 _OutputIter __result
) {
1422 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
1423 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
1424 while (__first1
!= __last1
&& __first2
!= __last2
) {
1425 if (*__first2
< *__first1
) {
1426 *__result
= *__first2
;
1430 *__result
= *__first1
;
1435 return _STLP_STD::copy(__first2
, __last2
, _STLP_STD::copy(__first1
, __last1
, __result
));
1438 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1440 _OutputIter
merge(_InputIter1 __first1
, _InputIter1 __last1
,
1441 _InputIter2 __first2
, _InputIter2 __last2
,
1442 _OutputIter __result
, _Compare __comp
) {
1443 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
1444 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
1445 while (__first1
!= __last1
&& __first2
!= __last2
) {
1446 if (__comp(*__first2
, *__first1
)) {
1447 _STLP_VERBOSE_ASSERT(!__comp(*__first1
, *__first2
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1448 *__result
= *__first2
;
1452 *__result
= *__first1
;
1457 return _STLP_STD::copy(__first2
, __last2
, _STLP_STD::copy(__first1
, __last1
, __result
));
1460 _STLP_MOVE_TO_PRIV_NAMESPACE
1462 template <class _BidirectionalIter
, class _Distance
, class _Compare
>
1463 void __merge_without_buffer(_BidirectionalIter __first
,
1464 _BidirectionalIter __middle
,
1465 _BidirectionalIter __last
,
1466 _Distance __len1
, _Distance __len2
,
1468 if (__len1
== 0 || __len2
== 0)
1470 if (__len1
+ __len2
== 2) {
1471 if (__comp(*__middle
, *__first
)) {
1472 _STLP_VERBOSE_ASSERT(!__comp(*__first
, *__middle
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1473 iter_swap(__first
, __middle
);
1477 _BidirectionalIter __first_cut
= __first
;
1478 _BidirectionalIter __second_cut
= __middle
;
1479 _Distance __len11
= 0;
1480 _Distance __len22
= 0;
1481 if (__len1
> __len2
) {
1482 __len11
= __len1
/ 2;
1483 _STLP_STD::advance(__first_cut
, __len11
);
1484 __second_cut
= _STLP_STD::lower_bound(__middle
, __last
, *__first_cut
, __comp
);
1485 __len22
+= _STLP_STD::distance(__middle
, __second_cut
);
1488 __len22
= __len2
/ 2;
1489 _STLP_STD::advance(__second_cut
, __len22
);
1490 __first_cut
= _STLP_STD::upper_bound(__first
, __middle
, *__second_cut
, __comp
);
1491 __len11
+= _STLP_STD::distance(__first
, __first_cut
);
1493 _BidirectionalIter __new_middle
1494 = _STLP_PRIV
__rotate(__first_cut
, __middle
, __second_cut
);
1495 __merge_without_buffer(__first
, __first_cut
, __new_middle
, __len11
, __len22
,
1497 __merge_without_buffer(__new_middle
, __second_cut
, __last
, __len1
- __len11
,
1498 __len2
- __len22
, __comp
);
1501 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
1502 class _BidirectionalIter3
, class _Compare
>
1503 _BidirectionalIter3
__merge_backward(_BidirectionalIter1 __first1
,
1504 _BidirectionalIter1 __last1
,
1505 _BidirectionalIter2 __first2
,
1506 _BidirectionalIter2 __last2
,
1507 _BidirectionalIter3 __result
,
1509 if (__first1
== __last1
)
1510 return copy_backward(__first2
, __last2
, __result
);
1511 if (__first2
== __last2
)
1512 return copy_backward(__first1
, __last1
, __result
);
1516 if (__comp(*__last2
, *__last1
)) {
1517 _STLP_VERBOSE_ASSERT(!__comp(*__last1
, *__last2
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1518 *--__result
= *__last1
;
1519 if (__first1
== __last1
)
1520 return copy_backward(__first2
, ++__last2
, __result
);
1524 *--__result
= *__last2
;
1525 if (__first2
== __last2
)
1526 return copy_backward(__first1
, ++__last1
, __result
);
1532 template <class _BidirectionalIter
, class _Tp
,
1533 class _Distance
, class _Compare
>
1534 inline void __inplace_merge_aux(_BidirectionalIter __first
,
1535 _BidirectionalIter __middle
,
1536 _BidirectionalIter __last
, _Tp
*, _Distance
*,
1538 _Distance __len1
= _STLP_STD::distance(__first
, __middle
);
1539 _Distance __len2
= _STLP_STD::distance(__middle
, __last
);
1541 _Temporary_buffer
<_BidirectionalIter
, _Tp
> __buf(__first
, __last
);
1542 if (__buf
.begin() == 0)
1543 __merge_without_buffer(__first
, __middle
, __last
, __len1
, __len2
, __comp
);
1545 __merge_adaptive(__first
, __middle
, __last
, __len1
, __len2
,
1546 __buf
.begin(), _Distance(__buf
.size()),
1550 _STLP_MOVE_TO_STD_NAMESPACE
1552 template <class _BidirectionalIter
>
1553 void inplace_merge(_BidirectionalIter __first
,
1554 _BidirectionalIter __middle
,
1555 _BidirectionalIter __last
) {
1556 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __middle
))
1557 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__middle
, __last
))
1558 if (__first
== __middle
|| __middle
== __last
)
1560 _STLP_PRIV
__inplace_merge_aux(__first
, __middle
, __last
,
1561 _STLP_VALUE_TYPE(__first
, _BidirectionalIter
), _STLP_DISTANCE_TYPE(__first
, _BidirectionalIter
),
1562 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _BidirectionalIter
)));
1565 template <class _BidirectionalIter
, class _Compare
>
1566 void inplace_merge(_BidirectionalIter __first
,
1567 _BidirectionalIter __middle
,
1568 _BidirectionalIter __last
, _Compare __comp
) {
1569 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __middle
))
1570 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__middle
, __last
))
1571 if (__first
== __middle
|| __middle
== __last
)
1573 _STLP_PRIV
__inplace_merge_aux(__first
, __middle
, __last
,
1574 _STLP_VALUE_TYPE(__first
, _BidirectionalIter
), _STLP_DISTANCE_TYPE(__first
, _BidirectionalIter
),
1578 _STLP_MOVE_TO_PRIV_NAMESPACE
1580 template <class _InputIter1
, class _InputIter2
, class _Compare
>
1581 bool __includes(_InputIter1 __first1
, _InputIter1 __last1
,
1582 _InputIter2 __first2
, _InputIter2 __last2
, _Compare __comp
) {
1583 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
1584 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
1585 while (__first1
!= __last1
&& __first2
!= __last2
)
1586 if (__comp(*__first2
, *__first1
)) {
1587 _STLP_VERBOSE_ASSERT(!__comp(*__first1
, *__first2
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1590 else if (__comp(*__first1
, *__first2
))
1593 ++__first1
, ++__first2
;
1595 return __first2
== __last2
;
1598 _STLP_MOVE_TO_STD_NAMESPACE
1600 template <class _InputIter1
, class _InputIter2
, class _Compare
>
1601 bool includes(_InputIter1 __first1
, _InputIter1 __last1
,
1602 _InputIter2 __first2
, _InputIter2 __last2
, _Compare __comp
) {
1603 return _STLP_PRIV
__includes(__first1
, __last1
, __first2
, __last2
, __comp
);
1606 template <class _InputIter1
, class _InputIter2
>
1607 bool includes(_InputIter1 __first1
, _InputIter1 __last1
,
1608 _InputIter2 __first2
, _InputIter2 __last2
) {
1609 return _STLP_PRIV
__includes(__first1
, __last1
, __first2
, __last2
,
1610 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first1
, _InputIter1
)));
1613 _STLP_MOVE_TO_PRIV_NAMESPACE
1615 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1617 _OutputIter
__set_union(_InputIter1 __first1
, _InputIter1 __last1
,
1618 _InputIter2 __first2
, _InputIter2 __last2
,
1619 _OutputIter __result
, _Compare __comp
) {
1620 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
1621 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
1622 while (__first1
!= __last1
&& __first2
!= __last2
) {
1623 if (__comp(*__first1
, *__first2
)) {
1624 _STLP_VERBOSE_ASSERT(!__comp(*__first2
, *__first1
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1625 *__result
= *__first1
;
1628 else if (__comp(*__first2
, *__first1
)) {
1629 _STLP_VERBOSE_ASSERT(!__comp(*__first1
, *__first2
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1630 *__result
= *__first2
;
1634 *__result
= *__first1
;
1640 return _STLP_STD::copy(__first2
, __last2
, _STLP_STD::copy(__first1
, __last1
, __result
));
1643 _STLP_MOVE_TO_STD_NAMESPACE
1645 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
1646 _OutputIter
set_union(_InputIter1 __first1
, _InputIter1 __last1
,
1647 _InputIter2 __first2
, _InputIter2 __last2
,
1648 _OutputIter __result
) {
1649 return _STLP_PRIV
__set_union(__first1
, __last1
, __first2
, __last2
, __result
,
1650 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first1
, _InputIter1
)));
1653 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1655 _OutputIter
set_union(_InputIter1 __first1
, _InputIter1 __last1
,
1656 _InputIter2 __first2
, _InputIter2 __last2
,
1657 _OutputIter __result
, _Compare __comp
) {
1658 return _STLP_PRIV
__set_union(__first1
, __last1
, __first2
, __last2
, __result
, __comp
);
1661 _STLP_MOVE_TO_PRIV_NAMESPACE
1663 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1665 _OutputIter
__set_intersection(_InputIter1 __first1
, _InputIter1 __last1
,
1666 _InputIter2 __first2
, _InputIter2 __last2
,
1667 _OutputIter __result
, _Compare __comp
) {
1668 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
1669 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
1670 while (__first1
!= __last1
&& __first2
!= __last2
)
1671 if (__comp(*__first1
, *__first2
)) {
1672 _STLP_VERBOSE_ASSERT(!__comp(*__first2
, *__first1
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1675 else if (__comp(*__first2
, *__first1
))
1678 *__result
= *__first1
;
1686 _STLP_MOVE_TO_STD_NAMESPACE
1688 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
1689 _OutputIter
set_intersection(_InputIter1 __first1
, _InputIter1 __last1
,
1690 _InputIter2 __first2
, _InputIter2 __last2
,
1691 _OutputIter __result
) {
1692 return _STLP_PRIV
__set_intersection(__first1
, __last1
, __first2
, __last2
, __result
,
1693 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first1
, _InputIter1
)));
1696 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1698 _OutputIter
set_intersection(_InputIter1 __first1
, _InputIter1 __last1
,
1699 _InputIter2 __first2
, _InputIter2 __last2
,
1700 _OutputIter __result
, _Compare __comp
) {
1701 return _STLP_PRIV
__set_intersection(__first1
, __last1
, __first2
, __last2
, __result
, __comp
);
1704 _STLP_MOVE_TO_PRIV_NAMESPACE
1706 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1708 _OutputIter
__set_difference(_InputIter1 __first1
, _InputIter1 __last1
,
1709 _InputIter2 __first2
, _InputIter2 __last2
,
1710 _OutputIter __result
, _Compare __comp
) {
1711 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
1712 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
1713 while (__first1
!= __last1
&& __first2
!= __last2
)
1714 if (__comp(*__first1
, *__first2
)) {
1715 _STLP_VERBOSE_ASSERT(!__comp(*__first2
, *__first1
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1716 *__result
= *__first1
;
1720 else if (__comp(*__first2
, *__first1
))
1726 return _STLP_STD::copy(__first1
, __last1
, __result
);
1729 _STLP_MOVE_TO_STD_NAMESPACE
1731 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
1732 _OutputIter
set_difference(_InputIter1 __first1
, _InputIter1 __last1
,
1733 _InputIter2 __first2
, _InputIter2 __last2
,
1734 _OutputIter __result
) {
1735 return _STLP_PRIV
__set_difference(__first1
, __last1
, __first2
, __last2
, __result
,
1736 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first1
, _InputIter1
)));
1739 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
1741 _OutputIter
set_difference(_InputIter1 __first1
, _InputIter1 __last1
,
1742 _InputIter2 __first2
, _InputIter2 __last2
,
1743 _OutputIter __result
, _Compare __comp
) {
1744 return _STLP_PRIV
__set_difference(__first1
, __last1
, __first2
, __last2
, __result
, __comp
);
1747 _STLP_MOVE_TO_PRIV_NAMESPACE
1749 template <class _InputIter1
, class _InputIter2
, class _OutputIter
, class _Compare
>
1751 __set_symmetric_difference(_InputIter1 __first1
, _InputIter1 __last1
,
1752 _InputIter2 __first2
, _InputIter2 __last2
,
1753 _OutputIter __result
, _Compare __comp
) {
1754 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
1755 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
1756 while (__first1
!= __last1
&& __first2
!= __last2
) {
1757 if (__comp(*__first1
, *__first2
)) {
1758 _STLP_VERBOSE_ASSERT(!__comp(*__first2
, *__first1
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1759 *__result
= *__first1
;
1763 else if (__comp(*__first2
, *__first1
)) {
1764 *__result
= *__first2
;
1773 return _STLP_STD::copy(__first2
, __last2
, _STLP_STD::copy(__first1
, __last1
, __result
));
1776 _STLP_MOVE_TO_STD_NAMESPACE
1778 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
1780 set_symmetric_difference(_InputIter1 __first1
, _InputIter1 __last1
,
1781 _InputIter2 __first2
, _InputIter2 __last2
,
1782 _OutputIter __result
) {
1783 return _STLP_PRIV
__set_symmetric_difference(__first1
, __last1
, __first2
, __last2
, __result
,
1784 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first1
, _InputIter1
)));
1787 template <class _InputIter1
, class _InputIter2
, class _OutputIter
, class _Compare
>
1789 set_symmetric_difference(_InputIter1 __first1
, _InputIter1 __last1
,
1790 _InputIter2 __first2
, _InputIter2 __last2
,
1791 _OutputIter __result
,
1793 return _STLP_PRIV
__set_symmetric_difference(__first1
, __last1
, __first2
, __last2
, __result
, __comp
);
1796 // min_element and max_element, with and without an explicitly supplied
1797 // comparison function.
1799 template <class _ForwardIter
>
1800 _ForwardIter
max_element(_ForwardIter __first
, _ForwardIter __last
) {
1801 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1802 if (__first
== __last
) return __first
;
1803 _ForwardIter __result
= __first
;
1804 while (++__first
!= __last
)
1805 if (*__result
< *__first
) {
1806 _STLP_VERBOSE_ASSERT(!(*__first
< *__result
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1812 template <class _ForwardIter
, class _Compare
>
1813 _ForwardIter
max_element(_ForwardIter __first
, _ForwardIter __last
,
1815 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1816 if (__first
== __last
) return __first
;
1817 _ForwardIter __result
= __first
;
1818 while (++__first
!= __last
) {
1819 if (__comp(*__result
, *__first
)) {
1820 _STLP_VERBOSE_ASSERT(!__comp(*__first
, *__result
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1827 template <class _ForwardIter
>
1828 _ForwardIter
min_element(_ForwardIter __first
, _ForwardIter __last
) {
1829 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1830 if (__first
== __last
) return __first
;
1831 _ForwardIter __result
= __first
;
1832 while (++__first
!= __last
)
1833 if (*__first
< *__result
) {
1834 _STLP_VERBOSE_ASSERT(!(*__result
< *__first
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1840 template <class _ForwardIter
, class _Compare
>
1841 _ForwardIter
min_element(_ForwardIter __first
, _ForwardIter __last
,
1843 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1844 if (__first
== __last
) return __first
;
1845 _ForwardIter __result
= __first
;
1846 while (++__first
!= __last
) {
1847 if (__comp(*__first
, *__result
)) {
1848 _STLP_VERBOSE_ASSERT(!__comp(*__result
, *__first
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1855 // next_permutation and prev_permutation, with and without an explicitly
1856 // supplied comparison function.
1857 _STLP_MOVE_TO_PRIV_NAMESPACE
1859 template <class _BidirectionalIter
, class _Compare
>
1860 bool __next_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
1862 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1863 if (__first
== __last
)
1865 _BidirectionalIter __i
= __first
;
1873 _BidirectionalIter __ii
= __i
;
1875 if (__comp(*__i
, *__ii
)) {
1876 _STLP_VERBOSE_ASSERT(!__comp(*__ii
, *__i
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1877 _BidirectionalIter __j
= __last
;
1878 while (!__comp(*__i
, *--__j
)) {}
1879 iter_swap(__i
, __j
);
1880 reverse(__ii
, __last
);
1883 if (__i
== __first
) {
1884 reverse(__first
, __last
);
1888 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
1893 _STLP_MOVE_TO_STD_NAMESPACE
1895 template <class _BidirectionalIter
>
1896 bool next_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
) {
1897 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1898 return _STLP_PRIV
__next_permutation(__first
, __last
,
1899 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _BidirectionalIter
)));
1902 template <class _BidirectionalIter
, class _Compare
>
1903 bool next_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
1905 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1906 return _STLP_PRIV
__next_permutation(__first
, __last
, __comp
);
1909 _STLP_MOVE_TO_PRIV_NAMESPACE
1911 template <class _BidirectionalIter
, class _Compare
>
1912 bool __prev_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
1914 if (__first
== __last
)
1916 _BidirectionalIter __i
= __first
;
1924 _BidirectionalIter __ii
= __i
;
1926 if (__comp(*__ii
, *__i
)) {
1927 _STLP_VERBOSE_ASSERT(!__comp(*__i
, *__ii
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1928 _BidirectionalIter __j
= __last
;
1929 while (!__comp(*--__j
, *__i
)) {}
1930 iter_swap(__i
, __j
);
1931 reverse(__ii
, __last
);
1934 if (__i
== __first
) {
1935 reverse(__first
, __last
);
1939 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
1944 _STLP_MOVE_TO_STD_NAMESPACE
1946 template <class _BidirectionalIter
>
1947 bool prev_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
) {
1948 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1949 return _STLP_PRIV
__prev_permutation(__first
, __last
,
1950 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _BidirectionalIter
)));
1953 template <class _BidirectionalIter
, class _Compare
>
1954 bool prev_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
1956 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1957 return _STLP_PRIV
__prev_permutation(__first
, __last
, __comp
);
1960 #if !defined (_STLP_NO_EXTENSIONS)
1962 // is_heap, a predicate testing whether or not a range is
1963 // a heap. This function is an extension, not part of the C++
1965 _STLP_MOVE_TO_PRIV_NAMESPACE
1967 template <class _RandomAccessIter
, class _Distance
, class _StrictWeakOrdering
>
1968 bool __is_heap(_RandomAccessIter __first
, _StrictWeakOrdering __comp
,
1970 _Distance __parent
= 0;
1971 for (_Distance __child
= 1; __child
< __n
; ++__child
) {
1972 if (__comp(__first
[__parent
], __first
[__child
])) {
1973 _STLP_VERBOSE_ASSERT(!__comp(__first
[__child
], __first
[__parent
]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
1976 if ((__child
& 1) == 0)
1982 _STLP_MOVE_TO_STD_NAMESPACE
1984 template <class _RandomAccessIter
>
1985 bool is_heap(_RandomAccessIter __first
, _RandomAccessIter __last
) {
1986 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1987 return _STLP_PRIV
__is_heap(__first
, _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _RandomAccessIter
)), __last
- __first
);
1990 template <class _RandomAccessIter
, class _StrictWeakOrdering
>
1991 bool is_heap(_RandomAccessIter __first
, _RandomAccessIter __last
,
1992 _StrictWeakOrdering __comp
) {
1993 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
1994 return _STLP_PRIV
__is_heap(__first
, __comp
, __last
- __first
);
1998 _STLP_MOVE_TO_PRIV_NAMESPACE
2000 template <class _ForwardIter
, class _StrictWeakOrdering
>
2001 bool __is_sorted(_ForwardIter __first
, _ForwardIter __last
,
2002 _StrictWeakOrdering __comp
) {
2003 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
2004 if (__first
== __last
)
2007 _ForwardIter __next
= __first
;
2008 for (++__next
; __next
!= __last
; __first
= __next
, ++__next
) {
2009 if (__comp(*__next
, *__first
)) {
2010 _STLP_VERBOSE_ASSERT(!__comp(*__first
, *__next
), _StlMsg_INVALID_STRICT_WEAK_PREDICATE
)
2018 _STLP_MOVE_TO_STD_NAMESPACE
2019 #endif /* _STLP_NO_EXTENSIONS */
2023 #undef __stl_threshold
2025 #endif /* _STLP_ALGO_C */