1 // Algorithm implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2016 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 #ifdef _GLIBCXX_CONCEPT_CHECKS 1739 typedef typename iterator_traits<_InputIterator>::value_type 1740 _InputValueType __attribute__((__unused__)); 1741 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1742 _OutputValueType __attribute__((__unused__)); 1743 #endif 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_irreflexive(__first, __last); 1754 __glibcxx_requires_valid_range(__result_first, __result_last); 1755 1756 return std::__partial_sort_copy(__first, __last, 1757 __result_first, __result_last, 1758 __gnu_cxx::__ops::__iter_less_iter()); 1759 } 1760 1761 /** 1762 * @brief Copy the smallest elements of a sequence using a predicate for 1763 * comparison. 1764 * @ingroup sorting_algorithms 1765 * @param __first An input iterator. 1766 * @param __last Another input iterator. 1767 * @param __result_first A random-access iterator. 1768 * @param __result_last Another random-access iterator. 1769 * @param __comp A comparison functor. 1770 * @return An iterator indicating the end of the resulting sequence. 1771 * 1772 * Copies and sorts the smallest N values from the range @p [__first,__last) 1773 * to the range beginning at @p result_first, where the number of 1774 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 1775 * @p (__result_last-__result_first). 1776 * After the sort if @e i and @e j are iterators in the range 1777 * @p [__result_first,__result_first+N) such that i precedes j then 1778 * @p __comp(*j,*i) is false. 1779 * The value returned is @p __result_first+N. 1780 */ 1781 template<typename _InputIterator, typename _RandomAccessIterator, 1782 typename _Compare> 1783 inline _RandomAccessIterator 1784 partial_sort_copy(_InputIterator __first, _InputIterator __last, 1785 _RandomAccessIterator __result_first, 1786 _RandomAccessIterator __result_last, 1787 _Compare __comp) 1788 { 1789 #ifdef _GLIBCXX_CONCEPT_CHECKS 1790 typedef typename iterator_traits<_InputIterator>::value_type 1791 _InputValueType __attribute__((__unused__)); 1792 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1793 _OutputValueType __attribute__((__unused__)); 1794 #endif 1795 1796 // concept requirements 1797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1799 _RandomAccessIterator>) 1800 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 1801 _OutputValueType>) 1802 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1803 _InputValueType, _OutputValueType>) 1804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1805 _OutputValueType, _OutputValueType>) 1806 __glibcxx_requires_valid_range(__first, __last); 1807 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 1808 __glibcxx_requires_valid_range(__result_first, __result_last); 1809 1810 return std::__partial_sort_copy(__first, __last, 1811 __result_first, __result_last, 1812 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 1813 } 1814 1815 /// This is a helper function for the sort routine. 1816 template<typename _RandomAccessIterator, typename _Compare> 1817 void 1818 __unguarded_linear_insert(_RandomAccessIterator __last, 1819 _Compare __comp) 1820 { 1821 typename iterator_traits<_RandomAccessIterator>::value_type 1822 __val = _GLIBCXX_MOVE(*__last); 1823 _RandomAccessIterator __next = __last; 1824 --__next; 1825 while (__comp(__val, __next)) 1826 { 1827 *__last = _GLIBCXX_MOVE(*__next); 1828 __last = __next; 1829 --__next; 1830 } 1831 *__last = _GLIBCXX_MOVE(__val); 1832 } 1833 1834 /// This is a helper function for the sort routine. 1835 template<typename _RandomAccessIterator, typename _Compare> 1836 void 1837 __insertion_sort(_RandomAccessIterator __first, 1838 _RandomAccessIterator __last, _Compare __comp) 1839 { 1840 if (__first == __last) return; 1841 1842 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 1843 { 1844 if (__comp(__i, __first)) 1845 { 1846 typename iterator_traits<_RandomAccessIterator>::value_type 1847 __val = _GLIBCXX_MOVE(*__i); 1848 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 1849 *__first = _GLIBCXX_MOVE(__val); 1850 } 1851 else 1852 std::__unguarded_linear_insert(__i, 1853 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1854 } 1855 } 1856 1857 /// This is a helper function for the sort routine. 1858 template<typename _RandomAccessIterator, typename _Compare> 1859 inline void 1860 __unguarded_insertion_sort(_RandomAccessIterator __first, 1861 _RandomAccessIterator __last, _Compare __comp) 1862 { 1863 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 1864 std::__unguarded_linear_insert(__i, 1865 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1866 } 1867 1868 /** 1869 * @doctodo 1870 * This controls some aspect of the sort routines. 1871 */ 1872 enum { _S_threshold = 16 }; 1873 1874 /// This is a helper function for the sort routine. 1875 template<typename _RandomAccessIterator, typename _Compare> 1876 void 1877 __final_insertion_sort(_RandomAccessIterator __first, 1878 _RandomAccessIterator __last, _Compare __comp) 1879 { 1880 if (__last - __first > int(_S_threshold)) 1881 { 1882 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 1883 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 1884 __comp); 1885 } 1886 else 1887 std::__insertion_sort(__first, __last, __comp); 1888 } 1889 1890 /// This is a helper function... 1891 template<typename _RandomAccessIterator, typename _Compare> 1892 _RandomAccessIterator 1893 __unguarded_partition(_RandomAccessIterator __first, 1894 _RandomAccessIterator __last, 1895 _RandomAccessIterator __pivot, _Compare __comp) 1896 { 1897 while (true) 1898 { 1899 while (__comp(__first, __pivot)) 1900 ++__first; 1901 --__last; 1902 while (__comp(__pivot, __last)) 1903 --__last; 1904 if (!(__first < __last)) 1905 return __first; 1906 std::iter_swap(__first, __last); 1907 ++__first; 1908 } 1909 } 1910 1911 /// This is a helper function... 1912 template<typename _RandomAccessIterator, typename _Compare> 1913 inline _RandomAccessIterator 1914 __unguarded_partition_pivot(_RandomAccessIterator __first, 1915 _RandomAccessIterator __last, _Compare __comp) 1916 { 1917 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 1918 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, 1919 __comp); 1920 return std::__unguarded_partition(__first + 1, __last, __first, __comp); 1921 } 1922 1923 template<typename _RandomAccessIterator, typename _Compare> 1924 inline void 1925 __partial_sort(_RandomAccessIterator __first, 1926 _RandomAccessIterator __middle, 1927 _RandomAccessIterator __last, 1928 _Compare __comp) 1929 { 1930 std::__heap_select(__first, __middle, __last, __comp); 1931 std::__sort_heap(__first, __middle, __comp); 1932 } 1933 1934 /// This is a helper function for the sort routine. 1935 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1936 void 1937 __introsort_loop(_RandomAccessIterator __first, 1938 _RandomAccessIterator __last, 1939 _Size __depth_limit, _Compare __comp) 1940 { 1941 while (__last - __first > int(_S_threshold)) 1942 { 1943 if (__depth_limit == 0) 1944 { 1945 std::__partial_sort(__first, __last, __last, __comp); 1946 return; 1947 } 1948 --__depth_limit; 1949 _RandomAccessIterator __cut = 1950 std::__unguarded_partition_pivot(__first, __last, __comp); 1951 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 1952 __last = __cut; 1953 } 1954 } 1955 1956 // sort 1957 1958 template<typename _RandomAccessIterator, typename _Compare> 1959 inline void 1960 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 1961 _Compare __comp) 1962 { 1963 if (__first != __last) 1964 { 1965 std::__introsort_loop(__first, __last, 1966 std::__lg(__last - __first) * 2, 1967 __comp); 1968 std::__final_insertion_sort(__first, __last, __comp); 1969 } 1970 } 1971 1972 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1973 void 1974 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 1975 _RandomAccessIterator __last, _Size __depth_limit, 1976 _Compare __comp) 1977 { 1978 while (__last - __first > 3) 1979 { 1980 if (__depth_limit == 0) 1981 { 1982 std::__heap_select(__first, __nth + 1, __last, __comp); 1983 // Place the nth largest element in its final position. 1984 std::iter_swap(__first, __nth); 1985 return; 1986 } 1987 --__depth_limit; 1988 _RandomAccessIterator __cut = 1989 std::__unguarded_partition_pivot(__first, __last, __comp); 1990 if (__cut <= __nth) 1991 __first = __cut; 1992 else 1993 __last = __cut; 1994 } 1995 std::__insertion_sort(__first, __last, __comp); 1996 } 1997 1998 // nth_element 1999 2000 // lower_bound moved to stl_algobase.h 2001 2002 /** 2003 * @brief Finds the first position in which @p __val could be inserted 2004 * without changing the ordering. 2005 * @ingroup binary_search_algorithms 2006 * @param __first An iterator. 2007 * @param __last Another iterator. 2008 * @param __val The search term. 2009 * @param __comp A functor to use for comparisons. 2010 * @return An iterator pointing to the first element <em>not less 2011 * than</em> @p __val, or end() if every element is less 2012 * than @p __val. 2013 * @ingroup binary_search_algorithms 2014 * 2015 * The comparison function should have the same effects on ordering as 2016 * the function used for the initial sort. 2017 */ 2018 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2019 inline _ForwardIterator 2020 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 2021 const _Tp& __val, _Compare __comp) 2022 { 2023 // concept requirements 2024 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2025 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2026 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2027 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2028 __val, __comp); 2029 2030 return std::__lower_bound(__first, __last, __val, 2031 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2032 } 2033 2034 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2035 _ForwardIterator 2036 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2037 const _Tp& __val, _Compare __comp) 2038 { 2039 typedef typename iterator_traits<_ForwardIterator>::difference_type 2040 _DistanceType; 2041 2042 _DistanceType __len = std::distance(__first, __last); 2043 2044 while (__len > 0) 2045 { 2046 _DistanceType __half = __len >> 1; 2047 _ForwardIterator __middle = __first; 2048 std::advance(__middle, __half); 2049 if (__comp(__val, __middle)) 2050 __len = __half; 2051 else 2052 { 2053 __first = __middle; 2054 ++__first; 2055 __len = __len - __half - 1; 2056 } 2057 } 2058 return __first; 2059 } 2060 2061 /** 2062 * @brief Finds the last position in which @p __val could be inserted 2063 * without changing the ordering. 2064 * @ingroup binary_search_algorithms 2065 * @param __first An iterator. 2066 * @param __last Another iterator. 2067 * @param __val The search term. 2068 * @return An iterator pointing to the first element greater than @p __val, 2069 * or end() if no elements are greater than @p __val. 2070 * @ingroup binary_search_algorithms 2071 */ 2072 template<typename _ForwardIterator, typename _Tp> 2073 inline _ForwardIterator 2074 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2075 const _Tp& __val) 2076 { 2077 // concept requirements 2078 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2079 __glibcxx_function_requires(_LessThanOpConcept< 2080 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2081 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2082 2083 return std::__upper_bound(__first, __last, __val, 2084 __gnu_cxx::__ops::__val_less_iter()); 2085 } 2086 2087 /** 2088 * @brief Finds the last position in which @p __val could be inserted 2089 * without changing the ordering. 2090 * @ingroup binary_search_algorithms 2091 * @param __first An iterator. 2092 * @param __last Another iterator. 2093 * @param __val The search term. 2094 * @param __comp A functor to use for comparisons. 2095 * @return An iterator pointing to the first element greater than @p __val, 2096 * or end() if no elements are greater than @p __val. 2097 * @ingroup binary_search_algorithms 2098 * 2099 * The comparison function should have the same effects on ordering as 2100 * the function used for the initial sort. 2101 */ 2102 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2103 inline _ForwardIterator 2104 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2105 const _Tp& __val, _Compare __comp) 2106 { 2107 // concept requirements 2108 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2109 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2110 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2111 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2112 __val, __comp); 2113 2114 return std::__upper_bound(__first, __last, __val, 2115 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2116 } 2117 2118 template<typename _ForwardIterator, typename _Tp, 2119 typename _CompareItTp, typename _CompareTpIt> 2120 pair<_ForwardIterator, _ForwardIterator> 2121 __equal_range(_ForwardIterator __first, _ForwardIterator __last, 2122 const _Tp& __val, 2123 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) 2124 { 2125 typedef typename iterator_traits<_ForwardIterator>::difference_type 2126 _DistanceType; 2127 2128 _DistanceType __len = std::distance(__first, __last); 2129 2130 while (__len > 0) 2131 { 2132 _DistanceType __half = __len >> 1; 2133 _ForwardIterator __middle = __first; 2134 std::advance(__middle, __half); 2135 if (__comp_it_val(__middle, __val)) 2136 { 2137 __first = __middle; 2138 ++__first; 2139 __len = __len - __half - 1; 2140 } 2141 else if (__comp_val_it(__val, __middle)) 2142 __len = __half; 2143 else 2144 { 2145 _ForwardIterator __left 2146 = std::__lower_bound(__first, __middle, __val, __comp_it_val); 2147 std::advance(__first, __len); 2148 _ForwardIterator __right 2149 = std::__upper_bound(++__middle, __first, __val, __comp_val_it); 2150 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 2151 } 2152 } 2153 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 2154 } 2155 2156 /** 2157 * @brief Finds the largest subrange in which @p __val could be inserted 2158 * at any place in it without changing the ordering. 2159 * @ingroup binary_search_algorithms 2160 * @param __first An iterator. 2161 * @param __last Another iterator. 2162 * @param __val The search term. 2163 * @return An pair of iterators defining the subrange. 2164 * @ingroup binary_search_algorithms 2165 * 2166 * This is equivalent to 2167 * @code 2168 * std::make_pair(lower_bound(__first, __last, __val), 2169 * upper_bound(__first, __last, __val)) 2170 * @endcode 2171 * but does not actually call those functions. 2172 */ 2173 template<typename _ForwardIterator, typename _Tp> 2174 inline pair<_ForwardIterator, _ForwardIterator> 2175 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2176 const _Tp& __val) 2177 { 2178 // concept requirements 2179 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2180 __glibcxx_function_requires(_LessThanOpConcept< 2181 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2182 __glibcxx_function_requires(_LessThanOpConcept< 2183 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2184 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2185 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2186 2187 return std::__equal_range(__first, __last, __val, 2188 __gnu_cxx::__ops::__iter_less_val(), 2189 __gnu_cxx::__ops::__val_less_iter()); 2190 } 2191 2192 /** 2193 * @brief Finds the largest subrange in which @p __val could be inserted 2194 * at any place in it without changing the ordering. 2195 * @param __first An iterator. 2196 * @param __last Another iterator. 2197 * @param __val The search term. 2198 * @param __comp A functor to use for comparisons. 2199 * @return An pair of iterators defining the subrange. 2200 * @ingroup binary_search_algorithms 2201 * 2202 * This is equivalent to 2203 * @code 2204 * std::make_pair(lower_bound(__first, __last, __val, __comp), 2205 * upper_bound(__first, __last, __val, __comp)) 2206 * @endcode 2207 * but does not actually call those functions. 2208 */ 2209 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2210 inline pair<_ForwardIterator, _ForwardIterator> 2211 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2212 const _Tp& __val, _Compare __comp) 2213 { 2214 // concept requirements 2215 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2216 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2217 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2218 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2219 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2220 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2221 __val, __comp); 2222 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2223 __val, __comp); 2224 2225 return std::__equal_range(__first, __last, __val, 2226 __gnu_cxx::__ops::__iter_comp_val(__comp), 2227 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2228 } 2229 2230 /** 2231 * @brief Determines whether an element exists in a range. 2232 * @ingroup binary_search_algorithms 2233 * @param __first An iterator. 2234 * @param __last Another iterator. 2235 * @param __val The search term. 2236 * @return True if @p __val (or its equivalent) is in [@p 2237 * __first,@p __last ]. 2238 * 2239 * Note that this does not actually return an iterator to @p __val. For 2240 * that, use std::find or a container's specialized find member functions. 2241 */ 2242 template<typename _ForwardIterator, typename _Tp> 2243 bool 2244 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2245 const _Tp& __val) 2246 { 2247 // concept requirements 2248 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2249 __glibcxx_function_requires(_LessThanOpConcept< 2250 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2251 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2252 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2253 2254 _ForwardIterator __i 2255 = std::__lower_bound(__first, __last, __val, 2256 __gnu_cxx::__ops::__iter_less_val()); 2257 return __i != __last && !(__val < *__i); 2258 } 2259 2260 /** 2261 * @brief Determines whether an element exists in a range. 2262 * @ingroup binary_search_algorithms 2263 * @param __first An iterator. 2264 * @param __last Another iterator. 2265 * @param __val The search term. 2266 * @param __comp A functor to use for comparisons. 2267 * @return True if @p __val (or its equivalent) is in @p [__first,__last]. 2268 * 2269 * Note that this does not actually return an iterator to @p __val. For 2270 * that, use std::find or a container's specialized find member functions. 2271 * 2272 * The comparison function should have the same effects on ordering as 2273 * the function used for the initial sort. 2274 */ 2275 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2276 bool 2277 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2278 const _Tp& __val, _Compare __comp) 2279 { 2280 // concept requirements 2281 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2282 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2283 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2284 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2285 __val, __comp); 2286 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2287 __val, __comp); 2288 2289 _ForwardIterator __i 2290 = std::__lower_bound(__first, __last, __val, 2291 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2292 return __i != __last && !bool(__comp(__val, *__i)); 2293 } 2294 2295 // merge 2296 2297 /// This is a helper function for the __merge_adaptive routines. 2298 template<typename _InputIterator1, typename _InputIterator2, 2299 typename _OutputIterator, typename _Compare> 2300 void 2301 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 2302 _InputIterator2 __first2, _InputIterator2 __last2, 2303 _OutputIterator __result, _Compare __comp) 2304 { 2305 while (__first1 != __last1 && __first2 != __last2) 2306 { 2307 if (__comp(__first2, __first1)) 2308 { 2309 *__result = _GLIBCXX_MOVE(*__first2); 2310 ++__first2; 2311 } 2312 else 2313 { 2314 *__result = _GLIBCXX_MOVE(*__first1); 2315 ++__first1; 2316 } 2317 ++__result; 2318 } 2319 if (__first1 != __last1) 2320 _GLIBCXX_MOVE3(__first1, __last1, __result); 2321 } 2322 2323 /// This is a helper function for the __merge_adaptive routines. 2324 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2325 typename _BidirectionalIterator3, typename _Compare> 2326 void 2327 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 2328 _BidirectionalIterator1 __last1, 2329 _BidirectionalIterator2 __first2, 2330 _BidirectionalIterator2 __last2, 2331 _BidirectionalIterator3 __result, 2332 _Compare __comp) 2333 { 2334 if (__first1 == __last1) 2335 { 2336 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 2337 return; 2338 } 2339 else if (__first2 == __last2) 2340 return; 2341 2342 --__last1; 2343 --__last2; 2344 while (true) 2345 { 2346 if (__comp(__last2, __last1)) 2347 { 2348 *--__result = _GLIBCXX_MOVE(*__last1); 2349 if (__first1 == __last1) 2350 { 2351 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 2352 return; 2353 } 2354 --__last1; 2355 } 2356 else 2357 { 2358 *--__result = _GLIBCXX_MOVE(*__last2); 2359 if (__first2 == __last2) 2360 return; 2361 --__last2; 2362 } 2363 } 2364 } 2365 2366 /// This is a helper function for the merge routines. 2367 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2368 typename _Distance> 2369 _BidirectionalIterator1 2370 __rotate_adaptive(_BidirectionalIterator1 __first, 2371 _BidirectionalIterator1 __middle, 2372 _BidirectionalIterator1 __last, 2373 _Distance __len1, _Distance __len2, 2374 _BidirectionalIterator2 __buffer, 2375 _Distance __buffer_size) 2376 { 2377 _BidirectionalIterator2 __buffer_end; 2378 if (__len1 > __len2 && __len2 <= __buffer_size) 2379 { 2380 if (__len2) 2381 { 2382 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2383 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 2384 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 2385 } 2386 else 2387 return __first; 2388 } 2389 else if (__len1 <= __buffer_size) 2390 { 2391 if (__len1) 2392 { 2393 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2394 _GLIBCXX_MOVE3(__middle, __last, __first); 2395 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 2396 } 2397 else 2398 return __last; 2399 } 2400 else 2401 { 2402 std::rotate(__first, __middle, __last); 2403 std::advance(__first, std::distance(__middle, __last)); 2404 return __first; 2405 } 2406 } 2407 2408 /// This is a helper function for the merge routines. 2409 template<typename _BidirectionalIterator, typename _Distance, 2410 typename _Pointer, typename _Compare> 2411 void 2412 __merge_adaptive(_BidirectionalIterator __first, 2413 _BidirectionalIterator __middle, 2414 _BidirectionalIterator __last, 2415 _Distance __len1, _Distance __len2, 2416 _Pointer __buffer, _Distance __buffer_size, 2417 _Compare __comp) 2418 { 2419 if (__len1 <= __len2 && __len1 <= __buffer_size) 2420 { 2421 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2422 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 2423 __first, __comp); 2424 } 2425 else if (__len2 <= __buffer_size) 2426 { 2427 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2428 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 2429 __buffer_end, __last, __comp); 2430 } 2431 else 2432 { 2433 _BidirectionalIterator __first_cut = __first; 2434 _BidirectionalIterator __second_cut = __middle; 2435 _Distance __len11 = 0; 2436 _Distance __len22 = 0; 2437 if (__len1 > __len2) 2438 { 2439 __len11 = __len1 / 2; 2440 std::advance(__first_cut, __len11); 2441 __second_cut 2442 = std::__lower_bound(__middle, __last, *__first_cut, 2443 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2444 __len22 = std::distance(__middle, __second_cut); 2445 } 2446 else 2447 { 2448 __len22 = __len2 / 2; 2449 std::advance(__second_cut, __len22); 2450 __first_cut 2451 = std::__upper_bound(__first, __middle, *__second_cut, 2452 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2453 __len11 = std::distance(__first, __first_cut); 2454 } 2455 2456 _BidirectionalIterator __new_middle 2457 = std::__rotate_adaptive(__first_cut, __middle, __second_cut, 2458 __len1 - __len11, __len22, __buffer, 2459 __buffer_size); 2460 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 2461 __len22, __buffer, __buffer_size, __comp); 2462 std::__merge_adaptive(__new_middle, __second_cut, __last, 2463 __len1 - __len11, 2464 __len2 - __len22, __buffer, 2465 __buffer_size, __comp); 2466 } 2467 } 2468 2469 /// This is a helper function for the merge routines. 2470 template<typename _BidirectionalIterator, typename _Distance, 2471 typename _Compare> 2472 void 2473 __merge_without_buffer(_BidirectionalIterator __first, 2474 _BidirectionalIterator __middle, 2475 _BidirectionalIterator __last, 2476 _Distance __len1, _Distance __len2, 2477 _Compare __comp) 2478 { 2479 if (__len1 == 0 || __len2 == 0) 2480 return; 2481 2482 if (__len1 + __len2 == 2) 2483 { 2484 if (__comp(__middle, __first)) 2485 std::iter_swap(__first, __middle); 2486 return; 2487 } 2488 2489 _BidirectionalIterator __first_cut = __first; 2490 _BidirectionalIterator __second_cut = __middle; 2491 _Distance __len11 = 0; 2492 _Distance __len22 = 0; 2493 if (__len1 > __len2) 2494 { 2495 __len11 = __len1 / 2; 2496 std::advance(__first_cut, __len11); 2497 __second_cut 2498 = std::__lower_bound(__middle, __last, *__first_cut, 2499 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2500 __len22 = std::distance(__middle, __second_cut); 2501 } 2502 else 2503 { 2504 __len22 = __len2 / 2; 2505 std::advance(__second_cut, __len22); 2506 __first_cut 2507 = std::__upper_bound(__first, __middle, *__second_cut, 2508 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2509 __len11 = std::distance(__first, __first_cut); 2510 } 2511 2512 std::rotate(__first_cut, __middle, __second_cut); 2513 _BidirectionalIterator __new_middle = __first_cut; 2514 std::advance(__new_middle, std::distance(__middle, __second_cut)); 2515 std::__merge_without_buffer(__first, __first_cut, __new_middle, 2516 __len11, __len22, __comp); 2517 std::__merge_without_buffer(__new_middle, __second_cut, __last, 2518 __len1 - __len11, __len2 - __len22, __comp); 2519 } 2520 2521 template<typename _BidirectionalIterator, typename _Compare> 2522 void 2523 __inplace_merge(_BidirectionalIterator __first, 2524 _BidirectionalIterator __middle, 2525 _BidirectionalIterator __last, 2526 _Compare __comp) 2527 { 2528 typedef typename iterator_traits<_BidirectionalIterator>::value_type 2529 _ValueType; 2530 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 2531 _DistanceType; 2532 2533 if (__first == __middle || __middle == __last) 2534 return; 2535 2536 const _DistanceType __len1 = std::distance(__first, __middle); 2537 const _DistanceType __len2 = std::distance(__middle, __last); 2538 2539 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf; 2540 _TmpBuf __buf(__first, __last); 2541 2542 if (__buf.begin() == 0) 2543 std::__merge_without_buffer 2544 (__first, __middle, __last, __len1, __len2, __comp); 2545 else 2546 std::__merge_adaptive 2547 (__first, __middle, __last, __len1, __len2, __buf.begin(), 2548 _DistanceType(__buf.size()), __comp); 2549 } 2550 2551 /** 2552 * @brief Merges two sorted ranges in place. 2553 * @ingroup sorting_algorithms 2554 * @param __first An iterator. 2555 * @param __middle Another iterator. 2556 * @param __last Another iterator. 2557 * @return Nothing. 2558 * 2559 * Merges two sorted and consecutive ranges, [__first,__middle) and 2560 * [__middle,__last), and puts the result in [__first,__last). The 2561 * output will be sorted. The sort is @e stable, that is, for 2562 * equivalent elements in the two ranges, elements from the first 2563 * range will always come before elements from the second. 2564 * 2565 * If enough additional memory is available, this takes (__last-__first)-1 2566 * comparisons. Otherwise an NlogN algorithm is used, where N is 2567 * distance(__first,__last). 2568 */ 2569 template<typename _BidirectionalIterator> 2570 inline void 2571 inplace_merge(_BidirectionalIterator __first, 2572 _BidirectionalIterator __middle, 2573 _BidirectionalIterator __last) 2574 { 2575 // concept requirements 2576 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2577 _BidirectionalIterator>) 2578 __glibcxx_function_requires(_LessThanComparableConcept< 2579 typename iterator_traits<_BidirectionalIterator>::value_type>) 2580 __glibcxx_requires_sorted(__first, __middle); 2581 __glibcxx_requires_sorted(__middle, __last); 2582 __glibcxx_requires_irreflexive(__first, __last); 2583 2584 std::__inplace_merge(__first, __middle, __last, 2585 __gnu_cxx::__ops::__iter_less_iter()); 2586 } 2587 2588 /** 2589 * @brief Merges two sorted ranges in place. 2590 * @ingroup sorting_algorithms 2591 * @param __first An iterator. 2592 * @param __middle Another iterator. 2593 * @param __last Another iterator. 2594 * @param __comp A functor to use for comparisons. 2595 * @return Nothing. 2596 * 2597 * Merges two sorted and consecutive ranges, [__first,__middle) and 2598 * [middle,last), and puts the result in [__first,__last). The output will 2599 * be sorted. The sort is @e stable, that is, for equivalent 2600 * elements in the two ranges, elements from the first range will always 2601 * come before elements from the second. 2602 * 2603 * If enough additional memory is available, this takes (__last-__first)-1 2604 * comparisons. Otherwise an NlogN algorithm is used, where N is 2605 * distance(__first,__last). 2606 * 2607 * The comparison function should have the same effects on ordering as 2608 * the function used for the initial sort. 2609 */ 2610 template<typename _BidirectionalIterator, typename _Compare> 2611 inline void 2612 inplace_merge(_BidirectionalIterator __first, 2613 _BidirectionalIterator __middle, 2614 _BidirectionalIterator __last, 2615 _Compare __comp) 2616 { 2617 // concept requirements 2618 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2619 _BidirectionalIterator>) 2620 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2621 typename iterator_traits<_BidirectionalIterator>::value_type, 2622 typename iterator_traits<_BidirectionalIterator>::value_type>) 2623 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 2624 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 2625 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2626 2627 std::__inplace_merge(__first, __middle, __last, 2628 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2629 } 2630 2631 2632 /// This is a helper function for the __merge_sort_loop routines. 2633 template<typename _InputIterator, typename _OutputIterator, 2634 typename _Compare> 2635 _OutputIterator 2636 __move_merge(_InputIterator __first1, _InputIterator __last1, 2637 _InputIterator __first2, _InputIterator __last2, 2638 _OutputIterator __result, _Compare __comp) 2639 { 2640 while (__first1 != __last1 && __first2 != __last2) 2641 { 2642 if (__comp(__first2, __first1)) 2643 { 2644 *__result = _GLIBCXX_MOVE(*__first2); 2645 ++__first2; 2646 } 2647 else 2648 { 2649 *__result = _GLIBCXX_MOVE(*__first1); 2650 ++__first1; 2651 } 2652 ++__result; 2653 } 2654 return _GLIBCXX_MOVE3(__first2, __last2, 2655 _GLIBCXX_MOVE3(__first1, __last1, 2656 __result)); 2657 } 2658 2659 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 2660 typename _Distance, typename _Compare> 2661 void 2662 __merge_sort_loop(_RandomAccessIterator1 __first, 2663 _RandomAccessIterator1 __last, 2664 _RandomAccessIterator2 __result, _Distance __step_size, 2665 _Compare __comp) 2666 { 2667 const _Distance __two_step = 2 * __step_size; 2668 2669 while (__last - __first >= __two_step) 2670 { 2671 __result = std::__move_merge(__first, __first + __step_size, 2672 __first + __step_size, 2673 __first + __two_step, 2674 __result, __comp); 2675 __first += __two_step; 2676 } 2677 __step_size = std::min(_Distance(__last - __first), __step_size); 2678 2679 std::__move_merge(__first, __first + __step_size, 2680 __first + __step_size, __last, __result, __comp); 2681 } 2682 2683 template<typename _RandomAccessIterator, typename _Distance, 2684 typename _Compare> 2685 void 2686 __chunk_insertion_sort(_RandomAccessIterator __first, 2687 _RandomAccessIterator __last, 2688 _Distance __chunk_size, _Compare __comp) 2689 { 2690 while (__last - __first >= __chunk_size) 2691 { 2692 std::__insertion_sort(__first, __first + __chunk_size, __comp); 2693 __first += __chunk_size; 2694 } 2695 std::__insertion_sort(__first, __last, __comp); 2696 } 2697 2698 enum { _S_chunk_size = 7 }; 2699 2700 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 2701 void 2702 __merge_sort_with_buffer(_RandomAccessIterator __first, 2703 _RandomAccessIterator __last, 2704 _Pointer __buffer, _Compare __comp) 2705 { 2706 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2707 _Distance; 2708 2709 const _Distance __len = __last - __first; 2710 const _Pointer __buffer_last = __buffer + __len; 2711 2712 _Distance __step_size = _S_chunk_size; 2713 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 2714 2715 while (__step_size < __len) 2716 { 2717 std::__merge_sort_loop(__first, __last, __buffer, 2718 __step_size, __comp); 2719 __step_size *= 2; 2720 std::__merge_sort_loop(__buffer, __buffer_last, __first, 2721 __step_size, __comp); 2722 __step_size *= 2; 2723 } 2724 } 2725 2726 template<typename _RandomAccessIterator, typename _Pointer, 2727 typename _Distance, typename _Compare> 2728 void 2729 __stable_sort_adaptive(_RandomAccessIterator __first, 2730 _RandomAccessIterator __last, 2731 _Pointer __buffer, _Distance __buffer_size, 2732 _Compare __comp) 2733 { 2734 const _Distance __len = (__last - __first + 1) / 2; 2735 const _RandomAccessIterator __middle = __first + __len; 2736 if (__len > __buffer_size) 2737 { 2738 std::__stable_sort_adaptive(__first, __middle, __buffer, 2739 __buffer_size, __comp); 2740 std::__stable_sort_adaptive(__middle, __last, __buffer, 2741 __buffer_size, __comp); 2742 } 2743 else 2744 { 2745 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 2746 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 2747 } 2748 std::__merge_adaptive(__first, __middle, __last, 2749 _Distance(__middle - __first), 2750 _Distance(__last - __middle), 2751 __buffer, __buffer_size, 2752 __comp); 2753 } 2754 2755 /// This is a helper function for the stable sorting routines. 2756 template<typename _RandomAccessIterator, typename _Compare> 2757 void 2758 __inplace_stable_sort(_RandomAccessIterator __first, 2759 _RandomAccessIterator __last, _Compare __comp) 2760 { 2761 if (__last - __first < 15) 2762 { 2763 std::__insertion_sort(__first, __last, __comp); 2764 return; 2765 } 2766 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 2767 std::__inplace_stable_sort(__first, __middle, __comp); 2768 std::__inplace_stable_sort(__middle, __last, __comp); 2769 std::__merge_without_buffer(__first, __middle, __last, 2770 __middle - __first, 2771 __last - __middle, 2772 __comp); 2773 } 2774 2775 // stable_sort 2776 2777 // Set algorithms: includes, set_union, set_intersection, set_difference, 2778 // set_symmetric_difference. All of these algorithms have the precondition 2779 // that their input ranges are sorted and the postcondition that their output 2780 // ranges are sorted. 2781 2782 template<typename _InputIterator1, typename _InputIterator2, 2783 typename _Compare> 2784 bool 2785 __includes(_InputIterator1 __first1, _InputIterator1 __last1, 2786 _InputIterator2 __first2, _InputIterator2 __last2, 2787 _Compare __comp) 2788 { 2789 while (__first1 != __last1 && __first2 != __last2) 2790 if (__comp(__first2, __first1)) 2791 return false; 2792 else if (__comp(__first1, __first2)) 2793 ++__first1; 2794 else 2795 { 2796 ++__first1; 2797 ++__first2; 2798 } 2799 2800 return __first2 == __last2; 2801 } 2802 2803 /** 2804 * @brief Determines whether all elements of a sequence exists in a range. 2805 * @param __first1 Start of search range. 2806 * @param __last1 End of search range. 2807 * @param __first2 Start of sequence 2808 * @param __last2 End of sequence. 2809 * @return True if each element in [__first2,__last2) is contained in order 2810 * within [__first1,__last1). False otherwise. 2811 * @ingroup set_algorithms 2812 * 2813 * This operation expects both [__first1,__last1) and 2814 * [__first2,__last2) to be sorted. Searches for the presence of 2815 * each element in [__first2,__last2) within [__first1,__last1). 2816 * The iterators over each range only move forward, so this is a 2817 * linear algorithm. If an element in [__first2,__last2) is not 2818 * found before the search iterator reaches @p __last2, false is 2819 * returned. 2820 */ 2821 template<typename _InputIterator1, typename _InputIterator2> 2822 inline bool 2823 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2824 _InputIterator2 __first2, _InputIterator2 __last2) 2825 { 2826 // concept requirements 2827 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2828 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2829 __glibcxx_function_requires(_LessThanOpConcept< 2830 typename iterator_traits<_InputIterator1>::value_type, 2831 typename iterator_traits<_InputIterator2>::value_type>) 2832 __glibcxx_function_requires(_LessThanOpConcept< 2833 typename iterator_traits<_InputIterator2>::value_type, 2834 typename iterator_traits<_InputIterator1>::value_type>) 2835 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 2836 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 2837 __glibcxx_requires_irreflexive2(__first1, __last1); 2838 __glibcxx_requires_irreflexive2(__first2, __last2); 2839 2840 return std::__includes(__first1, __last1, __first2, __last2, 2841 __gnu_cxx::__ops::__iter_less_iter()); 2842 } 2843 2844 /** 2845 * @brief Determines whether all elements of a sequence exists in a range 2846 * using comparison. 2847 * @ingroup set_algorithms 2848 * @param __first1 Start of search range. 2849 * @param __last1 End of search range. 2850 * @param __first2 Start of sequence 2851 * @param __last2 End of sequence. 2852 * @param __comp Comparison function to use. 2853 * @return True if each element in [__first2,__last2) is contained 2854 * in order within [__first1,__last1) according to comp. False 2855 * otherwise. @ingroup set_algorithms 2856 * 2857 * This operation expects both [__first1,__last1) and 2858 * [__first2,__last2) to be sorted. Searches for the presence of 2859 * each element in [__first2,__last2) within [__first1,__last1), 2860 * using comp to decide. The iterators over each range only move 2861 * forward, so this is a linear algorithm. If an element in 2862 * [__first2,__last2) is not found before the search iterator 2863 * reaches @p __last2, false is returned. 2864 */ 2865 template<typename _InputIterator1, typename _InputIterator2, 2866 typename _Compare> 2867 inline bool 2868 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2869 _InputIterator2 __first2, _InputIterator2 __last2, 2870 _Compare __comp) 2871 { 2872 // concept requirements 2873 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2874 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2875 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2876 typename iterator_traits<_InputIterator1>::value_type, 2877 typename iterator_traits<_InputIterator2>::value_type>) 2878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2879 typename iterator_traits<_InputIterator2>::value_type, 2880 typename iterator_traits<_InputIterator1>::value_type>) 2881 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 2882 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 2883 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 2884 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 2885 2886 return std::__includes(__first1, __last1, __first2, __last2, 2887 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2888 } 2889 2890 // nth_element 2891 // merge 2892 // set_difference 2893 // set_intersection 2894 // set_union 2895 // stable_sort 2896 // set_symmetric_difference 2897 // min_element 2898 // max_element 2899 2900 template<typename _BidirectionalIterator, typename _Compare> 2901 bool 2902 __next_permutation(_BidirectionalIterator __first, 2903 _BidirectionalIterator __last, _Compare __comp) 2904 { 2905 if (__first == __last) 2906 return false; 2907 _BidirectionalIterator __i = __first; 2908 ++__i; 2909 if (__i == __last) 2910 return false; 2911 __i = __last; 2912 --__i; 2913 2914 for(;;) 2915 { 2916 _BidirectionalIterator __ii = __i; 2917 --__i; 2918 if (__comp(__i, __ii)) 2919 { 2920 _BidirectionalIterator __j = __last; 2921 while (!__comp(__i, --__j)) 2922 {} 2923 std::iter_swap(__i, __j); 2924 std::__reverse(__ii, __last, 2925 std::__iterator_category(__first)); 2926 return true; 2927 } 2928 if (__i == __first) 2929 { 2930 std::__reverse(__first, __last, 2931 std::__iterator_category(__first)); 2932 return false; 2933 } 2934 } 2935 } 2936 2937 /** 2938 * @brief Permute range into the next @e dictionary ordering. 2939 * @ingroup sorting_algorithms 2940 * @param __first Start of range. 2941 * @param __last End of range. 2942 * @return False if wrapped to first permutation, true otherwise. 2943 * 2944 * Treats all permutations of the range as a set of @e dictionary sorted 2945 * sequences. Permutes the current sequence into the next one of this set. 2946 * Returns true if there are more sequences to generate. If the sequence 2947 * is the largest of the set, the smallest is generated and false returned. 2948 */ 2949 template<typename _BidirectionalIterator> 2950 inline bool 2951 next_permutation(_BidirectionalIterator __first, 2952 _BidirectionalIterator __last) 2953 { 2954 // concept requirements 2955 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2956 _BidirectionalIterator>) 2957 __glibcxx_function_requires(_LessThanComparableConcept< 2958 typename iterator_traits<_BidirectionalIterator>::value_type>) 2959 __glibcxx_requires_valid_range(__first, __last); 2960 __glibcxx_requires_irreflexive(__first, __last); 2961 2962 return std::__next_permutation 2963 (__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 2964 } 2965 2966 /** 2967 * @brief Permute range into the next @e dictionary ordering using 2968 * comparison functor. 2969 * @ingroup sorting_algorithms 2970 * @param __first Start of range. 2971 * @param __last End of range. 2972 * @param __comp A comparison functor. 2973 * @return False if wrapped to first permutation, true otherwise. 2974 * 2975 * Treats all permutations of the range [__first,__last) as a set of 2976 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 2977 * sequence into the next one of this set. Returns true if there are more 2978 * sequences to generate. If the sequence is the largest of the set, the 2979 * smallest is generated and false returned. 2980 */ 2981 template<typename _BidirectionalIterator, typename _Compare> 2982 inline bool 2983 next_permutation(_BidirectionalIterator __first, 2984 _BidirectionalIterator __last, _Compare __comp) 2985 { 2986 // concept requirements 2987 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2988 _BidirectionalIterator>) 2989 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2990 typename iterator_traits<_BidirectionalIterator>::value_type, 2991 typename iterator_traits<_BidirectionalIterator>::value_type>) 2992 __glibcxx_requires_valid_range(__first, __last); 2993 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2994 2995 return std::__next_permutation 2996 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2997 } 2998 2999 template<typename _BidirectionalIterator, typename _Compare> 3000 bool 3001 __prev_permutation(_BidirectionalIterator __first, 3002 _BidirectionalIterator __last, _Compare __comp) 3003 { 3004 if (__first == __last) 3005 return false; 3006 _BidirectionalIterator __i = __first; 3007 ++__i; 3008 if (__i == __last) 3009 return false; 3010 __i = __last; 3011 --__i; 3012 3013 for(;;) 3014 { 3015 _BidirectionalIterator __ii = __i; 3016 --__i; 3017 if (__comp(__ii, __i)) 3018 { 3019 _BidirectionalIterator __j = __last; 3020 while (!__comp(--__j, __i)) 3021 {} 3022 std::iter_swap(__i, __j); 3023 std::__reverse(__ii, __last, 3024 std::__iterator_category(__first)); 3025 return true; 3026 } 3027 if (__i == __first) 3028 { 3029 std::__reverse(__first, __last, 3030 std::__iterator_category(__first)); 3031 return false; 3032 } 3033 } 3034 } 3035 3036 /** 3037 * @brief Permute range into the previous @e dictionary ordering. 3038 * @ingroup sorting_algorithms 3039 * @param __first Start of range. 3040 * @param __last End of range. 3041 * @return False if wrapped to last permutation, true otherwise. 3042 * 3043 * Treats all permutations of the range as a set of @e dictionary sorted 3044 * sequences. Permutes the current sequence into the previous one of this 3045 * set. Returns true if there are more sequences to generate. If the 3046 * sequence is the smallest of the set, the largest is generated and false 3047 * returned. 3048 */ 3049 template<typename _BidirectionalIterator> 3050 inline bool 3051 prev_permutation(_BidirectionalIterator __first, 3052 _BidirectionalIterator __last) 3053 { 3054 // concept requirements 3055 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3056 _BidirectionalIterator>) 3057 __glibcxx_function_requires(_LessThanComparableConcept< 3058 typename iterator_traits<_BidirectionalIterator>::value_type>) 3059 __glibcxx_requires_valid_range(__first, __last); 3060 __glibcxx_requires_irreflexive(__first, __last); 3061 3062 return std::__prev_permutation(__first, __last, 3063 __gnu_cxx::__ops::__iter_less_iter()); 3064 } 3065 3066 /** 3067 * @brief Permute range into the previous @e dictionary ordering using 3068 * comparison functor. 3069 * @ingroup sorting_algorithms 3070 * @param __first Start of range. 3071 * @param __last End of range. 3072 * @param __comp A comparison functor. 3073 * @return False if wrapped to last permutation, true otherwise. 3074 * 3075 * Treats all permutations of the range [__first,__last) as a set of 3076 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 3077 * sequence into the previous one of this set. Returns true if there are 3078 * more sequences to generate. If the sequence is the smallest of the set, 3079 * the largest is generated and false returned. 3080 */ 3081 template<typename _BidirectionalIterator, typename _Compare> 3082 inline bool 3083 prev_permutation(_BidirectionalIterator __first, 3084 _BidirectionalIterator __last, _Compare __comp) 3085 { 3086 // concept requirements 3087 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3088 _BidirectionalIterator>) 3089 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3090 typename iterator_traits<_BidirectionalIterator>::value_type, 3091 typename iterator_traits<_BidirectionalIterator>::value_type>) 3092 __glibcxx_requires_valid_range(__first, __last); 3093 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3094 3095 return std::__prev_permutation(__first, __last, 3096 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3097 } 3098 3099 // replace 3100 // replace_if 3101 3102 template<typename _InputIterator, typename _OutputIterator, 3103 typename _Predicate, typename _Tp> 3104 _OutputIterator 3105 __replace_copy_if(_InputIterator __first, _InputIterator __last, 3106 _OutputIterator __result, 3107 _Predicate __pred, const _Tp& __new_value) 3108 { 3109 for (; __first != __last; ++__first, (void)++__result) 3110 if (__pred(__first)) 3111 *__result = __new_value; 3112 else 3113 *__result = *__first; 3114 return __result; 3115 } 3116 3117 /** 3118 * @brief Copy a sequence, replacing each element of one value with another 3119 * value. 3120 * @param __first An input iterator. 3121 * @param __last An input iterator. 3122 * @param __result An output iterator. 3123 * @param __old_value The value to be replaced. 3124 * @param __new_value The replacement value. 3125 * @return The end of the output sequence, @p result+(last-first). 3126 * 3127 * Copies each element in the input range @p [__first,__last) to the 3128 * output range @p [__result,__result+(__last-__first)) replacing elements 3129 * equal to @p __old_value with @p __new_value. 3130 */ 3131 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 3132 inline _OutputIterator 3133 replace_copy(_InputIterator __first, _InputIterator __last, 3134 _OutputIterator __result, 3135 const _Tp& __old_value, const _Tp& __new_value) 3136 { 3137 // concept requirements 3138 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3139 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3140 typename iterator_traits<_InputIterator>::value_type>) 3141 __glibcxx_function_requires(_EqualOpConcept< 3142 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3143 __glibcxx_requires_valid_range(__first, __last); 3144 3145 return std::__replace_copy_if(__first, __last, __result, 3146 __gnu_cxx::__ops::__iter_equals_val(__old_value), 3147 __new_value); 3148 } 3149 3150 /** 3151 * @brief Copy a sequence, replacing each value for which a predicate 3152 * returns true with another value. 3153 * @ingroup mutating_algorithms 3154 * @param __first An input iterator. 3155 * @param __last An input iterator. 3156 * @param __result An output iterator. 3157 * @param __pred A predicate. 3158 * @param __new_value The replacement value. 3159 * @return The end of the output sequence, @p __result+(__last-__first). 3160 * 3161 * Copies each element in the range @p [__first,__last) to the range 3162 * @p [__result,__result+(__last-__first)) replacing elements for which 3163 * @p __pred returns true with @p __new_value. 3164 */ 3165 template<typename _InputIterator, typename _OutputIterator, 3166 typename _Predicate, typename _Tp> 3167 inline _OutputIterator 3168 replace_copy_if(_InputIterator __first, _InputIterator __last, 3169 _OutputIterator __result, 3170 _Predicate __pred, const _Tp& __new_value) 3171 { 3172 // concept requirements 3173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3174 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3175 typename iterator_traits<_InputIterator>::value_type>) 3176 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3177 typename iterator_traits<_InputIterator>::value_type>) 3178 __glibcxx_requires_valid_range(__first, __last); 3179 3180 return std::__replace_copy_if(__first, __last, __result, 3181 __gnu_cxx::__ops::__pred_iter(__pred), 3182 __new_value); 3183 } 3184 3185 template<typename _InputIterator, typename _Predicate> 3186 typename iterator_traits<_InputIterator>::difference_type 3187 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 3188 { 3189 typename iterator_traits<_InputIterator>::difference_type __n = 0; 3190 for (; __first != __last; ++__first) 3191 if (__pred(__first)) 3192 ++__n; 3193 return __n; 3194 } 3195 3196 #if __cplusplus >= 201103L 3197 /** 3198 * @brief Determines whether the elements of a sequence are sorted. 3199 * @ingroup sorting_algorithms 3200 * @param __first An iterator. 3201 * @param __last Another iterator. 3202 * @return True if the elements are sorted, false otherwise. 3203 */ 3204 template<typename _ForwardIterator> 3205 inline bool 3206 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3207 { return std::is_sorted_until(__first, __last) == __last; } 3208 3209 /** 3210 * @brief Determines whether the elements of a sequence are sorted 3211 * according to a comparison functor. 3212 * @ingroup sorting_algorithms 3213 * @param __first An iterator. 3214 * @param __last Another iterator. 3215 * @param __comp A comparison functor. 3216 * @return True if the elements are sorted, false otherwise. 3217 */ 3218 template<typename _ForwardIterator, typename _Compare> 3219 inline bool 3220 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 3221 _Compare __comp) 3222 { return std::is_sorted_until(__first, __last, __comp) == __last; } 3223 3224 template<typename _ForwardIterator, typename _Compare> 3225 _ForwardIterator 3226 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3227 _Compare __comp) 3228 { 3229 if (__first == __last) 3230 return __last; 3231 3232 _ForwardIterator __next = __first; 3233 for (++__next; __next != __last; __first = __next, (void)++__next) 3234 if (__comp(__next, __first)) 3235 return __next; 3236 return __next; 3237 } 3238 3239 /** 3240 * @brief Determines the end of a sorted sequence. 3241 * @ingroup sorting_algorithms 3242 * @param __first An iterator. 3243 * @param __last Another iterator. 3244 * @return An iterator pointing to the last iterator i in [__first, __last) 3245 * for which the range [__first, i) is sorted. 3246 */ 3247 template<typename _ForwardIterator> 3248 inline _ForwardIterator 3249 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3250 { 3251 // concept requirements 3252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3253 __glibcxx_function_requires(_LessThanComparableConcept< 3254 typename iterator_traits<_ForwardIterator>::value_type>) 3255 __glibcxx_requires_valid_range(__first, __last); 3256 __glibcxx_requires_irreflexive(__first, __last); 3257 3258 return std::__is_sorted_until(__first, __last, 3259 __gnu_cxx::__ops::__iter_less_iter()); 3260 } 3261 3262 /** 3263 * @brief Determines the end of a sorted sequence using comparison functor. 3264 * @ingroup sorting_algorithms 3265 * @param __first An iterator. 3266 * @param __last Another iterator. 3267 * @param __comp A comparison functor. 3268 * @return An iterator pointing to the last iterator i in [__first, __last) 3269 * for which the range [__first, i) is sorted. 3270 */ 3271 template<typename _ForwardIterator, typename _Compare> 3272 inline _ForwardIterator 3273 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3274 _Compare __comp) 3275 { 3276 // concept requirements 3277 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3278 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3279 typename iterator_traits<_ForwardIterator>::value_type, 3280 typename iterator_traits<_ForwardIterator>::value_type>) 3281 __glibcxx_requires_valid_range(__first, __last); 3282 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 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 __glibcxx_requires_irreflexive(__first, __last); 3408 3409 return std::__minmax_element(__first, __last, 3410 __gnu_cxx::__ops::__iter_less_iter()); 3411 } 3412 3413 /** 3414 * @brief Return a pair of iterators pointing to the minimum and maximum 3415 * elements in a range. 3416 * @ingroup sorting_algorithms 3417 * @param __first Start of range. 3418 * @param __last End of range. 3419 * @param __comp Comparison functor. 3420 * @return make_pair(m, M), where m is the first iterator i in 3421 * [__first, __last) such that no other element in the range is 3422 * smaller, and where M is the last iterator i in [__first, __last) 3423 * such that no other element in the range is larger. 3424 */ 3425 template<typename _ForwardIterator, typename _Compare> 3426 _GLIBCXX14_CONSTEXPR 3427 inline pair<_ForwardIterator, _ForwardIterator> 3428 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 3429 _Compare __comp) 3430 { 3431 // concept requirements 3432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3433 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3434 typename iterator_traits<_ForwardIterator>::value_type, 3435 typename iterator_traits<_ForwardIterator>::value_type>) 3436 __glibcxx_requires_valid_range(__first, __last); 3437 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3438 3439 return std::__minmax_element(__first, __last, 3440 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3441 } 3442 3443 // N2722 + DR 915. 3444 template<typename _Tp> 3445 _GLIBCXX14_CONSTEXPR 3446 inline _Tp 3447 min(initializer_list<_Tp> __l) 3448 { return *std::min_element(__l.begin(), __l.end()); } 3449 3450 template<typename _Tp, typename _Compare> 3451 _GLIBCXX14_CONSTEXPR 3452 inline _Tp 3453 min(initializer_list<_Tp> __l, _Compare __comp) 3454 { return *std::min_element(__l.begin(), __l.end(), __comp); } 3455 3456 template<typename _Tp> 3457 _GLIBCXX14_CONSTEXPR 3458 inline _Tp 3459 max(initializer_list<_Tp> __l) 3460 { return *std::max_element(__l.begin(), __l.end()); } 3461 3462 template<typename _Tp, typename _Compare> 3463 _GLIBCXX14_CONSTEXPR 3464 inline _Tp 3465 max(initializer_list<_Tp> __l, _Compare __comp) 3466 { return *std::max_element(__l.begin(), __l.end(), __comp); } 3467 3468 template<typename _Tp> 3469 _GLIBCXX14_CONSTEXPR 3470 inline pair<_Tp, _Tp> 3471 minmax(initializer_list<_Tp> __l) 3472 { 3473 pair<const _Tp*, const _Tp*> __p = 3474 std::minmax_element(__l.begin(), __l.end()); 3475 return std::make_pair(*__p.first, *__p.second); 3476 } 3477 3478 template<typename _Tp, typename _Compare> 3479 _GLIBCXX14_CONSTEXPR 3480 inline pair<_Tp, _Tp> 3481 minmax(initializer_list<_Tp> __l, _Compare __comp) 3482 { 3483 pair<const _Tp*, const _Tp*> __p = 3484 std::minmax_element(__l.begin(), __l.end(), __comp); 3485 return std::make_pair(*__p.first, *__p.second); 3486 } 3487 3488 template<typename _ForwardIterator1, typename _ForwardIterator2, 3489 typename _BinaryPredicate> 3490 bool 3491 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3492 _ForwardIterator2 __first2, _BinaryPredicate __pred) 3493 { 3494 // Efficiently compare identical prefixes: O(N) if sequences 3495 // have the same elements in the same order. 3496 for (; __first1 != __last1; ++__first1, (void)++__first2) 3497 if (!__pred(__first1, __first2)) 3498 break; 3499 3500 if (__first1 == __last1) 3501 return true; 3502 3503 // Establish __last2 assuming equal ranges by iterating over the 3504 // rest of the list. 3505 _ForwardIterator2 __last2 = __first2; 3506 std::advance(__last2, std::distance(__first1, __last1)); 3507 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 3508 { 3509 if (__scan != std::__find_if(__first1, __scan, 3510 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 3511 continue; // We've seen this one before. 3512 3513 auto __matches 3514 = std::__count_if(__first2, __last2, 3515 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 3516 if (0 == __matches || 3517 std::__count_if(__scan, __last1, 3518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 3519 != __matches) 3520 return false; 3521 } 3522 return true; 3523 } 3524 3525 /** 3526 * @brief Checks whether a permutation of the second sequence is equal 3527 * to the first sequence. 3528 * @ingroup non_mutating_algorithms 3529 * @param __first1 Start of first range. 3530 * @param __last1 End of first range. 3531 * @param __first2 Start of second range. 3532 * @return true if there exists a permutation of the elements in the range 3533 * [__first2, __first2 + (__last1 - __first1)), beginning with 3534 * ForwardIterator2 begin, such that equal(__first1, __last1, begin) 3535 * returns true; otherwise, returns false. 3536 */ 3537 template<typename _ForwardIterator1, typename _ForwardIterator2> 3538 inline bool 3539 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3540 _ForwardIterator2 __first2) 3541 { 3542 // concept requirements 3543 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 3544 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 3545 __glibcxx_function_requires(_EqualOpConcept< 3546 typename iterator_traits<_ForwardIterator1>::value_type, 3547 typename iterator_traits<_ForwardIterator2>::value_type>) 3548 __glibcxx_requires_valid_range(__first1, __last1); 3549 3550 return std::__is_permutation(__first1, __last1, __first2, 3551 __gnu_cxx::__ops::__iter_equal_to_iter()); 3552 } 3553 3554 /** 3555 * @brief Checks whether a permutation of the second sequence is equal 3556 * to the first sequence. 3557 * @ingroup non_mutating_algorithms 3558 * @param __first1 Start of first range. 3559 * @param __last1 End of first range. 3560 * @param __first2 Start of second range. 3561 * @param __pred A binary predicate. 3562 * @return true if there exists a permutation of the elements in 3563 * the range [__first2, __first2 + (__last1 - __first1)), 3564 * beginning with ForwardIterator2 begin, such that 3565 * equal(__first1, __last1, __begin, __pred) returns true; 3566 * otherwise, returns false. 3567 */ 3568 template<typename _ForwardIterator1, typename _ForwardIterator2, 3569 typename _BinaryPredicate> 3570 inline bool 3571 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3572 _ForwardIterator2 __first2, _BinaryPredicate __pred) 3573 { 3574 // concept requirements 3575 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 3576 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 3577 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3578 typename iterator_traits<_ForwardIterator1>::value_type, 3579 typename iterator_traits<_ForwardIterator2>::value_type>) 3580 __glibcxx_requires_valid_range(__first1, __last1); 3581 3582 return std::__is_permutation(__first1, __last1, __first2, 3583 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3584 } 3585 3586 #if __cplusplus > 201103L 3587 template<typename _ForwardIterator1, typename _ForwardIterator2, 3588 typename _BinaryPredicate> 3589 bool 3590 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3591 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3592 _BinaryPredicate __pred) 3593 { 3594 using _Cat1 3595 = typename iterator_traits<_ForwardIterator1>::iterator_category; 3596 using _Cat2 3597 = typename iterator_traits<_ForwardIterator2>::iterator_category; 3598 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; 3599 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; 3600 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA(); 3601 if (__ra_iters) 3602 { 3603 auto __d1 = std::distance(__first1, __last1); 3604 auto __d2 = std::distance(__first2, __last2); 3605 if (__d1 != __d2) 3606 return false; 3607 } 3608 3609 // Efficiently compare identical prefixes: O(N) if sequences 3610 // have the same elements in the same order. 3611 for (; __first1 != __last1 && __first2 != __last2; 3612 ++__first1, (void)++__first2) 3613 if (!__pred(__first1, __first2)) 3614 break; 3615 3616 if (__ra_iters) 3617 { 3618 if (__first1 == __last1) 3619 return true; 3620 } 3621 else 3622 { 3623 auto __d1 = std::distance(__first1, __last1); 3624 auto __d2 = std::distance(__first2, __last2); 3625 if (__d1 == 0 && __d2 == 0) 3626 return true; 3627 if (__d1 != __d2) 3628 return false; 3629 } 3630 3631 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 3632 { 3633 if (__scan != std::__find_if(__first1, __scan, 3634 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 3635 continue; // We've seen this one before. 3636 3637 auto __matches = std::__count_if(__first2, __last2, 3638 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 3639 if (0 == __matches 3640 || std::__count_if(__scan, __last1, 3641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 3642 != __matches) 3643 return false; 3644 } 3645 return true; 3646 } 3647 3648 /** 3649 * @brief Checks whether a permutaion of the second sequence is equal 3650 * to the first sequence. 3651 * @ingroup non_mutating_algorithms 3652 * @param __first1 Start of first range. 3653 * @param __last1 End of first range. 3654 * @param __first2 Start of second range. 3655 * @param __last2 End of first range. 3656 * @return true if there exists a permutation of the elements in the range 3657 * [__first2, __last2), beginning with ForwardIterator2 begin, 3658 * such that equal(__first1, __last1, begin) returns true; 3659 * otherwise, returns false. 3660 */ 3661 template<typename _ForwardIterator1, typename _ForwardIterator2> 3662 inline bool 3663 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3664 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 3665 { 3666 __glibcxx_requires_valid_range(__first1, __last1); 3667 __glibcxx_requires_valid_range(__first2, __last2); 3668 3669 return 3670 std::__is_permutation(__first1, __last1, __first2, __last2, 3671 __gnu_cxx::__ops::__iter_equal_to_iter()); 3672 } 3673 3674 /** 3675 * @brief Checks whether a permutation of the second sequence is equal 3676 * to the first sequence. 3677 * @ingroup non_mutating_algorithms 3678 * @param __first1 Start of first range. 3679 * @param __last1 End of first range. 3680 * @param __first2 Start of second range. 3681 * @param __last2 End of first range. 3682 * @param __pred A binary predicate. 3683 * @return true if there exists a permutation of the elements in the range 3684 * [__first2, __last2), beginning with ForwardIterator2 begin, 3685 * such that equal(__first1, __last1, __begin, __pred) returns true; 3686 * otherwise, returns false. 3687 */ 3688 template<typename _ForwardIterator1, typename _ForwardIterator2, 3689 typename _BinaryPredicate> 3690 inline bool 3691 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3692 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3693 _BinaryPredicate __pred) 3694 { 3695 __glibcxx_requires_valid_range(__first1, __last1); 3696 __glibcxx_requires_valid_range(__first2, __last2); 3697 3698 return std::__is_permutation(__first1, __last1, __first2, __last2, 3699 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3700 } 3701 #endif 3702 3703 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3704 /** 3705 * @brief Shuffle the elements of a sequence using a uniform random 3706 * number generator. 3707 * @ingroup mutating_algorithms 3708 * @param __first A forward iterator. 3709 * @param __last A forward iterator. 3710 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 3711 * @return Nothing. 3712 * 3713 * Reorders the elements in the range @p [__first,__last) using @p __g to 3714 * provide random numbers. 3715 */ 3716 template<typename _RandomAccessIterator, 3717 typename _UniformRandomNumberGenerator> 3718 void 3719 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3720 _UniformRandomNumberGenerator&& __g) 3721 { 3722 // concept requirements 3723 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3724 _RandomAccessIterator>) 3725 __glibcxx_requires_valid_range(__first, __last); 3726 3727 if (__first == __last) 3728 return; 3729 3730 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3731 _DistanceType; 3732 3733 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 3734 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 3735 typedef typename __distr_type::param_type __p_type; 3736 __distr_type __d; 3737 3738 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 3739 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 3740 } 3741 #endif 3742 3743 #endif // C++11 3744 3745 _GLIBCXX_END_NAMESPACE_VERSION 3746 3747 _GLIBCXX_BEGIN_NAMESPACE_ALGO 3748 3749 /** 3750 * @brief Apply a function to every element of a sequence. 3751 * @ingroup non_mutating_algorithms 3752 * @param __first An input iterator. 3753 * @param __last An input iterator. 3754 * @param __f A unary function object. 3755 * @return @p __f (std::move(@p __f) in C++0x). 3756 * 3757 * Applies the function object @p __f to each element in the range 3758 * @p [first,last). @p __f must not modify the order of the sequence. 3759 * If @p __f has a return value it is ignored. 3760 */ 3761 template<typename _InputIterator, typename _Function> 3762 _Function 3763 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 3764 { 3765 // concept requirements 3766 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3767 __glibcxx_requires_valid_range(__first, __last); 3768 for (; __first != __last; ++__first) 3769 __f(*__first); 3770 return _GLIBCXX_MOVE(__f); 3771 } 3772 3773 /** 3774 * @brief Find the first occurrence of a value in a sequence. 3775 * @ingroup non_mutating_algorithms 3776 * @param __first An input iterator. 3777 * @param __last An input iterator. 3778 * @param __val The value to find. 3779 * @return The first iterator @c i in the range @p [__first,__last) 3780 * such that @c *i == @p __val, or @p __last if no such iterator exists. 3781 */ 3782 template<typename _InputIterator, typename _Tp> 3783 inline _InputIterator 3784 find(_InputIterator __first, _InputIterator __last, 3785 const _Tp& __val) 3786 { 3787 // concept requirements 3788 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3789 __glibcxx_function_requires(_EqualOpConcept< 3790 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3791 __glibcxx_requires_valid_range(__first, __last); 3792 return std::__find_if(__first, __last, 3793 __gnu_cxx::__ops::__iter_equals_val(__val)); 3794 } 3795 3796 /** 3797 * @brief Find the first element in a sequence for which a 3798 * predicate is true. 3799 * @ingroup non_mutating_algorithms 3800 * @param __first An input iterator. 3801 * @param __last An input iterator. 3802 * @param __pred A predicate. 3803 * @return The first iterator @c i in the range @p [__first,__last) 3804 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 3805 */ 3806 template<typename _InputIterator, typename _Predicate> 3807 inline _InputIterator 3808 find_if(_InputIterator __first, _InputIterator __last, 3809 _Predicate __pred) 3810 { 3811 // concept requirements 3812 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3813 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3814 typename iterator_traits<_InputIterator>::value_type>) 3815 __glibcxx_requires_valid_range(__first, __last); 3816 3817 return std::__find_if(__first, __last, 3818 __gnu_cxx::__ops::__pred_iter(__pred)); 3819 } 3820 3821 /** 3822 * @brief Find element from a set in a sequence. 3823 * @ingroup non_mutating_algorithms 3824 * @param __first1 Start of range to search. 3825 * @param __last1 End of range to search. 3826 * @param __first2 Start of match candidates. 3827 * @param __last2 End of match candidates. 3828 * @return The first iterator @c i in the range 3829 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 3830 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 3831 * 3832 * Searches the range @p [__first1,__last1) for an element that is 3833 * equal to some element in the range [__first2,__last2). If 3834 * found, returns an iterator in the range [__first1,__last1), 3835 * otherwise returns @p __last1. 3836 */ 3837 template<typename _InputIterator, typename _ForwardIterator> 3838 _InputIterator 3839 find_first_of(_InputIterator __first1, _InputIterator __last1, 3840 _ForwardIterator __first2, _ForwardIterator __last2) 3841 { 3842 // concept requirements 3843 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3844 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3845 __glibcxx_function_requires(_EqualOpConcept< 3846 typename iterator_traits<_InputIterator>::value_type, 3847 typename iterator_traits<_ForwardIterator>::value_type>) 3848 __glibcxx_requires_valid_range(__first1, __last1); 3849 __glibcxx_requires_valid_range(__first2, __last2); 3850 3851 for (; __first1 != __last1; ++__first1) 3852 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 3853 if (*__first1 == *__iter) 3854 return __first1; 3855 return __last1; 3856 } 3857 3858 /** 3859 * @brief Find element from a set in a sequence using a predicate. 3860 * @ingroup non_mutating_algorithms 3861 * @param __first1 Start of range to search. 3862 * @param __last1 End of range to search. 3863 * @param __first2 Start of match candidates. 3864 * @param __last2 End of match candidates. 3865 * @param __comp Predicate to use. 3866 * @return The first iterator @c i in the range 3867 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 3868 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 3869 * such iterator exists. 3870 * 3871 3872 * Searches the range @p [__first1,__last1) for an element that is 3873 * equal to some element in the range [__first2,__last2). If 3874 * found, returns an iterator in the range [__first1,__last1), 3875 * otherwise returns @p __last1. 3876 */ 3877 template<typename _InputIterator, typename _ForwardIterator, 3878 typename _BinaryPredicate> 3879 _InputIterator 3880 find_first_of(_InputIterator __first1, _InputIterator __last1, 3881 _ForwardIterator __first2, _ForwardIterator __last2, 3882 _BinaryPredicate __comp) 3883 { 3884 // concept requirements 3885 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3886 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3887 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3888 typename iterator_traits<_InputIterator>::value_type, 3889 typename iterator_traits<_ForwardIterator>::value_type>) 3890 __glibcxx_requires_valid_range(__first1, __last1); 3891 __glibcxx_requires_valid_range(__first2, __last2); 3892 3893 for (; __first1 != __last1; ++__first1) 3894 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 3895 if (__comp(*__first1, *__iter)) 3896 return __first1; 3897 return __last1; 3898 } 3899 3900 /** 3901 * @brief Find two adjacent values in a sequence that are equal. 3902 * @ingroup non_mutating_algorithms 3903 * @param __first A forward iterator. 3904 * @param __last A forward iterator. 3905 * @return The first iterator @c i such that @c i and @c i+1 are both 3906 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 3907 * or @p __last if no such iterator exists. 3908 */ 3909 template<typename _ForwardIterator> 3910 inline _ForwardIterator 3911 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 3912 { 3913 // concept requirements 3914 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3915 __glibcxx_function_requires(_EqualityComparableConcept< 3916 typename iterator_traits<_ForwardIterator>::value_type>) 3917 __glibcxx_requires_valid_range(__first, __last); 3918 3919 return std::__adjacent_find(__first, __last, 3920 __gnu_cxx::__ops::__iter_equal_to_iter()); 3921 } 3922 3923 /** 3924 * @brief Find two adjacent values in a sequence using a predicate. 3925 * @ingroup non_mutating_algorithms 3926 * @param __first A forward iterator. 3927 * @param __last A forward iterator. 3928 * @param __binary_pred A binary predicate. 3929 * @return The first iterator @c i such that @c i and @c i+1 are both 3930 * valid iterators in @p [__first,__last) and such that 3931 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 3932 * exists. 3933 */ 3934 template<typename _ForwardIterator, typename _BinaryPredicate> 3935 inline _ForwardIterator 3936 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 3937 _BinaryPredicate __binary_pred) 3938 { 3939 // concept requirements 3940 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3941 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3942 typename iterator_traits<_ForwardIterator>::value_type, 3943 typename iterator_traits<_ForwardIterator>::value_type>) 3944 __glibcxx_requires_valid_range(__first, __last); 3945 3946 return std::__adjacent_find(__first, __last, 3947 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 3948 } 3949 3950 /** 3951 * @brief Count the number of copies of a value in a sequence. 3952 * @ingroup non_mutating_algorithms 3953 * @param __first An input iterator. 3954 * @param __last An input iterator. 3955 * @param __value The value to be counted. 3956 * @return The number of iterators @c i in the range @p [__first,__last) 3957 * for which @c *i == @p __value 3958 */ 3959 template<typename _InputIterator, typename _Tp> 3960 inline typename iterator_traits<_InputIterator>::difference_type 3961 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 3962 { 3963 // concept requirements 3964 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3965 __glibcxx_function_requires(_EqualOpConcept< 3966 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3967 __glibcxx_requires_valid_range(__first, __last); 3968 3969 return std::__count_if(__first, __last, 3970 __gnu_cxx::__ops::__iter_equals_val(__value)); 3971 } 3972 3973 /** 3974 * @brief Count the elements of a sequence for which a predicate is true. 3975 * @ingroup non_mutating_algorithms 3976 * @param __first An input iterator. 3977 * @param __last An input iterator. 3978 * @param __pred A predicate. 3979 * @return The number of iterators @c i in the range @p [__first,__last) 3980 * for which @p __pred(*i) is true. 3981 */ 3982 template<typename _InputIterator, typename _Predicate> 3983 inline typename iterator_traits<_InputIterator>::difference_type 3984 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 3985 { 3986 // concept requirements 3987 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3988 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3989 typename iterator_traits<_InputIterator>::value_type>) 3990 __glibcxx_requires_valid_range(__first, __last); 3991 3992 return std::__count_if(__first, __last, 3993 __gnu_cxx::__ops::__pred_iter(__pred)); 3994 } 3995 3996 /** 3997 * @brief Search a sequence for a matching sub-sequence. 3998 * @ingroup non_mutating_algorithms 3999 * @param __first1 A forward iterator. 4000 * @param __last1 A forward iterator. 4001 * @param __first2 A forward iterator. 4002 * @param __last2 A forward iterator. 4003 * @return The first iterator @c i in the range @p 4004 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 4005 * *(__first2+N) for each @c N in the range @p 4006 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 4007 * 4008 * Searches the range @p [__first1,__last1) for a sub-sequence that 4009 * compares equal value-by-value with the sequence given by @p 4010 * [__first2,__last2) and returns an iterator to the first element 4011 * of the sub-sequence, or @p __last1 if the sub-sequence is not 4012 * found. 4013 * 4014 * Because the sub-sequence must lie completely within the range @p 4015 * [__first1,__last1) it must start at a position less than @p 4016 * __last1-(__last2-__first2) where @p __last2-__first2 is the 4017 * length of the sub-sequence. 4018 * 4019 * This means that the returned iterator @c i will be in the range 4020 * @p [__first1,__last1-(__last2-__first2)) 4021 */ 4022 template<typename _ForwardIterator1, typename _ForwardIterator2> 4023 inline _ForwardIterator1 4024 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4025 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 4026 { 4027 // concept requirements 4028 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 4029 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 4030 __glibcxx_function_requires(_EqualOpConcept< 4031 typename iterator_traits<_ForwardIterator1>::value_type, 4032 typename iterator_traits<_ForwardIterator2>::value_type>) 4033 __glibcxx_requires_valid_range(__first1, __last1); 4034 __glibcxx_requires_valid_range(__first2, __last2); 4035 4036 return std::__search(__first1, __last1, __first2, __last2, 4037 __gnu_cxx::__ops::__iter_equal_to_iter()); 4038 } 4039 4040 /** 4041 * @brief Search a sequence for a matching sub-sequence using a predicate. 4042 * @ingroup non_mutating_algorithms 4043 * @param __first1 A forward iterator. 4044 * @param __last1 A forward iterator. 4045 * @param __first2 A forward iterator. 4046 * @param __last2 A forward iterator. 4047 * @param __predicate A binary predicate. 4048 * @return The first iterator @c i in the range 4049 * @p [__first1,__last1-(__last2-__first2)) such that 4050 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range 4051 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. 4052 * 4053 * Searches the range @p [__first1,__last1) for a sub-sequence that 4054 * compares equal value-by-value with the sequence given by @p 4055 * [__first2,__last2), using @p __predicate to determine equality, 4056 * and returns an iterator to the first element of the 4057 * sub-sequence, or @p __last1 if no such iterator exists. 4058 * 4059 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 4060 */ 4061 template<typename _ForwardIterator1, typename _ForwardIterator2, 4062 typename _BinaryPredicate> 4063 inline _ForwardIterator1 4064 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4065 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 4066 _BinaryPredicate __predicate) 4067 { 4068 // concept requirements 4069 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 4070 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 4071 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4072 typename iterator_traits<_ForwardIterator1>::value_type, 4073 typename iterator_traits<_ForwardIterator2>::value_type>) 4074 __glibcxx_requires_valid_range(__first1, __last1); 4075 __glibcxx_requires_valid_range(__first2, __last2); 4076 4077 return std::__search(__first1, __last1, __first2, __last2, 4078 __gnu_cxx::__ops::__iter_comp_iter(__predicate)); 4079 } 4080 4081 /** 4082 * @brief Search a sequence for a number of consecutive values. 4083 * @ingroup non_mutating_algorithms 4084 * @param __first A forward iterator. 4085 * @param __last A forward iterator. 4086 * @param __count The number of consecutive values. 4087 * @param __val The value to find. 4088 * @return The first iterator @c i in the range @p 4089 * [__first,__last-__count) such that @c *(i+N) == @p __val for 4090 * each @c N in the range @p [0,__count), or @p __last if no such 4091 * iterator exists. 4092 * 4093 * Searches the range @p [__first,__last) for @p count consecutive elements 4094 * equal to @p __val. 4095 */ 4096 template<typename _ForwardIterator, typename _Integer, typename _Tp> 4097 inline _ForwardIterator 4098 search_n(_ForwardIterator __first, _ForwardIterator __last, 4099 _Integer __count, const _Tp& __val) 4100 { 4101 // concept requirements 4102 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4103 __glibcxx_function_requires(_EqualOpConcept< 4104 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4105 __glibcxx_requires_valid_range(__first, __last); 4106 4107 return std::__search_n(__first, __last, __count, 4108 __gnu_cxx::__ops::__iter_equals_val(__val)); 4109 } 4110 4111 4112 /** 4113 * @brief Search a sequence for a number of consecutive values using a 4114 * predicate. 4115 * @ingroup non_mutating_algorithms 4116 * @param __first A forward iterator. 4117 * @param __last A forward iterator. 4118 * @param __count The number of consecutive values. 4119 * @param __val The value to find. 4120 * @param __binary_pred A binary predicate. 4121 * @return The first iterator @c i in the range @p 4122 * [__first,__last-__count) such that @p 4123 * __binary_pred(*(i+N),__val) is true for each @c N in the range 4124 * @p [0,__count), or @p __last if no such iterator exists. 4125 * 4126 * Searches the range @p [__first,__last) for @p __count 4127 * consecutive elements for which the predicate returns true. 4128 */ 4129 template<typename _ForwardIterator, typename _Integer, typename _Tp, 4130 typename _BinaryPredicate> 4131 inline _ForwardIterator 4132 search_n(_ForwardIterator __first, _ForwardIterator __last, 4133 _Integer __count, const _Tp& __val, 4134 _BinaryPredicate __binary_pred) 4135 { 4136 // concept requirements 4137 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4138 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4139 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4140 __glibcxx_requires_valid_range(__first, __last); 4141 4142 return std::__search_n(__first, __last, __count, 4143 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 4144 } 4145 4146 4147 /** 4148 * @brief Perform an operation on a sequence. 4149 * @ingroup mutating_algorithms 4150 * @param __first An input iterator. 4151 * @param __last An input iterator. 4152 * @param __result An output iterator. 4153 * @param __unary_op A unary operator. 4154 * @return An output iterator equal to @p __result+(__last-__first). 4155 * 4156 * Applies the operator to each element in the input range and assigns 4157 * the results to successive elements of the output sequence. 4158 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 4159 * range @p [0,__last-__first). 4160 * 4161 * @p unary_op must not alter its argument. 4162 */ 4163 template<typename _InputIterator, typename _OutputIterator, 4164 typename _UnaryOperation> 4165 _OutputIterator 4166 transform(_InputIterator __first, _InputIterator __last, 4167 _OutputIterator __result, _UnaryOperation __unary_op) 4168 { 4169 // concept requirements 4170 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4172 // "the type returned by a _UnaryOperation" 4173 __typeof__(__unary_op(*__first))>) 4174 __glibcxx_requires_valid_range(__first, __last); 4175 4176 for (; __first != __last; ++__first, (void)++__result) 4177 *__result = __unary_op(*__first); 4178 return __result; 4179 } 4180 4181 /** 4182 * @brief Perform an operation on corresponding elements of two sequences. 4183 * @ingroup mutating_algorithms 4184 * @param __first1 An input iterator. 4185 * @param __last1 An input iterator. 4186 * @param __first2 An input iterator. 4187 * @param __result An output iterator. 4188 * @param __binary_op A binary operator. 4189 * @return An output iterator equal to @p result+(last-first). 4190 * 4191 * Applies the operator to the corresponding elements in the two 4192 * input ranges and assigns the results to successive elements of the 4193 * output sequence. 4194 * Evaluates @p 4195 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 4196 * @c N in the range @p [0,__last1-__first1). 4197 * 4198 * @p binary_op must not alter either of its arguments. 4199 */ 4200 template<typename _InputIterator1, typename _InputIterator2, 4201 typename _OutputIterator, typename _BinaryOperation> 4202 _OutputIterator 4203 transform(_InputIterator1 __first1, _InputIterator1 __last1, 4204 _InputIterator2 __first2, _OutputIterator __result, 4205 _BinaryOperation __binary_op) 4206 { 4207 // concept requirements 4208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4209 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4211 // "the type returned by a _BinaryOperation" 4212 __typeof__(__binary_op(*__first1,*__first2))>) 4213 __glibcxx_requires_valid_range(__first1, __last1); 4214 4215 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result) 4216 *__result = __binary_op(*__first1, *__first2); 4217 return __result; 4218 } 4219 4220 /** 4221 * @brief Replace each occurrence of one value in a sequence with another 4222 * value. 4223 * @ingroup mutating_algorithms 4224 * @param __first A forward iterator. 4225 * @param __last A forward iterator. 4226 * @param __old_value The value to be replaced. 4227 * @param __new_value The replacement value. 4228 * @return replace() returns no value. 4229 * 4230 * For each iterator @c i in the range @p [__first,__last) if @c *i == 4231 * @p __old_value then the assignment @c *i = @p __new_value is performed. 4232 */ 4233 template<typename _ForwardIterator, typename _Tp> 4234 void 4235 replace(_ForwardIterator __first, _ForwardIterator __last, 4236 const _Tp& __old_value, const _Tp& __new_value) 4237 { 4238 // concept requirements 4239 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4240 _ForwardIterator>) 4241 __glibcxx_function_requires(_EqualOpConcept< 4242 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4243 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4244 typename iterator_traits<_ForwardIterator>::value_type>) 4245 __glibcxx_requires_valid_range(__first, __last); 4246 4247 for (; __first != __last; ++__first) 4248 if (*__first == __old_value) 4249 *__first = __new_value; 4250 } 4251 4252 /** 4253 * @brief Replace each value in a sequence for which a predicate returns 4254 * true with another value. 4255 * @ingroup mutating_algorithms 4256 * @param __first A forward iterator. 4257 * @param __last A forward iterator. 4258 * @param __pred A predicate. 4259 * @param __new_value The replacement value. 4260 * @return replace_if() returns no value. 4261 * 4262 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i) 4263 * is true then the assignment @c *i = @p __new_value is performed. 4264 */ 4265 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 4266 void 4267 replace_if(_ForwardIterator __first, _ForwardIterator __last, 4268 _Predicate __pred, const _Tp& __new_value) 4269 { 4270 // concept requirements 4271 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4272 _ForwardIterator>) 4273 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4274 typename iterator_traits<_ForwardIterator>::value_type>) 4275 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4276 typename iterator_traits<_ForwardIterator>::value_type>) 4277 __glibcxx_requires_valid_range(__first, __last); 4278 4279 for (; __first != __last; ++__first) 4280 if (__pred(*__first)) 4281 *__first = __new_value; 4282 } 4283 4284 /** 4285 * @brief Assign the result of a function object to each value in a 4286 * sequence. 4287 * @ingroup mutating_algorithms 4288 * @param __first A forward iterator. 4289 * @param __last A forward iterator. 4290 * @param __gen A function object taking no arguments and returning 4291 * std::iterator_traits<_ForwardIterator>::value_type 4292 * @return generate() returns no value. 4293 * 4294 * Performs the assignment @c *i = @p __gen() for each @c i in the range 4295 * @p [__first,__last). 4296 */ 4297 template<typename _ForwardIterator, typename _Generator> 4298 void 4299 generate(_ForwardIterator __first, _ForwardIterator __last, 4300 _Generator __gen) 4301 { 4302 // concept requirements 4303 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4304 __glibcxx_function_requires(_GeneratorConcept<_Generator, 4305 typename iterator_traits<_ForwardIterator>::value_type>) 4306 __glibcxx_requires_valid_range(__first, __last); 4307 4308 for (; __first != __last; ++__first) 4309 *__first = __gen(); 4310 } 4311 4312 /** 4313 * @brief Assign the result of a function object to each value in a 4314 * sequence. 4315 * @ingroup mutating_algorithms 4316 * @param __first A forward iterator. 4317 * @param __n The length of the sequence. 4318 * @param __gen A function object taking no arguments and returning 4319 * std::iterator_traits<_ForwardIterator>::value_type 4320 * @return The end of the sequence, @p __first+__n 4321 * 4322 * Performs the assignment @c *i = @p __gen() for each @c i in the range 4323 * @p [__first,__first+__n). 4324 * 4325 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4326 * DR 865. More algorithms that throw away information 4327 */ 4328 template<typename _OutputIterator, typename _Size, typename _Generator> 4329 _OutputIterator 4330 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 4331 { 4332 // concept requirements 4333 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4334 // "the type returned by a _Generator" 4335 __typeof__(__gen())>) 4336 4337 for (__decltype(__n + 0) __niter = __n; 4338 __niter > 0; --__niter, ++__first) 4339 *__first = __gen(); 4340 return __first; 4341 } 4342 4343 /** 4344 * @brief Copy a sequence, removing consecutive duplicate values. 4345 * @ingroup mutating_algorithms 4346 * @param __first An input iterator. 4347 * @param __last An input iterator. 4348 * @param __result An output iterator. 4349 * @return An iterator designating the end of the resulting sequence. 4350 * 4351 * Copies each element in the range @p [__first,__last) to the range 4352 * beginning at @p __result, except that only the first element is copied 4353 * from groups of consecutive elements that compare equal. 4354 * unique_copy() is stable, so the relative order of elements that are 4355 * copied is unchanged. 4356 * 4357 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4358 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 4359 * 4360 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4361 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 4362 * Assignable? 4363 */ 4364 template<typename _InputIterator, typename _OutputIterator> 4365 inline _OutputIterator 4366 unique_copy(_InputIterator __first, _InputIterator __last, 4367 _OutputIterator __result) 4368 { 4369 // concept requirements 4370 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4371 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4372 typename iterator_traits<_InputIterator>::value_type>) 4373 __glibcxx_function_requires(_EqualityComparableConcept< 4374 typename iterator_traits<_InputIterator>::value_type>) 4375 __glibcxx_requires_valid_range(__first, __last); 4376 4377 if (__first == __last) 4378 return __result; 4379 return std::__unique_copy(__first, __last, __result, 4380 __gnu_cxx::__ops::__iter_equal_to_iter(), 4381 std::__iterator_category(__first), 4382 std::__iterator_category(__result)); 4383 } 4384 4385 /** 4386 * @brief Copy a sequence, removing consecutive values using a predicate. 4387 * @ingroup mutating_algorithms 4388 * @param __first An input iterator. 4389 * @param __last An input iterator. 4390 * @param __result An output iterator. 4391 * @param __binary_pred A binary predicate. 4392 * @return An iterator designating the end of the resulting sequence. 4393 * 4394 * Copies each element in the range @p [__first,__last) to the range 4395 * beginning at @p __result, except that only the first element is copied 4396 * from groups of consecutive elements for which @p __binary_pred returns 4397 * true. 4398 * unique_copy() is stable, so the relative order of elements that are 4399 * copied is unchanged. 4400 * 4401 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4402 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 4403 */ 4404 template<typename _InputIterator, typename _OutputIterator, 4405 typename _BinaryPredicate> 4406 inline _OutputIterator 4407 unique_copy(_InputIterator __first, _InputIterator __last, 4408 _OutputIterator __result, 4409 _BinaryPredicate __binary_pred) 4410 { 4411 // concept requirements -- predicates checked later 4412 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4413 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4414 typename iterator_traits<_InputIterator>::value_type>) 4415 __glibcxx_requires_valid_range(__first, __last); 4416 4417 if (__first == __last) 4418 return __result; 4419 return std::__unique_copy(__first, __last, __result, 4420 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 4421 std::__iterator_category(__first), 4422 std::__iterator_category(__result)); 4423 } 4424 4425 #if _GLIBCXX_HOSTED 4426 /** 4427 * @brief Randomly shuffle the elements of a sequence. 4428 * @ingroup mutating_algorithms 4429 * @param __first A forward iterator. 4430 * @param __last A forward iterator. 4431 * @return Nothing. 4432 * 4433 * Reorder the elements in the range @p [__first,__last) using a random 4434 * distribution, so that every possible ordering of the sequence is 4435 * equally likely. 4436 */ 4437 template<typename _RandomAccessIterator> 4438 inline void 4439 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 4440 { 4441 // concept requirements 4442 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4443 _RandomAccessIterator>) 4444 __glibcxx_requires_valid_range(__first, __last); 4445 4446 if (__first != __last) 4447 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4448 { 4449 // XXX rand() % N is not uniformly distributed 4450 _RandomAccessIterator __j = __first 4451 + std::rand() % ((__i - __first) + 1); 4452 if (__i != __j) 4453 std::iter_swap(__i, __j); 4454 } 4455 } 4456 #endif 4457 4458 /** 4459 * @brief Shuffle the elements of a sequence using a random number 4460 * generator. 4461 * @ingroup mutating_algorithms 4462 * @param __first A forward iterator. 4463 * @param __last A forward iterator. 4464 * @param __rand The RNG functor or function. 4465 * @return Nothing. 4466 * 4467 * Reorders the elements in the range @p [__first,__last) using @p __rand to 4468 * provide a random distribution. Calling @p __rand(N) for a positive 4469 * integer @p N should return a randomly chosen integer from the 4470 * range [0,N). 4471 */ 4472 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 4473 void 4474 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 4475 #if __cplusplus >= 201103L 4476 _RandomNumberGenerator&& __rand) 4477 #else 4478 _RandomNumberGenerator& __rand) 4479 #endif 4480 { 4481 // concept requirements 4482 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4483 _RandomAccessIterator>) 4484 __glibcxx_requires_valid_range(__first, __last); 4485 4486 if (__first == __last) 4487 return; 4488 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4489 { 4490 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); 4491 if (__i != __j) 4492 std::iter_swap(__i, __j); 4493 } 4494 } 4495 4496 4497 /** 4498 * @brief Move elements for which a predicate is true to the beginning 4499 * of a sequence. 4500 * @ingroup mutating_algorithms 4501 * @param __first A forward iterator. 4502 * @param __last A forward iterator. 4503 * @param __pred A predicate functor. 4504 * @return An iterator @p middle such that @p __pred(i) is true for each 4505 * iterator @p i in the range @p [__first,middle) and false for each @p i 4506 * in the range @p [middle,__last). 4507 * 4508 * @p __pred must not modify its operand. @p partition() does not preserve 4509 * the relative ordering of elements in each group, use 4510 * @p stable_partition() if this is needed. 4511 */ 4512 template<typename _ForwardIterator, typename _Predicate> 4513 inline _ForwardIterator 4514 partition(_ForwardIterator __first, _ForwardIterator __last, 4515 _Predicate __pred) 4516 { 4517 // concept requirements 4518 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4519 _ForwardIterator>) 4520 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4521 typename iterator_traits<_ForwardIterator>::value_type>) 4522 __glibcxx_requires_valid_range(__first, __last); 4523 4524 return std::__partition(__first, __last, __pred, 4525 std::__iterator_category(__first)); 4526 } 4527 4528 4529 /** 4530 * @brief Sort the smallest elements of a sequence. 4531 * @ingroup sorting_algorithms 4532 * @param __first An iterator. 4533 * @param __middle Another iterator. 4534 * @param __last Another iterator. 4535 * @return Nothing. 4536 * 4537 * Sorts the smallest @p (__middle-__first) elements in the range 4538 * @p [first,last) and moves them to the range @p [__first,__middle). The 4539 * order of the remaining elements in the range @p [__middle,__last) is 4540 * undefined. 4541 * After the sort if @e i and @e j are iterators in the range 4542 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 4543 * the range @p [__middle,__last) then *j<*i and *k<*i are both false. 4544 */ 4545 template<typename _RandomAccessIterator> 4546 inline void 4547 partial_sort(_RandomAccessIterator __first, 4548 _RandomAccessIterator __middle, 4549 _RandomAccessIterator __last) 4550 { 4551 // concept requirements 4552 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4553 _RandomAccessIterator>) 4554 __glibcxx_function_requires(_LessThanComparableConcept< 4555 typename iterator_traits<_RandomAccessIterator>::value_type>) 4556 __glibcxx_requires_valid_range(__first, __middle); 4557 __glibcxx_requires_valid_range(__middle, __last); 4558 __glibcxx_requires_irreflexive(__first, __last); 4559 4560 std::__partial_sort(__first, __middle, __last, 4561 __gnu_cxx::__ops::__iter_less_iter()); 4562 } 4563 4564 /** 4565 * @brief Sort the smallest elements of a sequence using a predicate 4566 * for comparison. 4567 * @ingroup sorting_algorithms 4568 * @param __first An iterator. 4569 * @param __middle Another iterator. 4570 * @param __last Another iterator. 4571 * @param __comp A comparison functor. 4572 * @return Nothing. 4573 * 4574 * Sorts the smallest @p (__middle-__first) elements in the range 4575 * @p [__first,__last) and moves them to the range @p [__first,__middle). The 4576 * order of the remaining elements in the range @p [__middle,__last) is 4577 * undefined. 4578 * After the sort if @e i and @e j are iterators in the range 4579 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 4580 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i) 4581 * are both false. 4582 */ 4583 template<typename _RandomAccessIterator, typename _Compare> 4584 inline void 4585 partial_sort(_RandomAccessIterator __first, 4586 _RandomAccessIterator __middle, 4587 _RandomAccessIterator __last, 4588 _Compare __comp) 4589 { 4590 // concept requirements 4591 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4592 _RandomAccessIterator>) 4593 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4594 typename iterator_traits<_RandomAccessIterator>::value_type, 4595 typename iterator_traits<_RandomAccessIterator>::value_type>) 4596 __glibcxx_requires_valid_range(__first, __middle); 4597 __glibcxx_requires_valid_range(__middle, __last); 4598 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4599 4600 std::__partial_sort(__first, __middle, __last, 4601 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4602 } 4603 4604 /** 4605 * @brief Sort a sequence just enough to find a particular position. 4606 * @ingroup sorting_algorithms 4607 * @param __first An iterator. 4608 * @param __nth Another iterator. 4609 * @param __last Another iterator. 4610 * @return Nothing. 4611 * 4612 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 4613 * is the same element that would have been in that position had the 4614 * whole sequence been sorted. The elements either side of @p *__nth are 4615 * not completely sorted, but for any iterator @e i in the range 4616 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 4617 * holds that *j < *i is false. 4618 */ 4619 template<typename _RandomAccessIterator> 4620 inline void 4621 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4622 _RandomAccessIterator __last) 4623 { 4624 // concept requirements 4625 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4626 _RandomAccessIterator>) 4627 __glibcxx_function_requires(_LessThanComparableConcept< 4628 typename iterator_traits<_RandomAccessIterator>::value_type>) 4629 __glibcxx_requires_valid_range(__first, __nth); 4630 __glibcxx_requires_valid_range(__nth, __last); 4631 __glibcxx_requires_irreflexive(__first, __last); 4632 4633 if (__first == __last || __nth == __last) 4634 return; 4635 4636 std::__introselect(__first, __nth, __last, 4637 std::__lg(__last - __first) * 2, 4638 __gnu_cxx::__ops::__iter_less_iter()); 4639 } 4640 4641 /** 4642 * @brief Sort a sequence just enough to find a particular position 4643 * using a predicate for comparison. 4644 * @ingroup sorting_algorithms 4645 * @param __first An iterator. 4646 * @param __nth Another iterator. 4647 * @param __last Another iterator. 4648 * @param __comp A comparison functor. 4649 * @return Nothing. 4650 * 4651 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 4652 * is the same element that would have been in that position had the 4653 * whole sequence been sorted. The elements either side of @p *__nth are 4654 * not completely sorted, but for any iterator @e i in the range 4655 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 4656 * holds that @p __comp(*j,*i) is false. 4657 */ 4658 template<typename _RandomAccessIterator, typename _Compare> 4659 inline void 4660 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4661 _RandomAccessIterator __last, _Compare __comp) 4662 { 4663 // concept requirements 4664 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4665 _RandomAccessIterator>) 4666 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4667 typename iterator_traits<_RandomAccessIterator>::value_type, 4668 typename iterator_traits<_RandomAccessIterator>::value_type>) 4669 __glibcxx_requires_valid_range(__first, __nth); 4670 __glibcxx_requires_valid_range(__nth, __last); 4671 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4672 4673 if (__first == __last || __nth == __last) 4674 return; 4675 4676 std::__introselect(__first, __nth, __last, 4677 std::__lg(__last - __first) * 2, 4678 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4679 } 4680 4681 /** 4682 * @brief Sort the elements of a sequence. 4683 * @ingroup sorting_algorithms 4684 * @param __first An iterator. 4685 * @param __last Another iterator. 4686 * @return Nothing. 4687 * 4688 * Sorts the elements in the range @p [__first,__last) in ascending order, 4689 * such that for each iterator @e i in the range @p [__first,__last-1), 4690 * *(i+1)<*i is false. 4691 * 4692 * The relative ordering of equivalent elements is not preserved, use 4693 * @p stable_sort() if this is needed. 4694 */ 4695 template<typename _RandomAccessIterator> 4696 inline void 4697 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4698 { 4699 // concept requirements 4700 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4701 _RandomAccessIterator>) 4702 __glibcxx_function_requires(_LessThanComparableConcept< 4703 typename iterator_traits<_RandomAccessIterator>::value_type>) 4704 __glibcxx_requires_valid_range(__first, __last); 4705 __glibcxx_requires_irreflexive(__first, __last); 4706 4707 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 4708 } 4709 4710 /** 4711 * @brief Sort the elements of a sequence using a predicate for comparison. 4712 * @ingroup sorting_algorithms 4713 * @param __first An iterator. 4714 * @param __last Another iterator. 4715 * @param __comp A comparison functor. 4716 * @return Nothing. 4717 * 4718 * Sorts the elements in the range @p [__first,__last) in ascending order, 4719 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the 4720 * range @p [__first,__last-1). 4721 * 4722 * The relative ordering of equivalent elements is not preserved, use 4723 * @p stable_sort() if this is needed. 4724 */ 4725 template<typename _RandomAccessIterator, typename _Compare> 4726 inline void 4727 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 4728 _Compare __comp) 4729 { 4730 // concept requirements 4731 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4732 _RandomAccessIterator>) 4733 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4734 typename iterator_traits<_RandomAccessIterator>::value_type, 4735 typename iterator_traits<_RandomAccessIterator>::value_type>) 4736 __glibcxx_requires_valid_range(__first, __last); 4737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4738 4739 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4740 } 4741 4742 template<typename _InputIterator1, typename _InputIterator2, 4743 typename _OutputIterator, typename _Compare> 4744 _OutputIterator 4745 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 4746 _InputIterator2 __first2, _InputIterator2 __last2, 4747 _OutputIterator __result, _Compare __comp) 4748 { 4749 while (__first1 != __last1 && __first2 != __last2) 4750 { 4751 if (__comp(__first2, __first1)) 4752 { 4753 *__result = *__first2; 4754 ++__first2; 4755 } 4756 else 4757 { 4758 *__result = *__first1; 4759 ++__first1; 4760 } 4761 ++__result; 4762 } 4763 return std::copy(__first2, __last2, 4764 std::copy(__first1, __last1, __result)); 4765 } 4766 4767 /** 4768 * @brief Merges two sorted ranges. 4769 * @ingroup sorting_algorithms 4770 * @param __first1 An iterator. 4771 * @param __first2 Another iterator. 4772 * @param __last1 Another iterator. 4773 * @param __last2 Another iterator. 4774 * @param __result An iterator pointing to the end of the merged range. 4775 * @return An iterator pointing to the first element <em>not less 4776 * than</em> @e val. 4777 * 4778 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4779 * the sorted range @p [__result, __result + (__last1-__first1) + 4780 * (__last2-__first2)). Both input ranges must be sorted, and the 4781 * output range must not overlap with either of the input ranges. 4782 * The sort is @e stable, that is, for equivalent elements in the 4783 * two ranges, elements from the first range will always come 4784 * before elements from the second. 4785 */ 4786 template<typename _InputIterator1, typename _InputIterator2, 4787 typename _OutputIterator> 4788 inline _OutputIterator 4789 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4790 _InputIterator2 __first2, _InputIterator2 __last2, 4791 _OutputIterator __result) 4792 { 4793 // concept requirements 4794 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4795 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4796 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4797 typename iterator_traits<_InputIterator1>::value_type>) 4798 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4799 typename iterator_traits<_InputIterator2>::value_type>) 4800 __glibcxx_function_requires(_LessThanOpConcept< 4801 typename iterator_traits<_InputIterator2>::value_type, 4802 typename iterator_traits<_InputIterator1>::value_type>) 4803 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 4804 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 4805 __glibcxx_requires_irreflexive2(__first1, __last1); 4806 __glibcxx_requires_irreflexive2(__first2, __last2); 4807 4808 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4809 __first2, __last2, __result, 4810 __gnu_cxx::__ops::__iter_less_iter()); 4811 } 4812 4813 /** 4814 * @brief Merges two sorted ranges. 4815 * @ingroup sorting_algorithms 4816 * @param __first1 An iterator. 4817 * @param __first2 Another iterator. 4818 * @param __last1 Another iterator. 4819 * @param __last2 Another iterator. 4820 * @param __result An iterator pointing to the end of the merged range. 4821 * @param __comp A functor to use for comparisons. 4822 * @return An iterator pointing to the first element "not less 4823 * than" @e val. 4824 * 4825 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4826 * the sorted range @p [__result, __result + (__last1-__first1) + 4827 * (__last2-__first2)). Both input ranges must be sorted, and the 4828 * output range must not overlap with either of the input ranges. 4829 * The sort is @e stable, that is, for equivalent elements in the 4830 * two ranges, elements from the first range will always come 4831 * before elements from the second. 4832 * 4833 * The comparison function should have the same effects on ordering as 4834 * the function used for the initial sort. 4835 */ 4836 template<typename _InputIterator1, typename _InputIterator2, 4837 typename _OutputIterator, typename _Compare> 4838 inline _OutputIterator 4839 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4840 _InputIterator2 __first2, _InputIterator2 __last2, 4841 _OutputIterator __result, _Compare __comp) 4842 { 4843 // concept requirements 4844 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4845 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4846 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4847 typename iterator_traits<_InputIterator1>::value_type>) 4848 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4849 typename iterator_traits<_InputIterator2>::value_type>) 4850 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4851 typename iterator_traits<_InputIterator2>::value_type, 4852 typename iterator_traits<_InputIterator1>::value_type>) 4853 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 4854 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 4855 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 4856 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 4857 4858 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4859 __first2, __last2, __result, 4860 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4861 } 4862 4863 template<typename _RandomAccessIterator, typename _Compare> 4864 inline void 4865 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 4866 _Compare __comp) 4867 { 4868 typedef typename iterator_traits<_RandomAccessIterator>::value_type 4869 _ValueType; 4870 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 4871 _DistanceType; 4872 4873 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 4874 _TmpBuf __buf(__first, __last); 4875 4876 if (__buf.begin() == 0) 4877 std::__inplace_stable_sort(__first, __last, __comp); 4878 else 4879 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 4880 _DistanceType(__buf.size()), __comp); 4881 } 4882 4883 /** 4884 * @brief Sort the elements of a sequence, preserving the relative order 4885 * of equivalent elements. 4886 * @ingroup sorting_algorithms 4887 * @param __first An iterator. 4888 * @param __last Another iterator. 4889 * @return Nothing. 4890 * 4891 * Sorts the elements in the range @p [__first,__last) in ascending order, 4892 * such that for each iterator @p i in the range @p [__first,__last-1), 4893 * @p *(i+1)<*i is false. 4894 * 4895 * The relative ordering of equivalent elements is preserved, so any two 4896 * elements @p x and @p y in the range @p [__first,__last) such that 4897 * @p x<y is false and @p y<x is false will have the same relative 4898 * ordering after calling @p stable_sort(). 4899 */ 4900 template<typename _RandomAccessIterator> 4901 inline void 4902 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4903 { 4904 // concept requirements 4905 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4906 _RandomAccessIterator>) 4907 __glibcxx_function_requires(_LessThanComparableConcept< 4908 typename iterator_traits<_RandomAccessIterator>::value_type>) 4909 __glibcxx_requires_valid_range(__first, __last); 4910 __glibcxx_requires_irreflexive(__first, __last); 4911 4912 _GLIBCXX_STD_A::__stable_sort(__first, __last, 4913 __gnu_cxx::__ops::__iter_less_iter()); 4914 } 4915 4916 /** 4917 * @brief Sort the elements of a sequence using a predicate for comparison, 4918 * preserving the relative order of equivalent elements. 4919 * @ingroup sorting_algorithms 4920 * @param __first An iterator. 4921 * @param __last Another iterator. 4922 * @param __comp A comparison functor. 4923 * @return Nothing. 4924 * 4925 * Sorts the elements in the range @p [__first,__last) in ascending order, 4926 * such that for each iterator @p i in the range @p [__first,__last-1), 4927 * @p __comp(*(i+1),*i) is false. 4928 * 4929 * The relative ordering of equivalent elements is preserved, so any two 4930 * elements @p x and @p y in the range @p [__first,__last) such that 4931 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 4932 * relative ordering after calling @p stable_sort(). 4933 */ 4934 template<typename _RandomAccessIterator, typename _Compare> 4935 inline void 4936 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 4937 _Compare __comp) 4938 { 4939 // concept requirements 4940 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4941 _RandomAccessIterator>) 4942 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4943 typename iterator_traits<_RandomAccessIterator>::value_type, 4944 typename iterator_traits<_RandomAccessIterator>::value_type>) 4945 __glibcxx_requires_valid_range(__first, __last); 4946 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4947 4948 _GLIBCXX_STD_A::__stable_sort(__first, __last, 4949 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4950 } 4951 4952 template<typename _InputIterator1, typename _InputIterator2, 4953 typename _OutputIterator, 4954 typename _Compare> 4955 _OutputIterator 4956 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 4957 _InputIterator2 __first2, _InputIterator2 __last2, 4958 _OutputIterator __result, _Compare __comp) 4959 { 4960 while (__first1 != __last1 && __first2 != __last2) 4961 { 4962 if (__comp(__first1, __first2)) 4963 { 4964 *__result = *__first1; 4965 ++__first1; 4966 } 4967 else if (__comp(__first2, __first1)) 4968 { 4969 *__result = *__first2; 4970 ++__first2; 4971 } 4972 else 4973 { 4974 *__result = *__first1; 4975 ++__first1; 4976 ++__first2; 4977 } 4978 ++__result; 4979 } 4980 return std::copy(__first2, __last2, 4981 std::copy(__first1, __last1, __result)); 4982 } 4983 4984 /** 4985 * @brief Return the union of two sorted ranges. 4986 * @ingroup set_algorithms 4987 * @param __first1 Start of first range. 4988 * @param __last1 End of first range. 4989 * @param __first2 Start of second range. 4990 * @param __last2 End of second range. 4991 * @return End of the output range. 4992 * @ingroup set_algorithms 4993 * 4994 * This operation iterates over both ranges, copying elements present in 4995 * each range in order to the output range. Iterators increment for each 4996 * range. When the current element of one range is less than the other, 4997 * that element is copied and the iterator advanced. If an element is 4998 * contained in both ranges, the element from the first range is copied and 4999 * both ranges advance. The output range may not overlap either input 5000 * range. 5001 */ 5002 template<typename _InputIterator1, typename _InputIterator2, 5003 typename _OutputIterator> 5004 inline _OutputIterator 5005 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5006 _InputIterator2 __first2, _InputIterator2 __last2, 5007 _OutputIterator __result) 5008 { 5009 // concept requirements 5010 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5011 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5012 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5013 typename iterator_traits<_InputIterator1>::value_type>) 5014 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5015 typename iterator_traits<_InputIterator2>::value_type>) 5016 __glibcxx_function_requires(_LessThanOpConcept< 5017 typename iterator_traits<_InputIterator1>::value_type, 5018 typename iterator_traits<_InputIterator2>::value_type>) 5019 __glibcxx_function_requires(_LessThanOpConcept< 5020 typename iterator_traits<_InputIterator2>::value_type, 5021 typename iterator_traits<_InputIterator1>::value_type>) 5022 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5023 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5024 __glibcxx_requires_irreflexive2(__first1, __last1); 5025 __glibcxx_requires_irreflexive2(__first2, __last2); 5026 5027 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5028 __first2, __last2, __result, 5029 __gnu_cxx::__ops::__iter_less_iter()); 5030 } 5031 5032 /** 5033 * @brief Return the union of two sorted ranges using a comparison functor. 5034 * @ingroup set_algorithms 5035 * @param __first1 Start of first range. 5036 * @param __last1 End of first range. 5037 * @param __first2 Start of second range. 5038 * @param __last2 End of second range. 5039 * @param __comp The comparison functor. 5040 * @return End of the output range. 5041 * @ingroup set_algorithms 5042 * 5043 * This operation iterates over both ranges, copying elements present in 5044 * each range in order to the output range. Iterators increment for each 5045 * range. When the current element of one range is less than the other 5046 * according to @p __comp, that element is copied and the iterator advanced. 5047 * If an equivalent element according to @p __comp is contained in both 5048 * ranges, the element from the first range is copied and both ranges 5049 * advance. The output range may not overlap either input range. 5050 */ 5051 template<typename _InputIterator1, typename _InputIterator2, 5052 typename _OutputIterator, typename _Compare> 5053 inline _OutputIterator 5054 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5055 _InputIterator2 __first2, _InputIterator2 __last2, 5056 _OutputIterator __result, _Compare __comp) 5057 { 5058 // concept requirements 5059 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5060 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5061 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5062 typename iterator_traits<_InputIterator1>::value_type>) 5063 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5064 typename iterator_traits<_InputIterator2>::value_type>) 5065 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5066 typename iterator_traits<_InputIterator1>::value_type, 5067 typename iterator_traits<_InputIterator2>::value_type>) 5068 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5069 typename iterator_traits<_InputIterator2>::value_type, 5070 typename iterator_traits<_InputIterator1>::value_type>) 5071 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5072 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5073 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5074 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5075 5076 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5077 __first2, __last2, __result, 5078 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5079 } 5080 5081 template<typename _InputIterator1, typename _InputIterator2, 5082 typename _OutputIterator, 5083 typename _Compare> 5084 _OutputIterator 5085 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5086 _InputIterator2 __first2, _InputIterator2 __last2, 5087 _OutputIterator __result, _Compare __comp) 5088 { 5089 while (__first1 != __last1 && __first2 != __last2) 5090 if (__comp(__first1, __first2)) 5091 ++__first1; 5092 else if (__comp(__first2, __first1)) 5093 ++__first2; 5094 else 5095 { 5096 *__result = *__first1; 5097 ++__first1; 5098 ++__first2; 5099 ++__result; 5100 } 5101 return __result; 5102 } 5103 5104 /** 5105 * @brief Return the intersection of two sorted ranges. 5106 * @ingroup set_algorithms 5107 * @param __first1 Start of first range. 5108 * @param __last1 End of first range. 5109 * @param __first2 Start of second range. 5110 * @param __last2 End of second range. 5111 * @return End of the output range. 5112 * @ingroup set_algorithms 5113 * 5114 * This operation iterates over both ranges, copying elements present in 5115 * both ranges in order to the output range. Iterators increment for each 5116 * range. When the current element of one range is less than the other, 5117 * that iterator advances. If an element is contained in both ranges, the 5118 * element from the first range is copied and both ranges advance. The 5119 * output range may not overlap either input range. 5120 */ 5121 template<typename _InputIterator1, typename _InputIterator2, 5122 typename _OutputIterator> 5123 inline _OutputIterator 5124 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5125 _InputIterator2 __first2, _InputIterator2 __last2, 5126 _OutputIterator __result) 5127 { 5128 // concept requirements 5129 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5130 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5131 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5132 typename iterator_traits<_InputIterator1>::value_type>) 5133 __glibcxx_function_requires(_LessThanOpConcept< 5134 typename iterator_traits<_InputIterator1>::value_type, 5135 typename iterator_traits<_InputIterator2>::value_type>) 5136 __glibcxx_function_requires(_LessThanOpConcept< 5137 typename iterator_traits<_InputIterator2>::value_type, 5138 typename iterator_traits<_InputIterator1>::value_type>) 5139 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5140 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5141 __glibcxx_requires_irreflexive2(__first1, __last1); 5142 __glibcxx_requires_irreflexive2(__first2, __last2); 5143 5144 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5145 __first2, __last2, __result, 5146 __gnu_cxx::__ops::__iter_less_iter()); 5147 } 5148 5149 /** 5150 * @brief Return the intersection of two sorted ranges using comparison 5151 * functor. 5152 * @ingroup set_algorithms 5153 * @param __first1 Start of first range. 5154 * @param __last1 End of first range. 5155 * @param __first2 Start of second range. 5156 * @param __last2 End of second range. 5157 * @param __comp The comparison functor. 5158 * @return End of the output range. 5159 * @ingroup set_algorithms 5160 * 5161 * This operation iterates over both ranges, copying elements present in 5162 * both ranges in order to the output range. Iterators increment for each 5163 * range. When the current element of one range is less than the other 5164 * according to @p __comp, that iterator advances. If an element is 5165 * contained in both ranges according to @p __comp, the element from the 5166 * first range is copied and both ranges advance. The output range may not 5167 * overlap either input range. 5168 */ 5169 template<typename _InputIterator1, typename _InputIterator2, 5170 typename _OutputIterator, typename _Compare> 5171 inline _OutputIterator 5172 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5173 _InputIterator2 __first2, _InputIterator2 __last2, 5174 _OutputIterator __result, _Compare __comp) 5175 { 5176 // concept requirements 5177 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5178 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5179 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5180 typename iterator_traits<_InputIterator1>::value_type>) 5181 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5182 typename iterator_traits<_InputIterator1>::value_type, 5183 typename iterator_traits<_InputIterator2>::value_type>) 5184 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5185 typename iterator_traits<_InputIterator2>::value_type, 5186 typename iterator_traits<_InputIterator1>::value_type>) 5187 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5188 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5189 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5190 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5191 5192 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5193 __first2, __last2, __result, 5194 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5195 } 5196 5197 template<typename _InputIterator1, typename _InputIterator2, 5198 typename _OutputIterator, 5199 typename _Compare> 5200 _OutputIterator 5201 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5202 _InputIterator2 __first2, _InputIterator2 __last2, 5203 _OutputIterator __result, _Compare __comp) 5204 { 5205 while (__first1 != __last1 && __first2 != __last2) 5206 if (__comp(__first1, __first2)) 5207 { 5208 *__result = *__first1; 5209 ++__first1; 5210 ++__result; 5211 } 5212 else if (__comp(__first2, __first1)) 5213 ++__first2; 5214 else 5215 { 5216 ++__first1; 5217 ++__first2; 5218 } 5219 return std::copy(__first1, __last1, __result); 5220 } 5221 5222 /** 5223 * @brief Return the difference of two sorted ranges. 5224 * @ingroup set_algorithms 5225 * @param __first1 Start of first range. 5226 * @param __last1 End of first range. 5227 * @param __first2 Start of second range. 5228 * @param __last2 End of second range. 5229 * @return End of the output range. 5230 * @ingroup set_algorithms 5231 * 5232 * This operation iterates over both ranges, copying elements present in 5233 * the first range but not the second in order to the output range. 5234 * Iterators increment for each range. When the current element of the 5235 * first range is less than the second, that element is copied and the 5236 * iterator advances. If the current element of the second range is less, 5237 * the iterator advances, but no element is copied. If an element is 5238 * contained in both ranges, no elements are copied and both ranges 5239 * advance. The output range may not overlap either input range. 5240 */ 5241 template<typename _InputIterator1, typename _InputIterator2, 5242 typename _OutputIterator> 5243 inline _OutputIterator 5244 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5245 _InputIterator2 __first2, _InputIterator2 __last2, 5246 _OutputIterator __result) 5247 { 5248 // concept requirements 5249 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5250 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5251 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5252 typename iterator_traits<_InputIterator1>::value_type>) 5253 __glibcxx_function_requires(_LessThanOpConcept< 5254 typename iterator_traits<_InputIterator1>::value_type, 5255 typename iterator_traits<_InputIterator2>::value_type>) 5256 __glibcxx_function_requires(_LessThanOpConcept< 5257 typename iterator_traits<_InputIterator2>::value_type, 5258 typename iterator_traits<_InputIterator1>::value_type>) 5259 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5260 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5261 __glibcxx_requires_irreflexive2(__first1, __last1); 5262 __glibcxx_requires_irreflexive2(__first2, __last2); 5263 5264 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5265 __first2, __last2, __result, 5266 __gnu_cxx::__ops::__iter_less_iter()); 5267 } 5268 5269 /** 5270 * @brief Return the difference of two sorted ranges using comparison 5271 * functor. 5272 * @ingroup set_algorithms 5273 * @param __first1 Start of first range. 5274 * @param __last1 End of first range. 5275 * @param __first2 Start of second range. 5276 * @param __last2 End of second range. 5277 * @param __comp The comparison functor. 5278 * @return End of the output range. 5279 * @ingroup set_algorithms 5280 * 5281 * This operation iterates over both ranges, copying elements present in 5282 * the first range but not the second in order to the output range. 5283 * Iterators increment for each range. When the current element of the 5284 * first range is less than the second according to @p __comp, that element 5285 * is copied and the iterator advances. If the current element of the 5286 * second range is less, no element is copied and the iterator advances. 5287 * If an element is contained in both ranges according to @p __comp, no 5288 * elements are copied and both ranges advance. The output range may not 5289 * overlap either input range. 5290 */ 5291 template<typename _InputIterator1, typename _InputIterator2, 5292 typename _OutputIterator, typename _Compare> 5293 inline _OutputIterator 5294 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5295 _InputIterator2 __first2, _InputIterator2 __last2, 5296 _OutputIterator __result, _Compare __comp) 5297 { 5298 // concept requirements 5299 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5300 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5301 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5302 typename iterator_traits<_InputIterator1>::value_type>) 5303 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5304 typename iterator_traits<_InputIterator1>::value_type, 5305 typename iterator_traits<_InputIterator2>::value_type>) 5306 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5307 typename iterator_traits<_InputIterator2>::value_type, 5308 typename iterator_traits<_InputIterator1>::value_type>) 5309 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5310 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5311 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5312 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5313 5314 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5315 __first2, __last2, __result, 5316 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5317 } 5318 5319 template<typename _InputIterator1, typename _InputIterator2, 5320 typename _OutputIterator, 5321 typename _Compare> 5322 _OutputIterator 5323 __set_symmetric_difference(_InputIterator1 __first1, 5324 _InputIterator1 __last1, 5325 _InputIterator2 __first2, 5326 _InputIterator2 __last2, 5327 _OutputIterator __result, 5328 _Compare __comp) 5329 { 5330 while (__first1 != __last1 && __first2 != __last2) 5331 if (__comp(__first1, __first2)) 5332 { 5333 *__result = *__first1; 5334 ++__first1; 5335 ++__result; 5336 } 5337 else if (__comp(__first2, __first1)) 5338 { 5339 *__result = *__first2; 5340 ++__first2; 5341 ++__result; 5342 } 5343 else 5344 { 5345 ++__first1; 5346 ++__first2; 5347 } 5348 return std::copy(__first2, __last2, 5349 std::copy(__first1, __last1, __result)); 5350 } 5351 5352 /** 5353 * @brief Return the symmetric difference of two sorted ranges. 5354 * @ingroup set_algorithms 5355 * @param __first1 Start of first range. 5356 * @param __last1 End of first range. 5357 * @param __first2 Start of second range. 5358 * @param __last2 End of second range. 5359 * @return End of the output range. 5360 * @ingroup set_algorithms 5361 * 5362 * This operation iterates over both ranges, copying elements present in 5363 * one range but not the other in order to the output range. Iterators 5364 * increment for each range. When the current element of one range is less 5365 * than the other, that element is copied and the iterator advances. If an 5366 * element is contained in both ranges, no elements are copied and both 5367 * ranges advance. The output range may not overlap either input range. 5368 */ 5369 template<typename _InputIterator1, typename _InputIterator2, 5370 typename _OutputIterator> 5371 inline _OutputIterator 5372 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5373 _InputIterator2 __first2, _InputIterator2 __last2, 5374 _OutputIterator __result) 5375 { 5376 // concept requirements 5377 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5378 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5379 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5380 typename iterator_traits<_InputIterator1>::value_type>) 5381 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5382 typename iterator_traits<_InputIterator2>::value_type>) 5383 __glibcxx_function_requires(_LessThanOpConcept< 5384 typename iterator_traits<_InputIterator1>::value_type, 5385 typename iterator_traits<_InputIterator2>::value_type>) 5386 __glibcxx_function_requires(_LessThanOpConcept< 5387 typename iterator_traits<_InputIterator2>::value_type, 5388 typename iterator_traits<_InputIterator1>::value_type>) 5389 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5390 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5391 __glibcxx_requires_irreflexive2(__first1, __last1); 5392 __glibcxx_requires_irreflexive2(__first2, __last2); 5393 5394 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5395 __first2, __last2, __result, 5396 __gnu_cxx::__ops::__iter_less_iter()); 5397 } 5398 5399 /** 5400 * @brief Return the symmetric difference of two sorted ranges using 5401 * comparison functor. 5402 * @ingroup set_algorithms 5403 * @param __first1 Start of first range. 5404 * @param __last1 End of first range. 5405 * @param __first2 Start of second range. 5406 * @param __last2 End of second range. 5407 * @param __comp The comparison functor. 5408 * @return End of the output range. 5409 * @ingroup set_algorithms 5410 * 5411 * This operation iterates over both ranges, copying elements present in 5412 * one range but not the other in order to the output range. Iterators 5413 * increment for each range. When the current element of one range is less 5414 * than the other according to @p comp, that element is copied and the 5415 * iterator advances. If an element is contained in both ranges according 5416 * to @p __comp, no elements are copied and both ranges advance. The output 5417 * range may not overlap either input range. 5418 */ 5419 template<typename _InputIterator1, typename _InputIterator2, 5420 typename _OutputIterator, typename _Compare> 5421 inline _OutputIterator 5422 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5423 _InputIterator2 __first2, _InputIterator2 __last2, 5424 _OutputIterator __result, 5425 _Compare __comp) 5426 { 5427 // concept requirements 5428 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5429 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5431 typename iterator_traits<_InputIterator1>::value_type>) 5432 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5433 typename iterator_traits<_InputIterator2>::value_type>) 5434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5435 typename iterator_traits<_InputIterator1>::value_type, 5436 typename iterator_traits<_InputIterator2>::value_type>) 5437 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5438 typename iterator_traits<_InputIterator2>::value_type, 5439 typename iterator_traits<_InputIterator1>::value_type>) 5440 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5441 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5442 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5443 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5444 5445 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5446 __first2, __last2, __result, 5447 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5448 } 5449 5450 template<typename _ForwardIterator, typename _Compare> 5451 _GLIBCXX14_CONSTEXPR 5452 _ForwardIterator 5453 __min_element(_ForwardIterator __first, _ForwardIterator __last, 5454 _Compare __comp) 5455 { 5456 if (__first == __last) 5457 return __first; 5458 _ForwardIterator __result = __first; 5459 while (++__first != __last) 5460 if (__comp(__first, __result)) 5461 __result = __first; 5462 return __result; 5463 } 5464 5465 /** 5466 * @brief Return the minimum element in a range. 5467 * @ingroup sorting_algorithms 5468 * @param __first Start of range. 5469 * @param __last End of range. 5470 * @return Iterator referencing the first instance of the smallest value. 5471 */ 5472 template<typename _ForwardIterator> 5473 _GLIBCXX14_CONSTEXPR 5474 _ForwardIterator 5475 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 5476 { 5477 // concept requirements 5478 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5479 __glibcxx_function_requires(_LessThanComparableConcept< 5480 typename iterator_traits<_ForwardIterator>::value_type>) 5481 __glibcxx_requires_valid_range(__first, __last); 5482 __glibcxx_requires_irreflexive(__first, __last); 5483 5484 return _GLIBCXX_STD_A::__min_element(__first, __last, 5485 __gnu_cxx::__ops::__iter_less_iter()); 5486 } 5487 5488 /** 5489 * @brief Return the minimum element in a range using comparison functor. 5490 * @ingroup sorting_algorithms 5491 * @param __first Start of range. 5492 * @param __last End of range. 5493 * @param __comp Comparison functor. 5494 * @return Iterator referencing the first instance of the smallest value 5495 * according to __comp. 5496 */ 5497 template<typename _ForwardIterator, typename _Compare> 5498 _GLIBCXX14_CONSTEXPR 5499 inline _ForwardIterator 5500 min_element(_ForwardIterator __first, _ForwardIterator __last, 5501 _Compare __comp) 5502 { 5503 // concept requirements 5504 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5505 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5506 typename iterator_traits<_ForwardIterator>::value_type, 5507 typename iterator_traits<_ForwardIterator>::value_type>) 5508 __glibcxx_requires_valid_range(__first, __last); 5509 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5510 5511 return _GLIBCXX_STD_A::__min_element(__first, __last, 5512 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5513 } 5514 5515 template<typename _ForwardIterator, typename _Compare> 5516 _GLIBCXX14_CONSTEXPR 5517 _ForwardIterator 5518 __max_element(_ForwardIterator __first, _ForwardIterator __last, 5519 _Compare __comp) 5520 { 5521 if (__first == __last) return __first; 5522 _ForwardIterator __result = __first; 5523 while (++__first != __last) 5524 if (__comp(__result, __first)) 5525 __result = __first; 5526 return __result; 5527 } 5528 5529 /** 5530 * @brief Return the maximum element in a range. 5531 * @ingroup sorting_algorithms 5532 * @param __first Start of range. 5533 * @param __last End of range. 5534 * @return Iterator referencing the first instance of the largest value. 5535 */ 5536 template<typename _ForwardIterator> 5537 _GLIBCXX14_CONSTEXPR 5538 inline _ForwardIterator 5539 max_element(_ForwardIterator __first, _ForwardIterator __last) 5540 { 5541 // concept requirements 5542 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5543 __glibcxx_function_requires(_LessThanComparableConcept< 5544 typename iterator_traits<_ForwardIterator>::value_type>) 5545 __glibcxx_requires_valid_range(__first, __last); 5546 __glibcxx_requires_irreflexive(__first, __last); 5547 5548 return _GLIBCXX_STD_A::__max_element(__first, __last, 5549 __gnu_cxx::__ops::__iter_less_iter()); 5550 } 5551 5552 /** 5553 * @brief Return the maximum element in a range using comparison functor. 5554 * @ingroup sorting_algorithms 5555 * @param __first Start of range. 5556 * @param __last End of range. 5557 * @param __comp Comparison functor. 5558 * @return Iterator referencing the first instance of the largest value 5559 * according to __comp. 5560 */ 5561 template<typename _ForwardIterator, typename _Compare> 5562 _GLIBCXX14_CONSTEXPR 5563 inline _ForwardIterator 5564 max_element(_ForwardIterator __first, _ForwardIterator __last, 5565 _Compare __comp) 5566 { 5567 // concept requirements 5568 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5569 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5570 typename iterator_traits<_ForwardIterator>::value_type, 5571 typename iterator_traits<_ForwardIterator>::value_type>) 5572 __glibcxx_requires_valid_range(__first, __last); 5573 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5574 5575 return _GLIBCXX_STD_A::__max_element(__first, __last, 5576 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5577 } 5578 5579 _GLIBCXX_END_NAMESPACE_ALGO 5580 } // namespace std 5581 5582 #endif /* _STL_ALGO_H */ 5583