# stl_algobase.h

Go to the documentation of this file.

    00001 // Bits and pieces used in algorithms -*- C++ -*-
    00002
    00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
    00004 // Free Software Foundation, Inc.
    00005 //
    00006 // This file is part of the GNU ISO C++ Library.  This library is free
    00007 // software; you can redistribute it and/or modify it under the
    00008 // terms of the GNU General Public License as published by the
    00009 // Free Software Foundation; either version 2, or (at your option)
    00010 // any later version.
    00011
    00012 // This library is distributed in the hope that it will be useful,
    00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00015 // GNU General Public License for more details.
    00016
    00017 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 /*
    00032  *
    00033  * Copyright (c) 1994
    00034  * Hewlett-Packard Company
    00035  *
    00036  * Permission to use, copy, modify, distribute and sell this software
    00037  * and its documentation for any purpose is hereby granted without fee,
    00038  * provided that the above copyright notice appear in all copies and
    00039  * that both that copyright notice and this permission notice appear
    00040  * in supporting documentation.  Hewlett-Packard Company makes no
    00041  * representations about the suitability of this software for any
    00042  * purpose.  It is provided "as is" without express or implied warranty.
    00043  *
    00044  *
    00045  * Copyright (c) 1996-1998
    00046  * Silicon Graphics Computer Systems, Inc.
    00047  *
    00048  * Permission to use, copy, modify, distribute and sell this software
    00049  * and its documentation for any purpose is hereby granted without fee,
    00050  * provided that the above copyright notice appear in all copies and
    00051  * that both that copyright notice and this permission notice appear
    00052  * in supporting documentation.  Silicon Graphics makes no
    00053  * representations about the suitability of this software for any
    00054  * purpose.  It is provided "as is" without express or implied warranty.
    00055  */
    00056
    00057 /** @file stl_algobase.h
    00058  *  This is an internal header file, included by other library headers.
    00059  *  You should not attempt to use it directly.
    00060  */
    00061
    00062 #ifndef _ALGOBASE_H
    00063 #define _ALGOBASE_H 1
    00064
    00065 #include <bits/c++config.h>
    00066 #include <cstring>
    00067 #include <climits>
    00068 #include <cstdlib>
    00069 #include <cstddef>
    00070 #include <iosfwd>
    00071 #include <bits/stl_pair.h>
    00072 #include <bits/cpp_type_traits.h>
    00073 #include <ext/type_traits.h>
    00074 #include <bits/stl_iterator_base_types.h>
    00075 #include <bits/stl_iterator_base_funcs.h>
    00076 #include <bits/stl_iterator.h>
    00077 #include <bits/concept_check.h>
    00078 #include <debug/debug.h>
    00079
    00080 _GLIBCXX_BEGIN_NAMESPACE(std)
    00081
    00082   /**
    00083    *  @brief Swaps two values.
    00084    *  @param  a  A thing of arbitrary type.
    00085    *  @param  b  Another thing of arbitrary type.
    00086    *  @return   Nothing.
    00087    *
    00088    *  This is the simple classic generic implementation.  It will work on
    00089    *  any type which has a copy constructor and an assignment operator.
    00090   */
    00091   template<typename _Tp>
    00092     inline void
    00093     swap(_Tp& __a, _Tp& __b)
    00094     {
    00095       // concept requirements
    00096       __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
    00097
    00098       _Tp __tmp = __a;
    00099       __a = __b;
    00100       __b = __tmp;
    00101     }
    00102
    00103   // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
    00104   // nutshell, we are partially implementing the resolution of DR 187,
    00105   // when it's safe, i.e., the value_types are equal.
    00106   template<bool _BoolType>
    00107     struct __iter_swap
    00108     {
    00109       template<typename _ForwardIterator1, typename _ForwardIterator2>
    00110         static void
    00111         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    00112         {
    00113           typedef typename iterator_traits<_ForwardIterator1>::value_type
    00114             _ValueType1;
    00115           _ValueType1 __tmp = *__a;
    00116           *__a = *__b;
    00117           *__b = __tmp;
    00118     }
    00119     };
    00120
    00121   template<>
    00122     struct __iter_swap<true>
    00123     {
    00124       template<typename _ForwardIterator1, typename _ForwardIterator2>
    00125         static void
    00126         iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    00127         {
    00128           swap(*__a, *__b);
    00129         }
    00130     };
    00131
    00132   /**
    00133    *  @brief Swaps the contents of two iterators.
    00134    *  @param  a  An iterator.
    00135    *  @param  b  Another iterator.
    00136    *  @return   Nothing.
    00137    *
    00138    *  This function swaps the values pointed to by two iterators, not the
    00139    *  iterators themselves.
    00140   */
    00141   template<typename _ForwardIterator1, typename _ForwardIterator2>
    00142     inline void
    00143     iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
    00144     {
    00145       typedef typename iterator_traits<_ForwardIterator1>::value_type
    00146     _ValueType1;
    00147       typedef typename iterator_traits<_ForwardIterator2>::value_type
    00148     _ValueType2;
    00149
    00150       // concept requirements
    00151       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
    00152                   _ForwardIterator1>)
    00153       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
    00154                   _ForwardIterator2>)
    00155       __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
    00156                   _ValueType2>)
    00157       __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
    00158                   _ValueType1>)
    00159
    00160       typedef typename iterator_traits<_ForwardIterator1>::reference
    00161     _ReferenceType1;
    00162       typedef typename iterator_traits<_ForwardIterator2>::reference
    00163     _ReferenceType2;
    00164       std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value &&
    00165     __are_same<_ValueType1 &, _ReferenceType1>::__value &&
    00166     __are_same<_ValueType2 &, _ReferenceType2>::__value>::
    00167 	iter_swap(__a, __b);
    00168     }
    00169
    00170   /**
    00171    *  @brief This does what you think it does.
    00172    *  @param  a  A thing of arbitrary type.
    00173    *  @param  b  Another thing of arbitrary type.
    00174    *  @return   The lesser of the parameters.
    00175    *
    00176    *  This is the simple classic generic implementation.  It will work on
    00177    *  temporary expressions, since they are only evaluated once, unlike a
    00178    *  preprocessor macro.
    00179   */
    00180   template<typename _Tp>
    00181     inline const _Tp&
    00182     min(const _Tp& __a, const _Tp& __b)
    00183     {
    00184       // concept requirements
    00185       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
    00186       //return __b < __a ? __b : __a;
    00187       if (__b < __a)
    00188     return __b;
    00189       return __a;
    00190     }
    00191
    00192   /**
    00193    *  @brief This does what you think it does.
    00194    *  @param  a  A thing of arbitrary type.
    00195    *  @param  b  Another thing of arbitrary type.
    00196    *  @return   The greater of the parameters.
    00197    *
    00198    *  This is the simple classic generic implementation.  It will work on
    00199    *  temporary expressions, since they are only evaluated once, unlike a
    00200    *  preprocessor macro.
    00201   */
    00202   template<typename _Tp>
    00203     inline const _Tp&
    00204     max(const _Tp& __a, const _Tp& __b)
    00205     {
    00206       // concept requirements
    00207       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
    00208       //return  __a < __b ? __b : __a;
    00209       if (__a < __b)
    00210     return __b;
    00211       return __a;
    00212     }
    00213
    00214   /**
    00215    *  @brief This does what you think it does.
    00216    *  @param  a  A thing of arbitrary type.
    00217    *  @param  b  Another thing of arbitrary type.
    00218    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
    00219    *  @return   The lesser of the parameters.
    00220    *
    00221    *  This will work on temporary expressions, since they are only evaluated
    00222    *  once, unlike a preprocessor macro.
    00223   */
    00224   template<typename _Tp, typename _Compare>
    00225     inline const _Tp&
    00226     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
    00227     {
    00228       //return __comp(__b, __a) ? __b : __a;
    00229       if (__comp(__b, __a))
    00230     return __b;
    00231       return __a;
    00232     }
    00233
    00234   /**
    00235    *  @brief This does what you think it does.
    00236    *  @param  a  A thing of arbitrary type.
    00237    *  @param  b  Another thing of arbitrary type.
    00238    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
    00239    *  @return   The greater of the parameters.
    00240    *
    00241    *  This will work on temporary expressions, since they are only evaluated
    00242    *  once, unlike a preprocessor macro.
    00243   */
    00244   template<typename _Tp, typename _Compare>
    00245     inline const _Tp&
    00246     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
    00247     {
    00248       //return __comp(__a, __b) ? __b : __a;
    00249       if (__comp(__a, __b))
    00250     return __b;
    00251       return __a;
    00252     }
    00253
    00254   // All of these auxiliary structs serve two purposes.  (1) Replace
    00255   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
    00256   // because the input and output ranges are permitted to overlap.)
    00257   // (2) If we're using random access iterators, then write the loop as
    00258   // a for loop with an explicit count.
    00259
    00260   template<bool, typename>
    00261     struct __copy
    00262     {
    00263       template<typename _II, typename _OI>
    00264         static _OI
    00265         copy(_II __first, _II __last, _OI __result)
    00266         {
    00267       for (; __first != __last; ++__result, ++__first)
    00268         *__result = *__first;
    00269       return __result;
    00270     }
    00271     };
    00272
    00273   template<bool _BoolType>
    00274     struct __copy<_BoolType, random_access_iterator_tag>
    00275     {
    00276       template<typename _II, typename _OI>
    00277         static _OI
    00278         copy(_II __first, _II __last, _OI __result)
    00279         {
    00280       typedef typename iterator_traits<_II>::difference_type _Distance;
    00281       for(_Distance __n = __last - __first; __n > 0; --__n)
    00282         {
    00283           *__result = *__first;
    00284           ++__first;
    00285           ++__result;
    00286         }
    00287       return __result;
    00288     }
    00289     };
    00290
    00291   template<>
    00292     struct __copy<true, random_access_iterator_tag>
    00293     {
    00294       template<typename _Tp>
    00295         static _Tp*
    00296         copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
    00297         {
    00298       std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
    00299       return __result + (__last - __first);
    00300     }
    00301     };
    00302
    00303   template<typename _II, typename _OI>
    00304     inline _OI
    00305     __copy_aux(_II __first, _II __last, _OI __result)
    00306     {
    00307       typedef typename iterator_traits<_II>::value_type _ValueTypeI;
    00308       typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
    00309       typedef typename iterator_traits<_II>::iterator_category _Category;
    00310       const bool __simple = (__is_scalar<_ValueTypeI>::__value
    00311                          && __is_pointer<_II>::__value
    00312                          && __is_pointer<_OI>::__value
    00313                  && __are_same<_ValueTypeI, _ValueTypeO>::__value);
    00314
    00315       return std::__copy<__simple, _Category>::copy(__first, __last, __result);
    00316     }
    00317
    00318   // Helpers for streambuf iterators (either istream or ostream).
    00319   template<typename _CharT>
    00320   typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
    00321                   ostreambuf_iterator<_CharT> >::__type
    00322     __copy_aux(_CharT*, _CharT*, ostreambuf_iterator<_CharT>);
    00323
    00324   template<typename _CharT>
    00325     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
    00326                     ostreambuf_iterator<_CharT> >::__type
    00327     __copy_aux(const _CharT*, const _CharT*, ostreambuf_iterator<_CharT>);
    00328
    00329   template<typename _CharT>
    00330   typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, _CharT*>::__type
    00331     __copy_aux(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>,
    00332            _CharT*);
    00333
    00334   template<bool, bool>
    00335     struct __copy_normal
    00336     {
    00337       template<typename _II, typename _OI>
    00338         static _OI
    00339         __copy_n(_II __first, _II __last, _OI __result)
    00340         { return std::__copy_aux(__first, __last, __result); }
    00341     };
    00342
    00343   template<>
    00344     struct __copy_normal<true, false>
    00345     {
    00346       template<typename _II, typename _OI>
    00347         static _OI
    00348         __copy_n(_II __first, _II __last, _OI __result)
    00349         { return std::__copy_aux(__first.base(), __last.base(), __result); }
    00350     };
    00351
    00352   template<>
    00353     struct __copy_normal<false, true>
    00354     {
    00355       template<typename _II, typename _OI>
    00356         static _OI
    00357         __copy_n(_II __first, _II __last, _OI __result)
    00358         { return _OI(std::__copy_aux(__first, __last, __result.base())); }
    00359     };
    00360
    00361   template<>
    00362     struct __copy_normal<true, true>
    00363     {
    00364       template<typename _II, typename _OI>
    00365         static _OI
    00366         __copy_n(_II __first, _II __last, _OI __result)
    00367         { return _OI(std::__copy_aux(__first.base(), __last.base(),
    00368                      __result.base())); }
    00369     };
    00370
    00371   /**
    00372    *  @brief Copies the range [first,last) into result.
    00373    *  @param  first  An input iterator.
    00374    *  @param  last   An input iterator.
    00375    *  @param  result An output iterator.
    00376    *  @return   result + (first - last)
    00377    *
    00378    *  This inline function will boil down to a call to @c memmove whenever
    00379    *  possible.  Failing that, if random access iterators are passed, then the
    00380    *  loop count will be known (and therefore a candidate for compiler
    00381    *  optimizations such as unrolling).  Result may not be contained within
    00382    *  [first,last); the copy_backward function should be used instead.
    00383    *
    00384    *  Note that the end of the output range is permitted to be contained
    00385    *  within [first,last).
    00386   */
    00387   template<typename _InputIterator, typename _OutputIterator>
    00388     inline _OutputIterator
    00389     copy(_InputIterator __first, _InputIterator __last,
    00390      _OutputIterator __result)
    00391     {
    00392       // concept requirements
    00393       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
    00394       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
    00395         typename iterator_traits<_InputIterator>::value_type>)
    00396       __glibcxx_requires_valid_range(__first, __last);
    00397
    00398        const bool __in = __is_normal_iterator<_InputIterator>::__value;
    00399        const bool __out = __is_normal_iterator<_OutputIterator>::__value;
    00400        return std::__copy_normal<__in, __out>::__copy_n(__first, __last,
    00401                             __result);
    00402     }
    00403
    00404   // Overload for streambuf iterators.
    00405   template<typename _CharT>
    00406     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
    00407                         ostreambuf_iterator<_CharT> >::__type
    00408     copy(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>,
    00409      ostreambuf_iterator<_CharT>);
    00410
    00411   template<bool, typename>
    00412     struct __copy_backward
    00413     {
    00414       template<typename _BI1, typename _BI2>
    00415         static _BI2
    00416         __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
    00417         {
    00418       while (__first != __last)
    00419         *--__result = *--__last;
    00420       return __result;
    00421     }
    00422     };
    00423
    00424   template<bool _BoolType>
    00425     struct __copy_backward<_BoolType, random_access_iterator_tag>
    00426     {
    00427       template<typename _BI1, typename _BI2>
    00428         static _BI2
    00429         __copy_b(_BI1 __first, _BI1 __last, _BI2 __result)
    00430         {
    00431       typename iterator_traits<_BI1>::difference_type __n;
    00432       for (__n = __last - __first; __n > 0; --__n)
    00433         *--__result = *--__last;
    00434       return __result;
    00435     }
    00436     };
    00437
    00438   template<>
    00439     struct __copy_backward<true, random_access_iterator_tag>
    00440     {
    00441       template<typename _Tp>
    00442         static _Tp*
    00443         __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
    00444         {
    00445       const ptrdiff_t _Num = __last - __first;
    00446       std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
    00447       return __result - _Num;
    00448     }
    00449     };
    00450
    00451   template<typename _BI1, typename _BI2>
    00452     inline _BI2
    00453     __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
    00454     {
    00455       typedef typename iterator_traits<_BI1>::value_type _ValueType1;
    00456       typedef typename iterator_traits<_BI2>::value_type _ValueType2;
    00457       typedef typename iterator_traits<_BI1>::iterator_category _Category;
    00458       const bool __simple = (__is_scalar<_ValueType1>::__value
    00459                          && __is_pointer<_BI1>::__value
    00460                          && __is_pointer<_BI2>::__value
    00461                  && __are_same<_ValueType1, _ValueType2>::__value);
    00462
    00463       return std::__copy_backward<__simple, _Category>::__copy_b(__first,
    00464                                  __last,
    00465                                  __result);
    00466     }
    00467
    00468   template<bool, bool>
    00469     struct __copy_backward_normal
    00470     {
    00471       template<typename _BI1, typename _BI2>
    00472         static _BI2
    00473         __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
    00474         { return std::__copy_backward_aux(__first, __last, __result); }
    00475     };
    00476
    00477   template<>
    00478     struct __copy_backward_normal<true, false>
    00479     {
    00480       template<typename _BI1, typename _BI2>
    00481         static _BI2
    00482         __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
    00483         { return std::__copy_backward_aux(__first.base(), __last.base(),
    00484                       __result); }
    00485     };
    00486
    00487   template<>
    00488     struct __copy_backward_normal<false, true>
    00489     {
    00490       template<typename _BI1, typename _BI2>
    00491         static _BI2
    00492         __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
    00493         { return _BI2(std::__copy_backward_aux(__first, __last,
    00494                            __result.base())); }
    00495     };
    00496
    00497   template<>
    00498     struct __copy_backward_normal<true, true>
    00499     {
    00500       template<typename _BI1, typename _BI2>
    00501         static _BI2
    00502         __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result)
    00503         { return _BI2(std::__copy_backward_aux(__first.base(), __last.base(),
    00504                            __result.base())); }
    00505     };
    00506
    00507   /**
    00508    *  @brief Copies the range [first,last) into result.
    00509    *  @param  first  A bidirectional iterator.
    00510    *  @param  last   A bidirectional iterator.
    00511    *  @param  result A bidirectional iterator.
    00512    *  @return   result - (first - last)
    00513    *
    00514    *  The function has the same effect as copy, but starts at the end of the
    00515    *  range and works its way to the start, returning the start of the result.
    00516    *  This inline function will boil down to a call to @c memmove whenever
    00517    *  possible.  Failing that, if random access iterators are passed, then the
    00518    *  loop count will be known (and therefore a candidate for compiler
    00519    *  optimizations such as unrolling).
    00520    *
    00521    *  Result may not be in the range [first,last).  Use copy instead.  Note
    00522    *  that the start of the output range may overlap [first,last).
    00523   */
    00524   template <typename _BI1, typename _BI2>
    00525     inline _BI2
    00526     copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
    00527     {
    00528       // concept requirements
    00529       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
    00530       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
    00531       __glibcxx_function_requires(_ConvertibleConcept<
    00532         typename iterator_traits<_BI1>::value_type,
    00533         typename iterator_traits<_BI2>::value_type>)
    00534       __glibcxx_requires_valid_range(__first, __last);
    00535
    00536       const bool __bi1 = __is_normal_iterator<_BI1>::__value;
    00537       const bool __bi2 = __is_normal_iterator<_BI2>::__value;
    00538       return std::__copy_backward_normal<__bi1, __bi2>::__copy_b_n(__first,
    00539                                    __last,
    00540                                    __result);
    00541     }
    00542
    00543   template<bool>
    00544     struct __fill
    00545     {
    00546       template<typename _ForwardIterator, typename _Tp>
    00547         static void
    00548         fill(_ForwardIterator __first, _ForwardIterator __last,
    00549          const _Tp& __value)
    00550         {
    00551       for (; __first != __last; ++__first)
    00552         *__first = __value;
    00553     }
    00554     };
    00555
    00556   template<>
    00557     struct __fill<true>
    00558     {
    00559       template<typename _ForwardIterator, typename _Tp>
    00560         static void
    00561         fill(_ForwardIterator __first, _ForwardIterator __last,
    00562          const _Tp& __value)
    00563         {
    00564       const _Tp __tmp = __value;
    00565       for (; __first != __last; ++__first)
    00566         *__first = __tmp;
    00567     }
    00568     };
    00569
    00570   /**
    00571    *  @brief Fills the range [first,last) with copies of value.
    00572    *  @param  first  A forward iterator.
    00573    *  @param  last   A forward iterator.
    00574    *  @param  value  A reference-to-const of arbitrary type.
    00575    *  @return   Nothing.
    00576    *
    00577    *  This function fills a range with copies of the same value.  For one-byte
    00578    *  types filling contiguous areas of memory, this becomes an inline call to
    00579    *  @c memset.
    00580   */
    00581   template<typename _ForwardIterator, typename _Tp>
    00582     void
    00583     fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
    00584     {
    00585       // concept requirements
    00586       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
    00587                   _ForwardIterator>)
    00588       __glibcxx_requires_valid_range(__first, __last);
    00589
    00590       const bool __scalar = __is_scalar<_Tp>::__value;
    00591       std::__fill<__scalar>::fill(__first, __last, __value);
    00592     }
    00593
    00594   // Specialization: for one-byte types we can use memset.
    00595   inline void
    00596   fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
    00597   {
    00598     __glibcxx_requires_valid_range(__first, __last);
    00599     const unsigned char __tmp = __c;
    00600     std::memset(__first, __tmp, __last - __first);
    00601   }
    00602
    00603   inline void
    00604   fill(signed char* __first, signed char* __last, const signed char& __c)
    00605   {
    00606     __glibcxx_requires_valid_range(__first, __last);
    00607     const signed char __tmp = __c;
    00608     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
    00609   }
    00610
    00611   inline void
    00612   fill(char* __first, char* __last, const char& __c)
    00613   {
    00614     __glibcxx_requires_valid_range(__first, __last);
    00615     const char __tmp = __c;
    00616     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
    00617   }
    00618
    00619   template<bool>
    00620     struct __fill_n
    00621     {
    00622       template<typename _OutputIterator, typename _Size, typename _Tp>
    00623         static _OutputIterator
    00624         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
    00625         {
    00626       for (; __n > 0; --__n, ++__first)
    00627         *__first = __value;
    00628       return __first;
    00629     }
    00630     };
    00631
    00632   template<>
    00633     struct __fill_n<true>
    00634     {
    00635       template<typename _OutputIterator, typename _Size, typename _Tp>
    00636         static _OutputIterator
    00637         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
    00638         {
    00639       const _Tp __tmp = __value;
    00640       for (; __n > 0; --__n, ++__first)
    00641         *__first = __tmp;
    00642       return __first;
    00643     }
    00644     };
    00645
    00646   /**
    00647    *  @brief Fills the range [first,first+n) with copies of value.
    00648    *  @param  first  An output iterator.
    00649    *  @param  n      The count of copies to perform.
    00650    *  @param  value  A reference-to-const of arbitrary type.
    00651    *  @return   The iterator at first+n.
    00652    *
    00653    *  This function fills a range with copies of the same value.  For one-byte
    00654    *  types filling contiguous areas of memory, this becomes an inline call to
    00655    *  @c memset.
    00656   */
    00657   template<typename _OutputIterator, typename _Size, typename _Tp>
    00658     _OutputIterator
    00659     fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
    00660     {
    00661       // concept requirements
    00662       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
    00663
    00664       const bool __scalar = __is_scalar<_Tp>::__value;
    00665       return std::__fill_n<__scalar>::fill_n(__first, __n, __value);
    00666     }
    00667
    00668   template<typename _Size>
    00669     inline unsigned char*
    00670     fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
    00671     {
    00672       std::fill(__first, __first + __n, __c);
    00673       return __first + __n;
    00674     }
    00675
    00676   template<typename _Size>
    00677     inline signed char*
    00678     fill_n(signed char* __first, _Size __n, const signed char& __c)
    00679     {
    00680       std::fill(__first, __first + __n, __c);
    00681       return __first + __n;
    00682     }
    00683
    00684   template<typename _Size>
    00685     inline char*
    00686     fill_n(char* __first, _Size __n, const char& __c)
    00687     {
    00688       std::fill(__first, __first + __n, __c);
    00689       return __first + __n;
    00690     }
    00691
    00692   /**
    00693    *  @brief Finds the places in ranges which don't match.
    00694    *  @param  first1  An input iterator.
    00695    *  @param  last1   An input iterator.
    00696    *  @param  first2  An input iterator.
    00697    *  @return   A pair of iterators pointing to the first mismatch.
    00698    *
    00699    *  This compares the elements of two ranges using @c == and returns a pair
    00700    *  of iterators.  The first iterator points into the first range, the
    00701    *  second iterator points into the second range, and the elements pointed
    00702    *  to by the iterators are not equal.
    00703   */
    00704   template<typename _InputIterator1, typename _InputIterator2>
    00705     pair<_InputIterator1, _InputIterator2>
    00706     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
    00707          _InputIterator2 __first2)
    00708     {
    00709       // concept requirements
    00710       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    00711       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    00712       __glibcxx_function_requires(_EqualOpConcept<
    00713         typename iterator_traits<_InputIterator1>::value_type,
    00714         typename iterator_traits<_InputIterator2>::value_type>)
    00715       __glibcxx_requires_valid_range(__first1, __last1);
    00716
    00717       while (__first1 != __last1 && *__first1 == *__first2)
    00718         {
    00719       ++__first1;
    00720       ++__first2;
    00721         }
    00722       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
    00723     }
    00724
    00725   /**
    00726    *  @brief Finds the places in ranges which don't match.
    00727    *  @param  first1  An input iterator.
    00728    *  @param  last1   An input iterator.
    00729    *  @param  first2  An input iterator.
    00730    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
    00731    *  @return   A pair of iterators pointing to the first mismatch.
    00732    *
    00733    *  This compares the elements of two ranges using the binary_pred
    00734    *  parameter, and returns a pair
    00735    *  of iterators.  The first iterator points into the first range, the
    00736    *  second iterator points into the second range, and the elements pointed
    00737    *  to by the iterators are not equal.
    00738   */
    00739   template<typename _InputIterator1, typename _InputIterator2,
    00740        typename _BinaryPredicate>
    00741     pair<_InputIterator1, _InputIterator2>
    00742     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
    00743          _InputIterator2 __first2, _BinaryPredicate __binary_pred)
    00744     {
    00745       // concept requirements
    00746       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    00747       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    00748       __glibcxx_requires_valid_range(__first1, __last1);
    00749
    00750       while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
    00751         {
    00752       ++__first1;
    00753       ++__first2;
    00754         }
    00755       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
    00756     }
    00757
    00758   /**
    00759    *  @brief Tests a range for element-wise equality.
    00760    *  @param  first1  An input iterator.
    00761    *  @param  last1   An input iterator.
    00762    *  @param  first2  An input iterator.
    00763    *  @return   A boolean true or false.
    00764    *
    00765    *  This compares the elements of two ranges using @c == and returns true or
    00766    *  false depending on whether all of the corresponding elements of the
    00767    *  ranges are equal.
    00768   */
    00769   template<typename _InputIterator1, typename _InputIterator2>
    00770     inline bool
    00771     equal(_InputIterator1 __first1, _InputIterator1 __last1,
    00772       _InputIterator2 __first2)
    00773     {
    00774       // concept requirements
    00775       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    00776       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    00777       __glibcxx_function_requires(_EqualOpConcept<
    00778         typename iterator_traits<_InputIterator1>::value_type,
    00779         typename iterator_traits<_InputIterator2>::value_type>)
    00780       __glibcxx_requires_valid_range(__first1, __last1);
    00781
    00782       for (; __first1 != __last1; ++__first1, ++__first2)
    00783     if (!(*__first1 == *__first2))
    00784       return false;
    00785       return true;
    00786     }
    00787
    00788   /**
    00789    *  @brief Tests a range for element-wise equality.
    00790    *  @param  first1  An input iterator.
    00791    *  @param  last1   An input iterator.
    00792    *  @param  first2  An input iterator.
    00793    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
    00794    *  @return   A boolean true or false.
    00795    *
    00796    *  This compares the elements of two ranges using the binary_pred
    00797    *  parameter, and returns true or
    00798    *  false depending on whether all of the corresponding elements of the
    00799    *  ranges are equal.
    00800   */
    00801   template<typename _InputIterator1, typename _InputIterator2,
    00802        typename _BinaryPredicate>
    00803     inline bool
    00804     equal(_InputIterator1 __first1, _InputIterator1 __last1,
    00805       _InputIterator2 __first2,
    00806       _BinaryPredicate __binary_pred)
    00807     {
    00808       // concept requirements
    00809       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    00810       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    00811       __glibcxx_requires_valid_range(__first1, __last1);
    00812
    00813       for (; __first1 != __last1; ++__first1, ++__first2)
    00814     if (!__binary_pred(*__first1, *__first2))
    00815       return false;
    00816       return true;
    00817     }
    00818
    00819   /**
    00820    *  @brief Performs "dictionary" comparison on ranges.
    00821    *  @param  first1  An input iterator.
    00822    *  @param  last1   An input iterator.
    00823    *  @param  first2  An input iterator.
    00824    *  @param  last2   An input iterator.
    00825    *  @return   A boolean true or false.
    00826    *
    00827    *  "Returns true if the sequence of elements defined by the range
    00828    *  [first1,last1) is lexicographically less than the sequence of elements
    00829    *  defined by the range [first2,last2).  Returns false otherwise."
    00830    *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
    00831    *  then this is an inline call to @c memcmp.
    00832   */
    00833   template<typename _InputIterator1, typename _InputIterator2>
    00834     bool
    00835     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
    00836                 _InputIterator2 __first2, _InputIterator2 __last2)
    00837     {
    00838       // concept requirements
    00839       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    00840       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    00841       __glibcxx_function_requires(_LessThanOpConcept<
    00842         typename iterator_traits<_InputIterator1>::value_type,
    00843         typename iterator_traits<_InputIterator2>::value_type>)
    00844       __glibcxx_function_requires(_LessThanOpConcept<
    00845         typename iterator_traits<_InputIterator2>::value_type,
    00846         typename iterator_traits<_InputIterator1>::value_type>)
    00847       __glibcxx_requires_valid_range(__first1, __last1);
    00848       __glibcxx_requires_valid_range(__first2, __last2);
    00849
    00850       for (; __first1 != __last1 && __first2 != __last2;
    00851        ++__first1, ++__first2)
    00852     {
    00853       if (*__first1 < *__first2)
    00854         return true;
    00855       if (*__first2 < *__first1)
    00856         return false;
    00857     }
    00858       return __first1 == __last1 && __first2 != __last2;
    00859     }
    00860
    00861   /**
    00862    *  @brief Performs "dictionary" comparison on ranges.
    00863    *  @param  first1  An input iterator.
    00864    *  @param  last1   An input iterator.
    00865    *  @param  first2  An input iterator.
    00866    *  @param  last2   An input iterator.
    00867    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
    00868    *  @return   A boolean true or false.
    00869    *
    00870    *  The same as the four-parameter @c lexigraphical_compare, but uses the
    00871    *  comp parameter instead of @c <.
    00872   */
    00873   template<typename _InputIterator1, typename _InputIterator2,
    00874        typename _Compare>
    00875     bool
    00876     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
    00877                 _InputIterator2 __first2, _InputIterator2 __last2,
    00878                 _Compare __comp)
    00879     {
    00880       // concept requirements
    00881       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
    00882       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
    00883       __glibcxx_requires_valid_range(__first1, __last1);
    00884       __glibcxx_requires_valid_range(__first2, __last2);
    00885
    00886       for (; __first1 != __last1 && __first2 != __last2;
    00887        ++__first1, ++__first2)
    00888     {
    00889       if (__comp(*__first1, *__first2))
    00890         return true;
    00891       if (__comp(*__first2, *__first1))
    00892         return false;
    00893     }
    00894       return __first1 == __last1 && __first2 != __last2;
    00895     }
    00896
    00897   inline bool
    00898   lexicographical_compare(const unsigned char* __first1,
    00899               const unsigned char* __last1,
    00900               const unsigned char* __first2,
    00901               const unsigned char* __last2)
    00902   {
    00903     __glibcxx_requires_valid_range(__first1, __last1);
    00904     __glibcxx_requires_valid_range(__first2, __last2);
    00905
    00906     const size_t __len1 = __last1 - __first1;
    00907     const size_t __len2 = __last2 - __first2;
    00908     const int __result = std::memcmp(__first1, __first2,
    00909                      std::min(__len1, __len2));
    00910     return __result != 0 ? __result < 0 : __len1 < __len2;
    00911   }
    00912
    00913   inline bool
    00914   lexicographical_compare(const char* __first1, const char* __last1,
    00915               const char* __first2, const char* __last2)
    00916   {
    00917     __glibcxx_requires_valid_range(__first1, __last1);
    00918     __glibcxx_requires_valid_range(__first2, __last2);
    00919
    00920 #if CHAR_MAX == SCHAR_MAX
    00921     return std::lexicographical_compare((const signed char*) __first1,
    00922                     (const signed char*) __last1,
    00923                     (const signed char*) __first2,
    00924                     (const signed char*) __last2);
    00925 #else /* CHAR_MAX == SCHAR_MAX */
    00926     return std::lexicographical_compare((const unsigned char*) __first1,
    00927                     (const unsigned char*) __last1,
    00928                     (const unsigned char*) __first2,
    00929                     (const unsigned char*) __last2);
    00930 #endif /* CHAR_MAX == SCHAR_MAX */
    00931   }
    00932
    00933 _GLIBCXX_END_NAMESPACE
    00934
    00935 #endif