更改排序时是否属于未定义行为？

Question

假设有以下情景：

std::atomic<int>  values[10];
std::size_t      indices[10];

void sort() {
    std::iota(indices, indices+10, 0);

    std::sort(indices, indices+10,
        [&](size_t lhs, size_t rhs) { return values[lhs] < values[rhs]; });
}

在运行sort()时，另一个线程正在更改values。这只会导致索引在排序后不正确，还是实际上是未定义的行为？

- Benno

---

快速排序可能依赖于扫描过程中存在比枢轴小和大的元素这一事实。如果打破了这个属性，算法可能会失控。 - user1196549

我不确定。本能地，我会把这样的行为归类为“疯狂”。 - Martin James

Martin James：在这个例子中，它看起来很显眼，因为所有不相关的细节都被删除了。一个更微妙的用例是对共享指针的使用计数进行排序。 - Benno

Answer 1

可能（见下文）这是未定义的行为；实际上，我曾经看到过仅仅因为不正确（即未引起全序关系）的比较器，甚至是超出容器边界访问而导致的崩溃，而且在排序时更改索引并使用 < 确实无法引起全序关系。

有趣的是，标准没有明确提到关于此问题的未定义行为；C++11 §5.4 ¶3 只是说明：

“对于除了 25.4.3 中描述的算法之外的算法，comp 必须在值上引起严格弱序关系才能正常工作。”

我在那里四处寻找“正常工作”的正式定义，但没有看到；即使整个第 25 章（描述 <algorithm>）中也从未提到“未定义”一词。

- Matteo Italia

---

只是为了抛砖引玉，难道崩溃也不可能是由于标准库错误地实现了C++标准所导致的吗？ - Benno

@Benno：事实上，我正在标准中查找一个引用。 - Matteo Italia

这可能不是一个明确的命令，但我认为由于标准没有定义应该发生什么，因此这使得它成为未定义行为。 - Puppy

那个措辞最近的 LWG 问题已经被修改为“必须”要求，我非常确定库介绍中有全局措辞会将违反此类要求视作未定义行为。 - T.C.

Answer 2

std::sort需要满足严格弱序规则的排序器。 (在这个答案中有解释)

如果同时更改内容，则此顺序可能无法保持，从而导致未定义的行为。(可能会导致排序器进入无限循环、崩溃、索引排序不正确(如您所述)、索引正确排序、2个月球或其他情况)

- Mohit Jain