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

Generated on Sun Sep 12 15:49:59 2004 for libstdc++ source by doxygen 1.3.8