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

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