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