libstdc++
|
00001 // Core algorithmic facilities -*- C++ -*- 00002 00003 // Copyright (C) 2001-2017 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996-1998 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/stl_algobase.h 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{algorithm} 00054 */ 00055 00056 #ifndef _STL_ALGOBASE_H 00057 #define _STL_ALGOBASE_H 1 00058 00059 #include <bits/c++config.h> 00060 #include <bits/functexcept.h> 00061 #include <bits/cpp_type_traits.h> 00062 #include <ext/type_traits.h> 00063 #include <ext/numeric_traits.h> 00064 #include <bits/stl_pair.h> 00065 #include <bits/stl_iterator_base_types.h> 00066 #include <bits/stl_iterator_base_funcs.h> 00067 #include <bits/stl_iterator.h> 00068 #include <bits/concept_check.h> 00069 #include <debug/debug.h> 00070 #include <bits/move.h> // For std::swap and _GLIBCXX_MOVE 00071 #include <bits/predefined_ops.h> 00072 00073 namespace std _GLIBCXX_VISIBILITY(default) 00074 { 00075 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00076 00077 #if __cplusplus < 201103L 00078 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a 00079 // nutshell, we are partially implementing the resolution of DR 187, 00080 // when it's safe, i.e., the value_types are equal. 00081 template<bool _BoolType> 00082 struct __iter_swap 00083 { 00084 template<typename _ForwardIterator1, typename _ForwardIterator2> 00085 static void 00086 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 00087 { 00088 typedef typename iterator_traits<_ForwardIterator1>::value_type 00089 _ValueType1; 00090 _ValueType1 __tmp = _GLIBCXX_MOVE(*__a); 00091 *__a = _GLIBCXX_MOVE(*__b); 00092 *__b = _GLIBCXX_MOVE(__tmp); 00093 } 00094 }; 00095 00096 template<> 00097 struct __iter_swap<true> 00098 { 00099 template<typename _ForwardIterator1, typename _ForwardIterator2> 00100 static void 00101 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 00102 { 00103 swap(*__a, *__b); 00104 } 00105 }; 00106 #endif 00107 00108 /** 00109 * @brief Swaps the contents of two iterators. 00110 * @ingroup mutating_algorithms 00111 * @param __a An iterator. 00112 * @param __b Another iterator. 00113 * @return Nothing. 00114 * 00115 * This function swaps the values pointed to by two iterators, not the 00116 * iterators themselves. 00117 */ 00118 template<typename _ForwardIterator1, typename _ForwardIterator2> 00119 inline void 00120 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 00121 { 00122 // concept requirements 00123 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00124 _ForwardIterator1>) 00125 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00126 _ForwardIterator2>) 00127 00128 #if __cplusplus < 201103L 00129 typedef typename iterator_traits<_ForwardIterator1>::value_type 00130 _ValueType1; 00131 typedef typename iterator_traits<_ForwardIterator2>::value_type 00132 _ValueType2; 00133 00134 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, 00135 _ValueType2>) 00136 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, 00137 _ValueType1>) 00138 00139 typedef typename iterator_traits<_ForwardIterator1>::reference 00140 _ReferenceType1; 00141 typedef typename iterator_traits<_ForwardIterator2>::reference 00142 _ReferenceType2; 00143 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value 00144 && __are_same<_ValueType1&, _ReferenceType1>::__value 00145 && __are_same<_ValueType2&, _ReferenceType2>::__value>:: 00146 iter_swap(__a, __b); 00147 #else 00148 swap(*__a, *__b); 00149 #endif 00150 } 00151 00152 /** 00153 * @brief Swap the elements of two sequences. 00154 * @ingroup mutating_algorithms 00155 * @param __first1 A forward iterator. 00156 * @param __last1 A forward iterator. 00157 * @param __first2 A forward iterator. 00158 * @return An iterator equal to @p first2+(last1-first1). 00159 * 00160 * Swaps each element in the range @p [first1,last1) with the 00161 * corresponding element in the range @p [first2,(last1-first1)). 00162 * The ranges must not overlap. 00163 */ 00164 template<typename _ForwardIterator1, typename _ForwardIterator2> 00165 _ForwardIterator2 00166 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00167 _ForwardIterator2 __first2) 00168 { 00169 // concept requirements 00170 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00171 _ForwardIterator1>) 00172 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00173 _ForwardIterator2>) 00174 __glibcxx_requires_valid_range(__first1, __last1); 00175 00176 for (; __first1 != __last1; ++__first1, (void)++__first2) 00177 std::iter_swap(__first1, __first2); 00178 return __first2; 00179 } 00180 00181 /** 00182 * @brief This does what you think it does. 00183 * @ingroup sorting_algorithms 00184 * @param __a A thing of arbitrary type. 00185 * @param __b Another thing of arbitrary type. 00186 * @return The lesser of the parameters. 00187 * 00188 * This is the simple classic generic implementation. It will work on 00189 * temporary expressions, since they are only evaluated once, unlike a 00190 * preprocessor macro. 00191 */ 00192 template<typename _Tp> 00193 _GLIBCXX14_CONSTEXPR 00194 inline const _Tp& 00195 min(const _Tp& __a, const _Tp& __b) 00196 { 00197 // concept requirements 00198 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 00199 //return __b < __a ? __b : __a; 00200 if (__b < __a) 00201 return __b; 00202 return __a; 00203 } 00204 00205 /** 00206 * @brief This does what you think it does. 00207 * @ingroup sorting_algorithms 00208 * @param __a A thing of arbitrary type. 00209 * @param __b Another thing of arbitrary type. 00210 * @return The greater of the parameters. 00211 * 00212 * This is the simple classic generic implementation. It will work on 00213 * temporary expressions, since they are only evaluated once, unlike a 00214 * preprocessor macro. 00215 */ 00216 template<typename _Tp> 00217 _GLIBCXX14_CONSTEXPR 00218 inline const _Tp& 00219 max(const _Tp& __a, const _Tp& __b) 00220 { 00221 // concept requirements 00222 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 00223 //return __a < __b ? __b : __a; 00224 if (__a < __b) 00225 return __b; 00226 return __a; 00227 } 00228 00229 /** 00230 * @brief This does what you think it does. 00231 * @ingroup sorting_algorithms 00232 * @param __a A thing of arbitrary type. 00233 * @param __b Another thing of arbitrary type. 00234 * @param __comp A @link comparison_functors comparison functor@endlink. 00235 * @return The lesser of the parameters. 00236 * 00237 * This will work on temporary expressions, since they are only evaluated 00238 * once, unlike a preprocessor macro. 00239 */ 00240 template<typename _Tp, typename _Compare> 00241 _GLIBCXX14_CONSTEXPR 00242 inline const _Tp& 00243 min(const _Tp& __a, const _Tp& __b, _Compare __comp) 00244 { 00245 //return __comp(__b, __a) ? __b : __a; 00246 if (__comp(__b, __a)) 00247 return __b; 00248 return __a; 00249 } 00250 00251 /** 00252 * @brief This does what you think it does. 00253 * @ingroup sorting_algorithms 00254 * @param __a A thing of arbitrary type. 00255 * @param __b Another thing of arbitrary type. 00256 * @param __comp A @link comparison_functors comparison functor@endlink. 00257 * @return The greater of the parameters. 00258 * 00259 * This will work on temporary expressions, since they are only evaluated 00260 * once, unlike a preprocessor macro. 00261 */ 00262 template<typename _Tp, typename _Compare> 00263 _GLIBCXX14_CONSTEXPR 00264 inline const _Tp& 00265 max(const _Tp& __a, const _Tp& __b, _Compare __comp) 00266 { 00267 //return __comp(__a, __b) ? __b : __a; 00268 if (__comp(__a, __b)) 00269 return __b; 00270 return __a; 00271 } 00272 00273 // Fallback implementation of the function in bits/stl_iterator.h used to 00274 // remove the __normal_iterator wrapper. See copy, fill, ... 00275 template<typename _Iterator> 00276 inline _Iterator 00277 __niter_base(_Iterator __it) 00278 { return __it; } 00279 00280 // All of these auxiliary structs serve two purposes. (1) Replace 00281 // calls to copy with memmove whenever possible. (Memmove, not memcpy, 00282 // because the input and output ranges are permitted to overlap.) 00283 // (2) If we're using random access iterators, then write the loop as 00284 // a for loop with an explicit count. 00285 00286 template<bool, bool, typename> 00287 struct __copy_move 00288 { 00289 template<typename _II, typename _OI> 00290 static _OI 00291 __copy_m(_II __first, _II __last, _OI __result) 00292 { 00293 for (; __first != __last; ++__result, (void)++__first) 00294 *__result = *__first; 00295 return __result; 00296 } 00297 }; 00298 00299 #if __cplusplus >= 201103L 00300 template<typename _Category> 00301 struct __copy_move<true, false, _Category> 00302 { 00303 template<typename _II, typename _OI> 00304 static _OI 00305 __copy_m(_II __first, _II __last, _OI __result) 00306 { 00307 for (; __first != __last; ++__result, (void)++__first) 00308 *__result = std::move(*__first); 00309 return __result; 00310 } 00311 }; 00312 #endif 00313 00314 template<> 00315 struct __copy_move<false, false, random_access_iterator_tag> 00316 { 00317 template<typename _II, typename _OI> 00318 static _OI 00319 __copy_m(_II __first, _II __last, _OI __result) 00320 { 00321 typedef typename iterator_traits<_II>::difference_type _Distance; 00322 for(_Distance __n = __last - __first; __n > 0; --__n) 00323 { 00324 *__result = *__first; 00325 ++__first; 00326 ++__result; 00327 } 00328 return __result; 00329 } 00330 }; 00331 00332 #if __cplusplus >= 201103L 00333 template<> 00334 struct __copy_move<true, 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 = std::move(*__first); 00344 ++__first; 00345 ++__result; 00346 } 00347 return __result; 00348 } 00349 }; 00350 #endif 00351 00352 template<bool _IsMove> 00353 struct __copy_move<_IsMove, true, random_access_iterator_tag> 00354 { 00355 template<typename _Tp> 00356 static _Tp* 00357 __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result) 00358 { 00359 #if __cplusplus >= 201103L 00360 using __assignable = conditional<_IsMove, 00361 is_move_assignable<_Tp>, 00362 is_copy_assignable<_Tp>>; 00363 // trivial types can have deleted assignment 00364 static_assert( __assignable::type::value, "type is not assignable" ); 00365 #endif 00366 const ptrdiff_t _Num = __last - __first; 00367 if (_Num) 00368 __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); 00369 return __result + _Num; 00370 } 00371 }; 00372 00373 template<bool _IsMove, typename _II, typename _OI> 00374 inline _OI 00375 __copy_move_a(_II __first, _II __last, _OI __result) 00376 { 00377 typedef typename iterator_traits<_II>::value_type _ValueTypeI; 00378 typedef typename iterator_traits<_OI>::value_type _ValueTypeO; 00379 typedef typename iterator_traits<_II>::iterator_category _Category; 00380 const bool __simple = (__is_trivial(_ValueTypeI) 00381 && __is_pointer<_II>::__value 00382 && __is_pointer<_OI>::__value 00383 && __are_same<_ValueTypeI, _ValueTypeO>::__value); 00384 00385 return std::__copy_move<_IsMove, __simple, 00386 _Category>::__copy_m(__first, __last, __result); 00387 } 00388 00389 // Helpers for streambuf iterators (either istream or ostream). 00390 // NB: avoid including <iosfwd>, relatively large. 00391 template<typename _CharT> 00392 struct char_traits; 00393 00394 template<typename _CharT, typename _Traits> 00395 class istreambuf_iterator; 00396 00397 template<typename _CharT, typename _Traits> 00398 class ostreambuf_iterator; 00399 00400 template<bool _IsMove, typename _CharT> 00401 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 00402 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 00403 __copy_move_a2(_CharT*, _CharT*, 00404 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 00405 00406 template<bool _IsMove, typename _CharT> 00407 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 00408 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 00409 __copy_move_a2(const _CharT*, const _CharT*, 00410 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 00411 00412 template<bool _IsMove, typename _CharT> 00413 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 00414 _CharT*>::__type 00415 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, 00416 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); 00417 00418 template<bool _IsMove, typename _II, typename _OI> 00419 inline _OI 00420 __copy_move_a2(_II __first, _II __last, _OI __result) 00421 { 00422 return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first), 00423 std::__niter_base(__last), 00424 std::__niter_base(__result))); 00425 } 00426 00427 /** 00428 * @brief Copies the range [first,last) into result. 00429 * @ingroup mutating_algorithms 00430 * @param __first An input iterator. 00431 * @param __last An input iterator. 00432 * @param __result An output iterator. 00433 * @return result + (first - last) 00434 * 00435 * This inline function will boil down to a call to @c memmove whenever 00436 * possible. Failing that, if random access iterators are passed, then the 00437 * loop count will be known (and therefore a candidate for compiler 00438 * optimizations such as unrolling). Result may not be contained within 00439 * [first,last); the copy_backward function should be used instead. 00440 * 00441 * Note that the end of the output range is permitted to be contained 00442 * within [first,last). 00443 */ 00444 template<typename _II, typename _OI> 00445 inline _OI 00446 copy(_II __first, _II __last, _OI __result) 00447 { 00448 // concept requirements 00449 __glibcxx_function_requires(_InputIteratorConcept<_II>) 00450 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 00451 typename iterator_traits<_II>::value_type>) 00452 __glibcxx_requires_valid_range(__first, __last); 00453 00454 return (std::__copy_move_a2<__is_move_iterator<_II>::__value> 00455 (std::__miter_base(__first), std::__miter_base(__last), 00456 __result)); 00457 } 00458 00459 #if __cplusplus >= 201103L 00460 /** 00461 * @brief Moves the range [first,last) into result. 00462 * @ingroup mutating_algorithms 00463 * @param __first An input iterator. 00464 * @param __last An input iterator. 00465 * @param __result An output iterator. 00466 * @return result + (first - last) 00467 * 00468 * This inline function will boil down to a call to @c memmove whenever 00469 * possible. Failing that, if random access iterators are passed, then the 00470 * loop count will be known (and therefore a candidate for compiler 00471 * optimizations such as unrolling). Result may not be contained within 00472 * [first,last); the move_backward function should be used instead. 00473 * 00474 * Note that the end of the output range is permitted to be contained 00475 * within [first,last). 00476 */ 00477 template<typename _II, typename _OI> 00478 inline _OI 00479 move(_II __first, _II __last, _OI __result) 00480 { 00481 // concept requirements 00482 __glibcxx_function_requires(_InputIteratorConcept<_II>) 00483 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 00484 typename iterator_traits<_II>::value_type>) 00485 __glibcxx_requires_valid_range(__first, __last); 00486 00487 return std::__copy_move_a2<true>(std::__miter_base(__first), 00488 std::__miter_base(__last), __result); 00489 } 00490 00491 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) 00492 #else 00493 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) 00494 #endif 00495 00496 template<bool, bool, typename> 00497 struct __copy_move_backward 00498 { 00499 template<typename _BI1, typename _BI2> 00500 static _BI2 00501 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00502 { 00503 while (__first != __last) 00504 *--__result = *--__last; 00505 return __result; 00506 } 00507 }; 00508 00509 #if __cplusplus >= 201103L 00510 template<typename _Category> 00511 struct __copy_move_backward<true, false, _Category> 00512 { 00513 template<typename _BI1, typename _BI2> 00514 static _BI2 00515 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00516 { 00517 while (__first != __last) 00518 *--__result = std::move(*--__last); 00519 return __result; 00520 } 00521 }; 00522 #endif 00523 00524 template<> 00525 struct __copy_move_backward<false, false, random_access_iterator_tag> 00526 { 00527 template<typename _BI1, typename _BI2> 00528 static _BI2 00529 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00530 { 00531 typename iterator_traits<_BI1>::difference_type __n; 00532 for (__n = __last - __first; __n > 0; --__n) 00533 *--__result = *--__last; 00534 return __result; 00535 } 00536 }; 00537 00538 #if __cplusplus >= 201103L 00539 template<> 00540 struct __copy_move_backward<true, false, random_access_iterator_tag> 00541 { 00542 template<typename _BI1, typename _BI2> 00543 static _BI2 00544 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 00545 { 00546 typename iterator_traits<_BI1>::difference_type __n; 00547 for (__n = __last - __first; __n > 0; --__n) 00548 *--__result = std::move(*--__last); 00549 return __result; 00550 } 00551 }; 00552 #endif 00553 00554 template<bool _IsMove> 00555 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> 00556 { 00557 template<typename _Tp> 00558 static _Tp* 00559 __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result) 00560 { 00561 #if __cplusplus >= 201103L 00562 using __assignable = conditional<_IsMove, 00563 is_move_assignable<_Tp>, 00564 is_copy_assignable<_Tp>>; 00565 // trivial types can have deleted assignment 00566 static_assert( __assignable::type::value, "type is not assignable" ); 00567 #endif 00568 const ptrdiff_t _Num = __last - __first; 00569 if (_Num) 00570 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 00571 return __result - _Num; 00572 } 00573 }; 00574 00575 template<bool _IsMove, typename _BI1, typename _BI2> 00576 inline _BI2 00577 __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) 00578 { 00579 typedef typename iterator_traits<_BI1>::value_type _ValueType1; 00580 typedef typename iterator_traits<_BI2>::value_type _ValueType2; 00581 typedef typename iterator_traits<_BI1>::iterator_category _Category; 00582 const bool __simple = (__is_trivial(_ValueType1) 00583 && __is_pointer<_BI1>::__value 00584 && __is_pointer<_BI2>::__value 00585 && __are_same<_ValueType1, _ValueType2>::__value); 00586 00587 return std::__copy_move_backward<_IsMove, __simple, 00588 _Category>::__copy_move_b(__first, 00589 __last, 00590 __result); 00591 } 00592 00593 template<bool _IsMove, typename _BI1, typename _BI2> 00594 inline _BI2 00595 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) 00596 { 00597 return _BI2(std::__copy_move_backward_a<_IsMove> 00598 (std::__niter_base(__first), std::__niter_base(__last), 00599 std::__niter_base(__result))); 00600 } 00601 00602 /** 00603 * @brief Copies the range [first,last) into result. 00604 * @ingroup mutating_algorithms 00605 * @param __first A bidirectional iterator. 00606 * @param __last A bidirectional iterator. 00607 * @param __result A bidirectional iterator. 00608 * @return result - (first - last) 00609 * 00610 * The function has the same effect as copy, but starts at the end of the 00611 * range and works its way to the start, returning the start of the result. 00612 * This inline function will boil down to a call to @c memmove whenever 00613 * possible. Failing that, if random access iterators are passed, then the 00614 * loop count will be known (and therefore a candidate for compiler 00615 * optimizations such as unrolling). 00616 * 00617 * Result may not be in the range (first,last]. Use copy instead. Note 00618 * that the start of the output range may overlap [first,last). 00619 */ 00620 template<typename _BI1, typename _BI2> 00621 inline _BI2 00622 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 00623 { 00624 // concept requirements 00625 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 00626 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 00627 __glibcxx_function_requires(_ConvertibleConcept< 00628 typename iterator_traits<_BI1>::value_type, 00629 typename iterator_traits<_BI2>::value_type>) 00630 __glibcxx_requires_valid_range(__first, __last); 00631 00632 return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> 00633 (std::__miter_base(__first), std::__miter_base(__last), 00634 __result)); 00635 } 00636 00637 #if __cplusplus >= 201103L 00638 /** 00639 * @brief Moves the range [first,last) into result. 00640 * @ingroup mutating_algorithms 00641 * @param __first A bidirectional iterator. 00642 * @param __last A bidirectional iterator. 00643 * @param __result A bidirectional iterator. 00644 * @return result - (first - last) 00645 * 00646 * The function has the same effect as move, but starts at the end of the 00647 * range and works its way to the start, returning the start of the result. 00648 * This inline function will boil down to a call to @c memmove whenever 00649 * possible. Failing that, if random access iterators are passed, then the 00650 * loop count will be known (and therefore a candidate for compiler 00651 * optimizations such as unrolling). 00652 * 00653 * Result may not be in the range (first,last]. Use move instead. Note 00654 * that the start of the output range may overlap [first,last). 00655 */ 00656 template<typename _BI1, typename _BI2> 00657 inline _BI2 00658 move_backward(_BI1 __first, _BI1 __last, _BI2 __result) 00659 { 00660 // concept requirements 00661 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 00662 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 00663 __glibcxx_function_requires(_ConvertibleConcept< 00664 typename iterator_traits<_BI1>::value_type, 00665 typename iterator_traits<_BI2>::value_type>) 00666 __glibcxx_requires_valid_range(__first, __last); 00667 00668 return std::__copy_move_backward_a2<true>(std::__miter_base(__first), 00669 std::__miter_base(__last), 00670 __result); 00671 } 00672 00673 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) 00674 #else 00675 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) 00676 #endif 00677 00678 template<typename _ForwardIterator, typename _Tp> 00679 inline typename 00680 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type 00681 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 00682 const _Tp& __value) 00683 { 00684 for (; __first != __last; ++__first) 00685 *__first = __value; 00686 } 00687 00688 template<typename _ForwardIterator, typename _Tp> 00689 inline typename 00690 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type 00691 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 00692 const _Tp& __value) 00693 { 00694 const _Tp __tmp = __value; 00695 for (; __first != __last; ++__first) 00696 *__first = __tmp; 00697 } 00698 00699 // Specialization: for char types we can use memset. 00700 template<typename _Tp> 00701 inline typename 00702 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type 00703 __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c) 00704 { 00705 const _Tp __tmp = __c; 00706 if (const size_t __len = __last - __first) 00707 __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len); 00708 } 00709 00710 /** 00711 * @brief Fills the range [first,last) with copies of value. 00712 * @ingroup mutating_algorithms 00713 * @param __first A forward iterator. 00714 * @param __last A forward iterator. 00715 * @param __value A reference-to-const of arbitrary type. 00716 * @return Nothing. 00717 * 00718 * This function fills a range with copies of the same value. For char 00719 * types filling contiguous areas of memory, this becomes an inline call 00720 * to @c memset or @c wmemset. 00721 */ 00722 template<typename _ForwardIterator, typename _Tp> 00723 inline void 00724 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 00725 { 00726 // concept requirements 00727 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00728 _ForwardIterator>) 00729 __glibcxx_requires_valid_range(__first, __last); 00730 00731 std::__fill_a(std::__niter_base(__first), std::__niter_base(__last), 00732 __value); 00733 } 00734 00735 template<typename _OutputIterator, typename _Size, typename _Tp> 00736 inline typename 00737 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type 00738 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 00739 { 00740 for (__decltype(__n + 0) __niter = __n; 00741 __niter > 0; --__niter, ++__first) 00742 *__first = __value; 00743 return __first; 00744 } 00745 00746 template<typename _OutputIterator, typename _Size, typename _Tp> 00747 inline typename 00748 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type 00749 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 00750 { 00751 const _Tp __tmp = __value; 00752 for (__decltype(__n + 0) __niter = __n; 00753 __niter > 0; --__niter, ++__first) 00754 *__first = __tmp; 00755 return __first; 00756 } 00757 00758 template<typename _Size, typename _Tp> 00759 inline typename 00760 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type 00761 __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c) 00762 { 00763 std::__fill_a(__first, __first + __n, __c); 00764 return __first + __n; 00765 } 00766 00767 /** 00768 * @brief Fills the range [first,first+n) with copies of value. 00769 * @ingroup mutating_algorithms 00770 * @param __first An output iterator. 00771 * @param __n The count of copies to perform. 00772 * @param __value A reference-to-const of arbitrary type. 00773 * @return The iterator at first+n. 00774 * 00775 * This function fills a range with copies of the same value. For char 00776 * types filling contiguous areas of memory, this becomes an inline call 00777 * to @c memset or @ wmemset. 00778 * 00779 * _GLIBCXX_RESOLVE_LIB_DEFECTS 00780 * DR 865. More algorithms that throw away information 00781 */ 00782 template<typename _OI, typename _Size, typename _Tp> 00783 inline _OI 00784 fill_n(_OI __first, _Size __n, const _Tp& __value) 00785 { 00786 // concept requirements 00787 __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) 00788 00789 return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value)); 00790 } 00791 00792 template<bool _BoolType> 00793 struct __equal 00794 { 00795 template<typename _II1, typename _II2> 00796 static bool 00797 equal(_II1 __first1, _II1 __last1, _II2 __first2) 00798 { 00799 for (; __first1 != __last1; ++__first1, (void)++__first2) 00800 if (!(*__first1 == *__first2)) 00801 return false; 00802 return true; 00803 } 00804 }; 00805 00806 template<> 00807 struct __equal<true> 00808 { 00809 template<typename _Tp> 00810 static bool 00811 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) 00812 { 00813 if (const size_t __len = (__last1 - __first1)) 00814 return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * __len); 00815 return true; 00816 } 00817 }; 00818 00819 template<typename _II1, typename _II2> 00820 inline bool 00821 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) 00822 { 00823 typedef typename iterator_traits<_II1>::value_type _ValueType1; 00824 typedef typename iterator_traits<_II2>::value_type _ValueType2; 00825 const bool __simple = ((__is_integer<_ValueType1>::__value 00826 || __is_pointer<_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 template<typename, typename> 00835 struct __lc_rai 00836 { 00837 template<typename _II1, typename _II2> 00838 static _II1 00839 __newlast1(_II1, _II1 __last1, _II2, _II2) 00840 { return __last1; } 00841 00842 template<typename _II> 00843 static bool 00844 __cnd2(_II __first, _II __last) 00845 { return __first != __last; } 00846 }; 00847 00848 template<> 00849 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> 00850 { 00851 template<typename _RAI1, typename _RAI2> 00852 static _RAI1 00853 __newlast1(_RAI1 __first1, _RAI1 __last1, 00854 _RAI2 __first2, _RAI2 __last2) 00855 { 00856 const typename iterator_traits<_RAI1>::difference_type 00857 __diff1 = __last1 - __first1; 00858 const typename iterator_traits<_RAI2>::difference_type 00859 __diff2 = __last2 - __first2; 00860 return __diff2 < __diff1 ? __first1 + __diff2 : __last1; 00861 } 00862 00863 template<typename _RAI> 00864 static bool 00865 __cnd2(_RAI, _RAI) 00866 { return true; } 00867 }; 00868 00869 template<typename _II1, typename _II2, typename _Compare> 00870 bool 00871 __lexicographical_compare_impl(_II1 __first1, _II1 __last1, 00872 _II2 __first2, _II2 __last2, 00873 _Compare __comp) 00874 { 00875 typedef typename iterator_traits<_II1>::iterator_category _Category1; 00876 typedef typename iterator_traits<_II2>::iterator_category _Category2; 00877 typedef std::__lc_rai<_Category1, _Category2> __rai_type; 00878 00879 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); 00880 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); 00881 ++__first1, (void)++__first2) 00882 { 00883 if (__comp(__first1, __first2)) 00884 return true; 00885 if (__comp(__first2, __first1)) 00886 return false; 00887 } 00888 return __first1 == __last1 && __first2 != __last2; 00889 } 00890 00891 template<bool _BoolType> 00892 struct __lexicographical_compare 00893 { 00894 template<typename _II1, typename _II2> 00895 static bool __lc(_II1, _II1, _II2, _II2); 00896 }; 00897 00898 template<bool _BoolType> 00899 template<typename _II1, typename _II2> 00900 bool 00901 __lexicographical_compare<_BoolType>:: 00902 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 00903 { 00904 return std::__lexicographical_compare_impl(__first1, __last1, 00905 __first2, __last2, 00906 __gnu_cxx::__ops::__iter_less_iter()); 00907 } 00908 00909 template<> 00910 struct __lexicographical_compare<true> 00911 { 00912 template<typename _Tp, typename _Up> 00913 static bool 00914 __lc(const _Tp* __first1, const _Tp* __last1, 00915 const _Up* __first2, const _Up* __last2) 00916 { 00917 const size_t __len1 = __last1 - __first1; 00918 const size_t __len2 = __last2 - __first2; 00919 if (const size_t __len = std::min(__len1, __len2)) 00920 if (int __result = __builtin_memcmp(__first1, __first2, __len)) 00921 return __result < 0; 00922 return __len1 < __len2; 00923 } 00924 }; 00925 00926 template<typename _II1, typename _II2> 00927 inline bool 00928 __lexicographical_compare_aux(_II1 __first1, _II1 __last1, 00929 _II2 __first2, _II2 __last2) 00930 { 00931 typedef typename iterator_traits<_II1>::value_type _ValueType1; 00932 typedef typename iterator_traits<_II2>::value_type _ValueType2; 00933 const bool __simple = 00934 (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value 00935 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed 00936 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed 00937 && __is_pointer<_II1>::__value 00938 && __is_pointer<_II2>::__value); 00939 00940 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, 00941 __first2, __last2); 00942 } 00943 00944 template<typename _ForwardIterator, typename _Tp, typename _Compare> 00945 _ForwardIterator 00946 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, 00947 const _Tp& __val, _Compare __comp) 00948 { 00949 typedef typename iterator_traits<_ForwardIterator>::difference_type 00950 _DistanceType; 00951 00952 _DistanceType __len = std::distance(__first, __last); 00953 00954 while (__len > 0) 00955 { 00956 _DistanceType __half = __len >> 1; 00957 _ForwardIterator __middle = __first; 00958 std::advance(__middle, __half); 00959 if (__comp(__middle, __val)) 00960 { 00961 __first = __middle; 00962 ++__first; 00963 __len = __len - __half - 1; 00964 } 00965 else 00966 __len = __half; 00967 } 00968 return __first; 00969 } 00970 00971 /** 00972 * @brief Finds the first position in which @a val could be inserted 00973 * without changing the ordering. 00974 * @param __first An iterator. 00975 * @param __last Another iterator. 00976 * @param __val The search term. 00977 * @return An iterator pointing to the first element <em>not less 00978 * than</em> @a val, or end() if every element is less than 00979 * @a val. 00980 * @ingroup binary_search_algorithms 00981 */ 00982 template<typename _ForwardIterator, typename _Tp> 00983 inline _ForwardIterator 00984 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 00985 const _Tp& __val) 00986 { 00987 // concept requirements 00988 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00989 __glibcxx_function_requires(_LessThanOpConcept< 00990 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 00991 __glibcxx_requires_partitioned_lower(__first, __last, __val); 00992 00993 return std::__lower_bound(__first, __last, __val, 00994 __gnu_cxx::__ops::__iter_less_val()); 00995 } 00996 00997 /// This is a helper function for the sort routines and for random.tcc. 00998 // Precondition: __n > 0. 00999 inline _GLIBCXX_CONSTEXPR int 01000 __lg(int __n) 01001 { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } 01002 01003 inline _GLIBCXX_CONSTEXPR unsigned 01004 __lg(unsigned __n) 01005 { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } 01006 01007 inline _GLIBCXX_CONSTEXPR long 01008 __lg(long __n) 01009 { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } 01010 01011 inline _GLIBCXX_CONSTEXPR unsigned long 01012 __lg(unsigned long __n) 01013 { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } 01014 01015 inline _GLIBCXX_CONSTEXPR long long 01016 __lg(long long __n) 01017 { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } 01018 01019 inline _GLIBCXX_CONSTEXPR unsigned long long 01020 __lg(unsigned long long __n) 01021 { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } 01022 01023 _GLIBCXX_END_NAMESPACE_VERSION 01024 01025 _GLIBCXX_BEGIN_NAMESPACE_ALGO 01026 01027 /** 01028 * @brief Tests a range for element-wise equality. 01029 * @ingroup non_mutating_algorithms 01030 * @param __first1 An input iterator. 01031 * @param __last1 An input iterator. 01032 * @param __first2 An input iterator. 01033 * @return A boolean true or false. 01034 * 01035 * This compares the elements of two ranges using @c == and returns true or 01036 * false depending on whether all of the corresponding elements of the 01037 * ranges are equal. 01038 */ 01039 template<typename _II1, typename _II2> 01040 inline bool 01041 equal(_II1 __first1, _II1 __last1, _II2 __first2) 01042 { 01043 // concept requirements 01044 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 01045 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 01046 __glibcxx_function_requires(_EqualOpConcept< 01047 typename iterator_traits<_II1>::value_type, 01048 typename iterator_traits<_II2>::value_type>) 01049 __glibcxx_requires_valid_range(__first1, __last1); 01050 01051 return std::__equal_aux(std::__niter_base(__first1), 01052 std::__niter_base(__last1), 01053 std::__niter_base(__first2)); 01054 } 01055 01056 /** 01057 * @brief Tests a range for element-wise equality. 01058 * @ingroup non_mutating_algorithms 01059 * @param __first1 An input iterator. 01060 * @param __last1 An input iterator. 01061 * @param __first2 An input iterator. 01062 * @param __binary_pred A binary predicate @link functors 01063 * functor@endlink. 01064 * @return A boolean true or false. 01065 * 01066 * This compares the elements of two ranges using the binary_pred 01067 * parameter, and returns true or 01068 * false depending on whether all of the corresponding elements of the 01069 * ranges are equal. 01070 */ 01071 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 01072 inline bool 01073 equal(_IIter1 __first1, _IIter1 __last1, 01074 _IIter2 __first2, _BinaryPredicate __binary_pred) 01075 { 01076 // concept requirements 01077 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 01078 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 01079 __glibcxx_requires_valid_range(__first1, __last1); 01080 01081 for (; __first1 != __last1; ++__first1, (void)++__first2) 01082 if (!bool(__binary_pred(*__first1, *__first2))) 01083 return false; 01084 return true; 01085 } 01086 01087 #if __cplusplus > 201103L 01088 01089 #define __cpp_lib_robust_nonmodifying_seq_ops 201304 01090 01091 /** 01092 * @brief Tests a range for element-wise equality. 01093 * @ingroup non_mutating_algorithms 01094 * @param __first1 An input iterator. 01095 * @param __last1 An input iterator. 01096 * @param __first2 An input iterator. 01097 * @param __last2 An input iterator. 01098 * @return A boolean true or false. 01099 * 01100 * This compares the elements of two ranges using @c == and returns true or 01101 * false depending on whether all of the corresponding elements of the 01102 * ranges are equal. 01103 */ 01104 template<typename _II1, typename _II2> 01105 inline bool 01106 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 01107 { 01108 // concept requirements 01109 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 01110 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 01111 __glibcxx_function_requires(_EqualOpConcept< 01112 typename iterator_traits<_II1>::value_type, 01113 typename iterator_traits<_II2>::value_type>) 01114 __glibcxx_requires_valid_range(__first1, __last1); 01115 __glibcxx_requires_valid_range(__first2, __last2); 01116 01117 using _RATag = random_access_iterator_tag; 01118 using _Cat1 = typename iterator_traits<_II1>::iterator_category; 01119 using _Cat2 = typename iterator_traits<_II2>::iterator_category; 01120 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 01121 if (_RAIters()) 01122 { 01123 auto __d1 = std::distance(__first1, __last1); 01124 auto __d2 = std::distance(__first2, __last2); 01125 if (__d1 != __d2) 01126 return false; 01127 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2); 01128 } 01129 01130 for (; __first1 != __last1 && __first2 != __last2; 01131 ++__first1, (void)++__first2) 01132 if (!(*__first1 == *__first2)) 01133 return false; 01134 return __first1 == __last1 && __first2 == __last2; 01135 } 01136 01137 /** 01138 * @brief Tests a range for element-wise equality. 01139 * @ingroup non_mutating_algorithms 01140 * @param __first1 An input iterator. 01141 * @param __last1 An input iterator. 01142 * @param __first2 An input iterator. 01143 * @param __last2 An input iterator. 01144 * @param __binary_pred A binary predicate @link functors 01145 * functor@endlink. 01146 * @return A boolean true or false. 01147 * 01148 * This compares the elements of two ranges using the binary_pred 01149 * parameter, and returns true or 01150 * false depending on whether all of the corresponding elements of the 01151 * ranges are equal. 01152 */ 01153 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 01154 inline bool 01155 equal(_IIter1 __first1, _IIter1 __last1, 01156 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred) 01157 { 01158 // concept requirements 01159 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 01160 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 01161 __glibcxx_requires_valid_range(__first1, __last1); 01162 __glibcxx_requires_valid_range(__first2, __last2); 01163 01164 using _RATag = random_access_iterator_tag; 01165 using _Cat1 = typename iterator_traits<_IIter1>::iterator_category; 01166 using _Cat2 = typename iterator_traits<_IIter2>::iterator_category; 01167 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 01168 if (_RAIters()) 01169 { 01170 auto __d1 = std::distance(__first1, __last1); 01171 auto __d2 = std::distance(__first2, __last2); 01172 if (__d1 != __d2) 01173 return false; 01174 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, 01175 __binary_pred); 01176 } 01177 01178 for (; __first1 != __last1 && __first2 != __last2; 01179 ++__first1, (void)++__first2) 01180 if (!bool(__binary_pred(*__first1, *__first2))) 01181 return false; 01182 return __first1 == __last1 && __first2 == __last2; 01183 } 01184 #endif 01185 01186 /** 01187 * @brief Performs @b dictionary comparison on ranges. 01188 * @ingroup sorting_algorithms 01189 * @param __first1 An input iterator. 01190 * @param __last1 An input iterator. 01191 * @param __first2 An input iterator. 01192 * @param __last2 An input iterator. 01193 * @return A boolean true or false. 01194 * 01195 * <em>Returns true if the sequence of elements defined by the range 01196 * [first1,last1) is lexicographically less than the sequence of elements 01197 * defined by the range [first2,last2). Returns false otherwise.</em> 01198 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 01199 * then this is an inline call to @c memcmp. 01200 */ 01201 template<typename _II1, typename _II2> 01202 inline bool 01203 lexicographical_compare(_II1 __first1, _II1 __last1, 01204 _II2 __first2, _II2 __last2) 01205 { 01206 #ifdef _GLIBCXX_CONCEPT_CHECKS 01207 // concept requirements 01208 typedef typename iterator_traits<_II1>::value_type _ValueType1; 01209 typedef typename iterator_traits<_II2>::value_type _ValueType2; 01210 #endif 01211 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 01212 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 01213 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 01214 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 01215 __glibcxx_requires_valid_range(__first1, __last1); 01216 __glibcxx_requires_valid_range(__first2, __last2); 01217 01218 return std::__lexicographical_compare_aux(std::__niter_base(__first1), 01219 std::__niter_base(__last1), 01220 std::__niter_base(__first2), 01221 std::__niter_base(__last2)); 01222 } 01223 01224 /** 01225 * @brief Performs @b dictionary comparison on ranges. 01226 * @ingroup sorting_algorithms 01227 * @param __first1 An input iterator. 01228 * @param __last1 An input iterator. 01229 * @param __first2 An input iterator. 01230 * @param __last2 An input iterator. 01231 * @param __comp A @link comparison_functors comparison functor@endlink. 01232 * @return A boolean true or false. 01233 * 01234 * The same as the four-parameter @c lexicographical_compare, but uses the 01235 * comp parameter instead of @c <. 01236 */ 01237 template<typename _II1, typename _II2, typename _Compare> 01238 inline bool 01239 lexicographical_compare(_II1 __first1, _II1 __last1, 01240 _II2 __first2, _II2 __last2, _Compare __comp) 01241 { 01242 // concept requirements 01243 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 01244 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 01245 __glibcxx_requires_valid_range(__first1, __last1); 01246 __glibcxx_requires_valid_range(__first2, __last2); 01247 01248 return std::__lexicographical_compare_impl 01249 (__first1, __last1, __first2, __last2, 01250 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 01251 } 01252 01253 template<typename _InputIterator1, typename _InputIterator2, 01254 typename _BinaryPredicate> 01255 pair<_InputIterator1, _InputIterator2> 01256 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01257 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 01258 { 01259 while (__first1 != __last1 && __binary_pred(__first1, __first2)) 01260 { 01261 ++__first1; 01262 ++__first2; 01263 } 01264 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 01265 } 01266 01267 /** 01268 * @brief Finds the places in ranges which don't match. 01269 * @ingroup non_mutating_algorithms 01270 * @param __first1 An input iterator. 01271 * @param __last1 An input iterator. 01272 * @param __first2 An input iterator. 01273 * @return A pair of iterators pointing to the first mismatch. 01274 * 01275 * This compares the elements of two ranges using @c == and returns a pair 01276 * of iterators. The first iterator points into the first range, the 01277 * second iterator points into the second range, and the elements pointed 01278 * to by the iterators are not equal. 01279 */ 01280 template<typename _InputIterator1, typename _InputIterator2> 01281 inline pair<_InputIterator1, _InputIterator2> 01282 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01283 _InputIterator2 __first2) 01284 { 01285 // concept requirements 01286 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 01287 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 01288 __glibcxx_function_requires(_EqualOpConcept< 01289 typename iterator_traits<_InputIterator1>::value_type, 01290 typename iterator_traits<_InputIterator2>::value_type>) 01291 __glibcxx_requires_valid_range(__first1, __last1); 01292 01293 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 01294 __gnu_cxx::__ops::__iter_equal_to_iter()); 01295 } 01296 01297 /** 01298 * @brief Finds the places in ranges which don't match. 01299 * @ingroup non_mutating_algorithms 01300 * @param __first1 An input iterator. 01301 * @param __last1 An input iterator. 01302 * @param __first2 An input iterator. 01303 * @param __binary_pred A binary predicate @link functors 01304 * functor@endlink. 01305 * @return A pair of iterators pointing to the first mismatch. 01306 * 01307 * This compares the elements of two ranges using the binary_pred 01308 * parameter, and returns a pair 01309 * of iterators. The first iterator points into the first range, the 01310 * second iterator points into the second range, and the elements pointed 01311 * to by the iterators are not equal. 01312 */ 01313 template<typename _InputIterator1, typename _InputIterator2, 01314 typename _BinaryPredicate> 01315 inline pair<_InputIterator1, _InputIterator2> 01316 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01317 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 01318 { 01319 // concept requirements 01320 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 01321 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 01322 __glibcxx_requires_valid_range(__first1, __last1); 01323 01324 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 01325 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 01326 } 01327 01328 #if __cplusplus > 201103L 01329 01330 template<typename _InputIterator1, typename _InputIterator2, 01331 typename _BinaryPredicate> 01332 pair<_InputIterator1, _InputIterator2> 01333 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01334 _InputIterator2 __first2, _InputIterator2 __last2, 01335 _BinaryPredicate __binary_pred) 01336 { 01337 while (__first1 != __last1 && __first2 != __last2 01338 && __binary_pred(__first1, __first2)) 01339 { 01340 ++__first1; 01341 ++__first2; 01342 } 01343 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 01344 } 01345 01346 /** 01347 * @brief Finds the places in ranges which don't match. 01348 * @ingroup non_mutating_algorithms 01349 * @param __first1 An input iterator. 01350 * @param __last1 An input iterator. 01351 * @param __first2 An input iterator. 01352 * @param __last2 An input iterator. 01353 * @return A pair of iterators pointing to the first mismatch. 01354 * 01355 * This compares the elements of two ranges using @c == and returns a pair 01356 * of iterators. The first iterator points into the first range, the 01357 * second iterator points into the second range, and the elements pointed 01358 * to by the iterators are not equal. 01359 */ 01360 template<typename _InputIterator1, typename _InputIterator2> 01361 inline pair<_InputIterator1, _InputIterator2> 01362 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01363 _InputIterator2 __first2, _InputIterator2 __last2) 01364 { 01365 // concept requirements 01366 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 01367 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 01368 __glibcxx_function_requires(_EqualOpConcept< 01369 typename iterator_traits<_InputIterator1>::value_type, 01370 typename iterator_traits<_InputIterator2>::value_type>) 01371 __glibcxx_requires_valid_range(__first1, __last1); 01372 __glibcxx_requires_valid_range(__first2, __last2); 01373 01374 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 01375 __gnu_cxx::__ops::__iter_equal_to_iter()); 01376 } 01377 01378 /** 01379 * @brief Finds the places in ranges which don't match. 01380 * @ingroup non_mutating_algorithms 01381 * @param __first1 An input iterator. 01382 * @param __last1 An input iterator. 01383 * @param __first2 An input iterator. 01384 * @param __last2 An input iterator. 01385 * @param __binary_pred A binary predicate @link functors 01386 * functor@endlink. 01387 * @return A pair of iterators pointing to the first mismatch. 01388 * 01389 * This compares the elements of two ranges using the binary_pred 01390 * parameter, and returns a pair 01391 * of iterators. The first iterator points into the first range, the 01392 * second iterator points into the second range, and the elements pointed 01393 * to by the iterators are not equal. 01394 */ 01395 template<typename _InputIterator1, typename _InputIterator2, 01396 typename _BinaryPredicate> 01397 inline pair<_InputIterator1, _InputIterator2> 01398 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 01399 _InputIterator2 __first2, _InputIterator2 __last2, 01400 _BinaryPredicate __binary_pred) 01401 { 01402 // concept requirements 01403 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 01404 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 01405 __glibcxx_requires_valid_range(__first1, __last1); 01406 __glibcxx_requires_valid_range(__first2, __last2); 01407 01408 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 01409 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 01410 } 01411 #endif 01412 01413 _GLIBCXX_END_NAMESPACE_ALGO 01414 } // namespace std 01415 01416 // NB: This file is included within many other C++ includes, as a way 01417 // of getting the base algorithms. So, make sure that parallel bits 01418 // come in too if requested. 01419 #ifdef _GLIBCXX_PARALLEL 01420 # include <parallel/algobase.h> 01421 #endif 01422 01423 #endif