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