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