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