output range to be Output Iterators, while random_sample only requires its input range to be Input Iterators and requires its output range to be Random Access Iterators.
See also random_shuffle, random_sample, Random Number Generator
Category: algorithms
Component type: function
Prototype template <class ForwardIterator, class Predicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)
Description Partition reorders the elements in the range [first, last) based on the function object pred, such that the elements that satisfy pred precede the elements that fail to satisfy it. The postcondition is that, for some iterator middle in the range [first, last), pred(*i) is true for every iterator i in the range [first, middle) and false for every iterator i in the range [middle, last). [1] The return value of partition is middle.
Definition Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
Requirements on types • ForwardIterator is a model of Forward Iterator.
• Predicate is a model of Predicate.
• ForwardIterator's value type is convertible to Predicate's argument type.
Preconditions • [first, last) is a valid range.
Complexity Linear. Exactly last – first applications of pred , and at most (last – first)/2 swaps.
Example Reorder a sequence so that even numbers precede odd numbers.
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A + N, compose1(bind2nd(equal_to<int>(), 0), bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, ' '));
// The output is '10 2 8 4 6 5 7 3 9 1'. [1]
Notes [1] The relative order of elements in these two blocks is not necessarily the same as it was in the original sequence. A different algorithm, stable_partition, does guarantee to preserve the relative order.
See also stable_partition, Predicate, function object
Category: algorithms
Component type: function
Prototype template <class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
Description Stable_partition is much like partition: it reorders the elements in the range [first, last) based on the function object pred, such that all of the elements that satisfy pred appear before all of the elements that fail to satisfy it. The postcondition is that, for some iterator middle in the range [first, last), pred(*i) is true for every iterator i in the range [first, middle) and false for every iterator i in the range [middle, last). The return value of stable_partition is middle.
Stable_partition differs from partition in that stable_partition is guaranteed to preserve relative order. That is, if x and y are elements in [first, last) such that pred(x) == pred(y), and if x precedes y, then it will still be true after stable_partition is true that x precedes y. [1]
Definition Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.
Requirements on types • ForwardIterator is a model of Forward Iterator
• Predicate is a model of Predicate
• ForwardIterator's value type is convertible to Predicate's argument type.
Preconditions • [first, last) is a valid range.
Complexity Stable_partition is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is at most N*log(N) swaps, where N is last – first, and best case (if a large enough auxiliary memory buffer is available) is linear in N. In either case, pred is applied exactly N times.
Example Reorder a sequence so that even numbers precede odd numbers.
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
