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