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

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

1 2 3 3 4 5

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

EDIT: он кажется хуже, чем я думал, потому что передача std::less_equal<int> вернет false в этом случае... Какое условие применяется при передаче функции компаратора?

Ответ 1

В 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.

Ответ 2

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

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

Ответ 3

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

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