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