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 iterator_traits<_ForwardIterator>::value_type _ValueType;
 550       typedef typename __type_traits<_ValueType>::has_trivial_copy_constructor
 551         _Trivial;
 552       std::__fill<_Trivial>::fill(__first, __last, __value);
 553     }
 554
 555   // Specialization: for one-byte types we can use memset.
 556   inline void
 557   fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
 558   {
 559     __glibcxx_requires_valid_range(__first, __last);
 560     const unsigned char __tmp = __c;
 561     std::memset(__first, __tmp, __last - __first);
 562   }
 563
 564   inline void
 565   fill(signed char* __first, signed char* __last, const signed char& __c)
 566   {
 567     __glibcxx_requires_valid_range(__first, __last);
 568     const signed char __tmp = __c;
 569     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
 570   }
 571
 572   inline void
 573   fill(char* __first, char* __last, const char& __c)
 574   {
 575     __glibcxx_requires_valid_range(__first, __last);
 576     const char __tmp = __c;
 577     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
 578   }
 579
 580   template<typename>
 581     struct __fill_n
 582     {
 583       template<typename _OutputIterator, typename _Size, typename _Tp>
 584         static _OutputIterator
 585         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
 586         {
 587           for (; __n > 0; --__n, ++__first)
 588             *__first = __value;
 589           return __first;
 590         }
 591     };
 592
 593   template<>
 594     struct __fill_n<__true_type>
 595     {
 596       template<typename _OutputIterator, typename _Size, typename _Tp>
 597         static _OutputIterator
 598         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
 599         {
 600           const _Tp __tmp = __value;
 601           for (; __n > 0; --__n, ++__first)
 602             *__first = __tmp;
 603           return __first;
 604         }
 605     };
 606
 607   /**
 608    *  @brief Fills the range [first,first+n) with copies of value.
 609    *  @param  first  An output iterator.
 610    *  @param  n      The count of copies to perform.
 611    *  @param  value  A reference-to-const of arbitrary type.
 612    *  @return   The iterator at first+n.
 613    *
 614    *  This function fills a range with copies of the same value.  For one-byte
 615    *  types filling contiguous areas of memory, this becomes an inline call to
 616    *  @c memset.
 617   */
 618   template<typename _OutputIterator, typename _Size, typename _Tp>
 619     _OutputIterator
 620     fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
 621     {
 622       // concept requirements
 623       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
 624
 625       typedef typename iterator_traits<_OutputIterator>::value_type _ValueType;
 626       typedef typename __type_traits<_ValueType>::has_trivial_copy_constructor
 627         _Trivial;
 628       return std::__fill_n<_Trivial>::fill_n(__first, __n, __value);
 629     }
 630
 631   template<typename _Size>
 632     inline unsigned char*
 633     fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
 634     {
 635       std::fill(__first, __first + __n, __c);
 636       return __first + __n;
 637     }
 638
 639   template<typename _Size>
 640     inline signed char*
 641     fill_n(char* __first, _Size __n, const signed char& __c)
 642     {
 643       std::fill(__first, __first + __n, __c);
 644       return __first + __n;
 645     }
 646
 647   template<typename _Size>
 648     inline char*
 649     fill_n(char* __first, _Size __n, const char& __c)
 650     {
 651       std::fill(__first, __first + __n, __c);
 652       return __first + __n;
 653     }
 654
 655   /**
 656    *  @brief Finds the places in ranges which don't match.
 657    *  @param  first1  An input iterator.
 658    *  @param  last1   An input iterator.
 659    *  @param  first2  An input iterator.
 660    *  @return   A pair of iterators pointing to the first mismatch.
 661    *
 662    *  This compares the elements of two ranges using @c == and returns a pair
 663    *  of iterators.  The first iterator points into the first range, the
 664    *  second iterator points into the second range, and the elements pointed
 665    *  to by the iterators are not equal.
 666   */
 667   template<typename _InputIterator1, typename _InputIterator2>
 668     pair<_InputIterator1, _InputIterator2>
 669     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 670              _InputIterator2 __first2)
 671     {
 672       // concept requirements
 673       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 674       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 675       __glibcxx_function_requires(_EqualityComparableConcept<
 676             typename iterator_traits<_InputIterator1>::value_type>)
 677       __glibcxx_function_requires(_EqualityComparableConcept<
 678             typename iterator_traits<_InputIterator2>::value_type>)
 679       __glibcxx_requires_valid_range(__first1, __last1);
 680
 681       while (__first1 != __last1 && *__first1 == *__first2)
 682         {
 683           ++__first1;
 684           ++__first2;
 685         }
 686       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
 687     }
 688
 689   /**
 690    *  @brief Finds the places in ranges which don't match.
 691    *  @param  first1  An input iterator.
 692    *  @param  last1   An input iterator.
 693    *  @param  first2  An input iterator.
 694    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
 695    *  @return   A pair of iterators pointing to the first mismatch.
 696    *
 697    *  This compares the elements of two ranges using the binary_pred
 698    *  parameter, and returns a pair
 699    *  of iterators.  The first iterator points into the first range, the
 700    *  second iterator points into the second range, and the elements pointed
 701    *  to by the iterators are not equal.
 702   */
 703   template<typename _InputIterator1, typename _InputIterator2,
 704            typename _BinaryPredicate>
 705     pair<_InputIterator1, _InputIterator2>
 706     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 707              _InputIterator2 __first2, _BinaryPredicate __binary_pred)
 708     {
 709       // concept requirements
 710       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 711       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 712       __glibcxx_requires_valid_range(__first1, __last1);
 713
 714       while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
 715         {
 716           ++__first1;
 717           ++__first2;
 718         }
 719       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
 720     }
 721
 722   /**
 723    *  @brief Tests a range for element-wise equality.
 724    *  @param  first1  An input iterator.
 725    *  @param  last1   An input iterator.
 726    *  @param  first2  An input iterator.
 727    *  @return   A boolean true or false.
 728    *
 729    *  This compares the elements of two ranges using @c == and returns true or
 730    *  false depending on whether all of the corresponding elements of the
 731    *  ranges are equal.
 732   */
 733   template<typename _InputIterator1, typename _InputIterator2>
 734     inline bool
 735     equal(_InputIterator1 __first1, _InputIterator1 __last1,
 736           _InputIterator2 __first2)
 737     {
 738       // concept requirements
 739       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 740       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 741       __glibcxx_function_requires(_EqualOpConcept<
 742             typename iterator_traits<_InputIterator1>::value_type,
 743             typename iterator_traits<_InputIterator2>::value_type>)
 744       __glibcxx_requires_valid_range(__first1, __last1);
 745
 746       for ( ; __first1 != __last1; ++__first1, ++__first2)
 747         if (!(*__first1 == *__first2))
 748           return false;
 749       return true;
 750     }
 751
 752   /**
 753    *  @brief Tests a range for element-wise equality.
 754    *  @param  first1  An input iterator.
 755    *  @param  last1   An input iterator.
 756    *  @param  first2  An input iterator.
 757    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
 758    *  @return   A boolean true or false.
 759    *
 760    *  This compares the elements of two ranges using the binary_pred
 761    *  parameter, and returns true or
 762    *  false depending on whether all of the corresponding elements of the
 763    *  ranges are equal.
 764   */
 765   template<typename _InputIterator1, typename _InputIterator2,
 766            typename _BinaryPredicate>
 767     inline bool
 768     equal(_InputIterator1 __first1, _InputIterator1 __last1,
 769           _InputIterator2 __first2,
 770           _BinaryPredicate __binary_pred)
 771     {
 772       // concept requirements
 773       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 774       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 775       __glibcxx_requires_valid_range(__first1, __last1);
 776
 777       for ( ; __first1 != __last1; ++__first1, ++__first2)
 778         if (!__binary_pred(*__first1, *__first2))
 779           return false;
 780       return true;
 781     }
 782
 783   /**
 784    *  @brief Performs "dictionary" comparison on ranges.
 785    *  @param  first1  An input iterator.
 786    *  @param  last1   An input iterator.
 787    *  @param  first2  An input iterator.
 788    *  @param  last2   An input iterator.
 789    *  @return   A boolean true or false.
 790    *
 791    *  "Returns true if the sequence of elements defined by the range
 792    *  [first1,last1) is lexicographically less than the sequence of elements
 793    *  defined by the range [first2,last2).  Returns false otherwise."
 794    *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
 795    *  then this is an inline call to @c memcmp.
 796   */
 797   template<typename _InputIterator1, typename _InputIterator2>
 798     bool
 799     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
 800                             _InputIterator2 __first2, _InputIterator2 __last2)
 801     {
 802       // concept requirements
 803       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 804       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 805       __glibcxx_function_requires(_LessThanComparableConcept<
 806             typename iterator_traits<_InputIterator1>::value_type>)
 807       __glibcxx_function_requires(_LessThanComparableConcept<
 808             typename iterator_traits<_InputIterator2>::value_type>)
 809       __glibcxx_requires_valid_range(__first1, __last1);
 810       __glibcxx_requires_valid_range(__first2, __last2);
 811
 812       for (;__first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
 813         {
 814           if (*__first1 < *__first2)
 815             return true;
 816           if (*__first2 < *__first1)
 817             return false;
 818         }
 819       return __first1 == __last1 && __first2 != __last2;
 820     }
 821
 822   /**
 823    *  @brief Performs "dictionary" comparison on ranges.
 824    *  @param  first1  An input iterator.
 825    *  @param  last1   An input iterator.
 826    *  @param  first2  An input iterator.
 827    *  @param  last2   An input iterator.
 828    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
 829    *  @return   A boolean true or false.
 830    *
 831    *  The same as the four-parameter @c lexigraphical_compare, but uses the
 832    *  comp parameter instead of @c <.
 833   */
 834   template<typename _InputIterator1, typename _InputIterator2,
 835            typename _Compare>
 836     bool
 837     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
 838                             _InputIterator2 __first2, _InputIterator2 __last2,
 839                             _Compare __comp)
 840     {
 841       // concept requirements
 842       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 843       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 844       __glibcxx_requires_valid_range(__first1, __last1);
 845       __glibcxx_requires_valid_range(__first2, __last2);
 846
 847       for ( ; __first1 != __last1 && __first2 != __last2
 848             ; ++__first1, ++__first2)
 849         {
 850           if (__comp(*__first1, *__first2))
 851             return true;
 852           if (__comp(*__first2, *__first1))
 853             return false;
 854         }
 855       return __first1 == __last1 && __first2 != __last2;
 856     }
 857
 858   inline bool
 859   lexicographical_compare(const unsigned char* __first1,
 860                           const unsigned char* __last1,
 861                           const unsigned char* __first2,
 862                           const unsigned char* __last2)
 863   {
 864     __glibcxx_requires_valid_range(__first1, __last1);
 865     __glibcxx_requires_valid_range(__first2, __last2);
 866
 867     const size_t __len1 = __last1 - __first1;
 868     const size_t __len2 = __last2 - __first2;
 869     const int __result = std::memcmp(__first1, __first2,
 870                                      std::min(__len1, __len2));
 871     return __result != 0 ? __result < 0 : __len1 < __len2;
 872   }
 873
 874   inline bool
 875   lexicographical_compare(const char* __first1, const char* __last1,
 876                           const char* __first2, const char* __last2)
 877   {
 878     __glibcxx_requires_valid_range(__first1, __last1);
 879     __glibcxx_requires_valid_range(__first2, __last2);
 880
 881 #if CHAR_MAX == SCHAR_MAX
 882     return std::lexicographical_compare((const signed char*) __first1,
 883                                         (const signed char*) __last1,
 884                                         (const signed char*) __first2,
 885                                         (const signed char*) __last2);
 886 #else /* CHAR_MAX == SCHAR_MAX */
 887     return std::lexicographical_compare((const unsigned char*) __first1,
 888                                         (const unsigned char*) __last1,
 889                                         (const unsigned char*) __first2,
 890                                         (const unsigned char*) __last2);
 891 #endif /* CHAR_MAX == SCHAR_MAX */
 892   }
 893
 894 } // namespace std
 895
 896 #endif