std::is_sorted and strictly less comparison?

Question

I do not understand well the std::is_sorted algorithm and its default behaviour. If we look to cppreference, it says that by default std::is_sorted uses the < operator. Instead of that, I find that using <= would be natural. But my problem is that for the following list of numbers :

1 2 3 3 4 5

it will return true, even if 3 < 3 should be false. How is that possible ?

EDIT: its seems to be worse than what I thought, because passing std::less_equal<int> will return false in that case... What is the condition applied when I pass a comparator function?

Answer 1

Per 25.4/5:

A sequence is sorted with respect to a comparator comp if for any iterator i pointing to the sequence and any non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, comp(*(i + n), *i) == false.

So, for

1 2 3 3 4 5

std::less<int>()(*(i + n), *i) will return false for all n, while std::less_equal will return true for case 3 3.

Answer 2

Even if you only have the < operator you can figure out if two numbers are equivalent not necessarily equal.

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

In addition, as paxdiablo's solution actually mentioned first, you could implement is_sorted as going up the list and continually checking for < not to be true, if it is ever true you stop.

Here is the correct behavior of the function from 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;
}