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.

interface

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 );
}}

Examples

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

Iterator Requirements

all_of and all_of_equal work on all iterators except output iterators.

Complexity

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.

Exception Safety

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.

Notes

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.

interface

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 );
}}

Examples

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

Iterator Requirements

any_of and any_of_equal work on all iterators except output iterators.

Complexity

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.

Exception Safety

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.

Notes

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.

interface

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 );
}}

Examples

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

Iterator Requirements

none_of and none_of_equal work on all iterators except output iterators.

Complexity

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.

Exception Safety

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.

Notes

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.

interface

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 );
}}

Examples

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

Iterator Requirements

one_of and one_of_equal work on all iterators except output iterators.

Complexity

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.

Exception Safety

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.

Notes

The header file <boost/algorithm/cxx11/is_sorted.hpp> contains functions for determining if a sequence is ordered.

is_sorted

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

is_sorted_until

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.

Notes

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.

interface

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 );

Examples

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

Iterator Requirements

is_partitioned works on all iterators except output iterators.

Complexity

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.

Exception Safety

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.

Notes

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.

Interface

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 );

Examples

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

Iterator Requirements

is_permutation works on forward iterators or better.

Complexity

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.

Exception Safety

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.

Notes

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