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