C(++)中双打的排序/比较不稳定？

Question

我遇到了一个非常奇怪的双打问题.我有一个浮点数(双)列表,按降序排序.后来在我的程序中,我发现它们不再完全排序了.例如:

0.65801139819
0.6545651031    <-- a
0.65456513001   <-- b
0.64422968678

中间的两个数字被翻转.有人可能会认为这个问题存在于数字的表示中,而且它们只是打印错了.但是我使用我用来对它们进行排序的相同运算符将每个数字与前一个数字进行比较 - 没有转换为基数10或类似情况:

double last_pt = 0;
for (int i = 0; i < npoints; i++) {
  if (last_pt && last_pt < track[i]->Pt()) {
    cout << "ERROR: new value " << track[i]->Pt()
         << " is higher than previous value " << last_pt << endl;
  }
  last_pt = track[i]->Pt();
}

在排序期间比较值

bool moreThan(const Track& a, const Track& b) {
  return a.Pt() > b.Pt();
}

我确保它们总是加倍,而不是转换成浮点数.Pt()返回一个double.列表中没有NaN,排序后我不会触摸列表.

为什么这些,这些数字有什么问题,以及(如何)我可以对这些数字进行排序,以便它们保持排序状态？

Answer 1

你确定你不是转换double到float在一段时间吗？让我们看看这两个数字的二进制表示:

0 01111111110 0100111100100011001010000011110111010101101100010101
0 01111111110 0100111100100011001010010010010011111101011010001001

在double我们有1位符号,11位指数和53位尾数,而在float那里有1位符号,8位指数和23位尾数.请注意,两个数字中的尾数在前23位是相同的.

根据舍入方法,会有不同的行为.如果仅修整位> 23,则这两个数字float相同:

0 011111110 01001111001000110010100 (trim: 00011110111010101101100010101)
0 011111110 01001111001000110010100 (trim: 10010010011111101011010001001)