◐ Shell
clean mode source ↗

std::is_sorted — cppreference.com

Материал из cppreference.com

Объявление

<tbody> </tbody>

Определено в заголовочном файле <algorithm>

template< class ForwardIt > bool is_sorted( ForwardIt first, ForwardIt last );

 (1) (начиная с C++11)
(constexpr начиная с C++20)

template< class ExecutionPolicy, class ForwardIt > bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );

 (2) (начиная с C++17)

template< class ForwardIt, class Compare > bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );

 (3) (начиная с C++11)
(constexpr начиная с C++20)

template< class ExecutionPolicy, class ForwardIt, class Compare > bool is_sorted( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, Compare comp );

 (4) (начиная с C++17)

Описание

Проверяет, отсортированы ли элементы диапазона [first, last) в неубывающем порядке.

1) Проверяет отсортированность с помощью operator< (до C++20)std::less{} (начиная с C++20).

3) Соответствует (1), но для сравнения значений элементов диапазона используется comp.

2,4) Соответствуют (1,3), но исполнение управляется политикой policy.

Эти перегрузки не участвуют в разрешении перегрузки, если только

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> не равно true.

(до C++20)

std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> не равно true.

(начиная с C++20)

Параметры

[first, last) — два итератора задающих диапазон элементов для проверки
policy — используемая политика выполнения. Подробнее смотрите политика выполнения.
comp — функциональный объект сравнения (то есть объект, который соответствует требованиям Compare), который возвращает ​true, если первый аргумент меньше чем (т.е. упорядочен до) второй.

Сигнатура функции сравнения должна быть эквивалентна следующему:

bool cmp(const Type1& a, const Type2& b);

Хотя сигнатура не обязательно должна иметь const&, функция не должна изменять переданные ей объекты и должна иметь возможность принимать все значения типа (возможно, const) Type1 и Type2 независимо от категории значения (таким образом, Type1& не допускается, равно как и Type1 если только для Type1 перемещение эквивалентно копированию (начиная с C++11)).
Типы Type1 и Type2 должны быть таковы, что объект типа ForwardIt может быть разыменован и затем неявно преобразован в оба из них. ​

Требования к типам
-ForwardIt должен соответствовать требованиям LegacyForwardIterator.
-Compare должен соответствовать требованиям Compare.

Возвращаемое значение

true если элементы диапазона отсортированы в неубывающем порядке,
false в противном случае.

Предусловия

Постусловия

(нет)

Исключения

Перегрузки с параметром шаблона по имени ExecutionPolicy сообщают об ошибках следующим образом:

  • Если выполнение функции, вызванной как часть алгоритма, вызывает исключение и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любой другой ExecutionPolicy поведение определяется реализацией.
  • Если алгоритму не удаётся выделить память, генерируется std::bad_alloc.

Сложность

Пусть N это std::distance(first, last) тогда: O(N) сравнений.

Заметки

std::is_sorted Возвращает true для диапазона длины 0 и\или 1 не выполняя сравнений значений элементов диапазона.

Возможная реализация

См. также реализации в libstdc++ и libc++.

is_sorted (1) 
template<class ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last)
{
    return std::is_sorted_until(first, last) == last;
}
is_sorted (3) 
template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp)
{
    return std::is_sorted_until(first, last, comp) == last;
}

Пример

#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <vector>

int main()
{
    std::vector<int> v;
    assert(std::is_sorted(v.cbegin(), v.cend()) && "an empty range is always sorted");
    v.push_back(42);
    assert(std::is_sorted(v.cbegin(), v.cend()) && "a range of size 1 is always sorted");

    int data[] = {3, 1, 4, 1, 5};
    assert(not std::is_sorted(std::begin(data), std::end(data)));

    std::sort(std::begin(data), std::end(data));
    assert(std::is_sorted(std::begin(data), std::end(data)));
    assert(not std::is_sorted(std::begin(data), std::end(data), std::greater<>{}));
}

См. также