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