Boost C++ Libraries

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 Iterator, typename Pred>
	bool is_sorted ( Iterator first, Iterator last, Pred p );
	
	template <typename Iterator>
	bool is_sorted ( Iterator first, Iterator 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 on all kinds of iterators (except output iterators).

is_sorted_until

The function is_sorted_until(sequence, predicate) compares each sequential pair of elements in the sequence, checking if they satisfy the predicate. it returns the first element of the sequence that does not satisfy the predicate with its' predecessor. In short, it returns the element in the sequence that is "out of order". If all adjacent pairs satisfy the predicate, then it will return one past the last element of the sequence.

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 preceeding 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 preceeding one):

namespace boost { namespace algorithm {
	template <typename Iterator>
	bool is_decreasing ( Iterator first, Iterator last );
	
	template <typename R>
	bool is_decreasing ( const R &range );
}}

To test if a sequence is strictly increasing (each element larger than the preceeding one):

namespace boost { namespace algorithm {
	template <typename Iterator>
	bool is_strictly_increasing ( Iterator first, Iterator last );
	
	template <typename R>
	bool is_strictly_increasing ( const R &range );
}}

To test if a sequence is strictly decreasing (each element smaller than the preceeding one):

namespace boost { namespace algorithm {
	template <typename Iterator>
	bool is_strictly_decreasing ( Iterator first, Iterator 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