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