Clang编译环境下std::is_sorted连续调用结果不一致问题求助

问题现象 #

在以下Clang版本中，使用自定义插入排序对std::array排序后，连续两次调用std::is_sorted会出现第一次返回false、第二次返回true的异常行为：

• Apple clang version 15.0.0 (clang-1500.3.9.4)
• Ubuntu clang version 15.0.7
• Ubuntu clang version 18.1.3 (1ubuntu1)

编译参数为-O2 -std=c++20，同时在C11、C17标准下也能复现该问题。低优化级别（如-O0）下无此问题，GNU g++编译后表现符合预期。

若在调用std::is_sorted前打印数组内容，可见数组已正确排序，且两次std::is_sorted调用均返回true。

问题根源 #

问题出在自定义insertion_sort函数的循环逻辑中，存在未定义行为（UB）：

while(j >= begin && *j > key) {
    *(j+1) = *j;
    --j;
}

当j指向begin时，若*j > key，执行--j会让j指向begin之前的非法内存地址。此时对j >= begin的比较属于未定义行为——C++标准规定，随机访问迭代器的比较仅允许在同一容器的合法迭代器（指向元素或end()）之间进行，超出begin()之前的迭代器与合法迭代器的比较是未定义的。

Clang在-O2优化级别下会利用未定义行为进行激进优化，导致第一次std::is_sorted调用的结果异常；而第二次调用时，数组实际已处于有序状态，优化后的代码逻辑恰好返回正确结果。

解决方法 #

修改插入排序的循环逻辑，避免生成非法迭代器：

template<class T>
void insertion_sort(T begin, T end)
{
    if (begin == end) return; // 空范围直接返回
    T current = begin;
    ++current;
    while(current < end) {
        auto key = *current;
        auto j = current;
        // 从current向前遍历，避免j超出begin范围
        while (j != begin && *(j-1) > key) {
            *j = *(j-1);
            --j;
        }
        *j = key;
        current++;
    }
}

调整后的逻辑通过j != begin作为前置判断，确保不会让j指向begin之前的非法地址，彻底消除未定义行为。

验证 #

修改代码后，使用Clang -O2编译运行，两次std::is_sorted调用均会返回true，与GCC的表现一致。

内容的提问来源于stack exchange，提问作者Michael Conlen