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