| Home | Libraries | People | FAQ | More

## C++11 Algorithms

### all_of

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 routine `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.
- The second parameter to `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)

### any_of

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 routine `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.
- The second parameter to `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)

### none_of

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 routine `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.
- The second parameter to `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)

### one_of

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

- `one_of` and `one_of_equal` both return false for empty ranges, no matter what is passed to test against.
- The second parameter to `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)

### is_sorted

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 routines `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.

### is_partitioned

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 iterator-based version of the routine `is_partitioned` is also available as part of the C++11 standard.
- `is_partitioned` returns true for empty ranges, no matter what predicate is passed to test against.

### is_permutation

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 three iterator versions of the routine `is_permutation` are also available as part of the C++11 standard.
- The four iterator versions of the routine `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.

### partition_point

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

- The iterator-based version of the routine `partition_point` is also available as part of the C++11 standard.
- For empty ranges, the partition point is the end of the range.