When is it safe to compare doubles using standard < in a map/sort?

Question

Possible Duplicate:
Floating point keys in std:map

Well I know there are cases where you want to provide a special function for doing doubles comparison. Such cases could include times when you do arithmetic operations because you get rounding in the floating point arithmetic.

However are there times when it is safe to use < or > to compare doubles?

Let's say I have list of doubles that are calculated once that I need to sort or use as a key in a map (ie. std::map) and I guarantee that there aren't any additional arithmetic operations afterwards.

Can I guarantee that my sort order will be correct if I traverse the collection using iterators?

I'm thinking I can get more performance this way.

I'm confused, why wouldn't it be safe? Are you thinking of `==`? — Pubby, Nov 12 '12 at 19:28
Inequality comparisons should be fine... equality comparison is what people generally warn about. — obataku, Nov 12 '12 at 19:29
@Pubby: A map needs to know equality, so it's not safe to have floating point keys even though it's using `operator<` — Mooing Duck, Nov 12 '12 at 20:05
@MooingDuck - it's **safe** to use doubles. If you don't know how good your values are, you may well find that your results are incorrect. That's not the container's fault. — Pete Becker, Nov 12 '12 at 20:10
@oldrinb - yes, you hear warnings about testing for equality, because that's what people notice. But ordering comparisons have the same "problem": if you don't know whether you've lost or gained a bit or two you not only get surprising results for equality tests, you get surprising results for ordering tests. — Pete Becker, Nov 12 '12 at 20:12
@PeteBecker right, but the problem is generally that strict equality without some tolerance (epsilon) yields surprising results... — obataku, Nov 12 '12 at 20:15
As does <, for **exactly** the same reason. Using a tolerance is an advanced technique; it greatly complicates logic when a "equals" b and b "equals" c but a does not "equal" c. — Pete Becker, Nov 12 '12 at 20:18

score 5 · Answer 1 · answered Nov 12 '12 at 19:52

It's always safe to use < to compare double values in a std::map, as long as you never add any NaN values. The comparison used for the map must be a strict weak ordering, which has these requirements (C++03 §23.1.2/2 and §25.3/3-4):

Define equiv(a, b) as !(a < b) && !(b < a). Then, both < and equiv must be transitive relations:
1. If a < b and b < c, then a < c must be true
2. If equiv(a, b) and equiv(b, c), then equiv(a, c) must be true

double value comparisons certainly satisfy these axioms, except when NaN values are thrown into the mix. NaNs have the strange property that they are unequal to all values (including themselves!) but not less than or greater than anything:

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 (!!!)

This causes problems, because under the rules above, NaN has the property that equiv(x, NaN) is true for all x, which by transitivity implies that all values are equivalent, except non-NaN values are clearly not equivalent.

I don't understand why this answer got down-voted. It's the only one that's correct. — Pete Becker, Nov 12 '12 at 20:09
Ayep -- good answer here! So you could fix this problem by ordering everything that does not equal itself lowest? Ie, something like `struct NaNSafeLess { bool operator()(double left, double right) const { bool leftNaN = left!=left; bool rightNaN = right!=right; return (leftNaN!=rightNaN)?leftNaN — Yakk - Adam Nevraumont, Nov 12 '12 at 20:39

Yakk - Adam Nevraumont · Answer 2 · 2012-11-12T20:46:56.883

Yes, use standard operator< in a set or a map. Most fuzzy double comparators are not strict enough to be used in a map or set. (And hope to hell that you aren't messing around with floating point modes while accessing said map...)

I would advise to use multimap or multiset, because two values you think are equal might be slightly different. If you are already expecting multiple entries, you should handle almost-equal entries much better.

Next, when searching for a hit do lower_bound(x - epsilon) and upper_bound(x + epsilon) in order to catch entries in the map that aren't where you think they are.

Ie, here is "is this double in this multiset<double>" code:

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;
}

So a given double could map to a range of entries, or have more than 1 hit in the set.

Stolen from a great answer below: Default double operator< will screw your map or set up if you pass NaN in.

When putting things into map and set (and multi versions), you must maintain the strict weak ordering rules. If you fail, you will get seemingly random crashes, and the occasional infinite loop: the code in map and set is not robust against ordering failure.

You use the `lower_bound` when looking for a hit. Ie, instead of `set s; auto it = s.find( 0.7 ); if (it != end()) { ... }`, you do a `set s; auto lower = s.lower_bound( 0.7-epsilon ); auto upper = s.upper_bound( 0.7+epsilon ); if (lower != upper) { ... }` — Yakk - Adam Nevraumont, Nov 12 '12 at 20:28

score 3 · Answer 3 · answered Nov 12 '12 at 19:32

Using standard '<' in a map or set is vital, because any fudge factor you try to introduce will destroy the strict ordering they use to organize the container. Unfortunately this means that you might have trouble finding an element unless you have the exact value.

You can use lower_bound and upper_bound with values just below and above your desired search value to produce a range where the value must be.

When is it safe to compare doubles using standard < in a map/sort?

3 Answers3