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++标准库通常是确定性的吗？

- Phastasm

---

我不相信标准保证这种确定性。据我所知，它对此问题保持沉默，因此实现不需要是确定性的。 - Igor Tandetnik

事实上，对于核心语言，它明确表示相反的意思（可能是在一个非规范性的注释中；我太懒了，不想查）- 在像 f() + g() 这样的表达式中，两个函数调用的顺序是未指定的，并且在两次计算此表达式之间不必相同。 - Igor Tandetnik

没有这样的保证。使用stable_sort可以更安全。 - rustyx

可能的不稳定性原因之一是如果线程在地下使用。 - Jarod42

Answer 1

使用 std::sort 排序后的范围唯一要求是元素按照提供的谓词进行排序。如果有多个有效的排序方式，则只要实现中生成了其中任意一个，则符合标准。

每次在相同的范围上调用 std::sort，实现可以生成不同的排序顺序。程序每次执行时也可以生成不同的排序顺序。

这里是关于 std::sort 的要求。注意没有提到结果必须每次相同的要求，因此不能保证结果是确定性的。

- cigien

---

请提供源连接，我会接受这个答案。 - Phastasm

@Phastasm 我已经链接到标准页面。没有特定的措辞表明它是“非确定性的”，但我认为这可以从缺乏保证它是“确定性的”中推断出来。 - cigien

除此之外，如果需要更多的话，还有 stable_sort。 - SoronelHaetir

@SoronelHaetir 稳定性和确定性并不相同，有些情况可能只需要确定性，比如问题中的代码。 - Phastasm

@SoronelHaetir 这并不能证明排序是非确定性的。虽然在没有稳定性的情况下保证确定性可能会相当奇怪，但正如Phastasm所指出的那样，这是可能的。 - cigien