C++ 标准库中的确定性

Question

std::sort不保证稳定

它是否保证是确定性的？

例如，这段代码是否总是打印 1？

struct S
{
    int a, b;
};

bool cmp(const S& lhs, const S& rhs)
{
    return lhs.a < rhs.a;
}

int main()
{
    std::vector<S> seq1 = {{1, 2}, {1, 3}};
    std::vector<S> seq2 = seq1;
    std::sort(seq1.begin(), seq1.end(), cmp);
    std::sort(seq2.begin(), seq2.end(), cmp);
    std::cout << (seq1.back().b == seq2.back().b) << '\n';
}

此外，C++ 标准库是否通常具有确定性（除了明显不确定的元素，如 RNG 和时钟）？

Answer 1

使用 std::sort 对范围进行排序后，对范围的唯一要求是根据提供的谓词对元素进行排序。因此，如果存在多个可能的有效排序，那么只要生成其中任何一个，该实现就是符合要求的。

每次在同一范围上调用 std::sort 时，允许实现生成不同的顺序。它还可以在每次执行程序时生成不同的顺序。

这是 std::sort 上的 requirements。请注意，没有提及任何结果范围每次都相同的要求，因此不能保证结果是确定的。

C++ 标准库中的确定性

Determinism in C++ standard library

c++

stl

deterministic