Standard Template Library Programmer's Guide

• ForwardIterator is a model of Forward Iterator

• OutputIterator is a model of Output Iterator

• ForwardIterator 's value type is convertible to a type in OutputIterator 's set of value types.

• Distance is an integral type that is large enough to represent the value last – first .

For the second version:

• ForwardIterator is a model of Forward Iterator

• OutputIterator is a model of Output Iterator

• RandomNumberGenerator is a model of Random Number Generator

• Distance is an integral type that is large enough to represent the value last – first .

• ForwardIterator 's value type is convertible to a type in OutputIterator 's set of value types.

• Distance is convertible to RandomNumberGenerator 's argument type.

• [first, last) is a valid range.

• n is nonnegative.

• [first, last) and [out, out + n) do not overlap.

• There is enough space to hold all of the elements being copied. More formally, the requirement is that [out, out + min(n, last – first)) is a valid range.

• last – first is less than rand 's maximum value.

Linear in last – first . At most last – first elements from the input range are examined, and exactly min(n, last – first) elements are copied to the output range.

int main() {

const int N = 10;

int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

random_sample_n(A, A+N, ostream_iterator(cout, " "), 4);

// The printed value might be 3 5 6 10,

// or any of 209 other possibilities.

}

[1] This is "Algorithm S" from section 3.4.2 of Knuth (D. E. Knuth, The Art of Computer Programming. Volume 2: Seminumerical Algorithms , second edition. Addison-Wesley, 1981). Knuth credits C. T. Fan, M. E. Muller, and I. Rezucha (1962) and T. G. Jones (1962). Note that there are N! / n! / (N – n)! ways of selecting a sample of n elements from a range of N elements. Random_sample_n yields uniformly distributed results; that is, the probability of selecting any particular element is n / N , and the probability of any particular sampling is n! * (N – n)! / N! .

[2] In contrast, the random_sample algorithm does not preserve relative ordering within the input range. The other major distinction between the two algorithms is that random_sample_n requires its input range to be Forward Iterators and only requires its 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.

random_shuffle , random_sample , Random Number Generator

Category: algorithms

Component type: function

template

ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)

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 .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

• ForwardIterator is a model of Forward Iterator.

• Predicate is a model of Predicate.

• ForwardIterator 's value type is convertible to Predicate 's argument type.

• [first, last) is a valid range.

Linear. Exactly last – first applications of pred , and at most (last – first)/2 swaps.

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(), 0), bind2nd(modulus(), 2)));

copy(A, A + N, ostream_iterator(cout, " "));

// The output is "10 2 8 4 6 5 7 3 9 1". [1]

[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.

stable_partition , Predicate, function object

Category: algorithms

Component type: function

template

ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);

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]

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

• ForwardIterator is a model of Forward Iterator

• Predicate is a model of Predicate

• ForwardIterator 's value type is convertible to Predicate 's argument type.

• [first, last) is a valid range.