...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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.
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 );
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
partition_point
requires
forward iterators or better; it will not work on input iterators or output
iterators.
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.
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.
partition_point
is also available as part of the C++11 standard.