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