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.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_ALGO_H
31 #define _STLP_INTERNAL_ALGO_H
33 #ifndef _STLP_INTERNAL_ALGOBASE_H
34 # include <stl/_algobase.h>
37 #ifndef _STLP_INTERNAL_HEAP_H
38 # include <stl/_heap.h>
41 #ifndef _STLP_INTERNAL_ITERATOR_H
42 # include <stl/_iterator.h>
45 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
46 # include <stl/_function_base.h>
49 #if defined (__SUNPRO_CC) && !defined (_STLP_INTERNAL_CSTDIO)
51 # include <stl/_cstdio.h>
56 // for_each. Apply a function to every element of a range.
57 template <class _InputIter
, class _Function
>
58 _STLP_INLINE_LOOP _Function
59 for_each(_InputIter __first
, _InputIter __last
, _Function __f
) {
60 for ( ; __first
!= __last
; ++__first
)
66 template <class _InputIter
, class _Predicate
>
67 _STLP_INLINE_LOOP
_STLP_DIFFERENCE_TYPE(_InputIter
)
68 count_if(_InputIter __first
, _InputIter __last
, _Predicate __pred
) {
69 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
70 _STLP_DIFFERENCE_TYPE(_InputIter
) __n
= 0;
71 for ( ; __first
!= __last
; ++__first
) {
80 template <class _ForwardIter
, class _BinaryPredicate
>
81 _STLP_INLINE_LOOP _ForwardIter
82 adjacent_find(_ForwardIter __first
, _ForwardIter __last
,
83 _BinaryPredicate __binary_pred
) {
84 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
85 if (__first
== __last
)
87 _ForwardIter __next
= __first
;
88 while(++__next
!= __last
) {
89 if (__binary_pred(*__first
, *__next
))
96 template <class _ForwardIter
>
97 _STLP_INLINE_LOOP _ForwardIter
98 adjacent_find(_ForwardIter __first
, _ForwardIter __last
) {
99 return adjacent_find(__first
, __last
,
100 _STLP_PRIV
__equal_to(_STLP_VALUE_TYPE(__first
, _ForwardIter
)));
103 #if !defined (_STLP_NO_ANACHRONISMS)
104 template <class _InputIter
, class _Tp
, class _Size
>
105 _STLP_INLINE_LOOP
void
106 count(_InputIter __first
, _InputIter __last
, const _Tp
& __val
, _Size
& __n
) {
107 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
108 for ( ; __first
!= __last
; ++__first
)
109 if (*__first
== __val
)
113 template <class _InputIter
, class _Predicate
, class _Size
>
114 _STLP_INLINE_LOOP
void
115 count_if(_InputIter __first
, _InputIter __last
, _Predicate __pred
, _Size
& __n
) {
116 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
117 for ( ; __first
!= __last
; ++__first
)
118 if (__pred(*__first
))
123 template <class _ForwardIter1
, class _ForwardIter2
>
124 _ForwardIter1
search(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
125 _ForwardIter2 __first2
, _ForwardIter2 __last2
);
127 // search_n. Search for __count consecutive copies of __val.
128 template <class _ForwardIter
, class _Integer
, class _Tp
>
129 _ForwardIter
search_n(_ForwardIter __first
, _ForwardIter __last
,
130 _Integer __count
, const _Tp
& __val
);
131 template <class _ForwardIter
, class _Integer
, class _Tp
, class _BinaryPred
>
132 _ForwardIter
search_n(_ForwardIter __first
, _ForwardIter __last
,
133 _Integer __count
, const _Tp
& __val
, _BinaryPred __binary_pred
);
135 template <class _InputIter
, class _ForwardIter
>
136 inline _InputIter
find_first_of(_InputIter __first1
, _InputIter __last1
,
137 _ForwardIter __first2
, _ForwardIter __last2
) {
138 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
139 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
140 return _STLP_PRIV
__find_first_of(__first1
, __last1
, __first2
, __last2
);
143 template <class _InputIter
, class _ForwardIter
, class _BinaryPredicate
>
145 find_first_of(_InputIter __first1
, _InputIter __last1
,
146 _ForwardIter __first2
, _ForwardIter __last2
, _BinaryPredicate __comp
) {
147 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
148 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first2
, __last2
))
149 return _STLP_PRIV
__find_first_of(__first1
, __last1
, __first2
, __last2
, __comp
);
152 template <class _ForwardIter1
, class _ForwardIter2
>
154 find_end(_ForwardIter1 __first1
, _ForwardIter1 __last1
,
155 _ForwardIter2 __first2
, _ForwardIter2 __last2
);
158 template <class _ForwardIter1
, class _ForwardIter2
>
159 _STLP_INLINE_LOOP _ForwardIter2
160 swap_ranges(_ForwardIter1 __first1
, _ForwardIter1 __last1
, _ForwardIter2 __first2
) {
161 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
162 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
163 iter_swap(__first1
, __first2
);
168 template <class _InputIter
, class _OutputIter
, class _UnaryOperation
>
169 _STLP_INLINE_LOOP _OutputIter
170 transform(_InputIter __first
, _InputIter __last
, _OutputIter __result
, _UnaryOperation __opr
) {
171 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
172 for ( ; __first
!= __last
; ++__first
, ++__result
)
173 *__result
= __opr(*__first
);
176 template <class _InputIter1
, class _InputIter2
, class _OutputIter
, class _BinaryOperation
>
177 _STLP_INLINE_LOOP _OutputIter
178 transform(_InputIter1 __first1
, _InputIter1 __last1
,
179 _InputIter2 __first2
, _OutputIter __result
,_BinaryOperation __binary_op
) {
180 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first1
, __last1
))
181 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
, ++__result
)
182 *__result
= __binary_op(*__first1
, *__first2
);
186 // replace_if, replace_copy, replace_copy_if
188 template <class _ForwardIter
, class _Predicate
, class _Tp
>
189 _STLP_INLINE_LOOP
void
190 replace_if(_ForwardIter __first
, _ForwardIter __last
, _Predicate __pred
, const _Tp
& __new_value
) {
191 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
192 for ( ; __first
!= __last
; ++__first
)
193 if (__pred(*__first
))
194 *__first
= __new_value
;
197 template <class _InputIter
, class _OutputIter
, class _Tp
>
198 _STLP_INLINE_LOOP _OutputIter
199 replace_copy(_InputIter __first
, _InputIter __last
,_OutputIter __result
,
200 const _Tp
& __old_value
, const _Tp
& __new_value
) {
201 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
202 for ( ; __first
!= __last
; ++__first
, ++__result
)
203 *__result
= *__first
== __old_value
? __new_value
: *__first
;
207 template <class _Iterator
, class _OutputIter
, class _Predicate
, class _Tp
>
208 _STLP_INLINE_LOOP _OutputIter
209 replace_copy_if(_Iterator __first
, _Iterator __last
,
210 _OutputIter __result
,
211 _Predicate __pred
, const _Tp
& __new_value
) {
212 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
213 for ( ; __first
!= __last
; ++__first
, ++__result
)
214 *__result
= __pred(*__first
) ? __new_value
: *__first
;
218 // generate and generate_n
220 template <class _ForwardIter
, class _Generator
>
221 _STLP_INLINE_LOOP
void
222 generate(_ForwardIter __first
, _ForwardIter __last
, _Generator __gen
) {
223 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
224 for ( ; __first
!= __last
; ++__first
)
228 template <class _OutputIter
, class _Size
, class _Generator
>
229 _STLP_INLINE_LOOP
void
230 generate_n(_OutputIter __first
, _Size __n
, _Generator __gen
) {
231 for ( ; __n
> 0; --__n
, ++__first
)
235 // remove, remove_if, remove_copy, remove_copy_if
237 template <class _InputIter
, class _OutputIter
, class _Tp
>
238 _STLP_INLINE_LOOP _OutputIter
239 remove_copy(_InputIter __first
, _InputIter __last
,_OutputIter __result
, const _Tp
& __val
) {
240 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
241 for ( ; __first
!= __last
; ++__first
) {
242 if (!(*__first
== __val
)) {
243 *__result
= *__first
;
250 template <class _InputIter
, class _OutputIter
, class _Predicate
>
251 _STLP_INLINE_LOOP _OutputIter
252 remove_copy_if(_InputIter __first
, _InputIter __last
, _OutputIter __result
, _Predicate __pred
) {
253 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
254 for ( ; __first
!= __last
; ++__first
) {
255 if (!__pred(*__first
)) {
256 *__result
= *__first
;
263 template <class _ForwardIter
, class _Tp
>
264 _STLP_INLINE_LOOP _ForwardIter
265 remove(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
) {
266 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
267 __first
= find(__first
, __last
, __val
);
268 if (__first
== __last
)
271 _ForwardIter __next
= __first
;
272 return remove_copy(++__next
, __last
, __first
, __val
);
276 template <class _ForwardIter
, class _Predicate
>
277 _STLP_INLINE_LOOP _ForwardIter
278 remove_if(_ForwardIter __first
, _ForwardIter __last
, _Predicate __pred
) {
279 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
280 __first
= find_if(__first
, __last
, __pred
);
281 if ( __first
== __last
)
284 _ForwardIter __next
= __first
;
285 return remove_copy_if(++__next
, __last
, __first
, __pred
);
289 // unique and unique_copy
290 template <class _InputIter
, class _OutputIter
>
291 _OutputIter
unique_copy(_InputIter __first
, _InputIter __last
, _OutputIter __result
);
293 template <class _InputIter
, class _OutputIter
, class _BinaryPredicate
>
294 _OutputIter
unique_copy(_InputIter __first
, _InputIter __last
,_OutputIter __result
,
295 _BinaryPredicate __binary_pred
);
297 template <class _ForwardIter
>
298 inline _ForwardIter
unique(_ForwardIter __first
, _ForwardIter __last
) {
299 __first
= adjacent_find(__first
, __last
);
300 return unique_copy(__first
, __last
, __first
);
303 template <class _ForwardIter
, class _BinaryPredicate
>
304 inline _ForwardIter
unique(_ForwardIter __first
, _ForwardIter __last
,
305 _BinaryPredicate __binary_pred
) {
306 __first
= adjacent_find(__first
, __last
, __binary_pred
);
307 return unique_copy(__first
, __last
, __first
, __binary_pred
);
310 // reverse and reverse_copy, and their auxiliary functions
312 _STLP_MOVE_TO_PRIV_NAMESPACE
314 template <class _BidirectionalIter
>
315 _STLP_INLINE_LOOP
void
316 __reverse(_BidirectionalIter __first
, _BidirectionalIter __last
, const bidirectional_iterator_tag
&) {
317 for (; __first
!= __last
&& __first
!= --__last
; ++__first
)
318 _STLP_STD::iter_swap(__first
,__last
);
321 template <class _RandomAccessIter
>
322 _STLP_INLINE_LOOP
void
323 __reverse(_RandomAccessIter __first
, _RandomAccessIter __last
, const random_access_iterator_tag
&) {
324 for (; __first
< __last
; ++__first
)
325 _STLP_STD::iter_swap(__first
, --__last
);
328 _STLP_MOVE_TO_STD_NAMESPACE
330 template <class _BidirectionalIter
>
332 reverse(_BidirectionalIter __first
, _BidirectionalIter __last
) {
333 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
334 _STLP_PRIV
__reverse(__first
, __last
, _STLP_ITERATOR_CATEGORY(__first
, _BidirectionalIter
));
337 template <class _BidirectionalIter
, class _OutputIter
>
339 _OutputIter
reverse_copy(_BidirectionalIter __first
,
340 _BidirectionalIter __last
,
341 _OutputIter __result
) {
342 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
343 while (__first
!= __last
) {
351 template <class _ForwardIter
>
352 void rotate(_ForwardIter __first
, _ForwardIter __middle
, _ForwardIter __last
);
354 template <class _ForwardIter
, class _OutputIter
>
355 inline _OutputIter
rotate_copy(_ForwardIter __first
, _ForwardIter __middle
,
356 _ForwardIter __last
, _OutputIter __result
) {
357 return _STLP_STD::copy(__first
, __middle
, copy(__middle
, __last
, __result
));
362 template <class _RandomAccessIter
>
363 void random_shuffle(_RandomAccessIter __first
, _RandomAccessIter __last
);
365 template <class _RandomAccessIter
, class _RandomNumberGenerator
>
366 void random_shuffle(_RandomAccessIter __first
, _RandomAccessIter __last
,
367 _RandomNumberGenerator
& __rand
);
369 #if !defined (_STLP_NO_EXTENSIONS)
370 // random_sample and random_sample_n (extensions, not part of the standard).
372 template <class _ForwardIter
, class _OutputIter
, class _Distance
>
373 _OutputIter
random_sample_n(_ForwardIter __first
, _ForwardIter __last
,
374 _OutputIter __out_ite
, const _Distance __n
);
376 template <class _ForwardIter
, class _OutputIter
, class _Distance
,
377 class _RandomNumberGenerator
>
378 _OutputIter
random_sample_n(_ForwardIter __first
, _ForwardIter __last
,
379 _OutputIter __out_ite
, const _Distance __n
,
380 _RandomNumberGenerator
& __rand
);
382 template <class _InputIter
, class _RandomAccessIter
>
384 random_sample(_InputIter __first
, _InputIter __last
,
385 _RandomAccessIter __out_first
, _RandomAccessIter __out_last
);
387 template <class _InputIter
, class _RandomAccessIter
,
388 class _RandomNumberGenerator
>
390 random_sample(_InputIter __first
, _InputIter __last
,
391 _RandomAccessIter __out_first
, _RandomAccessIter __out_last
,
392 _RandomNumberGenerator
& __rand
);
394 #endif /* _STLP_NO_EXTENSIONS */
396 // partition, stable_partition, and their auxiliary functions
398 template <class _ForwardIter
, class _Predicate
>
399 _ForwardIter
partition(_ForwardIter __first
, _ForwardIter __last
, _Predicate __pred
);
401 template <class _ForwardIter
, class _Predicate
>
403 stable_partition(_ForwardIter __first
, _ForwardIter __last
, _Predicate __pred
);
405 // sort() and its auxiliary functions.
406 _STLP_MOVE_TO_PRIV_NAMESPACE
408 template <class _Size
>
409 inline _Size
__lg(_Size __n
) {
411 for (__k
= 0; __n
!= 1; __n
>>= 1) ++__k
;
415 _STLP_MOVE_TO_STD_NAMESPACE
417 template <class _RandomAccessIter
>
418 void sort(_RandomAccessIter __first
, _RandomAccessIter __last
);
419 template <class _RandomAccessIter
, class _Compare
>
420 void sort(_RandomAccessIter __first
, _RandomAccessIter __last
, _Compare __comp
);
422 // stable_sort() and its auxiliary functions.
423 template <class _RandomAccessIter
>
424 void stable_sort(_RandomAccessIter __first
,
425 _RandomAccessIter __last
);
427 template <class _RandomAccessIter
, class _Compare
>
428 void stable_sort(_RandomAccessIter __first
,
429 _RandomAccessIter __last
, _Compare __comp
);
431 // partial_sort, partial_sort_copy, and auxiliary functions.
433 template <class _RandomAccessIter
>
434 void partial_sort(_RandomAccessIter __first
, _RandomAccessIter __middle
,
435 _RandomAccessIter __last
);
437 template <class _RandomAccessIter
, class _Compare
>
438 void partial_sort(_RandomAccessIter __first
,_RandomAccessIter __middle
,
439 _RandomAccessIter __last
, _Compare __comp
);
441 template <class _InputIter
, class _RandomAccessIter
>
443 partial_sort_copy(_InputIter __first
, _InputIter __last
,
444 _RandomAccessIter __result_first
, _RandomAccessIter __result_last
);
446 template <class _InputIter
, class _RandomAccessIter
, class _Compare
>
448 partial_sort_copy(_InputIter __first
, _InputIter __last
,
449 _RandomAccessIter __result_first
,
450 _RandomAccessIter __result_last
, _Compare __comp
);
452 // nth_element() and its auxiliary functions.
453 template <class _RandomAccessIter
>
454 void nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
455 _RandomAccessIter __last
);
457 template <class _RandomAccessIter
, class _Compare
>
458 void nth_element(_RandomAccessIter __first
, _RandomAccessIter __nth
,
459 _RandomAccessIter __last
, _Compare __comp
);
461 // auxiliary class for lower_bound, etc.
462 _STLP_MOVE_TO_PRIV_NAMESPACE
464 template <class _T1
, class _T2
>
466 bool operator() (const _T1
& __x
, const _T2
& __y
) const { return __x
< __y
; }
469 template <class _T1
, class _T2
>
470 __less_2
<_T1
,_T2
> __less2(_T1
*, _T2
* ) { return __less_2
<_T1
, _T2
>(); }
472 #if defined (_STLP_FUNCTION_PARTIAL_ORDER)
474 less
<_Tp
> __less2(_Tp
*, _Tp
* ) { return less
<_Tp
>(); }
477 _STLP_MOVE_TO_STD_NAMESPACE
479 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
480 template <class _ForwardIter
, class _Tp
>
481 inline _ForwardIter
lower_bound(_ForwardIter __first
, _ForwardIter __last
,
483 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
484 return _STLP_PRIV
__lower_bound(__first
, __last
, __val
,
485 _STLP_PRIV
__less2(_STLP_VALUE_TYPE(__first
, _ForwardIter
), (_Tp
*)0),
486 _STLP_PRIV
__less2((_Tp
*)0, _STLP_VALUE_TYPE(__first
, _ForwardIter
)),
487 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
490 template <class _ForwardIter
, class _Tp
, class _Compare
>
491 inline _ForwardIter
lower_bound(_ForwardIter __first
, _ForwardIter __last
,
492 const _Tp
& __val
, _Compare __comp
) {
493 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
494 return _STLP_PRIV
__lower_bound(__first
, __last
, __val
, __comp
, __comp
,
495 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
498 _STLP_MOVE_TO_PRIV_NAMESPACE
500 template <class _ForwardIter
, class _Tp
, class _Compare1
, class _Compare2
, class _Distance
>
501 _ForwardIter
__upper_bound(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
502 _Compare1 __comp1
, _Compare2 __comp2
, _Distance
*);
504 _STLP_MOVE_TO_STD_NAMESPACE
506 template <class _ForwardIter
, class _Tp
>
507 inline _ForwardIter
upper_bound(_ForwardIter __first
, _ForwardIter __last
,
509 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
510 return _STLP_PRIV
__upper_bound(__first
, __last
, __val
,
511 _STLP_PRIV
__less2(_STLP_VALUE_TYPE(__first
, _ForwardIter
), (_Tp
*)0),
512 _STLP_PRIV
__less2((_Tp
*)0, _STLP_VALUE_TYPE(__first
, _ForwardIter
)),
513 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
516 template <class _ForwardIter
, class _Tp
, class _Compare
>
517 inline _ForwardIter
upper_bound(_ForwardIter __first
, _ForwardIter __last
,
518 const _Tp
& __val
, _Compare __comp
) {
519 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
520 return _STLP_PRIV
__upper_bound(__first
, __last
, __val
, __comp
, __comp
,
521 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
524 _STLP_MOVE_TO_PRIV_NAMESPACE
526 template <class _ForwardIter
, class _Tp
, class _Compare1
, class _Compare2
, class _Distance
>
527 pair
<_ForwardIter
, _ForwardIter
>
528 __equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
529 _Compare1 __comp1
, _Compare2 __comp2
, _Distance
*);
531 _STLP_MOVE_TO_STD_NAMESPACE
533 template <class _ForwardIter
, class _Tp
>
534 inline pair
<_ForwardIter
, _ForwardIter
>
535 equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
) {
536 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
537 return _STLP_PRIV
__equal_range(__first
, __last
, __val
,
538 _STLP_PRIV
__less2(_STLP_VALUE_TYPE(__first
, _ForwardIter
), (_Tp
*)0),
539 _STLP_PRIV
__less2((_Tp
*)0, _STLP_VALUE_TYPE(__first
, _ForwardIter
)),
540 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
543 template <class _ForwardIter
, class _Tp
, class _Compare
>
544 inline pair
<_ForwardIter
, _ForwardIter
>
545 equal_range(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __val
,
547 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
548 return _STLP_PRIV
__equal_range(__first
, __last
, __val
, __comp
, __comp
,
549 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
552 template <class _ForwardIter
, class _Tp
>
553 inline bool binary_search(_ForwardIter __first
, _ForwardIter __last
,
555 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
556 _ForwardIter __i
= _STLP_PRIV
__lower_bound(__first
, __last
, __val
,
557 _STLP_PRIV
__less2(_STLP_VALUE_TYPE(__first
, _ForwardIter
), (_Tp
*)0),
558 _STLP_PRIV
__less2((_Tp
*)0, _STLP_VALUE_TYPE(__first
, _ForwardIter
)),
559 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
560 return __i
!= __last
&& !(__val
< *__i
);
563 template <class _ForwardIter
, class _Tp
, class _Compare
>
564 inline bool binary_search(_ForwardIter __first
, _ForwardIter __last
,
567 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
568 _ForwardIter __i
= _STLP_PRIV
__lower_bound(__first
, __last
, __val
, __comp
, __comp
,
569 _STLP_DISTANCE_TYPE(__first
, _ForwardIter
));
570 return __i
!= __last
&& !__comp(__val
, *__i
);
573 // merge, with and without an explicitly supplied comparison function.
575 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
576 _OutputIter
merge(_InputIter1 __first1
, _InputIter1 __last1
,
577 _InputIter2 __first2
, _InputIter2 __last2
,
578 _OutputIter __result
);
580 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
582 _OutputIter
merge(_InputIter1 __first1
, _InputIter1 __last1
,
583 _InputIter2 __first2
, _InputIter2 __last2
,
584 _OutputIter __result
, _Compare __comp
);
587 // inplace_merge and its auxiliary functions.
590 template <class _BidirectionalIter
>
591 void inplace_merge(_BidirectionalIter __first
,
592 _BidirectionalIter __middle
,
593 _BidirectionalIter __last
) ;
595 template <class _BidirectionalIter
, class _Compare
>
596 void inplace_merge(_BidirectionalIter __first
,
597 _BidirectionalIter __middle
,
598 _BidirectionalIter __last
, _Compare __comp
);
600 // Set algorithms: includes, set_union, set_intersection, set_difference,
601 // set_symmetric_difference. All of these algorithms have the precondition
602 // that their input ranges are sorted and the postcondition that their output
603 // ranges are sorted.
605 template <class _InputIter1
, class _InputIter2
>
606 bool includes(_InputIter1 __first1
, _InputIter1 __last1
,
607 _InputIter2 __first2
, _InputIter2 __last2
);
609 template <class _InputIter1
, class _InputIter2
, class _Compare
>
610 bool includes(_InputIter1 __first1
, _InputIter1 __last1
,
611 _InputIter2 __first2
, _InputIter2 __last2
, _Compare __comp
);
613 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
614 _OutputIter
set_union(_InputIter1 __first1
, _InputIter1 __last1
,
615 _InputIter2 __first2
, _InputIter2 __last2
,
616 _OutputIter __result
);
618 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
620 _OutputIter
set_union(_InputIter1 __first1
, _InputIter1 __last1
,
621 _InputIter2 __first2
, _InputIter2 __last2
,
622 _OutputIter __result
, _Compare __comp
);
624 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
625 _OutputIter
set_intersection(_InputIter1 __first1
, _InputIter1 __last1
,
626 _InputIter2 __first2
, _InputIter2 __last2
,
627 _OutputIter __result
);
629 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
631 _OutputIter
set_intersection(_InputIter1 __first1
, _InputIter1 __last1
,
632 _InputIter2 __first2
, _InputIter2 __last2
,
633 _OutputIter __result
, _Compare __comp
);
637 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
638 _OutputIter
set_difference(_InputIter1 __first1
, _InputIter1 __last1
,
639 _InputIter2 __first2
, _InputIter2 __last2
,
640 _OutputIter __result
);
642 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
644 _OutputIter
set_difference(_InputIter1 __first1
, _InputIter1 __last1
,
645 _InputIter2 __first2
, _InputIter2 __last2
,
646 _OutputIter __result
, _Compare __comp
);
648 template <class _InputIter1
, class _InputIter2
, class _OutputIter
>
650 set_symmetric_difference(_InputIter1 __first1
, _InputIter1 __last1
,
651 _InputIter2 __first2
, _InputIter2 __last2
,
652 _OutputIter __result
);
655 template <class _InputIter1
, class _InputIter2
, class _OutputIter
,
658 set_symmetric_difference(_InputIter1 __first1
, _InputIter1 __last1
,
659 _InputIter2 __first2
, _InputIter2 __last2
,
660 _OutputIter __result
,
664 // min_element and max_element, with and without an explicitly supplied
665 // comparison function.
667 template <class _ForwardIter
>
668 _ForwardIter
max_element(_ForwardIter __first
, _ForwardIter __last
);
669 template <class _ForwardIter
, class _Compare
>
670 _ForwardIter
max_element(_ForwardIter __first
, _ForwardIter __last
,
673 template <class _ForwardIter
>
674 _ForwardIter
min_element(_ForwardIter __first
, _ForwardIter __last
);
676 template <class _ForwardIter
, class _Compare
>
677 _ForwardIter
min_element(_ForwardIter __first
, _ForwardIter __last
,
680 // next_permutation and prev_permutation, with and without an explicitly
681 // supplied comparison function.
683 template <class _BidirectionalIter
>
684 bool next_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
);
686 template <class _BidirectionalIter
, class _Compare
>
687 bool next_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
691 template <class _BidirectionalIter
>
692 bool prev_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
);
695 template <class _BidirectionalIter
, class _Compare
>
696 bool prev_permutation(_BidirectionalIter __first
, _BidirectionalIter __last
,
699 #if !defined (_STLP_NO_EXTENSIONS)
700 // is_heap, a predicate testing whether or not a range is
701 // a heap. This function is an extension, not part of the C++
704 template <class _RandomAccessIter
>
705 bool is_heap(_RandomAccessIter __first
, _RandomAccessIter __last
);
707 template <class _RandomAccessIter
, class _StrictWeakOrdering
>
708 bool is_heap(_RandomAccessIter __first
, _RandomAccessIter __last
,
709 _StrictWeakOrdering __comp
);
711 // is_sorted, a predicated testing whether a range is sorted in
712 // nondescending order. This is an extension, not part of the C++
714 _STLP_MOVE_TO_PRIV_NAMESPACE
716 template <class _ForwardIter
, class _StrictWeakOrdering
>
717 bool __is_sorted(_ForwardIter __first
, _ForwardIter __last
,
718 _StrictWeakOrdering __comp
);
720 _STLP_MOVE_TO_STD_NAMESPACE
721 template <class _ForwardIter
>
722 inline bool is_sorted(_ForwardIter __first
, _ForwardIter __last
) {
723 return _STLP_PRIV
__is_sorted(__first
, __last
,
724 _STLP_PRIV
__less(_STLP_VALUE_TYPE(__first
, _ForwardIter
)));
727 template <class _ForwardIter
, class _StrictWeakOrdering
>
728 inline bool is_sorted(_ForwardIter __first
, _ForwardIter __last
,
729 _StrictWeakOrdering __comp
) {
730 return _STLP_PRIV
__is_sorted(__first
, __last
, __comp
);
736 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
737 # include <stl/_algo.c>
740 #endif /* _STLP_INTERNAL_ALGO_H */