algorithm - 多个 double 的字典顺序

Question

考虑一类 double 类型

class path_cost {
   double length;
   double time;
};

如果我想按字典顺序排列 path_costs 的列表， 我有个问题。继续阅读:)

如果我像这样使用完全相等的相等性测试

bool operator<(const path_cost& rhs) const {
   if (length == rhs.length) return time < rhs.time;
   return length < rhs.length;
}

得到的顺序很可能是错误的，因为一个小的偏差(例如由于计算长度的数值不准确)可能会导致长度测试失败，以至于例如

{ 231.00000000000001, 40 } < { 231.00000000000002, 10 }

错误地持有。

如果我选择使用这样的公差

bool operator<(const path_cost& rhs) const {
   if (std::fabs(length-rhs.length)<1-e6)) return time < rhs.time;
   return length < rhs.length;
}

那么排序算法可能会严重失败，因为 <-operator 不再具有传递性(也就是说，如果 a < b 和 b < c 那么 a < c 可能不成立)

有什么想法吗？解决方案？我考虑过对实线进行分区，以便每个分区内的数字被认为是相等的，但这仍然留下太多相等性测试失败但不应该失败的情况。

(James Curran 更新，希望能解释问题): 给定数字:

• A = {231.0000001200, 10}
• B = {231.0000000500, 40}

• C = {231.0000000100, 60}

  • A.Length 和 B.Length 相差 7-e7，所以我们使用时间，A < B.
  • B.Length 和 C.Length 相差 4-e7，所以我们使用时间，B < C.
  • A.Length 和 C.Length 相差 1.1-e6，所以我们使用长度，并且 A > C。

(Esben Mose Hansen 更新) 这不仅仅是理论上的。当给定非传递排序运算符时，标准排序算法往往会崩溃或更糟。这正是我一直在争论的问题(男孩调试起来很有趣；))

Answer 1

你真的只想要一个比较函数吗？

你为什么不先按长度排序，然后将这些对分组到你认为长度相同的地方，然后在每个组内按时间排序？

按长度排序后，您可以应用所需的任何启发式方法来确定长度的“相等性”，以进行分组。