3

I asked me how the cmp function in std::sort and std::is_sorted is defined.

here are two documentations for is_sorted_until how say it should be operator< :

en.cppreference.com cplusplus.com

But i think there should be a problem with equal elements. The list {1,1,1} should not be sorted because 1<1==false. But there is an example which says:

...
int *sorted_end = std::is_sorted_until(nums, nums + N);
...

1 1 4 9 5 3 : 4 initial sorted elements

but that should return 1 if < is used like documented.

It would work with <=, but that is not the way it is documented.

I'm really confused.

15r10nk
  • 41
  • 1
  • 3
  • 1
    "but that should return 1 if < is used like documented." no, why should it? – juanchopanza Aug 21 '13 at 12:02
  • You might find this question and answers informative in addition to the thousands of results from google: [Operator < and Strict Weak Ordering](http://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering) – WhozCraig Aug 21 '13 at 12:03
  • because 1<1==false. so {1,1} is not sorted and {1} would be the largest sorted list. – 15r10nk Aug 21 '13 at 12:19
  • A list is considered sorted if `sort(list.begin(), list.end())` would not change it. Sorting `{1,1}` does not change it, ergo it is already sorted. – MSalters Aug 21 '13 at 13:18

4 Answers4

6

The comparison is required to define a strict weak ordering. A strict weak ordering defines a set of equivalence classes from the incomparability relation, i.e., if x < y is false, and y < x is false too (i.e. x and y cannot be compared with <), x and y are considered equivalent. These equivalence classes have a total order, and that's the total order resulting from the sort functions.

In the example given, {1,1,1} has only a single equivalence class, the one composed of {1,1,1}.

is_sorted_until finds the first element x[i] for which x[i] < x[i-1] is true.

R. Martinho Fernandes
  • 228,013
  • 71
  • 433
  • 510
2

To be exact, it's neither < nor <=, it is defaulted to std::less. That one in turn calls < for most types, except where it is specialized. For example, < for pointers does not generally give a strict ordering, while std::less does.

Arne Mertz
  • 24,171
  • 3
  • 51
  • 90
  • `<` for pointers does not give a strict ordering **unless** the pointers point to objects in the same array or one-past-the-end. – Pete Becker Aug 21 '13 at 13:25
  • thanks, added a "*generally*" for that part (imo for the example the exact circumstances are not of much interest, only the fact that strict ordering is not always given) – Arne Mertz Aug 21 '13 at 13:34
  • Either way, algorithms are specified in terms of `operator<`, not `std::less` ($25.4[alg.sorting]/1) – Cubbi Aug 21 '13 at 14:52
2

It does indeed use operator< unless you provide a custom comparison. But the definition of "sorted" is not a[n] < a[n+1] (which we might call "strictly sorted"), but !(a[n+1] < a[n]); so equal elements are considered sorted. This is equivalent to using <=, but (in common with all other standard algorithms) doesn't require that operator to be defined.

In general, all ordered comparisons must define a "strict weak ordering". "Strict" means that the comparison must be false for equivalent objects; so < is valid, while <= is not.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • Is it really `std::less`? 25.4/1 says `All the operations in 25.4 have two versions: one that takes a function object of type Compare and one that uses an operator<.` – Cubbi Aug 21 '13 at 13:12
  • @Cubbi: You're right; I was assuming it would be the same as the ordered containers, but the algorithms do indeed specify `operator<`. – Mike Seymour Aug 21 '13 at 14:48
0

If you look at the example implementation, < is used for checking if the next element is less than the previous one:

if (*next < *first)
    return next;

If it is, then the order is broken, and the function returns. I. e. the logic is reversed - the algorithm does not terminate if the next element is equal to the previous.