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