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