1 // Bits and pieces used in algorithms -*- C++ -*-
3 // Copyright (C) 2001, 2002 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 /** @file stl_algobase.h
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
61 #ifndef __GLIBCPP_INTERNAL_ALGOBASE_H
62 #define __GLIBCPP_INTERNAL_ALGOBASE_H
64 #include <bits/c++config.h>
71 #include <bits/stl_pair.h>
72 #include <bits/type_traits.h>
73 #include <bits/stl_iterator_base_types.h>
74 #include <bits/stl_iterator_base_funcs.h>
75 #include <bits/stl_iterator.h>
76 #include <bits/concept_check.h>
83 * @brief Swaps the contents of two iterators.
84 * @param a An iterator.
85 * @param b Another iterator.
88 * This function swaps the values pointed to by two iterators, not the
89 * iterators themselves.
91 template<typename _ForwardIter1, typename _ForwardIter2>
93 iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)
95 typedef typename iterator_traits<_ForwardIter1>::value_type _ValueType1;
96 typedef typename iterator_traits<_ForwardIter2>::value_type _ValueType2;
98 // concept requirements
99 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>)
100 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>)
101 __glibcpp_function_requires(_ConvertibleConcept<_ValueType1, _ValueType2>)
102 __glibcpp_function_requires(_ConvertibleConcept<_ValueType2, _ValueType1>)
104 _ValueType1 __tmp = *__a;
110 * @brief Swaps two values.
111 * @param a A thing of arbitrary type.
112 * @param b Another thing of arbitrary type.
115 * This is the simple classic generic implementation. It will work on
116 * any type which has a copy constructor and an assignment operator.
118 template<typename _Tp>
120 swap(_Tp& __a, _Tp& __b)
122 // concept requirements
123 __glibcpp_function_requires(_SGIAssignableConcept<_Tp>)
130 //--------------------------------------------------
137 * @brief This does what you think it does.
138 * @param a A thing of arbitrary type.
139 * @param b Another thing of arbitrary type.
140 * @return The lesser of the parameters.
142 * This is the simple classic generic implementation. It will work on
143 * temporary expressions, since they are only evaluated once, unlike a
144 * preprocessor macro.
146 template<typename _Tp>
148 min(const _Tp& __a, const _Tp& __b)
150 // concept requirements
151 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
152 //return __b < __a ? __b : __a;
153 if (__b < __a) return __b; return __a;
157 * @brief This does what you think it does.
158 * @param a A thing of arbitrary type.
159 * @param b Another thing of arbitrary type.
160 * @return The greater of the parameters.
162 * This is the simple classic generic implementation. It will work on
163 * temporary expressions, since they are only evaluated once, unlike a
164 * preprocessor macro.
166 template<typename _Tp>
168 max(const _Tp& __a, const _Tp& __b)
170 // concept requirements
171 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
172 //return __a < __b ? __b : __a;
173 if (__a < __b) return __b; return __a;
177 * @brief This does what you think it does.
178 * @param a A thing of arbitrary type.
179 * @param b Another thing of arbitrary type.
180 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
181 * @return The lesser of the parameters.
183 * This will work on temporary expressions, since they are only evaluated
184 * once, unlike a preprocessor macro.
186 template<typename _Tp, typename _Compare>
188 min(const _Tp& __a, const _Tp& __b, _Compare __comp)
190 //return __comp(__b, __a) ? __b : __a;
191 if (__comp(__b, __a)) return __b; return __a;
195 * @brief This does what you think it does.
196 * @param a A thing of arbitrary type.
197 * @param b Another thing of arbitrary type.
198 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
199 * @return The greater of the parameters.
201 * This will work on temporary expressions, since they are only evaluated
202 * once, unlike a preprocessor macro.
204 template<typename _Tp, typename _Compare>
206 max(const _Tp& __a, const _Tp& __b, _Compare __comp)
208 //return __comp(__a, __b) ? __b : __a;
209 if (__comp(__a, __b)) return __b; return __a;
212 //--------------------------------------------------
215 // All of these auxiliary functions serve two purposes. (1) Replace
216 // calls to copy with memmove whenever possible. (Memmove, not memcpy,
217 // because the input and output ranges are permitted to overlap.)
218 // (2) If we're using random access iterators, then write the loop as
219 // a for loop with an explicit count.
221 template<typename _InputIter, typename _OutputIter>
223 __copy(_InputIter __first, _InputIter __last,
224 _OutputIter __result,
227 for ( ; __first != __last; ++__result, ++__first)
228 *__result = *__first;
232 template<typename _RandomAccessIter, typename _OutputIter>
234 __copy(_RandomAccessIter __first, _RandomAccessIter __last,
235 _OutputIter __result,
236 random_access_iterator_tag)
238 typedef typename iterator_traits<_RandomAccessIter>::difference_type
240 for (_Distance __n = __last - __first; __n > 0; --__n) {
241 *__result = *__first;
248 template<typename _Tp>
250 __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
252 memmove(__result, __first, sizeof(_Tp) * (__last - __first));
253 return __result + (__last - __first);
256 template<typename _InputIter, typename _OutputIter>
258 __copy_aux2(_InputIter __first, _InputIter __last,
259 _OutputIter __result, __false_type)
260 { return __copy(__first, __last, __result, __iterator_category(__first)); }
262 template<typename _InputIter, typename _OutputIter>
264 __copy_aux2(_InputIter __first, _InputIter __last,
265 _OutputIter __result, __true_type)
266 { return __copy(__first, __last, __result, __iterator_category(__first)); }
268 template<typename _Tp>
270 __copy_aux2(_Tp* __first, _Tp* __last,
271 _Tp* __result, __true_type)
272 { return __copy_trivial(__first, __last, __result); }
274 template<typename _Tp>
276 __copy_aux2(const _Tp* __first, const _Tp* __last,
277 _Tp* __result, __true_type)
278 { return __copy_trivial(__first, __last, __result); }
280 template<typename _InputIter, typename _OutputIter>
282 __copy_ni2(_InputIter __first, _InputIter __last,
283 _OutputIter __result, __true_type)
285 typedef typename iterator_traits<_InputIter>::value_type
287 typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator
289 return _OutputIter(__copy_aux2(__first, __last,
294 template<typename _InputIter, typename _OutputIter>
296 __copy_ni2(_InputIter __first, _InputIter __last,
297 _OutputIter __result, __false_type)
299 typedef typename iterator_traits<_InputIter>::value_type
301 typedef typename __type_traits<_ValueType>::has_trivial_assignment_operator
303 return __copy_aux2(__first, __last,
308 template<typename _InputIter, typename _OutputIter>
310 __copy_ni1(_InputIter __first, _InputIter __last,
311 _OutputIter __result, __true_type)
313 typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
314 return __copy_ni2(__first.base(), __last.base(), __result, __Normal());
317 template<typename _InputIter, typename _OutputIter>
319 __copy_ni1(_InputIter __first, _InputIter __last,
320 _OutputIter __result, __false_type)
322 typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
323 return __copy_ni2(__first, __last, __result, __Normal());
327 * @brief Copies the range [first,last) into result.
328 * @param first An input iterator.
329 * @param last An input iterator.
330 * @param result An output iterator.
331 * @return result + (first - last)
333 * This inline function will boil down to a call to @c memmove whenever
334 * possible. Failing that, if random access iterators are passed, then the
335 * loop count will be known (and therefore a candidate for compiler
336 * optimizations such as unrolling). If the input range and the output
337 * range overlap, then the copy_backward function should be used instead.
339 template<typename _InputIter, typename _OutputIter>
341 copy(_InputIter __first, _InputIter __last, _OutputIter __result)
343 // concept requirements
344 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>)
345 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,
346 typename iterator_traits<_InputIter>::value_type>)
348 typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal;
349 return __copy_ni1(__first, __last, __result, __Normal());
352 //--------------------------------------------------
355 template<typename _BidirectionalIter1, typename _BidirectionalIter2>
356 inline _BidirectionalIter2
357 __copy_backward(_BidirectionalIter1 __first, _BidirectionalIter1 __last,
358 _BidirectionalIter2 __result,
359 bidirectional_iterator_tag)
361 while (__first != __last)
362 *--__result = *--__last;
366 template<typename _RandomAccessIter, typename _BidirectionalIter>
367 inline _BidirectionalIter
368 __copy_backward(_RandomAccessIter __first, _RandomAccessIter __last,
369 _BidirectionalIter __result,
370 random_access_iterator_tag)
372 typename iterator_traits<_RandomAccessIter>::difference_type __n;
373 for (__n = __last - __first; __n > 0; --__n)
374 *--__result = *--__last;
379 // This dispatch class is a workaround for compilers that do not
380 // have partial ordering of function templates. All we're doing is
381 // creating a specialization so that we can turn a call to copy_backward
382 // into a memmove whenever possible.
384 template<typename _BidirectionalIter1, typename _BidirectionalIter2,
386 struct __copy_backward_dispatch
388 static _BidirectionalIter2
389 copy(_BidirectionalIter1 __first, _BidirectionalIter1 __last,
390 _BidirectionalIter2 __result)
392 return __copy_backward(__first, __last,
394 __iterator_category(__first));
398 template<typename _Tp>
399 struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
402 copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
404 const ptrdiff_t _Num = __last - __first;
405 memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
406 return __result - _Num;
410 template<typename _Tp>
411 struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
414 copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
416 return __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
417 ::copy(__first, __last, __result);
421 template<typename _BI1, typename _BI2>
423 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
425 typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
426 ::has_trivial_assignment_operator _Trivial;
427 return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
428 ::copy(__first, __last, __result);
431 template <typename _BI1, typename _BI2>
433 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
434 _BI2 __result, __true_type)
435 { return _BI2(__copy_backward_aux(__first, __last, __result.base())); }
437 template <typename _BI1, typename _BI2>
439 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
440 _BI2 __result, __false_type)
441 { return __copy_backward_aux(__first, __last, __result); }
443 template <typename _BI1, typename _BI2>
445 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
446 _BI2 __result, __true_type)
448 typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
449 return __copy_backward_output_normal_iterator(__first.base(), __last.base(),
450 __result, __Normal());
453 template <typename _BI1, typename _BI2>
455 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
456 _BI2 __result, __false_type)
458 typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
459 return __copy_backward_output_normal_iterator(__first, __last, __result,
464 * @brief Copies the range [first,last) into result.
465 * @param first An input iterator.
466 * @param last An input iterator.
467 * @param result An output iterator.
468 * @return result - (first - last)
470 * The function has the same effect as copy, but starts at the end of the
471 * range and works its way to the start, returning the start of the result.
472 * This inline function will boil down to a call to @c memmove whenever
473 * possible. Failing that, if random access iterators are passed, then the
474 * loop count will be known (and therefore a candidate for compiler
475 * optimizations such as unrolling).
477 template <typename _BI1, typename _BI2>
479 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
481 // concept requirements
482 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BI1>)
483 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
484 __glibcpp_function_requires(_ConvertibleConcept<
485 typename iterator_traits<_BI1>::value_type,
486 typename iterator_traits<_BI2>::value_type>)
488 typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
489 return __copy_backward_input_normal_iterator(__first, __last, __result,
494 //--------------------------------------------------
499 * @brief Fills the range [first,last) with copies of value.
500 * @param first A forward iterator.
501 * @param last A forward iterator.
502 * @param value A reference-to-const of arbitrary type.
505 * This function fills a range with copies of the same value. For one-byte
506 * types filling contiguous areas of memory, this becomes an inline call to
509 template<typename _ForwardIter, typename _Tp>
511 fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
513 // concept requirements
514 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>)
516 for ( ; __first != __last; ++__first)
521 * @brief Fills the range [first,first+n) with copies of value.
522 * @param first An output iterator.
523 * @param n The count of copies to perform.
524 * @param value A reference-to-const of arbitrary type.
525 * @return The iterator at first+n.
527 * This function fills a range with copies of the same value. For one-byte
528 * types filling contiguous areas of memory, this becomes an inline call to
531 template<typename _OutputIter, typename _Size, typename _Tp>
533 fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
535 // concept requirements
536 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter,_Tp>)
538 for ( ; __n > 0; --__n, ++__first)
543 // Specialization: for one-byte types we can use memset.
546 fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
548 unsigned char __tmp = __c;
549 memset(__first, __tmp, __last - __first);
553 fill(signed char* __first, signed char* __last, const signed char& __c)
555 signed char __tmp = __c;
556 memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
560 fill(char* __first, char* __last, const char& __c)
563 memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
566 template<typename _Size>
567 inline unsigned char*
568 fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
570 fill(__first, __first + __n, __c);
571 return __first + __n;
574 template<typename _Size>
576 fill_n(char* __first, _Size __n, const signed char& __c)
578 fill(__first, __first + __n, __c);
579 return __first + __n;
582 template<typename _Size>
584 fill_n(char* __first, _Size __n, const char& __c)
586 fill(__first, __first + __n, __c);
587 return __first + __n;
591 //--------------------------------------------------
592 // equal and mismatch
595 * @brief Finds the places in ranges which don't match.
596 * @param first1 An input iterator.
597 * @param last1 An input iterator.
598 * @param first2 An input iterator.
599 * @return A pair of iterators pointing to the first mismatch.
601 * This compares the elements of two ranges using @c == and returns a pair
602 * of iterators. The first iterator points into the first range, the
603 * second iterator points into the second range, and the elements pointed
604 * to by the iterators are not equal.
606 template<typename _InputIter1, typename _InputIter2>
607 pair<_InputIter1, _InputIter2>
608 mismatch(_InputIter1 __first1, _InputIter1 __last1,
609 _InputIter2 __first2)
611 // concept requirements
612 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
613 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
614 __glibcpp_function_requires(_EqualityComparableConcept<
615 typename iterator_traits<_InputIter1>::value_type>)
616 __glibcpp_function_requires(_EqualityComparableConcept<
617 typename iterator_traits<_InputIter2>::value_type>)
619 while (__first1 != __last1 && *__first1 == *__first2) {
623 return pair<_InputIter1, _InputIter2>(__first1, __first2);
627 * @brief Finds the places in ranges which don't match.
628 * @param first1 An input iterator.
629 * @param last1 An input iterator.
630 * @param first2 An input iterator.
631 * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
632 * @return A pair of iterators pointing to the first mismatch.
634 * This compares the elements of two ranges using the binary_pred
635 * parameter, and returns a pair
636 * of iterators. The first iterator points into the first range, the
637 * second iterator points into the second range, and the elements pointed
638 * to by the iterators are not equal.
640 template<typename _InputIter1, typename _InputIter2, typename _BinaryPredicate>
641 pair<_InputIter1, _InputIter2>
642 mismatch(_InputIter1 __first1, _InputIter1 __last1,
643 _InputIter2 __first2,
644 _BinaryPredicate __binary_pred)
646 // concept requirements
647 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
648 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
650 while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
654 return pair<_InputIter1, _InputIter2>(__first1, __first2);
658 * @brief Tests a range for element-wise equality.
659 * @param first1 An input iterator.
660 * @param last1 An input iterator.
661 * @param first2 An input iterator.
662 * @return A boolean true or false.
664 * This compares the elements of two ranges using @c == and returns true or
665 * false depending on whether all of the corresponding elements of the
668 template<typename _InputIter1, typename _InputIter2>
670 equal(_InputIter1 __first1, _InputIter1 __last1,
671 _InputIter2 __first2)
673 // concept requirements
674 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
675 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
676 __glibcpp_function_requires(_EqualOpConcept<
677 typename iterator_traits<_InputIter1>::value_type,
678 typename iterator_traits<_InputIter2>::value_type>)
680 for ( ; __first1 != __last1; ++__first1, ++__first2)
681 if (!(*__first1 == *__first2))
687 * @brief Tests a range for element-wise equality.
688 * @param first1 An input iterator.
689 * @param last1 An input iterator.
690 * @param first2 An input iterator.
691 * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink.
692 * @return A boolean true or false.
694 * This compares the elements of two ranges using the binary_pred
695 * parameter, and returns true or
696 * false depending on whether all of the corresponding elements of the
699 template<typename _InputIter1, typename _InputIter2, typename _BinaryPredicate>
701 equal(_InputIter1 __first1, _InputIter1 __last1,
702 _InputIter2 __first2,
703 _BinaryPredicate __binary_pred)
705 // concept requirements
706 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
707 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
709 for ( ; __first1 != __last1; ++__first1, ++__first2)
710 if (!__binary_pred(*__first1, *__first2))
715 //--------------------------------------------------
716 // lexicographical_compare
719 * @brief Performs "dictionary" comparison on ranges.
720 * @param first1 An input iterator.
721 * @param last1 An input iterator.
722 * @param first2 An input iterator.
723 * @param last2 An input iterator.
724 * @return A boolean true or false.
726 * "Returns true if the sequence of elements defined by the range
727 * [first1,last1) is lexicographically less than the sequence of elements
728 * defined by the range [first2,last2). Returns false otherwise."
729 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers,
730 * then this is an inline call to @c memcmp.
732 template<typename _InputIter1, typename _InputIter2>
734 lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
735 _InputIter2 __first2, _InputIter2 __last2)
737 // concept requirements
738 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
739 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
740 __glibcpp_function_requires(_LessThanComparableConcept<
741 typename iterator_traits<_InputIter1>::value_type>)
742 __glibcpp_function_requires(_LessThanComparableConcept<
743 typename iterator_traits<_InputIter2>::value_type>)
745 for ( ; __first1 != __last1 && __first2 != __last2
746 ; ++__first1, ++__first2) {
747 if (*__first1 < *__first2)
749 if (*__first2 < *__first1)
752 return __first1 == __last1 && __first2 != __last2;
756 * @brief Performs "dictionary" comparison on ranges.
757 * @param first1 An input iterator.
758 * @param last1 An input iterator.
759 * @param first2 An input iterator.
760 * @param last2 An input iterator.
761 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
762 * @return A boolean true or false.
764 * The same as the four-parameter @c lexigraphical_compare, but uses the
765 * comp parameter instead of @c <.
767 template<typename _InputIter1, typename _InputIter2, typename _Compare>
769 lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
770 _InputIter2 __first2, _InputIter2 __last2,
773 // concept requirements
774 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>)
775 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>)
777 for ( ; __first1 != __last1 && __first2 != __last2
778 ; ++__first1, ++__first2) {
779 if (__comp(*__first1, *__first2))
781 if (__comp(*__first2, *__first1))
784 return __first1 == __last1 && __first2 != __last2;
788 lexicographical_compare(const unsigned char* __first1, const unsigned char* __last1,
789 const unsigned char* __first2, const unsigned char* __last2)
791 const size_t __len1 = __last1 - __first1;
792 const size_t __len2 = __last2 - __first2;
793 const int __result = memcmp(__first1, __first2, min(__len1, __len2));
794 return __result != 0 ? __result < 0 : __len1 < __len2;
798 lexicographical_compare(const char* __first1, const char* __last1,
799 const char* __first2, const char* __last2)
801 #if CHAR_MAX == SCHAR_MAX
802 return lexicographical_compare((const signed char*) __first1,
803 (const signed char*) __last1,
804 (const signed char*) __first2,
805 (const signed char*) __last2);
806 #else /* CHAR_MAX == SCHAR_MAX */
807 return lexicographical_compare((const unsigned char*) __first1,
808 (const unsigned char*) __last1,
809 (const unsigned char*) __first2,
810 (const unsigned char*) __last2);
811 #endif /* CHAR_MAX == SCHAR_MAX */
816 #endif /* __GLIBCPP_INTERNAL_ALGOBASE_H */