1

我使用标准BinaryHeap作为算法的一部分,我需要检索最大的对象(通过一些最大的定义)。两个非等价元素可能都同样大(因此它们在二进制堆中的相对顺序无关紧要) - 例如,我可能只对多字段结构的单个字段进行排序感兴趣。

因此,让我的类型实现OrdEq. PartialOrd相反,我可能应该PartialEq只实施。但是,唉,BinaryHeap要求它的元素是Ord!为什么会这样,使用BinaryHeap这种类型的最惯用的方法是什么?

(顺便说一句,在 C++ 中,在这种情况下,我会相当容易地编写自定义比较器类型,并在比较器类型上模板化优先级队列。所以我不认为我想做的在数学或算法上是错误的。)

4

1 回答 1

6

PartialOrd给你不对称和传递的顺序,即a < b蕴含!(a > b)a < b && b < c暗示a < cPartialOrd根本不需要所有元素实际上都具有有意义的排序,这就是为什么PartialOrd::partial_cmp返回Option<Ordering>whereNone表示“我不知道”的原因(请注意,这不会影响上述要求)。

然而,二叉堆需要对其元素进行全排序,因为二叉堆必须具有以下属性:“存储在每个节点中的键大于或等于 (≥) 或小于或等于 (≤)在节点的孩子中,根据一些总顺序。” (通过维基百科直接引用)。

Ord为您提供不对称、传递和总(恰好是或之一a < b)排序。对总订单的要求导致返回 a ,而不是 a ,因为-case 是不允许的。a == ba > bOrd::cmpOrderingOption<Ordering>None

如果您需要特定的行为PartialOrd,编写特定的实现并不少见。Ord还有educecrate,它允许您派生更具体的版本PartialOrd以及Ord忽略某些字段的位置。

于 2020-08-28T19:33:43.660 回答