Partitions

These functions are found in the #include <algorithm> library.

Suppose you have a Boolean-valued function (a "predicate", represented as bool predicate( T entry )) on a given type and you have a range in a container of that type. That range is partitioned if all entries up to some point return true when passed to bool predicate(...), and all subsequent entries return false. If our Boolean-valued function returns true if an integer is odd, then the this first example is not partitioned:

    4, 5, 5, 9, 9, 2, 0, 0, 0, 5

Thus, you can partition any range within a container that has a bi-directional iterator (which includes containers with random-access containers).

The Boolean-valued function can be, for example, the name of a function (an identifier), an object that has a public bool Class_name::operator()( T entry ) member operator, or a lambda expression []( T entry )->bool { /* some code returning a bool... */ }.

The function std::is_partitioned( itr_first, itr_beyond, bool predicate( T entry ) ) returns true if the range is partitioned, and false otherwise.

The function std::partition( itr_first, itr_beyond, bool predicate( T entry ) ) partitions the entries in the range and returns an iterator itr_first_false so that the range itr_first to itr_first_false are all entries that are true and itr_first_false to itr_beyond are all that are false. The order, however, may not match the original order. Thus, partitioning for odd numbers first,

    3, 6, 7, 3, 9, 2, 9, 3, 4, 2

may be partitioned as

    3, 3, 7, 3, 9, 9, 2, 2, 4, 6

In the original range, the order of the odd entries are 3, 7, 3, 9, 9, 3 while in the partitioned range, the odd entries are 3, 3, 7, 3, 9, 9.

The std::stable_partition(...) algorithm is similar but much slower but the partition will preserve the order of those that satisfy the Boolean-valued function, and those that don't, so the result would be:

    3, 7, 3, 9, 9, 3, 6, 2, 4, 2

The function std::partition_copy( itr_first, itr_beyond, itr_true, itr_false, bool predicate( T entry ) ) copies those entries that are true to the range starting at itr_true and those that are false to the range starting at itr_false. The returned value is a pair of iterators pair_beyond such that the true range is itr_true to pair_beyond.first and the false range is itr_false to pair_beyond.second. This is a stable partition.

The function std::partition_point( itr_first, itr_beyond, bool predicate( T entry ) ) assumes the range is partitioned and returns an iterator to the first entry that is false; thus the range for the true entries is itr_first up to the returned iterator, and the false entries start at the returned iterator and go up to itr_beyond.

You can view examples at replit.com.