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

Generated on Sat Apr 2 13:54:43 2005 for libstdc++ source by  doxygen 1.4.0