CODEWITHSUNDEEP
c++algorithmsortingcompareassert
XYZCODE123
XYZCODE123

Reputation: 372

Weird behavior of std::is_sorted

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

Upvotes: 2

Views: 768

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 311126

According to the C++ Standard (28.7 Sorting and related operations)

2 Compare is a function object type (23.14). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool (Clause 7), yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

This lambda expression

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

always returns (contextually converted value) true if lengths of two strings are unequal.

So for this vector

std::vector<std::string> v {"y" , "yyyy" , "yy" ,
                             "yy" , "yyyyyyy" , "yyy"};

the lambda-expression returns false for adjacent elements "yy" and "yy" at position 2 and 3.

If for example you will place an intermediate value between positions 2 and 3 as for example

std::vector<std::string> v {"y" , "yyyy" , "yy" , "y",
                             "yy" , "yyyyyyy" , "yyy"};

then the first assertion 

assert(false == std::is_sorted(v.begin() , v.end(),comparator));

fails.

Thus you need correctly to define the comparison function. For example

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

Also the parameters of the lambda expression should be constant references.

Take into account that if your compiler supports C++ 17 then you could also rewrite the lambda expression the following way

auto comparator( []( const std::string &a , const std::string &b ) 
                 {
                     return std::size( a ) < std::size( b ); 
                 } );

Upvotes: 3

lubgr
lubgr

Reputation: 38325

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.

Upvotes: 7

Related Questions