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

Answer 3

You seem to be assuming that it's checking (for the positive case) if element N is less than element N+1 for all elements bar the last. That would indeed not work with just <, though you can use a 'trick' to evaluate <= with < and !: the following two are equivalent:

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

However, it's far more likely that it detects (the negative case) if element N is less than element N-1 for all but the first so that it can stop as soon as it finds a violation. That can be done with nothing more than <, something like (pseudocode):

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