1

I came across the old question on is_sorted here: std::is_sorted and strictly less comparison?

after stumbling upon a use case where monotonicity check using a comparator of pairs failed the tests. I thought giving the lambda as below was in line with the requirements: it would return true (only if) both elements of lhs and rhs were sorted

bool 
check_pair_sorted(std::vector<std::pair<int, int>>& vec)
{
    return std::is_sorted(vec.begin(), vec.end(),[](auto& lhs, auto& rhs){
            return (lhs.first < rhs.first) && (lhs.second < rhs.second);
            });
}

However, the true intended function is possible if I split the check like so

bool check_separate_sorted(std::vector<std::pair<int, int>>& vec)
{
    return std::is_sorted(vec.begin(), vec.end(),[](auto& lhs, auto& rhs){
           return (lhs.first < rhs.first) ; })
        && std::is_sorted(vec.begin(), vec.end(),[](auto& lhs, auto& rhs){ 
           return (lhs.second < rhs.second) ; });
}

Looking at the answers in the questions above, where it is suggested an early-return of false might be the preferred implementation, shouldn't the requirement also be posed likewise?

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns false if the first argument is not less than (i.e. is not ordered before) the second.

It's possible that I might be missing something in terms of ordering here, but just can't seem to wrap my head around it at the moment.

Aseem Dua
  • 193
  • 8
  • 2
    There's a good use for [`std::tie`](https://en.cppreference.com/w/cpp/utility/tuple/tie) in element-wise comparison. – Deduplicator Apr 27 '19 at 10:39

3 Answers3

3

Your check_pair_sorted is doing a different thing than check_separate_sorted and that is, I presume, the source of confusion.

It comes down to the precise wording of how std::is_sorted is defined. For every two elements a[i] and a[j] where i<j:

  • it checks that a[j] < a[i] is never true
  • it does not check that a[i] < a[j] is always true

(naturally, a clever algorithm avoids making all O(n^2) comparisons)

Those two bullets above are not the same!

For simple numbers, as in the other SO question, sequence 1 2 3 3 4 5 satisfies the first point, but it does not satisfy the latter.

Something similar happens in your case. Consider a sequence of two pairs: { {1,2}, {2,1} }. The elements of the sequence are different, but they are not comparable by your first lambda comparator - it returns false in both directions. So, for the purpose of the algorithm, those two elements are treated as equivalent, even if they are not strictly equal.

So, is_sorted inside your check_pair_sorted for the sequence { {1,2}, {2,1} } will return true, as it checks the first bullet point and not the second.

Note, that the same equivalency issue can affect other STL structures and algorithms. For example, if you have a std::set, you would not be able to have both {1,2} and {2,1} elements in it using your first lambda as a comparator.

CygnusX1
  • 20,968
  • 5
  • 65
  • 109
  • I actually figured out from the answer by paxdiablo in the linked SO question. That is_sorted is actually checking that a[j] is not less a[i] for consecutive i,j. Shouldn't the standard in that case better require a comparator that does that? My main query was that the comparator definition seems to be somehow misleading (at least I got mislead, which I addressed thanks to the tests). Shouldn't it be defined so it reflects the first bullet point and not the second? – Aseem Dua Apr 27 '19 at 11:37
  • To my knowledge, all STL uses a single kind of comparator. Introducing another one which would basically be a negation of the former seems redundant. Moreover, naming it `operator>=` (or similar) could be even more misleading, as it should read "greater-equal-or-noncomparable". – CygnusX1 Apr 27 '19 at 16:14
1

For lexical sorting you need:

return (lhs.first < rhs.first) || ((lhs.first == rhs.first) && lhs.second < rhs.second));
Paul Evans
  • 27,315
  • 3
  • 37
  • 54
  • *Why?* Can you please add an explanation of why that is needed for lexical sorting. – Some programmer dude Apr 27 '19 at 09:39
  • I kind of get what you mean here, but interestingly, one test still fails for me: cpp.sh/4o3g7 – Aseem Dua Apr 27 '19 at 09:41
  • Your third test checks that all `lhs.first`s are less then all `rhs.first`s and that all `lhs.second`s are less than all `rhs.second`s which is clearly not the case in the `nmis` vector you test. You probably meant to test the `mib` vector. – Ted Lyngmo Apr 27 '19 at 09:57
  • @TedLyngmo, mib (monotonic in both) is definitely what should pass and does even with my comparator without lexical checks. I expect both other vectors nmif and nmis (non-monotonic in first/second) to fail, i.e. return 0 (which would be a test pass) and it happens only for the _separate_ comparator. Considering the logical || I'd expect the _lexical_ to work as the _separate_ but it doesn't in the non-monotonic in second (nmis) vector – Aseem Dua Apr 27 '19 at 10:07
  • I'm not sure I followed. Can you change all tests to display `true` when they pass? [cpp.sh/33gkq](http://cpp.sh/33gkq) – Ted Lyngmo Apr 27 '19 at 10:33
  • @TedLyngmo, Here you go cpp.sh/75fay. I tried to make it verbose enough. Also I added a level of complication to the story with a version of the comparator that worked as I'd like. Of course I still feel that the comparator requirement doesn't reflect what the algorithm tries to achieve. Or al least, it's not very explicit. – Aseem Dua Apr 27 '19 at 11:53
  • @AseemDua I'm not sure I understand it either, but I added some debug prints that might help: [cpp.sh/9u4bn](http://cpp.sh/9u4bn). The last test should return true and not false though. – Ted Lyngmo Apr 27 '19 at 15:07
1

std::is_sorted is clearly defined in terms of comparison function - operator<() or some functional object - lambda in TS`s example.

However, if the comparison function is constructed in such a way, that 2 elements don't have clear relation - i.e. both a < b and b < a are true - then the result of any sorting or ordering operation can not be fully defined.

This is the real source of confusion.

Vlad Bespalov
  • 21
  • 2
  • I think another way to put it is that the Comparator must obey a _strict total ordering_ which means that for all distinct a,b, either a – Aseem Dua May 01 '19 at 08:08
  • Well, but if a=b and b>=a true, which in turn means that elements are equivalent (a == b). – Vlad Bespalov May 02 '19 at 01:37