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

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