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