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