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 Wed Aug 4 21:43:17 2004 for libstdc++-v3 Source by doxygen 1.3.8