stl_algobase.h

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

Generated on Thu Feb 10 23:22:58 2005 for libstdc++-v3 Source by  doxygen 1.4.0