#include <algorithm> iterator partition( iterator start, iterator end, Predicate p );
The partition() algorithm re-orders the elements in [start,end) such that the elements for which the predicate p returns true come before the elements for which p returns false.
In other words, partition() uses p to divide the elements into two groups.
The return value of partition() is an iterator to the first element for which p returns false.
parition() runs in linear time.