The C and C++ Include Header Files

/usr/include/c++/11/bits/stl_algo.h

$ cat -n /usr/include/c++/11/bits/stl_algo.h 1 // Algorithm implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2021 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 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_algo.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_ALGO_H 57 #define _STL_ALGO_H 1 58 59 #include <cstdlib> // for rand 60 #include <bits/algorithmfwd.h> 61 #include <bits/stl_heap.h> 62 #include <bits/stl_tempbuf.h> // for _Temporary_buffer 63 #include <bits/predefined_ops.h> 64 65 #if __cplusplus >= 201103L 66 #include <bits/uniform_int_dist.h> 67 #endif 68 69 // See concept_check.h for the __glibcxx_*_requires macros. 70 71 namespace std _GLIBCXX_VISIBILITY(default) 72 { 73 _GLIBCXX_BEGIN_NAMESPACE_VERSION 74 75 /// Swaps the median value of *__a, *__b and *__c under __comp to *__result 76 template<typename _Iterator, typename _Compare> 77 _GLIBCXX20_CONSTEXPR 78 void 79 __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b, 80 _Iterator __c, _Compare __comp) 81 { 82 if (__comp(__a, __b)) 83 { 84 if (__comp(__b, __c)) 85 std::iter_swap(__result, __b); 86 else if (__comp(__a, __c)) 87 std::iter_swap(__result, __c); 88 else 89 std::iter_swap(__result, __a); 90 } 91 else if (__comp(__a, __c)) 92 std::iter_swap(__result, __a); 93 else if (__comp(__b, __c)) 94 std::iter_swap(__result, __c); 95 else 96 std::iter_swap(__result, __b); 97 } 98 99 /// Provided for stable_partition to use. 100 template<typename _InputIterator, typename _Predicate> 101 _GLIBCXX20_CONSTEXPR 102 inline _InputIterator 103 __find_if_not(_InputIterator __first, _InputIterator __last, 104 _Predicate __pred) 105 { 106 return std::__find_if(__first, __last, 107 __gnu_cxx::__ops::__negate(__pred), 108 std::__iterator_category(__first)); 109 } 110 111 /// Like find_if_not(), but uses and updates a count of the 112 /// remaining range length instead of comparing against an end 113 /// iterator. 114 template<typename _InputIterator, typename _Predicate, typename _Distance> 115 _GLIBCXX20_CONSTEXPR 116 _InputIterator 117 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred) 118 { 119 for (; __len; --__len, (void) ++__first) 120 if (!__pred(__first)) 121 break; 122 return __first; 123 } 124 125 // set_difference 126 // set_intersection 127 // set_symmetric_difference 128 // set_union 129 // for_each 130 // find 131 // find_if 132 // find_first_of 133 // adjacent_find 134 // count 135 // count_if 136 // search 137 138 template<typename _ForwardIterator1, typename _ForwardIterator2, 139 typename _BinaryPredicate> 140 _GLIBCXX20_CONSTEXPR 141 _ForwardIterator1 142 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 143 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 144 _BinaryPredicate __predicate) 145 { 146 // Test for empty ranges 147 if (__first1 == __last1 || __first2 == __last2) 148 return __first1; 149 150 // Test for a pattern of length 1. 151 _ForwardIterator2 __p1(__first2); 152 if (++__p1 == __last2) 153 return std::__find_if(__first1, __last1, 154 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); 155 156 // General case. 157 _ForwardIterator1 __current = __first1; 158 159 for (;;) 160 { 161 __first1 = 162 std::__find_if(__first1, __last1, 163 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); 164 165 if (__first1 == __last1) 166 return __last1; 167 168 _ForwardIterator2 __p = __p1; 169 __current = __first1; 170 if (++__current == __last1) 171 return __last1; 172 173 while (__predicate(__current, __p)) 174 { 175 if (++__p == __last2) 176 return __first1; 177 if (++__current == __last1) 178 return __last1; 179 } 180 ++__first1; 181 } 182 return __first1; 183 } 184 185 // search_n 186 187 /** 188 * This is an helper function for search_n overloaded for forward iterators. 189 */ 190 template<typename _ForwardIterator, typename _Integer, 191 typename _UnaryPredicate> 192 _GLIBCXX20_CONSTEXPR 193 _ForwardIterator 194 __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, 195 _Integer __count, _UnaryPredicate __unary_pred, 196 std::forward_iterator_tag) 197 { 198 __first = std::__find_if(__first, __last, __unary_pred); 199 while (__first != __last) 200 { 201 typename iterator_traits<_ForwardIterator>::difference_type 202 __n = __count; 203 _ForwardIterator __i = __first; 204 ++__i; 205 while (__i != __last && __n != 1 && __unary_pred(__i)) 206 { 207 ++__i; 208 --__n; 209 } 210 if (__n == 1) 211 return __first; 212 if (__i == __last) 213 return __last; 214 __first = std::__find_if(++__i, __last, __unary_pred); 215 } 216 return __last; 217 } 218 219 /** 220 * This is an helper function for search_n overloaded for random access 221 * iterators. 222 */ 223 template<typename _RandomAccessIter, typename _Integer, 224 typename _UnaryPredicate> 225 _GLIBCXX20_CONSTEXPR 226 _RandomAccessIter 227 __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last, 228 _Integer __count, _UnaryPredicate __unary_pred, 229 std::random_access_iterator_tag) 230 { 231 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type 232 _DistanceType; 233 234 _DistanceType __tailSize = __last - __first; 235 _DistanceType __remainder = __count; 236 237 while (__remainder <= __tailSize) // the main loop... 238 { 239 __first += __remainder; 240 __tailSize -= __remainder; 241 // __first here is always pointing to one past the last element of 242 // next possible match. 243 _RandomAccessIter __backTrack = __first; 244 while (__unary_pred(--__backTrack)) 245 { 246 if (--__remainder == 0) 247 return (__first - __count); // Success 248 } 249 __remainder = __count + 1 - (__first - __backTrack); 250 } 251 return __last; // Failure 252 } 253 254 template<typename _ForwardIterator, typename _Integer, 255 typename _UnaryPredicate> 256 _GLIBCXX20_CONSTEXPR 257 _ForwardIterator 258 __search_n(_ForwardIterator __first, _ForwardIterator __last, 259 _Integer __count, 260 _UnaryPredicate __unary_pred) 261 { 262 if (__count <= 0) 263 return __first; 264 265 if (__count == 1) 266 return std::__find_if(__first, __last, __unary_pred); 267 268 return std::__search_n_aux(__first, __last, __count, __unary_pred, 269 std::__iterator_category(__first)); 270 } 271 272 // find_end for forward iterators. 273 template<typename _ForwardIterator1, typename _ForwardIterator2, 274 typename _BinaryPredicate> 275 _GLIBCXX20_CONSTEXPR 276 _ForwardIterator1 277 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 278 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 279 forward_iterator_tag, forward_iterator_tag, 280 _BinaryPredicate __comp) 281 { 282 if (__first2 == __last2) 283 return __last1; 284 285 _ForwardIterator1 __result = __last1; 286 while (1) 287 { 288 _ForwardIterator1 __new_result 289 = std::__search(__first1, __last1, __first2, __last2, __comp); 290 if (__new_result == __last1) 291 return __result; 292 else 293 { 294 __result = __new_result; 295 __first1 = __new_result; 296 ++__first1; 297 } 298 } 299 } 300 301 // find_end for bidirectional iterators (much faster). 302 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 303 typename _BinaryPredicate> 304 _GLIBCXX20_CONSTEXPR 305 _BidirectionalIterator1 306 __find_end(_BidirectionalIterator1 __first1, 307 _BidirectionalIterator1 __last1, 308 _BidirectionalIterator2 __first2, 309 _BidirectionalIterator2 __last2, 310 bidirectional_iterator_tag, bidirectional_iterator_tag, 311 _BinaryPredicate __comp) 312 { 313 // concept requirements 314 __glibcxx_function_requires(_BidirectionalIteratorConcept< 315 _BidirectionalIterator1>) 316 __glibcxx_function_requires(_BidirectionalIteratorConcept< 317 _BidirectionalIterator2>) 318 319 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 320 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 321 322 _RevIterator1 __rlast1(__first1); 323 _RevIterator2 __rlast2(__first2); 324 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1, 325 _RevIterator2(__last2), __rlast2, 326 __comp); 327 328 if (__rresult == __rlast1) 329 return __last1; 330 else 331 { 332 _BidirectionalIterator1 __result = __rresult.base(); 333 std::advance(__result, -std::distance(__first2, __last2)); 334 return __result; 335 } 336 } 337 338 /** 339 * @brief Find last matching subsequence in a sequence. 340 * @ingroup non_mutating_algorithms 341 * @param __first1 Start of range to search. 342 * @param __last1 End of range to search. 343 * @param __first2 Start of sequence to match. 344 * @param __last2 End of sequence to match. 345 * @return The last iterator @c i in the range 346 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == 347 * @p *(__first2+N) for each @c N in the range @p 348 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 349 * 350 * Searches the range @p [__first1,__last1) for a sub-sequence that 351 * compares equal value-by-value with the sequence given by @p 352 * [__first2,__last2) and returns an iterator to the __first 353 * element of the sub-sequence, or @p __last1 if the sub-sequence 354 * is not found. The sub-sequence will be the last such 355 * subsequence contained in [__first1,__last1). 356 * 357 * Because the sub-sequence must lie completely within the range @p 358 * [__first1,__last1) it must start at a position less than @p 359 * __last1-(__last2-__first2) where @p __last2-__first2 is the 360 * length of the sub-sequence. This means that the returned 361 * iterator @c i will be in the range @p 362 * [__first1,__last1-(__last2-__first2)) 363 */ 364 template<typename _ForwardIterator1, typename _ForwardIterator2> 365 _GLIBCXX20_CONSTEXPR 366 inline _ForwardIterator1 367 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 368 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 369 { 370 // concept requirements 371 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 372 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 373 __glibcxx_function_requires(_EqualOpConcept< 374 typename iterator_traits<_ForwardIterator1>::value_type, 375 typename iterator_traits<_ForwardIterator2>::value_type>) 376 __glibcxx_requires_valid_range(__first1, __last1); 377 __glibcxx_requires_valid_range(__first2, __last2); 378 379 return std::__find_end(__first1, __last1, __first2, __last2, 380 std::__iterator_category(__first1), 381 std::__iterator_category(__first2), 382 __gnu_cxx::__ops::__iter_equal_to_iter()); 383 } 384 385 /** 386 * @brief Find last matching subsequence in a sequence using a predicate. 387 * @ingroup non_mutating_algorithms 388 * @param __first1 Start of range to search. 389 * @param __last1 End of range to search. 390 * @param __first2 Start of sequence to match. 391 * @param __last2 End of sequence to match. 392 * @param __comp The predicate to use. 393 * @return The last iterator @c i in the range @p 394 * [__first1,__last1-(__last2-__first2)) such that @c 395 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the 396 * range @p [0,__last2-__first2), or @p __last1 if no such iterator 397 * exists. 398 * 399 * Searches the range @p [__first1,__last1) for a sub-sequence that 400 * compares equal value-by-value with the sequence given by @p 401 * [__first2,__last2) using comp as a predicate and returns an 402 * iterator to the first element of the sub-sequence, or @p __last1 403 * if the sub-sequence is not found. The sub-sequence will be the 404 * last such subsequence contained in [__first,__last1). 405 * 406 * Because the sub-sequence must lie completely within the range @p 407 * [__first1,__last1) it must start at a position less than @p 408 * __last1-(__last2-__first2) where @p __last2-__first2 is the 409 * length of the sub-sequence. This means that the returned 410 * iterator @c i will be in the range @p 411 * [__first1,__last1-(__last2-__first2)) 412 */ 413 template<typename _ForwardIterator1, typename _ForwardIterator2, 414 typename _BinaryPredicate> 415 _GLIBCXX20_CONSTEXPR 416 inline _ForwardIterator1 417 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 418 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 419 _BinaryPredicate __comp) 420 { 421 // concept requirements 422 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 423 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 424 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 425 typename iterator_traits<_ForwardIterator1>::value_type, 426 typename iterator_traits<_ForwardIterator2>::value_type>) 427 __glibcxx_requires_valid_range(__first1, __last1); 428 __glibcxx_requires_valid_range(__first2, __last2); 429 430 return std::__find_end(__first1, __last1, __first2, __last2, 431 std::__iterator_category(__first1), 432 std::__iterator_category(__first2), 433 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 434 } 435 436 #if __cplusplus >= 201103L 437 /** 438 * @brief Checks that a predicate is true for all the elements 439 * of a sequence. 440 * @ingroup non_mutating_algorithms 441 * @param __first An input iterator. 442 * @param __last An input iterator. 443 * @param __pred A predicate. 444 * @return True if the check is true, false otherwise. 445 * 446 * Returns true if @p __pred is true for each element in the range 447 * @p [__first,__last), and false otherwise. 448 */ 449 template<typename _InputIterator, typename _Predicate> 450 _GLIBCXX20_CONSTEXPR 451 inline bool 452 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 453 { return __last == std::find_if_not(__first, __last, __pred); } 454 455 /** 456 * @brief Checks that a predicate is false for all the elements 457 * of a sequence. 458 * @ingroup non_mutating_algorithms 459 * @param __first An input iterator. 460 * @param __last An input iterator. 461 * @param __pred A predicate. 462 * @return True if the check is true, false otherwise. 463 * 464 * Returns true if @p __pred is false for each element in the range 465 * @p [__first,__last), and false otherwise. 466 */ 467 template<typename _InputIterator, typename _Predicate> 468 _GLIBCXX20_CONSTEXPR 469 inline bool 470 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 471 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); } 472 473 /** 474 * @brief Checks that a predicate is true for at least one element 475 * of a sequence. 476 * @ingroup non_mutating_algorithms 477 * @param __first An input iterator. 478 * @param __last An input iterator. 479 * @param __pred A predicate. 480 * @return True if the check is true, false otherwise. 481 * 482 * Returns true if an element exists in the range @p 483 * [__first,__last) such that @p __pred is true, and false 484 * otherwise. 485 */ 486 template<typename _InputIterator, typename _Predicate> 487 _GLIBCXX20_CONSTEXPR 488 inline bool 489 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 490 { return !std::none_of(__first, __last, __pred); } 491 492 /** 493 * @brief Find the first element in a sequence for which a 494 * predicate is false. 495 * @ingroup non_mutating_algorithms 496 * @param __first An input iterator. 497 * @param __last An input iterator. 498 * @param __pred A predicate. 499 * @return The first iterator @c i in the range @p [__first,__last) 500 * such that @p __pred(*i) is false, or @p __last if no such iterator exists. 501 */ 502 template<typename _InputIterator, typename _Predicate> 503 _GLIBCXX20_CONSTEXPR 504 inline _InputIterator 505 find_if_not(_InputIterator __first, _InputIterator __last, 506 _Predicate __pred) 507 { 508 // concept requirements 509 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 510 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 511 typename iterator_traits<_InputIterator>::value_type>) 512 __glibcxx_requires_valid_range(__first, __last); 513 return std::__find_if_not(__first, __last, 514 __gnu_cxx::__ops::__pred_iter(__pred)); 515 } 516 517 /** 518 * @brief Checks whether the sequence is partitioned. 519 * @ingroup mutating_algorithms 520 * @param __first An input iterator. 521 * @param __last An input iterator. 522 * @param __pred A predicate. 523 * @return True if the range @p [__first,__last) is partioned by @p __pred, 524 * i.e. if all elements that satisfy @p __pred appear before those that 525 * do not. 526 */ 527 template<typename _InputIterator, typename _Predicate> 528 _GLIBCXX20_CONSTEXPR 529 inline bool 530 is_partitioned(_InputIterator __first, _InputIterator __last, 531 _Predicate __pred) 532 { 533 __first = std::find_if_not(__first, __last, __pred); 534 if (__first == __last) 535 return true; 536 ++__first; 537 return std::none_of(__first, __last, __pred); 538 } 539 540 /** 541 * @brief Find the partition point of a partitioned range. 542 * @ingroup mutating_algorithms 543 * @param __first An iterator. 544 * @param __last Another iterator. 545 * @param __pred A predicate. 546 * @return An iterator @p mid such that @p all_of(__first, mid, __pred) 547 * and @p none_of(mid, __last, __pred) are both true. 548 */ 549 template<typename _ForwardIterator, typename _Predicate> 550 _GLIBCXX20_CONSTEXPR 551 _ForwardIterator 552 partition_point(_ForwardIterator __first, _ForwardIterator __last, 553 _Predicate __pred) 554 { 555 // concept requirements 556 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 557 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 558 typename iterator_traits<_ForwardIterator>::value_type>) 559 560 // A specific debug-mode test will be necessary... 561 __glibcxx_requires_valid_range(__first, __last); 562 563 typedef typename iterator_traits<_ForwardIterator>::difference_type 564 _DistanceType; 565 566 _DistanceType __len = std::distance(__first, __last); 567 568 while (__len > 0) 569 { 570 _DistanceType __half = __len >> 1; 571 _ForwardIterator __middle = __first; 572 std::advance(__middle, __half); 573 if (__pred(*__middle)) 574 { 575 __first = __middle; 576 ++__first; 577 __len = __len - __half - 1; 578 } 579 else 580 __len = __half; 581 } 582 return __first; 583 } 584 #endif 585 586 template<typename _InputIterator, typename _OutputIterator, 587 typename _Predicate> 588 _GLIBCXX20_CONSTEXPR 589 _OutputIterator 590 __remove_copy_if(_InputIterator __first, _InputIterator __last, 591 _OutputIterator __result, _Predicate __pred) 592 { 593 for (; __first != __last; ++__first) 594 if (!__pred(__first)) 595 { 596 *__result = *__first; 597 ++__result; 598 } 599 return __result; 600 } 601 602 /** 603 * @brief Copy a sequence, removing elements of a given value. 604 * @ingroup mutating_algorithms 605 * @param __first An input iterator. 606 * @param __last An input iterator. 607 * @param __result An output iterator. 608 * @param __value The value to be removed. 609 * @return An iterator designating the end of the resulting sequence. 610 * 611 * Copies each element in the range @p [__first,__last) not equal 612 * to @p __value to the range beginning at @p __result. 613 * remove_copy() is stable, so the relative order of elements that 614 * are copied is unchanged. 615 */ 616 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 617 _GLIBCXX20_CONSTEXPR 618 inline _OutputIterator 619 remove_copy(_InputIterator __first, _InputIterator __last, 620 _OutputIterator __result, const _Tp& __value) 621 { 622 // concept requirements 623 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 624 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 625 typename iterator_traits<_InputIterator>::value_type>) 626 __glibcxx_function_requires(_EqualOpConcept< 627 typename iterator_traits<_InputIterator>::value_type, _Tp>) 628 __glibcxx_requires_valid_range(__first, __last); 629 630 return std::__remove_copy_if(__first, __last, __result, 631 __gnu_cxx::__ops::__iter_equals_val(__value)); 632 } 633 634 /** 635 * @brief Copy a sequence, removing elements for which a predicate is true. 636 * @ingroup mutating_algorithms 637 * @param __first An input iterator. 638 * @param __last An input iterator. 639 * @param __result An output iterator. 640 * @param __pred A predicate. 641 * @return An iterator designating the end of the resulting sequence. 642 * 643 * Copies each element in the range @p [__first,__last) for which 644 * @p __pred returns false to the range beginning at @p __result. 645 * 646 * remove_copy_if() is stable, so the relative order of elements that are 647 * copied is unchanged. 648 */ 649 template<typename _InputIterator, typename _OutputIterator, 650 typename _Predicate> 651 _GLIBCXX20_CONSTEXPR 652 inline _OutputIterator 653 remove_copy_if(_InputIterator __first, _InputIterator __last, 654 _OutputIterator __result, _Predicate __pred) 655 { 656 // concept requirements 657 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 658 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 659 typename iterator_traits<_InputIterator>::value_type>) 660 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 661 typename iterator_traits<_InputIterator>::value_type>) 662 __glibcxx_requires_valid_range(__first, __last); 663 664 return std::__remove_copy_if(__first, __last, __result, 665 __gnu_cxx::__ops::__pred_iter(__pred)); 666 } 667 668 #if __cplusplus >= 201103L 669 /** 670 * @brief Copy the elements of a sequence for which a predicate is true. 671 * @ingroup mutating_algorithms 672 * @param __first An input iterator. 673 * @param __last An input iterator. 674 * @param __result An output iterator. 675 * @param __pred A predicate. 676 * @return An iterator designating the end of the resulting sequence. 677 * 678 * Copies each element in the range @p [__first,__last) for which 679 * @p __pred returns true to the range beginning at @p __result. 680 * 681 * copy_if() is stable, so the relative order of elements that are 682 * copied is unchanged. 683 */ 684 template<typename _InputIterator, typename _OutputIterator, 685 typename _Predicate> 686 _GLIBCXX20_CONSTEXPR 687 _OutputIterator 688 copy_if(_InputIterator __first, _InputIterator __last, 689 _OutputIterator __result, _Predicate __pred) 690 { 691 // concept requirements 692 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 693 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 694 typename iterator_traits<_InputIterator>::value_type>) 695 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 696 typename iterator_traits<_InputIterator>::value_type>) 697 __glibcxx_requires_valid_range(__first, __last); 698 699 for (; __first != __last; ++__first) 700 if (__pred(*__first)) 701 { 702 *__result = *__first; 703 ++__result; 704 } 705 return __result; 706 } 707 708 template<typename _InputIterator, typename _Size, typename _OutputIterator> 709 _GLIBCXX20_CONSTEXPR 710 _OutputIterator 711 __copy_n(_InputIterator __first, _Size __n, 712 _OutputIterator __result, input_iterator_tag) 713 { 714 return std::__niter_wrap(__result, 715 __copy_n_a(__first, __n, 716 std::__niter_base(__result), true)); 717 } 718 719 template<typename _RandomAccessIterator, typename _Size, 720 typename _OutputIterator> 721 _GLIBCXX20_CONSTEXPR 722 inline _OutputIterator 723 __copy_n(_RandomAccessIterator __first, _Size __n, 724 _OutputIterator __result, random_access_iterator_tag) 725 { return std::copy(__first, __first + __n, __result); } 726 727 /** 728 * @brief Copies the range [first,first+n) into [result,result+n). 729 * @ingroup mutating_algorithms 730 * @param __first An input iterator. 731 * @param __n The number of elements to copy. 732 * @param __result An output iterator. 733 * @return result+n. 734 * 735 * This inline function will boil down to a call to @c memmove whenever 736 * possible. Failing that, if random access iterators are passed, then the 737 * loop count will be known (and therefore a candidate for compiler 738 * optimizations such as unrolling). 739 */ 740 template<typename _InputIterator, typename _Size, typename _OutputIterator> 741 _GLIBCXX20_CONSTEXPR 742 inline _OutputIterator 743 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) 744 { 745 // concept requirements 746 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 747 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 748 typename iterator_traits<_InputIterator>::value_type>) 749 750 const auto __n2 = std::__size_to_integer(__n); 751 if (__n2 <= 0) 752 return __result; 753 754 __glibcxx_requires_can_increment(__first, __n2); 755 __glibcxx_requires_can_increment(__result, __n2); 756 757 return std::__copy_n(__first, __n2, __result, 758 std::__iterator_category(__first)); 759 } 760 761 /** 762 * @brief Copy the elements of a sequence to separate output sequences 763 * depending on the truth value of a predicate. 764 * @ingroup mutating_algorithms 765 * @param __first An input iterator. 766 * @param __last An input iterator. 767 * @param __out_true An output iterator. 768 * @param __out_false An output iterator. 769 * @param __pred A predicate. 770 * @return A pair designating the ends of the resulting sequences. 771 * 772 * Copies each element in the range @p [__first,__last) for which 773 * @p __pred returns true to the range beginning at @p out_true 774 * and each element for which @p __pred returns false to @p __out_false. 775 */ 776 template<typename _InputIterator, typename _OutputIterator1, 777 typename _OutputIterator2, typename _Predicate> 778 _GLIBCXX20_CONSTEXPR 779 pair<_OutputIterator1, _OutputIterator2> 780 partition_copy(_InputIterator __first, _InputIterator __last, 781 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 782 _Predicate __pred) 783 { 784 // concept requirements 785 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 786 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1, 787 typename iterator_traits<_InputIterator>::value_type>) 788 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2, 789 typename iterator_traits<_InputIterator>::value_type>) 790 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 791 typename iterator_traits<_InputIterator>::value_type>) 792 __glibcxx_requires_valid_range(__first, __last); 793 794 for (; __first != __last; ++__first) 795 if (__pred(*__first)) 796 { 797 *__out_true = *__first; 798 ++__out_true; 799 } 800 else 801 { 802 *__out_false = *__first; 803 ++__out_false; 804 } 805 806 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 807 } 808 #endif // C++11 809 810 template<typename _ForwardIterator, typename _Predicate> 811 _GLIBCXX20_CONSTEXPR 812 _ForwardIterator 813 __remove_if(_ForwardIterator __first, _ForwardIterator __last, 814 _Predicate __pred) 815 { 816 __first = std::__find_if(__first, __last, __pred); 817 if (__first == __last) 818 return __first; 819 _ForwardIterator __result = __first; 820 ++__first; 821 for (; __first != __last; ++__first) 822 if (!__pred(__first)) 823 { 824 *__result = _GLIBCXX_MOVE(*__first); 825 ++__result; 826 } 827 return __result; 828 } 829 830 /** 831 * @brief Remove elements from a sequence. 832 * @ingroup mutating_algorithms 833 * @param __first An input iterator. 834 * @param __last An input iterator. 835 * @param __value The value to be removed. 836 * @return An iterator designating the end of the resulting sequence. 837 * 838 * All elements equal to @p __value are removed from the range 839 * @p [__first,__last). 840 * 841 * remove() is stable, so the relative order of elements that are 842 * not removed is unchanged. 843 * 844 * Elements between the end of the resulting sequence and @p __last 845 * are still present, but their value is unspecified. 846 */ 847 template<typename _ForwardIterator, typename _Tp> 848 _GLIBCXX20_CONSTEXPR 849 inline _ForwardIterator 850 remove(_ForwardIterator __first, _ForwardIterator __last, 851 const _Tp& __value) 852 { 853 // concept requirements 854 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 855 _ForwardIterator>) 856 __glibcxx_function_requires(_EqualOpConcept< 857 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 858 __glibcxx_requires_valid_range(__first, __last); 859 860 return std::__remove_if(__first, __last, 861 __gnu_cxx::__ops::__iter_equals_val(__value)); 862 } 863 864 /** 865 * @brief Remove elements from a sequence using a predicate. 866 * @ingroup mutating_algorithms 867 * @param __first A forward iterator. 868 * @param __last A forward iterator. 869 * @param __pred A predicate. 870 * @return An iterator designating the end of the resulting sequence. 871 * 872 * All elements for which @p __pred returns true are removed from the range 873 * @p [__first,__last). 874 * 875 * remove_if() is stable, so the relative order of elements that are 876 * not removed is unchanged. 877 * 878 * Elements between the end of the resulting sequence and @p __last 879 * are still present, but their value is unspecified. 880 */ 881 template<typename _ForwardIterator, typename _Predicate> 882 _GLIBCXX20_CONSTEXPR 883 inline _ForwardIterator 884 remove_if(_ForwardIterator __first, _ForwardIterator __last, 885 _Predicate __pred) 886 { 887 // concept requirements 888 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 889 _ForwardIterator>) 890 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 891 typename iterator_traits<_ForwardIterator>::value_type>) 892 __glibcxx_requires_valid_range(__first, __last); 893 894 return std::__remove_if(__first, __last, 895 __gnu_cxx::__ops::__pred_iter(__pred)); 896 } 897 898 template<typename _ForwardIterator, typename _BinaryPredicate> 899 _GLIBCXX20_CONSTEXPR 900 _ForwardIterator 901 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 902 _BinaryPredicate __binary_pred) 903 { 904 if (__first == __last) 905 return __last; 906 _ForwardIterator __next = __first; 907 while (++__next != __last) 908 { 909 if (__binary_pred(__first, __next)) 910 return __first; 911 __first = __next; 912 } 913 return __last; 914 } 915 916 template<typename _ForwardIterator, typename _BinaryPredicate> 917 _GLIBCXX20_CONSTEXPR 918 _ForwardIterator 919 __unique(_ForwardIterator __first, _ForwardIterator __last, 920 _BinaryPredicate __binary_pred) 921 { 922 // Skip the beginning, if already unique. 923 __first = std::__adjacent_find(__first, __last, __binary_pred); 924 if (__first == __last) 925 return __last; 926 927 // Do the real copy work. 928 _ForwardIterator __dest = __first; 929 ++__first; 930 while (++__first != __last) 931 if (!__binary_pred(__dest, __first)) 932 *++__dest = _GLIBCXX_MOVE(*__first); 933 return ++__dest; 934 } 935 936 /** 937 * @brief Remove consecutive duplicate values from a sequence. 938 * @ingroup mutating_algorithms 939 * @param __first A forward iterator. 940 * @param __last A forward iterator. 941 * @return An iterator designating the end of the resulting sequence. 942 * 943 * Removes all but the first element from each group of consecutive 944 * values that compare equal. 945 * unique() is stable, so the relative order of elements that are 946 * not removed is unchanged. 947 * Elements between the end of the resulting sequence and @p __last 948 * are still present, but their value is unspecified. 949 */ 950 template<typename _ForwardIterator> 951 _GLIBCXX20_CONSTEXPR 952 inline _ForwardIterator 953 unique(_ForwardIterator __first, _ForwardIterator __last) 954 { 955 // concept requirements 956 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 957 _ForwardIterator>) 958 __glibcxx_function_requires(_EqualityComparableConcept< 959 typename iterator_traits<_ForwardIterator>::value_type>) 960 __glibcxx_requires_valid_range(__first, __last); 961 962 return std::__unique(__first, __last, 963 __gnu_cxx::__ops::__iter_equal_to_iter()); 964 } 965 966 /** 967 * @brief Remove consecutive values from a sequence using a predicate. 968 * @ingroup mutating_algorithms 969 * @param __first A forward iterator. 970 * @param __last A forward iterator. 971 * @param __binary_pred A binary predicate. 972 * @return An iterator designating the end of the resulting sequence. 973 * 974 * Removes all but the first element from each group of consecutive 975 * values for which @p __binary_pred returns true. 976 * unique() is stable, so the relative order of elements that are 977 * not removed is unchanged. 978 * Elements between the end of the resulting sequence and @p __last 979 * are still present, but their value is unspecified. 980 */ 981 template<typename _ForwardIterator, typename _BinaryPredicate> 982 _GLIBCXX20_CONSTEXPR 983 inline _ForwardIterator 984 unique(_ForwardIterator __first, _ForwardIterator __last, 985 _BinaryPredicate __binary_pred) 986 { 987 // concept requirements 988 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 989 _ForwardIterator>) 990 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 991 typename iterator_traits<_ForwardIterator>::value_type, 992 typename iterator_traits<_ForwardIterator>::value_type>) 993 __glibcxx_requires_valid_range(__first, __last); 994 995 return std::__unique(__first, __last, 996 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 997 } 998 999 /** 1000 * This is an uglified 1001 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1002 * _BinaryPredicate) 1003 * overloaded for forward iterators and output iterator as result. 1004 */ 1005 template<typename _ForwardIterator, typename _OutputIterator, 1006 typename _BinaryPredicate> 1007 _GLIBCXX20_CONSTEXPR 1008 _OutputIterator 1009 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, 1010 _OutputIterator __result, _BinaryPredicate __binary_pred, 1011 forward_iterator_tag, output_iterator_tag) 1012 { 1013 // concept requirements -- iterators already checked 1014 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1015 typename iterator_traits<_ForwardIterator>::value_type, 1016 typename iterator_traits<_ForwardIterator>::value_type>) 1017 1018 _ForwardIterator __next = __first; 1019 *__result = *__first; 1020 while (++__next != __last) 1021 if (!__binary_pred(__first, __next)) 1022 { 1023 __first = __next; 1024 *++__result = *__first; 1025 } 1026 return ++__result; 1027 } 1028 1029 /** 1030 * This is an uglified 1031 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1032 * _BinaryPredicate) 1033 * overloaded for input iterators and output iterator as result. 1034 */ 1035 template<typename _InputIterator, typename _OutputIterator, 1036 typename _BinaryPredicate> 1037 _GLIBCXX20_CONSTEXPR 1038 _OutputIterator 1039 __unique_copy(_InputIterator __first, _InputIterator __last, 1040 _OutputIterator __result, _BinaryPredicate __binary_pred, 1041 input_iterator_tag, output_iterator_tag) 1042 { 1043 // concept requirements -- iterators already checked 1044 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1045 typename iterator_traits<_InputIterator>::value_type, 1046 typename iterator_traits<_InputIterator>::value_type>) 1047 1048 typename iterator_traits<_InputIterator>::value_type __value = *__first; 1049 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred)) 1050 __rebound_pred 1051 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred); 1052 *__result = __value; 1053 while (++__first != __last) 1054 if (!__rebound_pred(__first, __value)) 1055 { 1056 __value = *__first; 1057 *++__result = __value; 1058 } 1059 return ++__result; 1060 } 1061 1062 /** 1063 * This is an uglified 1064 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 1065 * _BinaryPredicate) 1066 * overloaded for input iterators and forward iterator as result. 1067 */ 1068 template<typename _InputIterator, typename _ForwardIterator, 1069 typename _BinaryPredicate> 1070 _GLIBCXX20_CONSTEXPR 1071 _ForwardIterator 1072 __unique_copy(_InputIterator __first, _InputIterator __last, 1073 _ForwardIterator __result, _BinaryPredicate __binary_pred, 1074 input_iterator_tag, forward_iterator_tag) 1075 { 1076 // concept requirements -- iterators already checked 1077 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1078 typename iterator_traits<_ForwardIterator>::value_type, 1079 typename iterator_traits<_InputIterator>::value_type>) 1080 *__result = *__first; 1081 while (++__first != __last) 1082 if (!__binary_pred(__result, __first)) 1083 *++__result = *__first; 1084 return ++__result; 1085 } 1086 1087 /** 1088 * This is an uglified reverse(_BidirectionalIterator, 1089 * _BidirectionalIterator) 1090 * overloaded for bidirectional iterators. 1091 */ 1092 template<typename _BidirectionalIterator> 1093 _GLIBCXX20_CONSTEXPR 1094 void 1095 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, 1096 bidirectional_iterator_tag) 1097 { 1098 while (true) 1099 if (__first == __last || __first == --__last) 1100 return; 1101 else 1102 { 1103 std::iter_swap(__first, __last); 1104 ++__first; 1105 } 1106 } 1107 1108 /** 1109 * This is an uglified reverse(_BidirectionalIterator, 1110 * _BidirectionalIterator) 1111 * overloaded for random access iterators. 1112 */ 1113 template<typename _RandomAccessIterator> 1114 _GLIBCXX20_CONSTEXPR 1115 void 1116 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, 1117 random_access_iterator_tag) 1118 { 1119 if (__first == __last) 1120 return; 1121 --__last; 1122 while (__first < __last) 1123 { 1124 std::iter_swap(__first, __last); 1125 ++__first; 1126 --__last; 1127 } 1128 } 1129 1130 /** 1131 * @brief Reverse a sequence. 1132 * @ingroup mutating_algorithms 1133 * @param __first A bidirectional iterator. 1134 * @param __last A bidirectional iterator. 1135 * @return reverse() returns no value. 1136 * 1137 * Reverses the order of the elements in the range @p [__first,__last), 1138 * so that the first element becomes the last etc. 1139 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse() 1140 * swaps @p *(__first+i) and @p *(__last-(i+1)) 1141 */ 1142 template<typename _BidirectionalIterator> 1143 _GLIBCXX20_CONSTEXPR 1144 inline void 1145 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 1146 { 1147 // concept requirements 1148 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1149 _BidirectionalIterator>) 1150 __glibcxx_requires_valid_range(__first, __last); 1151 std::__reverse(__first, __last, std::__iterator_category(__first)); 1152 } 1153 1154 /** 1155 * @brief Copy a sequence, reversing its elements. 1156 * @ingroup mutating_algorithms 1157 * @param __first A bidirectional iterator. 1158 * @param __last A bidirectional iterator. 1159 * @param __result An output iterator. 1160 * @return An iterator designating the end of the resulting sequence. 1161 * 1162 * Copies the elements in the range @p [__first,__last) to the 1163 * range @p [__result,__result+(__last-__first)) such that the 1164 * order of the elements is reversed. For every @c i such that @p 1165 * 0<=i<=(__last-__first), @p reverse_copy() performs the 1166 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i). 1167 * The ranges @p [__first,__last) and @p 1168 * [__result,__result+(__last-__first)) must not overlap. 1169 */ 1170 template<typename _BidirectionalIterator, typename _OutputIterator> 1171 _GLIBCXX20_CONSTEXPR 1172 _OutputIterator 1173 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, 1174 _OutputIterator __result) 1175 { 1176 // concept requirements 1177 __glibcxx_function_requires(_BidirectionalIteratorConcept< 1178 _BidirectionalIterator>) 1179 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1180 typename iterator_traits<_BidirectionalIterator>::value_type>) 1181 __glibcxx_requires_valid_range(__first, __last); 1182 1183 while (__first != __last) 1184 { 1185 --__last; 1186 *__result = *__last; 1187 ++__result; 1188 } 1189 return __result; 1190 } 1191 1192 /** 1193 * This is a helper function for the rotate algorithm specialized on RAIs. 1194 * It returns the greatest common divisor of two integer values. 1195 */ 1196 template<typename _EuclideanRingElement> 1197 _GLIBCXX20_CONSTEXPR 1198 _EuclideanRingElement 1199 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 1200 { 1201 while (__n != 0) 1202 { 1203 _EuclideanRingElement __t = __m % __n; 1204 __m = __n; 1205 __n = __t; 1206 } 1207 return __m; 1208 } 1209 1210 inline namespace _V2 1211 { 1212 1213 /// This is a helper function for the rotate algorithm. 1214 template<typename _ForwardIterator> 1215 _GLIBCXX20_CONSTEXPR 1216 _ForwardIterator 1217 __rotate(_ForwardIterator __first, 1218 _ForwardIterator __middle, 1219 _ForwardIterator __last, 1220 forward_iterator_tag) 1221 { 1222 if (__first == __middle) 1223 return __last; 1224 else if (__last == __middle) 1225 return __first; 1226 1227 _ForwardIterator __first2 = __middle; 1228 do 1229 { 1230 std::iter_swap(__first, __first2); 1231 ++__first; 1232 ++__first2; 1233 if (__first == __middle) 1234 __middle = __first2; 1235 } 1236 while (__first2 != __last); 1237 1238 _ForwardIterator __ret = __first; 1239 1240 __first2 = __middle; 1241 1242 while (__first2 != __last) 1243 { 1244 std::iter_swap(__first, __first2); 1245 ++__first; 1246 ++__first2; 1247 if (__first == __middle) 1248 __middle = __first2; 1249 else if (__first2 == __last) 1250 __first2 = __middle; 1251 } 1252 return __ret; 1253 } 1254 1255 /// This is a helper function for the rotate algorithm. 1256 template<typename _BidirectionalIterator> 1257 _GLIBCXX20_CONSTEXPR 1258 _BidirectionalIterator 1259 __rotate(_BidirectionalIterator __first, 1260 _BidirectionalIterator __middle, 1261 _BidirectionalIterator __last, 1262 bidirectional_iterator_tag) 1263 { 1264 // concept requirements 1265 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1266 _BidirectionalIterator>) 1267 1268 if (__first == __middle) 1269 return __last; 1270 else if (__last == __middle) 1271 return __first; 1272 1273 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 1274 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 1275 1276 while (__first != __middle && __middle != __last) 1277 { 1278 std::iter_swap(__first, --__last); 1279 ++__first; 1280 } 1281 1282 if (__first == __middle) 1283 { 1284 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 1285 return __last; 1286 } 1287 else 1288 { 1289 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 1290 return __first; 1291 } 1292 } 1293 1294 /// This is a helper function for the rotate algorithm. 1295 template<typename _RandomAccessIterator> 1296 _GLIBCXX20_CONSTEXPR 1297 _RandomAccessIterator 1298 __rotate(_RandomAccessIterator __first, 1299 _RandomAccessIterator __middle, 1300 _RandomAccessIterator __last, 1301 random_access_iterator_tag) 1302 { 1303 // concept requirements 1304 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1305 _RandomAccessIterator>) 1306 1307 if (__first == __middle) 1308 return __last; 1309 else if (__last == __middle) 1310 return __first; 1311 1312 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 1313 _Distance; 1314 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1315 _ValueType; 1316 1317 _Distance __n = __last - __first; 1318 _Distance __k = __middle - __first; 1319 1320 if (__k == __n - __k) 1321 { 1322 std::swap_ranges(__first, __middle, __middle); 1323 return __middle; 1324 } 1325 1326 _RandomAccessIterator __p = __first; 1327 _RandomAccessIterator __ret = __first + (__last - __middle); 1328 1329 for (;;) 1330 { 1331 if (__k < __n - __k) 1332 { 1333 if (__is_pod(_ValueType) && __k == 1) 1334 { 1335 _ValueType __t = _GLIBCXX_MOVE(*__p); 1336 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p); 1337 *(__p + __n - 1) = _GLIBCXX_MOVE(__t); 1338 return __ret; 1339 } 1340 _RandomAccessIterator __q = __p + __k; 1341 for (_Distance __i = 0; __i < __n - __k; ++ __i) 1342 { 1343 std::iter_swap(__p, __q); 1344 ++__p; 1345 ++__q; 1346 } 1347 __n %= __k; 1348 if (__n == 0) 1349 return __ret; 1350 std::swap(__n, __k); 1351 __k = __n - __k; 1352 } 1353 else 1354 { 1355 __k = __n - __k; 1356 if (__is_pod(_ValueType) && __k == 1) 1357 { 1358 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); 1359 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); 1360 *__p = _GLIBCXX_MOVE(__t); 1361 return __ret; 1362 } 1363 _RandomAccessIterator __q = __p + __n; 1364 __p = __q - __k; 1365 for (_Distance __i = 0; __i < __n - __k; ++ __i) 1366 { 1367 --__p; 1368 --__q; 1369 std::iter_swap(__p, __q); 1370 } 1371 __n %= __k; 1372 if (__n == 0) 1373 return __ret; 1374 std::swap(__n, __k); 1375 } 1376 } 1377 } 1378 1379 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1380 // DR 488. rotate throws away useful information 1381 /** 1382 * @brief Rotate the elements of a sequence. 1383 * @ingroup mutating_algorithms 1384 * @param __first A forward iterator. 1385 * @param __middle A forward iterator. 1386 * @param __last A forward iterator. 1387 * @return first + (last - middle). 1388 * 1389 * Rotates the elements of the range @p [__first,__last) by 1390 * @p (__middle - __first) positions so that the element at @p __middle 1391 * is moved to @p __first, the element at @p __middle+1 is moved to 1392 * @p __first+1 and so on for each element in the range 1393 * @p [__first,__last). 1394 * 1395 * This effectively swaps the ranges @p [__first,__middle) and 1396 * @p [__middle,__last). 1397 * 1398 * Performs 1399 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n) 1400 * for each @p n in the range @p [0,__last-__first). 1401 */ 1402 template<typename _ForwardIterator> 1403 _GLIBCXX20_CONSTEXPR 1404 inline _ForwardIterator 1405 rotate(_ForwardIterator __first, _ForwardIterator __middle, 1406 _ForwardIterator __last) 1407 { 1408 // concept requirements 1409 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1410 _ForwardIterator>) 1411 __glibcxx_requires_valid_range(__first, __middle); 1412 __glibcxx_requires_valid_range(__middle, __last); 1413 1414 return std::__rotate(__first, __middle, __last, 1415 std::__iterator_category(__first)); 1416 } 1417 1418 } // namespace _V2 1419 1420 /** 1421 * @brief Copy a sequence, rotating its elements. 1422 * @ingroup mutating_algorithms 1423 * @param __first A forward iterator. 1424 * @param __middle A forward iterator. 1425 * @param __last A forward iterator. 1426 * @param __result An output iterator. 1427 * @return An iterator designating the end of the resulting sequence. 1428 * 1429 * Copies the elements of the range @p [__first,__last) to the 1430 * range beginning at @result, rotating the copied elements by 1431 * @p (__middle-__first) positions so that the element at @p __middle 1432 * is moved to @p __result, the element at @p __middle+1 is moved 1433 * to @p __result+1 and so on for each element in the range @p 1434 * [__first,__last). 1435 * 1436 * Performs 1437 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n) 1438 * for each @p n in the range @p [0,__last-__first). 1439 */ 1440 template<typename _ForwardIterator, typename _OutputIterator> 1441 _GLIBCXX20_CONSTEXPR 1442 inline _OutputIterator 1443 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, 1444 _ForwardIterator __last, _OutputIterator __result) 1445 { 1446 // concept requirements 1447 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1448 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1449 typename iterator_traits<_ForwardIterator>::value_type>) 1450 __glibcxx_requires_valid_range(__first, __middle); 1451 __glibcxx_requires_valid_range(__middle, __last); 1452 1453 return std::copy(__first, __middle, 1454 std::copy(__middle, __last, __result)); 1455 } 1456 1457 /// This is a helper function... 1458 template<typename _ForwardIterator, typename _Predicate> 1459 _GLIBCXX20_CONSTEXPR 1460 _ForwardIterator 1461 __partition(_ForwardIterator __first, _ForwardIterator __last, 1462 _Predicate __pred, forward_iterator_tag) 1463 { 1464 if (__first == __last) 1465 return __first; 1466 1467 while (__pred(*__first)) 1468 if (++__first == __last) 1469 return __first; 1470 1471 _ForwardIterator __next = __first; 1472 1473 while (++__next != __last) 1474 if (__pred(*__next)) 1475 { 1476 std::iter_swap(__first, __next); 1477 ++__first; 1478 } 1479 1480 return __first; 1481 } 1482 1483 /// This is a helper function... 1484 template<typename _BidirectionalIterator, typename _Predicate> 1485 _GLIBCXX20_CONSTEXPR 1486 _BidirectionalIterator 1487 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, 1488 _Predicate __pred, bidirectional_iterator_tag) 1489 { 1490 while (true) 1491 { 1492 while (true) 1493 if (__first == __last) 1494 return __first; 1495 else if (__pred(*__first)) 1496 ++__first; 1497 else 1498 break; 1499 --__last; 1500 while (true) 1501 if (__first == __last) 1502 return __first; 1503 else if (!bool(__pred(*__last))) 1504 --__last; 1505 else 1506 break; 1507 std::iter_swap(__first, __last); 1508 ++__first; 1509 } 1510 } 1511 1512 // partition 1513 1514 /// This is a helper function... 1515 /// Requires __first != __last and !__pred(__first) 1516 /// and __len == distance(__first, __last). 1517 /// 1518 /// !__pred(__first) allows us to guarantee that we don't 1519 /// move-assign an element onto itself. 1520 template<typename _ForwardIterator, typename _Pointer, typename _Predicate, 1521 typename _Distance> 1522 _ForwardIterator 1523 __stable_partition_adaptive(_ForwardIterator __first, 1524 _ForwardIterator __last, 1525 _Predicate __pred, _Distance __len, 1526 _Pointer __buffer, 1527 _Distance __buffer_size) 1528 { 1529 if (__len == 1) 1530 return __first; 1531 1532 if (__len <= __buffer_size) 1533 { 1534 _ForwardIterator __result1 = __first; 1535 _Pointer __result2 = __buffer; 1536 1537 // The precondition guarantees that !__pred(__first), so 1538 // move that element to the buffer before starting the loop. 1539 // This ensures that we only call __pred once per element. 1540 *__result2 = _GLIBCXX_MOVE(*__first); 1541 ++__result2; 1542 ++__first; 1543 for (; __first != __last; ++__first) 1544 if (__pred(__first)) 1545 { 1546 *__result1 = _GLIBCXX_MOVE(*__first); 1547 ++__result1; 1548 } 1549 else 1550 { 1551 *__result2 = _GLIBCXX_MOVE(*__first); 1552 ++__result2; 1553 } 1554 1555 _GLIBCXX_MOVE3(__buffer, __result2, __result1); 1556 return __result1; 1557 } 1558 1559 _ForwardIterator __middle = __first; 1560 std::advance(__middle, __len / 2); 1561 _ForwardIterator __left_split = 1562 std::__stable_partition_adaptive(__first, __middle, __pred, 1563 __len / 2, __buffer, 1564 __buffer_size); 1565 1566 // Advance past true-predicate values to satisfy this 1567 // function's preconditions. 1568 _Distance __right_len = __len - __len / 2; 1569 _ForwardIterator __right_split = 1570 std::__find_if_not_n(__middle, __right_len, __pred); 1571 1572 if (__right_len) 1573 __right_split = 1574 std::__stable_partition_adaptive(__right_split, __last, __pred, 1575 __right_len, 1576 __buffer, __buffer_size); 1577 1578 return std::rotate(__left_split, __middle, __right_split); 1579 } 1580 1581 template<typename _ForwardIterator, typename _Predicate> 1582 _ForwardIterator 1583 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, 1584 _Predicate __pred) 1585 { 1586 __first = std::__find_if_not(__first, __last, __pred); 1587 1588 if (__first == __last) 1589 return __first; 1590 1591 typedef typename iterator_traits<_ForwardIterator>::value_type 1592 _ValueType; 1593 typedef typename iterator_traits<_ForwardIterator>::difference_type 1594 _DistanceType; 1595 1596 _Temporary_buffer<_ForwardIterator, _ValueType> 1597 __buf(__first, std::distance(__first, __last)); 1598 return 1599 std::__stable_partition_adaptive(__first, __last, __pred, 1600 _DistanceType(__buf.requested_size()), 1601 __buf.begin(), 1602 _DistanceType(__buf.size())); 1603 } 1604 1605 /** 1606 * @brief Move elements for which a predicate is true to the beginning 1607 * of a sequence, preserving relative ordering. 1608 * @ingroup mutating_algorithms 1609 * @param __first A forward iterator. 1610 * @param __last A forward iterator. 1611 * @param __pred A predicate functor. 1612 * @return An iterator @p middle such that @p __pred(i) is true for each 1613 * iterator @p i in the range @p [first,middle) and false for each @p i 1614 * in the range @p [middle,last). 1615 * 1616 * Performs the same function as @p partition() with the additional 1617 * guarantee that the relative ordering of elements in each group is 1618 * preserved, so any two elements @p x and @p y in the range 1619 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same 1620 * relative ordering after calling @p stable_partition(). 1621 */ 1622 template<typename _ForwardIterator, typename _Predicate> 1623 inline _ForwardIterator 1624 stable_partition(_ForwardIterator __first, _ForwardIterator __last, 1625 _Predicate __pred) 1626 { 1627 // concept requirements 1628 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1629 _ForwardIterator>) 1630 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1631 typename iterator_traits<_ForwardIterator>::value_type>) 1632 __glibcxx_requires_valid_range(__first, __last); 1633 1634 return std::__stable_partition(__first, __last, 1635 __gnu_cxx::__ops::__pred_iter(__pred)); 1636 } 1637 1638 /// This is a helper function for the sort routines. 1639 template<typename _RandomAccessIterator, typename _Compare> 1640 _GLIBCXX20_CONSTEXPR 1641 void 1642 __heap_select(_RandomAccessIterator __first, 1643 _RandomAccessIterator __middle, 1644 _RandomAccessIterator __last, _Compare __comp) 1645 { 1646 std::__make_heap(__first, __middle, __comp); 1647 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 1648 if (__comp(__i, __first)) 1649 std::__pop_heap(__first, __middle, __i, __comp); 1650 } 1651 1652 // partial_sort 1653 1654 template<typename _InputIterator, typename _RandomAccessIterator, 1655 typename _Compare> 1656 _GLIBCXX20_CONSTEXPR 1657 _RandomAccessIterator 1658 __partial_sort_copy(_InputIterator __first, _InputIterator __last, 1659 _RandomAccessIterator __result_first, 1660 _RandomAccessIterator __result_last, 1661 _Compare __comp) 1662 { 1663 typedef typename iterator_traits<_InputIterator>::value_type 1664 _InputValueType; 1665 typedef iterator_traits<_RandomAccessIterator> _RItTraits; 1666 typedef typename _RItTraits::difference_type _DistanceType; 1667 1668 if (__result_first == __result_last) 1669 return __result_last; 1670 _RandomAccessIterator __result_real_last = __result_first; 1671 while (__first != __last && __result_real_last != __result_last) 1672 { 1673 *__result_real_last = *__first; 1674 ++__result_real_last; 1675 ++__first; 1676 } 1677 1678 std::__make_heap(__result_first, __result_real_last, __comp); 1679 while (__first != __last) 1680 { 1681 if (__comp(__first, __result_first)) 1682 std::__adjust_heap(__result_first, _DistanceType(0), 1683 _DistanceType(__result_real_last 1684 - __result_first), 1685 _InputValueType(*__first), __comp); 1686 ++__first; 1687 } 1688 std::__sort_heap(__result_first, __result_real_last, __comp); 1689 return __result_real_last; 1690 } 1691 1692 /** 1693 * @brief Copy the smallest elements of a sequence. 1694 * @ingroup sorting_algorithms 1695 * @param __first An iterator. 1696 * @param __last Another iterator. 1697 * @param __result_first A random-access iterator. 1698 * @param __result_last Another random-access iterator. 1699 * @return An iterator indicating the end of the resulting sequence. 1700 * 1701 * Copies and sorts the smallest N values from the range @p [__first,__last) 1702 * to the range beginning at @p __result_first, where the number of 1703 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 1704 * @p (__result_last-__result_first). 1705 * After the sort if @e i and @e j are iterators in the range 1706 * @p [__result_first,__result_first+N) such that i precedes j then 1707 * *j<*i is false. 1708 * The value returned is @p __result_first+N. 1709 */ 1710 template<typename _InputIterator, typename _RandomAccessIterator> 1711 _GLIBCXX20_CONSTEXPR 1712 inline _RandomAccessIterator 1713 partial_sort_copy(_InputIterator __first, _InputIterator __last, 1714 _RandomAccessIterator __result_first, 1715 _RandomAccessIterator __result_last) 1716 { 1717 #ifdef _GLIBCXX_CONCEPT_CHECKS 1718 typedef typename iterator_traits<_InputIterator>::value_type 1719 _InputValueType; 1720 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1721 _OutputValueType; 1722 #endif 1723 1724 // concept requirements 1725 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1726 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 1727 _OutputValueType>) 1728 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, 1729 _OutputValueType>) 1730 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 1731 __glibcxx_requires_valid_range(__first, __last); 1732 __glibcxx_requires_irreflexive(__first, __last); 1733 __glibcxx_requires_valid_range(__result_first, __result_last); 1734 1735 return std::__partial_sort_copy(__first, __last, 1736 __result_first, __result_last, 1737 __gnu_cxx::__ops::__iter_less_iter()); 1738 } 1739 1740 /** 1741 * @brief Copy the smallest elements of a sequence using a predicate for 1742 * comparison. 1743 * @ingroup sorting_algorithms 1744 * @param __first An input iterator. 1745 * @param __last Another input iterator. 1746 * @param __result_first A random-access iterator. 1747 * @param __result_last Another random-access iterator. 1748 * @param __comp A comparison functor. 1749 * @return An iterator indicating the end of the resulting sequence. 1750 * 1751 * Copies and sorts the smallest N values from the range @p [__first,__last) 1752 * to the range beginning at @p result_first, where the number of 1753 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 1754 * @p (__result_last-__result_first). 1755 * After the sort if @e i and @e j are iterators in the range 1756 * @p [__result_first,__result_first+N) such that i precedes j then 1757 * @p __comp(*j,*i) is false. 1758 * The value returned is @p __result_first+N. 1759 */ 1760 template<typename _InputIterator, typename _RandomAccessIterator, 1761 typename _Compare> 1762 _GLIBCXX20_CONSTEXPR 1763 inline _RandomAccessIterator 1764 partial_sort_copy(_InputIterator __first, _InputIterator __last, 1765 _RandomAccessIterator __result_first, 1766 _RandomAccessIterator __result_last, 1767 _Compare __comp) 1768 { 1769 #ifdef _GLIBCXX_CONCEPT_CHECKS 1770 typedef typename iterator_traits<_InputIterator>::value_type 1771 _InputValueType; 1772 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1773 _OutputValueType; 1774 #endif 1775 1776 // concept requirements 1777 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1778 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1779 _RandomAccessIterator>) 1780 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 1781 _OutputValueType>) 1782 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1783 _InputValueType, _OutputValueType>) 1784 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1785 _OutputValueType, _OutputValueType>) 1786 __glibcxx_requires_valid_range(__first, __last); 1787 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 1788 __glibcxx_requires_valid_range(__result_first, __result_last); 1789 1790 return std::__partial_sort_copy(__first, __last, 1791 __result_first, __result_last, 1792 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 1793 } 1794 1795 /// This is a helper function for the sort routine. 1796 template<typename _RandomAccessIterator, typename _Compare> 1797 _GLIBCXX20_CONSTEXPR 1798 void 1799 __unguarded_linear_insert(_RandomAccessIterator __last, 1800 _Compare __comp) 1801 { 1802 typename iterator_traits<_RandomAccessIterator>::value_type 1803 __val = _GLIBCXX_MOVE(*__last); 1804 _RandomAccessIterator __next = __last; 1805 --__next; 1806 while (__comp(__val, __next)) 1807 { 1808 *__last = _GLIBCXX_MOVE(*__next); 1809 __last = __next; 1810 --__next; 1811 } 1812 *__last = _GLIBCXX_MOVE(__val); 1813 } 1814 1815 /// This is a helper function for the sort routine. 1816 template<typename _RandomAccessIterator, typename _Compare> 1817 _GLIBCXX20_CONSTEXPR 1818 void 1819 __insertion_sort(_RandomAccessIterator __first, 1820 _RandomAccessIterator __last, _Compare __comp) 1821 { 1822 if (__first == __last) return; 1823 1824 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 1825 { 1826 if (__comp(__i, __first)) 1827 { 1828 typename iterator_traits<_RandomAccessIterator>::value_type 1829 __val = _GLIBCXX_MOVE(*__i); 1830 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 1831 *__first = _GLIBCXX_MOVE(__val); 1832 } 1833 else 1834 std::__unguarded_linear_insert(__i, 1835 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1836 } 1837 } 1838 1839 /// This is a helper function for the sort routine. 1840 template<typename _RandomAccessIterator, typename _Compare> 1841 _GLIBCXX20_CONSTEXPR 1842 inline void 1843 __unguarded_insertion_sort(_RandomAccessIterator __first, 1844 _RandomAccessIterator __last, _Compare __comp) 1845 { 1846 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 1847 std::__unguarded_linear_insert(__i, 1848 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1849 } 1850 1851 /** 1852 * @doctodo 1853 * This controls some aspect of the sort routines. 1854 */ 1855 enum { _S_threshold = 16 }; 1856 1857 /// This is a helper function for the sort routine. 1858 template<typename _RandomAccessIterator, typename _Compare> 1859 _GLIBCXX20_CONSTEXPR 1860 void 1861 __final_insertion_sort(_RandomAccessIterator __first, 1862 _RandomAccessIterator __last, _Compare __comp) 1863 { 1864 if (__last - __first > int(_S_threshold)) 1865 { 1866 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 1867 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 1868 __comp); 1869 } 1870 else 1871 std::__insertion_sort(__first, __last, __comp); 1872 } 1873 1874 /// This is a helper function... 1875 template<typename _RandomAccessIterator, typename _Compare> 1876 _GLIBCXX20_CONSTEXPR 1877 _RandomAccessIterator 1878 __unguarded_partition(_RandomAccessIterator __first, 1879 _RandomAccessIterator __last, 1880 _RandomAccessIterator __pivot, _Compare __comp) 1881 { 1882 while (true) 1883 { 1884 while (__comp(__first, __pivot)) 1885 ++__first; 1886 --__last; 1887 while (__comp(__pivot, __last)) 1888 --__last; 1889 if (!(__first < __last)) 1890 return __first; 1891 std::iter_swap(__first, __last); 1892 ++__first; 1893 } 1894 } 1895 1896 /// This is a helper function... 1897 template<typename _RandomAccessIterator, typename _Compare> 1898 _GLIBCXX20_CONSTEXPR 1899 inline _RandomAccessIterator 1900 __unguarded_partition_pivot(_RandomAccessIterator __first, 1901 _RandomAccessIterator __last, _Compare __comp) 1902 { 1903 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 1904 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, 1905 __comp); 1906 return std::__unguarded_partition(__first + 1, __last, __first, __comp); 1907 } 1908 1909 template<typename _RandomAccessIterator, typename _Compare> 1910 _GLIBCXX20_CONSTEXPR 1911 inline void 1912 __partial_sort(_RandomAccessIterator __first, 1913 _RandomAccessIterator __middle, 1914 _RandomAccessIterator __last, 1915 _Compare __comp) 1916 { 1917 std::__heap_select(__first, __middle, __last, __comp); 1918 std::__sort_heap(__first, __middle, __comp); 1919 } 1920 1921 /// This is a helper function for the sort routine. 1922 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1923 _GLIBCXX20_CONSTEXPR 1924 void 1925 __introsort_loop(_RandomAccessIterator __first, 1926 _RandomAccessIterator __last, 1927 _Size __depth_limit, _Compare __comp) 1928 { 1929 while (__last - __first > int(_S_threshold)) 1930 { 1931 if (__depth_limit == 0) 1932 { 1933 std::__partial_sort(__first, __last, __last, __comp); 1934 return; 1935 } 1936 --__depth_limit; 1937 _RandomAccessIterator __cut = 1938 std::__unguarded_partition_pivot(__first, __last, __comp); 1939 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 1940 __last = __cut; 1941 } 1942 } 1943 1944 // sort 1945 1946 template<typename _RandomAccessIterator, typename _Compare> 1947 _GLIBCXX20_CONSTEXPR 1948 inline void 1949 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 1950 _Compare __comp) 1951 { 1952 if (__first != __last) 1953 { 1954 std::__introsort_loop(__first, __last, 1955 std::__lg(__last - __first) * 2, 1956 __comp); 1957 std::__final_insertion_sort(__first, __last, __comp); 1958 } 1959 } 1960 1961 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1962 _GLIBCXX20_CONSTEXPR 1963 void 1964 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 1965 _RandomAccessIterator __last, _Size __depth_limit, 1966 _Compare __comp) 1967 { 1968 while (__last - __first > 3) 1969 { 1970 if (__depth_limit == 0) 1971 { 1972 std::__heap_select(__first, __nth + 1, __last, __comp); 1973 // Place the nth largest element in its final position. 1974 std::iter_swap(__first, __nth); 1975 return; 1976 } 1977 --__depth_limit; 1978 _RandomAccessIterator __cut = 1979 std::__unguarded_partition_pivot(__first, __last, __comp); 1980 if (__cut <= __nth) 1981 __first = __cut; 1982 else 1983 __last = __cut; 1984 } 1985 std::__insertion_sort(__first, __last, __comp); 1986 } 1987 1988 // nth_element 1989 1990 // lower_bound moved to stl_algobase.h 1991 1992 /** 1993 * @brief Finds the first position in which @p __val could be inserted 1994 * without changing the ordering. 1995 * @ingroup binary_search_algorithms 1996 * @param __first An iterator. 1997 * @param __last Another iterator. 1998 * @param __val The search term. 1999 * @param __comp A functor to use for comparisons. 2000 * @return An iterator pointing to the first element <em>not less 2001 * than</em> @p __val, or end() if every element is less 2002 * than @p __val. 2003 * @ingroup binary_search_algorithms 2004 * 2005 * The comparison function should have the same effects on ordering as 2006 * the function used for the initial sort. 2007 */ 2008 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2009 _GLIBCXX20_CONSTEXPR 2010 inline _ForwardIterator 2011 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 2012 const _Tp& __val, _Compare __comp) 2013 { 2014 // concept requirements 2015 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2016 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2017 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2018 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2019 __val, __comp); 2020 2021 return std::__lower_bound(__first, __last, __val, 2022 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2023 } 2024 2025 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2026 _GLIBCXX20_CONSTEXPR 2027 _ForwardIterator 2028 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2029 const _Tp& __val, _Compare __comp) 2030 { 2031 typedef typename iterator_traits<_ForwardIterator>::difference_type 2032 _DistanceType; 2033 2034 _DistanceType __len = std::distance(__first, __last); 2035 2036 while (__len > 0) 2037 { 2038 _DistanceType __half = __len >> 1; 2039 _ForwardIterator __middle = __first; 2040 std::advance(__middle, __half); 2041 if (__comp(__val, __middle)) 2042 __len = __half; 2043 else 2044 { 2045 __first = __middle; 2046 ++__first; 2047 __len = __len - __half - 1; 2048 } 2049 } 2050 return __first; 2051 } 2052 2053 /** 2054 * @brief Finds the last position in which @p __val could be inserted 2055 * without changing the ordering. 2056 * @ingroup binary_search_algorithms 2057 * @param __first An iterator. 2058 * @param __last Another iterator. 2059 * @param __val The search term. 2060 * @return An iterator pointing to the first element greater than @p __val, 2061 * or end() if no elements are greater than @p __val. 2062 * @ingroup binary_search_algorithms 2063 */ 2064 template<typename _ForwardIterator, typename _Tp> 2065 _GLIBCXX20_CONSTEXPR 2066 inline _ForwardIterator 2067 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2068 const _Tp& __val) 2069 { 2070 // concept requirements 2071 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2072 __glibcxx_function_requires(_LessThanOpConcept< 2073 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2074 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2075 2076 return std::__upper_bound(__first, __last, __val, 2077 __gnu_cxx::__ops::__val_less_iter()); 2078 } 2079 2080 /** 2081 * @brief Finds the last position in which @p __val could be inserted 2082 * without changing the ordering. 2083 * @ingroup binary_search_algorithms 2084 * @param __first An iterator. 2085 * @param __last Another iterator. 2086 * @param __val The search term. 2087 * @param __comp A functor to use for comparisons. 2088 * @return An iterator pointing to the first element greater than @p __val, 2089 * or end() if no elements are greater than @p __val. 2090 * @ingroup binary_search_algorithms 2091 * 2092 * The comparison function should have the same effects on ordering as 2093 * the function used for the initial sort. 2094 */ 2095 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2096 _GLIBCXX20_CONSTEXPR 2097 inline _ForwardIterator 2098 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2099 const _Tp& __val, _Compare __comp) 2100 { 2101 // concept requirements 2102 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2103 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2104 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2105 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2106 __val, __comp); 2107 2108 return std::__upper_bound(__first, __last, __val, 2109 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2110 } 2111 2112 template<typename _ForwardIterator, typename _Tp, 2113 typename _CompareItTp, typename _CompareTpIt> 2114 _GLIBCXX20_CONSTEXPR 2115 pair<_ForwardIterator, _ForwardIterator> 2116 __equal_range(_ForwardIterator __first, _ForwardIterator __last, 2117 const _Tp& __val, 2118 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) 2119 { 2120 typedef typename iterator_traits<_ForwardIterator>::difference_type 2121 _DistanceType; 2122 2123 _DistanceType __len = std::distance(__first, __last); 2124 2125 while (__len > 0) 2126 { 2127 _DistanceType __half = __len >> 1; 2128 _ForwardIterator __middle = __first; 2129 std::advance(__middle, __half); 2130 if (__comp_it_val(__middle, __val)) 2131 { 2132 __first = __middle; 2133 ++__first; 2134 __len = __len - __half - 1; 2135 } 2136 else if (__comp_val_it(__val, __middle)) 2137 __len = __half; 2138 else 2139 { 2140 _ForwardIterator __left 2141 = std::__lower_bound(__first, __middle, __val, __comp_it_val); 2142 std::advance(__first, __len); 2143 _ForwardIterator __right 2144 = std::__upper_bound(++__middle, __first, __val, __comp_val_it); 2145 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 2146 } 2147 } 2148 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 2149 } 2150 2151 /** 2152 * @brief Finds the largest subrange in which @p __val could be inserted 2153 * at any place in it without changing the ordering. 2154 * @ingroup binary_search_algorithms 2155 * @param __first An iterator. 2156 * @param __last Another iterator. 2157 * @param __val The search term. 2158 * @return An pair of iterators defining the subrange. 2159 * @ingroup binary_search_algorithms 2160 * 2161 * This is equivalent to 2162 * @code 2163 * std::make_pair(lower_bound(__first, __last, __val), 2164 * upper_bound(__first, __last, __val)) 2165 * @endcode 2166 * but does not actually call those functions. 2167 */ 2168 template<typename _ForwardIterator, typename _Tp> 2169 _GLIBCXX20_CONSTEXPR 2170 inline pair<_ForwardIterator, _ForwardIterator> 2171 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2172 const _Tp& __val) 2173 { 2174 // concept requirements 2175 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2176 __glibcxx_function_requires(_LessThanOpConcept< 2177 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2178 __glibcxx_function_requires(_LessThanOpConcept< 2179 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2180 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2181 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2182 2183 return std::__equal_range(__first, __last, __val, 2184 __gnu_cxx::__ops::__iter_less_val(), 2185 __gnu_cxx::__ops::__val_less_iter()); 2186 } 2187 2188 /** 2189 * @brief Finds the largest subrange in which @p __val could be inserted 2190 * at any place in it without changing the ordering. 2191 * @param __first An iterator. 2192 * @param __last Another iterator. 2193 * @param __val The search term. 2194 * @param __comp A functor to use for comparisons. 2195 * @return An pair of iterators defining the subrange. 2196 * @ingroup binary_search_algorithms 2197 * 2198 * This is equivalent to 2199 * @code 2200 * std::make_pair(lower_bound(__first, __last, __val, __comp), 2201 * upper_bound(__first, __last, __val, __comp)) 2202 * @endcode 2203 * but does not actually call those functions. 2204 */ 2205 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2206 _GLIBCXX20_CONSTEXPR 2207 inline pair<_ForwardIterator, _ForwardIterator> 2208 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2209 const _Tp& __val, _Compare __comp) 2210 { 2211 // concept requirements 2212 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2213 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2214 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2215 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2216 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2217 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2218 __val, __comp); 2219 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2220 __val, __comp); 2221 2222 return std::__equal_range(__first, __last, __val, 2223 __gnu_cxx::__ops::__iter_comp_val(__comp), 2224 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2225 } 2226 2227 /** 2228 * @brief Determines whether an element exists in a range. 2229 * @ingroup binary_search_algorithms 2230 * @param __first An iterator. 2231 * @param __last Another iterator. 2232 * @param __val The search term. 2233 * @return True if @p __val (or its equivalent) is in [@p 2234 * __first,@p __last ]. 2235 * 2236 * Note that this does not actually return an iterator to @p __val. For 2237 * that, use std::find or a container's specialized find member functions. 2238 */ 2239 template<typename _ForwardIterator, typename _Tp> 2240 _GLIBCXX20_CONSTEXPR 2241 bool 2242 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2243 const _Tp& __val) 2244 { 2245 // concept requirements 2246 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2247 __glibcxx_function_requires(_LessThanOpConcept< 2248 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2249 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2250 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2251 2252 _ForwardIterator __i 2253 = std::__lower_bound(__first, __last, __val, 2254 __gnu_cxx::__ops::__iter_less_val()); 2255 return __i != __last && !(__val < *__i); 2256 } 2257 2258 /** 2259 * @brief Determines whether an element exists in a range. 2260 * @ingroup binary_search_algorithms 2261 * @param __first An iterator. 2262 * @param __last Another iterator. 2263 * @param __val The search term. 2264 * @param __comp A functor to use for comparisons. 2265 * @return True if @p __val (or its equivalent) is in @p [__first,__last]. 2266 * 2267 * Note that this does not actually return an iterator to @p __val. For 2268 * that, use std::find or a container's specialized find member functions. 2269 * 2270 * The comparison function should have the same effects on ordering as 2271 * the function used for the initial sort. 2272 */ 2273 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2274 _GLIBCXX20_CONSTEXPR 2275 bool 2276 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2277 const _Tp& __val, _Compare __comp) 2278 { 2279 // concept requirements 2280 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2281 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2282 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2283 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2284 __val, __comp); 2285 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2286 __val, __comp); 2287 2288 _ForwardIterator __i 2289 = std::__lower_bound(__first, __last, __val, 2290 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2291 return __i != __last && !bool(__comp(__val, *__i)); 2292 } 2293 2294 // merge 2295 2296 /// This is a helper function for the __merge_adaptive routines. 2297 template<typename _InputIterator1, typename _InputIterator2, 2298 typename _OutputIterator, typename _Compare> 2299 void 2300 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 2301 _InputIterator2 __first2, _InputIterator2 __last2, 2302 _OutputIterator __result, _Compare __comp) 2303 { 2304 while (__first1 != __last1 && __first2 != __last2) 2305 { 2306 if (__comp(__first2, __first1)) 2307 { 2308 *__result = _GLIBCXX_MOVE(*__first2); 2309 ++__first2; 2310 } 2311 else 2312 { 2313 *__result = _GLIBCXX_MOVE(*__first1); 2314 ++__first1; 2315 } 2316 ++__result; 2317 } 2318 if (__first1 != __last1) 2319 _GLIBCXX_MOVE3(__first1, __last1, __result); 2320 } 2321 2322 /// This is a helper function for the __merge_adaptive routines. 2323 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2324 typename _BidirectionalIterator3, typename _Compare> 2325 void 2326 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 2327 _BidirectionalIterator1 __last1, 2328 _BidirectionalIterator2 __first2, 2329 _BidirectionalIterator2 __last2, 2330 _BidirectionalIterator3 __result, 2331 _Compare __comp) 2332 { 2333 if (__first1 == __last1) 2334 { 2335 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 2336 return; 2337 } 2338 else if (__first2 == __last2) 2339 return; 2340 2341 --__last1; 2342 --__last2; 2343 while (true) 2344 { 2345 if (__comp(__last2, __last1)) 2346 { 2347 *--__result = _GLIBCXX_MOVE(*__last1); 2348 if (__first1 == __last1) 2349 { 2350 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 2351 return; 2352 } 2353 --__last1; 2354 } 2355 else 2356 { 2357 *--__result = _GLIBCXX_MOVE(*__last2); 2358 if (__first2 == __last2) 2359 return; 2360 --__last2; 2361 } 2362 } 2363 } 2364 2365 /// This is a helper function for the merge routines. 2366 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2367 typename _Distance> 2368 _BidirectionalIterator1 2369 __rotate_adaptive(_BidirectionalIterator1 __first, 2370 _BidirectionalIterator1 __middle, 2371 _BidirectionalIterator1 __last, 2372 _Distance __len1, _Distance __len2, 2373 _BidirectionalIterator2 __buffer, 2374 _Distance __buffer_size) 2375 { 2376 _BidirectionalIterator2 __buffer_end; 2377 if (__len1 > __len2 && __len2 <= __buffer_size) 2378 { 2379 if (__len2) 2380 { 2381 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2382 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 2383 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 2384 } 2385 else 2386 return __first; 2387 } 2388 else if (__len1 <= __buffer_size) 2389 { 2390 if (__len1) 2391 { 2392 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2393 _GLIBCXX_MOVE3(__middle, __last, __first); 2394 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 2395 } 2396 else 2397 return __last; 2398 } 2399 else 2400 return std::rotate(__first, __middle, __last); 2401 } 2402 2403 /// This is a helper function for the merge routines. 2404 template<typename _BidirectionalIterator, typename _Distance, 2405 typename _Pointer, typename _Compare> 2406 void 2407 __merge_adaptive(_BidirectionalIterator __first, 2408 _BidirectionalIterator __middle, 2409 _BidirectionalIterator __last, 2410 _Distance __len1, _Distance __len2, 2411 _Pointer __buffer, _Distance __buffer_size, 2412 _Compare __comp) 2413 { 2414 if (__len1 <= __len2 && __len1 <= __buffer_size) 2415 { 2416 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2417 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 2418 __first, __comp); 2419 } 2420 else if (__len2 <= __buffer_size) 2421 { 2422 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2423 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 2424 __buffer_end, __last, __comp); 2425 } 2426 else 2427 { 2428 _BidirectionalIterator __first_cut = __first; 2429 _BidirectionalIterator __second_cut = __middle; 2430 _Distance __len11 = 0; 2431 _Distance __len22 = 0; 2432 if (__len1 > __len2) 2433 { 2434 __len11 = __len1 / 2; 2435 std::advance(__first_cut, __len11); 2436 __second_cut 2437 = std::__lower_bound(__middle, __last, *__first_cut, 2438 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2439 __len22 = std::distance(__middle, __second_cut); 2440 } 2441 else 2442 { 2443 __len22 = __len2 / 2; 2444 std::advance(__second_cut, __len22); 2445 __first_cut 2446 = std::__upper_bound(__first, __middle, *__second_cut, 2447 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2448 __len11 = std::distance(__first, __first_cut); 2449 } 2450 2451 _BidirectionalIterator __new_middle 2452 = std::__rotate_adaptive(__first_cut, __middle, __second_cut, 2453 __len1 - __len11, __len22, __buffer, 2454 __buffer_size); 2455 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 2456 __len22, __buffer, __buffer_size, __comp); 2457 std::__merge_adaptive(__new_middle, __second_cut, __last, 2458 __len1 - __len11, 2459 __len2 - __len22, __buffer, 2460 __buffer_size, __comp); 2461 } 2462 } 2463 2464 /// This is a helper function for the merge routines. 2465 template<typename _BidirectionalIterator, typename _Distance, 2466 typename _Compare> 2467 void 2468 __merge_without_buffer(_BidirectionalIterator __first, 2469 _BidirectionalIterator __middle, 2470 _BidirectionalIterator __last, 2471 _Distance __len1, _Distance __len2, 2472 _Compare __comp) 2473 { 2474 if (__len1 == 0 || __len2 == 0) 2475 return; 2476 2477 if (__len1 + __len2 == 2) 2478 { 2479 if (__comp(__middle, __first)) 2480 std::iter_swap(__first, __middle); 2481 return; 2482 } 2483 2484 _BidirectionalIterator __first_cut = __first; 2485 _BidirectionalIterator __second_cut = __middle; 2486 _Distance __len11 = 0; 2487 _Distance __len22 = 0; 2488 if (__len1 > __len2) 2489 { 2490 __len11 = __len1 / 2; 2491 std::advance(__first_cut, __len11); 2492 __second_cut 2493 = std::__lower_bound(__middle, __last, *__first_cut, 2494 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2495 __len22 = std::distance(__middle, __second_cut); 2496 } 2497 else 2498 { 2499 __len22 = __len2 / 2; 2500 std::advance(__second_cut, __len22); 2501 __first_cut 2502 = std::__upper_bound(__first, __middle, *__second_cut, 2503 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2504 __len11 = std::distance(__first, __first_cut); 2505 } 2506 2507 _BidirectionalIterator __new_middle 2508 = std::rotate(__first_cut, __middle, __second_cut); 2509 std::__merge_without_buffer(__first, __first_cut, __new_middle, 2510 __len11, __len22, __comp); 2511 std::__merge_without_buffer(__new_middle, __second_cut, __last, 2512 __len1 - __len11, __len2 - __len22, __comp); 2513 } 2514 2515 template<typename _BidirectionalIterator, typename _Compare> 2516 void 2517 __inplace_merge(_BidirectionalIterator __first, 2518 _BidirectionalIterator __middle, 2519 _BidirectionalIterator __last, 2520 _Compare __comp) 2521 { 2522 typedef typename iterator_traits<_BidirectionalIterator>::value_type 2523 _ValueType; 2524 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 2525 _DistanceType; 2526 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf; 2527 2528 if (__first == __middle || __middle == __last) 2529 return; 2530 2531 const _DistanceType __len1 = std::distance(__first, __middle); 2532 const _DistanceType __len2 = std::distance(__middle, __last); 2533 2534 // __merge_adaptive will use a buffer for the smaller of 2535 // [first,middle) and [middle,last). 2536 _TmpBuf __buf(__first, std::min(__len1, __len2)); 2537 2538 if (__buf.begin() == 0) 2539 std::__merge_without_buffer 2540 (__first, __middle, __last, __len1, __len2, __comp); 2541 else 2542 std::__merge_adaptive 2543 (__first, __middle, __last, __len1, __len2, __buf.begin(), 2544 _DistanceType(__buf.size()), __comp); 2545 } 2546 2547 /** 2548 * @brief Merges two sorted ranges in place. 2549 * @ingroup sorting_algorithms 2550 * @param __first An iterator. 2551 * @param __middle Another iterator. 2552 * @param __last Another iterator. 2553 * @return Nothing. 2554 * 2555 * Merges two sorted and consecutive ranges, [__first,__middle) and 2556 * [__middle,__last), and puts the result in [__first,__last). The 2557 * output will be sorted. The sort is @e stable, that is, for 2558 * equivalent elements in the two ranges, elements from the first 2559 * range will always come before elements from the second. 2560 * 2561 * If enough additional memory is available, this takes (__last-__first)-1 2562 * comparisons. Otherwise an NlogN algorithm is used, where N is 2563 * distance(__first,__last). 2564 */ 2565 template<typename _BidirectionalIterator> 2566 inline void 2567 inplace_merge(_BidirectionalIterator __first, 2568 _BidirectionalIterator __middle, 2569 _BidirectionalIterator __last) 2570 { 2571 // concept requirements 2572 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2573 _BidirectionalIterator>) 2574 __glibcxx_function_requires(_LessThanComparableConcept< 2575 typename iterator_traits<_BidirectionalIterator>::value_type>) 2576 __glibcxx_requires_sorted(__first, __middle); 2577 __glibcxx_requires_sorted(__middle, __last); 2578 __glibcxx_requires_irreflexive(__first, __last); 2579 2580 std::__inplace_merge(__first, __middle, __last, 2581 __gnu_cxx::__ops::__iter_less_iter()); 2582 } 2583 2584 /** 2585 * @brief Merges two sorted ranges in place. 2586 * @ingroup sorting_algorithms 2587 * @param __first An iterator. 2588 * @param __middle Another iterator. 2589 * @param __last Another iterator. 2590 * @param __comp A functor to use for comparisons. 2591 * @return Nothing. 2592 * 2593 * Merges two sorted and consecutive ranges, [__first,__middle) and 2594 * [middle,last), and puts the result in [__first,__last). The output will 2595 * be sorted. The sort is @e stable, that is, for equivalent 2596 * elements in the two ranges, elements from the first range will always 2597 * come before elements from the second. 2598 * 2599 * If enough additional memory is available, this takes (__last-__first)-1 2600 * comparisons. Otherwise an NlogN algorithm is used, where N is 2601 * distance(__first,__last). 2602 * 2603 * The comparison function should have the same effects on ordering as 2604 * the function used for the initial sort. 2605 */ 2606 template<typename _BidirectionalIterator, typename _Compare> 2607 inline void 2608 inplace_merge(_BidirectionalIterator __first, 2609 _BidirectionalIterator __middle, 2610 _BidirectionalIterator __last, 2611 _Compare __comp) 2612 { 2613 // concept requirements 2614 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2615 _BidirectionalIterator>) 2616 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2617 typename iterator_traits<_BidirectionalIterator>::value_type, 2618 typename iterator_traits<_BidirectionalIterator>::value_type>) 2619 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 2620 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 2621 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2622 2623 std::__inplace_merge(__first, __middle, __last, 2624 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2625 } 2626 2627 2628 /// This is a helper function for the __merge_sort_loop routines. 2629 template<typename _InputIterator, typename _OutputIterator, 2630 typename _Compare> 2631 _OutputIterator 2632 __move_merge(_InputIterator __first1, _InputIterator __last1, 2633 _InputIterator __first2, _InputIterator __last2, 2634 _OutputIterator __result, _Compare __comp) 2635 { 2636 while (__first1 != __last1 && __first2 != __last2) 2637 { 2638 if (__comp(__first2, __first1)) 2639 { 2640 *__result = _GLIBCXX_MOVE(*__first2); 2641 ++__first2; 2642 } 2643 else 2644 { 2645 *__result = _GLIBCXX_MOVE(*__first1); 2646 ++__first1; 2647 } 2648 ++__result; 2649 } 2650 return _GLIBCXX_MOVE3(__first2, __last2, 2651 _GLIBCXX_MOVE3(__first1, __last1, 2652 __result)); 2653 } 2654 2655 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 2656 typename _Distance, typename _Compare> 2657 void 2658 __merge_sort_loop(_RandomAccessIterator1 __first, 2659 _RandomAccessIterator1 __last, 2660 _RandomAccessIterator2 __result, _Distance __step_size, 2661 _Compare __comp) 2662 { 2663 const _Distance __two_step = 2 * __step_size; 2664 2665 while (__last - __first >= __two_step) 2666 { 2667 __result = std::__move_merge(__first, __first + __step_size, 2668 __first + __step_size, 2669 __first + __two_step, 2670 __result, __comp); 2671 __first += __two_step; 2672 } 2673 __step_size = std::min(_Distance(__last - __first), __step_size); 2674 2675 std::__move_merge(__first, __first + __step_size, 2676 __first + __step_size, __last, __result, __comp); 2677 } 2678 2679 template<typename _RandomAccessIterator, typename _Distance, 2680 typename _Compare> 2681 _GLIBCXX20_CONSTEXPR 2682 void 2683 __chunk_insertion_sort(_RandomAccessIterator __first, 2684 _RandomAccessIterator __last, 2685 _Distance __chunk_size, _Compare __comp) 2686 { 2687 while (__last - __first >= __chunk_size) 2688 { 2689 std::__insertion_sort(__first, __first + __chunk_size, __comp); 2690 __first += __chunk_size; 2691 } 2692 std::__insertion_sort(__first, __last, __comp); 2693 } 2694 2695 enum { _S_chunk_size = 7 }; 2696 2697 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 2698 void 2699 __merge_sort_with_buffer(_RandomAccessIterator __first, 2700 _RandomAccessIterator __last, 2701 _Pointer __buffer, _Compare __comp) 2702 { 2703 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2704 _Distance; 2705 2706 const _Distance __len = __last - __first; 2707 const _Pointer __buffer_last = __buffer + __len; 2708 2709 _Distance __step_size = _S_chunk_size; 2710 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 2711 2712 while (__step_size < __len) 2713 { 2714 std::__merge_sort_loop(__first, __last, __buffer, 2715 __step_size, __comp); 2716 __step_size *= 2; 2717 std::__merge_sort_loop(__buffer, __buffer_last, __first, 2718 __step_size, __comp); 2719 __step_size *= 2; 2720 } 2721 } 2722 2723 template<typename _RandomAccessIterator, typename _Pointer, 2724 typename _Distance, typename _Compare> 2725 void 2726 __stable_sort_adaptive(_RandomAccessIterator __first, 2727 _RandomAccessIterator __last, 2728 _Pointer __buffer, _Distance __buffer_size, 2729 _Compare __comp) 2730 { 2731 const _Distance __len = (__last - __first + 1) / 2; 2732 const _RandomAccessIterator __middle = __first + __len; 2733 if (__len > __buffer_size) 2734 { 2735 std::__stable_sort_adaptive(__first, __middle, __buffer, 2736 __buffer_size, __comp); 2737 std::__stable_sort_adaptive(__middle, __last, __buffer, 2738 __buffer_size, __comp); 2739 } 2740 else 2741 { 2742 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 2743 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 2744 } 2745 2746 std::__merge_adaptive(__first, __middle, __last, 2747 _Distance(__middle - __first), 2748 _Distance(__last - __middle), 2749 __buffer, __buffer_size, 2750 __comp); 2751 } 2752 2753 /// This is a helper function for the stable sorting routines. 2754 template<typename _RandomAccessIterator, typename _Compare> 2755 void 2756 __inplace_stable_sort(_RandomAccessIterator __first, 2757 _RandomAccessIterator __last, _Compare __comp) 2758 { 2759 if (__last - __first < 15) 2760 { 2761 std::__insertion_sort(__first, __last, __comp); 2762 return; 2763 } 2764 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 2765 std::__inplace_stable_sort(__first, __middle, __comp); 2766 std::__inplace_stable_sort(__middle, __last, __comp); 2767 std::__merge_without_buffer(__first, __middle, __last, 2768 __middle - __first, 2769 __last - __middle, 2770 __comp); 2771 } 2772 2773 // stable_sort 2774 2775 // Set algorithms: includes, set_union, set_intersection, set_difference, 2776 // set_symmetric_difference. All of these algorithms have the precondition 2777 // that their input ranges are sorted and the postcondition that their output 2778 // ranges are sorted. 2779 2780 template<typename _InputIterator1, typename _InputIterator2, 2781 typename _Compare> 2782 _GLIBCXX20_CONSTEXPR 2783 bool 2784 __includes(_InputIterator1 __first1, _InputIterator1 __last1, 2785 _InputIterator2 __first2, _InputIterator2 __last2, 2786 _Compare __comp) 2787 { 2788 while (__first1 != __last1 && __first2 != __last2) 2789 { 2790 if (__comp(__first2, __first1)) 2791 return false; 2792 if (!__comp(__first1, __first2)) 2793 ++__first2; 2794 ++__first1; 2795 } 2796 2797 return __first2 == __last2; 2798 } 2799 2800 /** 2801 * @brief Determines whether all elements of a sequence exists in a range. 2802 * @param __first1 Start of search range. 2803 * @param __last1 End of search range. 2804 * @param __first2 Start of sequence 2805 * @param __last2 End of sequence. 2806 * @return True if each element in [__first2,__last2) is contained in order 2807 * within [__first1,__last1). False otherwise. 2808 * @ingroup set_algorithms 2809 * 2810 * This operation expects both [__first1,__last1) and 2811 * [__first2,__last2) to be sorted. Searches for the presence of 2812 * each element in [__first2,__last2) within [__first1,__last1). 2813 * The iterators over each range only move forward, so this is a 2814 * linear algorithm. If an element in [__first2,__last2) is not 2815 * found before the search iterator reaches @p __last2, false is 2816 * returned. 2817 */ 2818 template<typename _InputIterator1, typename _InputIterator2> 2819 _GLIBCXX20_CONSTEXPR 2820 inline bool 2821 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2822 _InputIterator2 __first2, _InputIterator2 __last2) 2823 { 2824 // concept requirements 2825 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2826 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2827 __glibcxx_function_requires(_LessThanOpConcept< 2828 typename iterator_traits<_InputIterator1>::value_type, 2829 typename iterator_traits<_InputIterator2>::value_type>) 2830 __glibcxx_function_requires(_LessThanOpConcept< 2831 typename iterator_traits<_InputIterator2>::value_type, 2832 typename iterator_traits<_InputIterator1>::value_type>) 2833 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 2834 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 2835 __glibcxx_requires_irreflexive2(__first1, __last1); 2836 __glibcxx_requires_irreflexive2(__first2, __last2); 2837 2838 return std::__includes(__first1, __last1, __first2, __last2, 2839 __gnu_cxx::__ops::__iter_less_iter()); 2840 } 2841 2842 /** 2843 * @brief Determines whether all elements of a sequence exists in a range 2844 * using comparison. 2845 * @ingroup set_algorithms 2846 * @param __first1 Start of search range. 2847 * @param __last1 End of search range. 2848 * @param __first2 Start of sequence 2849 * @param __last2 End of sequence. 2850 * @param __comp Comparison function to use. 2851 * @return True if each element in [__first2,__last2) is contained 2852 * in order within [__first1,__last1) according to comp. False 2853 * otherwise. @ingroup set_algorithms 2854 * 2855 * This operation expects both [__first1,__last1) and 2856 * [__first2,__last2) to be sorted. Searches for the presence of 2857 * each element in [__first2,__last2) within [__first1,__last1), 2858 * using comp to decide. The iterators over each range only move 2859 * forward, so this is a linear algorithm. If an element in 2860 * [__first2,__last2) is not found before the search iterator 2861 * reaches @p __last2, false is returned. 2862 */ 2863 template<typename _InputIterator1, typename _InputIterator2, 2864 typename _Compare> 2865 _GLIBCXX20_CONSTEXPR 2866 inline bool 2867 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2868 _InputIterator2 __first2, _InputIterator2 __last2, 2869 _Compare __comp) 2870 { 2871 // concept requirements 2872 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2873 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2874 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2875 typename iterator_traits<_InputIterator1>::value_type, 2876 typename iterator_traits<_InputIterator2>::value_type>) 2877 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2878 typename iterator_traits<_InputIterator2>::value_type, 2879 typename iterator_traits<_InputIterator1>::value_type>) 2880 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 2881 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 2882 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 2883 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 2884 2885 return std::__includes(__first1, __last1, __first2, __last2, 2886 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2887 } 2888 2889 // nth_element 2890 // merge 2891 // set_difference 2892 // set_intersection 2893 // set_union 2894 // stable_sort 2895 // set_symmetric_difference 2896 // min_element 2897 // max_element 2898 2899 template<typename _BidirectionalIterator, typename _Compare> 2900 _GLIBCXX20_CONSTEXPR 2901 bool 2902 __next_permutation(_BidirectionalIterator __first, 2903 _BidirectionalIterator __last, _Compare __comp) 2904 { 2905 if (__first == __last) 2906 return false; 2907 _BidirectionalIterator __i = __first; 2908 ++__i; 2909 if (__i == __last) 2910 return false; 2911 __i = __last; 2912 --__i; 2913 2914 for(;;) 2915 { 2916 _BidirectionalIterator __ii = __i; 2917 --__i; 2918 if (__comp(__i, __ii)) 2919 { 2920 _BidirectionalIterator __j = __last; 2921 while (!__comp(__i, --__j)) 2922 {} 2923 std::iter_swap(__i, __j); 2924 std::__reverse(__ii, __last, 2925 std::__iterator_category(__first)); 2926 return true; 2927 } 2928 if (__i == __first) 2929 { 2930 std::__reverse(__first, __last, 2931 std::__iterator_category(__first)); 2932 return false; 2933 } 2934 } 2935 } 2936 2937 /** 2938 * @brief Permute range into the next @e dictionary ordering. 2939 * @ingroup sorting_algorithms 2940 * @param __first Start of range. 2941 * @param __last End of range. 2942 * @return False if wrapped to first permutation, true otherwise. 2943 * 2944 * Treats all permutations of the range as a set of @e dictionary sorted 2945 * sequences. Permutes the current sequence into the next one of this set. 2946 * Returns true if there are more sequences to generate. If the sequence 2947 * is the largest of the set, the smallest is generated and false returned. 2948 */ 2949 template<typename _BidirectionalIterator> 2950 _GLIBCXX20_CONSTEXPR 2951 inline bool 2952 next_permutation(_BidirectionalIterator __first, 2953 _BidirectionalIterator __last) 2954 { 2955 // concept requirements 2956 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2957 _BidirectionalIterator>) 2958 __glibcxx_function_requires(_LessThanComparableConcept< 2959 typename iterator_traits<_BidirectionalIterator>::value_type>) 2960 __glibcxx_requires_valid_range(__first, __last); 2961 __glibcxx_requires_irreflexive(__first, __last); 2962 2963 return std::__next_permutation 2964 (__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 2965 } 2966 2967 /** 2968 * @brief Permute range into the next @e dictionary ordering using 2969 * comparison functor. 2970 * @ingroup sorting_algorithms 2971 * @param __first Start of range. 2972 * @param __last End of range. 2973 * @param __comp A comparison functor. 2974 * @return False if wrapped to first permutation, true otherwise. 2975 * 2976 * Treats all permutations of the range [__first,__last) as a set of 2977 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 2978 * sequence into the next one of this set. Returns true if there are more 2979 * sequences to generate. If the sequence is the largest of the set, the 2980 * smallest is generated and false returned. 2981 */ 2982 template<typename _BidirectionalIterator, typename _Compare> 2983 _GLIBCXX20_CONSTEXPR 2984 inline bool 2985 next_permutation(_BidirectionalIterator __first, 2986 _BidirectionalIterator __last, _Compare __comp) 2987 { 2988 // concept requirements 2989 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2990 _BidirectionalIterator>) 2991 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2992 typename iterator_traits<_BidirectionalIterator>::value_type, 2993 typename iterator_traits<_BidirectionalIterator>::value_type>) 2994 __glibcxx_requires_valid_range(__first, __last); 2995 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2996 2997 return std::__next_permutation 2998 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2999 } 3000 3001 template<typename _BidirectionalIterator, typename _Compare> 3002 _GLIBCXX20_CONSTEXPR 3003 bool 3004 __prev_permutation(_BidirectionalIterator __first, 3005 _BidirectionalIterator __last, _Compare __comp) 3006 { 3007 if (__first == __last) 3008 return false; 3009 _BidirectionalIterator __i = __first; 3010 ++__i; 3011 if (__i == __last) 3012 return false; 3013 __i = __last; 3014 --__i; 3015 3016 for(;;) 3017 { 3018 _BidirectionalIterator __ii = __i; 3019 --__i; 3020 if (__comp(__ii, __i)) 3021 { 3022 _BidirectionalIterator __j = __last; 3023 while (!__comp(--__j, __i)) 3024 {} 3025 std::iter_swap(__i, __j); 3026 std::__reverse(__ii, __last, 3027 std::__iterator_category(__first)); 3028 return true; 3029 } 3030 if (__i == __first) 3031 { 3032 std::__reverse(__first, __last, 3033 std::__iterator_category(__first)); 3034 return false; 3035 } 3036 } 3037 } 3038 3039 /** 3040 * @brief Permute range into the previous @e dictionary ordering. 3041 * @ingroup sorting_algorithms 3042 * @param __first Start of range. 3043 * @param __last End of range. 3044 * @return False if wrapped to last permutation, true otherwise. 3045 * 3046 * Treats all permutations of the range as a set of @e dictionary sorted 3047 * sequences. Permutes the current sequence into the previous one of this 3048 * set. Returns true if there are more sequences to generate. If the 3049 * sequence is the smallest of the set, the largest is generated and false 3050 * returned. 3051 */ 3052 template<typename _BidirectionalIterator> 3053 _GLIBCXX20_CONSTEXPR 3054 inline bool 3055 prev_permutation(_BidirectionalIterator __first, 3056 _BidirectionalIterator __last) 3057 { 3058 // concept requirements 3059 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3060 _BidirectionalIterator>) 3061 __glibcxx_function_requires(_LessThanComparableConcept< 3062 typename iterator_traits<_BidirectionalIterator>::value_type>) 3063 __glibcxx_requires_valid_range(__first, __last); 3064 __glibcxx_requires_irreflexive(__first, __last); 3065 3066 return std::__prev_permutation(__first, __last, 3067 __gnu_cxx::__ops::__iter_less_iter()); 3068 } 3069 3070 /** 3071 * @brief Permute range into the previous @e dictionary ordering using 3072 * comparison functor. 3073 * @ingroup sorting_algorithms 3074 * @param __first Start of range. 3075 * @param __last End of range. 3076 * @param __comp A comparison functor. 3077 * @return False if wrapped to last permutation, true otherwise. 3078 * 3079 * Treats all permutations of the range [__first,__last) as a set of 3080 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 3081 * sequence into the previous one of this set. Returns true if there are 3082 * more sequences to generate. If the sequence is the smallest of the set, 3083 * the largest is generated and false returned. 3084 */ 3085 template<typename _BidirectionalIterator, typename _Compare> 3086 _GLIBCXX20_CONSTEXPR 3087 inline bool 3088 prev_permutation(_BidirectionalIterator __first, 3089 _BidirectionalIterator __last, _Compare __comp) 3090 { 3091 // concept requirements 3092 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3093 _BidirectionalIterator>) 3094 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3095 typename iterator_traits<_BidirectionalIterator>::value_type, 3096 typename iterator_traits<_BidirectionalIterator>::value_type>) 3097 __glibcxx_requires_valid_range(__first, __last); 3098 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3099 3100 return std::__prev_permutation(__first, __last, 3101 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3102 } 3103 3104 // replace 3105 // replace_if 3106 3107 template<typename _InputIterator, typename _OutputIterator, 3108 typename _Predicate, typename _Tp> 3109 _GLIBCXX20_CONSTEXPR 3110 _OutputIterator 3111 __replace_copy_if(_InputIterator __first, _InputIterator __last, 3112 _OutputIterator __result, 3113 _Predicate __pred, const _Tp& __new_value) 3114 { 3115 for (; __first != __last; ++__first, (void)++__result) 3116 if (__pred(__first)) 3117 *__result = __new_value; 3118 else 3119 *__result = *__first; 3120 return __result; 3121 } 3122 3123 /** 3124 * @brief Copy a sequence, replacing each element of one value with another 3125 * value. 3126 * @param __first An input iterator. 3127 * @param __last An input iterator. 3128 * @param __result An output iterator. 3129 * @param __old_value The value to be replaced. 3130 * @param __new_value The replacement value. 3131 * @return The end of the output sequence, @p result+(last-first). 3132 * 3133 * Copies each element in the input range @p [__first,__last) to the 3134 * output range @p [__result,__result+(__last-__first)) replacing elements 3135 * equal to @p __old_value with @p __new_value. 3136 */ 3137 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 3138 _GLIBCXX20_CONSTEXPR 3139 inline _OutputIterator 3140 replace_copy(_InputIterator __first, _InputIterator __last, 3141 _OutputIterator __result, 3142 const _Tp& __old_value, const _Tp& __new_value) 3143 { 3144 // concept requirements 3145 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3146 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3147 typename iterator_traits<_InputIterator>::value_type>) 3148 __glibcxx_function_requires(_EqualOpConcept< 3149 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3150 __glibcxx_requires_valid_range(__first, __last); 3151 3152 return std::__replace_copy_if(__first, __last, __result, 3153 __gnu_cxx::__ops::__iter_equals_val(__old_value), 3154 __new_value); 3155 } 3156 3157 /** 3158 * @brief Copy a sequence, replacing each value for which a predicate 3159 * returns true with another value. 3160 * @ingroup mutating_algorithms 3161 * @param __first An input iterator. 3162 * @param __last An input iterator. 3163 * @param __result An output iterator. 3164 * @param __pred A predicate. 3165 * @param __new_value The replacement value. 3166 * @return The end of the output sequence, @p __result+(__last-__first). 3167 * 3168 * Copies each element in the range @p [__first,__last) to the range 3169 * @p [__result,__result+(__last-__first)) replacing elements for which 3170 * @p __pred returns true with @p __new_value. 3171 */ 3172 template<typename _InputIterator, typename _OutputIterator, 3173 typename _Predicate, typename _Tp> 3174 _GLIBCXX20_CONSTEXPR 3175 inline _OutputIterator 3176 replace_copy_if(_InputIterator __first, _InputIterator __last, 3177 _OutputIterator __result, 3178 _Predicate __pred, const _Tp& __new_value) 3179 { 3180 // concept requirements 3181 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3182 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3183 typename iterator_traits<_InputIterator>::value_type>) 3184 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3185 typename iterator_traits<_InputIterator>::value_type>) 3186 __glibcxx_requires_valid_range(__first, __last); 3187 3188 return std::__replace_copy_if(__first, __last, __result, 3189 __gnu_cxx::__ops::__pred_iter(__pred), 3190 __new_value); 3191 } 3192 3193 #if __cplusplus >= 201103L 3194 /** 3195 * @brief Determines whether the elements of a sequence are sorted. 3196 * @ingroup sorting_algorithms 3197 * @param __first An iterator. 3198 * @param __last Another iterator. 3199 * @return True if the elements are sorted, false otherwise. 3200 */ 3201 template<typename _ForwardIterator> 3202 _GLIBCXX20_CONSTEXPR 3203 inline bool 3204 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3205 { return std::is_sorted_until(__first, __last) == __last; } 3206 3207 /** 3208 * @brief Determines whether the elements of a sequence are sorted 3209 * according to a comparison functor. 3210 * @ingroup sorting_algorithms 3211 * @param __first An iterator. 3212 * @param __last Another iterator. 3213 * @param __comp A comparison functor. 3214 * @return True if the elements are sorted, false otherwise. 3215 */ 3216 template<typename _ForwardIterator, typename _Compare> 3217 _GLIBCXX20_CONSTEXPR 3218 inline bool 3219 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 3220 _Compare __comp) 3221 { return std::is_sorted_until(__first, __last, __comp) == __last; } 3222 3223 template<typename _ForwardIterator, typename _Compare> 3224 _GLIBCXX20_CONSTEXPR 3225 _ForwardIterator 3226 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3227 _Compare __comp) 3228 { 3229 if (__first == __last) 3230 return __last; 3231 3232 _ForwardIterator __next = __first; 3233 for (++__next; __next != __last; __first = __next, (void)++__next) 3234 if (__comp(__next, __first)) 3235 return __next; 3236 return __next; 3237 } 3238 3239 /** 3240 * @brief Determines the end of a sorted sequence. 3241 * @ingroup sorting_algorithms 3242 * @param __first An iterator. 3243 * @param __last Another iterator. 3244 * @return An iterator pointing to the last iterator i in [__first, __last) 3245 * for which the range [__first, i) is sorted. 3246 */ 3247 template<typename _ForwardIterator> 3248 _GLIBCXX20_CONSTEXPR 3249 inline _ForwardIterator 3250 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3251 { 3252 // concept requirements 3253 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3254 __glibcxx_function_requires(_LessThanComparableConcept< 3255 typename iterator_traits<_ForwardIterator>::value_type>) 3256 __glibcxx_requires_valid_range(__first, __last); 3257 __glibcxx_requires_irreflexive(__first, __last); 3258 3259 return std::__is_sorted_until(__first, __last, 3260 __gnu_cxx::__ops::__iter_less_iter()); 3261 } 3262 3263 /** 3264 * @brief Determines the end of a sorted sequence using comparison functor. 3265 * @ingroup sorting_algorithms 3266 * @param __first An iterator. 3267 * @param __last Another iterator. 3268 * @param __comp A comparison functor. 3269 * @return An iterator pointing to the last iterator i in [__first, __last) 3270 * for which the range [__first, i) is sorted. 3271 */ 3272 template<typename _ForwardIterator, typename _Compare> 3273 _GLIBCXX20_CONSTEXPR 3274 inline _ForwardIterator 3275 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3276 _Compare __comp) 3277 { 3278 // concept requirements 3279 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3280 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3281 typename iterator_traits<_ForwardIterator>::value_type, 3282 typename iterator_traits<_ForwardIterator>::value_type>) 3283 __glibcxx_requires_valid_range(__first, __last); 3284 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3285 3286 return std::__is_sorted_until(__first, __last, 3287 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3288 } 3289 3290 /** 3291 * @brief Determines min and max at once as an ordered pair. 3292 * @ingroup sorting_algorithms 3293 * @param __a A thing of arbitrary type. 3294 * @param __b Another thing of arbitrary type. 3295 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 3296 * __b) otherwise. 3297 */ 3298 template<typename _Tp> 3299 _GLIBCXX14_CONSTEXPR 3300 inline pair<const _Tp&, const _Tp&> 3301 minmax(const _Tp& __a, const _Tp& __b) 3302 { 3303 // concept requirements 3304 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 3305 3306 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a) 3307 : pair<const _Tp&, const _Tp&>(__a, __b); 3308 } 3309 3310 /** 3311 * @brief Determines min and max at once as an ordered pair. 3312 * @ingroup sorting_algorithms 3313 * @param __a A thing of arbitrary type. 3314 * @param __b Another thing of arbitrary type. 3315 * @param __comp A @link comparison_functors comparison functor @endlink. 3316 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 3317 * __b) otherwise. 3318 */ 3319 template<typename _Tp, typename _Compare> 3320 _GLIBCXX14_CONSTEXPR 3321 inline pair<const _Tp&, const _Tp&> 3322 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 3323 { 3324 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) 3325 : pair<const _Tp&, const _Tp&>(__a, __b); 3326 } 3327 3328 template<typename _ForwardIterator, typename _Compare> 3329 _GLIBCXX14_CONSTEXPR 3330 pair<_ForwardIterator, _ForwardIterator> 3331 __minmax_element(_ForwardIterator __first, _ForwardIterator __last, 3332 _Compare __comp) 3333 { 3334 _ForwardIterator __next = __first; 3335 if (__first == __last 3336 || ++__next == __last) 3337 return std::make_pair(__first, __first); 3338 3339 _ForwardIterator __min{}, __max{}; 3340 if (__comp(__next, __first)) 3341 { 3342 __min = __next; 3343 __max = __first; 3344 } 3345 else 3346 { 3347 __min = __first; 3348 __max = __next; 3349 } 3350 3351 __first = __next; 3352 ++__first; 3353 3354 while (__first != __last) 3355 { 3356 __next = __first; 3357 if (++__next == __last) 3358 { 3359 if (__comp(__first, __min)) 3360 __min = __first; 3361 else if (!__comp(__first, __max)) 3362 __max = __first; 3363 break; 3364 } 3365 3366 if (__comp(__next, __first)) 3367 { 3368 if (__comp(__next, __min)) 3369 __min = __next; 3370 if (!__comp(__first, __max)) 3371 __max = __first; 3372 } 3373 else 3374 { 3375 if (__comp(__first, __min)) 3376 __min = __first; 3377 if (!__comp(__next, __max)) 3378 __max = __next; 3379 } 3380 3381 __first = __next; 3382 ++__first; 3383 } 3384 3385 return std::make_pair(__min, __max); 3386 } 3387 3388 /** 3389 * @brief Return a pair of iterators pointing to the minimum and maximum 3390 * elements in a range. 3391 * @ingroup sorting_algorithms 3392 * @param __first Start of range. 3393 * @param __last End of range. 3394 * @return make_pair(m, M), where m is the first iterator i in 3395 * [__first, __last) such that no other element in the range is 3396 * smaller, and where M is the last iterator i in [__first, __last) 3397 * such that no other element in the range is larger. 3398 */ 3399 template<typename _ForwardIterator> 3400 _GLIBCXX14_CONSTEXPR 3401 inline pair<_ForwardIterator, _ForwardIterator> 3402 minmax_element(_ForwardIterator __first, _ForwardIterator __last) 3403 { 3404 // concept requirements 3405 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3406 __glibcxx_function_requires(_LessThanComparableConcept< 3407 typename iterator_traits<_ForwardIterator>::value_type>) 3408 __glibcxx_requires_valid_range(__first, __last); 3409 __glibcxx_requires_irreflexive(__first, __last); 3410 3411 return std::__minmax_element(__first, __last, 3412 __gnu_cxx::__ops::__iter_less_iter()); 3413 } 3414 3415 /** 3416 * @brief Return a pair of iterators pointing to the minimum and maximum 3417 * elements in a range. 3418 * @ingroup sorting_algorithms 3419 * @param __first Start of range. 3420 * @param __last End of range. 3421 * @param __comp Comparison functor. 3422 * @return make_pair(m, M), where m is the first iterator i in 3423 * [__first, __last) such that no other element in the range is 3424 * smaller, and where M is the last iterator i in [__first, __last) 3425 * such that no other element in the range is larger. 3426 */ 3427 template<typename _ForwardIterator, typename _Compare> 3428 _GLIBCXX14_CONSTEXPR 3429 inline pair<_ForwardIterator, _ForwardIterator> 3430 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 3431 _Compare __comp) 3432 { 3433 // concept requirements 3434 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3435 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3436 typename iterator_traits<_ForwardIterator>::value_type, 3437 typename iterator_traits<_ForwardIterator>::value_type>) 3438 __glibcxx_requires_valid_range(__first, __last); 3439 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3440 3441 return std::__minmax_element(__first, __last, 3442 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3443 } 3444 3445 // N2722 + DR 915. 3446 template<typename _Tp> 3447 _GLIBCXX14_CONSTEXPR 3448 inline _Tp 3449 min(initializer_list<_Tp> __l) 3450 { return *std::min_element(__l.begin(), __l.end()); } 3451 3452 template<typename _Tp, typename _Compare> 3453 _GLIBCXX14_CONSTEXPR 3454 inline _Tp 3455 min(initializer_list<_Tp> __l, _Compare __comp) 3456 { return *std::min_element(__l.begin(), __l.end(), __comp); } 3457 3458 template<typename _Tp> 3459 _GLIBCXX14_CONSTEXPR 3460 inline _Tp 3461 max(initializer_list<_Tp> __l) 3462 { return *std::max_element(__l.begin(), __l.end()); } 3463 3464 template<typename _Tp, typename _Compare> 3465 _GLIBCXX14_CONSTEXPR 3466 inline _Tp 3467 max(initializer_list<_Tp> __l, _Compare __comp) 3468 { return *std::max_element(__l.begin(), __l.end(), __comp); } 3469 3470 template<typename _Tp> 3471 _GLIBCXX14_CONSTEXPR 3472 inline pair<_Tp, _Tp> 3473 minmax(initializer_list<_Tp> __l) 3474 { 3475 pair<const _Tp*, const _Tp*> __p = 3476 std::minmax_element(__l.begin(), __l.end()); 3477 return std::make_pair(*__p.first, *__p.second); 3478 } 3479 3480 template<typename _Tp, typename _Compare> 3481 _GLIBCXX14_CONSTEXPR 3482 inline pair<_Tp, _Tp> 3483 minmax(initializer_list<_Tp> __l, _Compare __comp) 3484 { 3485 pair<const _Tp*, const _Tp*> __p = 3486 std::minmax_element(__l.begin(), __l.end(), __comp); 3487 return std::make_pair(*__p.first, *__p.second); 3488 } 3489 3490 /** 3491 * @brief Checks whether a permutation of the second sequence is equal 3492 * to the first sequence. 3493 * @ingroup non_mutating_algorithms 3494 * @param __first1 Start of first range. 3495 * @param __last1 End of first range. 3496 * @param __first2 Start of second range. 3497 * @param __pred A binary predicate. 3498 * @return true if there exists a permutation of the elements in 3499 * the range [__first2, __first2 + (__last1 - __first1)), 3500 * beginning with ForwardIterator2 begin, such that 3501 * equal(__first1, __last1, __begin, __pred) returns true; 3502 * otherwise, returns false. 3503 */ 3504 template<typename _ForwardIterator1, typename _ForwardIterator2, 3505 typename _BinaryPredicate> 3506 _GLIBCXX20_CONSTEXPR 3507 inline bool 3508 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3509 _ForwardIterator2 __first2, _BinaryPredicate __pred) 3510 { 3511 // concept requirements 3512 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 3513 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 3514 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3515 typename iterator_traits<_ForwardIterator1>::value_type, 3516 typename iterator_traits<_ForwardIterator2>::value_type>) 3517 __glibcxx_requires_valid_range(__first1, __last1); 3518 3519 return std::__is_permutation(__first1, __last1, __first2, 3520 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3521 } 3522 3523 #if __cplusplus > 201103L 3524 template<typename _ForwardIterator1, typename _ForwardIterator2, 3525 typename _BinaryPredicate> 3526 _GLIBCXX20_CONSTEXPR 3527 bool 3528 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3529 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3530 _BinaryPredicate __pred) 3531 { 3532 using _Cat1 3533 = typename iterator_traits<_ForwardIterator1>::iterator_category; 3534 using _Cat2 3535 = typename iterator_traits<_ForwardIterator2>::iterator_category; 3536 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; 3537 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; 3538 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA(); 3539 if (__ra_iters) 3540 { 3541 auto __d1 = std::distance(__first1, __last1); 3542 auto __d2 = std::distance(__first2, __last2); 3543 if (__d1 != __d2) 3544 return false; 3545 } 3546 3547 // Efficiently compare identical prefixes: O(N) if sequences 3548 // have the same elements in the same order. 3549 for (; __first1 != __last1 && __first2 != __last2; 3550 ++__first1, (void)++__first2) 3551 if (!__pred(__first1, __first2)) 3552 break; 3553 3554 if (__ra_iters) 3555 { 3556 if (__first1 == __last1) 3557 return true; 3558 } 3559 else 3560 { 3561 auto __d1 = std::distance(__first1, __last1); 3562 auto __d2 = std::distance(__first2, __last2); 3563 if (__d1 == 0 && __d2 == 0) 3564 return true; 3565 if (__d1 != __d2) 3566 return false; 3567 } 3568 3569 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 3570 { 3571 if (__scan != std::__find_if(__first1, __scan, 3572 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 3573 continue; // We've seen this one before. 3574 3575 auto __matches = std::__count_if(__first2, __last2, 3576 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 3577 if (0 == __matches 3578 || std::__count_if(__scan, __last1, 3579 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 3580 != __matches) 3581 return false; 3582 } 3583 return true; 3584 } 3585 3586 /** 3587 * @brief Checks whether a permutaion of the second sequence is equal 3588 * to the first sequence. 3589 * @ingroup non_mutating_algorithms 3590 * @param __first1 Start of first range. 3591 * @param __last1 End of first range. 3592 * @param __first2 Start of second range. 3593 * @param __last2 End of first range. 3594 * @return true if there exists a permutation of the elements in the range 3595 * [__first2, __last2), beginning with ForwardIterator2 begin, 3596 * such that equal(__first1, __last1, begin) returns true; 3597 * otherwise, returns false. 3598 */ 3599 template<typename _ForwardIterator1, typename _ForwardIterator2> 3600 _GLIBCXX20_CONSTEXPR 3601 inline bool 3602 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3603 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 3604 { 3605 __glibcxx_requires_valid_range(__first1, __last1); 3606 __glibcxx_requires_valid_range(__first2, __last2); 3607 3608 return 3609 std::__is_permutation(__first1, __last1, __first2, __last2, 3610 __gnu_cxx::__ops::__iter_equal_to_iter()); 3611 } 3612 3613 /** 3614 * @brief Checks whether a permutation of the second sequence is equal 3615 * to the first sequence. 3616 * @ingroup non_mutating_algorithms 3617 * @param __first1 Start of first range. 3618 * @param __last1 End of first range. 3619 * @param __first2 Start of second range. 3620 * @param __last2 End of first range. 3621 * @param __pred A binary predicate. 3622 * @return true if there exists a permutation of the elements in the range 3623 * [__first2, __last2), beginning with ForwardIterator2 begin, 3624 * such that equal(__first1, __last1, __begin, __pred) returns true; 3625 * otherwise, returns false. 3626 */ 3627 template<typename _ForwardIterator1, typename _ForwardIterator2, 3628 typename _BinaryPredicate> 3629 _GLIBCXX20_CONSTEXPR 3630 inline bool 3631 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3632 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3633 _BinaryPredicate __pred) 3634 { 3635 __glibcxx_requires_valid_range(__first1, __last1); 3636 __glibcxx_requires_valid_range(__first2, __last2); 3637 3638 return std::__is_permutation(__first1, __last1, __first2, __last2, 3639 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3640 } 3641 3642 #if __cplusplus > 201402L 3643 3644 #define __cpp_lib_clamp 201603 3645 3646 /** 3647 * @brief Returns the value clamped between lo and hi. 3648 * @ingroup sorting_algorithms 3649 * @param __val A value of arbitrary type. 3650 * @param __lo A lower limit of arbitrary type. 3651 * @param __hi An upper limit of arbitrary type. 3652 * @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise. 3653 */ 3654 template<typename _Tp> 3655 constexpr const _Tp& 3656 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi) 3657 { 3658 __glibcxx_assert(!(__hi < __lo)); 3659 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val; 3660 } 3661 3662 /** 3663 * @brief Returns the value clamped between lo and hi. 3664 * @ingroup sorting_algorithms 3665 * @param __val A value of arbitrary type. 3666 * @param __lo A lower limit of arbitrary type. 3667 * @param __hi An upper limit of arbitrary type. 3668 * @param __comp A comparison functor. 3669 * @return max(__val, __lo, __comp) if __comp(__val, __hi) 3670 * or min(__val, __hi, __comp) otherwise. 3671 */ 3672 template<typename _Tp, typename _Compare> 3673 constexpr const _Tp& 3674 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp) 3675 { 3676 __glibcxx_assert(!__comp(__hi, __lo)); 3677 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val; 3678 } 3679 #endif // C++17 3680 #endif // C++14 3681 3682 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3683 /** 3684 * @brief Generate two uniformly distributed integers using a 3685 * single distribution invocation. 3686 * @param __b0 The upper bound for the first integer. 3687 * @param __b1 The upper bound for the second integer. 3688 * @param __g A UniformRandomBitGenerator. 3689 * @return A pair (i, j) with i and j uniformly distributed 3690 * over [0, __b0) and [0, __b1), respectively. 3691 * 3692 * Requires: __b0 * __b1 <= __g.max() - __g.min(). 3693 * 3694 * Using uniform_int_distribution with a range that is very 3695 * small relative to the range of the generator ends up wasting 3696 * potentially expensively generated randomness, since 3697 * uniform_int_distribution does not store leftover randomness 3698 * between invocations. 3699 * 3700 * If we know we want two integers in ranges that are sufficiently 3701 * small, we can compose the ranges, use a single distribution 3702 * invocation, and significantly reduce the waste. 3703 */ 3704 template<typename _IntType, typename _UniformRandomBitGenerator> 3705 pair<_IntType, _IntType> 3706 __gen_two_uniform_ints(_IntType __b0, _IntType __b1, 3707 _UniformRandomBitGenerator&& __g) 3708 { 3709 _IntType __x 3710 = uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g); 3711 return std::make_pair(__x / __b1, __x % __b1); 3712 } 3713 3714 /** 3715 * @brief Shuffle the elements of a sequence using a uniform random 3716 * number generator. 3717 * @ingroup mutating_algorithms 3718 * @param __first A forward iterator. 3719 * @param __last A forward iterator. 3720 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 3721 * @return Nothing. 3722 * 3723 * Reorders the elements in the range @p [__first,__last) using @p __g to 3724 * provide random numbers. 3725 */ 3726 template<typename _RandomAccessIterator, 3727 typename _UniformRandomNumberGenerator> 3728 void 3729 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3730 _UniformRandomNumberGenerator&& __g) 3731 { 3732 // concept requirements 3733 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3734 _RandomAccessIterator>) 3735 __glibcxx_requires_valid_range(__first, __last); 3736 3737 if (__first == __last) 3738 return; 3739 3740 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3741 _DistanceType; 3742 3743 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 3744 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 3745 typedef typename __distr_type::param_type __p_type; 3746 3747 typedef typename remove_reference<_UniformRandomNumberGenerator>::type 3748 _Gen; 3749 typedef typename common_type<typename _Gen::result_type, __ud_type>::type 3750 __uc_type; 3751 3752 const __uc_type __urngrange = __g.max() - __g.min(); 3753 const __uc_type __urange = __uc_type(__last - __first); 3754 3755 if (__urngrange / __urange >= __urange) 3756 // I.e. (__urngrange >= __urange * __urange) but without wrap issues. 3757 { 3758 _RandomAccessIterator __i = __first + 1; 3759 3760 // Since we know the range isn't empty, an even number of elements 3761 // means an uneven number of elements /to swap/, in which case we 3762 // do the first one up front: 3763 3764 if ((__urange % 2) == 0) 3765 { 3766 __distr_type __d{0, 1}; 3767 std::iter_swap(__i++, __first + __d(__g)); 3768 } 3769 3770 // Now we know that __last - __i is even, so we do the rest in pairs, 3771 // using a single distribution invocation to produce swap positions 3772 // for two successive elements at a time: 3773 3774 while (__i != __last) 3775 { 3776 const __uc_type __swap_range = __uc_type(__i - __first) + 1; 3777 3778 const pair<__uc_type, __uc_type> __pospos = 3779 __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g); 3780 3781 std::iter_swap(__i++, __first + __pospos.first); 3782 std::iter_swap(__i++, __first + __pospos.second); 3783 } 3784 3785 return; 3786 } 3787 3788 __distr_type __d; 3789 3790 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 3791 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 3792 } 3793 #endif 3794 3795 #endif // C++11 3796 3797 _GLIBCXX_BEGIN_NAMESPACE_ALGO 3798 3799 /** 3800 * @brief Apply a function to every element of a sequence. 3801 * @ingroup non_mutating_algorithms 3802 * @param __first An input iterator. 3803 * @param __last An input iterator. 3804 * @param __f A unary function object. 3805 * @return @p __f 3806 * 3807 * Applies the function object @p __f to each element in the range 3808 * @p [first,last). @p __f must not modify the order of the sequence. 3809 * If @p __f has a return value it is ignored. 3810 */ 3811 template<typename _InputIterator, typename _Function> 3812 _GLIBCXX20_CONSTEXPR 3813 _Function 3814 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 3815 { 3816 // concept requirements 3817 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3818 __glibcxx_requires_valid_range(__first, __last); 3819 for (; __first != __last; ++__first) 3820 __f(*__first); 3821 return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant. 3822 } 3823 3824 #if __cplusplus >= 201703L 3825 /** 3826 * @brief Apply a function to every element of a sequence. 3827 * @ingroup non_mutating_algorithms 3828 * @param __first An input iterator. 3829 * @param __n A value convertible to an integer. 3830 * @param __f A unary function object. 3831 * @return `__first+__n` 3832 * 3833 * Applies the function object `__f` to each element in the range 3834 * `[first, first+n)`. `__f` must not modify the order of the sequence. 3835 * If `__f` has a return value it is ignored. 3836 */ 3837 template<typename _InputIterator, typename _Size, typename _Function> 3838 _GLIBCXX20_CONSTEXPR 3839 _InputIterator 3840 for_each_n(_InputIterator __first, _Size __n, _Function __f) 3841 { 3842 auto __n2 = std::__size_to_integer(__n); 3843 using _Cat = typename iterator_traits<_InputIterator>::iterator_category; 3844 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>) 3845 { 3846 if (__n2 <= 0) 3847 return __first; 3848 auto __last = __first + __n2; 3849 std::for_each(__first, __last, std::move(__f)); 3850 return __last; 3851 } 3852 else 3853 { 3854 while (__n2-->0) 3855 { 3856 __f(*__first); 3857 ++__first; 3858 } 3859 return __first; 3860 } 3861 } 3862 #endif // C++17 3863 3864 /** 3865 * @brief Find the first occurrence of a value in a sequence. 3866 * @ingroup non_mutating_algorithms 3867 * @param __first An input iterator. 3868 * @param __last An input iterator. 3869 * @param __val The value to find. 3870 * @return The first iterator @c i in the range @p [__first,__last) 3871 * such that @c *i == @p __val, or @p __last if no such iterator exists. 3872 */ 3873 template<typename _InputIterator, typename _Tp> 3874 _GLIBCXX20_CONSTEXPR 3875 inline _InputIterator 3876 find(_InputIterator __first, _InputIterator __last, 3877 const _Tp& __val) 3878 { 3879 // concept requirements 3880 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3881 __glibcxx_function_requires(_EqualOpConcept< 3882 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3883 __glibcxx_requires_valid_range(__first, __last); 3884 return std::__find_if(__first, __last, 3885 __gnu_cxx::__ops::__iter_equals_val(__val)); 3886 } 3887 3888 /** 3889 * @brief Find the first element in a sequence for which a 3890 * predicate is true. 3891 * @ingroup non_mutating_algorithms 3892 * @param __first An input iterator. 3893 * @param __last An input iterator. 3894 * @param __pred A predicate. 3895 * @return The first iterator @c i in the range @p [__first,__last) 3896 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 3897 */ 3898 template<typename _InputIterator, typename _Predicate> 3899 _GLIBCXX20_CONSTEXPR 3900 inline _InputIterator 3901 find_if(_InputIterator __first, _InputIterator __last, 3902 _Predicate __pred) 3903 { 3904 // concept requirements 3905 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3906 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3907 typename iterator_traits<_InputIterator>::value_type>) 3908 __glibcxx_requires_valid_range(__first, __last); 3909 3910 return std::__find_if(__first, __last, 3911 __gnu_cxx::__ops::__pred_iter(__pred)); 3912 } 3913 3914 /** 3915 * @brief Find element from a set in a sequence. 3916 * @ingroup non_mutating_algorithms 3917 * @param __first1 Start of range to search. 3918 * @param __last1 End of range to search. 3919 * @param __first2 Start of match candidates. 3920 * @param __last2 End of match candidates. 3921 * @return The first iterator @c i in the range 3922 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 3923 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 3924 * 3925 * Searches the range @p [__first1,__last1) for an element that is 3926 * equal to some element in the range [__first2,__last2). If 3927 * found, returns an iterator in the range [__first1,__last1), 3928 * otherwise returns @p __last1. 3929 */ 3930 template<typename _InputIterator, typename _ForwardIterator> 3931 _GLIBCXX20_CONSTEXPR 3932 _InputIterator 3933 find_first_of(_InputIterator __first1, _InputIterator __last1, 3934 _ForwardIterator __first2, _ForwardIterator __last2) 3935 { 3936 // concept requirements 3937 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3938 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3939 __glibcxx_function_requires(_EqualOpConcept< 3940 typename iterator_traits<_InputIterator>::value_type, 3941 typename iterator_traits<_ForwardIterator>::value_type>) 3942 __glibcxx_requires_valid_range(__first1, __last1); 3943 __glibcxx_requires_valid_range(__first2, __last2); 3944 3945 for (; __first1 != __last1; ++__first1) 3946 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 3947 if (*__first1 == *__iter) 3948 return __first1; 3949 return __last1; 3950 } 3951 3952 /** 3953 * @brief Find element from a set in a sequence using a predicate. 3954 * @ingroup non_mutating_algorithms 3955 * @param __first1 Start of range to search. 3956 * @param __last1 End of range to search. 3957 * @param __first2 Start of match candidates. 3958 * @param __last2 End of match candidates. 3959 * @param __comp Predicate to use. 3960 * @return The first iterator @c i in the range 3961 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 3962 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 3963 * such iterator exists. 3964 * 3965 3966 * Searches the range @p [__first1,__last1) for an element that is 3967 * equal to some element in the range [__first2,__last2). If 3968 * found, returns an iterator in the range [__first1,__last1), 3969 * otherwise returns @p __last1. 3970 */ 3971 template<typename _InputIterator, typename _ForwardIterator, 3972 typename _BinaryPredicate> 3973 _GLIBCXX20_CONSTEXPR 3974 _InputIterator 3975 find_first_of(_InputIterator __first1, _InputIterator __last1, 3976 _ForwardIterator __first2, _ForwardIterator __last2, 3977 _BinaryPredicate __comp) 3978 { 3979 // concept requirements 3980 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3981 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3982 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3983 typename iterator_traits<_InputIterator>::value_type, 3984 typename iterator_traits<_ForwardIterator>::value_type>) 3985 __glibcxx_requires_valid_range(__first1, __last1); 3986 __glibcxx_requires_valid_range(__first2, __last2); 3987 3988 for (; __first1 != __last1; ++__first1) 3989 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 3990 if (__comp(*__first1, *__iter)) 3991 return __first1; 3992 return __last1; 3993 } 3994 3995 /** 3996 * @brief Find two adjacent values in a sequence that are equal. 3997 * @ingroup non_mutating_algorithms 3998 * @param __first A forward iterator. 3999 * @param __last A forward iterator. 4000 * @return The first iterator @c i such that @c i and @c i+1 are both 4001 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 4002 * or @p __last if no such iterator exists. 4003 */ 4004 template<typename _ForwardIterator> 4005 _GLIBCXX20_CONSTEXPR 4006 inline _ForwardIterator 4007 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 4008 { 4009 // concept requirements 4010 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4011 __glibcxx_function_requires(_EqualityComparableConcept< 4012 typename iterator_traits<_ForwardIterator>::value_type>) 4013 __glibcxx_requires_valid_range(__first, __last); 4014 4015 return std::__adjacent_find(__first, __last, 4016 __gnu_cxx::__ops::__iter_equal_to_iter()); 4017 } 4018 4019 /** 4020 * @brief Find two adjacent values in a sequence using a predicate. 4021 * @ingroup non_mutating_algorithms 4022 * @param __first A forward iterator. 4023 * @param __last A forward iterator. 4024 * @param __binary_pred A binary predicate. 4025 * @return The first iterator @c i such that @c i and @c i+1 are both 4026 * valid iterators in @p [__first,__last) and such that 4027 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 4028 * exists. 4029 */ 4030 template<typename _ForwardIterator, typename _BinaryPredicate> 4031 _GLIBCXX20_CONSTEXPR 4032 inline _ForwardIterator 4033 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 4034 _BinaryPredicate __binary_pred) 4035 { 4036 // concept requirements 4037 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4038 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4039 typename iterator_traits<_ForwardIterator>::value_type, 4040 typename iterator_traits<_ForwardIterator>::value_type>) 4041 __glibcxx_requires_valid_range(__first, __last); 4042 4043 return std::__adjacent_find(__first, __last, 4044 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 4045 } 4046 4047 /** 4048 * @brief Count the number of copies of a value in a sequence. 4049 * @ingroup non_mutating_algorithms 4050 * @param __first An input iterator. 4051 * @param __last An input iterator. 4052 * @param __value The value to be counted. 4053 * @return The number of iterators @c i in the range @p [__first,__last) 4054 * for which @c *i == @p __value 4055 */ 4056 template<typename _InputIterator, typename _Tp> 4057 _GLIBCXX20_CONSTEXPR 4058 inline typename iterator_traits<_InputIterator>::difference_type 4059 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 4060 { 4061 // concept requirements 4062 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4063 __glibcxx_function_requires(_EqualOpConcept< 4064 typename iterator_traits<_InputIterator>::value_type, _Tp>) 4065 __glibcxx_requires_valid_range(__first, __last); 4066 4067 return std::__count_if(__first, __last, 4068 __gnu_cxx::__ops::__iter_equals_val(__value)); 4069 } 4070 4071 /** 4072 * @brief Count the elements of a sequence for which a predicate is true. 4073 * @ingroup non_mutating_algorithms 4074 * @param __first An input iterator. 4075 * @param __last An input iterator. 4076 * @param __pred A predicate. 4077 * @return The number of iterators @c i in the range @p [__first,__last) 4078 * for which @p __pred(*i) is true. 4079 */ 4080 template<typename _InputIterator, typename _Predicate> 4081 _GLIBCXX20_CONSTEXPR 4082 inline typename iterator_traits<_InputIterator>::difference_type 4083 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 4084 { 4085 // concept requirements 4086 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4087 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4088 typename iterator_traits<_InputIterator>::value_type>) 4089 __glibcxx_requires_valid_range(__first, __last); 4090 4091 return std::__count_if(__first, __last, 4092 __gnu_cxx::__ops::__pred_iter(__pred)); 4093 } 4094 4095 /** 4096 * @brief Search a sequence for a matching sub-sequence. 4097 * @ingroup non_mutating_algorithms 4098 * @param __first1 A forward iterator. 4099 * @param __last1 A forward iterator. 4100 * @param __first2 A forward iterator. 4101 * @param __last2 A forward iterator. 4102 * @return The first iterator @c i in the range @p 4103 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 4104 * *(__first2+N) for each @c N in the range @p 4105 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 4106 * 4107 * Searches the range @p [__first1,__last1) for a sub-sequence that 4108 * compares equal value-by-value with the sequence given by @p 4109 * [__first2,__last2) and returns an iterator to the first element 4110 * of the sub-sequence, or @p __last1 if the sub-sequence is not 4111 * found. 4112 * 4113 * Because the sub-sequence must lie completely within the range @p 4114 * [__first1,__last1) it must start at a position less than @p 4115 * __last1-(__last2-__first2) where @p __last2-__first2 is the 4116 * length of the sub-sequence. 4117 * 4118 * This means that the returned iterator @c i will be in the range 4119 * @p [__first1,__last1-(__last2-__first2)) 4120 */ 4121 template<typename _ForwardIterator1, typename _ForwardIterator2> 4122 _GLIBCXX20_CONSTEXPR 4123 inline _ForwardIterator1 4124 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4125 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 4126 { 4127 // concept requirements 4128 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 4129 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 4130 __glibcxx_function_requires(_EqualOpConcept< 4131 typename iterator_traits<_ForwardIterator1>::value_type, 4132 typename iterator_traits<_ForwardIterator2>::value_type>) 4133 __glibcxx_requires_valid_range(__first1, __last1); 4134 __glibcxx_requires_valid_range(__first2, __last2); 4135 4136 return std::__search(__first1, __last1, __first2, __last2, 4137 __gnu_cxx::__ops::__iter_equal_to_iter()); 4138 } 4139 4140 /** 4141 * @brief Search a sequence for a matching sub-sequence using a predicate. 4142 * @ingroup non_mutating_algorithms 4143 * @param __first1 A forward iterator. 4144 * @param __last1 A forward iterator. 4145 * @param __first2 A forward iterator. 4146 * @param __last2 A forward iterator. 4147 * @param __predicate A binary predicate. 4148 * @return The first iterator @c i in the range 4149 * @p [__first1,__last1-(__last2-__first2)) such that 4150 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range 4151 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. 4152 * 4153 * Searches the range @p [__first1,__last1) for a sub-sequence that 4154 * compares equal value-by-value with the sequence given by @p 4155 * [__first2,__last2), using @p __predicate to determine equality, 4156 * and returns an iterator to the first element of the 4157 * sub-sequence, or @p __last1 if no such iterator exists. 4158 * 4159 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 4160 */ 4161 template<typename _ForwardIterator1, typename _ForwardIterator2, 4162 typename _BinaryPredicate> 4163 _GLIBCXX20_CONSTEXPR 4164 inline _ForwardIterator1 4165 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4166 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 4167 _BinaryPredicate __predicate) 4168 { 4169 // concept requirements 4170 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 4171 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 4172 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4173 typename iterator_traits<_ForwardIterator1>::value_type, 4174 typename iterator_traits<_ForwardIterator2>::value_type>) 4175 __glibcxx_requires_valid_range(__first1, __last1); 4176 __glibcxx_requires_valid_range(__first2, __last2); 4177 4178 return std::__search(__first1, __last1, __first2, __last2, 4179 __gnu_cxx::__ops::__iter_comp_iter(__predicate)); 4180 } 4181 4182 /** 4183 * @brief Search a sequence for a number of consecutive values. 4184 * @ingroup non_mutating_algorithms 4185 * @param __first A forward iterator. 4186 * @param __last A forward iterator. 4187 * @param __count The number of consecutive values. 4188 * @param __val The value to find. 4189 * @return The first iterator @c i in the range @p 4190 * [__first,__last-__count) such that @c *(i+N) == @p __val for 4191 * each @c N in the range @p [0,__count), or @p __last if no such 4192 * iterator exists. 4193 * 4194 * Searches the range @p [__first,__last) for @p count consecutive elements 4195 * equal to @p __val. 4196 */ 4197 template<typename _ForwardIterator, typename _Integer, typename _Tp> 4198 _GLIBCXX20_CONSTEXPR 4199 inline _ForwardIterator 4200 search_n(_ForwardIterator __first, _ForwardIterator __last, 4201 _Integer __count, const _Tp& __val) 4202 { 4203 // concept requirements 4204 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4205 __glibcxx_function_requires(_EqualOpConcept< 4206 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4207 __glibcxx_requires_valid_range(__first, __last); 4208 4209 return std::__search_n(__first, __last, __count, 4210 __gnu_cxx::__ops::__iter_equals_val(__val)); 4211 } 4212 4213 4214 /** 4215 * @brief Search a sequence for a number of consecutive values using a 4216 * predicate. 4217 * @ingroup non_mutating_algorithms 4218 * @param __first A forward iterator. 4219 * @param __last A forward iterator. 4220 * @param __count The number of consecutive values. 4221 * @param __val The value to find. 4222 * @param __binary_pred A binary predicate. 4223 * @return The first iterator @c i in the range @p 4224 * [__first,__last-__count) such that @p 4225 * __binary_pred(*(i+N),__val) is true for each @c N in the range 4226 * @p [0,__count), or @p __last if no such iterator exists. 4227 * 4228 * Searches the range @p [__first,__last) for @p __count 4229 * consecutive elements for which the predicate returns true. 4230 */ 4231 template<typename _ForwardIterator, typename _Integer, typename _Tp, 4232 typename _BinaryPredicate> 4233 _GLIBCXX20_CONSTEXPR 4234 inline _ForwardIterator 4235 search_n(_ForwardIterator __first, _ForwardIterator __last, 4236 _Integer __count, const _Tp& __val, 4237 _BinaryPredicate __binary_pred) 4238 { 4239 // concept requirements 4240 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4241 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4242 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4243 __glibcxx_requires_valid_range(__first, __last); 4244 4245 return std::__search_n(__first, __last, __count, 4246 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 4247 } 4248 4249 #if __cplusplus >= 201703L 4250 /** @brief Search a sequence using a Searcher object. 4251 * 4252 * @param __first A forward iterator. 4253 * @param __last A forward iterator. 4254 * @param __searcher A callable object. 4255 * @return @p __searcher(__first,__last).first 4256 */ 4257 template<typename _ForwardIterator, typename _Searcher> 4258 _GLIBCXX20_CONSTEXPR 4259 inline _ForwardIterator 4260 search(_ForwardIterator __first, _ForwardIterator __last, 4261 const _Searcher& __searcher) 4262 { return __searcher(__first, __last).first; } 4263 #endif 4264 4265 /** 4266 * @brief Perform an operation on a sequence. 4267 * @ingroup mutating_algorithms 4268 * @param __first An input iterator. 4269 * @param __last An input iterator. 4270 * @param __result An output iterator. 4271 * @param __unary_op A unary operator. 4272 * @return An output iterator equal to @p __result+(__last-__first). 4273 * 4274 * Applies the operator to each element in the input range and assigns 4275 * the results to successive elements of the output sequence. 4276 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 4277 * range @p [0,__last-__first). 4278 * 4279 * @p unary_op must not alter its argument. 4280 */ 4281 template<typename _InputIterator, typename _OutputIterator, 4282 typename _UnaryOperation> 4283 _GLIBCXX20_CONSTEXPR 4284 _OutputIterator 4285 transform(_InputIterator __first, _InputIterator __last, 4286 _OutputIterator __result, _UnaryOperation __unary_op) 4287 { 4288 // concept requirements 4289 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4290 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4291 // "the type returned by a _UnaryOperation" 4292 __typeof__(__unary_op(*__first))>) 4293 __glibcxx_requires_valid_range(__first, __last); 4294 4295 for (; __first != __last; ++__first, (void)++__result) 4296 *__result = __unary_op(*__first); 4297 return __result; 4298 } 4299 4300 /** 4301 * @brief Perform an operation on corresponding elements of two sequences. 4302 * @ingroup mutating_algorithms 4303 * @param __first1 An input iterator. 4304 * @param __last1 An input iterator. 4305 * @param __first2 An input iterator. 4306 * @param __result An output iterator. 4307 * @param __binary_op A binary operator. 4308 * @return An output iterator equal to @p result+(last-first). 4309 * 4310 * Applies the operator to the corresponding elements in the two 4311 * input ranges and assigns the results to successive elements of the 4312 * output sequence. 4313 * Evaluates @p 4314 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 4315 * @c N in the range @p [0,__last1-__first1). 4316 * 4317 * @p binary_op must not alter either of its arguments. 4318 */ 4319 template<typename _InputIterator1, typename _InputIterator2, 4320 typename _OutputIterator, typename _BinaryOperation> 4321 _GLIBCXX20_CONSTEXPR 4322 _OutputIterator 4323 transform(_InputIterator1 __first1, _InputIterator1 __last1, 4324 _InputIterator2 __first2, _OutputIterator __result, 4325 _BinaryOperation __binary_op) 4326 { 4327 // concept requirements 4328 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4329 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4330 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4331 // "the type returned by a _BinaryOperation" 4332 __typeof__(__binary_op(*__first1,*__first2))>) 4333 __glibcxx_requires_valid_range(__first1, __last1); 4334 4335 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result) 4336 *__result = __binary_op(*__first1, *__first2); 4337 return __result; 4338 } 4339 4340 /** 4341 * @brief Replace each occurrence of one value in a sequence with another 4342 * value. 4343 * @ingroup mutating_algorithms 4344 * @param __first A forward iterator. 4345 * @param __last A forward iterator. 4346 * @param __old_value The value to be replaced. 4347 * @param __new_value The replacement value. 4348 * @return replace() returns no value. 4349 * 4350 * For each iterator @c i in the range @p [__first,__last) if @c *i == 4351 * @p __old_value then the assignment @c *i = @p __new_value is performed. 4352 */ 4353 template<typename _ForwardIterator, typename _Tp> 4354 _GLIBCXX20_CONSTEXPR 4355 void 4356 replace(_ForwardIterator __first, _ForwardIterator __last, 4357 const _Tp& __old_value, const _Tp& __new_value) 4358 { 4359 // concept requirements 4360 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4361 _ForwardIterator>) 4362 __glibcxx_function_requires(_EqualOpConcept< 4363 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4364 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4365 typename iterator_traits<_ForwardIterator>::value_type>) 4366 __glibcxx_requires_valid_range(__first, __last); 4367 4368 for (; __first != __last; ++__first) 4369 if (*__first == __old_value) 4370 *__first = __new_value; 4371 } 4372 4373 /** 4374 * @brief Replace each value in a sequence for which a predicate returns 4375 * true with another value. 4376 * @ingroup mutating_algorithms 4377 * @param __first A forward iterator. 4378 * @param __last A forward iterator. 4379 * @param __pred A predicate. 4380 * @param __new_value The replacement value. 4381 * @return replace_if() returns no value. 4382 * 4383 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i) 4384 * is true then the assignment @c *i = @p __new_value is performed. 4385 */ 4386 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 4387 _GLIBCXX20_CONSTEXPR 4388 void 4389 replace_if(_ForwardIterator __first, _ForwardIterator __last, 4390 _Predicate __pred, const _Tp& __new_value) 4391 { 4392 // concept requirements 4393 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4394 _ForwardIterator>) 4395 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4396 typename iterator_traits<_ForwardIterator>::value_type>) 4397 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4398 typename iterator_traits<_ForwardIterator>::value_type>) 4399 __glibcxx_requires_valid_range(__first, __last); 4400 4401 for (; __first != __last; ++__first) 4402 if (__pred(*__first)) 4403 *__first = __new_value; 4404 } 4405 4406 /** 4407 * @brief Assign the result of a function object to each value in a 4408 * sequence. 4409 * @ingroup mutating_algorithms 4410 * @param __first A forward iterator. 4411 * @param __last A forward iterator. 4412 * @param __gen A function object taking no arguments and returning 4413 * std::iterator_traits<_ForwardIterator>::value_type 4414 * @return generate() returns no value. 4415 * 4416 * Performs the assignment @c *i = @p __gen() for each @c i in the range 4417 * @p [__first,__last). 4418 */ 4419 template<typename _ForwardIterator, typename _Generator> 4420 _GLIBCXX20_CONSTEXPR 4421 void 4422 generate(_ForwardIterator __first, _ForwardIterator __last, 4423 _Generator __gen) 4424 { 4425 // concept requirements 4426 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4427 __glibcxx_function_requires(_GeneratorConcept<_Generator, 4428 typename iterator_traits<_ForwardIterator>::value_type>) 4429 __glibcxx_requires_valid_range(__first, __last); 4430 4431 for (; __first != __last; ++__first) 4432 *__first = __gen(); 4433 } 4434 4435 /** 4436 * @brief Assign the result of a function object to each value in a 4437 * sequence. 4438 * @ingroup mutating_algorithms 4439 * @param __first A forward iterator. 4440 * @param __n The length of the sequence. 4441 * @param __gen A function object taking no arguments and returning 4442 * std::iterator_traits<_ForwardIterator>::value_type 4443 * @return The end of the sequence, @p __first+__n 4444 * 4445 * Performs the assignment @c *i = @p __gen() for each @c i in the range 4446 * @p [__first,__first+__n). 4447 * 4448 * If @p __n is negative, the function does nothing and returns @p __first. 4449 */ 4450 // _GLIBCXX_RESOLVE_LIB_DEFECTS 4451 // DR 865. More algorithms that throw away information 4452 // DR 426. search_n(), fill_n(), and generate_n() with negative n 4453 template<typename _OutputIterator, typename _Size, typename _Generator> 4454 _GLIBCXX20_CONSTEXPR 4455 _OutputIterator 4456 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 4457 { 4458 // concept requirements 4459 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4460 // "the type returned by a _Generator" 4461 __typeof__(__gen())>) 4462 4463 typedef __decltype(std::__size_to_integer(__n)) _IntSize; 4464 for (_IntSize __niter = std::__size_to_integer(__n); 4465 __niter > 0; --__niter, (void) ++__first) 4466 *__first = __gen(); 4467 return __first; 4468 } 4469 4470 /** 4471 * @brief Copy a sequence, removing consecutive duplicate values. 4472 * @ingroup mutating_algorithms 4473 * @param __first An input iterator. 4474 * @param __last An input iterator. 4475 * @param __result An output iterator. 4476 * @return An iterator designating the end of the resulting sequence. 4477 * 4478 * Copies each element in the range @p [__first,__last) to the range 4479 * beginning at @p __result, except that only the first element is copied 4480 * from groups of consecutive elements that compare equal. 4481 * unique_copy() is stable, so the relative order of elements that are 4482 * copied is unchanged. 4483 * 4484 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4485 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 4486 * 4487 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4488 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 4489 * Assignable? 4490 */ 4491 template<typename _InputIterator, typename _OutputIterator> 4492 _GLIBCXX20_CONSTEXPR 4493 inline _OutputIterator 4494 unique_copy(_InputIterator __first, _InputIterator __last, 4495 _OutputIterator __result) 4496 { 4497 // concept requirements 4498 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4499 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4500 typename iterator_traits<_InputIterator>::value_type>) 4501 __glibcxx_function_requires(_EqualityComparableConcept< 4502 typename iterator_traits<_InputIterator>::value_type>) 4503 __glibcxx_requires_valid_range(__first, __last); 4504 4505 if (__first == __last) 4506 return __result; 4507 return std::__unique_copy(__first, __last, __result, 4508 __gnu_cxx::__ops::__iter_equal_to_iter(), 4509 std::__iterator_category(__first), 4510 std::__iterator_category(__result)); 4511 } 4512 4513 /** 4514 * @brief Copy a sequence, removing consecutive values using a predicate. 4515 * @ingroup mutating_algorithms 4516 * @param __first An input iterator. 4517 * @param __last An input iterator. 4518 * @param __result An output iterator. 4519 * @param __binary_pred A binary predicate. 4520 * @return An iterator designating the end of the resulting sequence. 4521 * 4522 * Copies each element in the range @p [__first,__last) to the range 4523 * beginning at @p __result, except that only the first element is copied 4524 * from groups of consecutive elements for which @p __binary_pred returns 4525 * true. 4526 * unique_copy() is stable, so the relative order of elements that are 4527 * copied is unchanged. 4528 * 4529 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4530 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 4531 */ 4532 template<typename _InputIterator, typename _OutputIterator, 4533 typename _BinaryPredicate> 4534 _GLIBCXX20_CONSTEXPR 4535 inline _OutputIterator 4536 unique_copy(_InputIterator __first, _InputIterator __last, 4537 _OutputIterator __result, 4538 _BinaryPredicate __binary_pred) 4539 { 4540 // concept requirements -- predicates checked later 4541 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4542 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4543 typename iterator_traits<_InputIterator>::value_type>) 4544 __glibcxx_requires_valid_range(__first, __last); 4545 4546 if (__first == __last) 4547 return __result; 4548 return std::__unique_copy(__first, __last, __result, 4549 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 4550 std::__iterator_category(__first), 4551 std::__iterator_category(__result)); 4552 } 4553 4554 #if _GLIBCXX_HOSTED 4555 /** 4556 * @brief Randomly shuffle the elements of a sequence. 4557 * @ingroup mutating_algorithms 4558 * @param __first A forward iterator. 4559 * @param __last A forward iterator. 4560 * @return Nothing. 4561 * 4562 * Reorder the elements in the range @p [__first,__last) using a random 4563 * distribution, so that every possible ordering of the sequence is 4564 * equally likely. 4565 */ 4566 template<typename _RandomAccessIterator> 4567 inline void 4568 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 4569 { 4570 // concept requirements 4571 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4572 _RandomAccessIterator>) 4573 __glibcxx_requires_valid_range(__first, __last); 4574 4575 if (__first != __last) 4576 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4577 { 4578 // XXX rand() % N is not uniformly distributed 4579 _RandomAccessIterator __j = __first 4580 + std::rand() % ((__i - __first) + 1); 4581 if (__i != __j) 4582 std::iter_swap(__i, __j); 4583 } 4584 } 4585 #endif 4586 4587 /** 4588 * @brief Shuffle the elements of a sequence using a random number 4589 * generator. 4590 * @ingroup mutating_algorithms 4591 * @param __first A forward iterator. 4592 * @param __last A forward iterator. 4593 * @param __rand The RNG functor or function. 4594 * @return Nothing. 4595 * 4596 * Reorders the elements in the range @p [__first,__last) using @p __rand to 4597 * provide a random distribution. Calling @p __rand(N) for a positive 4598 * integer @p N should return a randomly chosen integer from the 4599 * range [0,N). 4600 */ 4601 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 4602 void 4603 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 4604 #if __cplusplus >= 201103L 4605 _RandomNumberGenerator&& __rand) 4606 #else 4607 _RandomNumberGenerator& __rand) 4608 #endif 4609 { 4610 // concept requirements 4611 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4612 _RandomAccessIterator>) 4613 __glibcxx_requires_valid_range(__first, __last); 4614 4615 if (__first == __last) 4616 return; 4617 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4618 { 4619 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); 4620 if (__i != __j) 4621 std::iter_swap(__i, __j); 4622 } 4623 } 4624 4625 4626 /** 4627 * @brief Move elements for which a predicate is true to the beginning 4628 * of a sequence. 4629 * @ingroup mutating_algorithms 4630 * @param __first A forward iterator. 4631 * @param __last A forward iterator. 4632 * @param __pred A predicate functor. 4633 * @return An iterator @p middle such that @p __pred(i) is true for each 4634 * iterator @p i in the range @p [__first,middle) and false for each @p i 4635 * in the range @p [middle,__last). 4636 * 4637 * @p __pred must not modify its operand. @p partition() does not preserve 4638 * the relative ordering of elements in each group, use 4639 * @p stable_partition() if this is needed. 4640 */ 4641 template<typename _ForwardIterator, typename _Predicate> 4642 _GLIBCXX20_CONSTEXPR 4643 inline _ForwardIterator 4644 partition(_ForwardIterator __first, _ForwardIterator __last, 4645 _Predicate __pred) 4646 { 4647 // concept requirements 4648 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4649 _ForwardIterator>) 4650 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4651 typename iterator_traits<_ForwardIterator>::value_type>) 4652 __glibcxx_requires_valid_range(__first, __last); 4653 4654 return std::__partition(__first, __last, __pred, 4655 std::__iterator_category(__first)); 4656 } 4657 4658 4659 /** 4660 * @brief Sort the smallest elements of a sequence. 4661 * @ingroup sorting_algorithms 4662 * @param __first An iterator. 4663 * @param __middle Another iterator. 4664 * @param __last Another iterator. 4665 * @return Nothing. 4666 * 4667 * Sorts the smallest @p (__middle-__first) elements in the range 4668 * @p [first,last) and moves them to the range @p [__first,__middle). The 4669 * order of the remaining elements in the range @p [__middle,__last) is 4670 * undefined. 4671 * After the sort if @e i and @e j are iterators in the range 4672 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 4673 * the range @p [__middle,__last) then *j<*i and *k<*i are both false. 4674 */ 4675 template<typename _RandomAccessIterator> 4676 _GLIBCXX20_CONSTEXPR 4677 inline void 4678 partial_sort(_RandomAccessIterator __first, 4679 _RandomAccessIterator __middle, 4680 _RandomAccessIterator __last) 4681 { 4682 // concept requirements 4683 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4684 _RandomAccessIterator>) 4685 __glibcxx_function_requires(_LessThanComparableConcept< 4686 typename iterator_traits<_RandomAccessIterator>::value_type>) 4687 __glibcxx_requires_valid_range(__first, __middle); 4688 __glibcxx_requires_valid_range(__middle, __last); 4689 __glibcxx_requires_irreflexive(__first, __last); 4690 4691 std::__partial_sort(__first, __middle, __last, 4692 __gnu_cxx::__ops::__iter_less_iter()); 4693 } 4694 4695 /** 4696 * @brief Sort the smallest elements of a sequence using a predicate 4697 * for comparison. 4698 * @ingroup sorting_algorithms 4699 * @param __first An iterator. 4700 * @param __middle Another iterator. 4701 * @param __last Another iterator. 4702 * @param __comp A comparison functor. 4703 * @return Nothing. 4704 * 4705 * Sorts the smallest @p (__middle-__first) elements in the range 4706 * @p [__first,__last) and moves them to the range @p [__first,__middle). The 4707 * order of the remaining elements in the range @p [__middle,__last) is 4708 * undefined. 4709 * After the sort if @e i and @e j are iterators in the range 4710 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 4711 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i) 4712 * are both false. 4713 */ 4714 template<typename _RandomAccessIterator, typename _Compare> 4715 _GLIBCXX20_CONSTEXPR 4716 inline void 4717 partial_sort(_RandomAccessIterator __first, 4718 _RandomAccessIterator __middle, 4719 _RandomAccessIterator __last, 4720 _Compare __comp) 4721 { 4722 // concept requirements 4723 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4724 _RandomAccessIterator>) 4725 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4726 typename iterator_traits<_RandomAccessIterator>::value_type, 4727 typename iterator_traits<_RandomAccessIterator>::value_type>) 4728 __glibcxx_requires_valid_range(__first, __middle); 4729 __glibcxx_requires_valid_range(__middle, __last); 4730 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4731 4732 std::__partial_sort(__first, __middle, __last, 4733 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4734 } 4735 4736 /** 4737 * @brief Sort a sequence just enough to find a particular position. 4738 * @ingroup sorting_algorithms 4739 * @param __first An iterator. 4740 * @param __nth Another iterator. 4741 * @param __last Another iterator. 4742 * @return Nothing. 4743 * 4744 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 4745 * is the same element that would have been in that position had the 4746 * whole sequence been sorted. The elements either side of @p *__nth are 4747 * not completely sorted, but for any iterator @e i in the range 4748 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 4749 * holds that *j < *i is false. 4750 */ 4751 template<typename _RandomAccessIterator> 4752 _GLIBCXX20_CONSTEXPR 4753 inline void 4754 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4755 _RandomAccessIterator __last) 4756 { 4757 // concept requirements 4758 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4759 _RandomAccessIterator>) 4760 __glibcxx_function_requires(_LessThanComparableConcept< 4761 typename iterator_traits<_RandomAccessIterator>::value_type>) 4762 __glibcxx_requires_valid_range(__first, __nth); 4763 __glibcxx_requires_valid_range(__nth, __last); 4764 __glibcxx_requires_irreflexive(__first, __last); 4765 4766 if (__first == __last || __nth == __last) 4767 return; 4768 4769 std::__introselect(__first, __nth, __last, 4770 std::__lg(__last - __first) * 2, 4771 __gnu_cxx::__ops::__iter_less_iter()); 4772 } 4773 4774 /** 4775 * @brief Sort a sequence just enough to find a particular position 4776 * using a predicate for comparison. 4777 * @ingroup sorting_algorithms 4778 * @param __first An iterator. 4779 * @param __nth Another iterator. 4780 * @param __last Another iterator. 4781 * @param __comp A comparison functor. 4782 * @return Nothing. 4783 * 4784 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 4785 * is the same element that would have been in that position had the 4786 * whole sequence been sorted. The elements either side of @p *__nth are 4787 * not completely sorted, but for any iterator @e i in the range 4788 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 4789 * holds that @p __comp(*j,*i) is false. 4790 */ 4791 template<typename _RandomAccessIterator, typename _Compare> 4792 _GLIBCXX20_CONSTEXPR 4793 inline void 4794 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4795 _RandomAccessIterator __last, _Compare __comp) 4796 { 4797 // concept requirements 4798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4799 _RandomAccessIterator>) 4800 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4801 typename iterator_traits<_RandomAccessIterator>::value_type, 4802 typename iterator_traits<_RandomAccessIterator>::value_type>) 4803 __glibcxx_requires_valid_range(__first, __nth); 4804 __glibcxx_requires_valid_range(__nth, __last); 4805 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4806 4807 if (__first == __last || __nth == __last) 4808 return; 4809 4810 std::__introselect(__first, __nth, __last, 4811 std::__lg(__last - __first) * 2, 4812 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4813 } 4814 4815 /** 4816 * @brief Sort the elements of a sequence. 4817 * @ingroup sorting_algorithms 4818 * @param __first An iterator. 4819 * @param __last Another iterator. 4820 * @return Nothing. 4821 * 4822 * Sorts the elements in the range @p [__first,__last) in ascending order, 4823 * such that for each iterator @e i in the range @p [__first,__last-1), 4824 * *(i+1)<*i is false. 4825 * 4826 * The relative ordering of equivalent elements is not preserved, use 4827 * @p stable_sort() if this is needed. 4828 */ 4829 template<typename _RandomAccessIterator> 4830 _GLIBCXX20_CONSTEXPR 4831 inline void 4832 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4833 { 4834 // concept requirements 4835 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4836 _RandomAccessIterator>) 4837 __glibcxx_function_requires(_LessThanComparableConcept< 4838 typename iterator_traits<_RandomAccessIterator>::value_type>) 4839 __glibcxx_requires_valid_range(__first, __last); 4840 __glibcxx_requires_irreflexive(__first, __last); 4841 4842 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 4843 } 4844 4845 /** 4846 * @brief Sort the elements of a sequence using a predicate for comparison. 4847 * @ingroup sorting_algorithms 4848 * @param __first An iterator. 4849 * @param __last Another iterator. 4850 * @param __comp A comparison functor. 4851 * @return Nothing. 4852 * 4853 * Sorts the elements in the range @p [__first,__last) in ascending order, 4854 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the 4855 * range @p [__first,__last-1). 4856 * 4857 * The relative ordering of equivalent elements is not preserved, use 4858 * @p stable_sort() if this is needed. 4859 */ 4860 template<typename _RandomAccessIterator, typename _Compare> 4861 _GLIBCXX20_CONSTEXPR 4862 inline void 4863 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 4864 _Compare __comp) 4865 { 4866 // concept requirements 4867 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4868 _RandomAccessIterator>) 4869 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4870 typename iterator_traits<_RandomAccessIterator>::value_type, 4871 typename iterator_traits<_RandomAccessIterator>::value_type>) 4872 __glibcxx_requires_valid_range(__first, __last); 4873 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4874 4875 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4876 } 4877 4878 template<typename _InputIterator1, typename _InputIterator2, 4879 typename _OutputIterator, typename _Compare> 4880 _GLIBCXX20_CONSTEXPR 4881 _OutputIterator 4882 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 4883 _InputIterator2 __first2, _InputIterator2 __last2, 4884 _OutputIterator __result, _Compare __comp) 4885 { 4886 while (__first1 != __last1 && __first2 != __last2) 4887 { 4888 if (__comp(__first2, __first1)) 4889 { 4890 *__result = *__first2; 4891 ++__first2; 4892 } 4893 else 4894 { 4895 *__result = *__first1; 4896 ++__first1; 4897 } 4898 ++__result; 4899 } 4900 return std::copy(__first2, __last2, 4901 std::copy(__first1, __last1, __result)); 4902 } 4903 4904 /** 4905 * @brief Merges two sorted ranges. 4906 * @ingroup sorting_algorithms 4907 * @param __first1 An iterator. 4908 * @param __first2 Another iterator. 4909 * @param __last1 Another iterator. 4910 * @param __last2 Another iterator. 4911 * @param __result An iterator pointing to the end of the merged range. 4912 * @return An output iterator equal to @p __result + (__last1 - __first1) 4913 * + (__last2 - __first2). 4914 * 4915 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4916 * the sorted range @p [__result, __result + (__last1-__first1) + 4917 * (__last2-__first2)). Both input ranges must be sorted, and the 4918 * output range must not overlap with either of the input ranges. 4919 * The sort is @e stable, that is, for equivalent elements in the 4920 * two ranges, elements from the first range will always come 4921 * before elements from the second. 4922 */ 4923 template<typename _InputIterator1, typename _InputIterator2, 4924 typename _OutputIterator> 4925 _GLIBCXX20_CONSTEXPR 4926 inline _OutputIterator 4927 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4928 _InputIterator2 __first2, _InputIterator2 __last2, 4929 _OutputIterator __result) 4930 { 4931 // concept requirements 4932 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4933 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4934 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4935 typename iterator_traits<_InputIterator1>::value_type>) 4936 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4937 typename iterator_traits<_InputIterator2>::value_type>) 4938 __glibcxx_function_requires(_LessThanOpConcept< 4939 typename iterator_traits<_InputIterator2>::value_type, 4940 typename iterator_traits<_InputIterator1>::value_type>) 4941 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 4942 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 4943 __glibcxx_requires_irreflexive2(__first1, __last1); 4944 __glibcxx_requires_irreflexive2(__first2, __last2); 4945 4946 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4947 __first2, __last2, __result, 4948 __gnu_cxx::__ops::__iter_less_iter()); 4949 } 4950 4951 /** 4952 * @brief Merges two sorted ranges. 4953 * @ingroup sorting_algorithms 4954 * @param __first1 An iterator. 4955 * @param __first2 Another iterator. 4956 * @param __last1 Another iterator. 4957 * @param __last2 Another iterator. 4958 * @param __result An iterator pointing to the end of the merged range. 4959 * @param __comp A functor to use for comparisons. 4960 * @return An output iterator equal to @p __result + (__last1 - __first1) 4961 * + (__last2 - __first2). 4962 * 4963 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4964 * the sorted range @p [__result, __result + (__last1-__first1) + 4965 * (__last2-__first2)). Both input ranges must be sorted, and the 4966 * output range must not overlap with either of the input ranges. 4967 * The sort is @e stable, that is, for equivalent elements in the 4968 * two ranges, elements from the first range will always come 4969 * before elements from the second. 4970 * 4971 * The comparison function should have the same effects on ordering as 4972 * the function used for the initial sort. 4973 */ 4974 template<typename _InputIterator1, typename _InputIterator2, 4975 typename _OutputIterator, typename _Compare> 4976 _GLIBCXX20_CONSTEXPR 4977 inline _OutputIterator 4978 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4979 _InputIterator2 __first2, _InputIterator2 __last2, 4980 _OutputIterator __result, _Compare __comp) 4981 { 4982 // concept requirements 4983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4984 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4985 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4986 typename iterator_traits<_InputIterator1>::value_type>) 4987 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4988 typename iterator_traits<_InputIterator2>::value_type>) 4989 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4990 typename iterator_traits<_InputIterator2>::value_type, 4991 typename iterator_traits<_InputIterator1>::value_type>) 4992 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 4993 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 4994 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 4995 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 4996 4997 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4998 __first2, __last2, __result, 4999 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5000 } 5001 5002 template<typename _RandomAccessIterator, typename _Compare> 5003 inline void 5004 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 5005 _Compare __comp) 5006 { 5007 typedef typename iterator_traits<_RandomAccessIterator>::value_type 5008 _ValueType; 5009 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 5010 _DistanceType; 5011 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 5012 5013 if (__first == __last) 5014 return; 5015 5016 // __stable_sort_adaptive sorts the range in two halves, 5017 // so the buffer only needs to fit half the range at once. 5018 _TmpBuf __buf(__first, (__last - __first + 1) / 2); 5019 5020 if (__buf.begin() == 0) 5021 std::__inplace_stable_sort(__first, __last, __comp); 5022 else 5023 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 5024 _DistanceType(__buf.size()), __comp); 5025 } 5026 5027 /** 5028 * @brief Sort the elements of a sequence, preserving the relative order 5029 * of equivalent elements. 5030 * @ingroup sorting_algorithms 5031 * @param __first An iterator. 5032 * @param __last Another iterator. 5033 * @return Nothing. 5034 * 5035 * Sorts the elements in the range @p [__first,__last) in ascending order, 5036 * such that for each iterator @p i in the range @p [__first,__last-1), 5037 * @p *(i+1)<*i is false. 5038 * 5039 * The relative ordering of equivalent elements is preserved, so any two 5040 * elements @p x and @p y in the range @p [__first,__last) such that 5041 * @p x<y is false and @p y<x is false will have the same relative 5042 * ordering after calling @p stable_sort(). 5043 */ 5044 template<typename _RandomAccessIterator> 5045 inline void 5046 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 5047 { 5048 // concept requirements 5049 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 5050 _RandomAccessIterator>) 5051 __glibcxx_function_requires(_LessThanComparableConcept< 5052 typename iterator_traits<_RandomAccessIterator>::value_type>) 5053 __glibcxx_requires_valid_range(__first, __last); 5054 __glibcxx_requires_irreflexive(__first, __last); 5055 5056 _GLIBCXX_STD_A::__stable_sort(__first, __last, 5057 __gnu_cxx::__ops::__iter_less_iter()); 5058 } 5059 5060 /** 5061 * @brief Sort the elements of a sequence using a predicate for comparison, 5062 * preserving the relative order of equivalent elements. 5063 * @ingroup sorting_algorithms 5064 * @param __first An iterator. 5065 * @param __last Another iterator. 5066 * @param __comp A comparison functor. 5067 * @return Nothing. 5068 * 5069 * Sorts the elements in the range @p [__first,__last) in ascending order, 5070 * such that for each iterator @p i in the range @p [__first,__last-1), 5071 * @p __comp(*(i+1),*i) is false. 5072 * 5073 * The relative ordering of equivalent elements is preserved, so any two 5074 * elements @p x and @p y in the range @p [__first,__last) such that 5075 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 5076 * relative ordering after calling @p stable_sort(). 5077 */ 5078 template<typename _RandomAccessIterator, typename _Compare> 5079 inline void 5080 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 5081 _Compare __comp) 5082 { 5083 // concept requirements 5084 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 5085 _RandomAccessIterator>) 5086 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5087 typename iterator_traits<_RandomAccessIterator>::value_type, 5088 typename iterator_traits<_RandomAccessIterator>::value_type>) 5089 __glibcxx_requires_valid_range(__first, __last); 5090 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5091 5092 _GLIBCXX_STD_A::__stable_sort(__first, __last, 5093 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5094 } 5095 5096 template<typename _InputIterator1, typename _InputIterator2, 5097 typename _OutputIterator, 5098 typename _Compare> 5099 _GLIBCXX20_CONSTEXPR 5100 _OutputIterator 5101 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5102 _InputIterator2 __first2, _InputIterator2 __last2, 5103 _OutputIterator __result, _Compare __comp) 5104 { 5105 while (__first1 != __last1 && __first2 != __last2) 5106 { 5107 if (__comp(__first1, __first2)) 5108 { 5109 *__result = *__first1; 5110 ++__first1; 5111 } 5112 else if (__comp(__first2, __first1)) 5113 { 5114 *__result = *__first2; 5115 ++__first2; 5116 } 5117 else 5118 { 5119 *__result = *__first1; 5120 ++__first1; 5121 ++__first2; 5122 } 5123 ++__result; 5124 } 5125 return std::copy(__first2, __last2, 5126 std::copy(__first1, __last1, __result)); 5127 } 5128 5129 /** 5130 * @brief Return the union of two sorted ranges. 5131 * @ingroup set_algorithms 5132 * @param __first1 Start of first range. 5133 * @param __last1 End of first range. 5134 * @param __first2 Start of second range. 5135 * @param __last2 End of second range. 5136 * @param __result Start of output range. 5137 * @return End of the output range. 5138 * @ingroup set_algorithms 5139 * 5140 * This operation iterates over both ranges, copying elements present in 5141 * each range in order to the output range. Iterators increment for each 5142 * range. When the current element of one range is less than the other, 5143 * that element is copied and the iterator advanced. If an element is 5144 * contained in both ranges, the element from the first range is copied and 5145 * both ranges advance. The output range may not overlap either input 5146 * range. 5147 */ 5148 template<typename _InputIterator1, typename _InputIterator2, 5149 typename _OutputIterator> 5150 _GLIBCXX20_CONSTEXPR 5151 inline _OutputIterator 5152 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5153 _InputIterator2 __first2, _InputIterator2 __last2, 5154 _OutputIterator __result) 5155 { 5156 // concept requirements 5157 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5158 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5159 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5160 typename iterator_traits<_InputIterator1>::value_type>) 5161 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5162 typename iterator_traits<_InputIterator2>::value_type>) 5163 __glibcxx_function_requires(_LessThanOpConcept< 5164 typename iterator_traits<_InputIterator1>::value_type, 5165 typename iterator_traits<_InputIterator2>::value_type>) 5166 __glibcxx_function_requires(_LessThanOpConcept< 5167 typename iterator_traits<_InputIterator2>::value_type, 5168 typename iterator_traits<_InputIterator1>::value_type>) 5169 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5170 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5171 __glibcxx_requires_irreflexive2(__first1, __last1); 5172 __glibcxx_requires_irreflexive2(__first2, __last2); 5173 5174 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5175 __first2, __last2, __result, 5176 __gnu_cxx::__ops::__iter_less_iter()); 5177 } 5178 5179 /** 5180 * @brief Return the union of two sorted ranges using a comparison functor. 5181 * @ingroup set_algorithms 5182 * @param __first1 Start of first range. 5183 * @param __last1 End of first range. 5184 * @param __first2 Start of second range. 5185 * @param __last2 End of second range. 5186 * @param __result Start of output range. 5187 * @param __comp The comparison functor. 5188 * @return End of the output range. 5189 * @ingroup set_algorithms 5190 * 5191 * This operation iterates over both ranges, copying elements present in 5192 * each range in order to the output range. Iterators increment for each 5193 * range. When the current element of one range is less than the other 5194 * according to @p __comp, that element is copied and the iterator advanced. 5195 * If an equivalent element according to @p __comp is contained in both 5196 * ranges, the element from the first range is copied and both ranges 5197 * advance. The output range may not overlap either input range. 5198 */ 5199 template<typename _InputIterator1, typename _InputIterator2, 5200 typename _OutputIterator, typename _Compare> 5201 _GLIBCXX20_CONSTEXPR 5202 inline _OutputIterator 5203 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5204 _InputIterator2 __first2, _InputIterator2 __last2, 5205 _OutputIterator __result, _Compare __comp) 5206 { 5207 // concept requirements 5208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5209 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5211 typename iterator_traits<_InputIterator1>::value_type>) 5212 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5213 typename iterator_traits<_InputIterator2>::value_type>) 5214 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5215 typename iterator_traits<_InputIterator1>::value_type, 5216 typename iterator_traits<_InputIterator2>::value_type>) 5217 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5218 typename iterator_traits<_InputIterator2>::value_type, 5219 typename iterator_traits<_InputIterator1>::value_type>) 5220 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5221 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5222 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5223 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5224 5225 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5226 __first2, __last2, __result, 5227 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5228 } 5229 5230 template<typename _InputIterator1, typename _InputIterator2, 5231 typename _OutputIterator, 5232 typename _Compare> 5233 _GLIBCXX20_CONSTEXPR 5234 _OutputIterator 5235 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5236 _InputIterator2 __first2, _InputIterator2 __last2, 5237 _OutputIterator __result, _Compare __comp) 5238 { 5239 while (__first1 != __last1 && __first2 != __last2) 5240 if (__comp(__first1, __first2)) 5241 ++__first1; 5242 else if (__comp(__first2, __first1)) 5243 ++__first2; 5244 else 5245 { 5246 *__result = *__first1; 5247 ++__first1; 5248 ++__first2; 5249 ++__result; 5250 } 5251 return __result; 5252 } 5253 5254 /** 5255 * @brief Return the intersection of two sorted ranges. 5256 * @ingroup set_algorithms 5257 * @param __first1 Start of first range. 5258 * @param __last1 End of first range. 5259 * @param __first2 Start of second range. 5260 * @param __last2 End of second range. 5261 * @param __result Start of output range. 5262 * @return End of the output range. 5263 * @ingroup set_algorithms 5264 * 5265 * This operation iterates over both ranges, copying elements present in 5266 * both ranges in order to the output range. Iterators increment for each 5267 * range. When the current element of one range is less than the other, 5268 * that iterator advances. If an element is contained in both ranges, the 5269 * element from the first range is copied and both ranges advance. The 5270 * output range may not overlap either input range. 5271 */ 5272 template<typename _InputIterator1, typename _InputIterator2, 5273 typename _OutputIterator> 5274 _GLIBCXX20_CONSTEXPR 5275 inline _OutputIterator 5276 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5277 _InputIterator2 __first2, _InputIterator2 __last2, 5278 _OutputIterator __result) 5279 { 5280 // concept requirements 5281 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5282 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5283 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5284 typename iterator_traits<_InputIterator1>::value_type>) 5285 __glibcxx_function_requires(_LessThanOpConcept< 5286 typename iterator_traits<_InputIterator1>::value_type, 5287 typename iterator_traits<_InputIterator2>::value_type>) 5288 __glibcxx_function_requires(_LessThanOpConcept< 5289 typename iterator_traits<_InputIterator2>::value_type, 5290 typename iterator_traits<_InputIterator1>::value_type>) 5291 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5292 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5293 __glibcxx_requires_irreflexive2(__first1, __last1); 5294 __glibcxx_requires_irreflexive2(__first2, __last2); 5295 5296 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5297 __first2, __last2, __result, 5298 __gnu_cxx::__ops::__iter_less_iter()); 5299 } 5300 5301 /** 5302 * @brief Return the intersection of two sorted ranges using comparison 5303 * functor. 5304 * @ingroup set_algorithms 5305 * @param __first1 Start of first range. 5306 * @param __last1 End of first range. 5307 * @param __first2 Start of second range. 5308 * @param __last2 End of second range. 5309 * @param __result Start of output range. 5310 * @param __comp The comparison functor. 5311 * @return End of the output range. 5312 * @ingroup set_algorithms 5313 * 5314 * This operation iterates over both ranges, copying elements present in 5315 * both ranges in order to the output range. Iterators increment for each 5316 * range. When the current element of one range is less than the other 5317 * according to @p __comp, that iterator advances. If an element is 5318 * contained in both ranges according to @p __comp, the element from the 5319 * first range is copied and both ranges advance. The output range may not 5320 * overlap either input range. 5321 */ 5322 template<typename _InputIterator1, typename _InputIterator2, 5323 typename _OutputIterator, typename _Compare> 5324 _GLIBCXX20_CONSTEXPR 5325 inline _OutputIterator 5326 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5327 _InputIterator2 __first2, _InputIterator2 __last2, 5328 _OutputIterator __result, _Compare __comp) 5329 { 5330 // concept requirements 5331 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5332 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5333 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5334 typename iterator_traits<_InputIterator1>::value_type>) 5335 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5336 typename iterator_traits<_InputIterator1>::value_type, 5337 typename iterator_traits<_InputIterator2>::value_type>) 5338 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5339 typename iterator_traits<_InputIterator2>::value_type, 5340 typename iterator_traits<_InputIterator1>::value_type>) 5341 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5342 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5343 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5344 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5345 5346 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5347 __first2, __last2, __result, 5348 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5349 } 5350 5351 template<typename _InputIterator1, typename _InputIterator2, 5352 typename _OutputIterator, 5353 typename _Compare> 5354 _GLIBCXX20_CONSTEXPR 5355 _OutputIterator 5356 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5357 _InputIterator2 __first2, _InputIterator2 __last2, 5358 _OutputIterator __result, _Compare __comp) 5359 { 5360 while (__first1 != __last1 && __first2 != __last2) 5361 if (__comp(__first1, __first2)) 5362 { 5363 *__result = *__first1; 5364 ++__first1; 5365 ++__result; 5366 } 5367 else if (__comp(__first2, __first1)) 5368 ++__first2; 5369 else 5370 { 5371 ++__first1; 5372 ++__first2; 5373 } 5374 return std::copy(__first1, __last1, __result); 5375 } 5376 5377 /** 5378 * @brief Return the difference of two sorted ranges. 5379 * @ingroup set_algorithms 5380 * @param __first1 Start of first range. 5381 * @param __last1 End of first range. 5382 * @param __first2 Start of second range. 5383 * @param __last2 End of second range. 5384 * @param __result Start of output range. 5385 * @return End of the output range. 5386 * @ingroup set_algorithms 5387 * 5388 * This operation iterates over both ranges, copying elements present in 5389 * the first range but not the second in order to the output range. 5390 * Iterators increment for each range. When the current element of the 5391 * first range is less than the second, that element is copied and the 5392 * iterator advances. If the current element of the second range is less, 5393 * the iterator advances, but no element is copied. If an element is 5394 * contained in both ranges, no elements are copied and both ranges 5395 * advance. The output range may not overlap either input range. 5396 */ 5397 template<typename _InputIterator1, typename _InputIterator2, 5398 typename _OutputIterator> 5399 _GLIBCXX20_CONSTEXPR 5400 inline _OutputIterator 5401 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5402 _InputIterator2 __first2, _InputIterator2 __last2, 5403 _OutputIterator __result) 5404 { 5405 // concept requirements 5406 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5407 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5408 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5409 typename iterator_traits<_InputIterator1>::value_type>) 5410 __glibcxx_function_requires(_LessThanOpConcept< 5411 typename iterator_traits<_InputIterator1>::value_type, 5412 typename iterator_traits<_InputIterator2>::value_type>) 5413 __glibcxx_function_requires(_LessThanOpConcept< 5414 typename iterator_traits<_InputIterator2>::value_type, 5415 typename iterator_traits<_InputIterator1>::value_type>) 5416 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5417 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5418 __glibcxx_requires_irreflexive2(__first1, __last1); 5419 __glibcxx_requires_irreflexive2(__first2, __last2); 5420 5421 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5422 __first2, __last2, __result, 5423 __gnu_cxx::__ops::__iter_less_iter()); 5424 } 5425 5426 /** 5427 * @brief Return the difference of two sorted ranges using comparison 5428 * functor. 5429 * @ingroup set_algorithms 5430 * @param __first1 Start of first range. 5431 * @param __last1 End of first range. 5432 * @param __first2 Start of second range. 5433 * @param __last2 End of second range. 5434 * @param __result Start of output range. 5435 * @param __comp The comparison functor. 5436 * @return End of the output range. 5437 * @ingroup set_algorithms 5438 * 5439 * This operation iterates over both ranges, copying elements present in 5440 * the first range but not the second in order to the output range. 5441 * Iterators increment for each range. When the current element of the 5442 * first range is less than the second according to @p __comp, that element 5443 * is copied and the iterator advances. If the current element of the 5444 * second range is less, no element is copied and the iterator advances. 5445 * If an element is contained in both ranges according to @p __comp, no 5446 * elements are copied and both ranges advance. The output range may not 5447 * overlap either input range. 5448 */ 5449 template<typename _InputIterator1, typename _InputIterator2, 5450 typename _OutputIterator, typename _Compare> 5451 _GLIBCXX20_CONSTEXPR 5452 inline _OutputIterator 5453 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5454 _InputIterator2 __first2, _InputIterator2 __last2, 5455 _OutputIterator __result, _Compare __comp) 5456 { 5457 // concept requirements 5458 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5459 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5460 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5461 typename iterator_traits<_InputIterator1>::value_type>) 5462 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5463 typename iterator_traits<_InputIterator1>::value_type, 5464 typename iterator_traits<_InputIterator2>::value_type>) 5465 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5466 typename iterator_traits<_InputIterator2>::value_type, 5467 typename iterator_traits<_InputIterator1>::value_type>) 5468 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5469 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5470 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5471 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5472 5473 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5474 __first2, __last2, __result, 5475 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5476 } 5477 5478 template<typename _InputIterator1, typename _InputIterator2, 5479 typename _OutputIterator, 5480 typename _Compare> 5481 _GLIBCXX20_CONSTEXPR 5482 _OutputIterator 5483 __set_symmetric_difference(_InputIterator1 __first1, 5484 _InputIterator1 __last1, 5485 _InputIterator2 __first2, 5486 _InputIterator2 __last2, 5487 _OutputIterator __result, 5488 _Compare __comp) 5489 { 5490 while (__first1 != __last1 && __first2 != __last2) 5491 if (__comp(__first1, __first2)) 5492 { 5493 *__result = *__first1; 5494 ++__first1; 5495 ++__result; 5496 } 5497 else if (__comp(__first2, __first1)) 5498 { 5499 *__result = *__first2; 5500 ++__first2; 5501 ++__result; 5502 } 5503 else 5504 { 5505 ++__first1; 5506 ++__first2; 5507 } 5508 return std::copy(__first2, __last2, 5509 std::copy(__first1, __last1, __result)); 5510 } 5511 5512 /** 5513 * @brief Return the symmetric difference of two sorted ranges. 5514 * @ingroup set_algorithms 5515 * @param __first1 Start of first range. 5516 * @param __last1 End of first range. 5517 * @param __first2 Start of second range. 5518 * @param __last2 End of second range. 5519 * @param __result Start of output range. 5520 * @return End of the output range. 5521 * @ingroup set_algorithms 5522 * 5523 * This operation iterates over both ranges, copying elements present in 5524 * one range but not the other in order to the output range. Iterators 5525 * increment for each range. When the current element of one range is less 5526 * than the other, that element is copied and the iterator advances. If an 5527 * element is contained in both ranges, no elements are copied and both 5528 * ranges advance. The output range may not overlap either input range. 5529 */ 5530 template<typename _InputIterator1, typename _InputIterator2, 5531 typename _OutputIterator> 5532 _GLIBCXX20_CONSTEXPR 5533 inline _OutputIterator 5534 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5535 _InputIterator2 __first2, _InputIterator2 __last2, 5536 _OutputIterator __result) 5537 { 5538 // concept requirements 5539 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5540 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5541 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5542 typename iterator_traits<_InputIterator1>::value_type>) 5543 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5544 typename iterator_traits<_InputIterator2>::value_type>) 5545 __glibcxx_function_requires(_LessThanOpConcept< 5546 typename iterator_traits<_InputIterator1>::value_type, 5547 typename iterator_traits<_InputIterator2>::value_type>) 5548 __glibcxx_function_requires(_LessThanOpConcept< 5549 typename iterator_traits<_InputIterator2>::value_type, 5550 typename iterator_traits<_InputIterator1>::value_type>) 5551 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5552 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5553 __glibcxx_requires_irreflexive2(__first1, __last1); 5554 __glibcxx_requires_irreflexive2(__first2, __last2); 5555 5556 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5557 __first2, __last2, __result, 5558 __gnu_cxx::__ops::__iter_less_iter()); 5559 } 5560 5561 /** 5562 * @brief Return the symmetric difference of two sorted ranges using 5563 * comparison functor. 5564 * @ingroup set_algorithms 5565 * @param __first1 Start of first range. 5566 * @param __last1 End of first range. 5567 * @param __first2 Start of second range. 5568 * @param __last2 End of second range. 5569 * @param __result Start of output range. 5570 * @param __comp The comparison functor. 5571 * @return End of the output range. 5572 * @ingroup set_algorithms 5573 * 5574 * This operation iterates over both ranges, copying elements present in 5575 * one range but not the other in order to the output range. Iterators 5576 * increment for each range. When the current element of one range is less 5577 * than the other according to @p comp, that element is copied and the 5578 * iterator advances. If an element is contained in both ranges according 5579 * to @p __comp, no elements are copied and both ranges advance. The output 5580 * range may not overlap either input range. 5581 */ 5582 template<typename _InputIterator1, typename _InputIterator2, 5583 typename _OutputIterator, typename _Compare> 5584 _GLIBCXX20_CONSTEXPR 5585 inline _OutputIterator 5586 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5587 _InputIterator2 __first2, _InputIterator2 __last2, 5588 _OutputIterator __result, 5589 _Compare __comp) 5590 { 5591 // concept requirements 5592 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5593 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5594 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5595 typename iterator_traits<_InputIterator1>::value_type>) 5596 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5597 typename iterator_traits<_InputIterator2>::value_type>) 5598 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5599 typename iterator_traits<_InputIterator1>::value_type, 5600 typename iterator_traits<_InputIterator2>::value_type>) 5601 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5602 typename iterator_traits<_InputIterator2>::value_type, 5603 typename iterator_traits<_InputIterator1>::value_type>) 5604 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5605 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5606 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5607 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5608 5609 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5610 __first2, __last2, __result, 5611 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5612 } 5613 5614 template<typename _ForwardIterator, typename _Compare> 5615 _GLIBCXX14_CONSTEXPR 5616 _ForwardIterator 5617 __min_element(_ForwardIterator __first, _ForwardIterator __last, 5618 _Compare __comp) 5619 { 5620 if (__first == __last) 5621 return __first; 5622 _ForwardIterator __result = __first; 5623 while (++__first != __last) 5624 if (__comp(__first, __result)) 5625 __result = __first; 5626 return __result; 5627 } 5628 5629 /** 5630 * @brief Return the minimum element in a range. 5631 * @ingroup sorting_algorithms 5632 * @param __first Start of range. 5633 * @param __last End of range. 5634 * @return Iterator referencing the first instance of the smallest value. 5635 */ 5636 template<typename _ForwardIterator> 5637 _GLIBCXX14_CONSTEXPR 5638 _ForwardIterator 5639 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 5640 { 5641 // concept requirements 5642 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5643 __glibcxx_function_requires(_LessThanComparableConcept< 5644 typename iterator_traits<_ForwardIterator>::value_type>) 5645 __glibcxx_requires_valid_range(__first, __last); 5646 __glibcxx_requires_irreflexive(__first, __last); 5647 5648 return _GLIBCXX_STD_A::__min_element(__first, __last, 5649 __gnu_cxx::__ops::__iter_less_iter()); 5650 } 5651 5652 /** 5653 * @brief Return the minimum element in a range using comparison functor. 5654 * @ingroup sorting_algorithms 5655 * @param __first Start of range. 5656 * @param __last End of range. 5657 * @param __comp Comparison functor. 5658 * @return Iterator referencing the first instance of the smallest value 5659 * according to __comp. 5660 */ 5661 template<typename _ForwardIterator, typename _Compare> 5662 _GLIBCXX14_CONSTEXPR 5663 inline _ForwardIterator 5664 min_element(_ForwardIterator __first, _ForwardIterator __last, 5665 _Compare __comp) 5666 { 5667 // concept requirements 5668 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5669 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5670 typename iterator_traits<_ForwardIterator>::value_type, 5671 typename iterator_traits<_ForwardIterator>::value_type>) 5672 __glibcxx_requires_valid_range(__first, __last); 5673 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5674 5675 return _GLIBCXX_STD_A::__min_element(__first, __last, 5676 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5677 } 5678 5679 template<typename _ForwardIterator, typename _Compare> 5680 _GLIBCXX14_CONSTEXPR 5681 _ForwardIterator 5682 __max_element(_ForwardIterator __first, _ForwardIterator __last, 5683 _Compare __comp) 5684 { 5685 if (__first == __last) return __first; 5686 _ForwardIterator __result = __first; 5687 while (++__first != __last) 5688 if (__comp(__result, __first)) 5689 __result = __first; 5690 return __result; 5691 } 5692 5693 /** 5694 * @brief Return the maximum element in a range. 5695 * @ingroup sorting_algorithms 5696 * @param __first Start of range. 5697 * @param __last End of range. 5698 * @return Iterator referencing the first instance of the largest value. 5699 */ 5700 template<typename _ForwardIterator> 5701 _GLIBCXX14_CONSTEXPR 5702 inline _ForwardIterator 5703 max_element(_ForwardIterator __first, _ForwardIterator __last) 5704 { 5705 // concept requirements 5706 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5707 __glibcxx_function_requires(_LessThanComparableConcept< 5708 typename iterator_traits<_ForwardIterator>::value_type>) 5709 __glibcxx_requires_valid_range(__first, __last); 5710 __glibcxx_requires_irreflexive(__first, __last); 5711 5712 return _GLIBCXX_STD_A::__max_element(__first, __last, 5713 __gnu_cxx::__ops::__iter_less_iter()); 5714 } 5715 5716 /** 5717 * @brief Return the maximum element in a range using comparison functor. 5718 * @ingroup sorting_algorithms 5719 * @param __first Start of range. 5720 * @param __last End of range. 5721 * @param __comp Comparison functor. 5722 * @return Iterator referencing the first instance of the largest value 5723 * according to __comp. 5724 */ 5725 template<typename _ForwardIterator, typename _Compare> 5726 _GLIBCXX14_CONSTEXPR 5727 inline _ForwardIterator 5728 max_element(_ForwardIterator __first, _ForwardIterator __last, 5729 _Compare __comp) 5730 { 5731 // concept requirements 5732 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5733 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5734 typename iterator_traits<_ForwardIterator>::value_type, 5735 typename iterator_traits<_ForwardIterator>::value_type>) 5736 __glibcxx_requires_valid_range(__first, __last); 5737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5738 5739 return _GLIBCXX_STD_A::__max_element(__first, __last, 5740 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5741 } 5742 5743 #if __cplusplus >= 201402L 5744 /// Reservoir sampling algorithm. 5745 template<typename _InputIterator, typename _RandomAccessIterator, 5746 typename _Size, typename _UniformRandomBitGenerator> 5747 _RandomAccessIterator 5748 __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, 5749 _RandomAccessIterator __out, random_access_iterator_tag, 5750 _Size __n, _UniformRandomBitGenerator&& __g) 5751 { 5752 using __distrib_type = uniform_int_distribution<_Size>; 5753 using __param_type = typename __distrib_type::param_type; 5754 __distrib_type __d{}; 5755 _Size __sample_sz = 0; 5756 while (__first != __last && __sample_sz != __n) 5757 { 5758 __out[__sample_sz++] = *__first; 5759 ++__first; 5760 } 5761 for (auto __pop_sz = __sample_sz; __first != __last; 5762 ++__first, (void) ++__pop_sz) 5763 { 5764 const auto __k = __d(__g, __param_type{0, __pop_sz}); 5765 if (__k < __n) 5766 __out[__k] = *__first; 5767 } 5768 return __out + __sample_sz; 5769 } 5770 5771 /// Selection sampling algorithm. 5772 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat, 5773 typename _Size, typename _UniformRandomBitGenerator> 5774 _OutputIterator 5775 __sample(_ForwardIterator __first, _ForwardIterator __last, 5776 forward_iterator_tag, 5777 _OutputIterator __out, _Cat, 5778 _Size __n, _UniformRandomBitGenerator&& __g) 5779 { 5780 using __distrib_type = uniform_int_distribution<_Size>; 5781 using __param_type = typename __distrib_type::param_type; 5782 using _USize = make_unsigned_t<_Size>; 5783 using _Gen = remove_reference_t<_UniformRandomBitGenerator>; 5784 using __uc_type = common_type_t<typename _Gen::result_type, _USize>; 5785 5786 if (__first == __last) 5787 return __out; 5788 5789 __distrib_type __d{}; 5790 _Size __unsampled_sz = std::distance(__first, __last); 5791 __n = std::min(__n, __unsampled_sz); 5792 5793 // If possible, we use __gen_two_uniform_ints to efficiently produce 5794 // two random numbers using a single distribution invocation: 5795 5796 const __uc_type __urngrange = __g.max() - __g.min(); 5797 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz)) 5798 // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without 5799 // wrapping issues. 5800 { 5801 while (__n != 0 && __unsampled_sz >= 2) 5802 { 5803 const pair<_Size, _Size> __p = 5804 __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g); 5805 5806 --__unsampled_sz; 5807 if (__p.first < __n) 5808 { 5809 *__out++ = *__first; 5810 --__n; 5811 } 5812 5813 ++__first; 5814 5815 if (__n == 0) break; 5816 5817 --__unsampled_sz; 5818 if (__p.second < __n) 5819 { 5820 *__out++ = *__first; 5821 --__n; 5822 } 5823 5824 ++__first; 5825 } 5826 } 5827 5828 // The loop above is otherwise equivalent to this one-at-a-time version: 5829 5830 for (; __n != 0; ++__first) 5831 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) 5832 { 5833 *__out++ = *__first; 5834 --__n; 5835 } 5836 return __out; 5837 } 5838 5839 #if __cplusplus > 201402L 5840 #define __cpp_lib_sample 201603 5841 /// Take a random sample from a population. 5842 template<typename _PopulationIterator, typename _SampleIterator, 5843 typename _Distance, typename _UniformRandomBitGenerator> 5844 _SampleIterator 5845 sample(_PopulationIterator __first, _PopulationIterator __last, 5846 _SampleIterator __out, _Distance __n, 5847 _UniformRandomBitGenerator&& __g) 5848 { 5849 using __pop_cat = typename 5850 std::iterator_traits<_PopulationIterator>::iterator_category; 5851 using __samp_cat = typename 5852 std::iterator_traits<_SampleIterator>::iterator_category; 5853 5854 static_assert( 5855 __or_<is_convertible<__pop_cat, forward_iterator_tag>, 5856 is_convertible<__samp_cat, random_access_iterator_tag>>::value, 5857 "output range must use a RandomAccessIterator when input range" 5858 " does not meet the ForwardIterator requirements"); 5859 5860 static_assert(is_integral<_Distance>::value, 5861 "sample size must be an integer type"); 5862 5863 typename iterator_traits<_PopulationIterator>::difference_type __d = __n; 5864 return _GLIBCXX_STD_A:: 5865 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d, 5866 std::forward<_UniformRandomBitGenerator>(__g)); 5867 } 5868 #endif // C++17 5869 #endif // C++14 5870 5871 _GLIBCXX_END_NAMESPACE_ALGO 5872 _GLIBCXX_END_NAMESPACE_VERSION 5873 } // namespace std 5874 5875 #endif /* _STL_ALGO_H */

---

Contact us      |      About us      |      Term of use      |       Copyright © 2000-2024 MyWebUniversity.com ™