1 // Core algorithmic facilities -*- C++ -*- 2 3 // Copyright (C) 2001-2015 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 and _GLIBCXX_MOVE 71 #include <bits/predefined_ops.h> 72 73 namespace std _GLIBCXX_VISIBILITY(default) 74 { 75 _GLIBCXX_BEGIN_NAMESPACE_VERSION 76 77 #if __cplusplus < 201103L 78 // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a 79 // nutshell, we are partially implementing the resolution of DR 187, 80 // when it's safe, i.e., the value_types are equal. 81 template<bool _BoolType> 82 struct __iter_swap 83 { 84 template<typename _ForwardIterator1, typename _ForwardIterator2> 85 static void 86 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 87 { 88 typedef typename iterator_traits<_ForwardIterator1>::value_type 89 _ValueType1; 90 _ValueType1 __tmp = _GLIBCXX_MOVE(*__a); 91 *__a = _GLIBCXX_MOVE(*__b); 92 *__b = _GLIBCXX_MOVE(__tmp); 93 } 94 }; 95 96 template<> 97 struct __iter_swap<true> 98 { 99 template<typename _ForwardIterator1, typename _ForwardIterator2> 100 static void 101 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 102 { 103 swap(*__a, *__b); 104 } 105 }; 106 #endif 107 108 /** 109 * @brief Swaps the contents of two iterators. 110 * @ingroup mutating_algorithms 111 * @param __a An iterator. 112 * @param __b Another iterator. 113 * @return Nothing. 114 * 115 * This function swaps the values pointed to by two iterators, not the 116 * iterators themselves. 117 */ 118 template<typename _ForwardIterator1, typename _ForwardIterator2> 119 inline void 120 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) 121 { 122 // concept requirements 123 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 124 _ForwardIterator1>) 125 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 126 _ForwardIterator2>) 127 128 #if __cplusplus < 201103L 129 typedef typename iterator_traits<_ForwardIterator1>::value_type 130 _ValueType1; 131 typedef typename iterator_traits<_ForwardIterator2>::value_type 132 _ValueType2; 133 134 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1, 135 _ValueType2>) 136 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, 137 _ValueType1>) 138 139 typedef typename iterator_traits<_ForwardIterator1>::reference 140 _ReferenceType1; 141 typedef typename iterator_traits<_ForwardIterator2>::reference 142 _ReferenceType2; 143 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value 144 && __are_same<_ValueType1&, _ReferenceType1>::__value 145 && __are_same<_ValueType2&, _ReferenceType2>::__value>:: 146 iter_swap(__a, __b); 147 #else 148 swap(*__a, *__b); 149 #endif 150 } 151 152 /** 153 * @brief Swap the elements of two sequences. 154 * @ingroup mutating_algorithms 155 * @param __first1 A forward iterator. 156 * @param __last1 A forward iterator. 157 * @param __first2 A forward iterator. 158 * @return An iterator equal to @p first2+(last1-first1). 159 * 160 * Swaps each element in the range @p [first1,last1) with the 161 * corresponding element in the range @p [first2,(last1-first1)). 162 * The ranges must not overlap. 163 */ 164 template<typename _ForwardIterator1, typename _ForwardIterator2> 165 _ForwardIterator2 166 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 167 _ForwardIterator2 __first2) 168 { 169 // concept requirements 170 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 171 _ForwardIterator1>) 172 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 173 _ForwardIterator2>) 174 __glibcxx_requires_valid_range(__first1, __last1); 175 176 for (; __first1 != __last1; ++__first1, ++__first2) 177 std::iter_swap(__first1, __first2); 178 return __first2; 179 } 180 181 /** 182 * @brief This does what you think it does. 183 * @ingroup sorting_algorithms 184 * @param __a A thing of arbitrary type. 185 * @param __b Another thing of arbitrary type. 186 * @return The lesser of the parameters. 187 * 188 * This is the simple classic generic implementation. It will work on 189 * temporary expressions, since they are only evaluated once, unlike a 190 * preprocessor macro. 191 */ 192 template<typename _Tp> 193 _GLIBCXX14_CONSTEXPR 194 inline const _Tp& 195 min(const _Tp& __a, const _Tp& __b) 196 { 197 // concept requirements 198 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 199 //return __b < __a ? __b : __a; 200 if (__b < __a) 201 return __b; 202 return __a; 203 } 204 205 /** 206 * @brief This does what you think it does. 207 * @ingroup sorting_algorithms 208 * @param __a A thing of arbitrary type. 209 * @param __b Another thing of arbitrary type. 210 * @return The greater of the parameters. 211 * 212 * This is the simple classic generic implementation. It will work on 213 * temporary expressions, since they are only evaluated once, unlike a 214 * preprocessor macro. 215 */ 216 template<typename _Tp> 217 _GLIBCXX14_CONSTEXPR 218 inline const _Tp& 219 max(const _Tp& __a, const _Tp& __b) 220 { 221 // concept requirements 222 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 223 //return __a < __b ? __b : __a; 224 if (__a < __b) 225 return __b; 226 return __a; 227 } 228 229 /** 230 * @brief This does what you think it does. 231 * @ingroup sorting_algorithms 232 * @param __a A thing of arbitrary type. 233 * @param __b Another thing of arbitrary type. 234 * @param __comp A @link comparison_functors comparison functor@endlink. 235 * @return The lesser of the parameters. 236 * 237 * This will work on temporary expressions, since they are only evaluated 238 * once, unlike a preprocessor macro. 239 */ 240 template<typename _Tp, typename _Compare> 241 _GLIBCXX14_CONSTEXPR 242 inline const _Tp& 243 min(const _Tp& __a, const _Tp& __b, _Compare __comp) 244 { 245 //return __comp(__b, __a) ? __b : __a; 246 if (__comp(__b, __a)) 247 return __b; 248 return __a; 249 } 250 251 /** 252 * @brief This does what you think it does. 253 * @ingroup sorting_algorithms 254 * @param __a A thing of arbitrary type. 255 * @param __b Another thing of arbitrary type. 256 * @param __comp A @link comparison_functors comparison functor@endlink. 257 * @return The greater of the parameters. 258 * 259 * This will work on temporary expressions, since they are only evaluated 260 * once, unlike a preprocessor macro. 261 */ 262 template<typename _Tp, typename _Compare> 263 _GLIBCXX14_CONSTEXPR 264 inline const _Tp& 265 max(const _Tp& __a, const _Tp& __b, _Compare __comp) 266 { 267 //return __comp(__a, __b) ? __b : __a; 268 if (__comp(__a, __b)) 269 return __b; 270 return __a; 271 } 272 273 // If _Iterator is a __normal_iterator return its base (a plain pointer, 274 // normally) otherwise return it untouched. See copy, fill, ... 275 template<typename _Iterator> 276 struct _Niter_base 277 : _Iter_base<_Iterator, __is_normal_iterator<_Iterator>::__value> 278 { }; 279 280 template<typename _Iterator> 281 inline typename _Niter_base<_Iterator>::iterator_type 282 __niter_base(_Iterator __it) 283 { return std::_Niter_base<_Iterator>::_S_base(__it); } 284 285 // Likewise, for move_iterator. 286 template<typename _Iterator> 287 struct _Miter_base 288 : _Iter_base<_Iterator, __is_move_iterator<_Iterator>::__value> 289 { }; 290 291 template<typename _Iterator> 292 inline typename _Miter_base<_Iterator>::iterator_type 293 __miter_base(_Iterator __it) 294 { return std::_Miter_base<_Iterator>::_S_base(__it); } 295 296 // All of these auxiliary structs serve two purposes. (1) Replace 297 // calls to copy with memmove whenever possible. (Memmove, not memcpy, 298 // because the input and output ranges are permitted to overlap.) 299 // (2) If we're using random access iterators, then write the loop as 300 // a for loop with an explicit count. 301 302 template<bool, bool, typename> 303 struct __copy_move 304 { 305 template<typename _II, typename _OI> 306 static _OI 307 __copy_m(_II __first, _II __last, _OI __result) 308 { 309 for (; __first != __last; ++__result, ++__first) 310 *__result = *__first; 311 return __result; 312 } 313 }; 314 315 #if __cplusplus >= 201103L 316 template<typename _Category> 317 struct __copy_move<true, false, _Category> 318 { 319 template<typename _II, typename _OI> 320 static _OI 321 __copy_m(_II __first, _II __last, _OI __result) 322 { 323 for (; __first != __last; ++__result, ++__first) 324 *__result = std::move(*__first); 325 return __result; 326 } 327 }; 328 #endif 329 330 template<> 331 struct __copy_move<false, false, random_access_iterator_tag> 332 { 333 template<typename _II, typename _OI> 334 static _OI 335 __copy_m(_II __first, _II __last, _OI __result) 336 { 337 typedef typename iterator_traits<_II>::difference_type _Distance; 338 for(_Distance __n = __last - __first; __n > 0; --__n) 339 { 340 *__result = *__first; 341 ++__first; 342 ++__result; 343 } 344 return __result; 345 } 346 }; 347 348 #if __cplusplus >= 201103L 349 template<> 350 struct __copy_move<true, false, random_access_iterator_tag> 351 { 352 template<typename _II, typename _OI> 353 static _OI 354 __copy_m(_II __first, _II __last, _OI __result) 355 { 356 typedef typename iterator_traits<_II>::difference_type _Distance; 357 for(_Distance __n = __last - __first; __n > 0; --__n) 358 { 359 *__result = std::move(*__first); 360 ++__first; 361 ++__result; 362 } 363 return __result; 364 } 365 }; 366 #endif 367 368 template<bool _IsMove> 369 struct __copy_move<_IsMove, true, random_access_iterator_tag> 370 { 371 template<typename _Tp> 372 static _Tp* 373 __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result) 374 { 375 #if __cplusplus >= 201103L 376 using __assignable = conditional<_IsMove, 377 is_move_assignable<_Tp>, 378 is_copy_assignable<_Tp>>; 379 // trivial types can have deleted assignment 380 static_assert( __assignable::type::value, "type is not assignable" ); 381 #endif 382 const ptrdiff_t _Num = __last - __first; 383 if (_Num) 384 __builtin_memmove(__result, __first, sizeof(_Tp) * _Num); 385 return __result + _Num; 386 } 387 }; 388 389 template<bool _IsMove, typename _II, typename _OI> 390 inline _OI 391 __copy_move_a(_II __first, _II __last, _OI __result) 392 { 393 typedef typename iterator_traits<_II>::value_type _ValueTypeI; 394 typedef typename iterator_traits<_OI>::value_type _ValueTypeO; 395 typedef typename iterator_traits<_II>::iterator_category _Category; 396 const bool __simple = (__is_trivial(_ValueTypeI) 397 && __is_pointer<_II>::__value 398 && __is_pointer<_OI>::__value 399 && __are_same<_ValueTypeI, _ValueTypeO>::__value); 400 401 return std::__copy_move<_IsMove, __simple, 402 _Category>::__copy_m(__first, __last, __result); 403 } 404 405 // Helpers for streambuf iterators (either istream or ostream). 406 // NB: avoid including <iosfwd>, relatively large. 407 template<typename _CharT> 408 struct char_traits; 409 410 template<typename _CharT, typename _Traits> 411 class istreambuf_iterator; 412 413 template<typename _CharT, typename _Traits> 414 class ostreambuf_iterator; 415 416 template<bool _IsMove, typename _CharT> 417 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 418 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 419 __copy_move_a2(_CharT*, _CharT*, 420 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 421 422 template<bool _IsMove, typename _CharT> 423 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 424 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type 425 __copy_move_a2(const _CharT*, const _CharT*, 426 ostreambuf_iterator<_CharT, char_traits<_CharT> >); 427 428 template<bool _IsMove, typename _CharT> 429 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, 430 _CharT*>::__type 431 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, 432 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); 433 434 template<bool _IsMove, typename _II, typename _OI> 435 inline _OI 436 __copy_move_a2(_II __first, _II __last, _OI __result) 437 { 438 return _OI(std::__copy_move_a<_IsMove>(std::__niter_base(__first), 439 std::__niter_base(__last), 440 std::__niter_base(__result))); 441 } 442 443 /** 444 * @brief Copies the range [first,last) into result. 445 * @ingroup mutating_algorithms 446 * @param __first An input iterator. 447 * @param __last An input iterator. 448 * @param __result An output iterator. 449 * @return result + (first - last) 450 * 451 * This inline function will boil down to a call to @c memmove whenever 452 * possible. Failing that, if random access iterators are passed, then the 453 * loop count will be known (and therefore a candidate for compiler 454 * optimizations such as unrolling). Result may not be contained within 455 * [first,last); the copy_backward function should be used instead. 456 * 457 * Note that the end of the output range is permitted to be contained 458 * within [first,last). 459 */ 460 template<typename _II, typename _OI> 461 inline _OI 462 copy(_II __first, _II __last, _OI __result) 463 { 464 // concept requirements 465 __glibcxx_function_requires(_InputIteratorConcept<_II>) 466 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 467 typename iterator_traits<_II>::value_type>) 468 __glibcxx_requires_valid_range(__first, __last); 469 470 return (std::__copy_move_a2<__is_move_iterator<_II>::__value> 471 (std::__miter_base(__first), std::__miter_base(__last), 472 __result)); 473 } 474 475 #if __cplusplus >= 201103L 476 /** 477 * @brief Moves the range [first,last) into result. 478 * @ingroup mutating_algorithms 479 * @param __first An input iterator. 480 * @param __last An input iterator. 481 * @param __result An output iterator. 482 * @return result + (first - last) 483 * 484 * This inline function will boil down to a call to @c memmove whenever 485 * possible. Failing that, if random access iterators are passed, then the 486 * loop count will be known (and therefore a candidate for compiler 487 * optimizations such as unrolling). Result may not be contained within 488 * [first,last); the move_backward function should be used instead. 489 * 490 * Note that the end of the output range is permitted to be contained 491 * within [first,last). 492 */ 493 template<typename _II, typename _OI> 494 inline _OI 495 move(_II __first, _II __last, _OI __result) 496 { 497 // concept requirements 498 __glibcxx_function_requires(_InputIteratorConcept<_II>) 499 __glibcxx_function_requires(_OutputIteratorConcept<_OI, 500 typename iterator_traits<_II>::value_type>) 501 __glibcxx_requires_valid_range(__first, __last); 502 503 return std::__copy_move_a2<true>(std::__miter_base(__first), 504 std::__miter_base(__last), __result); 505 } 506 507 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) 508 #else 509 #define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) 510 #endif 511 512 template<bool, bool, typename> 513 struct __copy_move_backward 514 { 515 template<typename _BI1, typename _BI2> 516 static _BI2 517 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 518 { 519 while (__first != __last) 520 *--__result = *--__last; 521 return __result; 522 } 523 }; 524 525 #if __cplusplus >= 201103L 526 template<typename _Category> 527 struct __copy_move_backward<true, false, _Category> 528 { 529 template<typename _BI1, typename _BI2> 530 static _BI2 531 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 532 { 533 while (__first != __last) 534 *--__result = std::move(*--__last); 535 return __result; 536 } 537 }; 538 #endif 539 540 template<> 541 struct __copy_move_backward<false, false, random_access_iterator_tag> 542 { 543 template<typename _BI1, typename _BI2> 544 static _BI2 545 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 546 { 547 typename iterator_traits<_BI1>::difference_type __n; 548 for (__n = __last - __first; __n > 0; --__n) 549 *--__result = *--__last; 550 return __result; 551 } 552 }; 553 554 #if __cplusplus >= 201103L 555 template<> 556 struct __copy_move_backward<true, false, random_access_iterator_tag> 557 { 558 template<typename _BI1, typename _BI2> 559 static _BI2 560 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) 561 { 562 typename iterator_traits<_BI1>::difference_type __n; 563 for (__n = __last - __first; __n > 0; --__n) 564 *--__result = std::move(*--__last); 565 return __result; 566 } 567 }; 568 #endif 569 570 template<bool _IsMove> 571 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> 572 { 573 template<typename _Tp> 574 static _Tp* 575 __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result) 576 { 577 #if __cplusplus >= 201103L 578 using __assignable = conditional<_IsMove, 579 is_move_assignable<_Tp>, 580 is_copy_assignable<_Tp>>; 581 // trivial types can have deleted assignment 582 static_assert( __assignable::type::value, "type is not assignable" ); 583 #endif 584 const ptrdiff_t _Num = __last - __first; 585 if (_Num) 586 __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); 587 return __result - _Num; 588 } 589 }; 590 591 template<bool _IsMove, typename _BI1, typename _BI2> 592 inline _BI2 593 __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) 594 { 595 typedef typename iterator_traits<_BI1>::value_type _ValueType1; 596 typedef typename iterator_traits<_BI2>::value_type _ValueType2; 597 typedef typename iterator_traits<_BI1>::iterator_category _Category; 598 const bool __simple = (__is_trivial(_ValueType1) 599 && __is_pointer<_BI1>::__value 600 && __is_pointer<_BI2>::__value 601 && __are_same<_ValueType1, _ValueType2>::__value); 602 603 return std::__copy_move_backward<_IsMove, __simple, 604 _Category>::__copy_move_b(__first, 605 __last, 606 __result); 607 } 608 609 template<bool _IsMove, typename _BI1, typename _BI2> 610 inline _BI2 611 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) 612 { 613 return _BI2(std::__copy_move_backward_a<_IsMove> 614 (std::__niter_base(__first), std::__niter_base(__last), 615 std::__niter_base(__result))); 616 } 617 618 /** 619 * @brief Copies the range [first,last) into result. 620 * @ingroup mutating_algorithms 621 * @param __first A bidirectional iterator. 622 * @param __last A bidirectional iterator. 623 * @param __result A bidirectional iterator. 624 * @return result - (first - last) 625 * 626 * The function has the same effect as copy, but starts at the end of the 627 * range and works its way to the start, returning the start of the result. 628 * This inline function will boil down to a call to @c memmove whenever 629 * possible. Failing that, if random access iterators are passed, then the 630 * loop count will be known (and therefore a candidate for compiler 631 * optimizations such as unrolling). 632 * 633 * Result may not be in the range (first,last]. Use copy instead. Note 634 * that the start of the output range may overlap [first,last). 635 */ 636 template<typename _BI1, typename _BI2> 637 inline _BI2 638 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) 639 { 640 // concept requirements 641 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 642 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 643 __glibcxx_function_requires(_ConvertibleConcept< 644 typename iterator_traits<_BI1>::value_type, 645 typename iterator_traits<_BI2>::value_type>) 646 __glibcxx_requires_valid_range(__first, __last); 647 648 return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> 649 (std::__miter_base(__first), std::__miter_base(__last), 650 __result)); 651 } 652 653 #if __cplusplus >= 201103L 654 /** 655 * @brief Moves the range [first,last) into result. 656 * @ingroup mutating_algorithms 657 * @param __first A bidirectional iterator. 658 * @param __last A bidirectional iterator. 659 * @param __result A bidirectional iterator. 660 * @return result - (first - last) 661 * 662 * The function has the same effect as move, but starts at the end of the 663 * range and works its way to the start, returning the start of the result. 664 * This inline function will boil down to a call to @c memmove whenever 665 * possible. Failing that, if random access iterators are passed, then the 666 * loop count will be known (and therefore a candidate for compiler 667 * optimizations such as unrolling). 668 * 669 * Result may not be in the range (first,last]. Use move instead. Note 670 * that the start of the output range may overlap [first,last). 671 */ 672 template<typename _BI1, typename _BI2> 673 inline _BI2 674 move_backward(_BI1 __first, _BI1 __last, _BI2 __result) 675 { 676 // concept requirements 677 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) 678 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) 679 __glibcxx_function_requires(_ConvertibleConcept< 680 typename iterator_traits<_BI1>::value_type, 681 typename iterator_traits<_BI2>::value_type>) 682 __glibcxx_requires_valid_range(__first, __last); 683 684 return std::__copy_move_backward_a2<true>(std::__miter_base(__first), 685 std::__miter_base(__last), 686 __result); 687 } 688 689 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) 690 #else 691 #define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) 692 #endif 693 694 template<typename _ForwardIterator, typename _Tp> 695 inline typename 696 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type 697 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 698 const _Tp& __value) 699 { 700 for (; __first != __last; ++__first) 701 *__first = __value; 702 } 703 704 template<typename _ForwardIterator, typename _Tp> 705 inline typename 706 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type 707 __fill_a(_ForwardIterator __first, _ForwardIterator __last, 708 const _Tp& __value) 709 { 710 const _Tp __tmp = __value; 711 for (; __first != __last; ++__first) 712 *__first = __tmp; 713 } 714 715 // Specialization: for char types we can use memset. 716 template<typename _Tp> 717 inline typename 718 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type 719 __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c) 720 { 721 const _Tp __tmp = __c; 722 if (const size_t __len = __last - __first) 723 __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len); 724 } 725 726 /** 727 * @brief Fills the range [first,last) with copies of value. 728 * @ingroup mutating_algorithms 729 * @param __first A forward iterator. 730 * @param __last A forward iterator. 731 * @param __value A reference-to-const of arbitrary type. 732 * @return Nothing. 733 * 734 * This function fills a range with copies of the same value. For char 735 * types filling contiguous areas of memory, this becomes an inline call 736 * to @c memset or @c wmemset. 737 */ 738 template<typename _ForwardIterator, typename _Tp> 739 inline void 740 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) 741 { 742 // concept requirements 743 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 744 _ForwardIterator>) 745 __glibcxx_requires_valid_range(__first, __last); 746 747 std::__fill_a(std::__niter_base(__first), std::__niter_base(__last), 748 __value); 749 } 750 751 template<typename _OutputIterator, typename _Size, typename _Tp> 752 inline typename 753 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type 754 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 755 { 756 for (__decltype(__n + 0) __niter = __n; 757 __niter > 0; --__niter, ++__first) 758 *__first = __value; 759 return __first; 760 } 761 762 template<typename _OutputIterator, typename _Size, typename _Tp> 763 inline typename 764 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type 765 __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) 766 { 767 const _Tp __tmp = __value; 768 for (__decltype(__n + 0) __niter = __n; 769 __niter > 0; --__niter, ++__first) 770 *__first = __tmp; 771 return __first; 772 } 773 774 template<typename _Size, typename _Tp> 775 inline typename 776 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type 777 __fill_n_a(_Tp* __first, _Size __n, const _Tp& __c) 778 { 779 std::__fill_a(__first, __first + __n, __c); 780 return __first + __n; 781 } 782 783 /** 784 * @brief Fills the range [first,first+n) with copies of value. 785 * @ingroup mutating_algorithms 786 * @param __first An output iterator. 787 * @param __n The count of copies to perform. 788 * @param __value A reference-to-const of arbitrary type. 789 * @return The iterator at first+n. 790 * 791 * This function fills a range with copies of the same value. For char 792 * types filling contiguous areas of memory, this becomes an inline call 793 * to @c memset or @ wmemset. 794 * 795 * _GLIBCXX_RESOLVE_LIB_DEFECTS 796 * DR 865. More algorithms that throw away information 797 */ 798 template<typename _OI, typename _Size, typename _Tp> 799 inline _OI 800 fill_n(_OI __first, _Size __n, const _Tp& __value) 801 { 802 // concept requirements 803 __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) 804 805 return _OI(std::__fill_n_a(std::__niter_base(__first), __n, __value)); 806 } 807 808 template<bool _BoolType> 809 struct __equal 810 { 811 template<typename _II1, typename _II2> 812 static bool 813 equal(_II1 __first1, _II1 __last1, _II2 __first2) 814 { 815 for (; __first1 != __last1; ++__first1, ++__first2) 816 if (!(*__first1 == *__first2)) 817 return false; 818 return true; 819 } 820 }; 821 822 template<> 823 struct __equal<true> 824 { 825 template<typename _Tp> 826 static bool 827 equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2) 828 { 829 if (const size_t __len = (__last1 - __first1)) 830 return !__builtin_memcmp(__first1, __first2, sizeof(_Tp) * __len); 831 return true; 832 } 833 }; 834 835 template<typename _II1, typename _II2> 836 inline bool 837 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2) 838 { 839 typedef typename iterator_traits<_II1>::value_type _ValueType1; 840 typedef typename iterator_traits<_II2>::value_type _ValueType2; 841 const bool __simple = ((__is_integer<_ValueType1>::__value 842 || __is_pointer<_ValueType1>::__value) 843 && __is_pointer<_II1>::__value 844 && __is_pointer<_II2>::__value 845 && __are_same<_ValueType1, _ValueType2>::__value); 846 847 return std::__equal<__simple>::equal(__first1, __last1, __first2); 848 } 849 850 template<typename, typename> 851 struct __lc_rai 852 { 853 template<typename _II1, typename _II2> 854 static _II1 855 __newlast1(_II1, _II1 __last1, _II2, _II2) 856 { return __last1; } 857 858 template<typename _II> 859 static bool 860 __cnd2(_II __first, _II __last) 861 { return __first != __last; } 862 }; 863 864 template<> 865 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> 866 { 867 template<typename _RAI1, typename _RAI2> 868 static _RAI1 869 __newlast1(_RAI1 __first1, _RAI1 __last1, 870 _RAI2 __first2, _RAI2 __last2) 871 { 872 const typename iterator_traits<_RAI1>::difference_type 873 __diff1 = __last1 - __first1; 874 const typename iterator_traits<_RAI2>::difference_type 875 __diff2 = __last2 - __first2; 876 return __diff2 < __diff1 ? __first1 + __diff2 : __last1; 877 } 878 879 template<typename _RAI> 880 static bool 881 __cnd2(_RAI, _RAI) 882 { return true; } 883 }; 884 885 template<typename _II1, typename _II2, typename _Compare> 886 bool 887 __lexicographical_compare_impl(_II1 __first1, _II1 __last1, 888 _II2 __first2, _II2 __last2, 889 _Compare __comp) 890 { 891 typedef typename iterator_traits<_II1>::iterator_category _Category1; 892 typedef typename iterator_traits<_II2>::iterator_category _Category2; 893 typedef std::__lc_rai<_Category1, _Category2> __rai_type; 894 895 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); 896 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); 897 ++__first1, ++__first2) 898 { 899 if (__comp(__first1, __first2)) 900 return true; 901 if (__comp(__first2, __first1)) 902 return false; 903 } 904 return __first1 == __last1 && __first2 != __last2; 905 } 906 907 template<bool _BoolType> 908 struct __lexicographical_compare 909 { 910 template<typename _II1, typename _II2> 911 static bool __lc(_II1, _II1, _II2, _II2); 912 }; 913 914 template<bool _BoolType> 915 template<typename _II1, typename _II2> 916 bool 917 __lexicographical_compare<_BoolType>:: 918 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 919 { 920 return std::__lexicographical_compare_impl(__first1, __last1, 921 __first2, __last2, 922 __gnu_cxx::__ops::__iter_less_iter()); 923 } 924 925 template<> 926 struct __lexicographical_compare<true> 927 { 928 template<typename _Tp, typename _Up> 929 static bool 930 __lc(const _Tp* __first1, const _Tp* __last1, 931 const _Up* __first2, const _Up* __last2) 932 { 933 const size_t __len1 = __last1 - __first1; 934 const size_t __len2 = __last2 - __first2; 935 if (const size_t __len = std::min(__len1, __len2)) 936 if (int __result = __builtin_memcmp(__first1, __first2, __len)) 937 return __result < 0; 938 return __len1 < __len2; 939 } 940 }; 941 942 template<typename _II1, typename _II2> 943 inline bool 944 __lexicographical_compare_aux(_II1 __first1, _II1 __last1, 945 _II2 __first2, _II2 __last2) 946 { 947 typedef typename iterator_traits<_II1>::value_type _ValueType1; 948 typedef typename iterator_traits<_II2>::value_type _ValueType2; 949 const bool __simple = 950 (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value 951 && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed_val 952 && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed_val 953 && __is_pointer<_II1>::__value 954 && __is_pointer<_II2>::__value); 955 956 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, 957 __first2, __last2); 958 } 959 960 template<typename _ForwardIterator, typename _Tp, typename _Compare> 961 _ForwardIterator 962 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, 963 const _Tp& __val, _Compare __comp) 964 { 965 typedef typename iterator_traits<_ForwardIterator>::difference_type 966 _DistanceType; 967 968 _DistanceType __len = std::distance(__first, __last); 969 970 while (__len > 0) 971 { 972 _DistanceType __half = __len >> 1; 973 _ForwardIterator __middle = __first; 974 std::advance(__middle, __half); 975 if (__comp(__middle, __val)) 976 { 977 __first = __middle; 978 ++__first; 979 __len = __len - __half - 1; 980 } 981 else 982 __len = __half; 983 } 984 return __first; 985 } 986 987 /** 988 * @brief Finds the first position in which @a val could be inserted 989 * without changing the ordering. 990 * @param __first An iterator. 991 * @param __last Another iterator. 992 * @param __val The search term. 993 * @return An iterator pointing to the first element <em>not less 994 * than</em> @a val, or end() if every element is less than 995 * @a val. 996 * @ingroup binary_search_algorithms 997 */ 998 template<typename _ForwardIterator, typename _Tp> 999 inline _ForwardIterator 1000 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 1001 const _Tp& __val) 1002 { 1003 // concept requirements 1004 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1005 __glibcxx_function_requires(_LessThanOpConcept< 1006 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 1007 __glibcxx_requires_partitioned_lower(__first, __last, __val); 1008 1009 return std::__lower_bound(__first, __last, __val, 1010 __gnu_cxx::__ops::__iter_less_val()); 1011 } 1012 1013 /// This is a helper function for the sort routines and for random.tcc. 1014 // Precondition: __n > 0. 1015 inline _GLIBCXX_CONSTEXPR int 1016 __lg(int __n) 1017 { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } 1018 1019 inline _GLIBCXX_CONSTEXPR unsigned 1020 __lg(unsigned __n) 1021 { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } 1022 1023 inline _GLIBCXX_CONSTEXPR long 1024 __lg(long __n) 1025 { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } 1026 1027 inline _GLIBCXX_CONSTEXPR unsigned long 1028 __lg(unsigned long __n) 1029 { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } 1030 1031 inline _GLIBCXX_CONSTEXPR long long 1032 __lg(long long __n) 1033 { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } 1034 1035 inline _GLIBCXX_CONSTEXPR unsigned long long 1036 __lg(unsigned long long __n) 1037 { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } 1038 1039 _GLIBCXX_END_NAMESPACE_VERSION 1040 1041 _GLIBCXX_BEGIN_NAMESPACE_ALGO 1042 1043 /** 1044 * @brief Tests a range for element-wise equality. 1045 * @ingroup non_mutating_algorithms 1046 * @param __first1 An input iterator. 1047 * @param __last1 An input iterator. 1048 * @param __first2 An input iterator. 1049 * @return A boolean true or false. 1050 * 1051 * This compares the elements of two ranges using @c == and returns true or 1052 * false depending on whether all of the corresponding elements of the 1053 * ranges are equal. 1054 */ 1055 template<typename _II1, typename _II2> 1056 inline bool 1057 equal(_II1 __first1, _II1 __last1, _II2 __first2) 1058 { 1059 // concept requirements 1060 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1061 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1062 __glibcxx_function_requires(_EqualOpConcept< 1063 typename iterator_traits<_II1>::value_type, 1064 typename iterator_traits<_II2>::value_type>) 1065 __glibcxx_requires_valid_range(__first1, __last1); 1066 1067 return std::__equal_aux(std::__niter_base(__first1), 1068 std::__niter_base(__last1), 1069 std::__niter_base(__first2)); 1070 } 1071 1072 /** 1073 * @brief Tests a range for element-wise equality. 1074 * @ingroup non_mutating_algorithms 1075 * @param __first1 An input iterator. 1076 * @param __last1 An input iterator. 1077 * @param __first2 An input iterator. 1078 * @param __binary_pred A binary predicate @link functors 1079 * functor@endlink. 1080 * @return A boolean true or false. 1081 * 1082 * This compares the elements of two ranges using the binary_pred 1083 * parameter, and returns true or 1084 * false depending on whether all of the corresponding elements of the 1085 * ranges are equal. 1086 */ 1087 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 1088 inline bool 1089 equal(_IIter1 __first1, _IIter1 __last1, 1090 _IIter2 __first2, _BinaryPredicate __binary_pred) 1091 { 1092 // concept requirements 1093 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 1094 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 1095 __glibcxx_requires_valid_range(__first1, __last1); 1096 1097 for (; __first1 != __last1; ++__first1, ++__first2) 1098 if (!bool(__binary_pred(*__first1, *__first2))) 1099 return false; 1100 return true; 1101 } 1102 1103 #if __cplusplus > 201103L 1104 1105 #define __cpp_lib_robust_nonmodifying_seq_ops 201304 1106 1107 /** 1108 * @brief Tests a range for element-wise equality. 1109 * @ingroup non_mutating_algorithms 1110 * @param __first1 An input iterator. 1111 * @param __last1 An input iterator. 1112 * @param __first2 An input iterator. 1113 * @param __last2 An input iterator. 1114 * @return A boolean true or false. 1115 * 1116 * This compares the elements of two ranges using @c == and returns true or 1117 * false depending on whether all of the corresponding elements of the 1118 * ranges are equal. 1119 */ 1120 template<typename _II1, typename _II2> 1121 inline bool 1122 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) 1123 { 1124 // concept requirements 1125 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1126 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1127 __glibcxx_function_requires(_EqualOpConcept< 1128 typename iterator_traits<_II1>::value_type, 1129 typename iterator_traits<_II2>::value_type>) 1130 __glibcxx_requires_valid_range(__first1, __last1); 1131 __glibcxx_requires_valid_range(__first2, __last2); 1132 1133 using _RATag = random_access_iterator_tag; 1134 using _Cat1 = typename iterator_traits<_II1>::iterator_category; 1135 using _Cat2 = typename iterator_traits<_II2>::iterator_category; 1136 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 1137 if (_RAIters()) 1138 { 1139 auto __d1 = std::distance(__first1, __last1); 1140 auto __d2 = std::distance(__first2, __last2); 1141 if (__d1 != __d2) 1142 return false; 1143 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2); 1144 } 1145 1146 for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) 1147 if (!(*__first1 == *__first2)) 1148 return false; 1149 return __first1 == __last1 && __first2 == __last2; 1150 } 1151 1152 /** 1153 * @brief Tests a range for element-wise equality. 1154 * @ingroup non_mutating_algorithms 1155 * @param __first1 An input iterator. 1156 * @param __last1 An input iterator. 1157 * @param __first2 An input iterator. 1158 * @param __last2 An input iterator. 1159 * @param __binary_pred A binary predicate @link functors 1160 * functor@endlink. 1161 * @return A boolean true or false. 1162 * 1163 * This compares the elements of two ranges using the binary_pred 1164 * parameter, and returns true or 1165 * false depending on whether all of the corresponding elements of the 1166 * ranges are equal. 1167 */ 1168 template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> 1169 inline bool 1170 equal(_IIter1 __first1, _IIter1 __last1, 1171 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred) 1172 { 1173 // concept requirements 1174 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) 1175 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) 1176 __glibcxx_requires_valid_range(__first1, __last1); 1177 __glibcxx_requires_valid_range(__first2, __last2); 1178 1179 using _RATag = random_access_iterator_tag; 1180 using _Cat1 = typename iterator_traits<_IIter1>::iterator_category; 1181 using _Cat2 = typename iterator_traits<_IIter2>::iterator_category; 1182 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>; 1183 if (_RAIters()) 1184 { 1185 auto __d1 = std::distance(__first1, __last1); 1186 auto __d2 = std::distance(__first2, __last2); 1187 if (__d1 != __d2) 1188 return false; 1189 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2, 1190 __binary_pred); 1191 } 1192 1193 for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) 1194 if (!bool(__binary_pred(*__first1, *__first2))) 1195 return false; 1196 return __first1 == __last1 && __first2 == __last2; 1197 } 1198 #endif 1199 1200 /** 1201 * @brief Performs @b dictionary comparison on ranges. 1202 * @ingroup sorting_algorithms 1203 * @param __first1 An input iterator. 1204 * @param __last1 An input iterator. 1205 * @param __first2 An input iterator. 1206 * @param __last2 An input iterator. 1207 * @return A boolean true or false. 1208 * 1209 * <em>Returns true if the sequence of elements defined by the range 1210 * [first1,last1) is lexicographically less than the sequence of elements 1211 * defined by the range [first2,last2). Returns false otherwise.</em> 1212 * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, 1213 * then this is an inline call to @c memcmp. 1214 */ 1215 template<typename _II1, typename _II2> 1216 inline bool 1217 lexicographical_compare(_II1 __first1, _II1 __last1, 1218 _II2 __first2, _II2 __last2) 1219 { 1220 #ifdef _GLIBCXX_CONCEPT_CHECKS 1221 // concept requirements 1222 typedef typename iterator_traits<_II1>::value_type _ValueType1; 1223 typedef typename iterator_traits<_II2>::value_type _ValueType2; 1224 #endif 1225 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1226 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1227 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) 1228 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) 1229 __glibcxx_requires_valid_range(__first1, __last1); 1230 __glibcxx_requires_valid_range(__first2, __last2); 1231 1232 return std::__lexicographical_compare_aux(std::__niter_base(__first1), 1233 std::__niter_base(__last1), 1234 std::__niter_base(__first2), 1235 std::__niter_base(__last2)); 1236 } 1237 1238 /** 1239 * @brief Performs @b dictionary comparison on ranges. 1240 * @ingroup sorting_algorithms 1241 * @param __first1 An input iterator. 1242 * @param __last1 An input iterator. 1243 * @param __first2 An input iterator. 1244 * @param __last2 An input iterator. 1245 * @param __comp A @link comparison_functors comparison functor@endlink. 1246 * @return A boolean true or false. 1247 * 1248 * The same as the four-parameter @c lexicographical_compare, but uses the 1249 * comp parameter instead of @c <. 1250 */ 1251 template<typename _II1, typename _II2, typename _Compare> 1252 inline bool 1253 lexicographical_compare(_II1 __first1, _II1 __last1, 1254 _II2 __first2, _II2 __last2, _Compare __comp) 1255 { 1256 // concept requirements 1257 __glibcxx_function_requires(_InputIteratorConcept<_II1>) 1258 __glibcxx_function_requires(_InputIteratorConcept<_II2>) 1259 __glibcxx_requires_valid_range(__first1, __last1); 1260 __glibcxx_requires_valid_range(__first2, __last2); 1261 1262 return std::__lexicographical_compare_impl 1263 (__first1, __last1, __first2, __last2, 1264 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 1265 } 1266 1267 template<typename _InputIterator1, typename _InputIterator2, 1268 typename _BinaryPredicate> 1269 pair<_InputIterator1, _InputIterator2> 1270 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1271 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 1272 { 1273 while (__first1 != __last1 && __binary_pred(__first1, __first2)) 1274 { 1275 ++__first1; 1276 ++__first2; 1277 } 1278 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 1279 } 1280 1281 /** 1282 * @brief Finds the places in ranges which don't match. 1283 * @ingroup non_mutating_algorithms 1284 * @param __first1 An input iterator. 1285 * @param __last1 An input iterator. 1286 * @param __first2 An input iterator. 1287 * @return A pair of iterators pointing to the first mismatch. 1288 * 1289 * This compares the elements of two ranges using @c == and returns a pair 1290 * of iterators. The first iterator points into the first range, the 1291 * second iterator points into the second range, and the elements pointed 1292 * to by the iterators are not equal. 1293 */ 1294 template<typename _InputIterator1, typename _InputIterator2> 1295 inline pair<_InputIterator1, _InputIterator2> 1296 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1297 _InputIterator2 __first2) 1298 { 1299 // concept requirements 1300 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 1301 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 1302 __glibcxx_function_requires(_EqualOpConcept< 1303 typename iterator_traits<_InputIterator1>::value_type, 1304 typename iterator_traits<_InputIterator2>::value_type>) 1305 __glibcxx_requires_valid_range(__first1, __last1); 1306 1307 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 1308 __gnu_cxx::__ops::__iter_equal_to_iter()); 1309 } 1310 1311 /** 1312 * @brief Finds the places in ranges which don't match. 1313 * @ingroup non_mutating_algorithms 1314 * @param __first1 An input iterator. 1315 * @param __last1 An input iterator. 1316 * @param __first2 An input iterator. 1317 * @param __binary_pred A binary predicate @link functors 1318 * functor@endlink. 1319 * @return A pair of iterators pointing to the first mismatch. 1320 * 1321 * This compares the elements of two ranges using the binary_pred 1322 * parameter, and returns a pair 1323 * of iterators. The first iterator points into the first range, the 1324 * second iterator points into the second range, and the elements pointed 1325 * to by the iterators are not equal. 1326 */ 1327 template<typename _InputIterator1, typename _InputIterator2, 1328 typename _BinaryPredicate> 1329 inline pair<_InputIterator1, _InputIterator2> 1330 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1331 _InputIterator2 __first2, _BinaryPredicate __binary_pred) 1332 { 1333 // concept requirements 1334 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 1335 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 1336 __glibcxx_requires_valid_range(__first1, __last1); 1337 1338 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, 1339 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 1340 } 1341 1342 #if __cplusplus > 201103L 1343 1344 template<typename _InputIterator1, typename _InputIterator2, 1345 typename _BinaryPredicate> 1346 pair<_InputIterator1, _InputIterator2> 1347 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1348 _InputIterator2 __first2, _InputIterator2 __last2, 1349 _BinaryPredicate __binary_pred) 1350 { 1351 while (__first1 != __last1 && __first2 != __last2 1352 && __binary_pred(__first1, __first2)) 1353 { 1354 ++__first1; 1355 ++__first2; 1356 } 1357 return pair<_InputIterator1, _InputIterator2>(__first1, __first2); 1358 } 1359 1360 /** 1361 * @brief Finds the places in ranges which don't match. 1362 * @ingroup non_mutating_algorithms 1363 * @param __first1 An input iterator. 1364 * @param __last1 An input iterator. 1365 * @param __first2 An input iterator. 1366 * @param __last2 An input iterator. 1367 * @return A pair of iterators pointing to the first mismatch. 1368 * 1369 * This compares the elements of two ranges using @c == and returns a pair 1370 * of iterators. The first iterator points into the first range, the 1371 * second iterator points into the second range, and the elements pointed 1372 * to by the iterators are not equal. 1373 */ 1374 template<typename _InputIterator1, typename _InputIterator2> 1375 inline pair<_InputIterator1, _InputIterator2> 1376 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1377 _InputIterator2 __first2, _InputIterator2 __last2) 1378 { 1379 // concept requirements 1380 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 1381 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 1382 __glibcxx_function_requires(_EqualOpConcept< 1383 typename iterator_traits<_InputIterator1>::value_type, 1384 typename iterator_traits<_InputIterator2>::value_type>) 1385 __glibcxx_requires_valid_range(__first1, __last1); 1386 __glibcxx_requires_valid_range(__first2, __last2); 1387 1388 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 1389 __gnu_cxx::__ops::__iter_equal_to_iter()); 1390 } 1391 1392 /** 1393 * @brief Finds the places in ranges which don't match. 1394 * @ingroup non_mutating_algorithms 1395 * @param __first1 An input iterator. 1396 * @param __last1 An input iterator. 1397 * @param __first2 An input iterator. 1398 * @param __last2 An input iterator. 1399 * @param __binary_pred A binary predicate @link functors 1400 * functor@endlink. 1401 * @return A pair of iterators pointing to the first mismatch. 1402 * 1403 * This compares the elements of two ranges using the binary_pred 1404 * parameter, and returns a pair 1405 * of iterators. The first iterator points into the first range, the 1406 * second iterator points into the second range, and the elements pointed 1407 * to by the iterators are not equal. 1408 */ 1409 template<typename _InputIterator1, typename _InputIterator2, 1410 typename _BinaryPredicate> 1411 inline pair<_InputIterator1, _InputIterator2> 1412 mismatch(_InputIterator1 __first1, _InputIterator1 __last1, 1413 _InputIterator2 __first2, _InputIterator2 __last2, 1414 _BinaryPredicate __binary_pred) 1415 { 1416 // concept requirements 1417 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 1418 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 1419 __glibcxx_requires_valid_range(__first1, __last1); 1420 __glibcxx_requires_valid_range(__first2, __last2); 1421 1422 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2, 1423 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 1424 } 1425 #endif 1426 1427 _GLIBCXX_END_NAMESPACE_ALGO 1428 } // namespace std 1429 1430 // NB: This file is included within many other C++ includes, as a way 1431 // of getting the base algorithms. So, make sure that parallel bits 1432 // come in too if requested. 1433 #ifdef _GLIBCXX_PARALLEL 1434 # include <parallel/algobase.h> 1435 #endif 1436 1437 #endif 1438