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) == equal(b, c) == true 但 equiv(a, c) == false。