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