...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 'is_partitioned_until.hpp' contains two variants of a single
algorithm, is_partitioned_until
.
The algorithm tests to see if a sequence is partitioned according to a predicate;
in other words, all the items in the sequence that satisfy the predicate
are at the beginning of the sequence.
The routine is_partitioned_until
takes a sequence and a predicate. It returns the last iterator 'it' in the
sequence [begin, end) for which the is_partitioned(begin, it) is true.
is_partitioned_until
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.
The function is_partitioned_until
returns the last iterator 'it' in the sequence [begin, end) for which the
is_partitioned(begin, it) is true. There are two versions; one takes two
iterators, and the other takes a range.
template<typename InputIterator, typename Predicate> InputIterator is_partitioned_until ( InputIterator first, InputIterator last, Predicate p ); template<typename Range, typename Predicate> typename boost::range_iterator<const Range>::type is_partitioned_until ( const Range &r, Predicate p );
Given the container c
containing
{ 0, 1,
2, 3, 14, 15 }
,
then
bool isOdd ( int i ) { return i % 2 == 1; } bool lessThan10 ( int i ) { return i < 10; } is_partitioned_until ( c, isOdd ) --> iterator to '1' is_partitioned_until ( c, lessThan10 ) --> end is_partitioned_until ( c.begin (), c.end (), lessThan10 ) --> end is_partitioned_until ( c.begin (), c.begin () + 3, lessThan10 ) --> end is_partitioned_until ( c.end (), c.end (), isOdd ) --> end // empty range
is_partitioned_until
works
on all iterators except output iterators.
Both of the variants of is_partitioned_until
run in O(N) (linear) time; that is, they compare against
each element in the list once. If the sequence is found to be not partitioned
at any point, the routine will terminate immediately, without examining the
rest of the elements.
Both of the variants of is_partitioned_until
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.
is_partitioned_until
returns iterator to the end for empty and single-element ranges, no matter
what predicate is passed to test against.