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.
15 * Copyright (c) 1996-1998
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.
32 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
33 #define __SGI_STL_INTERNAL_ALGOBASE_H
35 #include <bits/stl_config.h>
36 #include <bits/stl_relops.h>
37 #ifndef __SGI_STL_INTERNAL_PAIR_H
38 #include <bits/stl_pair.h>
40 #ifndef _CPP_BITS_TYPE_TRAITS_H
41 #include <bits/type_traits.h>
43 #include <bits/std_cstring.h>
44 #include <bits/std_climits.h>
45 #include <bits/std_cstdlib.h>
46 #include <bits/std_cstddef.h>
49 #ifdef __STL_USE_NEW_IOSTREAMS
51 #else /* __STL_USE_NEW_IOSTREAMS */
52 #include <bits/std_iosfwd.h>
53 #endif /* __STL_USE_NEW_IOSTREAMS */
55 #include <bits/stl_iterator_base.h>
56 #include <bits/stl_iterator.h>
58 // We pick up concept_checks.h from stl_iterator_base.h.
64 template <class _ForwardIter1
, class _ForwardIter2
, class _Tp
>
65 inline void __iter_swap(_ForwardIter1 __a
, _ForwardIter2 __b
, _Tp
*) {
71 template <class _ForwardIter1
, class _ForwardIter2
>
72 inline void iter_swap(_ForwardIter1 __a
, _ForwardIter2 __b
) {
73 __STL_REQUIRES(_ForwardIter1
, _Mutable_ForwardIterator
);
74 __STL_REQUIRES(_ForwardIter2
, _Mutable_ForwardIterator
);
75 __STL_CONVERTIBLE(typename iterator_traits
<_ForwardIter1
>::value_type
,
76 typename iterator_traits
<_ForwardIter2
>::value_type
);
77 __STL_CONVERTIBLE(typename iterator_traits
<_ForwardIter2
>::value_type
,
78 typename iterator_traits
<_ForwardIter1
>::value_type
);
79 __iter_swap(__a
, __b
, __VALUE_TYPE(__a
));
83 inline void swap(_Tp
& __a
, _Tp
& __b
) {
84 __STL_REQUIRES(_Tp
, _Assignable
);
90 //--------------------------------------------------
93 #if !defined(__BORLANDC__) || __BORLANDC__ >= 0x540 /* C++ Builder 4.0 */
99 inline const _Tp
& min(const _Tp
& __a
, const _Tp
& __b
) {
100 __STL_REQUIRES(_Tp
, _LessThanComparable
);
101 //return __b < __a ? __b : __a;
102 if (__b
< __a
) return __b
; return __a
;
106 inline const _Tp
& max(const _Tp
& __a
, const _Tp
& __b
) {
107 __STL_REQUIRES(_Tp
, _LessThanComparable
);
108 //return __a < __b ? __b : __a;
109 if (__a
< __b
) return __b
; return __a
;
112 #endif /* __BORLANDC__ */
114 template <class _Tp
, class _Compare
>
115 inline const _Tp
& min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
) {
116 //return __comp(__b, __a) ? __b : __a;
117 if (__comp(__b
, __a
)) return __b
; return __a
;
120 template <class _Tp
, class _Compare
>
121 inline const _Tp
& max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
) {
122 //return __comp(__a, __b) ? __b : __a;
123 if (__comp(__a
, __b
)) return __b
; return __a
;
126 //--------------------------------------------------
129 // All of these auxiliary functions serve two purposes. (1) Replace
130 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
131 // because the input and output ranges are permitted to overlap.)
132 // (2) If we're using random access iterators, then write the loop as
133 // a for loop with an explicit count.
135 template <class _InputIter
, class _OutputIter
, class _Distance
>
136 inline _OutputIter
__copy(_InputIter __first
, _InputIter __last
,
137 _OutputIter __result
,
138 input_iterator_tag
, _Distance
*)
140 for ( ; __first
!= __last
; ++__result
, ++__first
)
141 *__result
= *__first
;
145 template <class _RandomAccessIter
, class _OutputIter
, class _Distance
>
147 __copy(_RandomAccessIter __first
, _RandomAccessIter __last
,
148 _OutputIter __result
, random_access_iterator_tag
, _Distance
*)
150 for (_Distance __n
= __last
- __first
; __n
> 0; --__n
) {
151 *__result
= *__first
;
160 __copy_trivial(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
161 memmove(__result
, __first
, sizeof(_Tp
) * (__last
- __first
));
162 return __result
+ (__last
- __first
);
165 #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
167 template <class _InputIter
, class _OutputIter
>
168 inline _OutputIter
__copy_aux2(_InputIter __first
, _InputIter __last
,
169 _OutputIter __result
, __false_type
) {
170 return __copy(__first
, __last
, __result
,
171 __ITERATOR_CATEGORY(__first
),
172 __DISTANCE_TYPE(__first
));
175 template <class _InputIter
, class _OutputIter
>
176 inline _OutputIter
__copy_aux2(_InputIter __first
, _InputIter __last
,
177 _OutputIter __result
, __true_type
) {
178 return __copy(__first
, __last
, __result
,
179 __ITERATOR_CATEGORY(__first
),
180 __DISTANCE_TYPE(__first
));
186 inline _Tp
* __copy_aux2(_Tp
* __first
, _Tp
* __last
, _Tp
* __result
,
188 return __copy_trivial(__first
, __last
, __result
);
191 #endif /* __USLC__ */
194 inline _Tp
* __copy_aux2(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
,
196 return __copy_trivial(__first
, __last
, __result
);
200 template <class _InputIter
, class _OutputIter
, class _Tp
>
201 inline _OutputIter
__copy_aux(_InputIter __first
, _InputIter __last
,
202 _OutputIter __result
, _Tp
*) {
203 typedef typename __type_traits
<_Tp
>::has_trivial_assignment_operator
205 return __copy_aux2(__first
, __last
, __result
, _Trivial());
208 template<typename _InputIter
, typename _OutputIter
>
209 inline _OutputIter
__copy_ni2(_InputIter __first
, _InputIter __last
,
210 _OutputIter __result
, __true_type
) {
211 return _OutputIter(__copy_aux(__first
, __last
, __result
.base(),
212 __VALUE_TYPE(__first
)));
215 template<typename _InputIter
, typename _OutputIter
>
216 inline _OutputIter
__copy_ni2(_InputIter __first
, _InputIter __last
,
217 _OutputIter __result
, __false_type
) {
218 return __copy_aux(__first
, __last
, __result
, __VALUE_TYPE(__first
));
221 template<typename _InputIter
, typename _OutputIter
>
222 inline _OutputIter
__copy_ni1(_InputIter __first
, _InputIter __last
,
223 _OutputIter __result
, __true_type
) {
224 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
225 return __copy_ni2(__first
.base(), __last
.base(), __result
, __Normal());
228 template<typename _InputIter
, typename _OutputIter
>
229 inline _OutputIter
__copy_ni1(_InputIter __first
, _InputIter __last
,
230 _OutputIter __result
, __false_type
) {
231 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
232 return __copy_ni2(__first
, __last
, __result
, __Normal());
235 template <class _InputIter
, class _OutputIter
>
236 inline _OutputIter
copy(_InputIter __first
, _InputIter __last
,
237 _OutputIter __result
) {
238 __STL_REQUIRES(_InputIter
, _InputIterator
);
239 __STL_REQUIRES(_OutputIter
, _OutputIterator
);
240 typedef typename _Is_normal_iterator
<_InputIter
>::_Normal __Normal
;
241 return __copy_ni1(__first
, __last
, __result
, __Normal());
244 // Hack for compilers that don't have partial ordering of function templates
245 // but do have partial specialization of class templates.
246 #elif defined(__STL_CLASS_PARTIAL_SPECIALIZATION)
248 template <class _InputIter
, class _OutputIter
, class _BoolType
>
249 struct __copy_dispatch
{
250 static _OutputIter
copy(_InputIter __first
, _InputIter __last
,
251 _OutputIter __result
) {
252 typedef typename iterator_traits
<_InputIter
>::iterator_category _Category
;
253 typedef typename iterator_traits
<_InputIter
>::difference_type _Distance
;
254 return __copy(__first
, __last
, __result
, _Category(), (_Distance
*) 0);
259 struct __copy_dispatch
<_Tp
*, _Tp
*, __true_type
>
261 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
262 return __copy_trivial(__first
, __last
, __result
);
267 struct __copy_dispatch
<const _Tp
*, _Tp
*, __true_type
>
269 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
270 return __copy_trivial(__first
, __last
, __result
);
274 template <class _InputIter
, class _OutputIter
>
275 inline _OutputIter
copy(_InputIter __first
, _InputIter __last
,
276 _OutputIter __result
) {
277 __STL_REQUIRES(_InputIter
, _InputIterator
);
278 __STL_REQUIRES(_OutputIter
, _OutputIterator
);
279 typedef typename iterator_traits
<_InputIter
>::value_type _Tp
;
280 typedef typename __type_traits
<_Tp
>::has_trivial_assignment_operator
282 return __copy_dispatch
<_InputIter
, _OutputIter
, _Trivial
>
283 ::copy(__first
, __last
, __result
);
286 // Fallback for compilers with neither partial ordering nor partial
287 // specialization. Define the faster version for the basic builtin
289 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
291 template <class _InputIter
, class _OutputIter
>
292 inline _OutputIter
copy(_InputIter __first
, _InputIter __last
,
293 _OutputIter __result
)
295 return __copy(__first
, __last
, __result
,
296 __ITERATOR_CATEGORY(__first
),
297 __DISTANCE_TYPE(__first
));
300 #define __SGI_STL_DECLARE_COPY_TRIVIAL(_Tp) \
301 inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) { \
302 memmove(__result, __first, sizeof(_Tp) * (__last - __first)); \
303 return __result + (__last - __first); \
306 __SGI_STL_DECLARE_COPY_TRIVIAL(char)
307 __SGI_STL_DECLARE_COPY_TRIVIAL(signed char)
308 __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned char)
309 __SGI_STL_DECLARE_COPY_TRIVIAL(short)
310 __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned short)
311 __SGI_STL_DECLARE_COPY_TRIVIAL(int)
312 __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned int)
313 __SGI_STL_DECLARE_COPY_TRIVIAL(long)
314 __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned long)
315 #ifdef __STL_HAS_WCHAR_T
316 __SGI_STL_DECLARE_COPY_TRIVIAL(wchar_t)
318 #ifdef _STL_LONG_LONG
319 __SGI_STL_DECLARE_COPY_TRIVIAL(long long)
320 __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned long long)
322 __SGI_STL_DECLARE_COPY_TRIVIAL(float)
323 __SGI_STL_DECLARE_COPY_TRIVIAL(double)
324 __SGI_STL_DECLARE_COPY_TRIVIAL(long double)
326 #undef __SGI_STL_DECLARE_COPY_TRIVIAL
327 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
329 //--------------------------------------------------
332 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
334 inline _BidirectionalIter2
__copy_backward(_BidirectionalIter1 __first
,
335 _BidirectionalIter1 __last
,
336 _BidirectionalIter2 __result
,
337 bidirectional_iterator_tag
,
340 while (__first
!= __last
)
341 *--__result
= *--__last
;
345 template <class _RandomAccessIter
, class _BidirectionalIter
, class _Distance
>
346 inline _BidirectionalIter
__copy_backward(_RandomAccessIter __first
,
347 _RandomAccessIter __last
,
348 _BidirectionalIter __result
,
349 random_access_iterator_tag
,
352 for (_Distance __n
= __last
- __first
; __n
> 0; --__n
)
353 *--__result
= *--__last
;
357 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
359 // This dispatch class is a workaround for compilers that do not
360 // have partial ordering of function templates. All we're doing is
361 // creating a specialization so that we can turn a call to copy_backward
362 // into a memmove whenever possible.
364 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
366 struct __copy_backward_dispatch
368 typedef typename iterator_traits
<_BidirectionalIter1
>::iterator_category
370 typedef typename iterator_traits
<_BidirectionalIter1
>::difference_type
373 static _BidirectionalIter2
copy(_BidirectionalIter1 __first
,
374 _BidirectionalIter1 __last
,
375 _BidirectionalIter2 __result
) {
376 return __copy_backward(__first
, __last
, __result
, _Cat(), (_Distance
*) 0);
381 struct __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
383 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
384 const ptrdiff_t _Num
= __last
- __first
;
385 memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
386 return __result
- _Num
;
391 struct __copy_backward_dispatch
<const _Tp
*, _Tp
*, __true_type
>
393 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
394 return __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
395 ::copy(__first
, __last
, __result
);
399 template <class _BI1
, class _BI2
>
400 inline _BI2
__copy_backward_aux(_BI1 __first
, _BI1 __last
, _BI2 __result
) {
401 typedef typename __type_traits
<typename iterator_traits
<_BI2
>::value_type
>
402 ::has_trivial_assignment_operator
404 return __copy_backward_dispatch
<_BI1
, _BI2
, _Trivial
>
405 ::copy(__first
, __last
, __result
);
408 template <typename _BI1
, typename _BI2
>
409 inline _BI2
__copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
410 _BI2 __result
, __true_type
) {
411 return _BI2(__copy_backward_aux(__first
, __last
, __result
.base()));
414 template <typename _BI1
, typename _BI2
>
415 inline _BI2
__copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
416 _BI2 __result
, __false_type
){
417 return __copy_backward_aux(__first
, __last
, __result
);
420 template <typename _BI1
, typename _BI2
>
421 inline _BI2
__copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
422 _BI2 __result
, __true_type
) {
423 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
424 return __copy_backward_output_normal_iterator(__first
.base(), __last
.base(),
425 __result
, __Normal());
428 template <typename _BI1
, typename _BI2
>
429 inline _BI2
__copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
430 _BI2 __result
, __false_type
) {
431 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
432 return __copy_backward_output_normal_iterator(__first
, __last
, __result
,
436 template <typename _BI1
, typename _BI2
>
437 inline _BI2
copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
) {
438 __STL_REQUIRES(_BI1
, _BidirectionalIterator
);
439 __STL_REQUIRES(_BI2
, _Mutable_BidirectionalIterator
);
440 __STL_CONVERTIBLE(typename iterator_traits
<_BI1
>::value_type
,
441 typename iterator_traits
<_BI2
>::value_type
);
442 typedef typename _Is_normal_iterator
<_BI1
>::_Normal __Normal
;
443 return __copy_backward_input_normal_iterator(__first
, __last
, __result
,
447 #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
449 template <class _BI1
, class _BI2
>
450 inline _BI2
copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
) {
451 return __copy_backward(__first
, __last
, __result
,
452 __ITERATOR_CATEGORY(__first
),
453 __DISTANCE_TYPE(__first
));
456 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
458 //--------------------------------------------------
459 // copy_n (not part of the C++ standard)
461 template <class _InputIter
, class _Size
, class _OutputIter
>
462 pair
<_InputIter
, _OutputIter
> __copy_n(_InputIter __first
, _Size __count
,
463 _OutputIter __result
,
464 input_iterator_tag
) {
465 for ( ; __count
> 0; --__count
) {
466 *__result
= *__first
;
470 return pair
<_InputIter
, _OutputIter
>(__first
, __result
);
473 template <class _RAIter
, class _Size
, class _OutputIter
>
474 inline pair
<_RAIter
, _OutputIter
>
475 __copy_n(_RAIter __first
, _Size __count
,
476 _OutputIter __result
,
477 random_access_iterator_tag
) {
478 _RAIter __last
= __first
+ __count
;
479 return pair
<_RAIter
, _OutputIter
>(__last
, copy(__first
, __last
, __result
));
482 template <class _InputIter
, class _Size
, class _OutputIter
>
483 inline pair
<_InputIter
, _OutputIter
>
484 __copy_n(_InputIter __first
, _Size __count
, _OutputIter __result
) {
485 return __copy_n(__first
, __count
, __result
,
486 __ITERATOR_CATEGORY(__first
));
489 template <class _InputIter
, class _Size
, class _OutputIter
>
490 inline pair
<_InputIter
, _OutputIter
>
491 copy_n(_InputIter __first
, _Size __count
, _OutputIter __result
) {
492 __STL_REQUIRES(_InputIter
, _InputIterator
);
493 __STL_REQUIRES(_OutputIter
, _OutputIterator
);
494 return __copy_n(__first
, __count
, __result
);
497 //--------------------------------------------------
501 template <class _ForwardIter
, class _Tp
>
502 void fill(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __value
) {
503 __STL_REQUIRES(_ForwardIter
, _Mutable_ForwardIterator
);
504 for ( ; __first
!= __last
; ++__first
)
508 template <class _OutputIter
, class _Size
, class _Tp
>
509 _OutputIter
fill_n(_OutputIter __first
, _Size __n
, const _Tp
& __value
) {
510 __STL_REQUIRES(_OutputIter
, _OutputIterator
);
511 for ( ; __n
> 0; --__n
, ++__first
)
516 // Specialization: for one-byte types we can use memset.
518 inline void fill(unsigned char* __first
, unsigned char* __last
,
519 const unsigned char& __c
) {
520 unsigned char __tmp
= __c
;
521 memset(__first
, __tmp
, __last
- __first
);
524 inline void fill(signed char* __first
, signed char* __last
,
525 const signed char& __c
) {
526 signed char __tmp
= __c
;
527 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
530 inline void fill(char* __first
, char* __last
, const char& __c
) {
532 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
535 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
537 template <class _Size
>
538 inline unsigned char* fill_n(unsigned char* __first
, _Size __n
,
539 const unsigned char& __c
) {
540 fill(__first
, __first
+ __n
, __c
);
541 return __first
+ __n
;
544 template <class _Size
>
545 inline signed char* fill_n(char* __first
, _Size __n
,
546 const signed char& __c
) {
547 fill(__first
, __first
+ __n
, __c
);
548 return __first
+ __n
;
551 template <class _Size
>
552 inline char* fill_n(char* __first
, _Size __n
, const char& __c
) {
553 fill(__first
, __first
+ __n
, __c
);
554 return __first
+ __n
;
557 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
559 //--------------------------------------------------
560 // equal and mismatch
562 template <class _InputIter1
, class _InputIter2
>
563 pair
<_InputIter1
, _InputIter2
> mismatch(_InputIter1 __first1
,
565 _InputIter2 __first2
) {
566 __STL_REQUIRES(_InputIter1
, _InputIterator
);
567 __STL_REQUIRES(_InputIter2
, _InputIterator
);
568 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
569 _EqualityComparable
);
570 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
571 _EqualityComparable
);
572 while (__first1
!= __last1
&& *__first1
== *__first2
) {
576 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
579 template <class _InputIter1
, class _InputIter2
, class _BinaryPredicate
>
580 pair
<_InputIter1
, _InputIter2
> mismatch(_InputIter1 __first1
,
582 _InputIter2 __first2
,
583 _BinaryPredicate __binary_pred
) {
584 __STL_REQUIRES(_InputIter1
, _InputIterator
);
585 __STL_REQUIRES(_InputIter2
, _InputIterator
);
586 while (__first1
!= __last1
&& __binary_pred(*__first1
, *__first2
)) {
590 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
593 template <class _InputIter1
, class _InputIter2
>
594 inline bool equal(_InputIter1 __first1
, _InputIter1 __last1
,
595 _InputIter2 __first2
) {
596 __STL_REQUIRES(_InputIter1
, _InputIterator
);
597 __STL_REQUIRES(_InputIter2
, _InputIterator
);
598 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
599 _EqualityComparable
);
600 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
601 _EqualityComparable
);
602 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
603 if (*__first1
!= *__first2
)
608 template <class _InputIter1
, class _InputIter2
, class _BinaryPredicate
>
609 inline bool equal(_InputIter1 __first1
, _InputIter1 __last1
,
610 _InputIter2 __first2
, _BinaryPredicate __binary_pred
) {
611 __STL_REQUIRES(_InputIter1
, _InputIterator
);
612 __STL_REQUIRES(_InputIter2
, _InputIterator
);
613 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
614 if (!__binary_pred(*__first1
, *__first2
))
619 //--------------------------------------------------
620 // lexicographical_compare and lexicographical_compare_3way.
621 // (the latter is not part of the C++ standard.)
623 template <class _InputIter1
, class _InputIter2
>
624 bool lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
625 _InputIter2 __first2
, _InputIter2 __last2
) {
626 __STL_REQUIRES(_InputIter1
, _InputIterator
);
627 __STL_REQUIRES(_InputIter2
, _InputIterator
);
628 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
629 _LessThanComparable
);
630 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
631 _LessThanComparable
);
632 for ( ; __first1
!= __last1
&& __first2
!= __last2
633 ; ++__first1
, ++__first2
) {
634 if (*__first1
< *__first2
)
636 if (*__first2
< *__first1
)
639 return __first1
== __last1
&& __first2
!= __last2
;
642 template <class _InputIter1
, class _InputIter2
, class _Compare
>
643 bool lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
644 _InputIter2 __first2
, _InputIter2 __last2
,
646 __STL_REQUIRES(_InputIter1
, _InputIterator
);
647 __STL_REQUIRES(_InputIter2
, _InputIterator
);
648 for ( ; __first1
!= __last1
&& __first2
!= __last2
649 ; ++__first1
, ++__first2
) {
650 if (__comp(*__first1
, *__first2
))
652 if (__comp(*__first2
, *__first1
))
655 return __first1
== __last1
&& __first2
!= __last2
;
659 lexicographical_compare(const unsigned char* __first1
,
660 const unsigned char* __last1
,
661 const unsigned char* __first2
,
662 const unsigned char* __last2
)
664 const size_t __len1
= __last1
- __first1
;
665 const size_t __len2
= __last2
- __first2
;
666 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
667 return __result
!= 0 ? __result
< 0 : __len1
< __len2
;
670 inline bool lexicographical_compare(const char* __first1
, const char* __last1
,
671 const char* __first2
, const char* __last2
)
673 #if CHAR_MAX == SCHAR_MAX
674 return lexicographical_compare((const signed char*) __first1
,
675 (const signed char*) __last1
,
676 (const signed char*) __first2
,
677 (const signed char*) __last2
);
678 #else /* CHAR_MAX == SCHAR_MAX */
679 return lexicographical_compare((const unsigned char*) __first1
,
680 (const unsigned char*) __last1
,
681 (const unsigned char*) __first2
,
682 (const unsigned char*) __last2
);
683 #endif /* CHAR_MAX == SCHAR_MAX */
686 template <class _InputIter1
, class _InputIter2
>
687 int __lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
688 _InputIter2 __first2
, _InputIter2 __last2
)
690 while (__first1
!= __last1
&& __first2
!= __last2
) {
691 if (*__first1
< *__first2
)
693 if (*__first2
< *__first1
)
698 if (__first2
== __last2
) {
699 return !(__first1
== __last1
);
707 __lexicographical_compare_3way(const unsigned char* __first1
,
708 const unsigned char* __last1
,
709 const unsigned char* __first2
,
710 const unsigned char* __last2
)
712 const ptrdiff_t __len1
= __last1
- __first1
;
713 const ptrdiff_t __len2
= __last2
- __first2
;
714 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
715 return __result
!= 0 ? __result
716 : (__len1
== __len2
? 0 : (__len1
< __len2
? -1 : 1));
720 __lexicographical_compare_3way(const char* __first1
, const char* __last1
,
721 const char* __first2
, const char* __last2
)
723 #if CHAR_MAX == SCHAR_MAX
724 return __lexicographical_compare_3way(
725 (const signed char*) __first1
,
726 (const signed char*) __last1
,
727 (const signed char*) __first2
,
728 (const signed char*) __last2
);
730 return __lexicographical_compare_3way((const unsigned char*) __first1
,
731 (const unsigned char*) __last1
,
732 (const unsigned char*) __first2
,
733 (const unsigned char*) __last2
);
737 template <class _InputIter1
, class _InputIter2
>
738 int lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
739 _InputIter2 __first2
, _InputIter2 __last2
)
741 __STL_REQUIRES(_InputIter1
, _InputIterator
);
742 __STL_REQUIRES(_InputIter2
, _InputIterator
);
743 __STL_REQUIRES(typename iterator_traits
<_InputIter1
>::value_type
,
744 _LessThanComparable
);
745 __STL_REQUIRES(typename iterator_traits
<_InputIter2
>::value_type
,
746 _LessThanComparable
);
747 return __lexicographical_compare_3way(__first1
, __last1
, __first2
, __last2
);
752 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */