如果比较不一致，std::sort 会怎么做？（A<B、B<C、C<A）

Question

我需要按日期对文件列表进行排序。有这个答案如何做到这一点。但它让我担心：它运行在一个实时文件系统上，该文件系统可以在操作过程中发生变化。

比较函数使用：

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

据我了解，这个函数可以并且将会针对同一个文件多次调用，并将其与不同的文件进行比较。在排序运行时，外部进程可以修改该文件；较旧的文件之一可能会在两次比较之间成为最新的文件，并且会比相当旧的文件更旧，并且会比最新文件之一更新......

会做什么std::sort()？我对结果中的一些罕见的排序错误感到满意。我不喜欢崩溃或冻结（无限循环）或其他类似的不愉快的事情。我安全吗？

Answer 1

我安全吗？

不。

std::sort需要与严格的弱排序进行比较，并且A<B, B<C, C<A违反了这一点。

这种违规行为会导致未定义的行为，并且在实践中，会导致一些最糟糕的未定义行为。

还应该注意的是，任何为在排序过程中任意更改顺序的元素而编写的排序算法几乎都是不可能的。算法在任何时候都不会知道整个集合当前已排序。

Answer 2

正如其他答案已经说过的那样，传递std::sort一个不满足弱严格排序要求并且在使用相同值多次调用时保留的比较器将导致未定义的行为。

这不仅意味着范围最终可能无法正确排序，它实际上可能会导致更严重的问题，不仅在理论上，而且在实践中。正如您已经说过的，一种常见的情况是算法中的无限循环，但它也可能会导致崩溃或漏洞。

例如（我没有检查其他实现是否有类似的行为）我查看了 libstdc++ 的std::sort实现，它作为 introsort 的一部分使用插入排序。插入排序调用函数__unguarded_linear_insert，参见github镜像。该函数通过比较器对范围执行线性搜索，而不保护范围的末尾，因为调用者应该已经验证搜索的项目将落入该范围。如果调用者中的保护比较与不受保护的线性搜索之间的比较结果发生变化，则迭代器将超出范围递增，这可能会产生堆溢出或空取消引用或其他任何情况，具体取决于迭代器类型。

演示参见https://godbolt.org/z/8qajYEad7。