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