CODEWITHSUNDEEP
c++std
Aseem Dua
Aseem Dua

Reputation: 193

std::is_sorted and the comparator requirement misleading?

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.

Upvotes: 1

Views: 713

Answers (3)

Vlad Bespalov
Vlad Bespalov

Reputation: 21

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.

Upvotes: 1

CygnusX1
CygnusX1

Reputation: 21818

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.

Upvotes: 3

Paul Evans
Paul Evans

Reputation: 27577

For lexical sorting you need:

return (lhs.first < rhs.first) || ((lhs.first == rhs.first) && lhs.second < rhs.second));

Upvotes: 1

Related Questions