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

   1 // Bits and pieces used in algorithms -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  *
  45  * Copyright (c) 1996-1998
  46  * Silicon Graphics Computer Systems, Inc.
  47  *
  48  * Permission to use, copy, modify, distribute and sell this software
  49  * and its documentation for any purpose is hereby granted without fee,
  50  * provided that the above copyright notice appear in all copies and
  51  * that both that copyright notice and this permission notice appear
  52  * in supporting documentation.  Silicon Graphics makes no
  53  * representations about the suitability of this software for any
  54  * purpose.  It is provided "as is" without express or implied warranty.
  55  */
  56
  57 /** @file stl_algobase.h
  58  *  This is an internal header file, included by other library headers.
  59  *  You should not attempt to use it directly.
  60  */
  61
  62 #ifndef _ALGOBASE_H
  63 #define _ALGOBASE_H 1
  64
  65 #include <bits/c++config.h>
  66 #include <cstddef>
  67 #include <bits/functexcept.h>
  68 #include <bits/stl_pair.h>
  69 #include <bits/cpp_type_traits.h>
  70 #include <ext/type_traits.h>
  71 #include <ext/numeric_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   /**
 169    *  @brief Swap the elements of two sequences.
 170    *  @param  first1  A forward iterator.
 171    *  @param  last1   A forward iterator.
 172    *  @param  first2  A forward iterator.
 173    *  @return   An iterator equal to @p first2+(last1-first1).
 174    *
 175    *  Swaps each element in the range @p [first1,last1) with the
 176    *  corresponding element in the range @p [first2,(last1-first1)).
 177    *  The ranges must not overlap.
 178   */
 179   template<typename _ForwardIterator1, typename _ForwardIterator2>
 180     _ForwardIterator2
 181     swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 182                 _ForwardIterator2 __first2)
 183     {
 184       // concept requirements
 185       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 186                                   _ForwardIterator1>)
 187       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 188                                   _ForwardIterator2>)
 189       __glibcxx_function_requires(_ConvertibleConcept<
 190             typename iterator_traits<_ForwardIterator1>::value_type,
 191             typename iterator_traits<_ForwardIterator2>::value_type>)
 192       __glibcxx_function_requires(_ConvertibleConcept<
 193             typename iterator_traits<_ForwardIterator2>::value_type,
 194             typename iterator_traits<_ForwardIterator1>::value_type>)
 195       __glibcxx_requires_valid_range(__first1, __last1);
 196
 197       for (; __first1 != __last1; ++__first1, ++__first2)
 198         std::iter_swap(__first1, __first2);
 199       return __first2;
 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    *  @return   The lesser of the parameters.
 207    *
 208    *  This is the simple classic generic implementation.  It will work on
 209    *  temporary expressions, since they are only evaluated once, unlike a
 210    *  preprocessor macro.
 211   */
 212   template<typename _Tp>
 213     inline const _Tp&
 214     min(const _Tp& __a, const _Tp& __b)
 215     {
 216       // concept requirements
 217       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
 218       //return __b < __a ? __b : __a;
 219       if (__b < __a)
 220         return __b;
 221       return __a;
 222     }
 223
 224   /**
 225    *  @brief This does what you think it does.
 226    *  @param  a  A thing of arbitrary type.
 227    *  @param  b  Another thing of arbitrary type.
 228    *  @return   The greater of the parameters.
 229    *
 230    *  This is the simple classic generic implementation.  It will work on
 231    *  temporary expressions, since they are only evaluated once, unlike a
 232    *  preprocessor macro.
 233   */
 234   template<typename _Tp>
 235     inline const _Tp&
 236     max(const _Tp& __a, const _Tp& __b)
 237     {
 238       // concept requirements
 239       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
 240       //return  __a < __b ? __b : __a;
 241       if (__a < __b)
 242         return __b;
 243       return __a;
 244     }
 245
 246   /**
 247    *  @brief This does what you think it does.
 248    *  @param  a  A thing of arbitrary type.
 249    *  @param  b  Another thing of arbitrary type.
 250    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
 251    *  @return   The lesser of the parameters.
 252    *
 253    *  This will work on temporary expressions, since they are only evaluated
 254    *  once, unlike a preprocessor macro.
 255   */
 256   template<typename _Tp, typename _Compare>
 257     inline const _Tp&
 258     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
 259     {
 260       //return __comp(__b, __a) ? __b : __a;
 261       if (__comp(__b, __a))
 262         return __b;
 263       return __a;
 264     }
 265
 266   /**
 267    *  @brief This does what you think it does.
 268    *  @param  a  A thing of arbitrary type.
 269    *  @param  b  Another thing of arbitrary type.
 270    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
 271    *  @return   The greater of the parameters.
 272    *
 273    *  This will work on temporary expressions, since they are only evaluated
 274    *  once, unlike a preprocessor macro.
 275   */
 276   template<typename _Tp, typename _Compare>
 277     inline const _Tp&
 278     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
 279     {
 280       //return __comp(__a, __b) ? __b : __a;
 281       if (__comp(__a, __b))
 282         return __b;
 283       return __a;
 284     }
 285
 286
 287   // If _Iterator is a __normal_iterator return its base (a plain pointer,
 288   // normally) otherwise return it untouched.  See copy, fill, ...
 289   template<typename _Iterator,
 290            bool _BoolType = __is_normal_iterator<_Iterator>::__value>
 291     struct __niter_base
 292     {
 293       static const _Iterator&
 294       __b(const _Iterator& __it)
 295       { return __it; }
 296     };
 297
 298   template<typename _Iterator>
 299     struct __niter_base<_Iterator, true>
 300     {
 301       static const typename _Iterator::_Iterator_type&
 302       __b(const _Iterator& __it)
 303       { return __it.base(); }
 304     };
 305
 306   // All of these auxiliary structs serve two purposes.  (1) Replace
 307   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
 308   // because the input and output ranges are permitted to overlap.)
 309   // (2) If we're using random access iterators, then write the loop as
 310   // a for loop with an explicit count.
 311
 312   template<bool, typename>
 313     struct __copy
 314     {
 315       template<typename _II, typename _OI>
 316         static _OI
 317         copy(_II __first, _II __last, _OI __result)
 318         {
 319           for (; __first != __last; ++__result, ++__first)
 320             *__result = *__first;
 321           return __result;
 322         }
 323     };
 324
 325   template<bool _BoolType>
 326     struct __copy<_BoolType, random_access_iterator_tag>
 327     {
 328       template<typename _II, typename _OI>
 329         static _OI
 330         copy(_II __first, _II __last, _OI __result)
 331         {
 332           typedef typename iterator_traits<_II>::difference_type _Distance;
 333           for(_Distance __n = __last - __first; __n > 0; --__n)
 334             {
 335               *__result = *__first;
 336               ++__first;
 337               ++__result;
 338             }
 339           return __result;
 340         }
 341     };
 342
 343   template<>
 344     struct __copy<true, random_access_iterator_tag>
 345     {
 346       template<typename _Tp>
 347         static _Tp*
 348         copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
 349         {
 350           __builtin_memmove(__result, __first,
 351                             sizeof(_Tp) * (__last - __first));
 352           return __result + (__last - __first);
 353         }
 354     };
 355
 356   template<typename _II, typename _OI>
 357     inline _OI
 358     __copy_aux(_II __first, _II __last, _OI __result)
 359     {
 360       typedef typename iterator_traits<_II>::value_type _ValueTypeI;
 361       typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
 362       typedef typename iterator_traits<_II>::iterator_category _Category;
 363       const bool __simple = (__is_pod(_ValueTypeI)
 364                              && __is_pointer<_II>::__value
 365                              && __is_pointer<_OI>::__value
 366                              && __are_same<_ValueTypeI, _ValueTypeO>::__value);
 367
 368       return std::__copy<__simple, _Category>::copy(__first, __last, __result);
 369     }
 370
 371   // Helpers for streambuf iterators (either istream or ostream).
 372   // NB: avoid including <iosfwd>, relatively large.
 373   template<typename _CharT>
 374     struct char_traits;
 375
 376   template<typename _CharT, typename _Traits>
 377     class istreambuf_iterator;
 378
 379   template<typename _CharT, typename _Traits>
 380     class ostreambuf_iterator;
 381
 382   template<typename _CharT>
 383     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 384              ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
 385     __copy_aux(_CharT*, _CharT*,
 386                ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 387
 388   template<typename _CharT>
 389     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 390              ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
 391     __copy_aux(const _CharT*, const _CharT*,
 392                ostreambuf_iterator<_CharT, char_traits<_CharT> >);
 393
 394   template<typename _CharT>
 395     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
 396                                     _CharT*>::__type
 397     __copy_aux(istreambuf_iterator<_CharT, char_traits<_CharT> >,
 398                istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
 399
 400   /**
 401    *  @brief Copies the range [first,last) into result.
 402    *  @param  first  An input iterator.
 403    *  @param  last   An input iterator.
 404    *  @param  result An output iterator.
 405    *  @return   result + (first - last)
 406    *
 407    *  This inline function will boil down to a call to @c memmove whenever
 408    *  possible.  Failing that, if random access iterators are passed, then the
 409    *  loop count will be known (and therefore a candidate for compiler
 410    *  optimizations such as unrolling).  Result may not be contained within
 411    *  [first,last); the copy_backward function should be used instead.
 412    *
 413    *  Note that the end of the output range is permitted to be contained
 414    *  within [first,last).
 415   */
 416   template<typename _II, typename _OI>
 417     inline _OI
 418     copy(_II __first, _II __last, _OI __result)
 419     {
 420       // concept requirements
 421       __glibcxx_function_requires(_InputIteratorConcept<_II>)
 422       __glibcxx_function_requires(_OutputIteratorConcept<_OI,
 423             typename iterator_traits<_II>::value_type>)
 424       __glibcxx_requires_valid_range(__first, __last);
 425
 426       return _OI(std::__copy_aux(__niter_base<_II>::__b(__first),
 427                                  __niter_base<_II>::__b(__last),
 428                                  __niter_base<_OI>::__b(__result)));
 429     }
 430
 431
 432   template<bool, typename>
 433     struct __copy_backward
 434     {
 435       template<typename _BI1, typename _BI2>
 436         static _BI2
 437         __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
 438         {
 439           while (__first != __last)
 440             *--__result = *--__last;
 441           return __result;
 442         }
 443     };
 444
 445   template<bool _BoolType>
 446     struct __copy_backward<_BoolType, random_access_iterator_tag>
 447     {
 448       template<typename _BI1, typename _BI2>
 449         static _BI2
 450         __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
 451         {
 452           typename iterator_traits<_BI1>::difference_type __n;
 453           for (__n = __last - __first; __n > 0; --__n)
 454             *--__result = *--__last;
 455           return __result;
 456         }
 457     };
 458
 459   template<>
 460     struct __copy_backward<true, random_access_iterator_tag>
 461     {
 462       template<typename _Tp>
 463         static _Tp*
 464         __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
 465         {
 466           const ptrdiff_t _Num = __last - __first;
 467           __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
 468           return __result - _Num;
 469         }
 470     };
 471
 472   template<typename _BI1, typename _BI2>
 473     inline _BI2
 474     __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
 475     {
 476       typedef typename iterator_traits<_BI1>::value_type _ValueType1;
 477       typedef typename iterator_traits<_BI2>::value_type _ValueType2;
 478       typedef typename iterator_traits<_BI1>::iterator_category _Category;
 479       const bool __simple = (__is_pod(_ValueType1)
 480                              && __is_pointer<_BI1>::__value
 481                              && __is_pointer<_BI2>::__value
 482                              && __are_same<_ValueType1, _ValueType2>::__value);
 483
 484       return std::__copy_backward<__simple, _Category>::__copy_b(__first,
 485                                                                  __last,
 486                                                                  __result);
 487     }
 488
 489   /**
 490    *  @brief Copies the range [first,last) into result.
 491    *  @param  first  A bidirectional iterator.
 492    *  @param  last   A bidirectional iterator.
 493    *  @param  result A bidirectional iterator.
 494    *  @return   result - (first - last)
 495    *
 496    *  The function has the same effect as copy, but starts at the end of the
 497    *  range and works its way to the start, returning the start of the result.
 498    *  This inline function will boil down to a call to @c memmove whenever
 499    *  possible.  Failing that, if random access iterators are passed, then the
 500    *  loop count will be known (and therefore a candidate for compiler
 501    *  optimizations such as unrolling).
 502    *
 503    *  Result may not be in the range [first,last).  Use copy instead.  Note
 504    *  that the start of the output range may overlap [first,last).
 505   */
 506   template <typename _BI1, typename _BI2>
 507     inline _BI2
 508     copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
 509     {
 510       // concept requirements
 511       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
 512       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
 513       __glibcxx_function_requires(_ConvertibleConcept<
 514             typename iterator_traits<_BI1>::value_type,
 515             typename iterator_traits<_BI2>::value_type>)
 516       __glibcxx_requires_valid_range(__first, __last);
 517
 518       return _BI2(std::__copy_backward_aux(__niter_base<_BI1>::__b(__first),
 519                                            __niter_base<_BI1>::__b(__last),
 520                                            __niter_base<_BI2>::__b(__result)));
 521     }
 522
 523
 524   template<bool>
 525     struct __fill
 526     {
 527       template<typename _ForwardIterator, typename _Tp>
 528         static void
 529         fill(_ForwardIterator __first, _ForwardIterator __last,
 530              const _Tp& __value)
 531         {
 532           for (; __first != __last; ++__first)
 533             *__first = __value;
 534         }
 535     };
 536
 537   template<>
 538     struct __fill<true>
 539     {
 540       template<typename _ForwardIterator, typename _Tp>
 541         static void
 542         fill(_ForwardIterator __first, _ForwardIterator __last,
 543              const _Tp& __value)
 544         {
 545           const _Tp __tmp = __value;
 546           for (; __first != __last; ++__first)
 547             *__first = __tmp;
 548         }
 549     };
 550
 551   template<typename _ForwardIterator, typename _Tp>
 552     inline void
 553     __fill_aux(_ForwardIterator __first, _ForwardIterator __last,
 554                const _Tp& __value)
 555     {
 556       const bool __scalar = __is_scalar<_Tp>::__value;
 557       std::__fill<__scalar>::fill(__first, __last, __value);
 558     }
 559
 560   // Specialization: for char types we can use memset.
 561   inline void
 562   __fill_aux(unsigned char* __first, unsigned char* __last, unsigned char __c)
 563   { __builtin_memset(__first, __c, __last - __first); }
 564
 565   inline void
 566   __fill_aux(signed char* __first, signed char* __last, signed char __c)
 567   { __builtin_memset(__first, static_cast<unsigned char>(__c),
 568                      __last - __first); }
 569
 570   inline void
 571   __fill_aux(char* __first, char* __last, char __c)
 572   { __builtin_memset(__first, static_cast<unsigned char>(__c),
 573                      __last - __first); }
 574
 575   /**
 576    *  @brief Fills the range [first,last) with copies of value.
 577    *  @param  first  A forward iterator.
 578    *  @param  last   A forward iterator.
 579    *  @param  value  A reference-to-const of arbitrary type.
 580    *  @return   Nothing.
 581    *
 582    *  This function fills a range with copies of the same value.  For char
 583    *  types filling contiguous areas of memory, this becomes an inline call
 584    *  to @c memset or @c wmemset.
 585   */
 586   template<typename _ForwardIterator, typename _Tp>
 587     inline void
 588     fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
 589     {
 590       // concept requirements
 591       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
 592                                   _ForwardIterator>)
 593       __glibcxx_requires_valid_range(__first, __last);
 594
 595       std::__fill_aux(__niter_base<_ForwardIterator>::__b(__first),
 596                       __niter_base<_ForwardIterator>::__b(__last), __value);
 597     }
 598
 599
 600   template<bool>
 601     struct __fill_n
 602     {
 603       template<typename _OutputIterator, typename _Size, typename _Tp>
 604         static _OutputIterator
 605         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
 606         {
 607           for (; __n > 0; --__n, ++__first)
 608             *__first = __value;
 609           return __first;
 610         }
 611     };
 612
 613   template<>
 614     struct __fill_n<true>
 615     {
 616       template<typename _OutputIterator, typename _Size, typename _Tp>
 617         static _OutputIterator
 618         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
 619         {
 620           const _Tp __tmp = __value;
 621           for (; __n > 0; --__n, ++__first)
 622             *__first = __tmp;
 623           return __first;
 624         }
 625     };
 626
 627   template<typename _OutputIterator, typename _Size, typename _Tp>
 628     inline _OutputIterator
 629     __fill_n_aux(_OutputIterator __first, _Size __n, const _Tp& __value)
 630     {
 631       const bool __scalar = __is_scalar<_Tp>::__value;
 632       return std::__fill_n<__scalar>::fill_n(__first, __n, __value);
 633     }
 634
 635   template<typename _Size>
 636     inline unsigned char*
 637     __fill_n_aux(unsigned char* __first, _Size __n, unsigned char __c)
 638     {
 639       std::__fill_aux(__first, __first + __n, __c);
 640       return __first + __n;
 641     }
 642
 643   template<typename _Size>
 644     inline signed char*
 645     __fill_n_aux(signed char* __first, _Size __n, signed char __c)
 646     {
 647       std::__fill_aux(__first, __first + __n, __c);
 648       return __first + __n;
 649     }
 650
 651   template<typename _Size>
 652     inline char*
 653     __fill_n_aux(char* __first, _Size __n, char __c)
 654     {
 655       std::__fill_aux(__first, __first + __n, __c);
 656       return __first + __n;
 657     }
 658
 659   /**
 660    *  @brief Fills the range [first,first+n) with copies of value.
 661    *  @param  first  An output iterator.
 662    *  @param  n      The count of copies to perform.
 663    *  @param  value  A reference-to-const of arbitrary type.
 664    *  @return   The iterator at first+n.
 665    *
 666    *  This function fills a range with copies of the same value.  For char
 667    *  types filling contiguous areas of memory, this becomes an inline call
 668    *  to @c memset or @ wmemset.
 669   */
 670   template<typename _OI, typename _Size, typename _Tp>
 671     inline _OI
 672     fill_n(_OI __first, _Size __n, const _Tp& __value)
 673     {
 674       // concept requirements
 675       __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
 676
 677       return _OI(std::__fill_n_aux(__niter_base<_OI>::__b(__first), __n,
 678                                    __value));
 679     }
 680
 681   /**
 682    *  @brief Finds the places in ranges which don't match.
 683    *  @param  first1  An input iterator.
 684    *  @param  last1   An input iterator.
 685    *  @param  first2  An input iterator.
 686    *  @return   A pair of iterators pointing to the first mismatch.
 687    *
 688    *  This compares the elements of two ranges using @c == and returns a pair
 689    *  of iterators.  The first iterator points into the first range, the
 690    *  second iterator points into the second range, and the elements pointed
 691    *  to by the iterators are not equal.
 692   */
 693   template<typename _InputIterator1, typename _InputIterator2>
 694     pair<_InputIterator1, _InputIterator2>
 695     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 696              _InputIterator2 __first2)
 697     {
 698       // concept requirements
 699       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 700       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 701       __glibcxx_function_requires(_EqualOpConcept<
 702             typename iterator_traits<_InputIterator1>::value_type,
 703             typename iterator_traits<_InputIterator2>::value_type>)
 704       __glibcxx_requires_valid_range(__first1, __last1);
 705
 706       while (__first1 != __last1 && *__first1 == *__first2)
 707         {
 708           ++__first1;
 709           ++__first2;
 710         }
 711       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
 712     }
 713
 714   /**
 715    *  @brief Finds the places in ranges which don't match.
 716    *  @param  first1  An input iterator.
 717    *  @param  last1   An input iterator.
 718    *  @param  first2  An input iterator.
 719    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
 720    *  @return   A pair of iterators pointing to the first mismatch.
 721    *
 722    *  This compares the elements of two ranges using the binary_pred
 723    *  parameter, and returns a pair
 724    *  of iterators.  The first iterator points into the first range, the
 725    *  second iterator points into the second range, and the elements pointed
 726    *  to by the iterators are not equal.
 727   */
 728   template<typename _InputIterator1, typename _InputIterator2,
 729            typename _BinaryPredicate>
 730     pair<_InputIterator1, _InputIterator2>
 731     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 732              _InputIterator2 __first2, _BinaryPredicate __binary_pred)
 733     {
 734       // concept requirements
 735       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 736       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 737       __glibcxx_requires_valid_range(__first1, __last1);
 738
 739       while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2)))
 740         {
 741           ++__first1;
 742           ++__first2;
 743         }
 744       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
 745     }
 746
 747
 748   template<bool _BoolType>
 749     struct __equal
 750     {
 751       template<typename _II1, typename _II2>
 752         static bool
 753         equal(_II1 __first1, _II1 __last1, _II2 __first2)
 754         {
 755           for (; __first1 != __last1; ++__first1, ++__first2)
 756             if (!(*__first1 == *__first2))
 757               return false;
 758           return true;
 759         }
 760     };
 761
 762   template<>
 763     struct __equal<true>
 764     {
 765       template<typename _Tp>
 766         static bool
 767         equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2)
 768         {
 769           return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
 770                                    * (__last1 - __first1));
 771         }
 772     };
 773
 774   template<typename _II1, typename _II2>
 775     inline bool
 776     __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
 777     {
 778       typedef typename iterator_traits<_II1>::value_type _ValueType1;
 779       typedef typename iterator_traits<_II2>::value_type _ValueType2;
 780       const bool __simple = (__is_integer<_ValueType1>::__value
 781                              && __is_pointer<_II1>::__value
 782                              && __is_pointer<_II2>::__value
 783                              && __are_same<_ValueType1, _ValueType2>::__value);
 784
 785       return std::__equal<__simple>::equal(__first1, __last1, __first2);
 786     }
 787
 788   /**
 789    *  @brief Tests a range for element-wise equality.
 790    *  @param  first1  An input iterator.
 791    *  @param  last1   An input iterator.
 792    *  @param  first2  An input iterator.
 793    *  @return   A boolean true or false.
 794    *
 795    *  This compares the elements of two ranges using @c == and returns true or
 796    *  false depending on whether all of the corresponding elements of the
 797    *  ranges are equal.
 798   */
 799   template<typename _II1, typename _II2>
 800     inline bool
 801     equal(_II1 __first1, _II1 __last1, _II2 __first2)
 802     {
 803       // concept requirements
 804       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
 805       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
 806       __glibcxx_function_requires(_EqualOpConcept<
 807             typename iterator_traits<_II1>::value_type,
 808             typename iterator_traits<_II2>::value_type>)
 809       __glibcxx_requires_valid_range(__first1, __last1);
 810
 811       return std::__equal_aux(__niter_base<_II1>::__b(__first1),
 812                               __niter_base<_II1>::__b(__last1),
 813                               __niter_base<_II2>::__b(__first2));
 814     }
 815
 816   /**
 817    *  @brief Tests a range for element-wise equality.
 818    *  @param  first1  An input iterator.
 819    *  @param  last1   An input iterator.
 820    *  @param  first2  An input iterator.
 821    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
 822    *  @return   A boolean true or false.
 823    *
 824    *  This compares the elements of two ranges using the binary_pred
 825    *  parameter, and returns true or
 826    *  false depending on whether all of the corresponding elements of the
 827    *  ranges are equal.
 828   */
 829   template<typename _InputIterator1, typename _InputIterator2,
 830            typename _BinaryPredicate>
 831     inline bool
 832     equal(_InputIterator1 __first1, _InputIterator1 __last1,
 833           _InputIterator2 __first2,
 834           _BinaryPredicate __binary_pred)
 835     {
 836       // concept requirements
 837       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 838       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 839       __glibcxx_requires_valid_range(__first1, __last1);
 840
 841       for (; __first1 != __last1; ++__first1, ++__first2)
 842         if (!bool(__binary_pred(*__first1, *__first2)))
 843           return false;
 844       return true;
 845     }
 846
 847   /**
 848    *  @brief Performs "dictionary" comparison on ranges.
 849    *  @param  first1  An input iterator.
 850    *  @param  last1   An input iterator.
 851    *  @param  first2  An input iterator.
 852    *  @param  last2   An input iterator.
 853    *  @return   A boolean true or false.
 854    *
 855    *  "Returns true if the sequence of elements defined by the range
 856    *  [first1,last1) is lexicographically less than the sequence of elements
 857    *  defined by the range [first2,last2).  Returns false otherwise."
 858    *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
 859    *  then this is an inline call to @c memcmp.
 860   */
 861   template<typename _InputIterator1, typename _InputIterator2>
 862     bool
 863     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
 864                             _InputIterator2 __first2, _InputIterator2 __last2)
 865     {
 866       // concept requirements
 867       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 868       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 869       __glibcxx_function_requires(_LessThanOpConcept<
 870             typename iterator_traits<_InputIterator1>::value_type,
 871             typename iterator_traits<_InputIterator2>::value_type>)
 872       __glibcxx_function_requires(_LessThanOpConcept<
 873             typename iterator_traits<_InputIterator2>::value_type,
 874             typename iterator_traits<_InputIterator1>::value_type>)
 875       __glibcxx_requires_valid_range(__first1, __last1);
 876       __glibcxx_requires_valid_range(__first2, __last2);
 877
 878       for (; __first1 != __last1 && __first2 != __last2;
 879            ++__first1, ++__first2)
 880         {
 881           if (*__first1 < *__first2)
 882             return true;
 883           if (*__first2 < *__first1)
 884             return false;
 885         }
 886       return __first1 == __last1 && __first2 != __last2;
 887     }
 888
 889   /**
 890    *  @brief Performs "dictionary" comparison on ranges.
 891    *  @param  first1  An input iterator.
 892    *  @param  last1   An input iterator.
 893    *  @param  first2  An input iterator.
 894    *  @param  last2   An input iterator.
 895    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
 896    *  @return   A boolean true or false.
 897    *
 898    *  The same as the four-parameter @c lexigraphical_compare, but uses the
 899    *  comp parameter instead of @c <.
 900   */
 901   template<typename _InputIterator1, typename _InputIterator2,
 902            typename _Compare>
 903     bool
 904     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
 905                             _InputIterator2 __first2, _InputIterator2 __last2,
 906                             _Compare __comp)
 907     {
 908       // concept requirements
 909       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
 910       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
 911       __glibcxx_requires_valid_range(__first1, __last1);
 912       __glibcxx_requires_valid_range(__first2, __last2);
 913
 914       for (; __first1 != __last1 && __first2 != __last2;
 915            ++__first1, ++__first2)
 916         {
 917           if (__comp(*__first1, *__first2))
 918             return true;
 919           if (__comp(*__first2, *__first1))
 920             return false;
 921         }
 922       return __first1 == __last1 && __first2 != __last2;
 923     }
 924
 925   inline bool
 926   lexicographical_compare(const unsigned char* __first1,
 927                           const unsigned char* __last1,
 928                           const unsigned char* __first2,
 929                           const unsigned char* __last2)
 930   {
 931     __glibcxx_requires_valid_range(__first1, __last1);
 932     __glibcxx_requires_valid_range(__first2, __last2);
 933
 934     const size_t __len1 = __last1 - __first1;
 935     const size_t __len2 = __last2 - __first2;
 936     const int __result = __builtin_memcmp(__first1, __first2,
 937                                           std::min(__len1, __len2));
 938     return __result != 0 ? __result < 0 : __len1 < __len2;
 939   }
 940
 941   inline bool
 942   lexicographical_compare(const char* __first1, const char* __last1,
 943                           const char* __first2, const char* __last2)
 944   {
 945     __glibcxx_requires_valid_range(__first1, __last1);
 946     __glibcxx_requires_valid_range(__first2, __last2);
 947
 948     if (__gnu_cxx::__numeric_traits<char>::__is_signed)
 949       return std::lexicographical_compare((const signed char*) __first1,
 950                                           (const signed char*) __last1,
 951                                           (const signed char*) __first2,
 952                                           (const signed char*) __last2);
 953     else
 954       return std::lexicographical_compare((const unsigned char*) __first1,
 955                                           (const unsigned char*) __last1,
 956                                           (const unsigned char*) __first2,
 957                                           (const unsigned char*) __last2);
 958   }
 959
 960 _GLIBCXX_END_NAMESPACE
 961
 962 #endif