1 // This file is part of the ustl library, an STL implementation. 2 // 3 // Copyright (C) 2005 by Mike Sharov <msharov (at) users.sourceforge.net> 4 // This file is free software, distributed under the MIT License. 5 // 6 // ualgo.h 7 // 8 // Implementation of STL algorithms with custom predicates. 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 UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5 16 #define UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5 17 18 namespace ustl { 19 20 /// Copy_if copies elements from the range [first, last) to the range 21 /// [result, result + (last - first)) if pred(*i) returns true. 22 /// \ingroup MutatingAlgorithms 23 /// \ingroup PredicateAlgorithms 24 /// 25 template <typename InputIterator, typename OutputIterator, typename Predicate> 26 inline OutputIterator copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred) 27 { 28 for (; first != last; ++first) { 29 if (pred(*first)) { 30 *result = *first; 31 ++ result; 32 } 33 } 34 return (result); 35 } 36 37 /// Returns the first iterator i in the range [first, last) such that 38 /// pred(*i) is true. Returns last if no such iterator exists. 39 /// \ingroup SearchingAlgorithms 40 /// \ingroup PredicateAlgorithms 41 /// 42 template <typename InputIterator, typename Predicate> 43 inline InputIterator find_if (InputIterator first, InputIterator last, Predicate pred) 44 { 45 while (first != last && !pred (*first)) 46 ++ first; 47 return (first); 48 } 49 50 /// Returns the first iterator such that p(*i, *(i + 1)) == true. 51 /// \ingroup SearchingAlgorithms 52 /// \ingroup PredicateAlgorithms 53 /// 54 template <typename ForwardIterator, typename BinaryPredicate> 55 inline ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate p) 56 { 57 if (first != last) 58 for (ForwardIterator prev = first; ++first != last; ++ prev) 59 if (p (*prev, *first)) 60 return (prev); 61 return (last); 62 } 63 64 /// Returns the pointer to the first pair of unequal elements. 65 /// \ingroup SearchingAlgorithms 66 /// \ingroup PredicateAlgorithms 67 /// 68 template <typename InputIterator, typename BinaryPredicate> 69 inline pair<InputIterator,InputIterator> 70 mismatch (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp) 71 { 72 while (first1 != last1 && comp(*first1, *first2)) 73 ++ first1, ++ first2; 74 return (make_pair (first1, first2)); 75 } 76 77 /// Returns true if two ranges are equal. 78 /// This is an extension, present in uSTL and SGI STL. 79 /// \ingroup ConditionAlgorithms 80 /// \ingroup PredicateAlgorithms 81 /// 82 template <typename InputIterator, typename BinaryPredicate> 83 inline bool equal (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp) 84 { 85 return (mismatch (first1, last1, first2, comp).first == last1); 86 } 87 88 /// Count_if finds the number of elements in [first, last) that satisfy the 89 /// predicate pred. More precisely, the first version of count_if returns the 90 /// number of iterators i in [first, last) such that pred(*i) is true. 91 /// \ingroup ConditionAlgorithms 92 /// \ingroup PredicateAlgorithms 93 /// 94 template <typename InputIterator, typename Predicate> 95 inline size_t count_if (InputIterator first, InputIterator last, Predicate pred) 96 { 97 size_t total = 0; 98 for (; first != last; ++first) 99 if (pred (*first)) 100 ++ total; 101 return (total); 102 } 103 104 /// Replace_if replaces every element in the range [first, last) for which 105 /// pred returns true with new_value. That is: for every iterator i, if 106 /// pred(*i) is true then it performs the assignment *i = new_value. 107 /// \ingroup MutatingAlgorithms 108 /// \ingroup PredicateAlgorithms 109 /// 110 template <typename ForwardIterator, typename Predicate, typename T> 111 inline void replace_if (ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value) 112 { 113 for (; first != last; ++first) 114 if (pred (*first)) 115 *first = new_value; 116 } 117 118 /// Replace_copy_if copies elements from the range [first, last) to the range 119 /// [result, result + (last-first)), except that any element for which pred is 120 /// true is not copied; new_value is copied instead. More precisely, for every 121 /// integer n such that 0 <= n < last-first, replace_copy_if performs the 122 /// assignment *(result+n) = new_value if pred(*(first+n)), 123 /// and *(result+n) = *(first+n) otherwise. 124 /// \ingroup MutatingAlgorithms 125 /// \ingroup PredicateAlgorithms 126 /// 127 template <typename InputIterator, typename OutputIterator, typename Predicate, typename T> 128 inline OutputIterator replace_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value) 129 { 130 for (; first != last; ++result, ++first) 131 *result = pred(*first) ? new_value : *first; 132 } 133 134 /// Remove_copy_if copies elements from the range [first, last) to a range 135 /// beginning at result, except that elements for which pred is true are not 136 /// copied. The return value is the end of the resulting range. This operation 137 /// is stable, meaning that the relative order of the elements that are copied 138 /// is the same as in the range [first, last). 139 /// \ingroup MutatingAlgorithms 140 /// \ingroup PredicateAlgorithms 141 /// 142 template <typename InputIterator, typename OutputIterator, typename Predicate> 143 inline OutputIterator remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred) 144 { 145 for (; first != last; ++first) 146 if (pred (*first)) 147 *result++ = *first; 148 return (result); 149 } 150 151 /// Remove_if removes from the range [first, last) every element x such that 152 /// pred(x) is true. That is, remove_if returns an iterator new_last such that 153 /// the range [first, new_last) contains no elements for which pred is true. 154 /// The iterators in the range [new_last, last) are all still dereferenceable, 155 /// but the elements that they point to are unspecified. Remove_if is stable, 156 /// meaning that the relative order of elements that are not removed is 157 /// unchanged. 158 /// \ingroup MutatingAlgorithms 159 /// \ingroup PredicateAlgorithms 160 /// 161 template <typename ForwardIterator, typename Predicate> 162 inline ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, Predicate pred) 163 { 164 return (remove_copy_if (first, last, first, pred)); 165 } 166 167 /// The reason there are two different versions of unique_copy is that there 168 /// are two different definitions of what it means for a consecutive group of 169 /// elements to be duplicates. In the first version, the test is simple 170 /// equality: the elements in a range [f, l) are duplicates if, for every 171 /// iterator i in the range, either i == f or else *i == *(i-1). In the second, 172 /// the test is an arbitrary Binary Predicate binary_pred: the elements in 173 /// [f, l) are duplicates if, for every iterator i in the range, either 174 /// i == f or else binary_pred(*i, *(i-1)) is true. 175 /// \ingroup MutatingAlgorithms 176 /// \ingroup PredicateAlgorithms 177 /// 178 template <typename InputIterator, typename OutputIterator, typename BinaryPredicate> 179 OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred) 180 { 181 if (first != last) { 182 *result = *first; 183 while (++first != last) 184 if (!binary_pred (*first, *result)) 185 *++result = *first; 186 ++ result; 187 } 188 return (result); 189 } 190 191 /// Every time a consecutive group of duplicate elements appears in the range 192 /// [first, last), the algorithm unique removes all but the first element. 193 /// That is, unique returns an iterator new_last such that the range [first, 194 /// new_last) contains no two consecutive elements that are duplicates. 195 /// The iterators in the range [new_last, last) are all still dereferenceable, 196 /// but the elements that they point to are unspecified. Unique is stable, 197 /// meaning that the relative order of elements that are not removed is 198 /// unchanged. 199 /// \ingroup MutatingAlgorithms 200 /// \ingroup PredicateAlgorithms 201 /// 202 template <typename ForwardIterator, typename BinaryPredicate> 203 inline ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred) 204 { 205 return (unique_copy (first, last, first, binary_pred)); 206 } 207 208 /// Returns the furthermost iterator i in [first, last) such that, 209 /// for every iterator j in [first, i), comp(*j, value) is true. 210 /// Assumes the range is sorted. 211 /// \ingroup SearchingAlgorithms 212 /// \ingroup PredicateAlgorithms 213 /// 214 template <typename ForwardIterator, typename T, typename StrictWeakOrdering> 215 ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) 216 { 217 ForwardIterator mid; 218 while (first != last) { 219 mid = advance (first, distance (first,last) / 2); 220 if (comp (*mid, value)) 221 first = mid + 1; 222 else 223 last = mid; 224 } 225 return (first); 226 } 227 228 /// Performs a binary search inside the sorted range. 229 /// \ingroup SearchingAlgorithms 230 /// \ingroup PredicateAlgorithms 231 /// 232 template <typename ForwardIterator, typename T, typename StrictWeakOrdering> 233 inline ForwardIterator binary_search (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) 234 { 235 ForwardIterator found = lower_bound (first, last, value, comp); 236 return ((found == last || comp(value, *found)) ? last : found); 237 } 238 239 /// Returns the furthermost iterator i in [first,last) such that for 240 /// every iterator j in [first,i), comp(value,*j) is false. 241 /// \ingroup SearchingAlgorithms 242 /// \ingroup PredicateAlgorithms 243 /// 244 template <typename ForwardIterator, typename T, typename StrictWeakOrdering> 245 ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) 246 { 247 ForwardIterator mid; 248 while (first != last) { 249 mid = advance (first, distance (first,last) / 2); 250 if (comp (value, *mid)) 251 last = mid; 252 else 253 first = mid + 1; 254 } 255 return (last); 256 } 257 258 /// Returns pair<lower_bound,upper_bound> 259 /// \ingroup SearchingAlgorithms 260 /// \ingroup PredicateAlgorithms 261 /// 262 template <typename ForwardIterator, typename T, typename StrictWeakOrdering> 263 inline pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp) 264 { 265 pair<ForwardIterator,ForwardIterator> rv; 266 rv.second = rv.first = lower_bound (first, last, value, comp); 267 while (rv.second != last && !comp(value, *(rv.second))) 268 ++ rv.second; 269 return (rv); 270 } 271 272 /// \brief Puts \p nth element into its sorted position. 273 /// In this implementation, the entire array is sorted. The performance difference is 274 /// so small and the function use is so rare, there is no need to have code for it. 275 /// \ingroup SortingAlgorithms 276 /// \ingroup SearchingAlgorithms 277 /// \ingroup PredicateAlgorithms 278 /// 279 template <typename RandomAccessIterator, typename Compare> 280 inline void nth_element (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, Compare comp) 281 { 282 sort (first, last, comp); 283 } 284 285 /// \brief Searches for the first subsequence [first2,last2) in [first1,last1) 286 /// \ingroup SearchingAlgorithms 287 /// \ingroup PredicateAlgorithms 288 template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate> 289 ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp) 290 { 291 const ForwardIterator1 slast = last1 - distance(first2, last2) + 1; 292 for (; first1 < slast; ++first1) { 293 ForwardIterator2 i = first2; 294 ForwardIterator1 j = first1; 295 for (; i != last2 && comp(*j, *i); ++i, ++j); 296 if (i == last2) 297 return (first1); 298 } 299 return (last1); 300 } 301 302 /// \brief Searches for the last subsequence [first2,last2) in [first1,last1) 303 /// \ingroup SearchingAlgorithms 304 /// \ingroup PredicateAlgorithms 305 template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate> 306 ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp) 307 { 308 ForwardIterator1 s = last1 - distance(first2, last2); 309 for (; first1 < s; --s) { 310 ForwardIterator2 i = first2, j = s; 311 for (; i != last2 && comp(*j, *i); ++i, ++j); 312 if (i == last2) 313 return (s); 314 } 315 return (last1); 316 } 317 318 /// \brief Searches for the first occurence of \p count \p values in [first, last) 319 /// \ingroup SearchingAlgorithms 320 /// \ingroup PredicateAlgorithms 321 template <typename Iterator, typename T, typename BinaryPredicate> 322 Iterator search_n (Iterator first, Iterator last, size_t count, const T& value, BinaryPredicate comp) 323 { 324 size_t n = 0; 325 for (; first != last; ++first) { 326 if (!comp (*first, value)) 327 n = 0; 328 else if (++n == count) 329 return (first - --n); 330 } 331 return (last); 332 } 333 334 /// \brief Searches [first1,last1) for the first occurrence of an element from [first2,last2) 335 /// \ingroup SearchingAlgorithms 336 /// \ingroup PredicateAlgorithms 337 template <typename InputIterator, typename ForwardIterator, typename BinaryPredicate> 338 InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate comp) 339 { 340 for (; first1 != last1; ++first1) 341 for (ForwardIterator i = first2; i != last2; ++i) 342 if (comp (*first1, *i)) 343 return (first1); 344 return (first1); 345 } 346 347 /// \brief Returns true if [first2,last2) is a subset of [first1,last1) 348 /// \ingroup ConditionAlgorithms 349 /// \ingroup SetAlgorithms 350 /// \ingroup PredicateAlgorithms 351 template <typename InputIterator1, typename InputIterator2, typename StrictWeakOrdering> 352 bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering comp) 353 { 354 for (; (first1 != last1) & (first2 != last2); ++first1) { 355 if (comp (*first2, *first1)) 356 return (false); 357 first2 += !comp (*first1, *first2); 358 } 359 return (first2 == last2); 360 } 361 362 /// \brief Merges [first1,last1) with [first2,last2) 363 /// 364 /// Result will contain every element that is in either set. If duplicate 365 /// elements are present, max(n,m) is placed in the result. 366 /// 367 /// \ingroup SetAlgorithms 368 /// \ingroup PredicateAlgorithms 369 template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> 370 OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) 371 { 372 for (; (first1 != last1) & (first2 != last2); ++result) { 373 if (comp (*first2, *first1)) 374 *result = *first2++; 375 else { 376 first2 += !comp (*first1, *first2); 377 *result = *first1++; 378 } 379 } 380 return (copy (first2, last2, copy (first1, last1, result))); 381 } 382 383 /// \brief Creates a set containing elements shared by the given ranges. 384 /// \ingroup SetAlgorithms 385 /// \ingroup PredicateAlgorithms 386 template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> 387 OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) 388 { 389 while ((first1 != last1) & (first2 != last2)) { 390 bool b1ge2 = !comp (*first1, *first2), b2ge1 = !comp (*first2, *first1); 391 if (b1ge2 & b2ge1) 392 *result++ = *first1; 393 first1 += b2ge1; 394 first2 += b1ge2; 395 } 396 return (result); 397 } 398 399 /// \brief Removes from [first1,last1) elements present in [first2,last2) 400 /// \ingroup SetAlgorithms 401 /// \ingroup PredicateAlgorithms 402 template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> 403 OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) 404 { 405 while ((first1 != last1) & (first2 != last2)) { 406 bool b1ge2 = !comp (*first1, *first2), b2ge1 = !comp (*first2, *first1); 407 if (!b1ge2) 408 *result++ = *first1; 409 first1 += b2ge1; 410 first2 += b1ge2; 411 } 412 return (copy (first1, last1, result)); 413 } 414 415 /// \brief Performs union of sets A-B and B-A. 416 /// \ingroup SetAlgorithms 417 /// \ingroup PredicateAlgorithms 418 template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering> 419 OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp) 420 { 421 while ((first1 != last1) & (first2 != last2)) { 422 bool b1l2 = comp (*first1, *first2), b2l1 = comp (*first2, *first1); 423 if (b1l2) 424 *result++ = *first1; 425 else if (b2l1) 426 *result++ = *first2; 427 first1 += !b2l1; 428 first2 += !b1l2; 429 } 430 return (copy (first2, last2, copy (first1, last1, result))); 431 } 432 433 /// \brief Returns true if the given range is sorted. 434 /// \ingroup ConditionAlgorithms 435 /// \ingroup PredicateAlgorithms 436 template <typename ForwardIterator, typename StrictWeakOrdering> 437 bool is_sorted (ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp) 438 { 439 for (ForwardIterator i = first; ++i < last; ++first) 440 if (comp (*i, *first)) 441 return (false); 442 return (true); 443 } 444 445 /// \brief Compares two given containers like strcmp compares strings. 446 /// \ingroup ConditionAlgorithms 447 /// \ingroup PredicateAlgorithms 448 template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate> 449 bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate comp) 450 { 451 for (; (first1 != last1) & (first2 != last2); ++first1, ++first2) { 452 if (comp (*first1, *first2)) 453 return (true); 454 if (comp (*first2, *first1)) 455 return (false); 456 } 457 return ((first1 == last1) & (first2 != last2)); 458 } 459 460 /// \brief Creates the next lexicographical permutation of [first,last). 461 /// Returns false if no further permutations can be created. 462 /// \ingroup GeneratorAlgorithms 463 /// \ingroup PredicateAlgorithms 464 template <typename BidirectionalIterator, typename StrictWeakOrdering> 465 bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp) 466 { 467 if (distance (first, last) < 2) 468 return (false); 469 BidirectionalIterator i = last; 470 for (--i; i != first; ) { 471 --i; 472 if (comp (i[0], i[1])) { 473 BidirectionalIterator j = last; 474 while (!comp (*i, *--j)); 475 iter_swap (i, j); 476 reverse (i + 1, last); 477 return (true); 478 } 479 } 480 reverse (first, last); 481 return (false); 482 } 483 484 /// \brief Creates the previous lexicographical permutation of [first,last). 485 /// Returns false if no further permutations can be created. 486 /// \ingroup GeneratorAlgorithms 487 /// \ingroup PredicateAlgorithms 488 template <typename BidirectionalIterator, typename StrictWeakOrdering> 489 bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp) 490 { 491 if (distance (first, last) < 2) 492 return (false); 493 BidirectionalIterator i = last; 494 for (--i; i != first; ) { 495 --i; 496 if (comp(i[1], i[0])) { 497 BidirectionalIterator j = last; 498 while (!comp (*--j, *i)); 499 iter_swap (i, j); 500 reverse (i + 1, last); 501 return (true); 502 } 503 } 504 reverse (first, last); 505 return (false); 506 } 507 508 /// \brief Returns iterator to the max element in [first,last) 509 /// \ingroup SearchingAlgorithms 510 /// \ingroup PredicateAlgorithms 511 template <typename ForwardIterator, typename BinaryPredicate> 512 inline ForwardIterator max_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp) 513 { 514 ForwardIterator result = first; 515 for (; first != last; ++first) 516 if (comp (*result, *first)) 517 result = first; 518 return (result); 519 } 520 521 /// \brief Returns iterator to the min element in [first,last) 522 /// \ingroup SearchingAlgorithms 523 /// \ingroup PredicateAlgorithms 524 template <typename ForwardIterator, typename BinaryPredicate> 525 inline ForwardIterator min_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp) 526 { 527 ForwardIterator result = first; 528 for (; first != last; ++first) 529 if (comp (*first, *result)) 530 result = first; 531 return (result); 532 } 533 534 /// \brief Makes [first,middle) a part of the sorted array. 535 /// Contents of [middle,last) is undefined. This implementation just calls stable_sort. 536 /// \ingroup SortingAlgorithms 537 /// \ingroup PredicateAlgorithms 538 template <typename RandomAccessIterator, typename StrictWeakOrdering> 539 inline void partial_sort (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, StrictWeakOrdering comp) 540 { 541 stable_sort (first, last, comp); 542 } 543 544 /// \brief Like partial_sort, but outputs to [result_first,result_last) 545 /// \ingroup SortingAlgorithms 546 /// \ingroup PredicateAlgorithms 547 template <typename InputIterator, typename RandomAccessIterator, typename StrictWeakOrdering> 548 RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering comp) 549 { 550 RandomAccessIterator rend = result_first; 551 for (; first != last; ++first) { 552 RandomAccessIterator i = result_first; 553 for (; i != rend && comp (*i, *first); ++i); 554 if (i == result_last) 555 continue; 556 rend += (rend < result_last); 557 copy_backward (i, rend - 1, rend); 558 *i = *first; 559 } 560 return (rend); 561 } 562 563 /// \brief Like \ref partition, but preserves equal element order. 564 /// \ingroup SortingAlgorithms 565 /// \ingroup PredicateAlgorithms 566 template <typename ForwardIterator, typename Predicate> 567 ForwardIterator stable_partition (ForwardIterator first, ForwardIterator last, Predicate pred) 568 { 569 if (first == last) 570 return (first); 571 ForwardIterator l, r, m = advance (first, distance (first, last) / 2); 572 if (first == m) 573 return (pred(*first) ? last : first); 574 l = stable_partition (first, m, pred); 575 r = stable_partition (m, last, pred); 576 rotate (l, m, r); 577 return (advance (l, distance (m, r))); 578 } 579 580 /// \brief Splits [first,last) in two by \p pred. 581 /// 582 /// Creates two ranges [first,middle) and [middle,last), where every element 583 /// in the former is less than every element in the latter. 584 /// The return value is middle. 585 /// 586 /// \ingroup SortingAlgorithms 587 /// \ingroup PredicateAlgorithms 588 template <typename ForwardIterator, typename Predicate> 589 inline ForwardIterator partition (ForwardIterator first, ForwardIterator last, Predicate pred) 590 { 591 return (stable_partition (first, last, pred)); 592 } 593 594 } // namespace ustl 595 596 #endif 597 598