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