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

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