...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 'boost/algorithm/cxx11/all_of.hpp' contains four variants
of a single algorithm, all_of
.
The algorithm tests all the elements of a sequence and returns true if
they all share a property.
The routine all_of
takes
a sequence and a predicate. It will return true if the predicate returns
true when applied to every element in the sequence.
The routine all_of_equal
takes a sequence and a value. It will return true if every element in the
sequence compares equal to the passed in value.
Both routines 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 all_of
returns
true if the predicate returns true for every item in the sequence. There
are two versions; one takes two iterators, and the other takes a range.
namespace boost { namespace algorithm { template<typename InputIterator, typename Predicate> bool all_of ( InputIterator first, InputIterator last, Predicate p ); template<typename Range, typename Predicate> bool all_of ( const Range &r, Predicate p ); }}
The function all_of_equal
is similar to all_of
, but
instead of taking a predicate to test the elements of the sequence, it
takes a value to compare against.
namespace boost { namespace algorithm { template<typename InputIterator, typename V> bool all_of_equal ( InputIterator first, InputIterator last, V const &val ); template<typename Range, typename V> bool all_of_equal ( const Range &r, V const &val ); }}
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; } using boost::algorithm; all_of ( c, isOdd ) --> false all_of ( c.begin (), c.end (), lessThan10 ) --> false all_of ( c.begin (), c.begin () + 3, lessThan10 ) --> true all_of ( c.end (), c.end (), isOdd ) --> true // empty range all_of_equal ( c, 3 ) --> false all_of_equal ( c.begin () + 3, c.begin () + 4, 3 ) --> true all_of_equal ( c.begin (), c.begin (), 99 ) --> true // empty range
all_of
and all_of_equal
work on all iterators except
output iterators.
All of the variants of all_of
and all_of_equal
run in
O(N) (linear) time; that is, they compare against
each element in the list once. If any of the comparisons fail, the algorithm
will terminate immediately, without examining the remaining members of
the sequence.
All of the variants of all_of
and all_of_equal
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.
all_of
is also available as part of the C++11 standard.
all_of
and all_of_equal
both return true for
empty ranges, no matter what is passed to test against. When there
are no items in the sequence to test, they all satisfy the condition
to be tested against.
all_of_value
is a template parameter, rather than deduced from the first parameter
(std::iterator_traits<InputIterator>::value_type
) because that allows more
flexibility for callers, and takes advantage of built-in comparisons
for the type that is pointed to by the iterator. The function is defined
to return true if, for all elements in the sequence, the expression
*iter
== val
evaluates to true (where iter
is an iterator to each element in the sequence)
The header file 'boost/algorithm/cxx11/any_of.hpp' contains four variants
of a single algorithm, any_of
.
The algorithm tests the elements of a sequence and returns true if any
of the elements has a particular property.
The routine any_of
takes
a sequence and a predicate. It will return true if the predicate returns
true for any element in the sequence.
The routine any_of_equal
takes a sequence and a value. It will return true if any element in the
sequence compares equal to the passed in value.
Both routines 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 any_of
returns
true if the predicate returns true any item in the sequence. There are
two versions; one takes two iterators, and the other takes a range.
namespace boost { namespace algorithm { template<typename InputIterator, typename Predicate> bool any_of ( InputIterator first, InputIterator last, Predicate p ); template<typename Range, typename Predicate> bool any_of ( const Range &r, Predicate p ); }}
The function any_of_equal
is similar to any_of
, but
instead of taking a predicate to test the elements of the sequence, it
takes a value to compare against.
namespace boost { namespace algorithm { template<typename InputIterator, typename V> bool any_of_equal ( InputIterator first, InputIterator last, V const &val ); template<typename Range, typename V> bool any_of_equal ( const Range &r, V const &val ); }}
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; } using boost::algorithm; any_of ( c, isOdd ) --> true any_of ( c.begin (), c.end (), lessThan10 ) --> true any_of ( c.begin () + 4, c.end (), lessThan10 ) --> false any_of ( c.end (), c.end (), isOdd ) --> false // empty range any_of_equal ( c, 3 ) --> true any_of_equal ( c.begin (), c.begin () + 3, 3 ) --> false any_of_equal ( c.begin (), c.begin (), 99 ) --> false // empty range
any_of
and any_of_equal
work on all iterators except
output iterators.
All of the variants of any_of
and any_of_equal
run in
O(N) (linear) time; that is, they compare against
each element in the list once. If any of the comparisons succeed, the algorithm
will terminate immediately, without examining the remaining members of
the sequence.
All of the variants of any_of
and any_of_equal
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.
any_of
is also available as part of the C++11 standard.
any_of
and any_of_equal
both return false for
empty ranges, no matter what is passed to test against.
any_of_value
is a template parameter, rather than deduced from the first parameter
(std::iterator_traits<InputIterator>::value_type
) because that allows more
flexibility for callers, and takes advantage of built-in comparisons
for the type that is pointed to by the iterator. The function is defined
to return true if, for any element in the sequence, the expression
*iter
== val
evaluates to true (where iter
is an iterator to each element in the sequence)
The header file 'boost/algorithm/cxx11/none_of.hpp' contains four variants
of a single algorithm, none_of
.
The algorithm tests all the elements of a sequence and returns true if
they none of them share a property.
The routine none_of
takes
a sequence and a predicate. It will return true if the predicate returns
false when applied to every element in the sequence.
The routine none_of_equal
takes a sequence and a value. It will return true if none of the elements
in the sequence compare equal to the passed in value.
Both routines 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 none_of
returns
true if the predicate returns false for every item in the sequence. There
are two versions; one takes two iterators, and the other takes a range.
namespace boost { namespace algorithm { template<typename InputIterator, typename Predicate> bool none_of ( InputIterator first, InputIterator last, Predicate p ); template<typename Range, typename Predicate> bool none_of ( const Range &r, Predicate p ); }}
The function none_of_equal
is similar to none_of
,
but instead of taking a predicate to test the elements of the sequence,
it takes a value to compare against.
namespace boost { namespace algorithm { template<typename InputIterator, typename V> bool none_of_equal ( InputIterator first, InputIterator last, V const &val ); template<typename Range, typename V> bool none_of_equal ( const Range &r, V const &val ); }}
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; } using boost::algorithm; none_of ( c, isOdd ) --> false none_of ( c.begin (), c.end (), lessThan10 ) --> false none_of ( c.begin () + 4, c.end (), lessThan10 ) --> true none_of ( c.end (), c.end (), isOdd ) --> true // empty range none_of_equal ( c, 3 ) --> false none_of_equal ( c.begin (), c.begin () + 3, 3 ) --> true none_of_equal ( c.begin (), c.begin (), 99 ) --> true // empty range
none_of
and none_of_equal
work on all iterators except
output iterators.
All of the variants of none_of
and none_of_equal
run in
O(N) (linear) time; that is, they compare against
each element in the list once. If any of the comparisons succeed, the algorithm
will terminate immediately, without examining the remaining members of
the sequence.
All of the variants of none_of
and none_of_equal
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.
none_of
is also available as part of the C++11 standard.
none_of
and none_of_equal
both return true for
empty ranges, no matter what is passed to test against.
none_of_value
is a template parameter, rather than deduced from the first parameter
(std::iterator_traits<InputIterator>::value_type
) because that allows more
flexibility for callers, and takes advantage of built-in comparisons
for the type that is pointed to by the iterator. The function is defined
to return true if, for all elements in the sequence, the expression
*iter
== val
evaluates to false (where iter
is an iterator to each element in the sequence)
The header file 'boost/algorithm/cxx11/one_of.hpp' contains four variants
of a single algorithm, one_of
.
The algorithm tests the elements of a sequence and returns true if exactly
one of the elements in the sequence has a particular property.
The routine one_of
takes
a sequence and a predicate. It will return true if the predicate returns
true for one element in the sequence.
The routine one_of_equal
takes a sequence and a value. It will return true if one element in the
sequence compares equal to the passed in value.
Both routines 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 one_of
returns
true if the predicate returns true for one item in the sequence. There
are two versions; one takes two iterators, and the other takes a range.
namespace boost { namespace algorithm { template<typename InputIterator, typename Predicate> bool one_of ( InputIterator first, InputIterator last, Predicate p ); template<typename Range, typename Predicate> bool one_of ( const Range &r, Predicate p ); }}
The function one_of_equal
is similar to one_of
, but
instead of taking a predicate to test the elements of the sequence, it
takes a value to compare against.
namespace boost { namespace algorithm { template<typename InputIterator, typename V> bool one_of_equal ( InputIterator first, InputIterator last, V const &val ); template<typename Range, typename V> bool one_of_equal ( const Range &r, V const &val ); }}
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; } using boost::algorithm; one_of ( c, isOdd ) --> false one_of ( c.begin (), c.end (), lessThan10 ) --> false one_of ( c.begin () + 3, c.end (), lessThan10 ) --> true one_of ( c.end (), c.end (), isOdd ) --> false // empty range one_of_equal ( c, 3 ) --> true one_of_equal ( c.begin (), c.begin () + 3, 3 ) --> false one_of_equal ( c.begin (), c.begin (), 99 ) --> false // empty range
one_of
and one_of_equal
work on all iterators except
output iterators.
All of the variants of one_of
and one_of_equal
run in
O(N) (linear) time; that is, they compare against
each element in the list once. If more than one of the elements in the
sequence satisfy the condition, then algorithm will return false immediately,
without examining the remaining members of the sequence.
All of the variants of one_of
and one_of_equal
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.
one_of
and one_of_equal
both return false for
empty ranges, no matter what is passed to test against.
one_of_equal
is a template parameter, rather than deduced from the first parameter
(std::iterator_traits<InputIterator>::value_type
) because that allows more
flexibility for callers, and takes advantage of built-in comparisons
for the type that is pointed to by the iterator. The function is defined
to return true if, for one element in the sequence, the expression
*iter
== val
evaluates to true (where iter
is an iterator to each element in the sequence)
The header file <boost/algorithm/cxx11/is_sorted.hpp>
contains functions for determining
if a sequence is ordered.
The function is_sorted(sequence)
determines whether or not a sequence is
completely sorted according so some criteria. If no comparison predicate
is specified, then std::less
is used (i.e, the test is to see if the sequence is non-decreasing)
namespace boost { namespace algorithm { template <typename ForwardIterator, typename Pred> bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ); template <typename ForwardIterator> bool is_sorted ( ForwardIterator first, ForwardIterator last ); template <typename Range, typename Pred> bool is_sorted ( const Range &r, Pred p ); template <typename Range> bool is_sorted ( const Range &r ); }}
Iterator requirements: The is_sorted
functions will work forward iterators or better.
If distance(first, last) < 2
, then
is_sorted (
first,
last )
returns last
. Otherwise,
it returns the last iterator i in [first,last] for which the range [first,i)
is sorted.
In short, it returns the element in the sequence that is "out of order".
If the entire sequence is sorted (according to the predicate), then it
will return last
.
namespace boost { namespace algorithm { template <typename ForwardIterator, typename Pred> FI is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ); template <typename ForwardIterator> ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last ); template <typename Range, typename Pred> typename boost::range_iterator<const R>::type is_sorted_until ( const Range &r, Pred p ); template <typename Range> typename boost::range_iterator<const R>::type is_sorted_until ( const Range &r ); }}
Iterator requirements: The is_sorted_until
functions will work on forward iterators or better. Since they have to
return a place in the input sequence, input iterators will not suffice.
Complexity: is_sorted_until
will make at most N-1 calls to the predicate (given
a sequence of length N).
Examples:
Given the sequence { 1, 2,
3, 4, 5, 3 }
,
is_sorted_until (
beg,
end,
std::less<int>())
would return an iterator pointing at the second 3
.
Given the sequence { 1, 2,
3, 4, 5, 9 }
,
is_sorted_until (
beg,
end,
std::less<int>())
would return end
.
There are also a set of "wrapper functions" for is_ordered which make it easy to see if an entire sequence is ordered. These functions return a boolean indicating success or failure rather than an iterator to where the out of order items were found.
To test if a sequence is increasing (each element at least as large as the preceding one):
namespace boost { namespace algorithm { template <typename Iterator> bool is_increasing ( Iterator first, Iterator last ); template <typename R> bool is_increasing ( const R &range ); }}
To test if a sequence is decreasing (each element no larger than the preceding one):
namespace boost { namespace algorithm { template <typename ForwardIterator> bool is_decreasing ( ForwardIterator first, ForwardIterator last ); template <typename R> bool is_decreasing ( const R &range ); }}
To test if a sequence is strictly increasing (each element larger than the preceding one):
namespace boost { namespace algorithm { template <typename ForwardIterator> bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last ); template <typename R> bool is_strictly_increasing ( const R &range ); }}
To test if a sequence is strictly decreasing (each element smaller than the preceding one):
namespace boost { namespace algorithm { template <typename ForwardIterator> bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ); template <typename R> bool is_strictly_decreasing ( const R &range ); }}
Complexity: Each of these calls is just a thin wrapper over is_sorted
, so they have the same complexity
as is_sorted
.
is_sorted
and is_sorted_until
are part of the C++11 standard. When compiled using a C++11 implementation,
the implementation from the standard library will be used.
is_sorted
and is_sorted_until
both return true
for empty ranges and ranges of length one.
The header file 'is_partitioned.hpp' contains two variants of a single
algorithm, is_partitioned
.
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
takes a sequence and a predicate. It returns true if the sequence is partitioned
according to the predicate.
is_partitioned
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
returns true if the items in the sequence are separated according to their
ability to satisfy the predicate. There are two versions; one takes two
iterators, and the other takes a range.
template<typename InputIterator, typename Predicate> bool is_partitioned ( InputIterator first, InputIterator last, Predicate p ); template<typename Range, typename Predicate> bool is_partitioned ( 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 ( c, isOdd ) --> false is_partitioned ( c, lessThan10 ) --> true is_partitioned ( c.begin (), c.end (), lessThan10 ) --> true is_partitioned ( c.begin (), c.begin () + 3, lessThan10 ) --> true is_partitioned ( c.end (), c.end (), isOdd ) --> true // empty range
is_partitioned
works on
all iterators except output iterators.
Both of the variants of is_partitioned
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
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
is also available as part of the C++11 standard.
is_partitioned
returns
true for empty and single-element ranges, no matter what predicate
is passed to test against.
The header file 'is_permutation.hpp' contains six variants of a single
algorithm, is_permutation
.
The algorithm tests to see if one sequence is a permutation of a second
one; in other words, it contains all the same members, possibly in a different
order.
The routine is_permutation
takes two sequences and an (optional) predicate. It returns true if the
two sequences contain the same members. If it is passed a predicate, it
uses the predicate to compare the elements of the sequence to see if they
are the same.
is_permutation
come in
three forms. The first one takes two iterators to define the first range,
and the starting iterator of the second range. The second form takes a
two iterators to define the first range and two more to define the second
range. The third form takes a single range parameter, and uses Boost.Range
to traverse it.
The function is_permutation
returns true if the two input sequences contain the same elements. There
are six versions; two take three iterators, two take four iterators, and
the other two take two ranges.
In general, you should prefer the four iterator versions over the three
iterator ones. The three iterator version has to "create" the
fourth iterator internally by calling std::advance(first2, std::distance(first1,last1))
, and if the second sequence is shorter
than the first, that's undefined behavior.
template< class ForwardIterator1, class ForwardIterator2 > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 ); template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate p ); template< class ForwardIterator1, class ForwardIterator2 > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ); template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate p ); template <typename Range, typename ForwardIterator> bool is_permutation ( const Range &r, ForwardIterator first2 ); template <typename Range, typename ForwardIterator, typename BinaryPredicate> bool is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred );
Given the container c1
containing { 0, 1,
2, 3, 14, 15 }
,
and c2
containing { 15,
14, 3, 1, 2 }
,
then
is_permutation ( c1.begin(), c1.end (), c2.begin(), c2.end ()) --> false is_permutation ( c1.begin() + 1, c1.end (), c2.begin(), c2.end ()) --> true is_permutation ( c1.end (), c1.end (), c2.end(), c2.end ()) --> true // all empty ranges are permutations of each other
is_permutation
works on
forward iterators or better.
All of the variants of is_permutation
run in O(N^2) (quadratic) time; that is, they compare
against each element in the list (potentially) N times. If passed random-access
iterators, is_permutation
can return quickly if the sequences are different sizes.
All of the variants of is_permutation
take their parameters by value, and do not depend upon any global state.
Therefore, all the routines in this file provide the strong exception guarantee.
is_permutation
are also available as part of the C++11 standard.
is_permutation
are part of the proposed C++14 standard. When C++14 standard libraries
become available, the implementation should be changed to use the implementation
from the standard library (if available).
is_permutation
returns
true when passed a pair of empty ranges, no matter what predicate is
passed to test with.
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.
partition_copy
Copy a subset of a sequence to a new sequence