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