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?

[Effective STL](http://www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629) by Scott Meyers, Item 19: "Understand the difference between equivalence and equality" — TemplateRex, Jul 21 '13 at 11:02

score 12 · Accepted Answer · answered Jul 21 '13 at 05:00

12

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.

answered Jul 21 '13 at 05:00

awesoon

32,469
11
74
99

Ok, it makes sense now, even if it is counter-intuitive for me. – Vincent Jul 21 '13 at 05:04
@Vincent, It was counter intuitive for me too until I looked in the Standard :) – awesoon Jul 21 '13 at 05:07
1

i feel like if I had a standard quote in all my answers my rep would be way higher – aaronman Jul 21 '13 at 05:08
@aaronman When the standard is as clear as this, I think there is no better answer than that. – Vincent Jul 21 '13 at 05:09
@Vincent I would just like to point out that paxdiablos answer had this first, I edited mine after, he was saying the same thing without a standards quote – aaronman Jul 21 '13 at 05:11
@aaronman, The point is: only the Standard determines the behavior in all cases. – awesoon Jul 21 '13 at 05:17
my only point is that @Vincent argued that behavior that paxdiablo and I assumed it was using was not how it was behaving, but when he sees it in the standard he automatically agrees with it – aaronman Jul 21 '13 at 05:22

aaronman · Answer 2 · 2013-07-21T18:39:45.337

4

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

edited Jul 21 '13 at 18:39

answered Jul 21 '13 at 04:44

aaronman

18,343
7
63
78

I know that, but I think that `std::is_sorted` would return `true` if the provided condition was `true` for all `(N, N+1)` element and that is not the case. – Vincent Jul 21 '13 at 04:51
@Vincent not following could you elaborate – aaronman Jul 21 '13 at 04:52
if I pass the comparator `std::less`, the comparison will return : `true` for `(1, 2)`, `true` for `(2, 3)` but `false` for `(3, 3)`, so I thought that the algorithm stops here (first `false` detected) and return `false`. But that's not the case. – Vincent Jul 21 '13 at 04:56
[Effective STL](http://www.amazon.com/Effective-STL-Specific-Standard-Template/dp/0201749629) by Scott Meyers, Item 19: "Understand the difference between equivalence and equality" In particular `!(a < b) && !(b < a)` does not mean `a == b` but only that `a` and `b` are [equivalent](http://en.wikipedia.org/wiki/Equivalence_relation). For builtin types these notions coincide but not necessarily for class types. Equivalence is useful for partitioning (e.g. the `std::multiset` container and `std::partition` algorithm) – TemplateRex Jul 21 '13 at 11:51
@TemplateRex So what does that imply, just that the two objects are not necessarily exactly the same but just a equivalent – aaronman Jul 21 '13 at 15:48
consider a class with 2 strings, first and last name. if you sort by last name only, then equivalence means 2 objects have equal last names, and equality means that they are equal on first name as well. – TemplateRex Jul 21 '13 at 16:10
@TemplateRex yeah thats how i understand it, its a bit nit picky then who would assume that made 2 objects exactly the same – aaronman Jul 21 '13 at 16:29
1

The subtle difference between equality and equivalence is the difference between e.g. `stable_sort` and `sort`. It is not nitpicking at all (unless you consider Scott Meyers to write [nitpicking books](http://stackoverflow.com/q/388242/819272))! I have to downvote your answer as it stands, but if you change it to reflect these concepts, I would upvote it. – TemplateRex Jul 21 '13 at 18:32
@templaterex edited, just to be clear i understood your point – aaronman Jul 21 '13 at 18:41

paxdiablo · Answer 3 · 2013-07-21T11:16:59.507

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

std::is_sorted and strictly less comparison?

3 Answers3

Linked