Boost C++ Libraries

The header file 'partition_point.hpp' contains two variants of a single algorithm, partition_point. Given a partitioned sequence and a predicate, the algorithm finds the partition point; i.e, the first element in the sequence that does not satisfy the predicate.

The routine partition_point takes a partitioned sequence and a predicate. It returns an iterator which 'points to' the first element in the sequence that does not satisfy the predicate. If all the items in the sequence satisfy the predicate, then it returns one past the final element in the sequence.

partition_point come in two forms; the first one takes two iterators to define the range. The second form takes a single range parameter, and uses Boost.Range to traverse it.

interface

There are two versions; one takes two iterators, and the other takes a range.

template<typename ForwardIterator, typename Predicate>
	ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p );
template<typename Range, typename Predicate>
	boost::range_iterator<Range> partition_point ( const Range &r, Predicate p );

Examples

Given the container c containing { 0, 1, 2, 3, 14, 15 }, then

bool lessThan10 ( int i ) { return i < 10; }
bool isOdd ( int i ) { return i % 2 == 1; }

partition_point ( c, lessThan10 ) --> c.begin () + 4  (pointing at 14)
partition_point ( c.begin (), c.end (), lessThan10 ) --> c.begin () + 4  (pointing at 14)
partition_point ( c.begin (), c.begin () + 3, lessThan10 ) -> c.begin () + 3 (end)
partition_point ( c.end (), c.end (), isOdd ) --> c.end ()  // empty range

Iterator Requirements

partition_point requires forward iterators or better; it will not work on input iterators or output iterators.

Complexity

Both of the variants of partition_point run in O( log (N)) (logarithmic) time; that is, the predicate will be will be applied approximately log(N) times. To do this, however, the algorithm needs to know the size of the sequence. For forward and bidirectional iterators, calculating the size of the sequence is an O(N) operation.

Exception Safety

Both of the variants of partition_point take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.

Notes