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