stl_algobase.h

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

Generated on Tue Sep 7 10:05:15 2004 for libstdc++-v3 Source by doxygen 1.3.8