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