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

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