Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/13/bits/stl_algobase.h
$ cat -n /usr/include/c++/13/bits/stl_algobase.h 1 // Core algorithmic facilities -*- C++ -*- 2 3 // Copyright (C) 2001-2023 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996-1998 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/stl_algobase.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{algorithm} 54 */ 55 56 #ifndef _STL_ALGOBASE_H 57 #define _STL_ALGOBASE_H 1 58 59 #include <bits/c++config.h> 60 #include <bits/functexcept.h> 61 #include <bits/cpp_type_traits.h> 62 #include <ext/type_traits.h> 63 #include <ext/numeric_traits.h> 64 #include <bits/stl_pair.h> 65 #include <bits/stl_iterator_base_types.h> 66 #include <bits/stl_iterator_base_funcs.h> 67 #include <bits/stl_iterator.h> 68 #include <bits/concept_check.h> 69 #include <debug/debug.h> 70 #include <bits/move.h> // For std::swap 71 #include <bits/predefined_ops.h> 72 #if __cplusplus >= 201103L 73 # include <type_traits> 74 #endif 75 #if __cplusplus >= 201402L 76 # include <bit> // std::__bit_width 77 #endif 78 #if __cplusplus >= 202002L 79 # include <compare> 80 #endif 81 82 namespace std _GLIBCXX_VISIBILITY(default) 83 { 84 _GLIBCXX_BEGIN_NAMESPACE_VERSION 85 86 /* 87 * A constexpr wrapper for __builtin_memcmp. 88 * @param __num The number of elements of type _Tp (not bytes). 89 */ 90 template<typename _Tp, typename _Up> 91 _GLIBCXX14_CONSTEXPR 92 inline int 93 __memcmp(const _Tp* __first1, const _Up* __first2, size_t __num) 94 { 95 #if __cplusplus >= 201103L 96 static_assert(sizeof(_Tp) == sizeof(_Up), "can be compared with memcmp"); 97 #endif 98 #ifdef __cpp_lib_is_constant_evaluated 99 if (std::is_constant_evaluated()) 100 { 101 for(; __num > 0; ++__first1, ++__first2, --__num) 102 if (*__first1 != *__first2) 103 return *__first1 < *__first2 ? -1 : 1; 104 return 0; 105 } 106 else 107 #endif 108 return __builtin_memcmp(__first1, __first2, sizeof(_Tp) * __num); 109 } 110 111 #if __cplusplus < 201103L 112 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a 113 // nutshell, we are partially implementing the resolution of DR 187, 114 // when it's safe, i.e., the value_types are equal. 115 template<bool _BoolType> 116 struct __iter_swap 117 { 118 template<typename _ForwardIterator1, typename _ForwardIterator2> 119 static void 120 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 121 { 122 typedef typename iterator_traits<_ForwardIterator1>::value_type 123 _ValueType1; 124 _ValueType1 __tmp = *__a; 125 *__a = *__b; 126 *__b = __tmp; 127 } 128 }; 129 130 template<> 131 struct __iter_swap<true> 132 { 133 template<typename _ForwardIterator1, typename _ForwardIterator2> 134 static void 135 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 136 { 137 swap(*__a, *__b); 138 } 139 }; 140 #endif // C++03 141 142 /** 143 * @brief Swaps the contents of two iterators. 144 * @ingroup mutating_algorithms 145 * @param __a An iterator. 146 * @param __b Another iterator. 147 * @return Nothing. 148 * 149 * This function swaps the values pointed to by two iterators, not the 150 * iterators themselves. 151 */ 152 template<typename _ForwardIterator1, typename _ForwardIterator2> 153 _GLIBCXX20_CONSTEXPR 154 inline void 155 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 156 { 157 // concept requirements 158 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 159 _ForwardIterator1>) 160 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 161 _ForwardIterator2>) 162 163 #if __cplusplus < 201103L 164 typedef typename iterator_traits<_ForwardIterator1>::value_type 165 _ValueType1; 166 typedef typename iterator_traits<_ForwardIterator2>::value_type 167 _ValueType2; 168 169 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, 170 _ValueType2>) 171 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, 172 _ValueType1>) 173 174 typedef typename iterator_traits<_ForwardIterator1>::reference 175 _ReferenceType1; 176 typedef typename iterator_traits<_ForwardIterator2>::reference 177 _ReferenceType2; 178 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value 179 && __are_same<_ValueType1&, _ReferenceType1>::__value 180 && __are_same<_ValueType2&, _ReferenceType2>::__value>:: 181 iter_swap(__a, __b); 182 #else 183 // _GLIBCXX_RESOLVE_LIB_DEFECTS 184 // 187. iter_swap underspecified 185 swap(*__a, *__b); 186 #endif 187 } 188 189 /** 190 * @brief Swap the elements of two sequences. 191 * @ingroup mutating_algorithms 192 * @param __first1 A forward iterator. 193 * @param __last1 A forward iterator. 194 * @param __first2 A forward iterator. 195 * @return An iterator equal to @p first2+(last1-first1). 196 * 197 * Swaps each element in the range @p [first1,last1) with the 198 * corresponding element in the range @p [first2,(last1-first1)). 199 * The ranges must not overlap. 200 */ 201 template<typename _ForwardIterator1, typename _ForwardIterator2> 202 _GLIBCXX20_CONSTEXPR 203 _ForwardIterator2 204 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 205 _ForwardIterator2 __first2) 206 { 207 // concept requirements 208 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 209 _ForwardIterator1>) 210 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 211 _ForwardIterator2>) 212 __glibcxx_requires_valid_range(__first1, __last1); 213 214 for (; __first1 != __last1; ++__first1, (void)++__first2) 215 std::iter_swap(__first1, __first2); 216 return __first2; 217 } 218 219 /** 220 * @brief This does what you think it does. 221 * @ingroup sorting_algorithms 222 * @param __a A thing of arbitrary type. 223 * @param __b Another thing of arbitrary type. 224 * @return The lesser of the parameters. 225 * 226 * This is the simple classic generic implementation. It will work on 227 * temporary expressions, since they are only evaluated once, unlike a 228 * preprocessor macro. 229 */ 230 template<typename _Tp> 231 _GLIBCXX14_CONSTEXPR 232 inline const _Tp& 233 min(const _Tp& __a, const _Tp& __b) 234 { 235 // concept requirements 236 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 237 //return __b < __a ? __b : __a; 238 if (__b < __a) 239 return __b; 240 return __a; 241 } 242 243 /** 244 * @brief This does what you think it does. 245 * @ingroup sorting_algorithms 246 * @param __a A thing of arbitrary type. 247 * @param __b Another thing of arbitrary type. 248 * @return The greater of the parameters. 249 * 250 * This is the simple classic generic implementation. It will work on 251 * temporary expressions, since they are only evaluated once, unlike a 252 * preprocessor macro. 253 */ 254 template<typename _Tp> 255 _GLIBCXX14_CONSTEXPR 256 inline const _Tp& 257 max(const _Tp& __a, const _Tp& __b) 258 { 259 // concept requirements 260 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 261 //return __a < __b ? __b : __a; 262 if (__a < __b) 263 return __b; 264 return __a; 265 } 266 267 /** 268 * @brief This does what you think it does. 269 * @ingroup sorting_algorithms 270 * @param __a A thing of arbitrary type. 271 * @param __b Another thing of arbitrary type. 272 * @param __comp A @link comparison_functors comparison functor@endlink. 273 * @return The lesser of the parameters. 274 * 275 * This will work on temporary expressions, since they are only evaluated 276 * once, unlike a preprocessor macro. 277 */ 278 template<typename _Tp, typename _Compare> 279 _GLIBCXX14_CONSTEXPR 280 inline const _Tp& 281 min(const _Tp& __a, const _Tp& __b, _Compare __comp) 282 { 283 //return __comp(__b, __a) ? __b : __a; 284 if (__comp(__b, __a)) 285 return __b; 286 return __a; 287 } 288 289 /** 290 * @brief This does what you think it does. 291 * @ingroup sorting_algorithms 292 * @param __a A thing of arbitrary type. 293 * @param __b Another thing of arbitrary type. 294 * @param __comp A @link comparison_functors comparison functor@endlink. 295 * @return The greater of the parameters. 296 * 297 * This will work on temporary expressions, since they are only evaluated 298 * once, unlike a preprocessor macro. 299 */ 300 template<typename _Tp, typename _Compare> 301 _GLIBCXX14_CONSTEXPR 302 inline const _Tp& 303 max(const _Tp& __a, const _Tp& __b, _Compare __comp) 304 { 305 //return __comp(__a, __b) ? __b : __a; 306 if (__comp(__a, __b)) 307 return __b; 308 return __a; 309 } 310 311 // Fallback implementation of the function in bits/stl_iterator.h used to 312 // remove the __normal_iterator wrapper. See copy, fill, ... 313 template<typename _Iterator> 314 _GLIBCXX20_CONSTEXPR 315 inline _Iterator 316 __niter_base(_Iterator __it) 317 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value) 318 { return __it; } 319 320 template<typename _Ite, typename _Seq> 321 _Ite 322 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, 323 std::random_access_iterator_tag>&); 324 325 // Reverse the __niter_base transformation to get a 326 // __normal_iterator back again (this assumes that __normal_iterator 327 // is only used to wrap random access iterators, like pointers). 328 template<typename _From, typename _To> 329 _GLIBCXX20_CONSTEXPR 330 inline _From 331 __niter_wrap(_From __from, _To __res) 332 { return __from + (__res - std::__niter_base(__from)); } 333 334 // No need to wrap, iterator already has the right type. 335 template<typename _Iterator> 336 _GLIBCXX20_CONSTEXPR 337 inline _Iterator 338 __niter_wrap(const _Iterator&, _Iterator __res) 339 { return __res; } 340 341 // All of these auxiliary structs serve two purposes. (1) Replace 342 // calls to copy with memmove whenever possible. (Memmove, not memcpy, 343 // because the input and output ranges are permitted to overlap.) 344 // (2) If we're using random access iterators, then write the loop as 345 // a for loop with an explicit count. 346 347 template<bool _IsMove, bool _IsSimple, typename _Category> 348 struct __copy_move 349 { 350 template<typename _II, typename _OI> 351 _GLIBCXX20_CONSTEXPR 352 static _OI 353 __copy_m(_II __first, _II __last, _OI __result) 354 { 355 for (; __first != __last; ++__result, (void)++__first) 356 *__result = *__first; 357 return __result; 358 } 359 }; 360 361 #if __cplusplus >= 201103L 362 template<typename _Category> 363 struct __copy_move<true, false, _Category> 364 { 365 template<typename _II, typename _OI> 366 _GLIBCXX20_CONSTEXPR 367 static _OI 368 __copy_m(_II __first, _II __last, _OI __result) 369 { 370 for (; __first != __last; ++__result, (void)++__first) 371 *__result = std::move(*__first); 372 return __result; 373 } 374 }; 375 #endif 376 377 template<> 378 struct __copy_move<false, false, random_access_iterator_tag> 379 { 380 template<typename _II, typename _OI> 381 _GLIBCXX20_CONSTEXPR 382 static _OI 383 __copy_m(_II __first, _II __last, _OI __result) 384 { 385 typedef typename iterator_traits<_II>::difference_type _Distance; 386 for(_Distance __n = __last - __first; __n > 0; --__n) 387 { 388 *__result = *__first; 389 ++__first; 390 ++__result; 391 } 392 return __result; 393 } 394 395 template<typename _Tp, typename _Up> 396 static void 397 __assign_one(_Tp* __to, _Up* __from) 398 { *__to = *__from; } 399 }; 400 401 #if __cplusplus >= 201103L 402 template<> 403 struct __copy_move<true, false, random_access_iterator_tag> 404 { 405 template<typename _II, typename _OI> 406 _GLIBCXX20_CONSTEXPR 407 static _OI 408 __copy_m(_II __first, _II __last, _OI __result) 409 { 410 typedef typename iterator_traits<_II>::difference_type _Distance; 411 for(_Distance __n = __last - __first; __n > 0; --__n) 412 { 413 *__result = std::move(*__first); 414 ++__first; 415 ++__result; 416 } 417 return __result; 418 } 419 420 template<typename _Tp, typename _Up> 421 static void 422 __assign_one(_Tp* __to, _Up* __from) 423 { *__to = std::move(*__from); } 424 }; 425 #endif 426 427 template<bool _IsMove> 428 struct __copy_move<_IsMove, true, random_access_iterator_tag> 429 { 430 template<typename _Tp, typename _Up> 431 _GLIBCXX20_CONSTEXPR 432 static _Up* 433 __copy_m(_Tp* __first, _Tp* __last, _Up* __result) 434 { 435 const ptrdiff_t _Num = __last - __first; 436 if (__builtin_expect(_Num > 1, true)) 437 __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); 438 else if (_Num == 1) 439 std::__copy_move<_IsMove, false, random_access_iterator_tag>:: 440 __assign_one(__result, __first); 441 return __result + _Num; 442 } 443 }; 444 445 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 446 447 template<typename _Tp, typename _Ref, typename _Ptr> 448 struct _Deque_iterator; 449 450 struct _Bit_iterator; 451 452 _GLIBCXX_END_NAMESPACE_CONTAINER 453 454 #if _GLIBCXX_HOSTED 455 // Helpers for streambuf iterators (either istream or ostream). 456 // NB: avoid including <iosfwd>, relatively large. 457 template<typename _CharT> 458 struct char_traits; 459 460 template<typename _CharT, typename _Traits> 461 class istreambuf_iterator; 462 463 template<typename _CharT, typename _Traits> 464 class ostreambuf_iterator; 465 466 template<bool _IsMove, typename _CharT> 467 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 468 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 469 __copy_move_a2(_CharT*, _CharT*, 470 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 471 472 template<bool _IsMove, typename _CharT> 473 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 474 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 475 __copy_move_a2(const _CharT*, const _CharT*, 476 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 477 478 template<bool _IsMove, typename _CharT> 479 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 480 _CharT*>::__type 481 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, 482 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); 483 484 template<bool _IsMove, typename _CharT> 485 typename __gnu_cxx::__enable_if< 486 __is_char<_CharT>::__value, 487 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type 488 __copy_move_a2( 489 istreambuf_iterator<_CharT, char_traits<_CharT> >, 490 istreambuf_iterator<_CharT, char_traits<_CharT> >, 491 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>); 492 #endif // HOSTED 493 494 template<bool _IsMove, typename _II, typename _OI> 495 _GLIBCXX20_CONSTEXPR 496 inline _OI 497 __copy_move_a2(_II __first, _II __last, _OI __result) 498 { 499 typedef typename iterator_traits<_II>::iterator_category _Category; 500 #ifdef __cpp_lib_is_constant_evaluated 501 if (std::is_constant_evaluated()) 502 return std::__copy_move<_IsMove, false, _Category>:: 503 __copy_m(__first, __last, __result); 504 #endif 505 return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value, 506 _Category>::__copy_m(__first, __last, __result); 507 } 508 509 template<bool _IsMove, 510 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 511 _OI 512 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, 513 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, 514 _OI); 515 516 template<bool _IsMove, 517 typename _ITp, typename _IRef, typename _IPtr, typename _OTp> 518 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> 519 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, 520 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, 521 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>); 522 523 template<bool _IsMove, typename _II, typename _Tp> 524 typename __gnu_cxx::__enable_if< 525 __is_random_access_iter<_II>::__value, 526 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type 527 __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>); 528 529 template<bool _IsMove, typename _II, typename _OI> 530 _GLIBCXX20_CONSTEXPR 531 inline _OI 532 __copy_move_a1(_II __first, _II __last, _OI __result) 533 { return std::__copy_move_a2<_IsMove>(__first, __last, __result); } 534 535 template<bool _IsMove, typename _II, typename _OI> 536 _GLIBCXX20_CONSTEXPR 537 inline _OI 538 __copy_move_a(_II __first, _II __last, _OI __result) 539 { 540 return std::__niter_wrap(__result, 541 std::__copy_move_a1<_IsMove>(std::__niter_base(__first), 542 std::__niter_base(__last), 543 std::__niter_base(__result))); 544 } 545 546 template<bool _IsMove, 547 typename _Ite, typename _Seq, typename _Cat, typename _OI> 548 _OI 549 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, 550 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, 551 _OI); 552 553 template<bool _IsMove, 554 typename _II, typename _Ite, typename _Seq, typename _Cat> 555 __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> 556 __copy_move_a(_II, _II, 557 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&); 558 559 template<bool _IsMove, 560 typename _IIte, typename _ISeq, typename _ICat, 561 typename _OIte, typename _OSeq, typename _OCat> 562 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> 563 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, 564 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, 565 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&); 566 567 template<typename _InputIterator, typename _Size, typename _OutputIterator> 568 _GLIBCXX20_CONSTEXPR 569 _OutputIterator 570 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result, 571 bool) 572 { 573 if (__n > 0) 574 { 575 while (true) 576 { 577 *__result = *__first; 578 ++__result; 579 if (--__n > 0) 580 ++__first; 581 else 582 break; 583 } 584 } 585 return __result; 586 } 587 588 #if _GLIBCXX_HOSTED 589 template<typename _CharT, typename _Size> 590 typename __gnu_cxx::__enable_if< 591 __is_char<_CharT>::__value, _CharT*>::__type 592 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, 593 _Size, _CharT*, bool); 594 595 template<typename _CharT, typename _Size> 596 typename __gnu_cxx::__enable_if< 597 __is_char<_CharT>::__value, 598 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type 599 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size, 600 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>, 601 bool); 602 #endif 603 604 /** 605 * @brief Copies the range [first,last) into result. 606 * @ingroup mutating_algorithms 607 * @param __first An input iterator. 608 * @param __last An input iterator. 609 * @param __result An output iterator. 610 * @return result + (last - first) 611 * 612 * This inline function will boil down to a call to @c memmove whenever 613 * possible. Failing that, if random access iterators are passed, then the 614 * loop count will be known (and therefore a candidate for compiler 615 * optimizations such as unrolling). Result may not be contained within 616 * [first,last); the copy_backward function should be used instead. 617 * 618 * Note that the end of the output range is permitted to be contained 619 * within [first,last). 620 */ 621 template<typename _II, typename _OI> 622 _GLIBCXX20_CONSTEXPR 623 inline _OI 624 copy(_II __first, _II __last, _OI __result) 625 { 626 // concept requirements 627 __glibcxx_function_requires(_InputIteratorConcept<_II>) 628 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 629 typename iterator_traits<_II>::reference>) 630 __glibcxx_requires_can_increment_range(__first, __last, __result); 631 632 return std::__copy_move_a<__is_move_iterator<_II>::__value> 633 (std::__miter_base(__first), std::__miter_base(__last), __result); 634 } 635 636 #if __cplusplus >= 201103L 637 /** 638 * @brief Moves the range [first,last) into result. 639 * @ingroup mutating_algorithms 640 * @param __first An input iterator. 641 * @param __last An input iterator. 642 * @param __result An output iterator. 643 * @return result + (last - first) 644 * 645 * This inline function will boil down to a call to @c memmove whenever 646 * possible. Failing that, if random access iterators are passed, then the 647 * loop count will be known (and therefore a candidate for compiler 648 * optimizations such as unrolling). Result may not be contained within 649 * [first,last); the move_backward function should be used instead. 650 * 651 * Note that the end of the output range is permitted to be contained 652 * within [first,last). 653 */ 654 template<typename _II, typename _OI> 655 _GLIBCXX20_CONSTEXPR 656 inline _OI 657 move(_II __first, _II __last, _OI __result) 658 { 659 // concept requirements 660 __glibcxx_function_requires(_InputIteratorConcept<_II>) 661 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 662 typename iterator_traits<_II>::value_type&&>) 663 __glibcxx_requires_can_increment_range(__first, __last, __result); 664 665 return std::__copy_move_a<true>(std::__miter_base(__first), 666 std::__miter_base(__last), __result); 667 } 668 669 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) 670 #else 671 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) 672 #endif 673 674 template<bool _IsMove, bool _IsSimple, typename _Category> 675 struct __copy_move_backward 676 { 677 template<typename _BI1, typename _BI2> 678 _GLIBCXX20_CONSTEXPR 679 static _BI2 680 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 681 { 682 while (__first != __last) 683 *--__result = *--__last; 684 return __result; 685 } 686 }; 687 688 #if __cplusplus >= 201103L 689 template<typename _Category> 690 struct __copy_move_backward<true, false, _Category> 691 { 692 template<typename _BI1, typename _BI2> 693 _GLIBCXX20_CONSTEXPR 694 static _BI2 695 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 696 { 697 while (__first != __last) 698 *--__result = std::move(*--__last); 699 return __result; 700 } 701 }; 702 #endif 703 704 template<> 705 struct __copy_move_backward<false, false, random_access_iterator_tag> 706 { 707 template<typename _BI1, typename _BI2> 708 _GLIBCXX20_CONSTEXPR 709 static _BI2 710 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 711 { 712 typename iterator_traits<_BI1>::difference_type 713 __n = __last - __first; 714 for (; __n > 0; --__n) 715 *--__result = *--__last; 716 return __result; 717 } 718 }; 719 720 #if __cplusplus >= 201103L 721 template<> 722 struct __copy_move_backward<true, false, random_access_iterator_tag> 723 { 724 template<typename _BI1, typename _BI2> 725 _GLIBCXX20_CONSTEXPR 726 static _BI2 727 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 728 { 729 typename iterator_traits<_BI1>::difference_type 730 __n = __last - __first; 731 for (; __n > 0; --__n) 732 *--__result = std::move(*--__last); 733 return __result; 734 } 735 }; 736 #endif 737 738 template<bool _IsMove> 739 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> 740 { 741 template<typename _Tp, typename _Up> 742 _GLIBCXX20_CONSTEXPR 743 static _Up* 744 __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result) 745 { 746 const ptrdiff_t _Num = __last - __first; 747 if (__builtin_expect(_Num > 1, true)) 748 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 749 else if (_Num == 1) 750 std::__copy_move<_IsMove, false, random_access_iterator_tag>:: 751 __assign_one(__result - 1, __first); 752 return __result - _Num; 753 } 754 }; 755 756 template<bool _IsMove, typename _BI1, typename _BI2> 757 _GLIBCXX20_CONSTEXPR 758 inline _BI2 759 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) 760 { 761 typedef typename iterator_traits<_BI1>::iterator_category _Category; 762 #ifdef __cpp_lib_is_constant_evaluated 763 if (std::is_constant_evaluated()) 764 return std::__copy_move_backward<_IsMove, false, _Category>:: 765 __copy_move_b(__first, __last, __result); 766 #endif 767 return std::__copy_move_backward<_IsMove, 768 __memcpyable<_BI2, _BI1>::__value, 769 _Category>::__copy_move_b(__first, 770 __last, 771 __result); 772 } 773 774 template<bool _IsMove, typename _BI1, typename _BI2> 775 _GLIBCXX20_CONSTEXPR 776 inline _BI2 777 __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result) 778 { return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); } 779 780 template<bool _IsMove, 781 typename _Tp, typename _Ref, typename _Ptr, typename _OI> 782 _OI 783 __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, 784 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, 785 _OI); 786 787 template<bool _IsMove, 788 typename _ITp, typename _IRef, typename _IPtr, typename _OTp> 789 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> 790 __copy_move_backward_a1( 791 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, 792 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>, 793 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>); 794 795 template<bool _IsMove, typename _II, typename _Tp> 796 typename __gnu_cxx::__enable_if< 797 __is_random_access_iter<_II>::__value, 798 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type 799 __copy_move_backward_a1(_II, _II, 800 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>); 801 802 template<bool _IsMove, typename _II, typename _OI> 803 _GLIBCXX20_CONSTEXPR 804 inline _OI 805 __copy_move_backward_a(_II __first, _II __last, _OI __result) 806 { 807 return std::__niter_wrap(__result, 808 std::__copy_move_backward_a1<_IsMove> 809 (std::__niter_base(__first), std::__niter_base(__last), 810 std::__niter_base(__result))); 811 } 812 813 template<bool _IsMove, 814 typename _Ite, typename _Seq, typename _Cat, typename _OI> 815 _OI 816 __copy_move_backward_a( 817 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, 818 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, 819 _OI); 820 821 template<bool _IsMove, 822 typename _II, typename _Ite, typename _Seq, typename _Cat> 823 __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> 824 __copy_move_backward_a(_II, _II, 825 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&); 826 827 template<bool _IsMove, 828 typename _IIte, typename _ISeq, typename _ICat, 829 typename _OIte, typename _OSeq, typename _OCat> 830 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> 831 __copy_move_backward_a( 832 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, 833 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&, 834 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&); 835 836 /** 837 * @brief Copies the range [first,last) into result. 838 * @ingroup mutating_algorithms 839 * @param __first A bidirectional iterator. 840 * @param __last A bidirectional iterator. 841 * @param __result A bidirectional iterator. 842 * @return result - (last - first) 843 * 844 * The function has the same effect as copy, but starts at the end of the 845 * range and works its way to the start, returning the start of the result. 846 * This inline function will boil down to a call to @c memmove whenever 847 * possible. Failing that, if random access iterators are passed, then the 848 * loop count will be known (and therefore a candidate for compiler 849 * optimizations such as unrolling). 850 * 851 * Result may not be in the range (first,last]. Use copy instead. Note 852 * that the start of the output range may overlap [first,last). 853 */ 854 template<typename _BI1, typename _BI2> 855 _GLIBCXX20_CONSTEXPR 856 inline _BI2 857 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 858 { 859 // concept requirements 860 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 861 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 862 __glibcxx_function_requires(_OutputIteratorConcept<_BI2, 863 typename iterator_traits<_BI1>::reference>) 864 __glibcxx_requires_can_decrement_range(__first, __last, __result); 865 866 return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value> 867 (std::__miter_base(__first), std::__miter_base(__last), __result); 868 } 869 870 #if __cplusplus >= 201103L 871 /** 872 * @brief Moves the range [first,last) into result. 873 * @ingroup mutating_algorithms 874 * @param __first A bidirectional iterator. 875 * @param __last A bidirectional iterator. 876 * @param __result A bidirectional iterator. 877 * @return result - (last - first) 878 * 879 * The function has the same effect as move, but starts at the end of the 880 * range and works its way to the start, returning the start of the result. 881 * This inline function will boil down to a call to @c memmove whenever 882 * possible. Failing that, if random access iterators are passed, then the 883 * loop count will be known (and therefore a candidate for compiler 884 * optimizations such as unrolling). 885 * 886 * Result may not be in the range (first,last]. Use move instead. Note 887 * that the start of the output range may overlap [first,last). 888 */ 889 template<typename _BI1, typename _BI2> 890 _GLIBCXX20_CONSTEXPR 891 inline _BI2 892 move_backward(_BI1 __first, _BI1 __last, _BI2 __result) 893 { 894 // concept requirements 895 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 896 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 897 __glibcxx_function_requires(_OutputIteratorConcept<_BI2, 898 typename iterator_traits<_BI1>::value_type&&>) 899 __glibcxx_requires_can_decrement_range(__first, __last, __result); 900 901 return std::__copy_move_backward_a<true>(std::__miter_base(__first), 902 std::__miter_base(__last), 903 __result); 904 } 905 906 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) 907 #else 908 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) 909 #endif 910 911 template<typename _ForwardIterator, typename _Tp> 912 _GLIBCXX20_CONSTEXPR 913 inline typename 914 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type 915 __fill_a1(_ForwardIterator __first, _ForwardIterator __last, 916 const _Tp& __value) 917 { 918 for (; __first != __last; ++__first) 919 *__first = __value; 920 } 921 922 template<typename _ForwardIterator, typename _Tp> 923 _GLIBCXX20_CONSTEXPR 924 inline typename 925 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type 926 __fill_a1(_ForwardIterator __first, _ForwardIterator __last, 927 const _Tp& __value) 928 { 929 const _Tp __tmp = __value; 930 for (; __first != __last; ++__first) 931 *__first = __tmp; 932 } 933 934 // Specialization: for char types we can use memset. 935 template<typename _Tp> 936 _GLIBCXX20_CONSTEXPR 937 inline typename 938 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type 939 __fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c) 940 { 941 const _Tp __tmp = __c; 942 #if __cpp_lib_is_constant_evaluated 943 if (std::is_constant_evaluated()) 944 { 945 for (; __first != __last; ++__first) 946 *__first = __tmp; 947 return; 948 } 949 #endif 950 if (const size_t __len = __last - __first) 951 __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len); 952 } 953 954 template<typename _Ite, typename _Cont, typename _Tp> 955 _GLIBCXX20_CONSTEXPR 956 inline void 957 __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first, 958 ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last, 959 const _Tp& __value) 960 { std::__fill_a1(__first.base(), __last.base(), __value); } 961 962 template<typename _Tp, typename _VTp> 963 void 964 __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&, 965 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&, 966 const _VTp&); 967 968 _GLIBCXX20_CONSTEXPR 969 void 970 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator, 971 const bool&); 972 973 template<typename _FIte, typename _Tp> 974 _GLIBCXX20_CONSTEXPR 975 inline void 976 __fill_a(_FIte __first, _FIte __last, const _Tp& __value) 977 { std::__fill_a1(__first, __last, __value); } 978 979 template<typename _Ite, typename _Seq, typename _Cat, typename _Tp> 980 void 981 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, 982 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&, 983 const _Tp&); 984 985 /** 986 * @brief Fills the range [first,last) with copies of value. 987 * @ingroup mutating_algorithms 988 * @param __first A forward iterator. 989 * @param __last A forward iterator. 990 * @param __value A reference-to-const of arbitrary type. 991 * @return Nothing. 992 * 993 * This function fills a range with copies of the same value. For char 994 * types filling contiguous areas of memory, this becomes an inline call 995 * to @c memset or @c wmemset. 996 */ 997 template<typename _ForwardIterator, typename _Tp> 998 _GLIBCXX20_CONSTEXPR 999 inline void 1000 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 1001 { 1002 // concept requirements 1003 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1004 _ForwardIterator>) 1005 __glibcxx_requires_valid_range(__first, __last); 1006 1007 std::__fill_a(__first, __last, __value); 1008 } 1009 1010 // Used by fill_n, generate_n, etc. to convert _Size to an integral type: 1011 inline _GLIBCXX_CONSTEXPR int 1012 __size_to_integer(int __n) { return __n; } 1013 inline _GLIBCXX_CONSTEXPR unsigned 1014 __size_to_integer(unsigned __n) { return __n; } 1015 inline _GLIBCXX_CONSTEXPR long 1016 __size_to_integer(long __n) { return __n; } 1017 inline _GLIBCXX_CONSTEXPR unsigned long 1018 __size_to_integer(unsigned long __n) { return __n; } 1019 inline _GLIBCXX_CONSTEXPR long long 1020 __size_to_integer(long long __n) { return __n; } 1021 inline _GLIBCXX_CONSTEXPR unsigned long long 1022 __size_to_integer(unsigned long long __n) { return __n; } 1023 1024 #if defined(__GLIBCXX_TYPE_INT_N_0) 1025 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0 1026 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) { return __n; } 1027 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0 1028 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n) { return __n; } 1029 #endif 1030 #if defined(__GLIBCXX_TYPE_INT_N_1) 1031 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1 1032 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) { return __n; } 1033 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1 1034 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n) { return __n; } 1035 #endif 1036 #if defined(__GLIBCXX_TYPE_INT_N_2) 1037 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2 1038 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) { return __n; } 1039 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2 1040 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n) { return __n; } 1041 #endif 1042 #if defined(__GLIBCXX_TYPE_INT_N_3) 1043 __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3 1044 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) { return __n; } 1045 __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3 1046 __size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n) { return __n; } 1047 #endif 1048 1049 inline _GLIBCXX_CONSTEXPR long long 1050 __size_to_integer(float __n) { return (long long)__n; } 1051 inline _GLIBCXX_CONSTEXPR long long 1052 __size_to_integer(double __n) { return (long long)__n; } 1053 inline _GLIBCXX_CONSTEXPR long long 1054 __size_to_integer(long double __n) { return (long long)__n; } 1055 #if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128) && !defined(__CUDACC__) 1056 __extension__ inline _GLIBCXX_CONSTEXPR long long 1057 __size_to_integer(__float128 __n) { return (long long)__n; } 1058 #endif 1059 1060 template<typename _OutputIterator, typename _Size, typename _Tp> 1061 _GLIBCXX20_CONSTEXPR 1062 inline typename 1063 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type 1064 __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value) 1065 { 1066 for (; __n > 0; --__n, (void) ++__first) 1067 *__first = __value; 1068 return __first; 1069 } 1070 1071 template<typename _OutputIterator, typename _Size, typename _Tp> 1072 _GLIBCXX20_CONSTEXPR 1073 inline typename 1074 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type 1075 __fill_n_a1(_OutputIterator __first, _Size __n, const _Tp& __value) 1076 { 1077 const _Tp __tmp = __value; 1078 for (; __n > 0; --__n, (void) ++__first) 1079 *__first = __tmp; 1080 return __first; 1081 } 1082 1083 template<typename _Ite, typename _Seq, typename _Cat, typename _Size, 1084 typename _Tp> 1085 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> 1086 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, 1087 _Size __n, const _Tp& __value, 1088 std::input_iterator_tag); 1089 1090 template<typename _OutputIterator, typename _Size, typename _Tp> 1091 _GLIBCXX20_CONSTEXPR 1092 inline _OutputIterator 1093 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, 1094 std::output_iterator_tag) 1095 { 1096 #if __cplusplus >= 201103L 1097 static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); 1098 #endif 1099 return __fill_n_a1(__first, __n, __value); 1100 } 1101 1102 template<typename _OutputIterator, typename _Size, typename _Tp> 1103 _GLIBCXX20_CONSTEXPR 1104 inline _OutputIterator 1105 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, 1106 std::input_iterator_tag) 1107 { 1108 #if __cplusplus >= 201103L 1109 static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); 1110 #endif 1111 return __fill_n_a1(__first, __n, __value); 1112 } 1113 1114 template<typename _OutputIterator, typename _Size, typename _Tp> 1115 _GLIBCXX20_CONSTEXPR 1116 inline _OutputIterator 1117 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value, 1118 std::random_access_iterator_tag) 1119 { 1120 #if __cplusplus >= 201103L 1121 static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); 1122 #endif 1123 if (__n <= 0) 1124 return __first; 1125 1126 __glibcxx_requires_can_increment(__first, __n); 1127 1128 std::__fill_a(__first, __first + __n, __value); 1129 return __first + __n; 1130 } 1131 1132 /** 1133 * @brief Fills the range [first,first+n) with copies of value. 1134 * @ingroup mutating_algorithms 1135 * @param __first An output iterator. 1136 * @param __n The count of copies to perform. 1137 * @param __value A reference-to-const of arbitrary type. 1138 * @return The iterator at first+n. 1139 * 1140 * This function fills a range with copies of the same value. For char 1141 * types filling contiguous areas of memory, this becomes an inline call 1142 * to @c memset or @c wmemset. 1143 * 1144 * If @p __n is negative, the function does nothing. 1145 */ 1146 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1147 // DR 865. More algorithms that throw away information 1148 // DR 426. search_n(), fill_n(), and generate_n() with negative n 1149 template<typename _OI, typename _Size, typename _Tp> 1150 _GLIBCXX20_CONSTEXPR 1151 inline _OI 1152 fill_n(_OI __first, _Size __n, const _Tp& __value) 1153 { 1154 // concept requirements 1155 __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>) 1156 1157 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value, 1158 std::__iterator_category(__first)); 1159 } 1160 1161 template<bool _BoolType> 1162 struct __equal 1163 { 1164 template<typename _II1, typename _II2> 1165 _GLIBCXX20_CONSTEXPR 1166 static bool 1167 equal(_II1 __first1, _II1 __last1, _II2 __first2) 1168 { 1169 for (; __first1 != __last1; ++__first1, (void) ++__first2) 1170 if (!(*__first1 == *__first2)) 1171 return false; 1172 return true; 1173 } 1174 }; 1175 1176 template<> 1177 struct __equal<true> 1178 { 1179 template<typename _Tp> 1180 _GLIBCXX20_CONSTEXPR 1181 static bool 1182 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) 1183 { 1184 if (const size_t __len = (__last1 - __first1)) 1185 return !std::__memcmp(__first1, __first2, __len); 1186 return true; 1187 } 1188 }; 1189 1190 template<typename _Tp, typename _Ref, typename _Ptr, typename _II> 1191 typename __gnu_cxx::__enable_if< 1192 __is_random_access_iter<_II>::__value, bool>::__type 1193 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, 1194 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>, 1195 _II); 1196 1197 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1198 typename _Tp2, typename _Ref2, typename _Ptr2> 1199 bool 1200 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, 1201 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, 1202 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); 1203 1204 template<typename _II, typename _Tp, typename _Ref, typename _Ptr> 1205 typename __gnu_cxx::__enable_if< 1206 __is_random_access_iter<_II>::__value, bool>::__type 1207 __equal_aux1(_II, _II, 1208 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>); 1209 1210 template<typename _II1, typename _II2> 1211 _GLIBCXX20_CONSTEXPR 1212 inline bool 1213 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2) 1214 { 1215 typedef typename iterator_traits<_II1>::value_type _ValueType1; 1216 const bool __simple = ((__is_integer<_ValueType1>::__value 1217 || __is_pointer<_ValueType1>::__value) 1218 && __memcmpable<_II1, _II2>::__value); 1219 return std::__equal<__simple>::equal(__first1, __last1, __first2); 1220 } 1221 1222 template<typename _II1, typename _II2> 1223 _GLIBCXX20_CONSTEXPR 1224 inline bool 1225 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) 1226 { 1227 return std::__equal_aux1(std::__niter_base(__first1), 1228 std::__niter_base(__last1), 1229 std::__niter_base(__first2)); 1230 } 1231 1232 template<typename _II1, typename _Seq1, typename _Cat1, typename _II2> 1233 bool 1234 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, 1235 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, 1236 _II2); 1237 1238 template<typename _II1, typename _II2, typename _Seq2, typename _Cat2> 1239 bool 1240 __equal_aux(_II1, _II1, 1241 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&); 1242 1243 template<typename _II1, typename _Seq1, typename _Cat1, 1244 typename _II2, typename _Seq2, typename _Cat2> 1245 bool 1246 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, 1247 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&, 1248 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&); 1249 1250 template<typename, typename> 1251 struct __lc_rai 1252 { 1253 template<typename _II1, typename _II2> 1254 _GLIBCXX20_CONSTEXPR 1255 static _II1 1256 __newlast1(_II1, _II1 __last1, _II2, _II2) 1257 { return __last1; } 1258 1259 template<typename _II> 1260 _GLIBCXX20_CONSTEXPR 1261 static bool 1262 __cnd2(_II __first, _II __last) 1263 { return __first != __last; } 1264 }; 1265 1266 template<> 1267 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> 1268 { 1269 template<typename _RAI1, typename _RAI2> 1270 _GLIBCXX20_CONSTEXPR 1271 static _RAI1 1272 __newlast1(_RAI1 __first1, _RAI1 __last1, 1273 _RAI2 __first2, _RAI2 __last2) 1274 { 1275 const typename iterator_traits<_RAI1>::difference_type 1276 __diff1 = __last1 - __first1; 1277 const typename iterator_traits<_RAI2>::difference_type 1278 __diff2 = __last2 - __first2; 1279 return __diff2 < __diff1 ? __first1 + __diff2 : __last1; 1280 } 1281 1282 template<typename _RAI> 1283 static _GLIBCXX20_CONSTEXPR bool 1284 __cnd2(_RAI, _RAI) 1285 { return true; } 1286 }; 1287 1288 template<typename _II1, typename _II2, typename _Compare> 1289 _GLIBCXX20_CONSTEXPR 1290 bool 1291 __lexicographical_compare_impl(_II1 __first1, _II1 __last1, 1292 _II2 __first2, _II2 __last2, 1293 _Compare __comp) 1294 { 1295 typedef typename iterator_traits<_II1>::iterator_category _Category1; 1296 typedef typename iterator_traits<_II2>::iterator_category _Category2; 1297 typedef std::__lc_rai<_Category1, _Category2> __rai_type; 1298 1299 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); 1300 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); 1301 ++__first1, (void)++__first2) 1302 { 1303 if (__comp(__first1, __first2)) 1304 return true; 1305 if (__comp(__first2, __first1)) 1306 return false; 1307 } 1308 return __first1 == __last1 && __first2 != __last2; 1309 } 1310 1311 template<bool _BoolType> 1312 struct __lexicographical_compare 1313 { 1314 template<typename _II1, typename _II2> 1315 _GLIBCXX20_CONSTEXPR 1316 static bool 1317 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 1318 { 1319 using __gnu_cxx::__ops::__iter_less_iter; 1320 return std::__lexicographical_compare_impl(__first1, __last1, 1321 __first2, __last2, 1322 __iter_less_iter()); 1323 } 1324 1325 template<typename _II1, typename _II2> 1326 _GLIBCXX20_CONSTEXPR 1327 static int 1328 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 1329 { 1330 while (__first1 != __last1) 1331 { 1332 if (__first2 == __last2) 1333 return +1; 1334 if (*__first1 < *__first2) 1335 return -1; 1336 if (*__first2 < *__first1) 1337 return +1; 1338 ++__first1; 1339 ++__first2; 1340 } 1341 return int(__first2 == __last2) - 1; 1342 } 1343 }; 1344 1345 template<> 1346 struct __lexicographical_compare<true> 1347 { 1348 template<typename _Tp, typename _Up> 1349 _GLIBCXX20_CONSTEXPR 1350 static bool 1351 __lc(const _Tp* __first1, const _Tp* __last1, 1352 const _Up* __first2, const _Up* __last2) 1353 { return __3way(__first1, __last1, __first2, __last2) < 0; } 1354 1355 template<typename _Tp, typename _Up> 1356 _GLIBCXX20_CONSTEXPR 1357 static ptrdiff_t 1358 __3way(const _Tp* __first1, const _Tp* __last1, 1359 const _Up* __first2, const _Up* __last2) 1360 { 1361 const size_t __len1 = __last1 - __first1; 1362 const size_t __len2 = __last2 - __first2; 1363 if (const size_t __len = std::min(__len1, __len2)) 1364 if (int __result = std::__memcmp(__first1, __first2, __len)) 1365 return __result; 1366 return ptrdiff_t(__len1 - __len2); 1367 } 1368 }; 1369 1370 template<typename _II1, typename _II2> 1371 _GLIBCXX20_CONSTEXPR 1372 inline bool 1373 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1, 1374 _II2 __first2, _II2 __last2) 1375 { 1376 typedef typename iterator_traits<_II1>::value_type _ValueType1; 1377 typedef typename iterator_traits<_II2>::value_type _ValueType2; 1378 const bool __simple = 1379 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value 1380 && __is_pointer<_II1>::__value 1381 && __is_pointer<_II2>::__value 1382 #if __cplusplus > 201703L && __cpp_lib_concepts 1383 // For C++20 iterator_traits<volatile T*>::value_type is non-volatile 1384 // so __is_byte<T> could be true, but we can't use memcmp with 1385 // volatile data. 1386 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>> 1387 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>> 1388 #endif 1389 ); 1390 1391 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, 1392 __first2, __last2); 1393 } 1394 1395 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1396 typename _Tp2> 1397 bool 1398 __lexicographical_compare_aux1( 1399 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, 1400 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, 1401 _Tp2*, _Tp2*); 1402 1403 template<typename _Tp1, 1404 typename _Tp2, typename _Ref2, typename _Ptr2> 1405 bool 1406 __lexicographical_compare_aux1(_Tp1*, _Tp1*, 1407 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>, 1408 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); 1409 1410 template<typename _Tp1, typename _Ref1, typename _Ptr1, 1411 typename _Tp2, typename _Ref2, typename _Ptr2> 1412 bool 1413 __lexicographical_compare_aux1( 1414 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, 1415 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>, 1416 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>, 1417 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>); 1418 1419 template<typename _II1, typename _II2> 1420 _GLIBCXX20_CONSTEXPR 1421 inline bool 1422 __lexicographical_compare_aux(_II1 __first1, _II1 __last1, 1423 _II2 __first2, _II2 __last2) 1424 { 1425 return std::__lexicographical_compare_aux1(std::__niter_base(__first1), 1426 std::__niter_base(__last1), 1427 std::__niter_base(__first2), 1428 std::__niter_base(__last2)); 1429 } 1430 1431 template<typename _Iter1, typename _Seq1, typename _Cat1, 1432 typename _II2> 1433 bool 1434 __lexicographical_compare_aux( 1435 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, 1436 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, 1437 _II2, _II2); 1438 1439 template<typename _II1, 1440 typename _Iter2, typename _Seq2, typename _Cat2> 1441 bool 1442 __lexicographical_compare_aux( 1443 _II1, _II1, 1444 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&, 1445 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&); 1446 1447 template<typename _Iter1, typename _Seq1, typename _Cat1, 1448 typename _Iter2, typename _Seq2, typename _Cat2> 1449 bool 1450 __lexicographical_compare_aux( 1451 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, 1452 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&, 1453 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&, 1454 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&); 1455 1456 template<typename _ForwardIterator, typename _Tp, typename _Compare> 1457 _GLIBCXX20_CONSTEXPR 1458 _ForwardIterator 1459 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, 1460 const _Tp& __val, _Compare __comp) 1461 { 1462 typedef typename iterator_traits<_ForwardIterator>::difference_type 1463 _DistanceType; 1464 1465 _DistanceType __len = std::distance(__first, __last); 1466 1467 while (__len > 0) 1468 { 1469 _DistanceType __half = __len >> 1; 1470 _ForwardIterator __middle = __first; 1471 std::advance(__middle, __half); 1472 if (__comp(__middle, __val)) 1473 { 1474 __first = __middle; 1475 ++__first; 1476 __len = __len - __half - 1; 1477 } 1478 else 1479 __len = __half; 1480 } 1481 return __first; 1482 } 1483 1484 /** 1485 * @brief Finds the first position in which @a val could be inserted 1486 * without changing the ordering. 1487 * @param __first An iterator. 1488 * @param __last Another iterator. 1489 * @param __val The search term. 1490 * @return An iterator pointing to the first element <em>not less 1491 * than</em> @a val, or end() if every element is less than 1492 * @a val. 1493 * @ingroup binary_search_algorithms 1494 */ 1495 template<typename _ForwardIterator, typename _Tp> 1496 _GLIBCXX20_CONSTEXPR 1497 inline _ForwardIterator 1498 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 1499 const _Tp& __val) 1500 { 1501 // concept requirements 1502 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1503 __glibcxx_function_requires(_LessThanOpConcept< 1504 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 1505 __glibcxx_requires_partitioned_lower(__first, __last, __val); 1506 1507 return std::__lower_bound(__first, __last, __val, 1508 __gnu_cxx::__ops::__iter_less_val()); 1509 } 1510 1511 /// This is a helper function for the sort routines and for random.tcc. 1512 // Precondition: __n > 0. 1513 template<typename _Tp> 1514 inline _GLIBCXX_CONSTEXPR _Tp 1515 __lg(_Tp __n) 1516 { 1517 #if __cplusplus >= 201402L 1518 return std::__bit_width(make_unsigned_t<_Tp>(__n)) - 1; 1519 #else 1520 // Use +__n so it promotes to at least int. 1521 return (sizeof(+__n) * __CHAR_BIT__ - 1) 1522 - (sizeof(+__n) == sizeof(long long) 1523 ? __builtin_clzll(+__n) 1524 : (sizeof(+__n) == sizeof(long) 1525 ? __builtin_clzl(+__n) 1526 : __builtin_clz(+__n))); 1527 #endif 1528 } 1529 1530 _GLIBCXX_BEGIN_NAMESPACE_ALGO 1531 1532 /** 1533 * @brief Tests a range for element-wise equality. 1534 * @ingroup non_mutating_algorithms 1535 * @param __first1 An input iterator. 1536 * @param __last1 An input iterator. 1537 * @param __first2 An input iterator. 1538 * @return A boolean true or false. 1539 * 1540 * This compares the elements of two ranges using @c == and returns true or 1541 * false depending on whether all of the corresponding elements of the 1542 * ranges are equal. 1543 */ 1544 template<typename _II1, typename _II2> 1545 _GLIBCXX20_CONSTEXPR 1546 inline bool 1547 equal(_II1 __first1, _II1 __last1, _II2 __first2) 1548 { 1549 // concept requirements 1550 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1551 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1552 __glibcxx_function_requires(_EqualOpConcept< 1553 typename iterator_traits<_II1>::value_type, 1554 typename iterator_traits<_II2>::value_type>) 1555 __glibcxx_requires_can_increment_range(__first1, __last1, __first2); 1556 1557 return std::__equal_aux(__first1, __last1, __first2); 1558 } 1559 1560 /** 1561 * @brief Tests a range for element-wise equality. 1562 * @ingroup non_mutating_algorithms 1563 * @param __first1 An input iterator. 1564 * @param __last1 An input iterator. 1565 * @param __first2 An input iterator. 1566 * @param __binary_pred A binary predicate @link functors 1567 * functor@endlink. 1568 * @return A boolean true or false. 1569 * 1570 * This compares the elements of two ranges using the binary_pred 1571 * parameter, and returns true or 1572 * false depending on whether all of the corresponding elements of the 1573 * ranges are equal. 1574 */ 1575 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 1576 _GLIBCXX20_CONSTEXPR 1577 inline bool 1578 equal(_IIter1 __first1, _IIter1 __last1, 1579 _IIter2 __first2, _BinaryPredicate __binary_pred) 1580 { 1581 // concept requirements 1582 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 1583 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 1584 __glibcxx_requires_valid_range(__first1, __last1); 1585 1586 for (; __first1 != __last1; ++__first1, (void)++__first2) 1587 if (!bool(__binary_pred(*__first1, *__first2))) 1588 return false; 1589 return true; 1590 } 1591 1592 #if __cplusplus >= 201103L 1593 // 4-iterator version of std::equal<It1, It2> for use in C++11. 1594 template<typename _II1, typename _II2> 1595 _GLIBCXX20_CONSTEXPR 1596 inline bool 1597 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 1598 { 1599 using _RATag = random_access_iterator_tag; 1600 using _Cat1 = typename iterator_traits<_II1>::iterator_category; 1601 using _Cat2 = typename iterator_traits<_II2>::iterator_category; 1602 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 1603 if (_RAIters()) 1604 { 1605 auto __d1 = std::distance(__first1, __last1); 1606 auto __d2 = std::distance(__first2, __last2); 1607 if (__d1 != __d2) 1608 return false; 1609 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2); 1610 } 1611 1612 for (; __first1 != __last1 && __first2 != __last2; 1613 ++__first1, (void)++__first2) 1614 if (!(*__first1 == *__first2)) 1615 return false; 1616 return __first1 == __last1 && __first2 == __last2; 1617 } 1618 1619 // 4-iterator version of std::equal<It1, It2, BinaryPred> for use in C++11. 1620 template<typename _II1, typename _II2, typename _BinaryPredicate> 1621 _GLIBCXX20_CONSTEXPR 1622 inline bool 1623 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, 1624 _BinaryPredicate __binary_pred) 1625 { 1626 using _RATag = random_access_iterator_tag; 1627 using _Cat1 = typename iterator_traits<_II1>::iterator_category; 1628 using _Cat2 = typename iterator_traits<_II2>::iterator_category; 1629 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 1630 if (_RAIters()) 1631 { 1632 auto __d1 = std::distance(__first1, __last1); 1633 auto __d2 = std::distance(__first2, __last2); 1634 if (__d1 != __d2) 1635 return false; 1636 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, 1637 __binary_pred); 1638 } 1639 1640 for (; __first1 != __last1 && __first2 != __last2; 1641 ++__first1, (void)++__first2) 1642 if (!bool(__binary_pred(*__first1, *__first2))) 1643 return false; 1644 return __first1 == __last1 && __first2 == __last2; 1645 } 1646 #endif // C++11 1647 1648 #if __cplusplus > 201103L 1649 1650 #define __cpp_lib_robust_nonmodifying_seq_ops 201304L 1651 1652 /** 1653 * @brief Tests a range for element-wise equality. 1654 * @ingroup non_mutating_algorithms 1655 * @param __first1 An input iterator. 1656 * @param __last1 An input iterator. 1657 * @param __first2 An input iterator. 1658 * @param __last2 An input iterator. 1659 * @return A boolean true or false. 1660 * 1661 * This compares the elements of two ranges using @c == and returns true or 1662 * false depending on whether all of the corresponding elements of the 1663 * ranges are equal. 1664 */ 1665 template<typename _II1, typename _II2> 1666 _GLIBCXX20_CONSTEXPR 1667 inline bool 1668 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 1669 { 1670 // concept requirements 1671 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1672 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1673 __glibcxx_function_requires(_EqualOpConcept< 1674 typename iterator_traits<_II1>::value_type, 1675 typename iterator_traits<_II2>::value_type>) 1676 __glibcxx_requires_valid_range(__first1, __last1); 1677 __glibcxx_requires_valid_range(__first2, __last2); 1678 1679 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2); 1680 } 1681 1682 /** 1683 * @brief Tests a range for element-wise equality. 1684 * @ingroup non_mutating_algorithms 1685 * @param __first1 An input iterator. 1686 * @param __last1 An input iterator. 1687 * @param __first2 An input iterator. 1688 * @param __last2 An input iterator. 1689 * @param __binary_pred A binary predicate @link functors 1690 * functor@endlink. 1691 * @return A boolean true or false. 1692 * 1693 * This compares the elements of two ranges using the binary_pred 1694 * parameter, and returns true or 1695 * false depending on whether all of the corresponding elements of the 1696 * ranges are equal. 1697 */ 1698 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 1699 _GLIBCXX20_CONSTEXPR 1700 inline bool 1701 equal(_IIter1 __first1, _IIter1 __last1, 1702 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred) 1703 { 1704 // concept requirements 1705 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 1706 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 1707 __glibcxx_requires_valid_range(__first1, __last1); 1708 __glibcxx_requires_valid_range(__first2, __last2); 1709 1710 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2, 1711 __binary_pred); 1712 } 1713 #endif // C++14 1714 1715 /** 1716 * @brief Performs @b dictionary comparison on ranges. 1717 * @ingroup sorting_algorithms 1718 * @param __first1 An input iterator. 1719 * @param __last1 An input iterator. 1720 * @param __first2 An input iterator. 1721 * @param __last2 An input iterator. 1722 * @return A boolean true or false. 1723 * 1724 * <em>Returns true if the sequence of elements defined by the range 1725 * [first1,last1) is lexicographically less than the sequence of elements 1726 * defined by the range [first2,last2). Returns false otherwise.</em> 1727 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 1728 * then this is an inline call to @c memcmp. 1729 */ 1730 template<typename _II1, typename _II2> 1731 _GLIBCXX20_CONSTEXPR 1732 inline bool 1733 lexicographical_compare(_II1 __first1, _II1 __last1, 1734 _II2 __first2, _II2 __last2) 1735 { 1736 #ifdef _GLIBCXX_CONCEPT_CHECKS 1737 // concept requirements 1738 typedef typename iterator_traits<_II1>::value_type _ValueType1; 1739 typedef typename iterator_traits<_II2>::value_type _ValueType2; 1740 #endif 1741 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1742 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1743 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 1744 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 1745 __glibcxx_requires_valid_range(__first1, __last1); 1746 __glibcxx_requires_valid_range(__first2, __last2); 1747 1748 return std::__lexicographical_compare_aux(__first1, __last1, 1749 __first2, __last2); 1750 } 1751 1752 /** 1753 * @brief Performs @b dictionary comparison on ranges. 1754 * @ingroup sorting_algorithms 1755 * @param __first1 An input iterator. 1756 * @param __last1 An input iterator. 1757 * @param __first2 An input iterator. 1758 * @param __last2 An input iterator. 1759 * @param __comp A @link comparison_functors comparison functor@endlink. 1760 * @return A boolean true or false. 1761 * 1762 * The same as the four-parameter @c lexicographical_compare, but uses the 1763 * comp parameter instead of @c <. 1764 */ 1765 template<typename _II1, typename _II2, typename _Compare> 1766 _GLIBCXX20_CONSTEXPR 1767 inline bool 1768 lexicographical_compare(_II1 __first1, _II1 __last1, 1769 _II2 __first2, _II2 __last2, _Compare __comp) 1770 { 1771 // concept requirements 1772 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1773 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1774 __glibcxx_requires_valid_range(__first1, __last1); 1775 __glibcxx_requires_valid_range(__first2, __last2); 1776 1777 return std::__lexicographical_compare_impl 1778 (__first1, __last1, __first2, __last2, 1779 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 1780 } 1781 1782 #if __cpp_lib_three_way_comparison 1783 // Both iterators refer to contiguous ranges of unsigned narrow characters, 1784 // or std::byte, or big-endian unsigned integers, suitable for comparison 1785 // using memcmp. 1786 template<typename _Iter1, typename _Iter2> 1787 concept __memcmp_ordered_with 1788 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>, 1789 iter_value_t<_Iter2>>::__value) 1790 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>; 1791 1792 // Return a struct with two members, initialized to the smaller of x and y 1793 // (or x if they compare equal) and the result of the comparison x <=> y. 1794 template<typename _Tp> 1795 constexpr auto 1796 __min_cmp(_Tp __x, _Tp __y) 1797 { 1798 struct _Res { 1799 _Tp _M_min; 1800 decltype(__x <=> __y) _M_cmp; 1801 }; 1802 auto __c = __x <=> __y; 1803 if (__c > 0) 1804 return _Res{__y, __c}; 1805 return _Res{__x, __c}; 1806 } 1807 1808 /** 1809 * @brief Performs dictionary comparison on ranges. 1810 * @ingroup sorting_algorithms 1811 * @param __first1 An input iterator. 1812 * @param __last1 An input iterator. 1813 * @param __first2 An input iterator. 1814 * @param __last2 An input iterator. 1815 * @param __comp A @link comparison_functors comparison functor@endlink. 1816 * @return The comparison category that `__comp(*__first1, *__first2)` 1817 * returns. 1818 */ 1819 template<typename _InputIter1, typename _InputIter2, typename _Comp> 1820 constexpr auto 1821 lexicographical_compare_three_way(_InputIter1 __first1, 1822 _InputIter1 __last1, 1823 _InputIter2 __first2, 1824 _InputIter2 __last2, 1825 _Comp __comp) 1826 -> decltype(__comp(*__first1, *__first2)) 1827 { 1828 // concept requirements 1829 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>) 1830 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>) 1831 __glibcxx_requires_valid_range(__first1, __last1); 1832 __glibcxx_requires_valid_range(__first2, __last2); 1833 1834 using _Cat = decltype(__comp(*__first1, *__first2)); 1835 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>); 1836 1837 if (!std::__is_constant_evaluated()) 1838 if constexpr (same_as<_Comp, __detail::_Synth3way> 1839 || same_as<_Comp, compare_three_way>) 1840 if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>) 1841 { 1842 const auto [__len, __lencmp] = _GLIBCXX_STD_A:: 1843 __min_cmp(__last1 - __first1, __last2 - __first2); 1844 if (__len) 1845 { 1846 const auto __blen = __len * sizeof(*__first1); 1847 const auto __c 1848 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0; 1849 if (__c != 0) 1850 return __c; 1851 } 1852 return __lencmp; 1853 } 1854 1855 while (__first1 != __last1) 1856 { 1857 if (__first2 == __last2) 1858 return strong_ordering::greater; 1859 if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0) 1860 return __cmp; 1861 ++__first1; 1862 ++__first2; 1863 } 1864 return (__first2 == __last2) <=> true; // See PR 94006 1865 } 1866 1867 template<typename _InputIter1, typename _InputIter2> 1868 constexpr auto 1869 lexicographical_compare_three_way(_InputIter1 __first1, 1870 _InputIter1 __last1, 1871 _InputIter2 __first2, 1872 _InputIter2 __last2) 1873 { 1874 return _GLIBCXX_STD_A:: 1875 lexicographical_compare_three_way(__first1, __last1, __first2, __last2, 1876 compare_three_way{}); 1877 } 1878 #endif // three_way_comparison 1879 1880 template<typename _InputIterator1, typename _InputIterator2, 1881 typename _BinaryPredicate> 1882 _GLIBCXX20_CONSTEXPR 1883 pair<_InputIterator1, _InputIterator2> 1884 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1885 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 1886 { 1887 while (__first1 != __last1 && __binary_pred(__first1, __first2)) 1888 { 1889 ++__first1; 1890 ++__first2; 1891 } 1892 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 1893 } 1894 1895 /** 1896 * @brief Finds the places in ranges which don't match. 1897 * @ingroup non_mutating_algorithms 1898 * @param __first1 An input iterator. 1899 * @param __last1 An input iterator. 1900 * @param __first2 An input iterator. 1901 * @return A pair of iterators pointing to the first mismatch. 1902 * 1903 * This compares the elements of two ranges using @c == and returns a pair 1904 * of iterators. The first iterator points into the first range, the 1905 * second iterator points into the second range, and the elements pointed 1906 * to by the iterators are not equal. 1907 */ 1908 template<typename _InputIterator1, typename _InputIterator2> 1909 _GLIBCXX20_CONSTEXPR 1910 inline pair<_InputIterator1, _InputIterator2> 1911 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1912 _InputIterator2 __first2) 1913 { 1914 // concept requirements 1915 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 1916 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 1917 __glibcxx_function_requires(_EqualOpConcept< 1918 typename iterator_traits<_InputIterator1>::value_type, 1919 typename iterator_traits<_InputIterator2>::value_type>) 1920 __glibcxx_requires_valid_range(__first1, __last1); 1921 1922 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 1923 __gnu_cxx::__ops::__iter_equal_to_iter()); 1924 } 1925 1926 /** 1927 * @brief Finds the places in ranges which don't match. 1928 * @ingroup non_mutating_algorithms 1929 * @param __first1 An input iterator. 1930 * @param __last1 An input iterator. 1931 * @param __first2 An input iterator. 1932 * @param __binary_pred A binary predicate @link functors 1933 * functor@endlink. 1934 * @return A pair of iterators pointing to the first mismatch. 1935 * 1936 * This compares the elements of two ranges using the binary_pred 1937 * parameter, and returns a pair 1938 * of iterators. The first iterator points into the first range, the 1939 * second iterator points into the second range, and the elements pointed 1940 * to by the iterators are not equal. 1941 */ 1942 template<typename _InputIterator1, typename _InputIterator2, 1943 typename _BinaryPredicate> 1944 _GLIBCXX20_CONSTEXPR 1945 inline pair<_InputIterator1, _InputIterator2> 1946 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1947 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 1948 { 1949 // concept requirements 1950 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 1951 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 1952 __glibcxx_requires_valid_range(__first1, __last1); 1953 1954 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 1955 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 1956 } 1957 1958 #if __cplusplus > 201103L 1959 1960 template<typename _InputIterator1, typename _InputIterator2, 1961 typename _BinaryPredicate> 1962 _GLIBCXX20_CONSTEXPR 1963 pair<_InputIterator1, _InputIterator2> 1964 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1965 _InputIterator2 __first2, _InputIterator2 __last2, 1966 _BinaryPredicate __binary_pred) 1967 { 1968 while (__first1 != __last1 && __first2 != __last2 1969 && __binary_pred(__first1, __first2)) 1970 { 1971 ++__first1; 1972 ++__first2; 1973 } 1974 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 1975 } 1976 1977 /** 1978 * @brief Finds the places in ranges which don't match. 1979 * @ingroup non_mutating_algorithms 1980 * @param __first1 An input iterator. 1981 * @param __last1 An input iterator. 1982 * @param __first2 An input iterator. 1983 * @param __last2 An input iterator. 1984 * @return A pair of iterators pointing to the first mismatch. 1985 * 1986 * This compares the elements of two ranges using @c == and returns a pair 1987 * of iterators. The first iterator points into the first range, the 1988 * second iterator points into the second range, and the elements pointed 1989 * to by the iterators are not equal. 1990 */ 1991 template<typename _InputIterator1, typename _InputIterator2> 1992 _GLIBCXX20_CONSTEXPR 1993 inline pair<_InputIterator1, _InputIterator2> 1994 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1995 _InputIterator2 __first2, _InputIterator2 __last2) 1996 { 1997 // concept requirements 1998 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 1999 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2000 __glibcxx_function_requires(_EqualOpConcept< 2001 typename iterator_traits<_InputIterator1>::value_type, 2002 typename iterator_traits<_InputIterator2>::value_type>) 2003 __glibcxx_requires_valid_range(__first1, __last1); 2004 __glibcxx_requires_valid_range(__first2, __last2); 2005 2006 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 2007 __gnu_cxx::__ops::__iter_equal_to_iter()); 2008 } 2009 2010 /** 2011 * @brief Finds the places in ranges which don't match. 2012 * @ingroup non_mutating_algorithms 2013 * @param __first1 An input iterator. 2014 * @param __last1 An input iterator. 2015 * @param __first2 An input iterator. 2016 * @param __last2 An input iterator. 2017 * @param __binary_pred A binary predicate @link functors 2018 * functor@endlink. 2019 * @return A pair of iterators pointing to the first mismatch. 2020 * 2021 * This compares the elements of two ranges using the binary_pred 2022 * parameter, and returns a pair 2023 * of iterators. The first iterator points into the first range, the 2024 * second iterator points into the second range, and the elements pointed 2025 * to by the iterators are not equal. 2026 */ 2027 template<typename _InputIterator1, typename _InputIterator2, 2028 typename _BinaryPredicate> 2029 _GLIBCXX20_CONSTEXPR 2030 inline pair<_InputIterator1, _InputIterator2> 2031 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 2032 _InputIterator2 __first2, _InputIterator2 __last2, 2033 _BinaryPredicate __binary_pred) 2034 { 2035 // concept requirements 2036 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2037 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2038 __glibcxx_requires_valid_range(__first1, __last1); 2039 __glibcxx_requires_valid_range(__first2, __last2); 2040 2041 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 2042 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 2043 } 2044 #endif 2045 2046 _GLIBCXX_END_NAMESPACE_ALGO 2047 2048 /// This is an overload used by find algos for the Input Iterator case. 2049 template<typename _InputIterator, typename _Predicate> 2050 _GLIBCXX20_CONSTEXPR 2051 inline _InputIterator 2052 __find_if(_InputIterator __first, _InputIterator __last, 2053 _Predicate __pred, input_iterator_tag) 2054 { 2055 while (__first != __last && !__pred(__first)) 2056 ++__first; 2057 return __first; 2058 } 2059 2060 /// This is an overload used by find algos for the RAI case. 2061 template<typename _RandomAccessIterator, typename _Predicate> 2062 _GLIBCXX20_CONSTEXPR 2063 _RandomAccessIterator 2064 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, 2065 _Predicate __pred, random_access_iterator_tag) 2066 { 2067 typename iterator_traits<_RandomAccessIterator>::difference_type 2068 __trip_count = (__last - __first) >> 2; 2069 2070 for (; __trip_count > 0; --__trip_count) 2071 { 2072 if (__pred(__first)) 2073 return __first; 2074 ++__first; 2075 2076 if (__pred(__first)) 2077 return __first; 2078 ++__first; 2079 2080 if (__pred(__first)) 2081 return __first; 2082 ++__first; 2083 2084 if (__pred(__first)) 2085 return __first; 2086 ++__first; 2087 } 2088 2089 switch (__last - __first) 2090 { 2091 case 3: 2092 if (__pred(__first)) 2093 return __first; 2094 ++__first; 2095 // FALLTHRU 2096 case 2: 2097 if (__pred(__first)) 2098 return __first; 2099 ++__first; 2100 // FALLTHRU 2101 case 1: 2102 if (__pred(__first)) 2103 return __first; 2104 ++__first; 2105 // FALLTHRU 2106 case 0: 2107 default: 2108 return __last; 2109 } 2110 } 2111 2112 template<typename _Iterator, typename _Predicate> 2113 _GLIBCXX20_CONSTEXPR 2114 inline _Iterator 2115 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred) 2116 { 2117 return __find_if(__first, __last, __pred, 2118 std::__iterator_category(__first)); 2119 } 2120 2121 template<typename _InputIterator, typename _Predicate> 2122 _GLIBCXX20_CONSTEXPR 2123 typename iterator_traits<_InputIterator>::difference_type 2124 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 2125 { 2126 typename iterator_traits<_InputIterator>::difference_type __n = 0; 2127 for (; __first != __last; ++__first) 2128 if (__pred(__first)) 2129 ++__n; 2130 return __n; 2131 } 2132 2133 template<typename _ForwardIterator, typename _Predicate> 2134 _GLIBCXX20_CONSTEXPR 2135 _ForwardIterator 2136 __remove_if(_ForwardIterator __first, _ForwardIterator __last, 2137 _Predicate __pred) 2138 { 2139 __first = std::__find_if(__first, __last, __pred); 2140 if (__first == __last) 2141 return __first; 2142 _ForwardIterator __result = __first; 2143 ++__first; 2144 for (; __first != __last; ++__first) 2145 if (!__pred(__first)) 2146 { 2147 *__result = _GLIBCXX_MOVE(*__first); 2148 ++__result; 2149 } 2150 return __result; 2151 } 2152 2153 #if __cplusplus >= 201103L 2154 template<typename _ForwardIterator1, typename _ForwardIterator2, 2155 typename _BinaryPredicate> 2156 _GLIBCXX20_CONSTEXPR 2157 bool 2158 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 2159 _ForwardIterator2 __first2, _BinaryPredicate __pred) 2160 { 2161 // Efficiently compare identical prefixes: O(N) if sequences 2162 // have the same elements in the same order. 2163 for (; __first1 != __last1; ++__first1, (void)++__first2) 2164 if (!__pred(__first1, __first2)) 2165 break; 2166 2167 if (__first1 == __last1) 2168 return true; 2169 2170 // Establish __last2 assuming equal ranges by iterating over the 2171 // rest of the list. 2172 _ForwardIterator2 __last2 = __first2; 2173 std::advance(__last2, std::distance(__first1, __last1)); 2174 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 2175 { 2176 if (__scan != std::__find_if(__first1, __scan, 2177 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 2178 continue; // We've seen this one before. 2179 2180 auto __matches 2181 = std::__count_if(__first2, __last2, 2182 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 2183 if (0 == __matches || 2184 std::__count_if(__scan, __last1, 2185 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 2186 != __matches) 2187 return false; 2188 } 2189 return true; 2190 } 2191 2192 /** 2193 * @brief Checks whether a permutation of the second sequence is equal 2194 * to the first sequence. 2195 * @ingroup non_mutating_algorithms 2196 * @param __first1 Start of first range. 2197 * @param __last1 End of first range. 2198 * @param __first2 Start of second range. 2199 * @return true if there exists a permutation of the elements in the range 2200 * [__first2, __first2 + (__last1 - __first1)), beginning with 2201 * ForwardIterator2 begin, such that equal(__first1, __last1, begin) 2202 * returns true; otherwise, returns false. 2203 */ 2204 template<typename _ForwardIterator1, typename _ForwardIterator2> 2205 _GLIBCXX20_CONSTEXPR 2206 inline bool 2207 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 2208 _ForwardIterator2 __first2) 2209 { 2210 // concept requirements 2211 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 2212 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 2213 __glibcxx_function_requires(_EqualOpConcept< 2214 typename iterator_traits<_ForwardIterator1>::value_type, 2215 typename iterator_traits<_ForwardIterator2>::value_type>) 2216 __glibcxx_requires_valid_range(__first1, __last1); 2217 2218 return std::__is_permutation(__first1, __last1, __first2, 2219 __gnu_cxx::__ops::__iter_equal_to_iter()); 2220 } 2221 #endif // C++11 2222 2223 _GLIBCXX_END_NAMESPACE_VERSION 2224 } // namespace std 2225 2226 // NB: This file is included within many other C++ includes, as a way 2227 // of getting the base algorithms. So, make sure that parallel bits 2228 // come in too if requested. 2229 #ifdef _GLIBCXX_PARALLEL 2230 # include <parallel/algobase.h> 2231 #endif 2232 2233 #endif
Welcome to MyWebUniversity on April 15, 2025.
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
