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

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