libstdc++-v3/include/bits/stl_algobase.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   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.
  13  *
  14  *
  15  * Copyright (c) 1996-1998
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  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.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31
  32 #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
  33 #define __SGI_STL_INTERNAL_ALGOBASE_H
  34
  35 #include <bits/c++config.h>
  36 #ifndef __SGI_STL_INTERNAL_PAIR_H
  37 #include <bits/stl_pair.h>
  38 #endif
  39 #ifndef _CPP_BITS_TYPE_TRAITS_H
  40 #include <bits/type_traits.h>
  41 #endif
  42 #include <bits/std_cstring.h>
  43 #include <bits/std_climits.h>
  44 #include <bits/std_cstdlib.h>
  45 #include <bits/std_cstddef.h>
  46 #include <new>
  47
  48 #include <bits/std_iosfwd.h>
  49 #include <bits/stl_iterator_base_types.h>
  50 #include <bits/stl_iterator_base_funcs.h>
  51 #include <bits/stl_iterator.h>
  52 #include <bits/concept_check.h>
  53
  54 namespace std
  55 {
  56
  57 // swap and iter_swap
  58
  59 template <class _ForwardIter1, class _ForwardIter2, class _Tp>
  60 inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*)
  61 {
  62   _Tp __tmp = *__a;
  63   *__a = *__b;
  64   *__b = __tmp;
  65 }
  66
  67 template <class _ForwardIter1, class _ForwardIter2>
  68 inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b)
  69 {
  70   // concept requirements
  71   glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter1>);
  72   glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter2>);
  73   glibcpp_function_requires(ConvertibleConcept<
  74         typename iterator_traits<_ForwardIter1>::value_type,
  75         typename iterator_traits<_ForwardIter2>::value_type>);
  76   glibcpp_function_requires(ConvertibleConcept<
  77         typename iterator_traits<_ForwardIter2>::value_type,
  78         typename iterator_traits<_ForwardIter1>::value_type>);
  79
  80   __iter_swap(__a, __b, __value_type(__a));
  81 }
  82
  83 template <class _Tp>
  84 inline void swap(_Tp& __a, _Tp& __b)
  85 {
  86   // concept requirements
  87   glibcpp_function_requires(SGIAssignableConcept<_Tp>);
  88
  89   _Tp __tmp = __a;
  90   __a = __b;
  91   __b = __tmp;
  92 }
  93
  94 //--------------------------------------------------
  95 // min and max
  96
  97 #undef min
  98 #undef max
  99
 100 template <class _Tp>
 101 inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
 102   // concept requirements
 103   glibcpp_function_requires(LessThanComparableConcept<_Tp>);
 104   //return __b < __a ? __b : __a;
 105   if (__b < __a) return __b; return __a;
 106 }
 107
 108 template <class _Tp>
 109 inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
 110   // concept requirements
 111   glibcpp_function_requires(LessThanComparableConcept<_Tp>);
 112   //return  __a < __b ? __b : __a;
 113   if (__a < __b) return __b; return __a;
 114 }
 115
 116 template <class _Tp, class _Compare>
 117 inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
 118   //return __comp(__b, __a) ? __b : __a;
 119   if (__comp(__b, __a)) return __b; return __a;
 120 }
 121
 122 template <class _Tp, class _Compare>
 123 inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
 124   //return __comp(__a, __b) ? __b : __a;
 125   if (__comp(__a, __b)) return __b; return __a;
 126 }
 127
 128 //--------------------------------------------------
 129 // copy
 130
 131 // All of these auxiliary functions serve two purposes.  (1) Replace
 132 // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
 133 // because the input and output ranges are permitted to overlap.)
 134 // (2) If we're using random access iterators, then write the loop as
 135 // a for loop with an explicit count.
 136
 137 template <class _InputIter, class _OutputIter, class _Distance>
 138 inline _OutputIter __copy(_InputIter __first, _InputIter __last,
 139                           _OutputIter __result,
 140                           input_iterator_tag, _Distance*)
 141 {
 142   for ( ; __first != __last; ++__result, ++__first)
 143     *__result = *__first;
 144   return __result;
 145 }
 146
 147 template <class _RandomAccessIter, class _OutputIter, class _Distance>
 148 inline _OutputIter
 149 __copy(_RandomAccessIter __first, _RandomAccessIter __last,
 150        _OutputIter __result, random_access_iterator_tag, _Distance*)
 151 {
 152   for (_Distance __n = __last - __first; __n > 0; --__n) {
 153     *__result = *__first;
 154     ++__first;
 155     ++__result;
 156   }
 157   return __result;
 158 }
 159
 160 template <class _Tp>
 161 inline _Tp*
 162 __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
 163 {
 164   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
 165   return __result + (__last - __first);
 166 }
 167
 168
 169 template <class _InputIter, class _OutputIter>
 170 inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
 171                                _OutputIter __result, __false_type)
 172 {
 173   return __copy(__first, __last, __result,
 174                 __iterator_category(__first),
 175                 __distance_type(__first));
 176 }
 177
 178 template <class _InputIter, class _OutputIter>
 179 inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
 180                                _OutputIter __result, __true_type)
 181 {
 182   return __copy(__first, __last, __result,
 183                 __iterator_category(__first),
 184                 __distance_type(__first));
 185 }
 186
 187 template <class _Tp>
 188 inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result,
 189                         __true_type)
 190 {
 191   return __copy_trivial(__first, __last, __result);
 192 }
 193
 194 template <class _Tp>
 195 inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
 196                         __true_type)
 197 {
 198   return __copy_trivial(__first, __last, __result);
 199 }
 200
 201
 202 template <class _InputIter, class _OutputIter, class _Tp>
 203 inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,
 204                               _OutputIter __result, _Tp*)
 205 {
 206   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
 207           _Trivial;
 208   return __copy_aux2(__first, __last, __result, _Trivial());
 209 }
 210
 211 template<typename _InputIter, typename _OutputIter>
 212 inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
 213                                _OutputIter __result, __true_type)
 214 {
 215   return _OutputIter(__copy_aux(__first, __last, __result.base(),
 216                                 __value_type(__first)));
 217 }
 218
 219 template<typename _InputIter, typename _OutputIter>
 220 inline _OutputIter __copy_ni2(_InputIter __first, _InputIter __last,
 221                               _OutputIter __result, __false_type)
 222 {
 223   return __copy_aux(__first, __last, __result, __value_type(__first));
 224 }
 225
 226 template<typename _InputIter, typename _OutputIter>
 227 inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
 228                                _OutputIter __result, __true_type)
 229 {
 230   typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
 231   return __copy_ni2(__first.base(), __last.base(), __result, __Normal());
 232 }
 233
 234 template<typename _InputIter, typename _OutputIter>
 235 inline _OutputIter __copy_ni1(_InputIter __first, _InputIter __last,
 236                                _OutputIter __result, __false_type)
 237 {
 238   typedef typename _Is_normal_iterator<_OutputIter>::_Normal __Normal;
 239   return __copy_ni2(__first, __last, __result, __Normal());
 240 }
 241
 242 template <class _InputIter, class _OutputIter>
 243 inline _OutputIter copy(_InputIter __first, _InputIter __last,
 244                         _OutputIter __result)
 245 {
 246   // concept requirements
 247   glibcpp_function_requires(InputIteratorConcept<_InputIter>);
 248   glibcpp_function_requires(OutputIteratorConcept<_OutputIter,
 249         typename iterator_traits<_InputIter>::value_type>);
 250
 251    typedef typename _Is_normal_iterator<_InputIter>::_Normal __Normal;
 252    return __copy_ni1(__first, __last, __result, __Normal());
 253 }
 254
 255 //--------------------------------------------------
 256 // copy_backward
 257
 258 template <class _BidirectionalIter1, class _BidirectionalIter2,
 259           class _Distance>
 260 inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
 261                                            _BidirectionalIter1 __last,
 262                                            _BidirectionalIter2 __result,
 263                                            bidirectional_iterator_tag,
 264                                            _Distance*)
 265 {
 266   while (__first != __last)
 267     *--__result = *--__last;
 268   return __result;
 269 }
 270
 271 template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
 272 inline _BidirectionalIter __copy_backward(_RandomAccessIter __first,
 273                                           _RandomAccessIter __last,
 274                                           _BidirectionalIter __result,
 275                                           random_access_iterator_tag,
 276                                           _Distance*)
 277 {
 278   for (_Distance __n = __last - __first; __n > 0; --__n)
 279     *--__result = *--__last;
 280   return __result;
 281 }
 282
 283
 284 // This dispatch class is a workaround for compilers that do not
 285 // have partial ordering of function templates.  All we're doing is
 286 // creating a specialization so that we can turn a call to copy_backward
 287 // into a memmove whenever possible.
 288
 289 template <class _BidirectionalIter1, class _BidirectionalIter2,
 290           class _BoolType>
 291 struct __copy_backward_dispatch
 292 {
 293   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category
 294           _Cat;
 295   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
 296           _Distance;
 297
 298   static _BidirectionalIter2 copy(_BidirectionalIter1 __first,
 299                                   _BidirectionalIter1 __last,
 300                                   _BidirectionalIter2 __result) {
 301     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
 302   }
 303 };
 304
 305 template <class _Tp>
 306 struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
 307 {
 308   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
 309     const ptrdiff_t _Num = __last - __first;
 310     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
 311     return __result - _Num;
 312   }
 313 };
 314
 315 template <class _Tp>
 316 struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
 317 {
 318   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
 319     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
 320       ::copy(__first, __last, __result);
 321   }
 322 };
 323
 324 template <class _BI1, class _BI2>
 325 inline _BI2 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) {
 326   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
 327                         ::has_trivial_assignment_operator
 328           _Trivial;
 329   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
 330               ::copy(__first, __last, __result);
 331 }
 332
 333 template <typename _BI1, typename _BI2>
 334 inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
 335                                                    _BI2 __result, __true_type) {
 336   return _BI2(__copy_backward_aux(__first, __last, __result.base()));
 337 }
 338
 339 template <typename _BI1, typename _BI2>
 340 inline _BI2 __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
 341                                                    _BI2 __result, __false_type){
 342   return __copy_backward_aux(__first, __last, __result);
 343 }
 344
 345 template <typename _BI1, typename _BI2>
 346 inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
 347                                                   _BI2 __result, __true_type) {
 348   typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
 349   return __copy_backward_output_normal_iterator(__first.base(), __last.base(),
 350                                                 __result, __Normal());
 351 }
 352
 353 template <typename _BI1, typename _BI2>
 354 inline _BI2 __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
 355                                                   _BI2 __result, __false_type) {
 356   typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
 357   return __copy_backward_output_normal_iterator(__first, __last, __result,
 358                                                 __Normal());
 359 }
 360
 361 template <typename _BI1, typename _BI2>
 362 inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
 363 {
 364   // concept requirements
 365   glibcpp_function_requires(BidirectionalIteratorConcept<_BI1>);
 366   glibcpp_function_requires(Mutable_BidirectionalIteratorConcept<_BI2>);
 367   glibcpp_function_requires(ConvertibleConcept<
 368         typename iterator_traits<_BI1>::value_type,
 369         typename iterator_traits<_BI2>::value_type>);
 370
 371   typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
 372   return __copy_backward_input_normal_iterator(__first, __last, __result,
 373                                                __Normal());
 374 }
 375
 376 //--------------------------------------------------
 377 // copy_n (not part of the C++ standard)
 378
 379 template <class _InputIter, class _Size, class _OutputIter>
 380 pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
 381                                        _OutputIter __result,
 382                                        input_iterator_tag) {
 383   for ( ; __count > 0; --__count) {
 384     *__result = *__first;
 385     ++__first;
 386     ++__result;
 387   }
 388   return pair<_InputIter, _OutputIter>(__first, __result);
 389 }
 390
 391 template <class _RAIter, class _Size, class _OutputIter>
 392 inline pair<_RAIter, _OutputIter>
 393 __copy_n(_RAIter __first, _Size __count,
 394          _OutputIter __result,
 395          random_access_iterator_tag) {
 396   _RAIter __last = __first + __count;
 397   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
 398 }
 399
 400 template <class _InputIter, class _Size, class _OutputIter>
 401 inline pair<_InputIter, _OutputIter>
 402 __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
 403   return __copy_n(__first, __count, __result,
 404                   __iterator_category(__first));
 405 }
 406
 407 template <class _InputIter, class _Size, class _OutputIter>
 408 inline pair<_InputIter, _OutputIter>
 409 copy_n(_InputIter __first, _Size __count, _OutputIter __result)
 410 {
 411   // concept requirements
 412   glibcpp_function_requires(InputIteratorConcept<_InputIter>);
 413   glibcpp_function_requires(OutputIteratorConcept<_OutputIter,
 414         typename iterator_traits<_InputIter>::value_type>);
 415
 416   return __copy_n(__first, __count, __result);
 417 }
 418
 419 //--------------------------------------------------
 420 // fill and fill_n
 421
 422
 423 template <class _ForwardIter, class _Tp>
 424 void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value)
 425 {
 426   // concept requirements
 427   glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>);
 428
 429   for ( ; __first != __last; ++__first)
 430     *__first = __value;
 431 }
 432
 433 template <class _OutputIter, class _Size, class _Tp>
 434 _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
 435 {
 436   // concept requirements
 437   glibcpp_function_requires(OutputIteratorConcept<_OutputIter,_Tp>);
 438
 439   for ( ; __n > 0; --__n, ++__first)
 440     *__first = __value;
 441   return __first;
 442 }
 443
 444 // Specialization: for one-byte types we can use memset.
 445
 446 inline void fill(unsigned char* __first, unsigned char* __last,
 447                  const unsigned char& __c)
 448 {
 449   unsigned char __tmp = __c;
 450   memset(__first, __tmp, __last - __first);
 451 }
 452
 453 inline void fill(signed char* __first, signed char* __last,
 454                  const signed char& __c)
 455 {
 456   signed char __tmp = __c;
 457   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
 458 }
 459
 460 inline void fill(char* __first, char* __last, const char& __c)
 461 {
 462   char __tmp = __c;
 463   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
 464 }
 465
 466 template <class _Size>
 467 inline unsigned char* fill_n(unsigned char* __first, _Size __n,
 468                              const unsigned char& __c)
 469 {
 470   fill(__first, __first + __n, __c);
 471   return __first + __n;
 472 }
 473
 474 template <class _Size>
 475 inline signed char* fill_n(char* __first, _Size __n,
 476                            const signed char& __c)
 477 {
 478   fill(__first, __first + __n, __c);
 479   return __first + __n;
 480 }
 481
 482 template <class _Size>
 483 inline char* fill_n(char* __first, _Size __n, const char& __c)
 484 {
 485   fill(__first, __first + __n, __c);
 486   return __first + __n;
 487 }
 488
 489
 490 //--------------------------------------------------
 491 // equal and mismatch
 492
 493 template <class _InputIter1, class _InputIter2>
 494 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
 495                                         _InputIter1 __last1,
 496                                         _InputIter2 __first2)
 497 {
 498   // concept requirements
 499   glibcpp_function_requires(InputIteratorConcept<_InputIter1>);
 500   glibcpp_function_requires(InputIteratorConcept<_InputIter2>);
 501   glibcpp_function_requires(EqualityComparableConcept<
 502         typename iterator_traits<_InputIter1>::value_type>);
 503   glibcpp_function_requires(EqualityComparableConcept<
 504         typename iterator_traits<_InputIter2>::value_type>);
 505
 506   while (__first1 != __last1 && *__first1 == *__first2) {
 507     ++__first1;
 508     ++__first2;
 509   }
 510   return pair<_InputIter1, _InputIter2>(__first1, __first2);
 511 }
 512
 513 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
 514 pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
 515                                         _InputIter1 __last1,
 516                                         _InputIter2 __first2,
 517                                         _BinaryPredicate __binary_pred)
 518 {
 519   // concept requirements
 520   glibcpp_function_requires(InputIteratorConcept<_InputIter1>);
 521   glibcpp_function_requires(InputIteratorConcept<_InputIter2>);
 522
 523   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
 524     ++__first1;
 525     ++__first2;
 526   }
 527   return pair<_InputIter1, _InputIter2>(__first1, __first2);
 528 }
 529
 530 template <class _InputIter1, class _InputIter2>
 531 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
 532                   _InputIter2 __first2)
 533 {
 534   // concept requirements
 535   glibcpp_function_requires(InputIteratorConcept<_InputIter1>);
 536   glibcpp_function_requires(InputIteratorConcept<_InputIter2>);
 537   glibcpp_function_requires(EqualityComparableConcept<
 538         typename iterator_traits<_InputIter1>::value_type>);
 539   glibcpp_function_requires(EqualityComparableConcept<
 540         typename iterator_traits<_InputIter2>::value_type>);
 541
 542   for ( ; __first1 != __last1; ++__first1, ++__first2)
 543     if (!(*__first1 == *__first2))
 544       return false;
 545   return true;
 546 }
 547
 548 template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
 549 inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
 550                   _InputIter2 __first2, _BinaryPredicate __binary_pred)
 551 {
 552   // concept requirements
 553   glibcpp_function_requires(InputIteratorConcept<_InputIter1>);
 554   glibcpp_function_requires(InputIteratorConcept<_InputIter2>);
 555
 556   for ( ; __first1 != __last1; ++__first1, ++__first2)
 557     if (!__binary_pred(*__first1, *__first2))
 558       return false;
 559   return true;
 560 }
 561
 562 //--------------------------------------------------
 563 // lexicographical_compare and lexicographical_compare_3way.
 564 // (the latter is not part of the C++ standard.)
 565
 566 template <class _InputIter1, class _InputIter2>
 567 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
 568                              _InputIter2 __first2, _InputIter2 __last2)
 569 {
 570   // concept requirements
 571   glibcpp_function_requires(InputIteratorConcept<_InputIter1>);
 572   glibcpp_function_requires(InputIteratorConcept<_InputIter2>);
 573   glibcpp_function_requires(LessThanComparableConcept<
 574         typename iterator_traits<_InputIter1>::value_type>);
 575   glibcpp_function_requires(LessThanComparableConcept<
 576         typename iterator_traits<_InputIter2>::value_type>);
 577
 578   for ( ; __first1 != __last1 && __first2 != __last2
 579         ; ++__first1, ++__first2) {
 580     if (*__first1 < *__first2)
 581       return true;
 582     if (*__first2 < *__first1)
 583       return false;
 584   }
 585   return __first1 == __last1 && __first2 != __last2;
 586 }
 587
 588 template <class _InputIter1, class _InputIter2, class _Compare>
 589 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
 590                              _InputIter2 __first2, _InputIter2 __last2,
 591                              _Compare __comp)
 592 {
 593   // concept requirements
 594   glibcpp_function_requires(InputIteratorConcept<_InputIter1>);
 595   glibcpp_function_requires(InputIteratorConcept<_InputIter2>);
 596
 597   for ( ; __first1 != __last1 && __first2 != __last2
 598         ; ++__first1, ++__first2) {
 599     if (__comp(*__first1, *__first2))
 600       return true;
 601     if (__comp(*__first2, *__first1))
 602       return false;
 603   }
 604   return __first1 == __last1 && __first2 != __last2;
 605 }
 606
 607 inline bool
 608 lexicographical_compare(const unsigned char* __first1,
 609                         const unsigned char* __last1,
 610                         const unsigned char* __first2,
 611                         const unsigned char* __last2)
 612 {
 613   const size_t __len1 = __last1 - __first1;
 614   const size_t __len2 = __last2 - __first2;
 615   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
 616   return __result != 0 ? __result < 0 : __len1 < __len2;
 617 }
 618
 619 inline bool lexicographical_compare(const char* __first1, const char* __last1,
 620                                     const char* __first2, const char* __last2)
 621 {
 622 #if CHAR_MAX == SCHAR_MAX
 623   return lexicographical_compare((const signed char*) __first1,
 624                                  (const signed char*) __last1,
 625                                  (const signed char*) __first2,
 626                                  (const signed char*) __last2);
 627 #else /* CHAR_MAX == SCHAR_MAX */
 628   return lexicographical_compare((const unsigned char*) __first1,
 629                                  (const unsigned char*) __last1,
 630                                  (const unsigned char*) __first2,
 631                                  (const unsigned char*) __last2);
 632 #endif /* CHAR_MAX == SCHAR_MAX */
 633 }
 634
 635 template <class _InputIter1, class _InputIter2>
 636 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 637                                    _InputIter2 __first2, _InputIter2 __last2)
 638 {
 639   while (__first1 != __last1 && __first2 != __last2) {
 640     if (*__first1 < *__first2)
 641       return -1;
 642     if (*__first2 < *__first1)
 643       return 1;
 644     ++__first1;
 645     ++__first2;
 646   }
 647   if (__first2 == __last2) {
 648     return !(__first1 == __last1);
 649   }
 650   else {
 651     return -1;
 652   }
 653 }
 654
 655 inline int
 656 __lexicographical_compare_3way(const unsigned char* __first1,
 657                                const unsigned char* __last1,
 658                                const unsigned char* __first2,
 659                                const unsigned char* __last2)
 660 {
 661   const ptrdiff_t __len1 = __last1 - __first1;
 662   const ptrdiff_t __len2 = __last2 - __first2;
 663   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
 664   return __result != 0 ? __result
 665                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
 666 }
 667
 668 inline int
 669 __lexicographical_compare_3way(const char* __first1, const char* __last1,
 670                                const char* __first2, const char* __last2)
 671 {
 672 #if CHAR_MAX == SCHAR_MAX
 673   return __lexicographical_compare_3way(
 674                                 (const signed char*) __first1,
 675                                 (const signed char*) __last1,
 676                                 (const signed char*) __first2,
 677                                 (const signed char*) __last2);
 678 #else
 679   return __lexicographical_compare_3way((const unsigned char*) __first1,
 680                                         (const unsigned char*) __last1,
 681                                         (const unsigned char*) __first2,
 682                                         (const unsigned char*) __last2);
 683 #endif
 684 }
 685
 686 template <class _InputIter1, class _InputIter2>
 687 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
 688                                  _InputIter2 __first2, _InputIter2 __last2)
 689 {
 690   // concept requirements
 691   glibcpp_function_requires(InputIteratorConcept<_InputIter1>);
 692   glibcpp_function_requires(InputIteratorConcept<_InputIter2>);
 693   glibcpp_function_requires(LessThanComparableConcept<
 694         typename iterator_traits<_InputIter1>::value_type>);
 695   glibcpp_function_requires(LessThanComparableConcept<
 696         typename iterator_traits<_InputIter2>::value_type>);
 697
 698   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
 699 }
 700
 701 } // namespace std
 702
 703 #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
 704
 705 // Local Variables:
 706 // mode:C++
 707 // End: