What will std::sort do if the comparison is inconsistent? (A<B, B<C, C<A)

Question

I need to sort a file list by date. There's this answer how to do it. It worries me though: it operates on a live filesystem that can change during operation.

The comparison function uses:

struct FileNameModificationDateComparator{
    //Returns true if and only if lhs < rhs
    bool operator() (const std::string& lhs, const std::string& rhs){
        struct stat attribLhs;
        struct stat attribRhs;  //File attribute structs
        stat( lhs.c_str(), &attribLhs);
        stat( rhs.c_str(), &attribRhs); //Get file stats                        
        return attribLhs.st_mtime < attribRhs.st_mtime; //Compare last modification dates
    }
};

From what I understand, this function can, and will be called multiple times against the same file, comparing it against different files. The file can be modified by external processes while sort is running; one of older files can become the newest in between two comparisons and turn up older than a rather old file, and later newer than one of newest files...

What will std::sort() do? I'm fine with some scarce ordering errors in the result. I'm not fine with a crash or a freeze (infinite loop) or other such unpleasantries. Am I safe?

Answer 1

As other answers have already said, handing std::sort a comparator that doesn't satisfy the weak strict ordering requirement and is preserved when called multiple times with the same value will cause undefined behavior.

That doesn't only mean that the range may end up not correctly sorted, it may actually cause more serious problems, not only in theory, but also in practice. A common one is as you already said infinite loops in the algorithm, but it can also introduce crashes or vulnerabilities.

For example (I haven't checked whether other implementations behave similarly) I looked at libstdc++'s std::sort implementation, which as part of introsort uses insertion sort. The insertion sort calls a function __unguarded_linear_insert, see github mirror. This function performs a linear search on a range via the comparator without guarding for the end of the range, because the caller is supposed to have already verified that the searched item will fall into the range. If the result of the comparison changes between the guard comparison in the caller and the unguarded linear search, the iterator will be incremented out-of-bounds, which could produce a heap overrun or null dereference or anything else depending on the iterator type.

Demonstration see https://godbolt.org/z/8qajYEad7.