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