std :: is_sorted и строго меньше сравнения?

Question

std :: is_sorted и строго меньше сравнения?

Я не очень хорошо понимаю std::is_sorted алгоритм и его поведение по умолчанию. Если мы посмотрим на cppreference, это говорит о том, что по умолчанию std::is_sorted использует < оператор. Вместо этого я нахожу, что используя <= было бы естественно. Но моя проблема в том, что для следующего списка номеров:

1 2 3 3 4 5

это вернется true, даже если 3 < 3 должно быть false, Как это возможно?

РЕДАКТИРОВАТЬ: кажется, хуже, чем я думал, потому что мимоходом std::less_equal<int> в этом случае вернет false … Какое условие применяется, когда я передаю функцию сравнения?

11

c++c++11 comparator sorting stl-algorithm

Решение

Другие решения

Даже если у вас есть только < Оператор вы можете выяснить, если два числа эквивалентны не обязательно равны.

if !(first < second) and !(second < first) then first equivalent to second

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

Вот правильное поведение функции от cplusplus.com

template <class ForwardIterator>
bool is_sorted (ForwardIterator first, ForwardIterator last)
{
if (first==last) return true;
ForwardIterator next = first;
while (++next!=last) {
if (*next<*first)     // or, if (comp(*next,*first)) for version (2)
return false;
++first;
}
return true;
}

4

Вы, кажется, предполагаете, что он проверяет (для положительного случая), является ли элемент N меньше элемента N + 1 для всех элементов, кроме последнего. Это действительно не будет работать только с <хотя вы можете использовать «трюк» для оценки <= с < а также !: следующие два эквивалентны:

if (a <= b)
if ((a < b) || (!((b < a) || (a < b)))) // no attempt at simplification.

Однако гораздо более вероятно, что он обнаружит (отрицательный случай), если элемент N меньше, чем элемент N-1 для всех, кроме первого, так что он может остановиться, как только обнаружит нарушение. Тот Можно быть сделано только с чем <что-то вроде (псевдокод):

for i = 1 to len - 1:
if elem[i] < elem[i-1]:
return false
return true

2

Источник

Accepted Answer

По 25,4 / 5:

Последовательность отсортирована относительно компаратора comp если для любого
итератор i указывая на последовательность и любое неотрицательное целое число n
такой, что i + n является действительным итератором, указывающим на элемент
последовательность, comp(*(i + n), *i) == false.

Таким образом, для

1 2 3 3 4 5

std::less<int>()(*(i + n), *i) вернусь false для всех n, в то время как std::less_equal вернусь true на случай 3 3,

10