c++ - 在偏序上使用 min_element

Question

可以std::min_element (还有 std::sort 和来自 <algorithm> 的类似函数)用于仅具有偏序的类型？

例如:

auto it = std::min_element(vec.cbegin(), vec.cend(), [](const node* a, const node* b) {
    return a->precedes(*b);
});

在这里node表示 DAG(有向无环图)中的节点，a.precedes(b)测试它 a是b的祖先.但是如果a和 b在不同的分支上，它也返回 false , 在这种情况下 a.precedes(b) == b.precedes(a) == false .

Answer 1

根据 §25.4/3(强调和脚注是我的):

For algorithms other than those described in 25.4.3^* to work correctly, comp^** has to induce a strict weak ordering on the values.

_{^* 25.4.3 是二进制搜索算法的部分。
^** comp 是自定义比较器。}

由于 std::sort 是在 25.4.1 中定义的，而 std::min_element 是在 25.4.7 中定义的，那么你只需要一个严格的弱排序 关于值(value)观，即:

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

(4.1) — comp(a, b) && comp(b, c) implies comp(a, c)

(4.2) — equiv(a, b) && equiv(b, c) implies equiv(a, c)

据我了解你的关系，它不符合 equiv 要求，因为你可能有两个节点 !comp(a, b) && !comp(b, a) 但 a != b。通常，如果您在一个分支上有 a 和 c 而在另一个分支上有 b，则以上内容将不起作用，因为 equiv( a, b) == equiv(b, c) == true 但是 equiv(a, c) == false。