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

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