Сортировка/сравнение удвоений в C (++) нестабильна?

Question

Я столкнулся с довольно странной проблемой с удвоениями. У меня есть список чисел с плавающей запятой (double), которые сортируются в порядке убывания. Позже в моей программе я обнаружил, что они больше не сортируются. Например:

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() возвращает двойной. В списке нет 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) 

Answer 2

Вы сравнивая возвращаемое значение функции. Возврат с плавающей запятой значения возвращаются в регистре с плавающей запятой, который имеет более высокую точность , чем двойную. При сравнении двух таких значений (например, a.Pt() > b.Pt()) компилятор вызовет одну из функций, сохранит значение в неназванном временном типе double (таким образом округляя результаты до double), затем вызовите другую функцию и сравните ее результаты (все еще находятся в регистре с плавающей запятой и не округлены до double) с сохраненным значением. Это означает, что вы можете получить случаях, где a.Pt() > b.Pt() и b.Pt() > a.Pt(), или a.Pt() > a.Pt(). Который приведет к тому, что sort будет немного запутанным. (Формально, если мы говорим о std::sort здесь, это приводит к неопределенному поведению, и я слышал о случаях, когда это было причина сердцевины дампа.)

С другой стороны, вы говорите, что Pt() «просто возвращает двойное поле». Если Pt() не вычисляет то, что когда-либо; если это только:

double Pt() const { return someDouble; } 

, то это не должно быть проблемой (при условии, someDouble имеет тип double). Увеличенная точность может представляет собой все возможные двойные значения .