Когда безопасно сравнивать парные числа, используя стандартные & lt; на карте / сортировать?
Возможный дубликат:
Ключи с плавающей точкой в std: map
Я знаю, что есть случаи, когда вы хотите предоставить специальную функцию для сравнения пар. Такие случаи могут включать случаи, когда вы выполняете арифметические операции, потому что вы получаете округление в арифметике с плавающей запятой.
Однако бывают ли случаи, когда это безопасно использовать < или> сравнивать двойники?
Допустим, у меня есть список парных чисел, которые рассчитываются один раз, которые мне нужно отсортировать или использовать в качестве ключа на карте (т. Е. Std :: map), и я гарантирую, что после этого не будет никаких дополнительных арифметических операций.
Могу ли я гарантировать, что мой порядок сортировки будет правильным, если я переберу коллекцию, используя итераторы?
Я думаю, что таким образом я смогу добиться большей производительности.
Решение
Это всегда безопасно для использования < сравнивать double значения в std::mapДо тех пор, пока вы никогда не добавите какие-либо значения NaN. Сравнение, используемое для карты, должно быть строгий слабый порядок, который имеет эти требования (C ++ 03 §23.1.2 / 2 и §25.3 / 3-4):
- определять
equiv(a, b)как!(a < b) && !(b < a), Тогда оба<а такжеequivдолжны быть переходные отношения:- Если
a < bа такжеb < c, затемa < cдолжно быть правдой - Если
equiv(a, b)а такжеequiv(b, c), затемequiv(a, c)должно быть правдой
- Если
double значения сравнения, безусловно, удовлетворяют этим аксиомам, Кроме когда значения NaN выбрасываются в смесь. NaN обладают странным свойством, что они неравны всем значениям (включая их самих!), Но не меньше или больше чем что-либо еще:
NaN < 0 // false
NaN <= 0 // false
NaN == 0 // false
NaN > 0 // false
NaN >= 0 // false
NaN != 0 // true
NaN < NaN // false
NaN <= NaN // false
NaN == NaN // false (!!!)
NaN > NaN // false
NaN >= NaN // false
NaN != NaN // true (!!!)
Это вызывает проблемы, потому что по правилам выше, NaN имеет свойство, которое equiv(x, NaN) верно для всех x, что под транзитивностью подразумевает, что все значения эквивалентны, за исключением того, что не-NaN значения явно не эквивалентны.
Другие решения
Да, использовать стандарт operator< в наборе или карте. Самый нечеткий double компараторы не являются достаточно строгими для использования в map или же set, (И надеюсь, что вы не возитесь с режимами с плавающей запятой при доступе к указанной карте …)
Я бы посоветовал использовать multimap или же multisetпотому что два значения, которые вы считаете равными, могут немного отличаться. Если вы уже ожидаете нескольких записей, вы должны обрабатывать почти одинаковые записи намного лучше.
Далее при поиске хит делаю lower_bound(x - epsilon) а также upper_bound(x + epsilon) чтобы поймать записи на карте, которые находятся не там, где вы думаете.
То есть вот это double в этом multiset<double>«код:
typedef std::multiset<double> double_set;
std::pair< double_set::iterator, double_set::iterator >
get_equal_range( double_set& s, double d, double epsilon = 0.00001 )
{
auto lower = s.lower_bound( d-epsilon );
auto upper = s.upper_bound( d+epsilon );
return std::make_pair( lower, upper );
}
std::pair< double_set::const_iterator, double_set::const_iterator >
get_equal_range( double_set const& s, double d, double epsilon = 0.00001 )
{
auto lower = s.lower_bound( d-epsilon );
auto upper = s.upper_bound( d+epsilon );
return std::make_pair( lower, upper );
}
bool TestMembership( double_set const& s, double d, double epsilon = 0.00001 )
{
auto range = get_equal_range( s, d, epsilon );
return range.first != range.second;
}
Итак, данный double может отображаться на диапазон записей или иметь более 1 попадания в set,
Украдено из отличного ответа ниже: двойной по умолчанию operator< прикрутит map или же set вверх, если вы пройдете NaN в.
Когда кладешь вещи в map а также set (и несколько версий), вы должен поддерживать строгие правила слабого порядка. Если вы потерпите неудачу, вы получите, казалось бы, случайные сбои и случайный бесконечный цикл: код в map а также set не устойчив к ошибкам при заказе.
Используя стандарт<‘в карте или наборе жизненно важно, потому что любой фактор выдумки, который вы пытаетесь ввести, разрушит строгий порядок, который они используют для организации контейнера. К сожалению, это означает, что у вас могут возникнуть проблемы с поиском элемента, если у вас нет точного значения.
Ты можешь использовать lower_bound а также upper_bound со значениями чуть ниже и выше желаемого значения поиска, чтобы получить диапазон, в котором значение должно быть.
detector