Заголовок файла <boost/algorithm/cxx11/is_sorted.hpp> содержит функции для определения последовательности заказа.

is_sorted

Функция is_sorted(sequence) определяет, полностью ли последовательность сортируется по некоторым критериям. Если не указан какой-либо предикат сравнения, то используется std::less_equal (т.е. тест состоит в том, чтобы увидеть, если последовательность не выясняется)

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

Требования к итератору: is_sorted функции будут работать вперед итераторов или лучше.

is_sorted_until

Если расстояние(первая, последняя) < 2, то is_sorted (первая, последняя><17 возврат> последняя>>>>. В противном случае он возвращает последний итератор i в [первый, последний], для которого сортируется диапазон [первый, i].

Короче говоря, он возвращает элемент в последовательности, который является «неправильным». Если вся последовательность отсортирована (по предикату), то она вернет 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 );
}}

Требования к итераторам: is_sorted_until функции будут работать над передними итераторами или лучше. Поскольку они должны вернуть место в последовательности ввода, итераторов ввода будет недостаточно.

Сложность: is_sorted_until будет делать максимум N-1 звонки на предикат (учитывая последовательность длины N).

Примеры:

Учитывая последовательность { 1, 2, 3>, 2>2>>>>>>>2>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.

Учитывая последовательность { 1, 2, 3>, 4>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.

Существует также набор «функций взлома» для is_ordered, которые позволяют легко увидеть, заказывается ли вся последовательность. Эти функции возвращают булеан, указывающий на успех или неудачу, а не на итератор, где были найдены предметы из-под заказа.

Проверить, увеличивается ли последовательность (каждый элемент, по крайней мере, такой же большой, как предыдущий):

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

Проверить, уменьшается ли последовательность (каждый элемент не больше предыдущего):

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

Чтобы проверить, если последовательность строго увеличивается (каждый элемент больше предыдущего):

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

Чтобы проверить, если последовательность строго уменьшается (каждый элемент меньше предыдущего):

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

Сложность: каждый из этих вызовов - это всего лишь тонкая обертка над is_sorted, поэтому они имеют ту же сложность, что и is_sorted.

Notes