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