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