1// This file is part of the ustl library, an STL implementation. 2// 3// Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net> 4// This file is free software, distributed under the MIT License. 5// 6// ualgo.h 7// 8// Implementation of STL algorithms. 9// 10// The function prototypes are copied 11// exactly from the SGI version of STL documentation along with comments about 12// their use. The code is NOT the same, though the functionality usually is. 13// 14 15#ifndef UALGO_H_711AB4214D417A51166694D47A662D6E 16#define UALGO_H_711AB4214D417A51166694D47A662D6E 17 18#include "upair.h" 19#include "ualgobase.h" 20#include "ufunction.h" 21#include "upredalgo.h" 22#include "umemory.h" 23#include <stdlib.h> // for rand() 24 25namespace ustl { 26 27/// Swaps corresponding elements of [first, last) and [result,) 28/// \ingroup SwapAlgorithms 29/// 30template <typename ForwardIterator1, typename ForwardIterator2> 31inline ForwardIterator2 swap_ranges (ForwardIterator1 first, ForwardIterator2 last, ForwardIterator2 result) 32{ 33 for (; first != last; ++first, ++result) 34 iter_swap (first, result); 35 return (result); 36} 37 38/// Returns the first iterator i in the range [first, last) such that 39/// *i == value. Returns last if no such iterator exists. 40/// \ingroup SearchingAlgorithms 41/// 42template <typename InputIterator, typename EqualityComparable> 43inline InputIterator find (InputIterator first, InputIterator last, const EqualityComparable& value) 44{ 45 while (first != last && !(*first == value)) 46 ++ first; 47 return (first); 48} 49 50/// Returns the first iterator such that *i == *(i + 1) 51/// \ingroup SearchingAlgorithms 52/// 53template <typename ForwardIterator> 54ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last) 55{ 56 if (first != last) 57 for (ForwardIterator prev = first; ++first != last; ++ prev) 58 if (*prev == *first) 59 return (prev); 60 return (last); 61} 62 63/// Returns the pointer to the first pair of unequal elements. 64/// \ingroup SearchingAlgorithms 65/// 66template <typename InputIterator> 67pair<InputIterator,InputIterator> 68mismatch (InputIterator first1, InputIterator last1, InputIterator first2) 69{ 70 while (first1 != last1 && *first1 == *first2) 71 ++ first1, ++ first2; 72 return (make_pair (first1, first2)); 73} 74 75/// \brief Returns true if two ranges are equal. 76/// This is an extension, present in uSTL and SGI STL. 77/// \ingroup SearchingAlgorithms 78/// 79template <typename InputIterator> 80inline bool equal (InputIterator first1, InputIterator last1, InputIterator first2) 81{ 82 return (mismatch (first1, last1, first2).first == last1); 83} 84 85/// Count finds the number of elements in [first, last) that are equal 86/// to value. More precisely, the first version of count returns the 87/// number of iterators i in [first, last) such that *i == value. 88/// \ingroup SearchingAlgorithms 89/// 90template <typename InputIterator, typename EqualityComparable> 91inline size_t count (InputIterator first, InputIterator last, const EqualityComparable& value) 92{ 93 size_t total = 0; 94 for (; first != last; ++first) 95 if (*first == value) 96 ++ total; 97 return (total); 98} 99 100/// 101/// The first version of transform performs the operation op(*i) for each 102/// iterator i in the range [first, last), and assigns the result of that 103/// operation to *o, where o is the corresponding output iterator. That is, 104/// for each n such that 0 <= n < last - first, it performs the assignment 105/// *(result + n) = op(*(first + n)). 106/// The return value is result + (last - first). 107/// \ingroup MutatingAlgorithms 108/// \ingroup PredicateAlgorithms 109/// 110template <typename InputIterator, typename OutputIterator, typename UnaryFunction> 111inline OutputIterator transform (InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op) 112{ 113 for (; first != last; ++result, ++first) 114 *result = op (*first); 115 return (result); 116} 117 118/// 119/// The second version of transform is very similar, except that it uses a 120/// Binary Function instead of a Unary Function: it performs the operation 121/// op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns 122/// the result to *o, where i2 is the corresponding iterator in the second 123/// input range and where o is the corresponding output iterator. That is, 124/// for each n such that 0 <= n < last1 - first1, it performs the assignment 125/// *(result + n) = op(*(first1 + n), *(first2 + n). 126/// The return value is result + (last1 - first1). 127/// \ingroup MutatingAlgorithms 128/// \ingroup PredicateAlgorithms 129/// 130template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryFunction> 131inline OutputIterator transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction op) 132{ 133 for (; first1 != last1; ++result, ++first1, ++first2) 134 *result = op (*first1, *first2); 135 return (result); 136} 137 138/// Replace replaces every element in the range [first, last) equal to 139/// old_value with new_value. That is: for every iterator i, 140/// if *i == old_value then it performs the assignment *i = new_value. 141/// \ingroup MutatingAlgorithms 142/// 143template <typename ForwardIterator, typename T> 144inline void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value) 145{ 146 for (; first != last; ++first) 147 if (*first == old_value) 148 *first = new_value; 149} 150 151/// Replace_copy copies elements from the range [first, last) to the range 152/// [result, result + (last-first)), except that any element equal to old_value 153/// is not copied; new_value is copied instead. More precisely, for every 154/// integer n such that 0 <= n < last-first, replace_copy performs the 155/// assignment *(result+n) = new_value if *(first+n) == old_value, and 156/// *(result+n) = *(first+n) otherwise. 157/// \ingroup MutatingAlgorithms 158/// 159template <typename InputIterator, typename OutputIterator, typename T> 160inline OutputIterator replace_copy (InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value) 161{ 162 for (; first != last; ++result, ++first) 163 *result = (*first == old_value) ? new_value : *first; 164} 165 166/// Generate assigns the result of invoking gen, a function object that 167/// takes no arguments, to each element in the range [first, last). 168/// \ingroup GeneratorAlgorithms 169/// \ingroup PredicateAlgorithms 170/// 171template <typename ForwardIterator, typename Generator> 172inline void generate (ForwardIterator first, ForwardIterator last, Generator gen) 173{ 174 for (; first != last; ++first) 175 *first = gen(); 176} 177 178/// Generate_n assigns the result of invoking gen, a function object that 179/// takes no arguments, to each element in the range [first, first+n). 180/// The return value is first + n. 181/// \ingroup GeneratorAlgorithms 182/// \ingroup PredicateAlgorithms 183/// 184template <typename OutputIterator, typename Generator> 185inline OutputIterator generate_n (OutputIterator first, size_t n, Generator gen) 186{ 187 for (uoff_t i = 0; i != n; ++i, ++first) 188 *first = gen(); 189 return (first); 190} 191 192/// \brief Reverse reverses a range. 193/// That is: for every i such that 0 <= i <= (last - first) / 2), 194/// it exchanges *(first + i) and *(last - (i + 1)). 195/// \ingroup MutatingAlgorithms 196/// 197template <typename BidirectionalIterator> 198inline void reverse (BidirectionalIterator first, BidirectionalIterator last) 199{ 200 for (; distance (first, --last) > 0; ++first) 201 iter_swap (first, last); 202} 203 204/// \brief Reverses [first,last) and writes it to \p output. 205/// \ingroup MutatingAlgorithms 206/// 207template <typename BidirectionalIterator, typename OutputIterator> 208inline OutputIterator reverse_copy (BidirectionalIterator first, BidirectionalIterator last, OutputIterator result) 209{ 210 for (; first != last; ++result) 211 *result = *--last; 212 return (result); 213} 214 215/// \brief Exchanges ranges [first, middle) and [middle, last) 216/// \ingroup MutatingAlgorithms 217/// 218template <typename ForwardIterator> 219ForwardIterator rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last) 220{ 221 if (first == middle || middle == last) 222 return (first); 223 reverse (first, middle); 224 reverse (middle, last); 225 for (;first != middle && middle != last; ++first) 226 iter_swap (first, --last); 227 reverse (first, (first == middle ? last : middle)); 228 return (first); 229} 230 231/// Specialization for pointers, which can be treated identically. 232template <typename T> 233inline T* rotate (T* first, T* middle, T* last) 234{ 235 rotate_fast (first, middle, last); 236 return (first); 237} 238 239 240/// \brief Exchanges ranges [first, middle) and [middle, last) into \p result. 241/// \ingroup MutatingAlgorithms 242/// 243template <typename ForwardIterator, typename OutputIterator> 244inline OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result) 245{ 246 return (copy (first, middle, copy (middle, last, result))); 247} 248 249/// \brief Combines two sorted ranges. 250/// \ingroup SortingAlgorithms 251/// 252template <typename InputIterator1, typename InputIterator2, typename OutputIterator> 253OutputIterator merge (InputIterator1 first1, InputIterator1 last1, 254 InputIterator2 first2, InputIterator2 last2, OutputIterator result) 255{ 256 for (; first1 != last1 && first2 != last2; ++result) { 257 if (*first1 < *first2) 258 *result = *first1++; 259 else 260 *result = *first2++; 261 } 262 if (first1 < last1) 263 return (copy (first1, last1, result)); 264 else 265 return (copy (first2, last2, result)); 266} 267 268/// Combines two sorted ranges from the same container. 269/// \ingroup SortingAlgorithms 270/// 271template <typename InputIterator> 272void inplace_merge (InputIterator first, InputIterator middle, InputIterator last) 273{ 274 for (; middle != last; ++first) { 275 while (*first < *middle) 276 ++ first; 277 reverse (first, middle); 278 reverse (first, ++middle); 279 } 280} 281 282/// Remove_copy copies elements that are not equal to value from the range 283/// [first, last) to a range beginning at result. The return value is the 284/// end of the resulting range. This operation is stable, meaning that the 285/// relative order of the elements that are copied is the same as in the 286/// range [first, last). 287/// \ingroup MutatingAlgorithms 288/// 289template <typename InputIterator, typename OutputIterator, typename T> 290OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T& value) 291{ 292 for (; first != last; ++first) { 293 if (!(*first == value)) { 294 *result = *first; 295 ++ result; 296 } 297 } 298 return (result); 299} 300 301/// Remove_copy copies elements pointed to by iterators in [rfirst, rlast) 302/// from the range [first, last) to a range beginning at result. The return 303/// value is the end of the resulting range. This operation is stable, meaning 304/// that the relative order of the elements that are copied is the same as in the 305/// range [first, last). Range [rfirst, rlast) is assumed to be sorted. 306/// This algorithm is a uSTL extension. 307/// \ingroup MutatingAlgorithms 308/// 309template <typename InputIterator, typename OutputIterator, typename RInputIterator> 310OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, RInputIterator rfirst, RInputIterator rlast) 311{ 312 for (; first != last; ++first) { 313 while (rfirst != rlast && *rfirst < first) 314 ++ rfirst; 315 if (rfirst == rlast || first != *rfirst) { 316 *result = *first; 317 ++ result; 318 } 319 } 320 return (result); 321} 322 323/// Remove removes from the range [first, last) all elements that are equal to 324/// value. That is, remove returns an iterator new_last such that the range 325/// [first, new_last) contains no elements equal to value. [1] The iterators 326/// in the range [new_last, last) are all still dereferenceable, but the 327/// elements that they point to are unspecified. Remove is stable, meaning 328/// that the relative order of elements that are not equal to value is 329/// unchanged. 330/// \ingroup MutatingAlgorithms 331/// 332template <typename ForwardIterator, typename T> 333inline ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& value) 334{ 335 return (remove_copy (first, last, first, value)); 336} 337 338/// Unique_copy copies elements from the range [first, last) to a range 339/// beginning with result, except that in a consecutive group of duplicate 340/// elements only the first one is copied. The return value is the end of 341/// the range to which the elements are copied. This behavior is similar 342/// to the Unix filter uniq. 343/// \ingroup MutatingAlgorithms 344/// 345template <typename InputIterator, typename OutputIterator> 346OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result) 347{ 348 if (first != last) { 349 *result = *first; 350 while (++first != last) 351 if (!(*first == *result)) 352 *++result = *first; 353 ++ result; 354 } 355 return (result); 356} 357 358/// Every time a consecutive group of duplicate elements appears in the range 359/// [first, last), the algorithm unique removes all but the first element. 360/// That is, unique returns an iterator new_last such that the range [first, 361/// new_last) contains no two consecutive elements that are duplicates. 362/// The iterators in the range [new_last, last) are all still dereferenceable, 363/// but the elements that they point to are unspecified. Unique is stable, 364/// meaning that the relative order of elements that are not removed is 365/// unchanged. 366/// \ingroup MutatingAlgorithms 367/// 368template <typename ForwardIterator> 369inline ForwardIterator unique (ForwardIterator first, ForwardIterator last) 370{ 371 return (unique_copy (first, last, first)); 372} 373 374/// Returns the furthermost iterator i in [first, last) such that, 375/// for every iterator j in [first, i), *j < value 376/// Assumes the range is sorted. 377/// \ingroup SearchingAlgorithms 378/// 379template <typename ForwardIterator, typename LessThanComparable> 380ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 381{ 382 ForwardIterator mid; 383 while (first != last) { 384 mid = advance (first, distance (first,last) / 2); 385 if (*mid < value) 386 first = mid + 1; 387 else 388 last = mid; 389 } 390 return (first); 391} 392 393/// Performs a binary search inside the sorted range. 394/// \ingroup SearchingAlgorithms 395/// 396template <typename ForwardIterator, typename LessThanComparable> 397inline ForwardIterator binary_search (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 398{ 399 ForwardIterator found = lower_bound (first, last, value); 400 return ((found == last || value < *found) ? last : found); 401} 402 403/// Returns the furthermost iterator i in [first,last) such that for 404/// every iterator j in [first,i), value < *j is false. 405/// \ingroup SearchingAlgorithms 406/// 407template <typename ForwardIterator, typename LessThanComparable> 408ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 409{ 410 ForwardIterator mid; 411 while (first != last) { 412 mid = advance (first, distance (first,last) / 2); 413 if (value < *mid) 414 last = mid; 415 else 416 first = mid + 1; 417 } 418 return (last); 419} 420 421/// Returns pair<lower_bound,upper_bound> 422/// \ingroup SearchingAlgorithms 423/// 424template <typename ForwardIterator, typename LessThanComparable> 425inline pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const LessThanComparable& value) 426{ 427 pair<ForwardIterator,ForwardIterator> rv; 428 rv.second = rv.first = lower_bound (first, last, value); 429 while (rv.second != last && !(value < *(rv.second))) 430 ++ rv.second; 431 return (rv); 432} 433 434/// Randomly permute the elements of the container. 435/// \ingroup GeneratorAlgorithms 436/// 437template <typename RandomAccessIterator> 438void random_shuffle (RandomAccessIterator first, RandomAccessIterator last) 439{ 440 for (; first != last; ++ first) 441 iter_swap (first, first + (rand() % distance (first, last))); 442} 443 444/// \brief Generic compare function adaptor to pass to qsort 445/// \ingroup FunctorObjects 446template <typename ConstPointer, typename Compare> 447int qsort_adapter (const void* p1, const void* p2) 448{ 449 ConstPointer i1 = reinterpret_cast<ConstPointer>(p1); 450 ConstPointer i2 = reinterpret_cast<ConstPointer>(p2); 451 Compare comp; 452 return (comp (*i1, *i2) ? -1 : (comp (*i2, *i1) ? 1 : 0)); 453} 454 455/// Sorts the container 456/// \ingroup SortingAlgorithms 457/// \ingroup PredicateAlgorithms 458/// 459template <typename RandomAccessIterator, typename Compare> 460void sort (RandomAccessIterator first, RandomAccessIterator last, Compare) 461{ 462 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 463 typedef typename iterator_traits<RandomAccessIterator>::const_pointer const_pointer; 464 qsort (first, distance (first, last), sizeof(value_type), 465 &qsort_adapter<const_pointer, Compare>); 466} 467 468/// Sorts the container 469/// \ingroup SortingAlgorithms 470/// 471template <typename RandomAccessIterator> 472inline void sort (RandomAccessIterator first, RandomAccessIterator last) 473{ 474 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 475 sort (first, last, less<value_type>()); 476} 477 478/// Sorts the container preserving order of equal elements. 479/// \ingroup SortingAlgorithms 480/// \ingroup PredicateAlgorithms 481/// 482template <typename RandomAccessIterator, typename Compare> 483void stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp) 484{ 485 for (RandomAccessIterator j, i = first; ++i < last;) { // Insertion sort 486 for (j = i; j-- > first && !comp(*j, *i);); 487 rotate (++j, i, i + 1); 488 } 489} 490 491/// Sorts the container 492/// \ingroup SortingAlgorithms 493/// 494template <typename RandomAccessIterator> 495inline void stable_sort (RandomAccessIterator first, RandomAccessIterator last) 496{ 497 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 498 stable_sort (first, last, less<value_type>()); 499} 500 501/// \brief Searches for the first subsequence [first2,last2) in [first1,last1) 502/// \ingroup SearchingAlgorithms 503template <typename ForwardIterator1, typename ForwardIterator2> 504inline ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) 505{ 506 typedef typename iterator_traits<ForwardIterator1>::value_type value_type; 507 return (search (first1, last1, first2, last2, equal_to<value_type>())); 508} 509 510/// \brief Searches for the last subsequence [first2,last2) in [first1,last1) 511/// \ingroup SearchingAlgorithms 512template <typename ForwardIterator1, typename ForwardIterator2> 513inline ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) 514{ 515 typedef typename iterator_traits<ForwardIterator1>::value_type value_type; 516 return (find_end (first1, last1, first2, last2, equal_to<value_type>())); 517} 518 519/// \brief Searches for the first occurence of \p count \p values in [first, last) 520/// \ingroup SearchingAlgorithms 521template <typename Iterator, typename T> 522inline Iterator search_n (Iterator first, Iterator last, size_t count, const T& value) 523{ 524 typedef typename iterator_traits<Iterator>::value_type value_type; 525 return (search_n (first, last, count, value, equal_to<value_type>())); 526} 527 528/// \brief Searches [first1,last1) for the first occurrence of an element from [first2,last2) 529/// \ingroup SearchingAlgorithms 530template <typename InputIterator, typename ForwardIterator> 531inline InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2) 532{ 533 typedef typename iterator_traits<InputIterator>::value_type value_type; 534 return (find_first_of (first1, last1, first2, last2, equal_to<value_type>())); 535} 536 537/// \brief Returns true if [first2,last2) is a subset of [first1,last1) 538/// \ingroup ConditionAlgorithms 539/// \ingroup SetAlgorithms 540template <typename InputIterator1, typename InputIterator2> 541inline bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) 542{ 543 typedef typename iterator_traits<InputIterator1>::value_type value_type; 544 return (includes (first1, last1, first2, last2, less<value_type>())); 545} 546 547/// \brief Merges [first1,last1) with [first2,last2) 548/// 549/// Result will contain every element that is in either set. If duplicate 550/// elements are present, max(n,m) is placed in the result. 551/// 552/// \ingroup SetAlgorithms 553template <typename InputIterator1, typename InputIterator2, typename OutputIterator> 554inline OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 555{ 556 typedef typename iterator_traits<InputIterator1>::value_type value_type; 557 return (set_union (first1, last1, first2, last2, result, less<value_type>())); 558} 559 560/// \brief Creates a set containing elements shared by the given ranges. 561/// \ingroup SetAlgorithms 562template <typename InputIterator1, typename InputIterator2, typename OutputIterator> 563inline OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 564{ 565 typedef typename iterator_traits<InputIterator1>::value_type value_type; 566 return (set_intersection (first1, last1, first2, last2, result, less<value_type>())); 567} 568 569/// \brief Removes from [first1,last1) elements present in [first2,last2) 570/// \ingroup SetAlgorithms 571template <typename InputIterator1, typename InputIterator2, typename OutputIterator> 572inline OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 573{ 574 typedef typename iterator_traits<InputIterator1>::value_type value_type; 575 return (set_difference (first1, last1, first2, last2, result, less<value_type>())); 576} 577 578/// \brief Performs union of sets A-B and B-A. 579/// \ingroup SetAlgorithms 580template <typename InputIterator1, typename InputIterator2, typename OutputIterator> 581inline OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 582{ 583 typedef typename iterator_traits<InputIterator1>::value_type value_type; 584 return (set_symmetric_difference (first1, last1, first2, last2, result, less<value_type>())); 585} 586 587/// \brief Returns true if the given range is sorted. 588/// \ingroup ConditionAlgorithms 589template <typename ForwardIterator> 590inline bool is_sorted (ForwardIterator first, ForwardIterator last) 591{ 592 typedef typename iterator_traits<ForwardIterator>::value_type value_type; 593 return (is_sorted (first, last, less<value_type>())); 594} 595 596/// \brief Compares two given containers like strcmp compares strings. 597/// \ingroup ConditionAlgorithms 598template <typename InputIterator1, typename InputIterator2> 599inline bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) 600{ 601 typedef typename iterator_traits<InputIterator1>::value_type value_type; 602 return (lexicographical_compare (first1, last1, first2, last2, less<value_type>())); 603} 604 605/// \brief Creates the next lexicographical permutation of [first,last). 606/// Returns false if no further permutations can be created. 607/// \ingroup GeneratorAlgorithms 608template <typename BidirectionalIterator> 609inline bool next_permutation (BidirectionalIterator first, BidirectionalIterator last) 610{ 611 typedef typename iterator_traits<BidirectionalIterator>::value_type value_type; 612 return (next_permutation (first, last, less<value_type>())); 613} 614 615/// \brief Creates the previous lexicographical permutation of [first,last). 616/// Returns false if no further permutations can be created. 617/// \ingroup GeneratorAlgorithms 618template <typename BidirectionalIterator> 619inline bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last) 620{ 621 typedef typename iterator_traits<BidirectionalIterator>::value_type value_type; 622 return (prev_permutation (first, last, less<value_type>())); 623} 624 625/// \brief Returns iterator to the max element in [first,last) 626/// \ingroup SearchingAlgorithms 627template <typename ForwardIterator> 628inline ForwardIterator max_element (ForwardIterator first, ForwardIterator last) 629{ 630 typedef typename iterator_traits<ForwardIterator>::value_type value_type; 631 return (max_element (first, last, less<value_type>())); 632} 633 634/// \brief Returns iterator to the min element in [first,last) 635/// \ingroup SearchingAlgorithms 636template <typename ForwardIterator> 637inline ForwardIterator min_element (ForwardIterator first, ForwardIterator last) 638{ 639 typedef typename iterator_traits<ForwardIterator>::value_type value_type; 640 return (min_element (first, last, less<value_type>())); 641} 642 643/// \brief Makes [first,middle) a part of the sorted array. 644/// Contents of [middle,last) is undefined. This implementation just calls stable_sort. 645/// \ingroup SortingAlgorithms 646template <typename RandomAccessIterator> 647inline void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) 648{ 649 typedef typename iterator_traits<RandomAccessIterator>::value_type value_type; 650 partial_sort (first, middle, last, less<value_type>()); 651} 652 653/// \brief Puts \p nth element into its sorted position. 654/// In this implementation, the entire array is sorted. I can't think of any 655/// use for it where the time gained would be useful. 656/// \ingroup SortingAlgorithms 657/// \ingroup SearchingAlgorithms 658/// 659template <typename RandomAccessIterator> 660inline void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) 661{ 662 partial_sort (first, nth, last); 663} 664 665/// \brief Like partial_sort, but outputs to [result_first,result_last) 666/// \ingroup SortingAlgorithms 667template <typename InputIterator, typename RandomAccessIterator> 668inline RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last) 669{ 670 typedef typename iterator_traits<InputIterator>::value_type value_type; 671 return (partial_sort_copy (first, last, result_first, result_last, less<value_type>())); 672} 673 674} // namespace ustl 675 676#endif 677 678