1// Algorithm implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 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 2, 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// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56/** @file stl_algo.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61#ifndef __GLIBCPP_INTERNAL_ALGO_H 62#define __GLIBCPP_INTERNAL_ALGO_H 63 64#include <bits/stl_heap.h> 65#include <bits/stl_tempbuf.h> // for _Temporary_buffer 66 67// See concept_check.h for the __glibcpp_*_requires macros. 68 69namespace std 70{ 71 72 /** 73 * @brief Find the median of three values. 74 * @param a A value. 75 * @param b A value. 76 * @param c A value. 77 * @return One of @p a, @p b or @p c. 78 * 79 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n 80 * then the value returned will be @c m. 81 * This is an SGI extension. 82 * @ingroup SGIextensions 83 */ 84 template<typename _Tp> 85 inline const _Tp& 86 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) 87 { 88 // concept requirements 89 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 90 if (__a < __b) 91 if (__b < __c) 92 return __b; 93 else if (__a < __c) 94 return __c; 95 else 96 return __a; 97 else if (__a < __c) 98 return __a; 99 else if (__b < __c) 100 return __c; 101 else 102 return __b; 103 } 104 105 /** 106 * @brief Find the median of three values using a predicate for comparison. 107 * @param a A value. 108 * @param b A value. 109 * @param c A value. 110 * @param comp A binary predicate. 111 * @return One of @p a, @p b or @p c. 112 * 113 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m) 114 * and @p comp(m,n) are both true then the value returned will be @c m. 115 * This is an SGI extension. 116 * @ingroup SGIextensions 117 */ 118 template<typename _Tp, typename _Compare> 119 inline const _Tp& 120 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) 121 { 122 // concept requirements 123 __glibcpp_function_requires(_BinaryFunctionConcept<_Compare,bool,_Tp,_Tp>) 124 if (__comp(__a, __b)) 125 if (__comp(__b, __c)) 126 return __b; 127 else if (__comp(__a, __c)) 128 return __c; 129 else 130 return __a; 131 else if (__comp(__a, __c)) 132 return __a; 133 else if (__comp(__b, __c)) 134 return __c; 135 else 136 return __b; 137 } 138 139 /** 140 * @brief Apply a function to every element of a sequence. 141 * @param first An input iterator. 142 * @param last An input iterator. 143 * @param f A unary function object. 144 * @return @p f. 145 * 146 * Applies the function object @p f to each element in the range 147 * @p [first,last). @p f must not modify the order of the sequence. 148 * If @p f has a return value it is ignored. 149 */ 150 template<typename _InputIter, typename _Function> 151 _Function 152 for_each(_InputIter __first, _InputIter __last, _Function __f) 153 { 154 // concept requirements 155 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 156 for ( ; __first != __last; ++__first) 157 __f(*__first); 158 return __f; 159 } 160 161 /** 162 * @if maint 163 * This is an overload used by find() for the Input Iterator case. 164 * @endif 165 */ 166 template<typename _InputIter, typename _Tp> 167 inline _InputIter 168 find(_InputIter __first, _InputIter __last, 169 const _Tp& __val, 170 input_iterator_tag) 171 { 172 while (__first != __last && !(*__first == __val)) 173 ++__first; 174 return __first; 175 } 176 177 /** 178 * @if maint 179 * This is an overload used by find_if() for the Input Iterator case. 180 * @endif 181 */ 182 template<typename _InputIter, typename _Predicate> 183 inline _InputIter 184 find_if(_InputIter __first, _InputIter __last, 185 _Predicate __pred, 186 input_iterator_tag) 187 { 188 while (__first != __last && !__pred(*__first)) 189 ++__first; 190 return __first; 191 } 192 193 /** 194 * @if maint 195 * This is an overload used by find() for the RAI case. 196 * @endif 197 */ 198 template<typename _RandomAccessIter, typename _Tp> 199 _RandomAccessIter 200 find(_RandomAccessIter __first, _RandomAccessIter __last, 201 const _Tp& __val, 202 random_access_iterator_tag) 203 { 204 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 205 = (__last - __first) >> 2; 206 207 for ( ; __trip_count > 0 ; --__trip_count) { 208 if (*__first == __val) return __first; 209 ++__first; 210 211 if (*__first == __val) return __first; 212 ++__first; 213 214 if (*__first == __val) return __first; 215 ++__first; 216 217 if (*__first == __val) return __first; 218 ++__first; 219 } 220 221 switch(__last - __first) { 222 case 3: 223 if (*__first == __val) return __first; 224 ++__first; 225 case 2: 226 if (*__first == __val) return __first; 227 ++__first; 228 case 1: 229 if (*__first == __val) return __first; 230 ++__first; 231 case 0: 232 default: 233 return __last; 234 } 235 } 236 237 /** 238 * @if maint 239 * This is an overload used by find_if() for the RAI case. 240 * @endif 241 */ 242 template<typename _RandomAccessIter, typename _Predicate> 243 _RandomAccessIter 244 find_if(_RandomAccessIter __first, _RandomAccessIter __last, 245 _Predicate __pred, 246 random_access_iterator_tag) 247 { 248 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count 249 = (__last - __first) >> 2; 250 251 for ( ; __trip_count > 0 ; --__trip_count) { 252 if (__pred(*__first)) return __first; 253 ++__first; 254 255 if (__pred(*__first)) return __first; 256 ++__first; 257 258 if (__pred(*__first)) return __first; 259 ++__first; 260 261 if (__pred(*__first)) return __first; 262 ++__first; 263 } 264 265 switch(__last - __first) { 266 case 3: 267 if (__pred(*__first)) return __first; 268 ++__first; 269 case 2: 270 if (__pred(*__first)) return __first; 271 ++__first; 272 case 1: 273 if (__pred(*__first)) return __first; 274 ++__first; 275 case 0: 276 default: 277 return __last; 278 } 279 } 280 281 /** 282 * @brief Find the first occurrence of a value in a sequence. 283 * @param first An input iterator. 284 * @param last An input iterator. 285 * @param val The value to find. 286 * @return The first iterator @c i in the range @p [first,last) 287 * such that @c *i == @p val, or @p last if no such iterator exists. 288 */ 289 template<typename _InputIter, typename _Tp> 290 inline _InputIter 291 find(_InputIter __first, _InputIter __last, 292 const _Tp& __val) 293 { 294 // concept requirements 295 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 296 __glibcpp_function_requires(_EqualOpConcept< 297 typename iterator_traits<_InputIter>::value_type, _Tp>) 298 return find(__first, __last, __val, __iterator_category(__first)); 299 } 300 301 /** 302 * @brief Find the first element in a sequence for which a predicate is true. 303 * @param first An input iterator. 304 * @param last An input iterator. 305 * @param pred A predicate. 306 * @return The first iterator @c i in the range @p [first,last) 307 * such that @p pred(*i) is true, or @p last if no such iterator exists. 308 */ 309 template<typename _InputIter, typename _Predicate> 310 inline _InputIter 311 find_if(_InputIter __first, _InputIter __last, 312 _Predicate __pred) 313 { 314 // concept requirements 315 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 316 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 317 typename iterator_traits<_InputIter>::value_type>) 318 return find_if(__first, __last, __pred, __iterator_category(__first)); 319 } 320 321 /** 322 * @brief Find two adjacent values in a sequence that are equal. 323 * @param first A forward iterator. 324 * @param last A forward iterator. 325 * @return The first iterator @c i such that @c i and @c i+1 are both 326 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), 327 * or @p last if no such iterator exists. 328 */ 329 template<typename _ForwardIter> 330 _ForwardIter 331 adjacent_find(_ForwardIter __first, _ForwardIter __last) 332 { 333 // concept requirements 334 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 335 __glibcpp_function_requires(_EqualityComparableConcept< 336 typename iterator_traits<_ForwardIter>::value_type>) 337 if (__first == __last) 338 return __last; 339 _ForwardIter __next = __first; 340 while(++__next != __last) { 341 if (*__first == *__next) 342 return __first; 343 __first = __next; 344 } 345 return __last; 346 } 347 348 /** 349 * @brief Find two adjacent values in a sequence using a predicate. 350 * @param first A forward iterator. 351 * @param last A forward iterator. 352 * @param binary_pred A binary predicate. 353 * @return The first iterator @c i such that @c i and @c i+1 are both 354 * valid iterators in @p [first,last) and such that 355 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator 356 * exists. 357 */ 358 template<typename _ForwardIter, typename _BinaryPredicate> 359 _ForwardIter 360 adjacent_find(_ForwardIter __first, _ForwardIter __last, 361 _BinaryPredicate __binary_pred) 362 { 363 // concept requirements 364 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 365 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 366 typename iterator_traits<_ForwardIter>::value_type, 367 typename iterator_traits<_ForwardIter>::value_type>) 368 if (__first == __last) 369 return __last; 370 _ForwardIter __next = __first; 371 while(++__next != __last) { 372 if (__binary_pred(*__first, *__next)) 373 return __first; 374 __first = __next; 375 } 376 return __last; 377 } 378 379 /** 380 * @brief Count the number of copies of a value in a sequence. 381 * @param first An input iterator. 382 * @param last An input iterator. 383 * @param value The value to be counted. 384 * @return The number of iterators @c i in the range @p [first,last) 385 * for which @c *i == @p value 386 */ 387 template<typename _InputIter, typename _Tp> 388 typename iterator_traits<_InputIter>::difference_type 389 count(_InputIter __first, _InputIter __last, const _Tp& __value) 390 { 391 // concept requirements 392 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 393 __glibcpp_function_requires(_EqualityComparableConcept< 394 typename iterator_traits<_InputIter>::value_type >) 395 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) 396 typename iterator_traits<_InputIter>::difference_type __n = 0; 397 for ( ; __first != __last; ++__first) 398 if (*__first == __value) 399 ++__n; 400 return __n; 401 } 402 403 /** 404 * @brief Count the elements of a sequence for which a predicate is true. 405 * @param first An input iterator. 406 * @param last An input iterator. 407 * @param pred A predicate. 408 * @return The number of iterators @c i in the range @p [first,last) 409 * for which @p pred(*i) is true. 410 */ 411 template<typename _InputIter, typename _Predicate> 412 typename iterator_traits<_InputIter>::difference_type 413 count_if(_InputIter __first, _InputIter __last, _Predicate __pred) 414 { 415 // concept requirements 416 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 417 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 418 typename iterator_traits<_InputIter>::value_type>) 419 typename iterator_traits<_InputIter>::difference_type __n = 0; 420 for ( ; __first != __last; ++__first) 421 if (__pred(*__first)) 422 ++__n; 423 return __n; 424 } 425 426 427 /** 428 * @brief Search a sequence for a matching sub-sequence. 429 * @param first1 A forward iterator. 430 * @param last1 A forward iterator. 431 * @param first2 A forward iterator. 432 * @param last2 A forward iterator. 433 * @return The first iterator @c i in the range 434 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) 435 * for each @c N in the range @p [0,last2-first2), or @p last1 if no 436 * such iterator exists. 437 * 438 * Searches the range @p [first1,last1) for a sub-sequence that compares 439 * equal value-by-value with the sequence given by @p [first2,last2) and 440 * returns an iterator to the first element of the sub-sequence, or 441 * @p last1 if the sub-sequence is not found. 442 * 443 * Because the sub-sequence must lie completely within the range 444 * @p [first1,last1) it must start at a position less than 445 * @p last1-(last2-first2) where @p last2-first2 is the length of the 446 * sub-sequence. 447 * This means that the returned iterator @c i will be in the range 448 * @p [first1,last1-(last2-first2)) 449 */ 450 template<typename _ForwardIter1, typename _ForwardIter2> 451 _ForwardIter1 452 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 453 _ForwardIter2 __first2, _ForwardIter2 __last2) 454 { 455 // concept requirements 456 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 457 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 458 __glibcpp_function_requires(_EqualOpConcept< 459 typename iterator_traits<_ForwardIter1>::value_type, 460 typename iterator_traits<_ForwardIter2>::value_type>) 461 462 // Test for empty ranges 463 if (__first1 == __last1 || __first2 == __last2) 464 return __first1; 465 466 // Test for a pattern of length 1. 467 _ForwardIter2 __tmp(__first2); 468 ++__tmp; 469 if (__tmp == __last2) 470 return find(__first1, __last1, *__first2); 471 472 // General case. 473 474 _ForwardIter2 __p1, __p; 475 476 __p1 = __first2; ++__p1; 477 478 _ForwardIter1 __current = __first1; 479 480 while (__first1 != __last1) { 481 __first1 = find(__first1, __last1, *__first2); 482 if (__first1 == __last1) 483 return __last1; 484 485 __p = __p1; 486 __current = __first1; 487 if (++__current == __last1) 488 return __last1; 489 490 while (*__current == *__p) { 491 if (++__p == __last2) 492 return __first1; 493 if (++__current == __last1) 494 return __last1; 495 } 496 497 ++__first1; 498 } 499 return __first1; 500 } 501 502 /** 503 * @brief Search a sequence for a matching sub-sequence using a predicate. 504 * @param first1 A forward iterator. 505 * @param last1 A forward iterator. 506 * @param first2 A forward iterator. 507 * @param last2 A forward iterator. 508 * @param predicate A binary predicate. 509 * @return The first iterator @c i in the range 510 * @p [first1,last1-(last2-first2)) such that 511 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range 512 * @p [0,last2-first2), or @p last1 if no such iterator exists. 513 * 514 * Searches the range @p [first1,last1) for a sub-sequence that compares 515 * equal value-by-value with the sequence given by @p [first2,last2), 516 * using @p predicate to determine equality, and returns an iterator 517 * to the first element of the sub-sequence, or @p last1 if no such 518 * iterator exists. 519 * 520 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 521 */ 522 template<typename _ForwardIter1, typename _ForwardIter2, typename _BinaryPred> 523 _ForwardIter1 524 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 525 _ForwardIter2 __first2, _ForwardIter2 __last2, 526 _BinaryPred __predicate) 527 { 528 // concept requirements 529 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 530 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 531 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred, 532 typename iterator_traits<_ForwardIter1>::value_type, 533 typename iterator_traits<_ForwardIter2>::value_type>) 534 535 // Test for empty ranges 536 if (__first1 == __last1 || __first2 == __last2) 537 return __first1; 538 539 // Test for a pattern of length 1. 540 _ForwardIter2 __tmp(__first2); 541 ++__tmp; 542 if (__tmp == __last2) { 543 while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 544 ++__first1; 545 return __first1; 546 } 547 548 // General case. 549 550 _ForwardIter2 __p1, __p; 551 552 __p1 = __first2; ++__p1; 553 554 _ForwardIter1 __current = __first1; 555 556 while (__first1 != __last1) { 557 while (__first1 != __last1) { 558 if (__predicate(*__first1, *__first2)) 559 break; 560 ++__first1; 561 } 562 while (__first1 != __last1 && !__predicate(*__first1, *__first2)) 563 ++__first1; 564 if (__first1 == __last1) 565 return __last1; 566 567 __p = __p1; 568 __current = __first1; 569 if (++__current == __last1) return __last1; 570 571 while (__predicate(*__current, *__p)) { 572 if (++__p == __last2) 573 return __first1; 574 if (++__current == __last1) 575 return __last1; 576 } 577 578 ++__first1; 579 } 580 return __first1; 581 } 582 583 /** 584 * @brief Search a sequence for a number of consecutive values. 585 * @param first A forward iterator. 586 * @param last A forward iterator. 587 * @param count The number of consecutive values. 588 * @param val The value to find. 589 * @return The first iterator @c i in the range @p [first,last-count) 590 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count), 591 * or @p last if no such iterator exists. 592 * 593 * Searches the range @p [first,last) for @p count consecutive elements 594 * equal to @p val. 595 */ 596 template<typename _ForwardIter, typename _Integer, typename _Tp> 597 _ForwardIter 598 search_n(_ForwardIter __first, _ForwardIter __last, 599 _Integer __count, const _Tp& __val) 600 { 601 // concept requirements 602 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 603 __glibcpp_function_requires(_EqualityComparableConcept< 604 typename iterator_traits<_ForwardIter>::value_type>) 605 __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) 606 607 if (__count <= 0) 608 return __first; 609 else { 610 __first = find(__first, __last, __val); 611 while (__first != __last) { 612 typename iterator_traits<_ForwardIter>::difference_type __n = __count; 613 --__n; 614 _ForwardIter __i = __first; 615 ++__i; 616 while (__i != __last && __n != 0 && *__i == __val) { 617 ++__i; 618 --__n; 619 } 620 if (__n == 0) 621 return __first; 622 else 623 __first = find(__i, __last, __val); 624 } 625 return __last; 626 } 627 } 628 629 /** 630 * @brief Search a sequence for a number of consecutive values using a 631 * predicate. 632 * @param first A forward iterator. 633 * @param last A forward iterator. 634 * @param count The number of consecutive values. 635 * @param val The value to find. 636 * @param binary_pred A binary predicate. 637 * @return The first iterator @c i in the range @p [first,last-count) 638 * such that @p binary_pred(*(i+N),val) is true for each @c N in the 639 * range @p [0,count), or @p last if no such iterator exists. 640 * 641 * Searches the range @p [first,last) for @p count consecutive elements 642 * for which the predicate returns true. 643 */ 644 template<typename _ForwardIter, typename _Integer, typename _Tp, 645 typename _BinaryPred> 646 _ForwardIter 647 search_n(_ForwardIter __first, _ForwardIter __last, 648 _Integer __count, const _Tp& __val, 649 _BinaryPred __binary_pred) 650 { 651 // concept requirements 652 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 653 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred, 654 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 655 656 if (__count <= 0) 657 return __first; 658 else { 659 while (__first != __last) { 660 if (__binary_pred(*__first, __val)) 661 break; 662 ++__first; 663 } 664 while (__first != __last) { 665 typename iterator_traits<_ForwardIter>::difference_type __n = __count; 666 --__n; 667 _ForwardIter __i = __first; 668 ++__i; 669 while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { 670 ++__i; 671 --__n; 672 } 673 if (__n == 0) 674 return __first; 675 else { 676 while (__i != __last) { 677 if (__binary_pred(*__i, __val)) 678 break; 679 ++__i; 680 } 681 __first = __i; 682 } 683 } 684 return __last; 685 } 686 } 687 688 /** 689 * @brief Swap the elements of two sequences. 690 * @param first1 A forward iterator. 691 * @param last1 A forward iterator. 692 * @param first2 A forward iterator. 693 * @return An iterator equal to @p first2+(last1-first1). 694 * 695 * Swaps each element in the range @p [first1,last1) with the 696 * corresponding element in the range @p [first2,(last1-first1)). 697 * The ranges must not overlap. 698 */ 699 template<typename _ForwardIter1, typename _ForwardIter2> 700 _ForwardIter2 701 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, 702 _ForwardIter2 __first2) 703 { 704 // concept requirements 705 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter1>) 706 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter2>) 707 __glibcpp_function_requires(_ConvertibleConcept< 708 typename iterator_traits<_ForwardIter1>::value_type, 709 typename iterator_traits<_ForwardIter2>::value_type>) 710 __glibcpp_function_requires(_ConvertibleConcept< 711 typename iterator_traits<_ForwardIter2>::value_type, 712 typename iterator_traits<_ForwardIter1>::value_type>) 713 714 for ( ; __first1 != __last1; ++__first1, ++__first2) 715 iter_swap(__first1, __first2); 716 return __first2; 717 } 718 719 /** 720 * @brief Perform an operation on a sequence. 721 * @param first An input iterator. 722 * @param last An input iterator. 723 * @param result An output iterator. 724 * @param unary_op A unary operator. 725 * @return An output iterator equal to @p result+(last-first). 726 * 727 * Applies the operator to each element in the input range and assigns 728 * the results to successive elements of the output sequence. 729 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the 730 * range @p [0,last-first). 731 * 732 * @p unary_op must not alter its argument. 733 */ 734 template<typename _InputIter, typename _OutputIter, typename _UnaryOperation> 735 _OutputIter 736 transform(_InputIter __first, _InputIter __last, 737 _OutputIter __result, _UnaryOperation __unary_op) 738 { 739 // concept requirements 740 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 741 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 742 // "the type returned by a _UnaryOperation" 743 __typeof__(__unary_op(*__first))>) 744 745 for ( ; __first != __last; ++__first, ++__result) 746 *__result = __unary_op(*__first); 747 return __result; 748 } 749 750 /** 751 * @brief Perform an operation on corresponding elements of two sequences. 752 * @param first1 An input iterator. 753 * @param last1 An input iterator. 754 * @param first2 An input iterator. 755 * @param result An output iterator. 756 * @param binary_op A binary operator. 757 * @return An output iterator equal to @p result+(last-first). 758 * 759 * Applies the operator to the corresponding elements in the two 760 * input ranges and assigns the results to successive elements of the 761 * output sequence. 762 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each 763 * @c N in the range @p [0,last1-first1). 764 * 765 * @p binary_op must not alter either of its arguments. 766 */ 767 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 768 typename _BinaryOperation> 769 _OutputIter 770 transform(_InputIter1 __first1, _InputIter1 __last1, 771 _InputIter2 __first2, _OutputIter __result, 772 _BinaryOperation __binary_op) 773 { 774 // concept requirements 775 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 776 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 777 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 778 // "the type returned by a _BinaryOperation" 779 __typeof__(__binary_op(*__first1,*__first2))>) 780 781 for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) 782 *__result = __binary_op(*__first1, *__first2); 783 return __result; 784 } 785 786 /** 787 * @brief Replace each occurrence of one value in a sequence with another 788 * value. 789 * @param first A forward iterator. 790 * @param last A forward iterator. 791 * @param old_value The value to be replaced. 792 * @param new_value The replacement value. 793 * @return replace() returns no value. 794 * 795 * For each iterator @c i in the range @p [first,last) if @c *i == 796 * @p old_value then the assignment @c *i = @p new_value is performed. 797 */ 798 template<typename _ForwardIter, typename _Tp> 799 void 800 replace(_ForwardIter __first, _ForwardIter __last, 801 const _Tp& __old_value, const _Tp& __new_value) 802 { 803 // concept requirements 804 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 805 __glibcpp_function_requires(_EqualOpConcept< 806 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 807 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 808 typename iterator_traits<_ForwardIter>::value_type>) 809 810 for ( ; __first != __last; ++__first) 811 if (*__first == __old_value) 812 *__first = __new_value; 813 } 814 815 /** 816 * @brief Replace each value in a sequence for which a predicate returns 817 * true with another value. 818 * @param first A forward iterator. 819 * @param last A forward iterator. 820 * @param pred A predicate. 821 * @param new_value The replacement value. 822 * @return replace_if() returns no value. 823 * 824 * For each iterator @c i in the range @p [first,last) if @p pred(*i) 825 * is true then the assignment @c *i = @p new_value is performed. 826 */ 827 template<typename _ForwardIter, typename _Predicate, typename _Tp> 828 void 829 replace_if(_ForwardIter __first, _ForwardIter __last, 830 _Predicate __pred, const _Tp& __new_value) 831 { 832 // concept requirements 833 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 834 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 835 typename iterator_traits<_ForwardIter>::value_type>) 836 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 837 typename iterator_traits<_ForwardIter>::value_type>) 838 839 for ( ; __first != __last; ++__first) 840 if (__pred(*__first)) 841 *__first = __new_value; 842 } 843 844 /** 845 * @brief Copy a sequence, replacing each element of one value with another 846 * value. 847 * @param first An input iterator. 848 * @param last An input iterator. 849 * @param result An output iterator. 850 * @param old_value The value to be replaced. 851 * @param new_value The replacement value. 852 * @return The end of the output sequence, @p result+(last-first). 853 * 854 * Copies each element in the input range @p [first,last) to the 855 * output range @p [result,result+(last-first)) replacing elements 856 * equal to @p old_value with @p new_value. 857 */ 858 template<typename _InputIter, typename _OutputIter, typename _Tp> 859 _OutputIter 860 replace_copy(_InputIter __first, _InputIter __last, 861 _OutputIter __result, 862 const _Tp& __old_value, const _Tp& __new_value) 863 { 864 // concept requirements 865 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 866 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 867 typename iterator_traits<_InputIter>::value_type>) 868 __glibcpp_function_requires(_EqualOpConcept< 869 typename iterator_traits<_InputIter>::value_type, _Tp>) 870 871 for ( ; __first != __last; ++__first, ++__result) 872 *__result = *__first == __old_value ? __new_value : *__first; 873 return __result; 874 } 875 876 /** 877 * @brief Copy a sequence, replacing each value for which a predicate 878 * returns true with another value. 879 * @param first An input iterator. 880 * @param last An input iterator. 881 * @param result An output iterator. 882 * @param pred A predicate. 883 * @param new_value The replacement value. 884 * @return The end of the output sequence, @p result+(last-first). 885 * 886 * Copies each element in the range @p [first,last) to the range 887 * @p [result,result+(last-first)) replacing elements for which 888 * @p pred returns true with @p new_value. 889 */ 890 template<typename _InputIter, typename _OutputIter, typename _Predicate, 891 typename _Tp> 892 _OutputIter 893 replace_copy_if(_InputIter __first, _InputIter __last, 894 _OutputIter __result, 895 _Predicate __pred, const _Tp& __new_value) 896 { 897 // concept requirements 898 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 899 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 900 typename iterator_traits<_InputIter>::value_type>) 901 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 902 typename iterator_traits<_InputIter>::value_type>) 903 904 for ( ; __first != __last; ++__first, ++__result) 905 *__result = __pred(*__first) ? __new_value : *__first; 906 return __result; 907 } 908 909 /** 910 * @brief Assign the result of a function object to each value in a 911 * sequence. 912 * @param first A forward iterator. 913 * @param last A forward iterator. 914 * @param gen A function object taking no arguments. 915 * @return generate() returns no value. 916 * 917 * Performs the assignment @c *i = @p gen() for each @c i in the range 918 * @p [first,last). 919 */ 920 template<typename _ForwardIter, typename _Generator> 921 void 922 generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) 923 { 924 // concept requirements 925 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 926 __glibcpp_function_requires(_GeneratorConcept<_Generator, 927 typename iterator_traits<_ForwardIter>::value_type>) 928 929 for ( ; __first != __last; ++__first) 930 *__first = __gen(); 931 } 932 933 /** 934 * @brief Assign the result of a function object to each value in a 935 * sequence. 936 * @param first A forward iterator. 937 * @param n The length of the sequence. 938 * @param gen A function object taking no arguments. 939 * @return The end of the sequence, @p first+n 940 * 941 * Performs the assignment @c *i = @p gen() for each @c i in the range 942 * @p [first,first+n). 943 */ 944 template<typename _OutputIter, typename _Size, typename _Generator> 945 _OutputIter 946 generate_n(_OutputIter __first, _Size __n, _Generator __gen) 947 { 948 // concept requirements 949 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 950 // "the type returned by a _Generator" 951 __typeof__(__gen())>) 952 953 for ( ; __n > 0; --__n, ++__first) 954 *__first = __gen(); 955 return __first; 956 } 957 958 /** 959 * @brief Copy a sequence, removing elements of a given value. 960 * @param first An input iterator. 961 * @param last An input iterator. 962 * @param result An output iterator. 963 * @param value The value to be removed. 964 * @return An iterator designating the end of the resulting sequence. 965 * 966 * Copies each element in the range @p [first,last) not equal to @p value 967 * to the range beginning at @p result. 968 * remove_copy() is stable, so the relative order of elements that are 969 * copied is unchanged. 970 */ 971 template<typename _InputIter, typename _OutputIter, typename _Tp> 972 _OutputIter 973 remove_copy(_InputIter __first, _InputIter __last, 974 _OutputIter __result, const _Tp& __value) 975 { 976 // concept requirements 977 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 978 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 979 typename iterator_traits<_InputIter>::value_type>) 980 __glibcpp_function_requires(_EqualOpConcept< 981 typename iterator_traits<_InputIter>::value_type, _Tp>) 982 983 for ( ; __first != __last; ++__first) 984 if (!(*__first == __value)) { 985 *__result = *__first; 986 ++__result; 987 } 988 return __result; 989 } 990 991 /** 992 * @brief Copy a sequence, removing elements for which a predicate is true. 993 * @param first An input iterator. 994 * @param last An input iterator. 995 * @param result An output iterator. 996 * @param pred A predicate. 997 * @return An iterator designating the end of the resulting sequence. 998 * 999 * Copies each element in the range @p [first,last) for which 1000 * @p pred returns true to the range beginning at @p result. 1001 * 1002 * remove_copy_if() is stable, so the relative order of elements that are 1003 * copied is unchanged. 1004 */ 1005 template<typename _InputIter, typename _OutputIter, typename _Predicate> 1006 _OutputIter 1007 remove_copy_if(_InputIter __first, _InputIter __last, 1008 _OutputIter __result, _Predicate __pred) 1009 { 1010 // concept requirements 1011 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 1012 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 1013 typename iterator_traits<_InputIter>::value_type>) 1014 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 1015 typename iterator_traits<_InputIter>::value_type>) 1016 1017 for ( ; __first != __last; ++__first) 1018 if (!__pred(*__first)) { 1019 *__result = *__first; 1020 ++__result; 1021 } 1022 return __result; 1023 } 1024 1025 /** 1026 * @brief Remove elements from a sequence. 1027 * @param first An input iterator. 1028 * @param last An input iterator. 1029 * @param value The value to be removed. 1030 * @return An iterator designating the end of the resulting sequence. 1031 * 1032 * All elements equal to @p value are removed from the range 1033 * @p [first,last). 1034 * 1035 * remove() is stable, so the relative order of elements that are 1036 * not removed is unchanged. 1037 * 1038 * Elements between the end of the resulting sequence and @p last 1039 * are still present, but their value is unspecified. 1040 */ 1041 template<typename _ForwardIter, typename _Tp> 1042 _ForwardIter 1043 remove(_ForwardIter __first, _ForwardIter __last, 1044 const _Tp& __value) 1045 { 1046 // concept requirements 1047 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 1048 __glibcpp_function_requires(_ConvertibleConcept<_Tp, 1049 typename iterator_traits<_ForwardIter>::value_type>) 1050 __glibcpp_function_requires(_EqualOpConcept< 1051 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 1052 1053 __first = find(__first, __last, __value); 1054 _ForwardIter __i = __first; 1055 return __first == __last ? __first 1056 : remove_copy(++__i, __last, __first, __value); 1057 } 1058 1059 /** 1060 * @brief Remove elements from a sequence using a predicate. 1061 * @param first A forward iterator. 1062 * @param last A forward iterator. 1063 * @param pred A predicate. 1064 * @return An iterator designating the end of the resulting sequence. 1065 * 1066 * All elements for which @p pred returns true are removed from the range 1067 * @p [first,last). 1068 * 1069 * remove_if() is stable, so the relative order of elements that are 1070 * not removed is unchanged. 1071 * 1072 * Elements between the end of the resulting sequence and @p last 1073 * are still present, but their value is unspecified. 1074 */ 1075 template<typename _ForwardIter, typename _Predicate> 1076 _ForwardIter 1077 remove_if(_ForwardIter __first, _ForwardIter __last, 1078 _Predicate __pred) 1079 { 1080 // concept requirements 1081 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 1082 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 1083 typename iterator_traits<_ForwardIter>::value_type>) 1084 1085 __first = find_if(__first, __last, __pred); 1086 _ForwardIter __i = __first; 1087 return __first == __last ? __first 1088 : remove_copy_if(++__i, __last, __first, __pred); 1089 } 1090 1091 /** 1092 * @if maint 1093 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter) 1094 * overloaded for output iterators. 1095 * @endif 1096 */ 1097 template<typename _InputIter, typename _OutputIter> 1098 _OutputIter 1099 __unique_copy(_InputIter __first, _InputIter __last, 1100 _OutputIter __result, 1101 output_iterator_tag) 1102 { 1103 // concept requirements -- taken care of in dispatching function 1104 typename iterator_traits<_InputIter>::value_type __value = *__first; 1105 *__result = __value; 1106 while (++__first != __last) 1107 if (!(__value == *__first)) { 1108 __value = *__first; 1109 *++__result = __value; 1110 } 1111 return ++__result; 1112 } 1113 1114 /** 1115 * @if maint 1116 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter) 1117 * overloaded for forward iterators. 1118 * @endif 1119 */ 1120 template<typename _InputIter, typename _ForwardIter> 1121 _ForwardIter 1122 __unique_copy(_InputIter __first, _InputIter __last, 1123 _ForwardIter __result, 1124 forward_iterator_tag) 1125 { 1126 // concept requirements -- taken care of in dispatching function 1127 *__result = *__first; 1128 while (++__first != __last) 1129 if (!(*__result == *__first)) 1130 *++__result = *__first; 1131 return ++__result; 1132 } 1133 1134 /** 1135 * @brief Copy a sequence, removing consecutive duplicate values. 1136 * @param first An input iterator. 1137 * @param last An input iterator. 1138 * @param result An output iterator. 1139 * @return An iterator designating the end of the resulting sequence. 1140 * 1141 * Copies each element in the range @p [first,last) to the range 1142 * beginning at @p result, except that only the first element is copied 1143 * from groups of consecutive elements that compare equal. 1144 * unique_copy() is stable, so the relative order of elements that are 1145 * copied is unchanged. 1146 */ 1147 template<typename _InputIter, typename _OutputIter> 1148 inline _OutputIter 1149 unique_copy(_InputIter __first, _InputIter __last, 1150 _OutputIter __result) 1151 { 1152 // concept requirements 1153 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 1154 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 1155 typename iterator_traits<_InputIter>::value_type>) 1156 __glibcpp_function_requires(_EqualityComparableConcept< 1157 typename iterator_traits<_InputIter>::value_type>) 1158 1159 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 1160 1161 if (__first == __last) return __result; 1162 return __unique_copy(__first, __last, __result, _IterType()); 1163 } 1164 1165 /** 1166 * @if maint 1167 * This is an uglified 1168 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate) 1169 * overloaded for output iterators. 1170 * @endif 1171 */ 1172 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 1173 _OutputIter 1174 __unique_copy(_InputIter __first, _InputIter __last, 1175 _OutputIter __result, 1176 _BinaryPredicate __binary_pred, 1177 output_iterator_tag) 1178 { 1179 // concept requirements -- iterators already checked 1180 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1181 typename iterator_traits<_InputIter>::value_type, 1182 typename iterator_traits<_InputIter>::value_type>) 1183 1184 typename iterator_traits<_InputIter>::value_type __value = *__first; 1185 *__result = __value; 1186 while (++__first != __last) 1187 if (!__binary_pred(__value, *__first)) { 1188 __value = *__first; 1189 *++__result = __value; 1190 } 1191 return ++__result; 1192 } 1193 1194 /** 1195 * @if maint 1196 * This is an uglified 1197 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate) 1198 * overloaded for forward iterators. 1199 * @endif 1200 */ 1201 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 1202 _ForwardIter 1203 __unique_copy(_InputIter __first, _InputIter __last, 1204 _ForwardIter __result, 1205 _BinaryPredicate __binary_pred, 1206 forward_iterator_tag) 1207 { 1208 // concept requirements -- iterators already checked 1209 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1210 typename iterator_traits<_ForwardIter>::value_type, 1211 typename iterator_traits<_InputIter>::value_type>) 1212 1213 *__result = *__first; 1214 while (++__first != __last) 1215 if (!__binary_pred(*__result, *__first)) *++__result = *__first; 1216 return ++__result; 1217 } 1218 1219 /** 1220 * @brief Copy a sequence, removing consecutive values using a predicate. 1221 * @param first An input iterator. 1222 * @param last An input iterator. 1223 * @param result An output iterator. 1224 * @param binary_pred A binary predicate. 1225 * @return An iterator designating the end of the resulting sequence. 1226 * 1227 * Copies each element in the range @p [first,last) to the range 1228 * beginning at @p result, except that only the first element is copied 1229 * from groups of consecutive elements for which @p binary_pred returns 1230 * true. 1231 * unique_copy() is stable, so the relative order of elements that are 1232 * copied is unchanged. 1233 */ 1234 template<typename _InputIter, typename _OutputIter, typename _BinaryPredicate> 1235 inline _OutputIter 1236 unique_copy(_InputIter __first, _InputIter __last, 1237 _OutputIter __result, 1238 _BinaryPredicate __binary_pred) 1239 { 1240 // concept requirements -- predicates checked later 1241 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 1242 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 1243 typename iterator_traits<_InputIter>::value_type>) 1244 1245 typedef typename iterator_traits<_OutputIter>::iterator_category _IterType; 1246 1247 if (__first == __last) return __result; 1248 return __unique_copy(__first, __last, 1249__result, __binary_pred, _IterType()); 1250 } 1251 1252 /** 1253 * @brief Remove consecutive duplicate values from a sequence. 1254 * @param first A forward iterator. 1255 * @param last A forward iterator. 1256 * @return An iterator designating the end of the resulting sequence. 1257 * 1258 * Removes all but the first element from each group of consecutive 1259 * values that compare equal. 1260 * unique() is stable, so the relative order of elements that are 1261 * not removed is unchanged. 1262 * Elements between the end of the resulting sequence and @p last 1263 * are still present, but their value is unspecified. 1264 */ 1265 template<typename _ForwardIter> 1266 _ForwardIter 1267 unique(_ForwardIter __first, _ForwardIter __last) 1268 { 1269 // concept requirements 1270 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 1271 __glibcpp_function_requires(_EqualityComparableConcept< 1272 typename iterator_traits<_ForwardIter>::value_type>) 1273 1274 __first = adjacent_find(__first, __last); 1275 return unique_copy(__first, __last, __first); 1276 } 1277 1278 /** 1279 * @brief Remove consecutive values from a sequence using a predicate. 1280 * @param first A forward iterator. 1281 * @param last A forward iterator. 1282 * @param binary_pred A binary predicate. 1283 * @return An iterator designating the end of the resulting sequence. 1284 * 1285 * Removes all but the first element from each group of consecutive 1286 * values for which @p binary_pred returns true. 1287 * unique() is stable, so the relative order of elements that are 1288 * not removed is unchanged. 1289 * Elements between the end of the resulting sequence and @p last 1290 * are still present, but their value is unspecified. 1291 */ 1292 template<typename _ForwardIter, typename _BinaryPredicate> 1293 _ForwardIter 1294 unique(_ForwardIter __first, _ForwardIter __last, 1295 _BinaryPredicate __binary_pred) 1296 { 1297 // concept requirements 1298 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 1299 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1300 typename iterator_traits<_ForwardIter>::value_type, 1301 typename iterator_traits<_ForwardIter>::value_type>) 1302 1303 __first = adjacent_find(__first, __last, __binary_pred); 1304 return unique_copy(__first, __last, __first, __binary_pred); 1305 } 1306 1307 /** 1308 * @if maint 1309 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter) 1310 * overloaded for bidirectional iterators. 1311 * @endif 1312 */ 1313 template<typename _BidirectionalIter> 1314 void 1315 __reverse(_BidirectionalIter __first, _BidirectionalIter __last, 1316 bidirectional_iterator_tag) 1317 { 1318 while (true) 1319 if (__first == __last || __first == --__last) 1320 return; 1321 else 1322 iter_swap(__first++, __last); 1323 } 1324 1325 /** 1326 * @if maint 1327 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter) 1328 * overloaded for bidirectional iterators. 1329 * @endif 1330 */ 1331 template<typename _RandomAccessIter> 1332 void 1333 __reverse(_RandomAccessIter __first, _RandomAccessIter __last, 1334 random_access_iterator_tag) 1335 { 1336 while (__first < __last) 1337 iter_swap(__first++, --__last); 1338 } 1339 1340 /** 1341 * @brief Reverse a sequence. 1342 * @param first A bidirectional iterator. 1343 * @param last A bidirectional iterator. 1344 * @return reverse() returns no value. 1345 * 1346 * Reverses the order of the elements in the range @p [first,last), 1347 * so that the first element becomes the last etc. 1348 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse() 1349 * swaps @p *(first+i) and @p *(last-(i+1)) 1350 */ 1351 template<typename _BidirectionalIter> 1352 inline void 1353 reverse(_BidirectionalIter __first, _BidirectionalIter __last) 1354 { 1355 // concept requirements 1356 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 1357 _BidirectionalIter>) 1358 __reverse(__first, __last, __iterator_category(__first)); 1359 } 1360 1361 /** 1362 * @brief Copy a sequence, reversing its elements. 1363 * @param first A bidirectional iterator. 1364 * @param last A bidirectional iterator. 1365 * @param result An output iterator. 1366 * @return An iterator designating the end of the resulting sequence. 1367 * 1368 * Copies the elements in the range @p [first,last) to the range 1369 * @p [result,result+(last-first)) such that the order of the 1370 * elements is reversed. 1371 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy() 1372 * performs the assignment @p *(result+(last-first)-i) = *(first+i). 1373 * The ranges @p [first,last) and @p [result,result+(last-first)) 1374 * must not overlap. 1375 */ 1376 template<typename _BidirectionalIter, typename _OutputIter> 1377 _OutputIter 1378 reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last, 1379 _OutputIter __result) 1380 { 1381 // concept requirements 1382 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 1383 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 1384 typename iterator_traits<_BidirectionalIter>::value_type>) 1385 1386 while (__first != __last) { 1387 --__last; 1388 *__result = *__last; 1389 ++__result; 1390 } 1391 return __result; 1392 } 1393 1394 1395 /** 1396 * @if maint 1397 * This is a helper function for the rotate algorithm specialized on RAIs. 1398 * It returns the greatest common divisor of two integer values. 1399 * @endif 1400 */ 1401 template<typename _EuclideanRingElement> 1402 _EuclideanRingElement 1403 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 1404 { 1405 while (__n != 0) { 1406 _EuclideanRingElement __t = __m % __n; 1407 __m = __n; 1408 __n = __t; 1409 } 1410 return __m; 1411 } 1412 1413 /** 1414 * @if maint 1415 * This is a helper function for the rotate algorithm. 1416 * @endif 1417 */ 1418 template<typename _ForwardIter> 1419 void 1420 __rotate(_ForwardIter __first, 1421 _ForwardIter __middle, 1422 _ForwardIter __last, 1423 forward_iterator_tag) 1424 { 1425 if ((__first == __middle) || (__last == __middle)) 1426 return; 1427 1428 _ForwardIter __first2 = __middle; 1429 do { 1430 swap(*__first++, *__first2++); 1431 if (__first == __middle) 1432 __middle = __first2; 1433 } while (__first2 != __last); 1434 1435 __first2 = __middle; 1436 1437 while (__first2 != __last) { 1438 swap(*__first++, *__first2++); 1439 if (__first == __middle) 1440 __middle = __first2; 1441 else if (__first2 == __last) 1442 __first2 = __middle; 1443 } 1444 } 1445 1446 /** 1447 * @if maint 1448 * This is a helper function for the rotate algorithm. 1449 * @endif 1450 */ 1451 template<typename _BidirectionalIter> 1452 void 1453 __rotate(_BidirectionalIter __first, 1454 _BidirectionalIter __middle, 1455 _BidirectionalIter __last, 1456 bidirectional_iterator_tag) 1457 { 1458 // concept requirements 1459 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 1460 _BidirectionalIter>) 1461 1462 if ((__first == __middle) || (__last == __middle)) 1463 return; 1464 1465 __reverse(__first, __middle, bidirectional_iterator_tag()); 1466 __reverse(__middle, __last, bidirectional_iterator_tag()); 1467 1468 while (__first != __middle && __middle != __last) 1469 swap (*__first++, *--__last); 1470 1471 if (__first == __middle) { 1472 __reverse(__middle, __last, bidirectional_iterator_tag()); 1473 } 1474 else { 1475 __reverse(__first, __middle, bidirectional_iterator_tag()); 1476 } 1477 } 1478 1479 /** 1480 * @if maint 1481 * This is a helper function for the rotate algorithm. 1482 * @endif 1483 */ 1484 template<typename _RandomAccessIter> 1485 void 1486 __rotate(_RandomAccessIter __first, 1487 _RandomAccessIter __middle, 1488 _RandomAccessIter __last, 1489 random_access_iterator_tag) 1490 { 1491 // concept requirements 1492 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 1493 _RandomAccessIter>) 1494 1495 if ((__first == __middle) || (__last == __middle)) 1496 return; 1497 1498 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 1499 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 1500 1501 _Distance __n = __last - __first; 1502 _Distance __k = __middle - __first; 1503 _Distance __l = __n - __k; 1504 1505 if (__k == __l) { 1506 swap_ranges(__first, __middle, __middle); 1507 return; 1508 } 1509 1510 _Distance __d = __gcd(__n, __k); 1511 1512 for (_Distance __i = 0; __i < __d; __i++) { 1513 _ValueType __tmp = *__first; 1514 _RandomAccessIter __p = __first; 1515 1516 if (__k < __l) { 1517 for (_Distance __j = 0; __j < __l/__d; __j++) { 1518 if (__p > __first + __l) { 1519 *__p = *(__p - __l); 1520 __p -= __l; 1521 } 1522 1523 *__p = *(__p + __k); 1524 __p += __k; 1525 } 1526 } 1527 1528 else { 1529 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { 1530 if (__p < __last - __k) { 1531 *__p = *(__p + __k); 1532 __p += __k; 1533 } 1534 1535 *__p = * (__p - __l); 1536 __p -= __l; 1537 } 1538 } 1539 1540 *__p = __tmp; 1541 ++__first; 1542 } 1543 } 1544 1545 /** 1546 * @brief Rotate the elements of a sequence. 1547 * @param first A forward iterator. 1548 * @param middle A forward iterator. 1549 * @param last A forward iterator. 1550 * @return Nothing. 1551 * 1552 * Rotates the elements of the range @p [first,last) by @p (middle-first) 1553 * positions so that the element at @p middle is moved to @p first, the 1554 * element at @p middle+1 is moved to @first+1 and so on for each element 1555 * in the range @p [first,last). 1556 * 1557 * This effectively swaps the ranges @p [first,middle) and 1558 * @p [middle,last). 1559 * 1560 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for 1561 * each @p n in the range @p [0,last-first). 1562 */ 1563 template<typename _ForwardIter> 1564 inline void 1565 rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) 1566 { 1567 // concept requirements 1568 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 1569 1570 typedef typename iterator_traits<_ForwardIter>::iterator_category _IterType; 1571 __rotate(__first, __middle, __last, _IterType()); 1572 } 1573 1574 /** 1575 * @brief Copy a sequence, rotating its elements. 1576 * @param first A forward iterator. 1577 * @param middle A forward iterator. 1578 * @param last A forward iterator. 1579 * @param result An output iterator. 1580 * @return An iterator designating the end of the resulting sequence. 1581 * 1582 * Copies the elements of the range @p [first,last) to the range 1583 * beginning at @result, rotating the copied elements by @p (middle-first) 1584 * positions so that the element at @p middle is moved to @p result, the 1585 * element at @p middle+1 is moved to @result+1 and so on for each element 1586 * in the range @p [first,last). 1587 * 1588 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for 1589 * each @p n in the range @p [0,last-first). 1590 */ 1591 template<typename _ForwardIter, typename _OutputIter> 1592 _OutputIter 1593 rotate_copy(_ForwardIter __first, _ForwardIter __middle, 1594 _ForwardIter __last, _OutputIter __result) 1595 { 1596 // concept requirements 1597 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 1598 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 1599 typename iterator_traits<_ForwardIter>::value_type>) 1600 1601 return copy(__first, __middle, copy(__middle, __last, __result)); 1602 } 1603 1604 1605 /** 1606 * @if maint 1607 * Return a random number in the range [0, __n). This function encapsulates 1608 * whether we're using rand (part of the standard C library) or lrand48 1609 * (not standard, but a much better choice whenever it's available). 1610 * 1611 * XXX There is no corresponding encapsulation fn to seed the generator. 1612 * @endif 1613 */ 1614 template<typename _Distance> 1615 inline _Distance 1616 __random_number(_Distance __n) 1617 { 1618 #ifdef _GLIBCPP_HAVE_DRAND48 1619 return lrand48() % __n; 1620 #else 1621 return rand() % __n; 1622 #endif 1623 } 1624 1625 1626 /** 1627 * @brief Randomly shuffle the elements of a sequence. 1628 * @param first A forward iterator. 1629 * @param last A forward iterator. 1630 * @return Nothing. 1631 * 1632 * Reorder the elements in the range @p [first,last) using a random 1633 * distribution, so that every possible ordering of the sequence is 1634 * equally likely. 1635 */ 1636 template<typename _RandomAccessIter> 1637 inline void 1638 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last) 1639 { 1640 // concept requirements 1641 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 1642 _RandomAccessIter>) 1643 1644 if (__first == __last) return; 1645 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 1646 iter_swap(__i, __first + __random_number((__i - __first) + 1)); 1647 } 1648 1649 /** 1650 * @brief Shuffle the elements of a sequence using a random number 1651 * generator. 1652 * @param first A forward iterator. 1653 * @param last A forward iterator. 1654 * @param rand The RNG functor or function. 1655 * @return Nothing. 1656 * 1657 * Reorders the elements in the range @p [first,last) using @p rand to 1658 * provide a random distribution. Calling @p rand(N) for a positive 1659 * integer @p N should return a randomly chosen integer from the 1660 * range [0,N). 1661 */ 1662 template<typename _RandomAccessIter, typename _RandomNumberGenerator> 1663 void 1664 random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 1665 _RandomNumberGenerator& __rand) 1666 { 1667 // concept requirements 1668 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 1669 _RandomAccessIter>) 1670 1671 if (__first == __last) return; 1672 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 1673 iter_swap(__i, __first + __rand((__i - __first) + 1)); 1674 } 1675 1676 1677 /** 1678 * @if maint 1679 * This is a helper function... 1680 * @endif 1681 */ 1682 template<typename _ForwardIter, typename _Predicate> 1683 _ForwardIter 1684 __partition(_ForwardIter __first, _ForwardIter __last, 1685 _Predicate __pred, 1686 forward_iterator_tag) 1687 { 1688 if (__first == __last) return __first; 1689 1690 while (__pred(*__first)) 1691 if (++__first == __last) return __first; 1692 1693 _ForwardIter __next = __first; 1694 1695 while (++__next != __last) 1696 if (__pred(*__next)) { 1697 swap(*__first, *__next); 1698 ++__first; 1699 } 1700 1701 return __first; 1702 } 1703 1704 /** 1705 * @if maint 1706 * This is a helper function... 1707 * @endif 1708 */ 1709 template<typename _BidirectionalIter, typename _Predicate> 1710 _BidirectionalIter 1711 __partition(_BidirectionalIter __first, _BidirectionalIter __last, 1712 _Predicate __pred, 1713 bidirectional_iterator_tag) 1714 { 1715 while (true) { 1716 while (true) 1717 if (__first == __last) 1718 return __first; 1719 else if (__pred(*__first)) 1720 ++__first; 1721 else 1722 break; 1723 --__last; 1724 while (true) 1725 if (__first == __last) 1726 return __first; 1727 else if (!__pred(*__last)) 1728 --__last; 1729 else 1730 break; 1731 iter_swap(__first, __last); 1732 ++__first; 1733 } 1734 } 1735 1736 /** 1737 * @brief Move elements for which a predicate is true to the beginning 1738 * of a sequence. 1739 * @param first A forward iterator. 1740 * @param last A forward iterator. 1741 * @param pred A predicate functor. 1742 * @return An iterator @p middle such that @p pred(i) is true for each 1743 * iterator @p i in the range @p [first,middle) and false for each @p i 1744 * in the range @p [middle,last). 1745 * 1746 * @p pred must not modify its operand. @p partition() does not preserve 1747 * the relative ordering of elements in each group, use 1748 * @p stable_partition() if this is needed. 1749 */ 1750 template<typename _ForwardIter, typename _Predicate> 1751 inline _ForwardIter 1752 partition(_ForwardIter __first, _ForwardIter __last, 1753 _Predicate __pred) 1754 { 1755 // concept requirements 1756 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 1757 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 1758 typename iterator_traits<_ForwardIter>::value_type>) 1759 1760 return __partition(__first, __last, __pred, __iterator_category(__first)); 1761 } 1762 1763 1764 /** 1765 * @if maint 1766 * This is a helper function... 1767 * @endif 1768 */ 1769 template<typename _ForwardIter, typename _Predicate, typename _Distance> 1770 _ForwardIter 1771 __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last, 1772 _Predicate __pred, _Distance __len) 1773 { 1774 if (__len == 1) 1775 return __pred(*__first) ? __last : __first; 1776 _ForwardIter __middle = __first; 1777 advance(__middle, __len / 2); 1778 _ForwardIter __begin = __inplace_stable_partition(__first, __middle, 1779 __pred, 1780 __len / 2); 1781 _ForwardIter __end = __inplace_stable_partition(__middle, __last, 1782 __pred, 1783 __len - __len / 2); 1784 rotate(__begin, __middle, __end); 1785 advance(__begin, distance(__middle, __end)); 1786 return __begin; 1787 } 1788 1789 /** 1790 * @if maint 1791 * This is a helper function... 1792 * @endif 1793 */ 1794 template<typename _ForwardIter, typename _Pointer, typename _Predicate, 1795 typename _Distance> 1796 _ForwardIter 1797 __stable_partition_adaptive(_ForwardIter __first, _ForwardIter __last, 1798 _Predicate __pred, _Distance __len, 1799 _Pointer __buffer, 1800 _Distance __buffer_size) 1801 { 1802 if (__len <= __buffer_size) { 1803 _ForwardIter __result1 = __first; 1804 _Pointer __result2 = __buffer; 1805 for ( ; __first != __last ; ++__first) 1806 if (__pred(*__first)) { 1807 *__result1 = *__first; 1808 ++__result1; 1809 } 1810 else { 1811 *__result2 = *__first; 1812 ++__result2; 1813 } 1814 copy(__buffer, __result2, __result1); 1815 return __result1; 1816 } 1817 else { 1818 _ForwardIter __middle = __first; 1819 advance(__middle, __len / 2); 1820 _ForwardIter __begin = __stable_partition_adaptive(__first, __middle, 1821 __pred, 1822 __len / 2, 1823 __buffer, __buffer_size); 1824 _ForwardIter __end = __stable_partition_adaptive( __middle, __last, 1825 __pred, 1826 __len - __len / 2, 1827 __buffer, __buffer_size); 1828 rotate(__begin, __middle, __end); 1829 advance(__begin, distance(__middle, __end)); 1830 return __begin; 1831 } 1832 } 1833 1834 /** 1835 * @brief Move elements for which a predicate is true to the beginning 1836 * of a sequence, preserving relative ordering. 1837 * @param first A forward iterator. 1838 * @param last A forward iterator. 1839 * @param pred A predicate functor. 1840 * @return An iterator @p middle such that @p pred(i) is true for each 1841 * iterator @p i in the range @p [first,middle) and false for each @p i 1842 * in the range @p [middle,last). 1843 * 1844 * Performs the same function as @p partition() with the additional 1845 * guarantee that the relative ordering of elements in each group is 1846 * preserved, so any two elements @p x and @p y in the range 1847 * @p [first,last) such that @p pred(x)==pred(y) will have the same 1848 * relative ordering after calling @p stable_partition(). 1849 */ 1850 template<typename _ForwardIter, typename _Predicate> 1851 _ForwardIter 1852 stable_partition(_ForwardIter __first, _ForwardIter __last, 1853 _Predicate __pred) 1854 { 1855 // concept requirements 1856 __glibcpp_function_requires(_Mutable_ForwardIteratorConcept<_ForwardIter>) 1857 __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, 1858 typename iterator_traits<_ForwardIter>::value_type>) 1859 1860 if (__first == __last) 1861 return __first; 1862 else 1863 { 1864 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 1865 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 1866 1867 _Temporary_buffer<_ForwardIter, _ValueType> __buf(__first, __last); 1868 if (__buf.size() > 0) 1869 return __stable_partition_adaptive(__first, __last, __pred, 1870 _DistanceType(__buf.requested_size()), 1871 __buf.begin(), __buf.size()); 1872 else 1873 return __inplace_stable_partition(__first, __last, __pred, 1874 _DistanceType(__buf.requested_size())); 1875 } 1876 } 1877 1878 /** 1879 * @if maint 1880 * This is a helper function... 1881 * @endif 1882 */ 1883 template<typename _RandomAccessIter, typename _Tp> 1884 _RandomAccessIter 1885 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 1886 _Tp __pivot) 1887 { 1888 while (true) { 1889 while (*__first < __pivot) 1890 ++__first; 1891 --__last; 1892 while (__pivot < *__last) 1893 --__last; 1894 if (!(__first < __last)) 1895 return __first; 1896 iter_swap(__first, __last); 1897 ++__first; 1898 } 1899 } 1900 1901 /** 1902 * @if maint 1903 * This is a helper function... 1904 * @endif 1905 */ 1906 template<typename _RandomAccessIter, typename _Tp, typename _Compare> 1907 _RandomAccessIter 1908 __unguarded_partition(_RandomAccessIter __first, _RandomAccessIter __last, 1909 _Tp __pivot, _Compare __comp) 1910 { 1911 while (true) { 1912 while (__comp(*__first, __pivot)) 1913 ++__first; 1914 --__last; 1915 while (__comp(__pivot, *__last)) 1916 --__last; 1917 if (!(__first < __last)) 1918 return __first; 1919 iter_swap(__first, __last); 1920 ++__first; 1921 } 1922 } 1923 1924 1925 /** 1926 * @if maint 1927 * @doctodo 1928 * This controls some aspect of the sort routines. 1929 * @endif 1930 */ 1931 enum { _M_threshold = 16 }; 1932 1933 /** 1934 * @if maint 1935 * This is a helper function for the sort routine. 1936 * @endif 1937 */ 1938 template<typename _RandomAccessIter, typename _Tp> 1939 void 1940 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) 1941 { 1942 _RandomAccessIter __next = __last; 1943 --__next; 1944 while (__val < *__next) { 1945 *__last = *__next; 1946 __last = __next; 1947 --__next; 1948 } 1949 *__last = __val; 1950 } 1951 1952 /** 1953 * @if maint 1954 * This is a helper function for the sort routine. 1955 * @endif 1956 */ 1957 template<typename _RandomAccessIter, typename _Tp, typename _Compare> 1958 void 1959 __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) 1960 { 1961 _RandomAccessIter __next = __last; 1962 --__next; 1963 while (__comp(__val, *__next)) { 1964 *__last = *__next; 1965 __last = __next; 1966 --__next; 1967 } 1968 *__last = __val; 1969 } 1970 1971 /** 1972 * @if maint 1973 * This is a helper function for the sort routine. 1974 * @endif 1975 */ 1976 template<typename _RandomAccessIter> 1977 void 1978 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 1979 { 1980 if (__first == __last) return; 1981 1982 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 1983 { 1984 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 1985 if (__val < *__first) { 1986 copy_backward(__first, __i, __i + 1); 1987 *__first = __val; 1988 } 1989 else 1990 __unguarded_linear_insert(__i, __val); 1991 } 1992 } 1993 1994 /** 1995 * @if maint 1996 * This is a helper function for the sort routine. 1997 * @endif 1998 */ 1999 template<typename _RandomAccessIter, typename _Compare> 2000 void 2001 __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 2002 _Compare __comp) 2003 { 2004 if (__first == __last) return; 2005 2006 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 2007 { 2008 typename iterator_traits<_RandomAccessIter>::value_type __val = *__i; 2009 if (__comp(__val, *__first)) { 2010 copy_backward(__first, __i, __i + 1); 2011 *__first = __val; 2012 } 2013 else 2014 __unguarded_linear_insert(__i, __val, __comp); 2015 } 2016 } 2017 2018 /** 2019 * @if maint 2020 * This is a helper function for the sort routine. 2021 * @endif 2022 */ 2023 template<typename _RandomAccessIter> 2024 inline void 2025 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 2026 { 2027 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2028 2029 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 2030 __unguarded_linear_insert(__i, _ValueType(*__i)); 2031 } 2032 2033 /** 2034 * @if maint 2035 * This is a helper function for the sort routine. 2036 * @endif 2037 */ 2038 template<typename _RandomAccessIter, typename _Compare> 2039 inline void 2040 __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 2041 _Compare __comp) 2042 { 2043 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2044 2045 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 2046 __unguarded_linear_insert(__i, _ValueType(*__i), __comp); 2047 } 2048 2049 /** 2050 * @if maint 2051 * This is a helper function for the sort routine. 2052 * @endif 2053 */ 2054 template<typename _RandomAccessIter> 2055 void 2056 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) 2057 { 2058 if (__last - __first > _M_threshold) { 2059 __insertion_sort(__first, __first + _M_threshold); 2060 __unguarded_insertion_sort(__first + _M_threshold, __last); 2061 } 2062 else 2063 __insertion_sort(__first, __last); 2064 } 2065 2066 /** 2067 * @if maint 2068 * This is a helper function for the sort routine. 2069 * @endif 2070 */ 2071 template<typename _RandomAccessIter, typename _Compare> 2072 void 2073 __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 2074 _Compare __comp) 2075 { 2076 if (__last - __first > _M_threshold) { 2077 __insertion_sort(__first, __first + _M_threshold, __comp); 2078 __unguarded_insertion_sort(__first + _M_threshold, __last, __comp); 2079 } 2080 else 2081 __insertion_sort(__first, __last, __comp); 2082 } 2083 2084 /** 2085 * @if maint 2086 * This is a helper function for the sort routine. 2087 * @endif 2088 */ 2089 template<typename _Size> 2090 inline _Size 2091 __lg(_Size __n) 2092 { 2093 _Size __k; 2094 for (__k = 0; __n != 1; __n >>= 1) ++__k; 2095 return __k; 2096 } 2097 2098 /** 2099 * @if maint 2100 * This is a helper function for the sort routine. 2101 * @endif 2102 */ 2103 template<typename _RandomAccessIter, typename _Size> 2104 void 2105 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 2106 _Size __depth_limit) 2107 { 2108 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2109 2110 while (__last - __first > _M_threshold) { 2111 if (__depth_limit == 0) { 2112 partial_sort(__first, __last, __last); 2113 return; 2114 } 2115 --__depth_limit; 2116 _RandomAccessIter __cut = 2117 __unguarded_partition(__first, __last, 2118 _ValueType(__median(*__first, 2119 *(__first + (__last - __first)/2), 2120 *(__last - 1)))); 2121 __introsort_loop(__cut, __last, __depth_limit); 2122 __last = __cut; 2123 } 2124 } 2125 2126 /** 2127 * @if maint 2128 * This is a helper function for the sort routine. 2129 * @endif 2130 */ 2131 template<typename _RandomAccessIter, typename _Size, typename _Compare> 2132 void 2133 __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, 2134 _Size __depth_limit, _Compare __comp) 2135 { 2136 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2137 2138 while (__last - __first > _M_threshold) { 2139 if (__depth_limit == 0) { 2140 partial_sort(__first, __last, __last, __comp); 2141 return; 2142 } 2143 --__depth_limit; 2144 _RandomAccessIter __cut = 2145 __unguarded_partition(__first, __last, 2146 _ValueType(__median(*__first, 2147 *(__first + (__last - __first)/2), 2148 *(__last - 1), __comp)), 2149 __comp); 2150 __introsort_loop(__cut, __last, __depth_limit, __comp); 2151 __last = __cut; 2152 } 2153 } 2154 2155 /** 2156 * @brief Sort the elements of a sequence. 2157 * @param first An iterator. 2158 * @param last Another iterator. 2159 * @return Nothing. 2160 * 2161 * Sorts the elements in the range @p [first,last) in ascending order, 2162 * such that @p *(i+1)<*i is false for each iterator @p i in the range 2163 * @p [first,last-1). 2164 * 2165 * The relative ordering of equivalent elements is not preserved, use 2166 * @p stable_sort() if this is needed. 2167 */ 2168 template<typename _RandomAccessIter> 2169 inline void 2170 sort(_RandomAccessIter __first, _RandomAccessIter __last) 2171 { 2172 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2173 2174 // concept requirements 2175 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 2176 _RandomAccessIter>) 2177 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 2178 2179 if (__first != __last) { 2180 __introsort_loop(__first, __last, __lg(__last - __first) * 2); 2181 __final_insertion_sort(__first, __last); 2182 } 2183 } 2184 2185 /** 2186 * @brief Sort the elements of a sequence using a predicate for comparison. 2187 * @param first An iterator. 2188 * @param last Another iterator. 2189 * @param comp A comparison functor. 2190 * @return Nothing. 2191 * 2192 * Sorts the elements in the range @p [first,last) in ascending order, 2193 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the 2194 * range @p [first,last-1). 2195 * 2196 * The relative ordering of equivalent elements is not preserved, use 2197 * @p stable_sort() if this is needed. 2198 */ 2199 template<typename _RandomAccessIter, typename _Compare> 2200 inline void 2201 sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 2202 { 2203 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2204 2205 // concept requirements 2206 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 2207 _RandomAccessIter>) 2208 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _ValueType>) 2209 2210 if (__first != __last) { 2211 __introsort_loop(__first, __last, __lg(__last - __first) * 2, __comp); 2212 __final_insertion_sort(__first, __last, __comp); 2213 } 2214 } 2215 2216 2217 /** 2218 * @if maint 2219 * This is a helper function for the stable sorting routines. 2220 * @endif 2221 */ 2222 template<typename _RandomAccessIter> 2223 void 2224 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 2225 { 2226 if (__last - __first < 15) { 2227 __insertion_sort(__first, __last); 2228 return; 2229 } 2230 _RandomAccessIter __middle = __first + (__last - __first) / 2; 2231 __inplace_stable_sort(__first, __middle); 2232 __inplace_stable_sort(__middle, __last); 2233 __merge_without_buffer(__first, __middle, __last, 2234 __middle - __first, 2235 __last - __middle); 2236 } 2237 2238 /** 2239 * @if maint 2240 * This is a helper function for the stable sorting routines. 2241 * @endif 2242 */ 2243 template<typename _RandomAccessIter, typename _Compare> 2244 void 2245 __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, 2246 _Compare __comp) 2247 { 2248 if (__last - __first < 15) { 2249 __insertion_sort(__first, __last, __comp); 2250 return; 2251 } 2252 _RandomAccessIter __middle = __first + (__last - __first) / 2; 2253 __inplace_stable_sort(__first, __middle, __comp); 2254 __inplace_stable_sort(__middle, __last, __comp); 2255 __merge_without_buffer(__first, __middle, __last, 2256 __middle - __first, 2257 __last - __middle, 2258 __comp); 2259 } 2260 2261 template<typename _RandomAccessIter1, typename _RandomAccessIter2, 2262 typename _Distance> 2263 void 2264 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 2265 _RandomAccessIter2 __result, _Distance __step_size) 2266 { 2267 _Distance __two_step = 2 * __step_size; 2268 2269 while (__last - __first >= __two_step) { 2270 __result = merge(__first, __first + __step_size, 2271 __first + __step_size, __first + __two_step, 2272 __result); 2273 __first += __two_step; 2274 } 2275 2276 __step_size = min(_Distance(__last - __first), __step_size); 2277 merge(__first, __first + __step_size, __first + __step_size, __last, 2278 __result); 2279 } 2280 2281 template<typename _RandomAccessIter1, typename _RandomAccessIter2, 2282 typename _Distance, typename _Compare> 2283 void 2284 __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, 2285 _RandomAccessIter2 __result, _Distance __step_size, 2286 _Compare __comp) 2287 { 2288 _Distance __two_step = 2 * __step_size; 2289 2290 while (__last - __first >= __two_step) { 2291 __result = merge(__first, __first + __step_size, 2292 __first + __step_size, __first + __two_step, 2293 __result, 2294 __comp); 2295 __first += __two_step; 2296 } 2297 __step_size = min(_Distance(__last - __first), __step_size); 2298 2299 merge(__first, __first + __step_size, 2300 __first + __step_size, __last, 2301 __result, 2302 __comp); 2303 } 2304 2305 enum { _M_chunk_size = 7 }; 2306 2307 template<typename _RandomAccessIter, typename _Distance> 2308 void 2309 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 2310 _Distance __chunk_size) 2311 { 2312 while (__last - __first >= __chunk_size) { 2313 __insertion_sort(__first, __first + __chunk_size); 2314 __first += __chunk_size; 2315 } 2316 __insertion_sort(__first, __last); 2317 } 2318 2319 template<typename _RandomAccessIter, typename _Distance, typename _Compare> 2320 void 2321 __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, 2322 _Distance __chunk_size, _Compare __comp) 2323 { 2324 while (__last - __first >= __chunk_size) { 2325 __insertion_sort(__first, __first + __chunk_size, __comp); 2326 __first += __chunk_size; 2327 } 2328 __insertion_sort(__first, __last, __comp); 2329 } 2330 2331 template<typename _RandomAccessIter, typename _Pointer> 2332 void 2333 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 2334 _Pointer __buffer) 2335 { 2336 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 2337 2338 _Distance __len = __last - __first; 2339 _Pointer __buffer_last = __buffer + __len; 2340 2341 _Distance __step_size = _M_chunk_size; 2342 __chunk_insertion_sort(__first, __last, __step_size); 2343 2344 while (__step_size < __len) { 2345 __merge_sort_loop(__first, __last, __buffer, __step_size); 2346 __step_size *= 2; 2347 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); 2348 __step_size *= 2; 2349 } 2350 } 2351 2352 template<typename _RandomAccessIter, typename _Pointer, typename _Compare> 2353 void 2354 __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, 2355 _Pointer __buffer, _Compare __comp) 2356 { 2357 typedef typename iterator_traits<_RandomAccessIter>::difference_type _Distance; 2358 2359 _Distance __len = __last - __first; 2360 _Pointer __buffer_last = __buffer + __len; 2361 2362 _Distance __step_size = _M_chunk_size; 2363 __chunk_insertion_sort(__first, __last, __step_size, __comp); 2364 2365 while (__step_size < __len) { 2366 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); 2367 __step_size *= 2; 2368 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); 2369 __step_size *= 2; 2370 } 2371 } 2372 2373 template<typename _RandomAccessIter, typename _Pointer, typename _Distance> 2374 void 2375 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 2376 _Pointer __buffer, _Distance __buffer_size) 2377 { 2378 _Distance __len = (__last - __first + 1) / 2; 2379 _RandomAccessIter __middle = __first + __len; 2380 if (__len > __buffer_size) { 2381 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size); 2382 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size); 2383 } 2384 else { 2385 __merge_sort_with_buffer(__first, __middle, __buffer); 2386 __merge_sort_with_buffer(__middle, __last, __buffer); 2387 } 2388 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 2389 _Distance(__last - __middle), __buffer, __buffer_size); 2390 } 2391 2392 template<typename _RandomAccessIter, typename _Pointer, typename _Distance, 2393 typename _Compare> 2394 void 2395 __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, 2396 _Pointer __buffer, _Distance __buffer_size, 2397 _Compare __comp) 2398 { 2399 _Distance __len = (__last - __first + 1) / 2; 2400 _RandomAccessIter __middle = __first + __len; 2401 if (__len > __buffer_size) { 2402 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 2403 __comp); 2404 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 2405 __comp); 2406 } 2407 else { 2408 __merge_sort_with_buffer(__first, __middle, __buffer, __comp); 2409 __merge_sort_with_buffer(__middle, __last, __buffer, __comp); 2410 } 2411 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 2412 _Distance(__last - __middle), __buffer, __buffer_size, 2413 __comp); 2414 } 2415 2416 /** 2417 * @brief Sort the elements of a sequence, preserving the relative order 2418 * of equivalent elements. 2419 * @param first An iterator. 2420 * @param last Another iterator. 2421 * @return Nothing. 2422 * 2423 * Sorts the elements in the range @p [first,last) in ascending order, 2424 * such that @p *(i+1)<*i is false for each iterator @p i in the range 2425 * @p [first,last-1). 2426 * 2427 * The relative ordering of equivalent elements is preserved, so any two 2428 * elements @p x and @p y in the range @p [first,last) such that 2429 * @p x<y is false and @p y<x is false will have the same relative 2430 * ordering after calling @p stable_sort(). 2431 */ 2432 template<typename _RandomAccessIter> 2433 inline void 2434 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last) 2435 { 2436 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2437 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 2438 2439 // concept requirements 2440 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 2441 _RandomAccessIter>) 2442 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 2443 2444 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 2445 if (buf.begin() == 0) 2446 __inplace_stable_sort(__first, __last); 2447 else 2448 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size())); 2449 } 2450 2451 /** 2452 * @brief Sort the elements of a sequence using a predicate for comparison, 2453 * preserving the relative order of equivalent elements. 2454 * @param first An iterator. 2455 * @param last Another iterator. 2456 * @param comp A comparison functor. 2457 * @return Nothing. 2458 * 2459 * Sorts the elements in the range @p [first,last) in ascending order, 2460 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the 2461 * range @p [first,last-1). 2462 * 2463 * The relative ordering of equivalent elements is preserved, so any two 2464 * elements @p x and @p y in the range @p [first,last) such that 2465 * @p comp(x,y) is false and @p comp(y,x) is false will have the same 2466 * relative ordering after calling @p stable_sort(). 2467 */ 2468 template<typename _RandomAccessIter, typename _Compare> 2469 inline void 2470 stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) 2471 { 2472 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2473 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 2474 2475 // concept requirements 2476 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 2477 _RandomAccessIter>) 2478 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 2479 _ValueType, _ValueType>) 2480 2481 _Temporary_buffer<_RandomAccessIter, _ValueType> buf(__first, __last); 2482 if (buf.begin() == 0) 2483 __inplace_stable_sort(__first, __last, __comp); 2484 else 2485 __stable_sort_adaptive(__first, __last, buf.begin(), _DistanceType(buf.size()), 2486 __comp); 2487 } 2488 2489 /** 2490 * @brief Sort the smallest elements of a sequence. 2491 * @param first An iterator. 2492 * @param middle Another iterator. 2493 * @param last Another iterator. 2494 * @return Nothing. 2495 * 2496 * Sorts the smallest @p (middle-first) elements in the range 2497 * @p [first,last) and moves them to the range @p [first,middle). The 2498 * order of the remaining elements in the range @p [middle,last) is 2499 * undefined. 2500 * After the sort if @p i and @j are iterators in the range 2501 * @p [first,middle) such that @i precedes @j and @k is an iterator in 2502 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. 2503 */ 2504 template<typename _RandomAccessIter> 2505 void 2506 partial_sort(_RandomAccessIter __first, 2507 _RandomAccessIter __middle, 2508 _RandomAccessIter __last) 2509 { 2510 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2511 2512 // concept requirements 2513 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 2514 _RandomAccessIter>) 2515 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 2516 2517 make_heap(__first, __middle); 2518 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 2519 if (*__i < *__first) 2520 __pop_heap(__first, __middle, __i, _ValueType(*__i)); 2521 sort_heap(__first, __middle); 2522 } 2523 2524 /** 2525 * @brief Sort the smallest elements of a sequence using a predicate 2526 * for comparison. 2527 * @param first An iterator. 2528 * @param middle Another iterator. 2529 * @param last Another iterator. 2530 * @param comp A comparison functor. 2531 * @return Nothing. 2532 * 2533 * Sorts the smallest @p (middle-first) elements in the range 2534 * @p [first,last) and moves them to the range @p [first,middle). The 2535 * order of the remaining elements in the range @p [middle,last) is 2536 * undefined. 2537 * After the sort if @p i and @j are iterators in the range 2538 * @p [first,middle) such that @i precedes @j and @k is an iterator in 2539 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i) 2540 * are both false. 2541 */ 2542 template<typename _RandomAccessIter, typename _Compare> 2543 void 2544 partial_sort(_RandomAccessIter __first, 2545 _RandomAccessIter __middle, 2546 _RandomAccessIter __last, 2547 _Compare __comp) 2548 { 2549 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2550 2551 // concept requirements 2552 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 2553 _RandomAccessIter>) 2554 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 2555 _ValueType, _ValueType>) 2556 2557 make_heap(__first, __middle, __comp); 2558 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) 2559 if (__comp(*__i, *__first)) 2560 __pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); 2561 sort_heap(__first, __middle, __comp); 2562 } 2563 2564 /** 2565 * @brief Copy the smallest elements of a sequence. 2566 * @param first An iterator. 2567 * @param last Another iterator. 2568 * @param result_first A random-access iterator. 2569 * @param result_last Another random-access iterator. 2570 * @return An iterator indicating the end of the resulting sequence. 2571 * 2572 * Copies and sorts the smallest N values from the range @p [first,last) 2573 * to the range beginning at @p result_first, where the number of 2574 * elements to be copied, @p N, is the smaller of @p (last-first) and 2575 * @p (result_last-result_first). 2576 * After the sort if @p i and @j are iterators in the range 2577 * @p [result_first,result_first+N) such that @i precedes @j then 2578 * @p *j<*i is false. 2579 * The value returned is @p result_first+N. 2580 */ 2581 template<typename _InputIter, typename _RandomAccessIter> 2582 _RandomAccessIter 2583 partial_sort_copy(_InputIter __first, _InputIter __last, 2584 _RandomAccessIter __result_first, 2585 _RandomAccessIter __result_last) 2586 { 2587 typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 2588 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 2589 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 2590 2591 // concept requirements 2592 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 2593 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 2594 __glibcpp_function_requires(_LessThanComparableConcept<_OutputValueType>) 2595 __glibcpp_function_requires(_LessThanComparableConcept<_InputValueType>) 2596 2597 if (__result_first == __result_last) return __result_last; 2598 _RandomAccessIter __result_real_last = __result_first; 2599 while(__first != __last && __result_real_last != __result_last) { 2600 *__result_real_last = *__first; 2601 ++__result_real_last; 2602 ++__first; 2603 } 2604 make_heap(__result_first, __result_real_last); 2605 while (__first != __last) { 2606 if (*__first < *__result_first) 2607 __adjust_heap(__result_first, _DistanceType(0), 2608 _DistanceType(__result_real_last - __result_first), 2609 _InputValueType(*__first)); 2610 ++__first; 2611 } 2612 sort_heap(__result_first, __result_real_last); 2613 return __result_real_last; 2614 } 2615 2616 /** 2617 * @brief Copy the smallest elements of a sequence using a predicate for 2618 * comparison. 2619 * @param first An input iterator. 2620 * @param last Another input iterator. 2621 * @param result_first A random-access iterator. 2622 * @param result_last Another random-access iterator. 2623 * @param comp A comparison functor. 2624 * @return An iterator indicating the end of the resulting sequence. 2625 * 2626 * Copies and sorts the smallest N values from the range @p [first,last) 2627 * to the range beginning at @p result_first, where the number of 2628 * elements to be copied, @p N, is the smaller of @p (last-first) and 2629 * @p (result_last-result_first). 2630 * After the sort if @p i and @j are iterators in the range 2631 * @p [result_first,result_first+N) such that @i precedes @j then 2632 * @p comp(*j,*i) is false. 2633 * The value returned is @p result_first+N. 2634 */ 2635 template<typename _InputIter, typename _RandomAccessIter, typename _Compare> 2636 _RandomAccessIter 2637 partial_sort_copy(_InputIter __first, _InputIter __last, 2638 _RandomAccessIter __result_first, 2639 _RandomAccessIter __result_last, 2640 _Compare __comp) 2641 { 2642 typedef typename iterator_traits<_InputIter>::value_type _InputValueType; 2643 typedef typename iterator_traits<_RandomAccessIter>::value_type _OutputValueType; 2644 typedef typename iterator_traits<_RandomAccessIter>::difference_type _DistanceType; 2645 2646 // concept requirements 2647 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 2648 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 2649 __glibcpp_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) 2650 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 2651 _OutputValueType, _OutputValueType>) 2652 2653 if (__result_first == __result_last) return __result_last; 2654 _RandomAccessIter __result_real_last = __result_first; 2655 while(__first != __last && __result_real_last != __result_last) { 2656 *__result_real_last = *__first; 2657 ++__result_real_last; 2658 ++__first; 2659 } 2660 make_heap(__result_first, __result_real_last, __comp); 2661 while (__first != __last) { 2662 if (__comp(*__first, *__result_first)) 2663 __adjust_heap(__result_first, _DistanceType(0), 2664 _DistanceType(__result_real_last - __result_first), 2665 _InputValueType(*__first), 2666 __comp); 2667 ++__first; 2668 } 2669 sort_heap(__result_first, __result_real_last, __comp); 2670 return __result_real_last; 2671 } 2672 2673 /** 2674 * @brief Sort a sequence just enough to find a particular position. 2675 * @param first An iterator. 2676 * @param nth Another iterator. 2677 * @param last Another iterator. 2678 * @return Nothing. 2679 * 2680 * Rearranges the elements in the range @p [first,last) so that @p *nth 2681 * is the same element that would have been in that position had the 2682 * whole sequence been sorted. 2683 * whole sequence been sorted. The elements either side of @p *nth are 2684 * not completely sorted, but for any iterator @i in the range 2685 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 2686 * holds that @p *j<*i is false. 2687 */ 2688 template<typename _RandomAccessIter> 2689 void 2690 nth_element(_RandomAccessIter __first, 2691 _RandomAccessIter __nth, 2692 _RandomAccessIter __last) 2693 { 2694 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2695 2696 // concept requirements 2697 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 2698 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 2699 2700 while (__last - __first > 3) { 2701 _RandomAccessIter __cut = 2702 __unguarded_partition(__first, __last, 2703 _ValueType(__median(*__first, 2704 *(__first + (__last - __first)/2), 2705 *(__last - 1)))); 2706 if (__cut <= __nth) 2707 __first = __cut; 2708 else 2709 __last = __cut; 2710 } 2711 __insertion_sort(__first, __last); 2712 } 2713 2714 /** 2715 * @brief Sort a sequence just enough to find a particular position 2716 * using a predicate for comparison. 2717 * @param first An iterator. 2718 * @param nth Another iterator. 2719 * @param last Another iterator. 2720 * @param comp A comparison functor. 2721 * @return Nothing. 2722 * 2723 * Rearranges the elements in the range @p [first,last) so that @p *nth 2724 * is the same element that would have been in that position had the 2725 * whole sequence been sorted. The elements either side of @p *nth are 2726 * not completely sorted, but for any iterator @i in the range 2727 * @p [first,nth) and any iterator @j in the range @p [nth,last) it 2728 * holds that @p comp(*j,*i) is false. 2729 */ 2730 template<typename _RandomAccessIter, typename _Compare> 2731 void 2732 nth_element(_RandomAccessIter __first, 2733 _RandomAccessIter __nth, 2734 _RandomAccessIter __last, 2735 _Compare __comp) 2736 { 2737 typedef typename iterator_traits<_RandomAccessIter>::value_type _ValueType; 2738 2739 // concept requirements 2740 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<_RandomAccessIter>) 2741 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 2742 _ValueType, _ValueType>) 2743 2744 while (__last - __first > 3) { 2745 _RandomAccessIter __cut = 2746 __unguarded_partition(__first, __last, 2747 _ValueType(__median(*__first, 2748 *(__first + (__last - __first)/2), 2749 *(__last - 1), 2750 __comp)), 2751 __comp); 2752 if (__cut <= __nth) 2753 __first = __cut; 2754 else 2755 __last = __cut; 2756 } 2757 __insertion_sort(__first, __last, __comp); 2758 } 2759 2760 2761 /** 2762 * @brief Finds the first position in which @a val could be inserted 2763 * without changing the ordering. 2764 * @param first An iterator. 2765 * @param last Another iterator. 2766 * @param val The search term. 2767 * @return An iterator pointing to the first element "not less than" @a val. 2768 * @ingroup binarysearch 2769 */ 2770 template<typename _ForwardIter, typename _Tp> 2771 _ForwardIter 2772 lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 2773 { 2774 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 2775 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 2776 2777 // concept requirements 2778 // Note that these are slightly stricter than those of the 4-argument 2779 // version, defined next. The difference is in the strictness of the 2780 // comparison operations... so for looser checking, define your own 2781 // comparison function, as was intended. 2782 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 2783 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 2784 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 2785 2786 _DistanceType __len = distance(__first, __last); 2787 _DistanceType __half; 2788 _ForwardIter __middle; 2789 2790 while (__len > 0) { 2791 __half = __len >> 1; 2792 __middle = __first; 2793 advance(__middle, __half); 2794 if (*__middle < __val) { 2795 __first = __middle; 2796 ++__first; 2797 __len = __len - __half - 1; 2798 } 2799 else 2800 __len = __half; 2801 } 2802 return __first; 2803 } 2804 2805 /** 2806 * @brief Finds the first position in which @a val could be inserted 2807 * without changing the ordering. 2808 * @param first An iterator. 2809 * @param last Another iterator. 2810 * @param val The search term. 2811 * @param comp A functor to use for comparisons. 2812 * @return An iterator pointing to the first element "not less than" @a val. 2813 * @ingroup binarysearch 2814 * 2815 * The comparison function should have the same effects on ordering as 2816 * the function used for the initial sort. 2817 */ 2818 template<typename _ForwardIter, typename _Tp, typename _Compare> 2819 _ForwardIter 2820 lower_bound(_ForwardIter __first, _ForwardIter __last, 2821 const _Tp& __val, _Compare __comp) 2822 { 2823 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 2824 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 2825 2826 // concept requirements 2827 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 2828 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 2829 2830 _DistanceType __len = distance(__first, __last); 2831 _DistanceType __half; 2832 _ForwardIter __middle; 2833 2834 while (__len > 0) { 2835 __half = __len >> 1; 2836 __middle = __first; 2837 advance(__middle, __half); 2838 if (__comp(*__middle, __val)) { 2839 __first = __middle; 2840 ++__first; 2841 __len = __len - __half - 1; 2842 } 2843 else 2844 __len = __half; 2845 } 2846 return __first; 2847 } 2848 2849 /** 2850 * @brief Finds the last position in which @a val could be inserted 2851 * without changing the ordering. 2852 * @param first An iterator. 2853 * @param last Another iterator. 2854 * @param val The search term. 2855 * @return An iterator pointing to the first element greater than @a val. 2856 * @ingroup binarysearch 2857 */ 2858 template<typename _ForwardIter, typename _Tp> 2859 _ForwardIter 2860 upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 2861 { 2862 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 2863 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 2864 2865 // concept requirements 2866 // See comments on lower_bound. 2867 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 2868 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 2869 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 2870 2871 _DistanceType __len = distance(__first, __last); 2872 _DistanceType __half; 2873 _ForwardIter __middle; 2874 2875 while (__len > 0) { 2876 __half = __len >> 1; 2877 __middle = __first; 2878 advance(__middle, __half); 2879 if (__val < *__middle) 2880 __len = __half; 2881 else { 2882 __first = __middle; 2883 ++__first; 2884 __len = __len - __half - 1; 2885 } 2886 } 2887 return __first; 2888 } 2889 2890 /** 2891 * @brief Finds the last position in which @a val could be inserted 2892 * without changing the ordering. 2893 * @param first An iterator. 2894 * @param last Another iterator. 2895 * @param val The search term. 2896 * @param comp A functor to use for comparisons. 2897 * @return An iterator pointing to the first element greater than @a val. 2898 * @ingroup binarysearch 2899 * 2900 * The comparison function should have the same effects on ordering as 2901 * the function used for the initial sort. 2902 */ 2903 template<typename _ForwardIter, typename _Tp, typename _Compare> 2904 _ForwardIter 2905 upper_bound(_ForwardIter __first, _ForwardIter __last, 2906 const _Tp& __val, _Compare __comp) 2907 { 2908 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 2909 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 2910 2911 // concept requirements 2912 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 2913 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 2914 2915 _DistanceType __len = distance(__first, __last); 2916 _DistanceType __half; 2917 _ForwardIter __middle; 2918 2919 while (__len > 0) { 2920 __half = __len >> 1; 2921 __middle = __first; 2922 advance(__middle, __half); 2923 if (__comp(__val, *__middle)) 2924 __len = __half; 2925 else { 2926 __first = __middle; 2927 ++__first; 2928 __len = __len - __half - 1; 2929 } 2930 } 2931 return __first; 2932 } 2933 2934 /** 2935 * @brief Finds the largest subrange in which @a val could be inserted 2936 * at any place in it without changing the ordering. 2937 * @param first An iterator. 2938 * @param last Another iterator. 2939 * @param val The search term. 2940 * @return An pair of iterators defining the subrange. 2941 * @ingroup binarysearch 2942 * 2943 * This is equivalent to 2944 * @code 2945 * std::make_pair(lower_bound(first, last, val), 2946 * upper_bound(first, last, val)) 2947 * @endcode 2948 * but does not actually call those functions. 2949 */ 2950 template<typename _ForwardIter, typename _Tp> 2951 pair<_ForwardIter, _ForwardIter> 2952 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) 2953 { 2954 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 2955 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 2956 2957 // concept requirements 2958 // See comments on lower_bound. 2959 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 2960 __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>) 2961 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 2962 2963 _DistanceType __len = distance(__first, __last); 2964 _DistanceType __half; 2965 _ForwardIter __middle, __left, __right; 2966 2967 while (__len > 0) { 2968 __half = __len >> 1; 2969 __middle = __first; 2970 advance(__middle, __half); 2971 if (*__middle < __val) { 2972 __first = __middle; 2973 ++__first; 2974 __len = __len - __half - 1; 2975 } 2976 else if (__val < *__middle) 2977 __len = __half; 2978 else { 2979 __left = lower_bound(__first, __middle, __val); 2980 advance(__first, __len); 2981 __right = upper_bound(++__middle, __first, __val); 2982 return pair<_ForwardIter, _ForwardIter>(__left, __right); 2983 } 2984 } 2985 return pair<_ForwardIter, _ForwardIter>(__first, __first); 2986 } 2987 2988 /** 2989 * @brief Finds the largest subrange in which @a val could be inserted 2990 * at any place in it without changing the ordering. 2991 * @param first An iterator. 2992 * @param last Another iterator. 2993 * @param val The search term. 2994 * @param comp A functor to use for comparisons. 2995 * @return An pair of iterators defining the subrange. 2996 * @ingroup binarysearch 2997 * 2998 * This is equivalent to 2999 * @code 3000 * std::make_pair(lower_bound(first, last, val, comp), 3001 * upper_bound(first, last, val, comp)) 3002 * @endcode 3003 * but does not actually call those functions. 3004 */ 3005 template<typename _ForwardIter, typename _Tp, typename _Compare> 3006 pair<_ForwardIter, _ForwardIter> 3007 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 3008 _Compare __comp) 3009 { 3010 typedef typename iterator_traits<_ForwardIter>::value_type _ValueType; 3011 typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType; 3012 3013 // concept requirements 3014 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 3015 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>) 3016 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>) 3017 3018 _DistanceType __len = distance(__first, __last); 3019 _DistanceType __half; 3020 _ForwardIter __middle, __left, __right; 3021 3022 while (__len > 0) { 3023 __half = __len >> 1; 3024 __middle = __first; 3025 advance(__middle, __half); 3026 if (__comp(*__middle, __val)) { 3027 __first = __middle; 3028 ++__first; 3029 __len = __len - __half - 1; 3030 } 3031 else if (__comp(__val, *__middle)) 3032 __len = __half; 3033 else { 3034 __left = lower_bound(__first, __middle, __val, __comp); 3035 advance(__first, __len); 3036 __right = upper_bound(++__middle, __first, __val, __comp); 3037 return pair<_ForwardIter, _ForwardIter>(__left, __right); 3038 } 3039 } 3040 return pair<_ForwardIter, _ForwardIter>(__first, __first); 3041 } 3042 3043 /** 3044 * @brief Determines whether an element exists in a range. 3045 * @param first An iterator. 3046 * @param last Another iterator. 3047 * @param val The search term. 3048 * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 3049 * @ingroup binarysearch 3050 * 3051 * Note that this does not actually return an iterator to @a val. For 3052 * that, use std::find or a container's specialized find member functions. 3053 */ 3054 template<typename _ForwardIter, typename _Tp> 3055 bool 3056 binary_search(_ForwardIter __first, _ForwardIter __last, 3057 const _Tp& __val) 3058 { 3059 // concept requirements 3060 // See comments on lower_bound. 3061 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 3062 __glibcpp_function_requires(_SameTypeConcept<_Tp, 3063 typename iterator_traits<_ForwardIter>::value_type>) 3064 __glibcpp_function_requires(_LessThanComparableConcept<_Tp>) 3065 3066 _ForwardIter __i = lower_bound(__first, __last, __val); 3067 return __i != __last && !(__val < *__i); 3068 } 3069 3070 /** 3071 * @brief Determines whether an element exists in a range. 3072 * @param first An iterator. 3073 * @param last Another iterator. 3074 * @param val The search term. 3075 * @param comp A functor to use for comparisons. 3076 * @return True if @a val (or its equivelent) is in [@a first,@a last ]. 3077 * @ingroup binarysearch 3078 * 3079 * Note that this does not actually return an iterator to @a val. For 3080 * that, use std::find or a container's specialized find member functions. 3081 * 3082 * The comparison function should have the same effects on ordering as 3083 * the function used for the initial sort. 3084 */ 3085 template<typename _ForwardIter, typename _Tp, typename _Compare> 3086 bool 3087 binary_search(_ForwardIter __first, _ForwardIter __last, 3088 const _Tp& __val, _Compare __comp) 3089 { 3090 // concept requirements 3091 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 3092 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3093 typename iterator_traits<_ForwardIter>::value_type, _Tp>) 3094 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, 3095 typename iterator_traits<_ForwardIter>::value_type>) 3096 3097 _ForwardIter __i = lower_bound(__first, __last, __val, __comp); 3098 return __i != __last && !__comp(__val, *__i); 3099 } 3100 3101 /** 3102 * @brief Merges two sorted ranges. 3103 * @param first1 An iterator. 3104 * @param first2 Another iterator. 3105 * @param last1 Another iterator. 3106 * @param last2 Another iterator. 3107 * @param result An iterator pointing to the end of the merged range. 3108 * @return An iterator pointing to the first element "not less than" @a val. 3109 * 3110 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 3111 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 3112 * must be sorted, and the output range must not overlap with either of 3113 * the input ranges. The sort is @e stable, that is, for equivalent 3114 * elements in the two ranges, elements from the first range will always 3115 * come before elements from the second. 3116 */ 3117 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 3118 _OutputIter 3119 merge(_InputIter1 __first1, _InputIter1 __last1, 3120 _InputIter2 __first2, _InputIter2 __last2, 3121 _OutputIter __result) 3122 { 3123 // concept requirements 3124 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3125 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3126 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3127 typename iterator_traits<_InputIter1>::value_type>) 3128 __glibcpp_function_requires(_SameTypeConcept< 3129 typename iterator_traits<_InputIter1>::value_type, 3130 typename iterator_traits<_InputIter2>::value_type>) 3131 __glibcpp_function_requires(_LessThanComparableConcept< 3132 typename iterator_traits<_InputIter1>::value_type>) 3133 3134 while (__first1 != __last1 && __first2 != __last2) { 3135 if (*__first2 < *__first1) { 3136 *__result = *__first2; 3137 ++__first2; 3138 } 3139 else { 3140 *__result = *__first1; 3141 ++__first1; 3142 } 3143 ++__result; 3144 } 3145 return copy(__first2, __last2, copy(__first1, __last1, __result)); 3146 } 3147 3148 /** 3149 * @brief Merges two sorted ranges. 3150 * @param first1 An iterator. 3151 * @param first2 Another iterator. 3152 * @param last1 Another iterator. 3153 * @param last2 Another iterator. 3154 * @param result An iterator pointing to the end of the merged range. 3155 * @param comp A functor to use for comparisons. 3156 * @return An iterator pointing to the first element "not less than" @a val. 3157 * 3158 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range 3159 * [result, result + (last1-first1) + (last2-first2)). Both input ranges 3160 * must be sorted, and the output range must not overlap with either of 3161 * the input ranges. The sort is @e stable, that is, for equivalent 3162 * elements in the two ranges, elements from the first range will always 3163 * come before elements from the second. 3164 * 3165 * The comparison function should have the same effects on ordering as 3166 * the function used for the initial sort. 3167 */ 3168 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 3169 typename _Compare> 3170 _OutputIter 3171 merge(_InputIter1 __first1, _InputIter1 __last1, 3172 _InputIter2 __first2, _InputIter2 __last2, 3173 _OutputIter __result, _Compare __comp) 3174 { 3175 // concept requirements 3176 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3177 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3178 __glibcpp_function_requires(_SameTypeConcept< 3179 typename iterator_traits<_InputIter1>::value_type, 3180 typename iterator_traits<_InputIter2>::value_type>) 3181 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3182 typename iterator_traits<_InputIter1>::value_type>) 3183 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3184 typename iterator_traits<_InputIter1>::value_type, 3185 typename iterator_traits<_InputIter2>::value_type>) 3186 3187 while (__first1 != __last1 && __first2 != __last2) { 3188 if (__comp(*__first2, *__first1)) { 3189 *__result = *__first2; 3190 ++__first2; 3191 } 3192 else { 3193 *__result = *__first1; 3194 ++__first1; 3195 } 3196 ++__result; 3197 } 3198 return copy(__first2, __last2, copy(__first1, __last1, __result)); 3199 } 3200 3201 /** 3202 * @if maint 3203 * This is a helper function for the merge routines. 3204 * @endif 3205 */ 3206 template<typename _BidirectionalIter, typename _Distance> 3207 void 3208 __merge_without_buffer(_BidirectionalIter __first, 3209 _BidirectionalIter __middle, 3210 _BidirectionalIter __last, 3211 _Distance __len1, _Distance __len2) 3212 { 3213 if (__len1 == 0 || __len2 == 0) 3214 return; 3215 if (__len1 + __len2 == 2) { 3216 if (*__middle < *__first) 3217 iter_swap(__first, __middle); 3218 return; 3219 } 3220 _BidirectionalIter __first_cut = __first; 3221 _BidirectionalIter __second_cut = __middle; 3222 _Distance __len11 = 0; 3223 _Distance __len22 = 0; 3224 if (__len1 > __len2) { 3225 __len11 = __len1 / 2; 3226 advance(__first_cut, __len11); 3227 __second_cut = lower_bound(__middle, __last, *__first_cut); 3228 __len22 = distance(__middle, __second_cut); 3229 } 3230 else { 3231 __len22 = __len2 / 2; 3232 advance(__second_cut, __len22); 3233 __first_cut = upper_bound(__first, __middle, *__second_cut); 3234 __len11 = distance(__first, __first_cut); 3235 } 3236 rotate(__first_cut, __middle, __second_cut); 3237 _BidirectionalIter __new_middle = __first_cut; 3238 advance(__new_middle, distance(__middle, __second_cut)); 3239 __merge_without_buffer(__first, __first_cut, __new_middle, 3240 __len11, __len22); 3241 __merge_without_buffer(__new_middle, __second_cut, __last, 3242 __len1 - __len11, __len2 - __len22); 3243 } 3244 3245 /** 3246 * @if maint 3247 * This is a helper function for the merge routines. 3248 * @endif 3249 */ 3250 template<typename _BidirectionalIter, typename _Distance, typename _Compare> 3251 void 3252 __merge_without_buffer(_BidirectionalIter __first, 3253 _BidirectionalIter __middle, 3254 _BidirectionalIter __last, 3255 _Distance __len1, _Distance __len2, 3256 _Compare __comp) 3257 { 3258 if (__len1 == 0 || __len2 == 0) 3259 return; 3260 if (__len1 + __len2 == 2) { 3261 if (__comp(*__middle, *__first)) 3262 iter_swap(__first, __middle); 3263 return; 3264 } 3265 _BidirectionalIter __first_cut = __first; 3266 _BidirectionalIter __second_cut = __middle; 3267 _Distance __len11 = 0; 3268 _Distance __len22 = 0; 3269 if (__len1 > __len2) { 3270 __len11 = __len1 / 2; 3271 advance(__first_cut, __len11); 3272 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 3273 __len22 = distance(__middle, __second_cut); 3274 } 3275 else { 3276 __len22 = __len2 / 2; 3277 advance(__second_cut, __len22); 3278 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 3279 __len11 = distance(__first, __first_cut); 3280 } 3281 rotate(__first_cut, __middle, __second_cut); 3282 _BidirectionalIter __new_middle = __first_cut; 3283 advance(__new_middle, distance(__middle, __second_cut)); 3284 __merge_without_buffer(__first, __first_cut, __new_middle, 3285 __len11, __len22, __comp); 3286 __merge_without_buffer(__new_middle, __second_cut, __last, 3287 __len1 - __len11, __len2 - __len22, __comp); 3288 } 3289 3290 /** 3291 * @if maint 3292 * This is a helper function for the merge routines. 3293 * @endif 3294 */ 3295 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 3296 typename _Distance> 3297 _BidirectionalIter1 3298 __rotate_adaptive(_BidirectionalIter1 __first, 3299 _BidirectionalIter1 __middle, 3300 _BidirectionalIter1 __last, 3301 _Distance __len1, _Distance __len2, 3302 _BidirectionalIter2 __buffer, 3303 _Distance __buffer_size) 3304 { 3305 _BidirectionalIter2 __buffer_end; 3306 if (__len1 > __len2 && __len2 <= __buffer_size) { 3307 __buffer_end = copy(__middle, __last, __buffer); 3308 copy_backward(__first, __middle, __last); 3309 return copy(__buffer, __buffer_end, __first); 3310 } 3311 else if (__len1 <= __buffer_size) { 3312 __buffer_end = copy(__first, __middle, __buffer); 3313 copy(__middle, __last, __first); 3314 return copy_backward(__buffer, __buffer_end, __last); 3315 } 3316 else { 3317 rotate(__first, __middle, __last); 3318 advance(__first, distance(__middle, __last)); 3319 return __first; 3320 } 3321 } 3322 3323 /** 3324 * @if maint 3325 * This is a helper function for the merge routines. 3326 * @endif 3327 */ 3328 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 3329 typename _BidirectionalIter3> 3330 _BidirectionalIter3 3331 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 3332 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 3333 _BidirectionalIter3 __result) 3334 { 3335 if (__first1 == __last1) 3336 return copy_backward(__first2, __last2, __result); 3337 if (__first2 == __last2) 3338 return copy_backward(__first1, __last1, __result); 3339 --__last1; 3340 --__last2; 3341 while (true) { 3342 if (*__last2 < *__last1) { 3343 *--__result = *__last1; 3344 if (__first1 == __last1) 3345 return copy_backward(__first2, ++__last2, __result); 3346 --__last1; 3347 } 3348 else { 3349 *--__result = *__last2; 3350 if (__first2 == __last2) 3351 return copy_backward(__first1, ++__last1, __result); 3352 --__last2; 3353 } 3354 } 3355 } 3356 3357 /** 3358 * @if maint 3359 * This is a helper function for the merge routines. 3360 * @endif 3361 */ 3362 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 3363 typename _BidirectionalIter3, typename _Compare> 3364 _BidirectionalIter3 3365 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 3366 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 3367 _BidirectionalIter3 __result, 3368 _Compare __comp) 3369 { 3370 if (__first1 == __last1) 3371 return copy_backward(__first2, __last2, __result); 3372 if (__first2 == __last2) 3373 return copy_backward(__first1, __last1, __result); 3374 --__last1; 3375 --__last2; 3376 while (true) { 3377 if (__comp(*__last2, *__last1)) { 3378 *--__result = *__last1; 3379 if (__first1 == __last1) 3380 return copy_backward(__first2, ++__last2, __result); 3381 --__last1; 3382 } 3383 else { 3384 *--__result = *__last2; 3385 if (__first2 == __last2) 3386 return copy_backward(__first1, ++__last1, __result); 3387 --__last2; 3388 } 3389 } 3390 } 3391 3392 /** 3393 * @if maint 3394 * This is a helper function for the merge routines. 3395 * @endif 3396 */ 3397 template<typename _BidirectionalIter, typename _Distance, typename _Pointer> 3398 void 3399 __merge_adaptive(_BidirectionalIter __first, 3400 _BidirectionalIter __middle, 3401 _BidirectionalIter __last, 3402 _Distance __len1, _Distance __len2, 3403 _Pointer __buffer, _Distance __buffer_size) 3404 { 3405 if (__len1 <= __len2 && __len1 <= __buffer_size) { 3406 _Pointer __buffer_end = copy(__first, __middle, __buffer); 3407 merge(__buffer, __buffer_end, __middle, __last, __first); 3408 } 3409 else if (__len2 <= __buffer_size) { 3410 _Pointer __buffer_end = copy(__middle, __last, __buffer); 3411 __merge_backward(__first, __middle, __buffer, __buffer_end, __last); 3412 } 3413 else { 3414 _BidirectionalIter __first_cut = __first; 3415 _BidirectionalIter __second_cut = __middle; 3416 _Distance __len11 = 0; 3417 _Distance __len22 = 0; 3418 if (__len1 > __len2) { 3419 __len11 = __len1 / 2; 3420 advance(__first_cut, __len11); 3421 __second_cut = lower_bound(__middle, __last, *__first_cut); 3422 __len22 = distance(__middle, __second_cut); 3423 } 3424 else { 3425 __len22 = __len2 / 2; 3426 advance(__second_cut, __len22); 3427 __first_cut = upper_bound(__first, __middle, *__second_cut); 3428 __len11 = distance(__first, __first_cut); 3429 } 3430 _BidirectionalIter __new_middle = 3431 __rotate_adaptive(__first_cut, __middle, __second_cut, 3432 __len1 - __len11, __len22, __buffer, 3433 __buffer_size); 3434 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 3435 __len22, __buffer, __buffer_size); 3436 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 3437 __len2 - __len22, __buffer, __buffer_size); 3438 } 3439 } 3440 3441 /** 3442 * @if maint 3443 * This is a helper function for the merge routines. 3444 * @endif 3445 */ 3446 template<typename _BidirectionalIter, typename _Distance, typename _Pointer, 3447 typename _Compare> 3448 void 3449 __merge_adaptive(_BidirectionalIter __first, 3450 _BidirectionalIter __middle, 3451 _BidirectionalIter __last, 3452 _Distance __len1, _Distance __len2, 3453 _Pointer __buffer, _Distance __buffer_size, 3454 _Compare __comp) 3455 { 3456 if (__len1 <= __len2 && __len1 <= __buffer_size) { 3457 _Pointer __buffer_end = copy(__first, __middle, __buffer); 3458 merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 3459 } 3460 else if (__len2 <= __buffer_size) { 3461 _Pointer __buffer_end = copy(__middle, __last, __buffer); 3462 __merge_backward(__first, __middle, __buffer, __buffer_end, __last, 3463 __comp); 3464 } 3465 else { 3466 _BidirectionalIter __first_cut = __first; 3467 _BidirectionalIter __second_cut = __middle; 3468 _Distance __len11 = 0; 3469 _Distance __len22 = 0; 3470 if (__len1 > __len2) { 3471 __len11 = __len1 / 2; 3472 advance(__first_cut, __len11); 3473 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); 3474 __len22 = distance(__middle, __second_cut); 3475 } 3476 else { 3477 __len22 = __len2 / 2; 3478 advance(__second_cut, __len22); 3479 __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); 3480 __len11 = distance(__first, __first_cut); 3481 } 3482 _BidirectionalIter __new_middle = 3483 __rotate_adaptive(__first_cut, __middle, __second_cut, 3484 __len1 - __len11, __len22, __buffer, 3485 __buffer_size); 3486 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 3487 __len22, __buffer, __buffer_size, __comp); 3488 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 3489 __len2 - __len22, __buffer, __buffer_size, __comp); 3490 } 3491 } 3492 3493 /** 3494 * @brief Merges two sorted ranges in place. 3495 * @param first An iterator. 3496 * @param middle Another iterator. 3497 * @param last Another iterator. 3498 * @return Nothing. 3499 * 3500 * Merges two sorted and consecutive ranges, [first,middle) and 3501 * [middle,last), and puts the result in [first,last). The output will 3502 * be sorted. The sort is @e stable, that is, for equivalent 3503 * elements in the two ranges, elements from the first range will always 3504 * come before elements from the second. 3505 * 3506 * If enough additional memory is available, this takes (last-first)-1 3507 * comparisons. Otherwise an NlogN algorithm is used, where N is 3508 * distance(first,last). 3509 */ 3510 template<typename _BidirectionalIter> 3511 void 3512 inplace_merge(_BidirectionalIter __first, 3513 _BidirectionalIter __middle, 3514 _BidirectionalIter __last) 3515 { 3516 typedef typename iterator_traits<_BidirectionalIter>::value_type 3517 _ValueType; 3518 typedef typename iterator_traits<_BidirectionalIter>::difference_type 3519 _DistanceType; 3520 3521 // concept requirements 3522 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 3523 _BidirectionalIter>) 3524 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 3525 3526 if (__first == __middle || __middle == __last) 3527 return; 3528 3529 _DistanceType __len1 = distance(__first, __middle); 3530 _DistanceType __len2 = distance(__middle, __last); 3531 3532 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 3533 if (__buf.begin() == 0) 3534 __merge_without_buffer(__first, __middle, __last, __len1, __len2); 3535 else 3536 __merge_adaptive(__first, __middle, __last, __len1, __len2, 3537 __buf.begin(), _DistanceType(__buf.size())); 3538 } 3539 3540 /** 3541 * @brief Merges two sorted ranges in place. 3542 * @param first An iterator. 3543 * @param middle Another iterator. 3544 * @param last Another iterator. 3545 * @param comp A functor to use for comparisons. 3546 * @return Nothing. 3547 * 3548 * Merges two sorted and consecutive ranges, [first,middle) and 3549 * [middle,last), and puts the result in [first,last). The output will 3550 * be sorted. The sort is @e stable, that is, for equivalent 3551 * elements in the two ranges, elements from the first range will always 3552 * come before elements from the second. 3553 * 3554 * If enough additional memory is available, this takes (last-first)-1 3555 * comparisons. Otherwise an NlogN algorithm is used, where N is 3556 * distance(first,last). 3557 * 3558 * The comparison function should have the same effects on ordering as 3559 * the function used for the initial sort. 3560 */ 3561 template<typename _BidirectionalIter, typename _Compare> 3562 void 3563 inplace_merge(_BidirectionalIter __first, 3564 _BidirectionalIter __middle, 3565 _BidirectionalIter __last, 3566 _Compare __comp) 3567 { 3568 typedef typename iterator_traits<_BidirectionalIter>::value_type 3569 _ValueType; 3570 typedef typename iterator_traits<_BidirectionalIter>::difference_type 3571 _DistanceType; 3572 3573 // concept requirements 3574 __glibcpp_function_requires(_Mutable_BidirectionalIteratorConcept< 3575 _BidirectionalIter>) 3576 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3577 _ValueType, _ValueType>) 3578 3579 if (__first == __middle || __middle == __last) 3580 return; 3581 3582 _DistanceType __len1 = distance(__first, __middle); 3583 _DistanceType __len2 = distance(__middle, __last); 3584 3585 _Temporary_buffer<_BidirectionalIter, _ValueType> __buf(__first, __last); 3586 if (__buf.begin() == 0) 3587 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); 3588 else 3589 __merge_adaptive(__first, __middle, __last, __len1, __len2, 3590 __buf.begin(), _DistanceType(__buf.size()), 3591 __comp); 3592 } 3593 3594 // Set algorithms: includes, set_union, set_intersection, set_difference, 3595 // set_symmetric_difference. All of these algorithms have the precondition 3596 // that their input ranges are sorted and the postcondition that their output 3597 // ranges are sorted. 3598 3599 template<typename _InputIter1, typename _InputIter2> 3600 bool 3601 includes(_InputIter1 __first1, _InputIter1 __last1, 3602 _InputIter2 __first2, _InputIter2 __last2) 3603 { 3604 // concept requirements 3605 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3606 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3607 __glibcpp_function_requires(_SameTypeConcept< 3608 typename iterator_traits<_InputIter1>::value_type, 3609 typename iterator_traits<_InputIter2>::value_type>) 3610 __glibcpp_function_requires(_LessThanComparableConcept< 3611 typename iterator_traits<_InputIter1>::value_type>) 3612 3613 while (__first1 != __last1 && __first2 != __last2) 3614 if (*__first2 < *__first1) 3615 return false; 3616 else if(*__first1 < *__first2) 3617 ++__first1; 3618 else 3619 ++__first1, ++__first2; 3620 3621 return __first2 == __last2; 3622 } 3623 3624 template<typename _InputIter1, typename _InputIter2, typename _Compare> 3625 bool 3626 includes(_InputIter1 __first1, _InputIter1 __last1, 3627 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) 3628 { 3629 // concept requirements 3630 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3631 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3632 __glibcpp_function_requires(_SameTypeConcept< 3633 typename iterator_traits<_InputIter1>::value_type, 3634 typename iterator_traits<_InputIter2>::value_type>) 3635 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3636 typename iterator_traits<_InputIter1>::value_type, 3637 typename iterator_traits<_InputIter2>::value_type>) 3638 3639 while (__first1 != __last1 && __first2 != __last2) 3640 if (__comp(*__first2, *__first1)) 3641 return false; 3642 else if(__comp(*__first1, *__first2)) 3643 ++__first1; 3644 else 3645 ++__first1, ++__first2; 3646 3647 return __first2 == __last2; 3648 } 3649 3650 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 3651 _OutputIter 3652 set_union(_InputIter1 __first1, _InputIter1 __last1, 3653 _InputIter2 __first2, _InputIter2 __last2, 3654 _OutputIter __result) 3655 { 3656 // concept requirements 3657 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3658 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3659 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3660 typename iterator_traits<_InputIter1>::value_type>) 3661 __glibcpp_function_requires(_SameTypeConcept< 3662 typename iterator_traits<_InputIter1>::value_type, 3663 typename iterator_traits<_InputIter2>::value_type>) 3664 __glibcpp_function_requires(_LessThanComparableConcept< 3665 typename iterator_traits<_InputIter1>::value_type>) 3666 3667 while (__first1 != __last1 && __first2 != __last2) { 3668 if (*__first1 < *__first2) { 3669 *__result = *__first1; 3670 ++__first1; 3671 } 3672 else if (*__first2 < *__first1) { 3673 *__result = *__first2; 3674 ++__first2; 3675 } 3676 else { 3677 *__result = *__first1; 3678 ++__first1; 3679 ++__first2; 3680 } 3681 ++__result; 3682 } 3683 return copy(__first2, __last2, copy(__first1, __last1, __result)); 3684 } 3685 3686 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 3687 typename _Compare> 3688 _OutputIter 3689 set_union(_InputIter1 __first1, _InputIter1 __last1, 3690 _InputIter2 __first2, _InputIter2 __last2, 3691 _OutputIter __result, _Compare __comp) 3692 { 3693 // concept requirements 3694 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3695 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3696 __glibcpp_function_requires(_SameTypeConcept< 3697 typename iterator_traits<_InputIter1>::value_type, 3698 typename iterator_traits<_InputIter2>::value_type>) 3699 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3700 typename iterator_traits<_InputIter1>::value_type>) 3701 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3702 typename iterator_traits<_InputIter1>::value_type, 3703 typename iterator_traits<_InputIter2>::value_type>) 3704 3705 while (__first1 != __last1 && __first2 != __last2) { 3706 if (__comp(*__first1, *__first2)) { 3707 *__result = *__first1; 3708 ++__first1; 3709 } 3710 else if (__comp(*__first2, *__first1)) { 3711 *__result = *__first2; 3712 ++__first2; 3713 } 3714 else { 3715 *__result = *__first1; 3716 ++__first1; 3717 ++__first2; 3718 } 3719 ++__result; 3720 } 3721 return copy(__first2, __last2, copy(__first1, __last1, __result)); 3722 } 3723 3724 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 3725 _OutputIter 3726 set_intersection(_InputIter1 __first1, _InputIter1 __last1, 3727 _InputIter2 __first2, _InputIter2 __last2, 3728 _OutputIter __result) 3729 { 3730 // concept requirements 3731 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3732 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3733 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3734 typename iterator_traits<_InputIter1>::value_type>) 3735 __glibcpp_function_requires(_SameTypeConcept< 3736 typename iterator_traits<_InputIter1>::value_type, 3737 typename iterator_traits<_InputIter2>::value_type>) 3738 __glibcpp_function_requires(_LessThanComparableConcept< 3739 typename iterator_traits<_InputIter1>::value_type>) 3740 3741 while (__first1 != __last1 && __first2 != __last2) 3742 if (*__first1 < *__first2) 3743 ++__first1; 3744 else if (*__first2 < *__first1) 3745 ++__first2; 3746 else { 3747 *__result = *__first1; 3748 ++__first1; 3749 ++__first2; 3750 ++__result; 3751 } 3752 return __result; 3753 } 3754 3755 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 3756 typename _Compare> 3757 _OutputIter 3758 set_intersection(_InputIter1 __first1, _InputIter1 __last1, 3759 _InputIter2 __first2, _InputIter2 __last2, 3760 _OutputIter __result, _Compare __comp) 3761 { 3762 // concept requirements 3763 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3764 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3765 __glibcpp_function_requires(_SameTypeConcept< 3766 typename iterator_traits<_InputIter1>::value_type, 3767 typename iterator_traits<_InputIter2>::value_type>) 3768 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3769 typename iterator_traits<_InputIter1>::value_type>) 3770 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3771 typename iterator_traits<_InputIter1>::value_type, 3772 typename iterator_traits<_InputIter2>::value_type>) 3773 3774 while (__first1 != __last1 && __first2 != __last2) 3775 if (__comp(*__first1, *__first2)) 3776 ++__first1; 3777 else if (__comp(*__first2, *__first1)) 3778 ++__first2; 3779 else { 3780 *__result = *__first1; 3781 ++__first1; 3782 ++__first2; 3783 ++__result; 3784 } 3785 return __result; 3786 } 3787 3788 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 3789 _OutputIter 3790 set_difference(_InputIter1 __first1, _InputIter1 __last1, 3791 _InputIter2 __first2, _InputIter2 __last2, 3792 _OutputIter __result) 3793 { 3794 // concept requirements 3795 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3796 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3797 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3798 typename iterator_traits<_InputIter1>::value_type>) 3799 __glibcpp_function_requires(_SameTypeConcept< 3800 typename iterator_traits<_InputIter1>::value_type, 3801 typename iterator_traits<_InputIter2>::value_type>) 3802 __glibcpp_function_requires(_LessThanComparableConcept< 3803 typename iterator_traits<_InputIter1>::value_type>) 3804 3805 while (__first1 != __last1 && __first2 != __last2) 3806 if (*__first1 < *__first2) { 3807 *__result = *__first1; 3808 ++__first1; 3809 ++__result; 3810 } 3811 else if (*__first2 < *__first1) 3812 ++__first2; 3813 else { 3814 ++__first1; 3815 ++__first2; 3816 } 3817 return copy(__first1, __last1, __result); 3818 } 3819 3820 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 3821 typename _Compare> 3822 _OutputIter 3823 set_difference(_InputIter1 __first1, _InputIter1 __last1, 3824 _InputIter2 __first2, _InputIter2 __last2, 3825 _OutputIter __result, _Compare __comp) 3826 { 3827 // concept requirements 3828 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3829 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3830 __glibcpp_function_requires(_SameTypeConcept< 3831 typename iterator_traits<_InputIter1>::value_type, 3832 typename iterator_traits<_InputIter2>::value_type>) 3833 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3834 typename iterator_traits<_InputIter1>::value_type>) 3835 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3836 typename iterator_traits<_InputIter1>::value_type, 3837 typename iterator_traits<_InputIter2>::value_type>) 3838 3839 while (__first1 != __last1 && __first2 != __last2) 3840 if (__comp(*__first1, *__first2)) { 3841 *__result = *__first1; 3842 ++__first1; 3843 ++__result; 3844 } 3845 else if (__comp(*__first2, *__first1)) 3846 ++__first2; 3847 else { 3848 ++__first1; 3849 ++__first2; 3850 } 3851 return copy(__first1, __last1, __result); 3852 } 3853 3854 template<typename _InputIter1, typename _InputIter2, typename _OutputIter> 3855 _OutputIter 3856 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 3857 _InputIter2 __first2, _InputIter2 __last2, 3858 _OutputIter __result) 3859 { 3860 // concept requirements 3861 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3862 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3863 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3864 typename iterator_traits<_InputIter1>::value_type>) 3865 __glibcpp_function_requires(_SameTypeConcept< 3866 typename iterator_traits<_InputIter1>::value_type, 3867 typename iterator_traits<_InputIter2>::value_type>) 3868 __glibcpp_function_requires(_LessThanComparableConcept< 3869 typename iterator_traits<_InputIter1>::value_type>) 3870 3871 while (__first1 != __last1 && __first2 != __last2) 3872 if (*__first1 < *__first2) { 3873 *__result = *__first1; 3874 ++__first1; 3875 ++__result; 3876 } 3877 else if (*__first2 < *__first1) { 3878 *__result = *__first2; 3879 ++__first2; 3880 ++__result; 3881 } 3882 else { 3883 ++__first1; 3884 ++__first2; 3885 } 3886 return copy(__first2, __last2, copy(__first1, __last1, __result)); 3887 } 3888 3889 template<typename _InputIter1, typename _InputIter2, typename _OutputIter, 3890 typename _Compare> 3891 _OutputIter 3892 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 3893 _InputIter2 __first2, _InputIter2 __last2, 3894 _OutputIter __result, 3895 _Compare __comp) 3896 { 3897 // concept requirements 3898 __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) 3899 __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) 3900 __glibcpp_function_requires(_SameTypeConcept< 3901 typename iterator_traits<_InputIter1>::value_type, 3902 typename iterator_traits<_InputIter2>::value_type>) 3903 __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, 3904 typename iterator_traits<_InputIter1>::value_type>) 3905 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3906 typename iterator_traits<_InputIter1>::value_type, 3907 typename iterator_traits<_InputIter2>::value_type>) 3908 3909 while (__first1 != __last1 && __first2 != __last2) 3910 if (__comp(*__first1, *__first2)) { 3911 *__result = *__first1; 3912 ++__first1; 3913 ++__result; 3914 } 3915 else if (__comp(*__first2, *__first1)) { 3916 *__result = *__first2; 3917 ++__first2; 3918 ++__result; 3919 } 3920 else { 3921 ++__first1; 3922 ++__first2; 3923 } 3924 return copy(__first2, __last2, copy(__first1, __last1, __result)); 3925 } 3926 3927 // min_element and max_element, with and without an explicitly supplied 3928 // comparison function. 3929 3930 template<typename _ForwardIter> 3931 _ForwardIter 3932 max_element(_ForwardIter __first, _ForwardIter __last) 3933 { 3934 // concept requirements 3935 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 3936 __glibcpp_function_requires(_LessThanComparableConcept< 3937 typename iterator_traits<_ForwardIter>::value_type>) 3938 3939 if (__first == __last) return __first; 3940 _ForwardIter __result = __first; 3941 while (++__first != __last) 3942 if (*__result < *__first) 3943 __result = __first; 3944 return __result; 3945 } 3946 3947 template<typename _ForwardIter, typename _Compare> 3948 _ForwardIter 3949 max_element(_ForwardIter __first, _ForwardIter __last, 3950 _Compare __comp) 3951 { 3952 // concept requirements 3953 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 3954 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3955 typename iterator_traits<_ForwardIter>::value_type, 3956 typename iterator_traits<_ForwardIter>::value_type>) 3957 3958 if (__first == __last) return __first; 3959 _ForwardIter __result = __first; 3960 while (++__first != __last) 3961 if (__comp(*__result, *__first)) __result = __first; 3962 return __result; 3963 } 3964 3965 template<typename _ForwardIter> 3966 _ForwardIter 3967 min_element(_ForwardIter __first, _ForwardIter __last) 3968 { 3969 // concept requirements 3970 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 3971 __glibcpp_function_requires(_LessThanComparableConcept< 3972 typename iterator_traits<_ForwardIter>::value_type>) 3973 3974 if (__first == __last) return __first; 3975 _ForwardIter __result = __first; 3976 while (++__first != __last) 3977 if (*__first < *__result) 3978 __result = __first; 3979 return __result; 3980 } 3981 3982 template<typename _ForwardIter, typename _Compare> 3983 _ForwardIter 3984 min_element(_ForwardIter __first, _ForwardIter __last, 3985 _Compare __comp) 3986 { 3987 // concept requirements 3988 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 3989 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 3990 typename iterator_traits<_ForwardIter>::value_type, 3991 typename iterator_traits<_ForwardIter>::value_type>) 3992 3993 if (__first == __last) return __first; 3994 _ForwardIter __result = __first; 3995 while (++__first != __last) 3996 if (__comp(*__first, *__result)) 3997 __result = __first; 3998 return __result; 3999 } 4000 4001 // next_permutation and prev_permutation, with and without an explicitly 4002 // supplied comparison function. 4003 4004 template<typename _BidirectionalIter> 4005 bool 4006 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 4007 { 4008 // concept requirements 4009 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 4010 __glibcpp_function_requires(_LessThanComparableConcept< 4011 typename iterator_traits<_BidirectionalIter>::value_type>) 4012 4013 if (__first == __last) 4014 return false; 4015 _BidirectionalIter __i = __first; 4016 ++__i; 4017 if (__i == __last) 4018 return false; 4019 __i = __last; 4020 --__i; 4021 4022 for(;;) { 4023 _BidirectionalIter __ii = __i; 4024 --__i; 4025 if (*__i < *__ii) { 4026 _BidirectionalIter __j = __last; 4027 while (!(*__i < *--__j)) 4028 {} 4029 iter_swap(__i, __j); 4030 reverse(__ii, __last); 4031 return true; 4032 } 4033 if (__i == __first) { 4034 reverse(__first, __last); 4035 return false; 4036 } 4037 } 4038 } 4039 4040 template<typename _BidirectionalIter, typename _Compare> 4041 bool 4042 next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 4043 _Compare __comp) 4044 { 4045 // concept requirements 4046 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 4047 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 4048 typename iterator_traits<_BidirectionalIter>::value_type, 4049 typename iterator_traits<_BidirectionalIter>::value_type>) 4050 4051 if (__first == __last) 4052 return false; 4053 _BidirectionalIter __i = __first; 4054 ++__i; 4055 if (__i == __last) 4056 return false; 4057 __i = __last; 4058 --__i; 4059 4060 for(;;) { 4061 _BidirectionalIter __ii = __i; 4062 --__i; 4063 if (__comp(*__i, *__ii)) { 4064 _BidirectionalIter __j = __last; 4065 while (!__comp(*__i, *--__j)) 4066 {} 4067 iter_swap(__i, __j); 4068 reverse(__ii, __last); 4069 return true; 4070 } 4071 if (__i == __first) { 4072 reverse(__first, __last); 4073 return false; 4074 } 4075 } 4076 } 4077 4078 template<typename _BidirectionalIter> 4079 bool 4080 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) 4081 { 4082 // concept requirements 4083 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 4084 __glibcpp_function_requires(_LessThanComparableConcept< 4085 typename iterator_traits<_BidirectionalIter>::value_type>) 4086 4087 if (__first == __last) 4088 return false; 4089 _BidirectionalIter __i = __first; 4090 ++__i; 4091 if (__i == __last) 4092 return false; 4093 __i = __last; 4094 --__i; 4095 4096 for(;;) { 4097 _BidirectionalIter __ii = __i; 4098 --__i; 4099 if (*__ii < *__i) { 4100 _BidirectionalIter __j = __last; 4101 while (!(*--__j < *__i)) 4102 {} 4103 iter_swap(__i, __j); 4104 reverse(__ii, __last); 4105 return true; 4106 } 4107 if (__i == __first) { 4108 reverse(__first, __last); 4109 return false; 4110 } 4111 } 4112 } 4113 4114 template<typename _BidirectionalIter, typename _Compare> 4115 bool 4116 prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 4117 _Compare __comp) 4118 { 4119 // concept requirements 4120 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter>) 4121 __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, 4122 typename iterator_traits<_BidirectionalIter>::value_type, 4123 typename iterator_traits<_BidirectionalIter>::value_type>) 4124 4125 if (__first == __last) 4126 return false; 4127 _BidirectionalIter __i = __first; 4128 ++__i; 4129 if (__i == __last) 4130 return false; 4131 __i = __last; 4132 --__i; 4133 4134 for(;;) { 4135 _BidirectionalIter __ii = __i; 4136 --__i; 4137 if (__comp(*__ii, *__i)) { 4138 _BidirectionalIter __j = __last; 4139 while (!__comp(*--__j, *__i)) 4140 {} 4141 iter_swap(__i, __j); 4142 reverse(__ii, __last); 4143 return true; 4144 } 4145 if (__i == __first) { 4146 reverse(__first, __last); 4147 return false; 4148 } 4149 } 4150 } 4151 4152 // find_first_of, with and without an explicitly supplied comparison function. 4153 4154 template<typename _InputIter, typename _ForwardIter> 4155 _InputIter 4156 find_first_of(_InputIter __first1, _InputIter __last1, 4157 _ForwardIter __first2, _ForwardIter __last2) 4158 { 4159 // concept requirements 4160 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 4161 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 4162 __glibcpp_function_requires(_EqualOpConcept< 4163 typename iterator_traits<_InputIter>::value_type, 4164 typename iterator_traits<_ForwardIter>::value_type>) 4165 4166 for ( ; __first1 != __last1; ++__first1) 4167 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 4168 if (*__first1 == *__iter) 4169 return __first1; 4170 return __last1; 4171 } 4172 4173 template<typename _InputIter, typename _ForwardIter, typename _BinaryPredicate> 4174 _InputIter 4175 find_first_of(_InputIter __first1, _InputIter __last1, 4176 _ForwardIter __first2, _ForwardIter __last2, 4177 _BinaryPredicate __comp) 4178 { 4179 // concept requirements 4180 __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) 4181 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) 4182 __glibcpp_function_requires(_EqualOpConcept< 4183 typename iterator_traits<_InputIter>::value_type, 4184 typename iterator_traits<_ForwardIter>::value_type>) 4185 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4186 typename iterator_traits<_InputIter>::value_type, 4187 typename iterator_traits<_ForwardIter>::value_type>) 4188 4189 for ( ; __first1 != __last1; ++__first1) 4190 for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) 4191 if (__comp(*__first1, *__iter)) 4192 return __first1; 4193 return __last1; 4194 } 4195 4196 4197 // find_end, with and without an explicitly supplied comparison function. 4198 // Search [first2, last2) as a subsequence in [first1, last1), and return 4199 // the *last* possible match. Note that find_end for bidirectional iterators 4200 // is much faster than for forward iterators. 4201 4202 // find_end for forward iterators. 4203 template<typename _ForwardIter1, typename _ForwardIter2> 4204 _ForwardIter1 4205 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 4206 _ForwardIter2 __first2, _ForwardIter2 __last2, 4207 forward_iterator_tag, forward_iterator_tag) 4208 { 4209 if (__first2 == __last2) 4210 return __last1; 4211 else { 4212 _ForwardIter1 __result = __last1; 4213 while (1) { 4214 _ForwardIter1 __new_result 4215 = search(__first1, __last1, __first2, __last2); 4216 if (__new_result == __last1) 4217 return __result; 4218 else { 4219 __result = __new_result; 4220 __first1 = __new_result; 4221 ++__first1; 4222 } 4223 } 4224 } 4225 } 4226 4227 template<typename _ForwardIter1, typename _ForwardIter2, 4228 typename _BinaryPredicate> 4229 _ForwardIter1 4230 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 4231 _ForwardIter2 __first2, _ForwardIter2 __last2, 4232 forward_iterator_tag, forward_iterator_tag, 4233 _BinaryPredicate __comp) 4234 { 4235 if (__first2 == __last2) 4236 return __last1; 4237 else { 4238 _ForwardIter1 __result = __last1; 4239 while (1) { 4240 _ForwardIter1 __new_result 4241 = search(__first1, __last1, __first2, __last2, __comp); 4242 if (__new_result == __last1) 4243 return __result; 4244 else { 4245 __result = __new_result; 4246 __first1 = __new_result; 4247 ++__first1; 4248 } 4249 } 4250 } 4251 } 4252 4253 // find_end for bidirectional iterators. Requires partial specialization. 4254 template<typename _BidirectionalIter1, typename _BidirectionalIter2> 4255 _BidirectionalIter1 4256 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 4257 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 4258 bidirectional_iterator_tag, bidirectional_iterator_tag) 4259 { 4260 // concept requirements 4261 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 4262 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 4263 4264 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 4265 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 4266 4267 _RevIter1 __rlast1(__first1); 4268 _RevIter2 __rlast2(__first2); 4269 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 4270 _RevIter2(__last2), __rlast2); 4271 4272 if (__rresult == __rlast1) 4273 return __last1; 4274 else { 4275 _BidirectionalIter1 __result = __rresult.base(); 4276 advance(__result, -distance(__first2, __last2)); 4277 return __result; 4278 } 4279 } 4280 4281 template<typename _BidirectionalIter1, typename _BidirectionalIter2, 4282 typename _BinaryPredicate> 4283 _BidirectionalIter1 4284 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 4285 _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 4286 bidirectional_iterator_tag, bidirectional_iterator_tag, 4287 _BinaryPredicate __comp) 4288 { 4289 // concept requirements 4290 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter1>) 4291 __glibcpp_function_requires(_BidirectionalIteratorConcept<_BidirectionalIter2>) 4292 4293 typedef reverse_iterator<_BidirectionalIter1> _RevIter1; 4294 typedef reverse_iterator<_BidirectionalIter2> _RevIter2; 4295 4296 _RevIter1 __rlast1(__first1); 4297 _RevIter2 __rlast2(__first2); 4298 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, 4299 _RevIter2(__last2), __rlast2, 4300 __comp); 4301 4302 if (__rresult == __rlast1) 4303 return __last1; 4304 else { 4305 _BidirectionalIter1 __result = __rresult.base(); 4306 advance(__result, -distance(__first2, __last2)); 4307 return __result; 4308 } 4309 } 4310 4311 // Dispatching functions for find_end. 4312 4313 template<typename _ForwardIter1, typename _ForwardIter2> 4314 inline _ForwardIter1 4315 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 4316 _ForwardIter2 __first2, _ForwardIter2 __last2) 4317 { 4318 // concept requirements 4319 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 4320 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 4321 __glibcpp_function_requires(_EqualOpConcept< 4322 typename iterator_traits<_ForwardIter1>::value_type, 4323 typename iterator_traits<_ForwardIter2>::value_type>) 4324 4325 return __find_end(__first1, __last1, __first2, __last2, 4326 __iterator_category(__first1), 4327 __iterator_category(__first2)); 4328 } 4329 4330 template<typename _ForwardIter1, typename _ForwardIter2, 4331 typename _BinaryPredicate> 4332 inline _ForwardIter1 4333 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 4334 _ForwardIter2 __first2, _ForwardIter2 __last2, 4335 _BinaryPredicate __comp) 4336 { 4337 // concept requirements 4338 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>) 4339 __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>) 4340 __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4341 typename iterator_traits<_ForwardIter1>::value_type, 4342 typename iterator_traits<_ForwardIter2>::value_type>) 4343 4344 return __find_end(__first1, __last1, __first2, __last2, 4345 __iterator_category(__first1), 4346 __iterator_category(__first2), 4347 __comp); 4348 } 4349 4350} // namespace std 4351 4352#endif /* __GLIBCPP_INTERNAL_ALGO_H */ 4353 4354