1 // Bits and pieces used in algorithms -*- C++ -*-
3 // Copyright (C) 2001 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
33 * Hewlett-Packard Company
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
44 * Copyright (c) 1996-1998
45 * Silicon Graphics Computer Systems, Inc.
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
56 /* NOTE: This is an internal header file, included by other STL headers.
57 * You should not attempt to use it directly.
61 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
62 #define __SGI_STL_INTERNAL_ALGOBASE_H
64 #include <bits/c++config.h>
65 #ifndef __SGI_STL_INTERNAL_PAIR_H
66 #include <bits/stl_pair.h>
68 #ifndef _CPP_BITS_TYPE_TRAITS_H
69 #include <bits/type_traits.h>
71 #include <bits/std_cstring.h>
72 #include <bits/std_climits.h>
73 #include <bits/std_cstdlib.h>
74 #include <bits/std_cstddef.h>
77 #include <bits/std_iosfwd.h>
78 #include <bits/stl_iterator_base_types.h>
79 #include <bits/stl_iterator_base_funcs.h>
80 #include <bits/stl_iterator.h>
81 #include <bits/concept_check.h>
88 template <class _ForwardIter1
, class _ForwardIter2
, class _Tp
>
89 inline void __iter_swap(_ForwardIter1 __a
, _ForwardIter2 __b
, _Tp
*)
96 template <class _ForwardIter1
, class _ForwardIter2
>
97 inline void iter_swap(_ForwardIter1 __a
, _ForwardIter2 __b
)
99 // concept requirements
100 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept
<_ForwardIter1
>);
101 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept
<_ForwardIter2
>);
102 __glibcpp_function_requires(_ConvertibleConcept
<
103 typename iterator_traits
<_ForwardIter1
>::value_type
,
104 typename iterator_traits
<_ForwardIter2
>::value_type
>);
105 __glibcpp_function_requires(_ConvertibleConcept
<
106 typename iterator_traits
<_ForwardIter2
>::value_type
,
107 typename iterator_traits
<_ForwardIter1
>::value_type
>);
109 __iter_swap(__a
, __b
, __value_type(__a
));
113 inline void swap(_Tp
& __a
, _Tp
& __b
)
115 // concept requirements
116 __glibcpp_function_requires(_SGIAssignableConcept
<_Tp
>);
123 //--------------------------------------------------
130 inline const _Tp
& min(const _Tp
& __a
, const _Tp
& __b
) {
131 // concept requirements
132 __glibcpp_function_requires(_LessThanComparableConcept
<_Tp
>);
133 //return __b < __a ? __b : __a;
134 if (__b
< __a
) return __b
; return __a
;
138 inline const _Tp
& max(const _Tp
& __a
, const _Tp
& __b
) {
139 // concept requirements
140 __glibcpp_function_requires(_LessThanComparableConcept
<_Tp
>);
141 //return __a < __b ? __b : __a;
142 if (__a
< __b
) return __b
; return __a
;
145 template <class _Tp
, class _Compare
>
146 inline const _Tp
& min(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
) {
147 //return __comp(__b, __a) ? __b : __a;
148 if (__comp(__b
, __a
)) return __b
; return __a
;
151 template <class _Tp
, class _Compare
>
152 inline const _Tp
& max(const _Tp
& __a
, const _Tp
& __b
, _Compare __comp
) {
153 //return __comp(__a, __b) ? __b : __a;
154 if (__comp(__a
, __b
)) return __b
; return __a
;
157 //--------------------------------------------------
160 // All of these auxiliary functions serve two purposes. (1) Replace
161 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
162 // because the input and output ranges are permitted to overlap.)
163 // (2) If we're using random access iterators, then write the loop as
164 // a for loop with an explicit count.
166 template <class _InputIter
, class _OutputIter
, class _Distance
>
167 inline _OutputIter
__copy(_InputIter __first
, _InputIter __last
,
168 _OutputIter __result
,
169 input_iterator_tag
, _Distance
*)
171 for ( ; __first
!= __last
; ++__result
, ++__first
)
172 *__result
= *__first
;
176 template <class _RandomAccessIter
, class _OutputIter
, class _Distance
>
178 __copy(_RandomAccessIter __first
, _RandomAccessIter __last
,
179 _OutputIter __result
, random_access_iterator_tag
, _Distance
*)
181 for (_Distance __n
= __last
- __first
; __n
> 0; --__n
) {
182 *__result
= *__first
;
191 __copy_trivial(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
)
193 memmove(__result
, __first
, sizeof(_Tp
) * (__last
- __first
));
194 return __result
+ (__last
- __first
);
198 template <class _InputIter
, class _OutputIter
>
199 inline _OutputIter
__copy_aux2(_InputIter __first
, _InputIter __last
,
200 _OutputIter __result
, __false_type
)
202 return __copy(__first
, __last
, __result
,
203 __iterator_category(__first
),
204 __distance_type(__first
));
207 template <class _InputIter
, class _OutputIter
>
208 inline _OutputIter
__copy_aux2(_InputIter __first
, _InputIter __last
,
209 _OutputIter __result
, __true_type
)
211 return __copy(__first
, __last
, __result
,
212 __iterator_category(__first
),
213 __distance_type(__first
));
217 inline _Tp
* __copy_aux2(_Tp
* __first
, _Tp
* __last
, _Tp
* __result
,
220 return __copy_trivial(__first
, __last
, __result
);
224 inline _Tp
* __copy_aux2(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
,
227 return __copy_trivial(__first
, __last
, __result
);
231 template <class _InputIter
, class _OutputIter
, class _Tp
>
232 inline _OutputIter
__copy_aux(_InputIter __first
, _InputIter __last
,
233 _OutputIter __result
, _Tp
*)
235 typedef typename __type_traits
<_Tp
>::has_trivial_assignment_operator
237 return __copy_aux2(__first
, __last
, __result
, _Trivial());
240 template<typename _InputIter
, typename _OutputIter
>
241 inline _OutputIter
__copy_ni2(_InputIter __first
, _InputIter __last
,
242 _OutputIter __result
, __true_type
)
244 return _OutputIter(__copy_aux(__first
, __last
, __result
.base(),
245 __value_type(__first
)));
248 template<typename _InputIter
, typename _OutputIter
>
249 inline _OutputIter
__copy_ni2(_InputIter __first
, _InputIter __last
,
250 _OutputIter __result
, __false_type
)
252 return __copy_aux(__first
, __last
, __result
, __value_type(__first
));
255 template<typename _InputIter
, typename _OutputIter
>
256 inline _OutputIter
__copy_ni1(_InputIter __first
, _InputIter __last
,
257 _OutputIter __result
, __true_type
)
259 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
260 return __copy_ni2(__first
.base(), __last
.base(), __result
, __Normal());
263 template<typename _InputIter
, typename _OutputIter
>
264 inline _OutputIter
__copy_ni1(_InputIter __first
, _InputIter __last
,
265 _OutputIter __result
, __false_type
)
267 typedef typename _Is_normal_iterator
<_OutputIter
>::_Normal __Normal
;
268 return __copy_ni2(__first
, __last
, __result
, __Normal());
271 template <class _InputIter
, class _OutputIter
>
272 inline _OutputIter
copy(_InputIter __first
, _InputIter __last
,
273 _OutputIter __result
)
275 // concept requirements
276 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter
>);
277 __glibcpp_function_requires(_OutputIteratorConcept
<_OutputIter
,
278 typename iterator_traits
<_InputIter
>::value_type
>);
280 typedef typename _Is_normal_iterator
<_InputIter
>::_Normal __Normal
;
281 return __copy_ni1(__first
, __last
, __result
, __Normal());
284 //--------------------------------------------------
287 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
289 inline _BidirectionalIter2
__copy_backward(_BidirectionalIter1 __first
,
290 _BidirectionalIter1 __last
,
291 _BidirectionalIter2 __result
,
292 bidirectional_iterator_tag
,
295 while (__first
!= __last
)
296 *--__result
= *--__last
;
300 template <class _RandomAccessIter
, class _BidirectionalIter
, class _Distance
>
301 inline _BidirectionalIter
__copy_backward(_RandomAccessIter __first
,
302 _RandomAccessIter __last
,
303 _BidirectionalIter __result
,
304 random_access_iterator_tag
,
307 for (_Distance __n
= __last
- __first
; __n
> 0; --__n
)
308 *--__result
= *--__last
;
313 // This dispatch class is a workaround for compilers that do not
314 // have partial ordering of function templates. All we're doing is
315 // creating a specialization so that we can turn a call to copy_backward
316 // into a memmove whenever possible.
318 template <class _BidirectionalIter1
, class _BidirectionalIter2
,
320 struct __copy_backward_dispatch
322 typedef typename iterator_traits
<_BidirectionalIter1
>::iterator_category
324 typedef typename iterator_traits
<_BidirectionalIter1
>::difference_type
327 static _BidirectionalIter2
copy(_BidirectionalIter1 __first
,
328 _BidirectionalIter1 __last
,
329 _BidirectionalIter2 __result
) {
330 return __copy_backward(__first
, __last
, __result
, _Cat(), (_Distance
*) 0);
335 struct __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
337 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
338 const ptrdiff_t _Num
= __last
- __first
;
339 memmove(__result
- _Num
, __first
, sizeof(_Tp
) * _Num
);
340 return __result
- _Num
;
345 struct __copy_backward_dispatch
<const _Tp
*, _Tp
*, __true_type
>
347 static _Tp
* copy(const _Tp
* __first
, const _Tp
* __last
, _Tp
* __result
) {
348 return __copy_backward_dispatch
<_Tp
*, _Tp
*, __true_type
>
349 ::copy(__first
, __last
, __result
);
353 template <class _BI1
, class _BI2
>
354 inline _BI2
__copy_backward_aux(_BI1 __first
, _BI1 __last
, _BI2 __result
) {
355 typedef typename __type_traits
<typename iterator_traits
<_BI2
>::value_type
>
356 ::has_trivial_assignment_operator
358 return __copy_backward_dispatch
<_BI1
, _BI2
, _Trivial
>
359 ::copy(__first
, __last
, __result
);
362 template <typename _BI1
, typename _BI2
>
363 inline _BI2
__copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
364 _BI2 __result
, __true_type
) {
365 return _BI2(__copy_backward_aux(__first
, __last
, __result
.base()));
368 template <typename _BI1
, typename _BI2
>
369 inline _BI2
__copy_backward_output_normal_iterator(_BI1 __first
, _BI1 __last
,
370 _BI2 __result
, __false_type
){
371 return __copy_backward_aux(__first
, __last
, __result
);
374 template <typename _BI1
, typename _BI2
>
375 inline _BI2
__copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
376 _BI2 __result
, __true_type
) {
377 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
378 return __copy_backward_output_normal_iterator(__first
.base(), __last
.base(),
379 __result
, __Normal());
382 template <typename _BI1
, typename _BI2
>
383 inline _BI2
__copy_backward_input_normal_iterator(_BI1 __first
, _BI1 __last
,
384 _BI2 __result
, __false_type
) {
385 typedef typename _Is_normal_iterator
<_BI2
>::_Normal __Normal
;
386 return __copy_backward_output_normal_iterator(__first
, __last
, __result
,
390 template <typename _BI1
, typename _BI2
>
391 inline _BI2
copy_backward(_BI1 __first
, _BI1 __last
, _BI2 __result
)
393 // concept requirements
394 __glibcpp_function_requires(_BidirectionalIteratorConcept
<_BI1
>);
395 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept
<_BI2
>);
396 __glibcpp_function_requires(_ConvertibleConcept
<
397 typename iterator_traits
<_BI1
>::value_type
,
398 typename iterator_traits
<_BI2
>::value_type
>);
400 typedef typename _Is_normal_iterator
<_BI1
>::_Normal __Normal
;
401 return __copy_backward_input_normal_iterator(__first
, __last
, __result
,
405 //--------------------------------------------------
406 // copy_n (not part of the C++ standard)
408 template <class _InputIter
, class _Size
, class _OutputIter
>
409 pair
<_InputIter
, _OutputIter
> __copy_n(_InputIter __first
, _Size __count
,
410 _OutputIter __result
,
411 input_iterator_tag
) {
412 for ( ; __count
> 0; --__count
) {
413 *__result
= *__first
;
417 return pair
<_InputIter
, _OutputIter
>(__first
, __result
);
420 template <class _RAIter
, class _Size
, class _OutputIter
>
421 inline pair
<_RAIter
, _OutputIter
>
422 __copy_n(_RAIter __first
, _Size __count
,
423 _OutputIter __result
,
424 random_access_iterator_tag
) {
425 _RAIter __last
= __first
+ __count
;
426 return pair
<_RAIter
, _OutputIter
>(__last
, copy(__first
, __last
, __result
));
429 template <class _InputIter
, class _Size
, class _OutputIter
>
430 inline pair
<_InputIter
, _OutputIter
>
431 __copy_n(_InputIter __first
, _Size __count
, _OutputIter __result
) {
432 return __copy_n(__first
, __count
, __result
,
433 __iterator_category(__first
));
436 template <class _InputIter
, class _Size
, class _OutputIter
>
437 inline pair
<_InputIter
, _OutputIter
>
438 copy_n(_InputIter __first
, _Size __count
, _OutputIter __result
)
440 // concept requirements
441 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter
>);
442 __glibcpp_function_requires(_OutputIteratorConcept
<_OutputIter
,
443 typename iterator_traits
<_InputIter
>::value_type
>);
445 return __copy_n(__first
, __count
, __result
);
448 //--------------------------------------------------
452 template <class _ForwardIter
, class _Tp
>
453 void fill(_ForwardIter __first
, _ForwardIter __last
, const _Tp
& __value
)
455 // concept requirements
456 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept
<_ForwardIter
>);
458 for ( ; __first
!= __last
; ++__first
)
462 template <class _OutputIter
, class _Size
, class _Tp
>
463 _OutputIter
fill_n(_OutputIter __first
, _Size __n
, const _Tp
& __value
)
465 // concept requirements
466 __glibcpp_function_requires(_OutputIteratorConcept
<_OutputIter
,_Tp
>);
468 for ( ; __n
> 0; --__n
, ++__first
)
473 // Specialization: for one-byte types we can use memset.
475 inline void fill(unsigned char* __first
, unsigned char* __last
,
476 const unsigned char& __c
)
478 unsigned char __tmp
= __c
;
479 memset(__first
, __tmp
, __last
- __first
);
482 inline void fill(signed char* __first
, signed char* __last
,
483 const signed char& __c
)
485 signed char __tmp
= __c
;
486 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
489 inline void fill(char* __first
, char* __last
, const char& __c
)
492 memset(__first
, static_cast<unsigned char>(__tmp
), __last
- __first
);
495 template <class _Size
>
496 inline unsigned char* fill_n(unsigned char* __first
, _Size __n
,
497 const unsigned char& __c
)
499 fill(__first
, __first
+ __n
, __c
);
500 return __first
+ __n
;
503 template <class _Size
>
504 inline signed char* fill_n(char* __first
, _Size __n
,
505 const signed char& __c
)
507 fill(__first
, __first
+ __n
, __c
);
508 return __first
+ __n
;
511 template <class _Size
>
512 inline char* fill_n(char* __first
, _Size __n
, const char& __c
)
514 fill(__first
, __first
+ __n
, __c
);
515 return __first
+ __n
;
519 //--------------------------------------------------
520 // equal and mismatch
522 template <class _InputIter1
, class _InputIter2
>
523 pair
<_InputIter1
, _InputIter2
> mismatch(_InputIter1 __first1
,
525 _InputIter2 __first2
)
527 // concept requirements
528 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>);
529 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>);
530 __glibcpp_function_requires(_EqualityComparableConcept
<
531 typename iterator_traits
<_InputIter1
>::value_type
>);
532 __glibcpp_function_requires(_EqualityComparableConcept
<
533 typename iterator_traits
<_InputIter2
>::value_type
>);
535 while (__first1
!= __last1
&& *__first1
== *__first2
) {
539 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
542 template <class _InputIter1
, class _InputIter2
, class _BinaryPredicate
>
543 pair
<_InputIter1
, _InputIter2
> mismatch(_InputIter1 __first1
,
545 _InputIter2 __first2
,
546 _BinaryPredicate __binary_pred
)
548 // concept requirements
549 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>);
550 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>);
552 while (__first1
!= __last1
&& __binary_pred(*__first1
, *__first2
)) {
556 return pair
<_InputIter1
, _InputIter2
>(__first1
, __first2
);
559 template <class _InputIter1
, class _InputIter2
>
560 inline bool equal(_InputIter1 __first1
, _InputIter1 __last1
,
561 _InputIter2 __first2
)
563 // concept requirements
564 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>);
565 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>);
566 __glibcpp_function_requires(_EqualOpConcept
<
567 typename iterator_traits
<_InputIter1
>::value_type
,
568 typename iterator_traits
<_InputIter2
>::value_type
>);
570 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
571 if (!(*__first1
== *__first2
))
576 template <class _InputIter1
, class _InputIter2
, class _BinaryPredicate
>
577 inline bool equal(_InputIter1 __first1
, _InputIter1 __last1
,
578 _InputIter2 __first2
, _BinaryPredicate __binary_pred
)
580 // concept requirements
581 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>);
582 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>);
584 for ( ; __first1
!= __last1
; ++__first1
, ++__first2
)
585 if (!__binary_pred(*__first1
, *__first2
))
590 //--------------------------------------------------
591 // lexicographical_compare and lexicographical_compare_3way.
592 // (the latter is not part of the C++ standard.)
594 template <class _InputIter1
, class _InputIter2
>
595 bool lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
596 _InputIter2 __first2
, _InputIter2 __last2
)
598 // concept requirements
599 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>);
600 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>);
601 __glibcpp_function_requires(_LessThanComparableConcept
<
602 typename iterator_traits
<_InputIter1
>::value_type
>);
603 __glibcpp_function_requires(_LessThanComparableConcept
<
604 typename iterator_traits
<_InputIter2
>::value_type
>);
606 for ( ; __first1
!= __last1
&& __first2
!= __last2
607 ; ++__first1
, ++__first2
) {
608 if (*__first1
< *__first2
)
610 if (*__first2
< *__first1
)
613 return __first1
== __last1
&& __first2
!= __last2
;
616 template <class _InputIter1
, class _InputIter2
, class _Compare
>
617 bool lexicographical_compare(_InputIter1 __first1
, _InputIter1 __last1
,
618 _InputIter2 __first2
, _InputIter2 __last2
,
621 // concept requirements
622 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>);
623 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>);
625 for ( ; __first1
!= __last1
&& __first2
!= __last2
626 ; ++__first1
, ++__first2
) {
627 if (__comp(*__first1
, *__first2
))
629 if (__comp(*__first2
, *__first1
))
632 return __first1
== __last1
&& __first2
!= __last2
;
636 lexicographical_compare(const unsigned char* __first1
,
637 const unsigned char* __last1
,
638 const unsigned char* __first2
,
639 const unsigned char* __last2
)
641 const size_t __len1
= __last1
- __first1
;
642 const size_t __len2
= __last2
- __first2
;
643 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
644 return __result
!= 0 ? __result
< 0 : __len1
< __len2
;
647 inline bool lexicographical_compare(const char* __first1
, const char* __last1
,
648 const char* __first2
, const char* __last2
)
650 #if CHAR_MAX == SCHAR_MAX
651 return lexicographical_compare((const signed char*) __first1
,
652 (const signed char*) __last1
,
653 (const signed char*) __first2
,
654 (const signed char*) __last2
);
655 #else /* CHAR_MAX == SCHAR_MAX */
656 return lexicographical_compare((const unsigned char*) __first1
,
657 (const unsigned char*) __last1
,
658 (const unsigned char*) __first2
,
659 (const unsigned char*) __last2
);
660 #endif /* CHAR_MAX == SCHAR_MAX */
663 template <class _InputIter1
, class _InputIter2
>
664 int __lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
665 _InputIter2 __first2
, _InputIter2 __last2
)
667 while (__first1
!= __last1
&& __first2
!= __last2
) {
668 if (*__first1
< *__first2
)
670 if (*__first2
< *__first1
)
675 if (__first2
== __last2
) {
676 return !(__first1
== __last1
);
684 __lexicographical_compare_3way(const unsigned char* __first1
,
685 const unsigned char* __last1
,
686 const unsigned char* __first2
,
687 const unsigned char* __last2
)
689 const ptrdiff_t __len1
= __last1
- __first1
;
690 const ptrdiff_t __len2
= __last2
- __first2
;
691 const int __result
= memcmp(__first1
, __first2
, min(__len1
, __len2
));
692 return __result
!= 0 ? __result
693 : (__len1
== __len2
? 0 : (__len1
< __len2
? -1 : 1));
697 __lexicographical_compare_3way(const char* __first1
, const char* __last1
,
698 const char* __first2
, const char* __last2
)
700 #if CHAR_MAX == SCHAR_MAX
701 return __lexicographical_compare_3way(
702 (const signed char*) __first1
,
703 (const signed char*) __last1
,
704 (const signed char*) __first2
,
705 (const signed char*) __last2
);
707 return __lexicographical_compare_3way((const unsigned char*) __first1
,
708 (const unsigned char*) __last1
,
709 (const unsigned char*) __first2
,
710 (const unsigned char*) __last2
);
714 template <class _InputIter1
, class _InputIter2
>
715 int lexicographical_compare_3way(_InputIter1 __first1
, _InputIter1 __last1
,
716 _InputIter2 __first2
, _InputIter2 __last2
)
718 // concept requirements
719 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter1
>);
720 __glibcpp_function_requires(_InputIteratorConcept
<_InputIter2
>);
721 __glibcpp_function_requires(_LessThanComparableConcept
<
722 typename iterator_traits
<_InputIter1
>::value_type
>);
723 __glibcpp_function_requires(_LessThanComparableConcept
<
724 typename iterator_traits
<_InputIter2
>::value_type
>);
726 return __lexicographical_compare_3way(__first1
, __last1
, __first2
, __last2
);
731 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */