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