Weird behavior of std::is_sorted

Question

I'm learning assertions in c++, and I came across weird behaviour of std::is_sorted.

Given a comparator(c), and unsorted vector(v) of std::strings. I use std::sort(v.begin(),v.end(),comparator). and then call std::is_sorted with the same arguments. And the outcome is false, why so ?

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <cassert>
int main(){
    auto comparator([](std::string a , std::string b) {return a.length() - b.length();} );
    std::vector<std::string> v {"y" , "yyyy" , "yy" ,
                                 "yy" , "yyyyyyy" , "yyy"};
    assert(false == std::is_sorted(v.begin() , v.end(),comparator));
    std::sort(v.begin(), v.end(),comparator);
    assert(true == std::is_sorted(v.begin() , v.end(),comparator));
}

Answer 1

Your predicate is not working properly. If you intend to sort by string length, you need

auto comparator([](std::string a , std::string b) {return a.length() < b.length();} );

The original predicate you posted returns the string length difference, which is of integral type and can be converted to bool when invoked by std::sort, and does result in true for everything different than 0, false otherwise. Hence, every non-equal string lengths result in the predicate being evaluated to true, and sequence elements with different string length would be infinitely swapped due to the predicate being "true" all the time. This results in undefined behavior.

The terminology here is that the predicate must implement a "strict weak ordering", which is documented e.g. on cppreference. Thanks to @FrançoisAndrieux and @Peter for the comments with this regard.

Also consider passing the arguments by const std::string& or std::string_view to avoid unnecessary copies.