3 ms·
> Yes. There is nothing about floats that should make them unusable in a set. Strictly speaking, there is. The < operator for floating-point types does not imp
by Sharlin 10y ago
> Yes. There is nothing about floats that should make them unusable in a set.
Strictly speaking, there is. The < operator for floating-point types does not impose a strict weak order because NaNs are a thing.
In any case, comparing floating-point values for strict equality (instead of using an appropriate epsilon) is more often a bad idea than not.
- temac 10y agoWell the thing is, it should not fail because of obscure reasons completely unrelated to NaNs...
- Someone 10y agoBut std::set doesn't use operator< for comparing values, but !(a<b) && !(b<a). http://www.cplusplus.com/reference/set/set http://www.cplusplus.com/reference/set/set: "Compare A binary predicate that takes two arguments of the same type as the elements and returns a bool. The expression comp(a,b), where comp is an object of this type and a and b are key values, shall return true if a is considered to go before b in the strict weak ordering the function defines. The set object uses this expression to determine both the order the elements follow in the container and whether two element keys are equivalent (by comparing them reflexively: they are equivalent if !comp(a,b) && !comp(b,a)). No two elements in a set container can be equivalent. This can be a function pointer or a function object (see constructor for an example). This defaults to less<T>, which returns the same as applying the less-than operator (a<b)." I think that guarantees that std::set works for IEEE floating point values, and that NaNs are at the end of the set.
- Sharlin 10y agoA strict weak order partitions a set of values into a collection of equivalence classes. Two values belong to different equivalence classes if and only if a<b or b<a. If either a or b is NaN, that condition is always false. Thus, every NaN is equivalent to every other value (regardless of the fact that no NaN is equal to any other value!) However, any equivalence relation must be transitive, that is, if a≡b and b≡c then a≡c. Let a=1, c=2, and b=(any)NaN. We now have 1≡NaN and 2≡Nan which implies that 1≡2 which is clearly false. Thus, the < operator for floating-point types is not a strict weak order in the presence of NaNs.
- DannyBee 10y ago"I think that guarantees that std::set works for IEEE floating point values, and that NaNs are at the end of the set. " No, this is, by definition, not a strict weak order because it's not transitive. It also doesn't have transitivity of equivalence. It's at best partial ordering. "strict weak" order is, by the way, such an incredibly stupid name it's hard to know where to begin (it's what they call it in math, but it doesn't make it any more sensible) It's much easier to understand in terms of the invariants. Partial orders: f(x, x) must be false. f(x, y) implies !f(y, x) f(x, y) and f(y, z) imply f(x, z). Strict weak ordering: All of the above plus Define equivalence as f(x, y) and f(y, x) being both false. Then if x equivalent to y, and y equivalent to z, then x must be equivalent to z. IE for all x, y, z: if f(x, y) and f(y, x) are both false, and f(y, z) and f(z,y) are both false, then f(x,z) and f(z, x) must both be false. It's strict because it's not reflexive, and it's weak because b < a && a < b does not imply a == b. It just implies they are "equivalent", and as mentioned, you get a total ordering on the equivalence classes.
- kobeya 10y agoIt's also a credulous bug that a standard ordering isn't defined for NaNs.
- brucedawson 10y agoSo, you want to redefine IEEE floats? 'cause it says that there is no ordering for NaNs. And if you do redefine IEEE floats, where do NaNs go, and why is that better?
- kobeya 10y agoI'm saying IEEE shouldn't have defined them that way, yes. It was an arbitrary choice. As to where, before negative infinity or after positive infinity; I don't really care which. But the fact that we can't have good things (e.g. a standards compliant std::set<float>) because of a standards committee punted on making that choice makes me sad :(
- Sharlin 10y agoI do wonder why they didn't special-case std::less for floats. They already did it for pointers - operator< for pointers isn't even defined, much less a strict weak order, if the operands do not point to the same object (region of storage). This is in order to facilitate non-flat addressing schemes. std::less, however, is explicitly specified to work with any pair of pointers.