Algorithms - Partitions

Overview

Partitions are commonly used for searching and sorting. Partitioning algorithms  operate on various types of containers such as sequence, associative and unordered to perform actions such as partition, sort and more. 

These function accepts parameters like 

• iterators such as forward, bidirectional, input, output 
• predicates such as unary

The parameter type  UnaryPredicate  is a function that accepts a single input and returns bool value (true or false). 

For example, bool isodd(int i) {return (i % 2) == 1;} or [](int i) {return (i % 2) == 1;}

Details

Name	Description
ForwardIterator partition ( ForwardIterator first, ForwardIterator last,  UnaryPredicate pred)	Partition the elements in the range [first,last] into two groups such that all the elements for which pred returns true precede all those for which it returns false.  The iterator returned points to the first element of the second group. Example: vector<int> v{3,2,6,5,4,1}; //v = {3,1,5,6,4,2} //itr = begin(v)+3 auto itr = partition(begin(v), end(v), [](int n) {return ((n % 2) == 1); });
BidirectionalIterator stable_partition ( BidirectionalIterator first, BidirectionalIterator last,  UnaryPredicate pred)	Same as partition except the relative order of elements within each group is preserved. Example: vector<int> v{3,2,6,5,4,1}; //v = {3,5,1,2,6,4} //itr = begin(v)+3 auto itr = stable_partition(begin(v), end(v), [](int n) {return ((n % 2) == 1); });
pair<OutputIterator,OutputIterator>partition_copy( InputIterator first, InputIterator last,  OutputIterator itrtrue, OutputIterator itrfalse,  UnaryPredicate pred)	Copies the elements in the range [first,last] for which pred returns true into the range pointed by itrtrue, and those for which it does not into the range pointed by itrfalse.  Returns a pair of iterators with the end of the generated sequences pointed by itrtrue and itrfalse, respectively. Example: vector<int> v{3,2,6,5,4,1},vodd(3),veven(3); //p:{end(vodd),end(veven)} //vodd = {3,5,1} //veven = {2,6,4} auto p = partition_copy(begin(v), end(v), begin(vodd),begin(veven), [](int n) {return ((n % 2) == 1); });
ForwardIterator partition_point (ForwardIterator first, ForwardIterator last,  UnaryPredicate pred)	Returns an iterator to the first element in the partitioned range [first,last] for which pred is not true, indicating its partition point. Note that the range should be partitioned, otherwise end() is returned. Example: vector<int> v{1,2,3,4,5}; //itr = begin(v)+2 auto itr = partition_point(begin(v), end(v), [](int n) {return (n < 3); });
bool is_partitioned ( InputIterator first, InputIterator last,  UnaryPredicate pred)	Test whether range is partitioned.  Returns true if all the elements in the range [first,last] for which pred returns true precede those for which it returns false. Examples: vector<int> v{1,2,3,4,5}, v2 {4,3,1,5,2}; //b = true bool b = is_partitioned(begin(v)+3, end(v), [](int n) {return (n < 3); }); //b = false b = is_partitioned(begin(v2)+3, end(v2), [](int n) {return (n < 3); });

The example depicts the usage.

Summary of Examples

Name	Description	github	wandbox
Example	Usage	source    output	source + output