libstdc++
|
00001 // Core algorithmic facilities -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * 00028 * Copyright (c) 1994 00029 * Hewlett-Packard Company 00030 * 00031 * Permission to use, copy, modify, distribute and sell this software 00032 * and its documentation for any purpose is hereby granted without fee, 00033 * provided that the above copyright notice appear in all copies and 00034 * that both that copyright notice and this permission notice appear 00035 * in supporting documentation. Hewlett-Packard Company makes no 00036 * representations about the suitability of this software for any 00037 * purpose. It is provided "as is" without express or implied warranty. 00038 * 00039 * 00040 * Copyright (c) 1996-1998 00041 * Silicon Graphics Computer Systems, Inc. 00042 * 00043 * Permission to use, copy, modify, distribute and sell this software 00044 * and its documentation for any purpose is hereby granted without fee, 00045 * provided that the above copyright notice appear in all copies and 00046 * that both that copyright notice and this permission notice appear 00047 * in supporting documentation. Silicon Graphics makes no 00048 * representations about the suitability of this software for any 00049 * purpose. It is provided "as is" without express or implied warranty. 00050 */ 00051 00052 /** @file stl_algobase.h 00053 * This is an internal header file, included by other library headers. 00054 * You should not attempt to use it directly. 00055 */ 00056 00057 #ifndef _STL_ALGOBASE_H 00058 #define _STL_ALGOBASE_H 1 00059 00060 #include <bits/c++config.h> 00061 #include <cstddef> 00062 #include <bits/functexcept.h> 00063 #include <bits/cpp_type_traits.h> 00064 #include <ext/type_traits.h> 00065 #include <ext/numeric_traits.h> 00066 #include <bits/stl_pair.h> 00067 #include <bits/stl_iterator_base_types.h> 00068 #include <bits/stl_iterator_base_funcs.h> 00069 #include <bits/stl_iterator.h> 00070 #include <bits/concept_check.h> 00071 #include <debug/debug.h> 00072 #include <bits/move.h> // For std::swap and _GLIBCXX_MOVE 00073 00074 _GLIBCXX_BEGIN_NAMESPACE(std) 00075 00076 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a 00077 // nutshell, we are partially implementing the resolution of DR 187, 00078 // when it's safe, i.e., the value_types are equal. 00079 template<bool _BoolType> 00080 struct __iter_swap 00081 { 00082 template<typename _ForwardIterator1, typename _ForwardIterator2> 00083 static void 00084 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 00085 { 00086 typedef typename iterator_traits<_ForwardIterator1>::value_type 00087 _ValueType1; 00088 _ValueType1 __tmp = _GLIBCXX_MOVE(*__a); 00089 *__a = _GLIBCXX_MOVE(*__b); 00090 *__b = _GLIBCXX_MOVE(__tmp); 00091 } 00092 }; 00093 00094 template<> 00095 struct __iter_swap<true> 00096 { 00097 template<typename _ForwardIterator1, typename _ForwardIterator2> 00098 static void 00099 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 00100 { 00101 swap(*__a, *__b); 00102 } 00103 }; 00104 00105 /** 00106 * @brief Swaps the contents of two iterators. 00107 * @ingroup mutating_algorithms 00108 * @param a An iterator. 00109 * @param b Another iterator. 00110 * @return Nothing. 00111 * 00112 * This function swaps the values pointed to by two iterators, not the 00113 * iterators themselves. 00114 */ 00115 template<typename _ForwardIterator1, typename _ForwardIterator2> 00116 inline void 00117 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 00118 { 00119 typedef typename iterator_traits<_ForwardIterator1>::value_type 00120 _ValueType1; 00121 typedef typename iterator_traits<_ForwardIterator2>::value_type 00122 _ValueType2; 00123 00124 // concept requirements 00125 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00126 _ForwardIterator1>) 00127 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00128 _ForwardIterator2>) 00129 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, 00130 _ValueType2>) 00131 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, 00132 _ValueType1>) 00133 00134 typedef typename iterator_traits<_ForwardIterator1>::reference 00135 _ReferenceType1; 00136 typedef typename iterator_traits<_ForwardIterator2>::reference 00137 _ReferenceType2; 00138 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value 00139 && __are_same<_ValueType1&, _ReferenceType1>::__value 00140 && __are_same<_ValueType2&, _ReferenceType2>::__value>:: 00141 iter_swap(__a, __b); 00142 } 00143 00144 /** 00145 * @brief Swap the elements of two sequences. 00146 * @ingroup mutating_algorithms 00147 * @param first1 A forward iterator. 00148 * @param last1 A forward iterator. 00149 * @param first2 A forward iterator. 00150 * @return An iterator equal to @p first2+(last1-first1). 00151 * 00152 * Swaps each element in the range @p [first1,last1) with the 00153 * corresponding element in the range @p [first2,(last1-first1)). 00154 * The ranges must not overlap. 00155 */ 00156 template<typename _ForwardIterator1, typename _ForwardIterator2> 00157 _ForwardIterator2 00158 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00159 _ForwardIterator2 __first2) 00160 { 00161 // concept requirements 00162 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00163 _ForwardIterator1>) 00164 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00165 _ForwardIterator2>) 00166 __glibcxx_requires_valid_range(__first1, __last1); 00167 00168 for (; __first1 != __last1; ++__first1, ++__first2) 00169 std::iter_swap(__first1, __first2); 00170 return __first2; 00171 } 00172 00173 /** 00174 * @brief This does what you think it does. 00175 * @ingroup sorting_algorithms 00176 * @param a A thing of arbitrary type. 00177 * @param b Another thing of arbitrary type. 00178 * @return The lesser of the parameters. 00179 * 00180 * This is the simple classic generic implementation. It will work on 00181 * temporary expressions, since they are only evaluated once, unlike a 00182 * preprocessor macro. 00183 */ 00184 template<typename _Tp> 00185 inline const _Tp& 00186 min(const _Tp& __a, const _Tp& __b) 00187 { 00188 // concept requirements 00189 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 00190 //return __b < __a ? __b : __a; 00191 if (__b < __a) 00192 return __b; 00193 return __a; 00194 } 00195 00196 /** 00197 * @brief This does what you think it does. 00198 * @ingroup sorting_algorithms 00199 * @param a A thing of arbitrary type. 00200 * @param b Another thing of arbitrary type. 00201 * @return The greater of the parameters. 00202 * 00203 * This is the simple classic generic implementation. It will work on 00204 * temporary expressions, since they are only evaluated once, unlike a 00205 * preprocessor macro. 00206 */ 00207 template<typename _Tp> 00208 inline const _Tp& 00209 max(const _Tp& __a, const _Tp& __b) 00210 { 00211 // concept requirements 00212 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 00213 //return __a < __b ? __b : __a; 00214 if (__a < __b) 00215 return __b; 00216 return __a; 00217 } 00218 00219 /** 00220 * @brief This does what you think it does. 00221 * @ingroup sorting_algorithms 00222 * @param a A thing of arbitrary type. 00223 * @param b Another thing of arbitrary type. 00224 * @param comp A @link comparison_functors comparison functor@endlink. 00225 * @return The lesser of the parameters. 00226 * 00227 * This will work on temporary expressions, since they are only evaluated 00228 * once, unlike a preprocessor macro. 00229 */ 00230 template<typename _Tp, typename _Compare> 00231 inline const _Tp& 00232 min(const _Tp& __a, const _Tp& __b, _Compare __comp) 00233 { 00234 //return __comp(__b, __a) ? __b : __a; 00235 if (__comp(__b, __a)) 00236 return __b; 00237 return __a; 00238 } 00239 00240 /** 00241 * @brief This does what you think it does. 00242 * @ingroup sorting_algorithms 00243 * @param a A thing of arbitrary type. 00244 * @param b Another thing of arbitrary type. 00245 * @param comp A @link comparison_functors comparison functor@endlink. 00246 * @return The greater of the parameters. 00247 * 00248 * This will work on temporary expressions, since they are only evaluated 00249 * once, unlike a preprocessor macro. 00250 */ 00251 template<typename _Tp, typename _Compare> 00252 inline const _Tp& 00253 max(const _Tp& __a, const _Tp& __b, _Compare __comp) 00254 { 00255 //return __comp(__a, __b) ? __b : __a; 00256 if (__comp(__a, __b)) 00257 return __b; 00258 return __a; 00259 } 00260 00261 00262 // If _Iterator is a __normal_iterator return its base (a plain pointer, 00263 // normally) otherwise return it untouched. See copy, fill, ... 00264 template<typename _Iterator, 00265 bool _IsNormal = __is_normal_iterator<_Iterator>::__value> 00266 struct __niter_base 00267 { 00268 static _Iterator 00269 __b(_Iterator __it) 00270 { return __it; } 00271 }; 00272 00273 template<typename _Iterator> 00274 struct __niter_base<_Iterator, true> 00275 { 00276 static typename _Iterator::iterator_type 00277 __b(_Iterator __it) 00278 { return __it.base(); } 00279 }; 00280 00281 // Likewise, for move_iterator. 00282 template<typename _Iterator, 00283 bool _IsMove = __is_move_iterator<_Iterator>::__value> 00284 struct __miter_base 00285 { 00286 static _Iterator 00287 __b(_Iterator __it) 00288 { return __it; } 00289 }; 00290 00291 template<typename _Iterator> 00292 struct __miter_base<_Iterator, true> 00293 { 00294 static typename _Iterator::iterator_type 00295 __b(_Iterator __it) 00296 { return __it.base(); } 00297 }; 00298 00299 // All of these auxiliary structs serve two purposes. (1) Replace 00300 // calls to copy with memmove whenever possible. (Memmove, not memcpy, 00301 // because the input and output ranges are permitted to overlap.) 00302 // (2) If we're using random access iterators, then write the loop as 00303 // a for loop with an explicit count. 00304 00305 template<bool, bool, typename> 00306 struct __copy_move 00307 { 00308 template<typename _II, typename _OI> 00309 static _OI 00310 __copy_m(_II __first, _II __last, _OI __result) 00311 { 00312 for (; __first != __last; ++__result, ++__first) 00313 *__result = *__first; 00314 return __result; 00315 } 00316 }; 00317 00318 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00319 template<typename _Category> 00320 struct __copy_move<true, false, _Category> 00321 { 00322 template<typename _II, typename _OI> 00323 static _OI 00324 __copy_m(_II __first, _II __last, _OI __result) 00325 { 00326 for (; __first != __last; ++__result, ++__first) 00327 *__result = std::move(*__first); 00328 return __result; 00329 } 00330 }; 00331 #endif 00332 00333 template<> 00334 struct __copy_move<false, false, random_access_iterator_tag> 00335 { 00336 template<typename _II, typename _OI> 00337 static _OI 00338 __copy_m(_II __first, _II __last, _OI __result) 00339 { 00340 typedef typename iterator_traits<_II>::difference_type _Distance; 00341 for(_Distance __n = __last - __first; __n > 0; --__n) 00342 { 00343 *__result = *__first; 00344 ++__first; 00345 ++__result; 00346 } 00347 return __result; 00348 } 00349 }; 00350 00351 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00352 template<> 00353 struct __copy_move<true, false, random_access_iterator_tag> 00354 { 00355 template<typename _II, typename _OI> 00356 static _OI 00357 __copy_m(_II __first, _II __last, _OI __result) 00358 { 00359 typedef typename iterator_traits<_II>::difference_type _Distance; 00360 for(_Distance __n = __last - __first; __n > 0; --__n) 00361 { 00362 *__result = std::move(*__first); 00363 ++__first; 00364 ++__result; 00365 } 00366 return __result; 00367 } 00368 }; 00369 #endif 00370 00371 template<bool _IsMove> 00372 struct __copy_move<_IsMove, true, random_access_iterator_tag> 00373 { 00374 template<typename _Tp> 00375 static _Tp* 00376 __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result) 00377 { 00378 __builtin_memmove(__result, __first, 00379 sizeof(_Tp) * (__last - __first)); 00380 return __result + (__last - __first); 00381 } 00382 }; 00383 00384 template<bool _IsMove, typename _II, typename _OI> 00385 inline _OI 00386 __copy_move_a(_II __first, _II __last, _OI __result) 00387 { 00388 typedef typename iterator_traits<_II>::value_type _ValueTypeI; 00389 typedef typename iterator_traits<_OI>::value_type _ValueTypeO; 00390 typedef typename iterator_traits<_II>::iterator_category _Category; 00391 const bool __simple = (__is_pod(_ValueTypeI) 00392 && __is_pointer<_II>::__value 00393 && __is_pointer<_OI>::__value 00394 && __are_same<_ValueTypeI, _ValueTypeO>::__value); 00395 00396 return std::__copy_move<_IsMove, __simple, 00397 _Category>::__copy_m(__first, __last, __result); 00398 } 00399 00400 // Helpers for streambuf iterators (either istream or ostream). 00401 // NB: avoid including <iosfwd>, relatively large. 00402 template<typename _CharT> 00403 struct char_traits; 00404 00405 template<typename _CharT, typename _Traits> 00406 class istreambuf_iterator; 00407 00408 template<typename _CharT, typename _Traits> 00409 class ostreambuf_iterator; 00410 00411 template<bool _IsMove, typename _CharT> 00412 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 00413 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 00414 __copy_move_a2(_CharT*, _CharT*, 00415 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 00416 00417 template<bool _IsMove, typename _CharT> 00418 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 00419 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 00420 __copy_move_a2(const _CharT*, const _CharT*, 00421 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 00422 00423 template<bool _IsMove, typename _CharT> 00424 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 00425 _CharT*>::__type 00426 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, 00427 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); 00428 00429 template<bool _IsMove, typename _II, typename _OI> 00430 inline _OI 00431 __copy_move_a2(_II __first, _II __last, _OI __result) 00432 { 00433 return _OI(std::__copy_move_a<_IsMove> 00434 (std::__niter_base<_II>::__b(__first), 00435 std::__niter_base<_II>::__b(__last), 00436 std::__niter_base<_OI>::__b(__result))); 00437 } 00438 00439 /** 00440 * @brief Copies the range [first,last) into result. 00441 * @ingroup mutating_algorithms 00442 * @param first An input iterator. 00443 * @param last An input iterator. 00444 * @param result An output iterator. 00445 * @return result + (first - last) 00446 * 00447 * This inline function will boil down to a call to @c memmove whenever 00448 * possible. Failing that, if random access iterators are passed, then the 00449 * loop count will be known (and therefore a candidate for compiler 00450 * optimizations such as unrolling). Result may not be contained within 00451 * [first,last); the copy_backward function should be used instead. 00452 * 00453 * Note that the end of the output range is permitted to be contained 00454 * within [first,last). 00455 */ 00456 template<typename _II, typename _OI> 00457 inline _OI 00458 copy(_II __first, _II __last, _OI __result) 00459 { 00460 // concept requirements 00461 __glibcxx_function_requires(_InputIteratorConcept<_II>) 00462 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 00463 typename iterator_traits<_II>::value_type>) 00464 __glibcxx_requires_valid_range(__first, __last); 00465 00466 return (std::__copy_move_a2<__is_move_iterator<_II>::__value> 00467 (std::__miter_base<_II>::__b(__first), 00468 std::__miter_base<_II>::__b(__last), __result)); 00469 } 00470 00471 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00472 /** 00473 * @brief Moves the range [first,last) into result. 00474 * @ingroup mutating_algorithms 00475 * @param first An input iterator. 00476 * @param last An input iterator. 00477 * @param result An output iterator. 00478 * @return result + (first - last) 00479 * 00480 * This inline function will boil down to a call to @c memmove whenever 00481 * possible. Failing that, if random access iterators are passed, then the 00482 * loop count will be known (and therefore a candidate for compiler 00483 * optimizations such as unrolling). Result may not be contained within 00484 * [first,last); the move_backward function should be used instead. 00485 * 00486 * Note that the end of the output range is permitted to be contained 00487 * within [first,last). 00488 */ 00489 template<typename _II, typename _OI> 00490 inline _OI 00491 move(_II __first, _II __last, _OI __result) 00492 { 00493 // concept requirements 00494 __glibcxx_function_requires(_InputIteratorConcept<_II>) 00495 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 00496 typename iterator_traits<_II>::value_type>) 00497 __glibcxx_requires_valid_range(__first, __last); 00498 00499 return (std::__copy_move_a2<true> 00500 (std::__miter_base<_II>::__b(__first), 00501 std::__miter_base<_II>::__b(__last), __result)); 00502 } 00503 00504 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) 00505 #else 00506 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) 00507 #endif 00508 00509 template<bool, bool, typename> 00510 struct __copy_move_backward 00511 { 00512 template<typename _BI1, typename _BI2> 00513 static _BI2 00514 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00515 { 00516 while (__first != __last) 00517 *--__result = *--__last; 00518 return __result; 00519 } 00520 }; 00521 00522 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00523 template<typename _Category> 00524 struct __copy_move_backward<true, false, _Category> 00525 { 00526 template<typename _BI1, typename _BI2> 00527 static _BI2 00528 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00529 { 00530 while (__first != __last) 00531 *--__result = std::move(*--__last); 00532 return __result; 00533 } 00534 }; 00535 #endif 00536 00537 template<> 00538 struct __copy_move_backward<false, false, random_access_iterator_tag> 00539 { 00540 template<typename _BI1, typename _BI2> 00541 static _BI2 00542 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00543 { 00544 typename iterator_traits<_BI1>::difference_type __n; 00545 for (__n = __last - __first; __n > 0; --__n) 00546 *--__result = *--__last; 00547 return __result; 00548 } 00549 }; 00550 00551 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00552 template<> 00553 struct __copy_move_backward<true, false, random_access_iterator_tag> 00554 { 00555 template<typename _BI1, typename _BI2> 00556 static _BI2 00557 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00558 { 00559 typename iterator_traits<_BI1>::difference_type __n; 00560 for (__n = __last - __first; __n > 0; --__n) 00561 *--__result = std::move(*--__last); 00562 return __result; 00563 } 00564 }; 00565 #endif 00566 00567 template<bool _IsMove> 00568 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> 00569 { 00570 template<typename _Tp> 00571 static _Tp* 00572 __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result) 00573 { 00574 const ptrdiff_t _Num = __last - __first; 00575 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 00576 return __result - _Num; 00577 } 00578 }; 00579 00580 template<bool _IsMove, typename _BI1, typename _BI2> 00581 inline _BI2 00582 __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) 00583 { 00584 typedef typename iterator_traits<_BI1>::value_type _ValueType1; 00585 typedef typename iterator_traits<_BI2>::value_type _ValueType2; 00586 typedef typename iterator_traits<_BI1>::iterator_category _Category; 00587 const bool __simple = (__is_pod(_ValueType1) 00588 && __is_pointer<_BI1>::__value 00589 && __is_pointer<_BI2>::__value 00590 && __are_same<_ValueType1, _ValueType2>::__value); 00591 00592 return std::__copy_move_backward<_IsMove, __simple, 00593 _Category>::__copy_move_b(__first, 00594 __last, 00595 __result); 00596 } 00597 00598 template<bool _IsMove, typename _BI1, typename _BI2> 00599 inline _BI2 00600 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) 00601 { 00602 return _BI2(std::__copy_move_backward_a<_IsMove> 00603 (std::__niter_base<_BI1>::__b(__first), 00604 std::__niter_base<_BI1>::__b(__last), 00605 std::__niter_base<_BI2>::__b(__result))); 00606 } 00607 00608 /** 00609 * @brief Copies the range [first,last) into result. 00610 * @ingroup mutating_algorithms 00611 * @param first A bidirectional iterator. 00612 * @param last A bidirectional iterator. 00613 * @param result A bidirectional iterator. 00614 * @return result - (first - last) 00615 * 00616 * The function has the same effect as copy, but starts at the end of the 00617 * range and works its way to the start, returning the start of the result. 00618 * This inline function will boil down to a call to @c memmove whenever 00619 * possible. Failing that, if random access iterators are passed, then the 00620 * loop count will be known (and therefore a candidate for compiler 00621 * optimizations such as unrolling). 00622 * 00623 * Result may not be in the range [first,last). Use copy instead. Note 00624 * that the start of the output range may overlap [first,last). 00625 */ 00626 template<typename _BI1, typename _BI2> 00627 inline _BI2 00628 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 00629 { 00630 // concept requirements 00631 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 00632 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 00633 __glibcxx_function_requires(_ConvertibleConcept< 00634 typename iterator_traits<_BI1>::value_type, 00635 typename iterator_traits<_BI2>::value_type>) 00636 __glibcxx_requires_valid_range(__first, __last); 00637 00638 return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> 00639 (std::__miter_base<_BI1>::__b(__first), 00640 std::__miter_base<_BI1>::__b(__last), __result)); 00641 } 00642 00643 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00644 /** 00645 * @brief Moves the range [first,last) into result. 00646 * @ingroup mutating_algorithms 00647 * @param first A bidirectional iterator. 00648 * @param last A bidirectional iterator. 00649 * @param result A bidirectional iterator. 00650 * @return result - (first - last) 00651 * 00652 * The function has the same effect as move, but starts at the end of the 00653 * range and works its way to the start, returning the start of the result. 00654 * This inline function will boil down to a call to @c memmove whenever 00655 * possible. Failing that, if random access iterators are passed, then the 00656 * loop count will be known (and therefore a candidate for compiler 00657 * optimizations such as unrolling). 00658 * 00659 * Result may not be in the range [first,last). Use move instead. Note 00660 * that the start of the output range may overlap [first,last). 00661 */ 00662 template<typename _BI1, typename _BI2> 00663 inline _BI2 00664 move_backward(_BI1 __first, _BI1 __last, _BI2 __result) 00665 { 00666 // concept requirements 00667 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 00668 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 00669 __glibcxx_function_requires(_ConvertibleConcept< 00670 typename iterator_traits<_BI1>::value_type, 00671 typename iterator_traits<_BI2>::value_type>) 00672 __glibcxx_requires_valid_range(__first, __last); 00673 00674 return (std::__copy_move_backward_a2<true> 00675 (std::__miter_base<_BI1>::__b(__first), 00676 std::__miter_base<_BI1>::__b(__last), __result)); 00677 } 00678 00679 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) 00680 #else 00681 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) 00682 #endif 00683 00684 template<typename _ForwardIterator, typename _Tp> 00685 inline typename 00686 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type 00687 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 00688 const _Tp& __value) 00689 { 00690 for (; __first != __last; ++__first) 00691 *__first = __value; 00692 } 00693 00694 template<typename _ForwardIterator, typename _Tp> 00695 inline typename 00696 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type 00697 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 00698 const _Tp& __value) 00699 { 00700 const _Tp __tmp = __value; 00701 for (; __first != __last; ++__first) 00702 *__first = __tmp; 00703 } 00704 00705 // Specialization: for char types we can use memset. 00706 template<typename _Tp> 00707 inline typename 00708 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type 00709 __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c) 00710 { 00711 const _Tp __tmp = __c; 00712 __builtin_memset(__first, static_cast<unsigned char>(__tmp), 00713 __last - __first); 00714 } 00715 00716 /** 00717 * @brief Fills the range [first,last) with copies of value. 00718 * @ingroup mutating_algorithms 00719 * @param first A forward iterator. 00720 * @param last A forward iterator. 00721 * @param value A reference-to-const of arbitrary type. 00722 * @return Nothing. 00723 * 00724 * This function fills a range with copies of the same value. For char 00725 * types filling contiguous areas of memory, this becomes an inline call 00726 * to @c memset or @c wmemset. 00727 */ 00728 template<typename _ForwardIterator, typename _Tp> 00729 inline void 00730 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 00731 { 00732 // concept requirements 00733 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00734 _ForwardIterator>) 00735 __glibcxx_requires_valid_range(__first, __last); 00736 00737 std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first), 00738 std::__niter_base<_ForwardIterator>::__b(__last), __value); 00739 } 00740 00741 template<typename _OutputIterator, typename _Size, typename _Tp> 00742 inline typename 00743 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type 00744 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 00745 { 00746 for (; __n > 0; --__n, ++__first) 00747 *__first = __value; 00748 return __first; 00749 } 00750 00751 template<typename _OutputIterator, typename _Size, typename _Tp> 00752 inline typename 00753 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type 00754 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 00755 { 00756 const _Tp __tmp = __value; 00757 for (; __n > 0; --__n, ++__first) 00758 *__first = __tmp; 00759 return __first; 00760 } 00761 00762 template<typename _Size, typename _Tp> 00763 inline typename 00764 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type 00765 __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c) 00766 { 00767 std::__fill_a(__first, __first + __n, __c); 00768 return __first + __n; 00769 } 00770 00771 /** 00772 * @brief Fills the range [first,first+n) with copies of value. 00773 * @ingroup mutating_algorithms 00774 * @param first An output iterator. 00775 * @param n The count of copies to perform. 00776 * @param value A reference-to-const of arbitrary type. 00777 * @return The iterator at first+n. 00778 * 00779 * This function fills a range with copies of the same value. For char 00780 * types filling contiguous areas of memory, this becomes an inline call 00781 * to @c memset or @ wmemset. 00782 */ 00783 template<typename _OI, typename _Size, typename _Tp> 00784 inline _OI 00785 fill_n(_OI __first, _Size __n, const _Tp& __value) 00786 { 00787 // concept requirements 00788 __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) 00789 00790 return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first), 00791 __n, __value)); 00792 } 00793 00794 template<bool _BoolType> 00795 struct __equal 00796 { 00797 template<typename _II1, typename _II2> 00798 static bool 00799 equal(_II1 __first1, _II1 __last1, _II2 __first2) 00800 { 00801 for (; __first1 != __last1; ++__first1, ++__first2) 00802 if (!(*__first1 == *__first2)) 00803 return false; 00804 return true; 00805 } 00806 }; 00807 00808 template<> 00809 struct __equal<true> 00810 { 00811 template<typename _Tp> 00812 static bool 00813 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) 00814 { 00815 return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) 00816 * (__last1 - __first1)); 00817 } 00818 }; 00819 00820 template<typename _II1, typename _II2> 00821 inline bool 00822 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) 00823 { 00824 typedef typename iterator_traits<_II1>::value_type _ValueType1; 00825 typedef typename iterator_traits<_II2>::value_type _ValueType2; 00826 const bool __simple = (__is_integer<_ValueType1>::__value 00827 && __is_pointer<_II1>::__value 00828 && __is_pointer<_II2>::__value 00829 && __are_same<_ValueType1, _ValueType2>::__value); 00830 00831 return std::__equal<__simple>::equal(__first1, __last1, __first2); 00832 } 00833 00834 00835 template<typename, typename> 00836 struct __lc_rai 00837 { 00838 template<typename _II1, typename _II2> 00839 static _II1 00840 __newlast1(_II1, _II1 __last1, _II2, _II2) 00841 { return __last1; } 00842 00843 template<typename _II> 00844 static bool 00845 __cnd2(_II __first, _II __last) 00846 { return __first != __last; } 00847 }; 00848 00849 template<> 00850 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> 00851 { 00852 template<typename _RAI1, typename _RAI2> 00853 static _RAI1 00854 __newlast1(_RAI1 __first1, _RAI1 __last1, 00855 _RAI2 __first2, _RAI2 __last2) 00856 { 00857 const typename iterator_traits<_RAI1>::difference_type 00858 __diff1 = __last1 - __first1; 00859 const typename iterator_traits<_RAI2>::difference_type 00860 __diff2 = __last2 - __first2; 00861 return __diff2 < __diff1 ? __first1 + __diff2 : __last1; 00862 } 00863 00864 template<typename _RAI> 00865 static bool 00866 __cnd2(_RAI, _RAI) 00867 { return true; } 00868 }; 00869 00870 template<bool _BoolType> 00871 struct __lexicographical_compare 00872 { 00873 template<typename _II1, typename _II2> 00874 static bool __lc(_II1, _II1, _II2, _II2); 00875 }; 00876 00877 template<bool _BoolType> 00878 template<typename _II1, typename _II2> 00879 bool 00880 __lexicographical_compare<_BoolType>:: 00881 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 00882 { 00883 typedef typename iterator_traits<_II1>::iterator_category _Category1; 00884 typedef typename iterator_traits<_II2>::iterator_category _Category2; 00885 typedef std::__lc_rai<_Category1, _Category2> __rai_type; 00886 00887 __last1 = __rai_type::__newlast1(__first1, __last1, 00888 __first2, __last2); 00889 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); 00890 ++__first1, ++__first2) 00891 { 00892 if (*__first1 < *__first2) 00893 return true; 00894 if (*__first2 < *__first1) 00895 return false; 00896 } 00897 return __first1 == __last1 && __first2 != __last2; 00898 } 00899 00900 template<> 00901 struct __lexicographical_compare<true> 00902 { 00903 template<typename _Tp, typename _Up> 00904 static bool 00905 __lc(const _Tp* __first1, const _Tp* __last1, 00906 const _Up* __first2, const _Up* __last2) 00907 { 00908 const size_t __len1 = __last1 - __first1; 00909 const size_t __len2 = __last2 - __first2; 00910 const int __result = __builtin_memcmp(__first1, __first2, 00911 std::min(__len1, __len2)); 00912 return __result != 0 ? __result < 0 : __len1 < __len2; 00913 } 00914 }; 00915 00916 template<typename _II1, typename _II2> 00917 inline bool 00918 __lexicographical_compare_aux(_II1 __first1, _II1 __last1, 00919 _II2 __first2, _II2 __last2) 00920 { 00921 typedef typename iterator_traits<_II1>::value_type _ValueType1; 00922 typedef typename iterator_traits<_II2>::value_type _ValueType2; 00923 const bool __simple = 00924 (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value 00925 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed 00926 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed 00927 && __is_pointer<_II1>::__value 00928 && __is_pointer<_II2>::__value); 00929 00930 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, 00931 __first2, __last2); 00932 } 00933 00934 _GLIBCXX_END_NAMESPACE 00935 00936 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) 00937 00938 /** 00939 * @brief Tests a range for element-wise equality. 00940 * @ingroup non_mutating_algorithms 00941 * @param first1 An input iterator. 00942 * @param last1 An input iterator. 00943 * @param first2 An input iterator. 00944 * @return A boolean true or false. 00945 * 00946 * This compares the elements of two ranges using @c == and returns true or 00947 * false depending on whether all of the corresponding elements of the 00948 * ranges are equal. 00949 */ 00950 template<typename _II1, typename _II2> 00951 inline bool 00952 equal(_II1 __first1, _II1 __last1, _II2 __first2) 00953 { 00954 // concept requirements 00955 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 00956 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 00957 __glibcxx_function_requires(_EqualOpConcept< 00958 typename iterator_traits<_II1>::value_type, 00959 typename iterator_traits<_II2>::value_type>) 00960 __glibcxx_requires_valid_range(__first1, __last1); 00961 00962 return std::__equal_aux(std::__niter_base<_II1>::__b(__first1), 00963 std::__niter_base<_II1>::__b(__last1), 00964 std::__niter_base<_II2>::__b(__first2)); 00965 } 00966 00967 /** 00968 * @brief Tests a range for element-wise equality. 00969 * @ingroup non_mutating_algorithms 00970 * @param first1 An input iterator. 00971 * @param last1 An input iterator. 00972 * @param first2 An input iterator. 00973 * @param binary_pred A binary predicate @link functors 00974 * functor@endlink. 00975 * @return A boolean true or false. 00976 * 00977 * This compares the elements of two ranges using the binary_pred 00978 * parameter, and returns true or 00979 * false depending on whether all of the corresponding elements of the 00980 * ranges are equal. 00981 */ 00982 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 00983 inline bool 00984 equal(_IIter1 __first1, _IIter1 __last1, 00985 _IIter2 __first2, _BinaryPredicate __binary_pred) 00986 { 00987 // concept requirements 00988 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 00989 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 00990 __glibcxx_requires_valid_range(__first1, __last1); 00991 00992 for (; __first1 != __last1; ++__first1, ++__first2) 00993 if (!bool(__binary_pred(*__first1, *__first2))) 00994 return false; 00995 return true; 00996 } 00997 00998 /** 00999 * @brief Performs "dictionary" comparison on ranges. 01000 * @ingroup sorting_algorithms 01001 * @param first1 An input iterator. 01002 * @param last1 An input iterator. 01003 * @param first2 An input iterator. 01004 * @param last2 An input iterator. 01005 * @return A boolean true or false. 01006 * 01007 * "Returns true if the sequence of elements defined by the range 01008 * [first1,last1) is lexicographically less than the sequence of elements 01009 * defined by the range [first2,last2). Returns false otherwise." 01010 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 01011 * then this is an inline call to @c memcmp. 01012 */ 01013 template<typename _II1, typename _II2> 01014 inline bool 01015 lexicographical_compare(_II1 __first1, _II1 __last1, 01016 _II2 __first2, _II2 __last2) 01017 { 01018 // concept requirements 01019 typedef typename iterator_traits<_II1>::value_type _ValueType1; 01020 typedef typename iterator_traits<_II2>::value_type _ValueType2; 01021 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 01022 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 01023 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 01024 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 01025 __glibcxx_requires_valid_range(__first1, __last1); 01026 __glibcxx_requires_valid_range(__first2, __last2); 01027 01028 return std::__lexicographical_compare_aux 01029 (std::__niter_base<_II1>::__b(__first1), 01030 std::__niter_base<_II1>::__b(__last1), 01031 std::__niter_base<_II2>::__b(__first2), 01032 std::__niter_base<_II2>::__b(__last2)); 01033 } 01034 01035 /** 01036 * @brief Performs "dictionary" comparison on ranges. 01037 * @ingroup sorting_algorithms 01038 * @param first1 An input iterator. 01039 * @param last1 An input iterator. 01040 * @param first2 An input iterator. 01041 * @param last2 An input iterator. 01042 * @param comp A @link comparison_functors comparison functor@endlink. 01043 * @return A boolean true or false. 01044 * 01045 * The same as the four-parameter @c lexicographical_compare, but uses the 01046 * comp parameter instead of @c <. 01047 */ 01048 template<typename _II1, typename _II2, typename _Compare> 01049 bool 01050 lexicographical_compare(_II1 __first1, _II1 __last1, 01051 _II2 __first2, _II2 __last2, _Compare __comp) 01052 { 01053 typedef typename iterator_traits<_II1>::iterator_category _Category1; 01054 typedef typename iterator_traits<_II2>::iterator_category _Category2; 01055 typedef std::__lc_rai<_Category1, _Category2> __rai_type; 01056 01057 // concept requirements 01058 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 01059 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 01060 __glibcxx_requires_valid_range(__first1, __last1); 01061 __glibcxx_requires_valid_range(__first2, __last2); 01062 01063 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); 01064 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); 01065 ++__first1, ++__first2) 01066 { 01067 if (__comp(*__first1, *__first2)) 01068 return true; 01069 if (__comp(*__first2, *__first1)) 01070 return false; 01071 } 01072 return __first1 == __last1 && __first2 != __last2; 01073 } 01074 01075 /** 01076 * @brief Finds the places in ranges which don't match. 01077 * @ingroup non_mutating_algorithms 01078 * @param first1 An input iterator. 01079 * @param last1 An input iterator. 01080 * @param first2 An input iterator. 01081 * @return A pair of iterators pointing to the first mismatch. 01082 * 01083 * This compares the elements of two ranges using @c == and returns a pair 01084 * of iterators. The first iterator points into the first range, the 01085 * second iterator points into the second range, and the elements pointed 01086 * to by the iterators are not equal. 01087 */ 01088 template<typename _InputIterator1, typename _InputIterator2> 01089 pair<_InputIterator1, _InputIterator2> 01090 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01091 _InputIterator2 __first2) 01092 { 01093 // concept requirements 01094 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 01095 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 01096 __glibcxx_function_requires(_EqualOpConcept< 01097 typename iterator_traits<_InputIterator1>::value_type, 01098 typename iterator_traits<_InputIterator2>::value_type>) 01099 __glibcxx_requires_valid_range(__first1, __last1); 01100 01101 while (__first1 != __last1 && *__first1 == *__first2) 01102 { 01103 ++__first1; 01104 ++__first2; 01105 } 01106 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 01107 } 01108 01109 /** 01110 * @brief Finds the places in ranges which don't match. 01111 * @ingroup non_mutating_algorithms 01112 * @param first1 An input iterator. 01113 * @param last1 An input iterator. 01114 * @param first2 An input iterator. 01115 * @param binary_pred A binary predicate @link functors 01116 * functor@endlink. 01117 * @return A pair of iterators pointing to the first mismatch. 01118 * 01119 * This compares the elements of two ranges using the binary_pred 01120 * parameter, and returns a pair 01121 * of iterators. The first iterator points into the first range, the 01122 * second iterator points into the second range, and the elements pointed 01123 * to by the iterators are not equal. 01124 */ 01125 template<typename _InputIterator1, typename _InputIterator2, 01126 typename _BinaryPredicate> 01127 pair<_InputIterator1, _InputIterator2> 01128 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01129 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 01130 { 01131 // concept requirements 01132 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 01133 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 01134 __glibcxx_requires_valid_range(__first1, __last1); 01135 01136 while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2))) 01137 { 01138 ++__first1; 01139 ++__first2; 01140 } 01141 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 01142 } 01143 01144 _GLIBCXX_END_NESTED_NAMESPACE 01145 01146 // NB: This file is included within many other C++ includes, as a way 01147 // of getting the base algorithms. So, make sure that parallel bits 01148 // come in too if requested. 01149 #ifdef _GLIBCXX_PARALLEL 01150 # include <parallel/algobase.h> 01151 #endif 01152 01153 #endif