在部分订单上使用 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 在不同的分支上，它也会 returns false，在这种情况下 a.precedes(b) == b.precedes(a) == false.

Answer 1

来自 C++11 标准 § 23.2.1:

a < b convertible to bool. lexicographical_-compare(a.begin(), a.end(), b.begin(), b.end()) pre[condition]: < is defined for values of T. < is a total ordering relationship.

所以，不，那行不通。

Answer 2

根据 §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 中定义的，那么您只需要对值进行 严格的弱排序 , 即:

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.

在部分订单上使用 min_element

using min_element on partial order

c++

graph

stl-algorithm