446,205 Members | 1,075 Online Need help? Post your question and get tips & solutions from a community of 446,205 IT Pros & Developers. It's quick & easy.

# using a float as the index in an STL map?

 P: n/a Hi, It seems that using floats as the first tupelo for an STL map (shown below) can cause problems but I don't remember what the problems were. Is it common practice to use a structure like below? I would appreciate if you can share your experience using such a structure. Thanks. std::map
23 Replies

 P: n/a JDT wrote: It seems that using floats as the first tupelo for an STL map (shown below) can cause problems but I don't remember what the problems were. The only thing I can think of is that if you expect two different results of a calculation to lead to the same number (and ultimately to the same stored in the map value), you may be in for a surprise. Due to rounding errors in the FPU the mathematically equivalent calculations can lead to different numbers internally. Example, given that 'a' is 1.f and 'b' is 2.f, the expressions (a + 2.f/3) and (b - 1.f/3) _can_ give you different results. Is it common practice to use a structure like below? I would appreciate if you can share your experience using such a structure. Thanks. std::map

 P: n/a Victor Bazarov wrote: Example, given that 'a' is 1.f and 'b' is 2.f, the expressions (a + 2.f/3) and (b - 1.f/3) _can_ give you different results. Concrete example: double d1 = 1.0; double d2 = 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1; std::cout << d1 << " " << d2 << " " << (d1 == d2) << std::endl; That prints (at least in a regular PC): 1 1 0 Printing the doubles with more decimal places would show the difference. It's very small, but it's there, thus (d1 == d2) is false. Apr 20 '07 #3

 P: n/a Victor Bazarov wrote: JDT wrote: >>It seems that using floats as the first tupelo for an STL map (shownbelow) can cause problems but I don't remember what the problems were. The only thing I can think of is that if you expect two different results of a calculation to lead to the same number (and ultimately to the same stored in the map value), you may be in for a surprise. Due to rounding errors in the FPU the mathematically equivalent calculations can lead to different numbers internally. Example, given that 'a' is 1.f and 'b' is 2.f, the expressions (a + 2.f/3) and (b - 1.f/3) _can_ give you different results. >>Is it common practice to use a structure like below? I wouldappreciate if you can share your experience using such a structure.Thanks.std::map

 P: n/a JDT wrote: Victor Bazarov wrote: >JDT wrote: >>It seems that using floats as the first tupelo for an STL map (shownbelow) can cause problems but I don't remember what the problemswere. The only thing I can think of is that if you expect two differentresults of a calculation to lead to the same number (and ultimatelyto the same stored in the map value), you may be in for a surprise.Due to rounding errors in the FPU the mathematically equivalentcalculations can lead to different numbers internally.Example, given that 'a' is 1.f and 'b' is 2.f, the expressions(a + 2.f/3) and (b - 1.f/3) _can_ give you different results. >>Is it common practice to use a structure like below? I wouldappreciate if you can share your experience using such a structure.Thanks.std::map

 P: n/a On 20 Apr, 22:33, "Victor Bazarov" . Regards, Zeppe Apr 20 '07 #6

 P: n/a On Apr 21, 12:36 am, zeppethef...@gmail.com wrote: On 20 Apr, 22:33, "Victor Bazarov"

 P: n/a On Fri, 20 Apr 2007 19:52:01 +0000, JDT wrote: Hi, It seems that using floats as the first tupelo for an STL map (shown below) can cause problems but I don't remember what the problems were. Is it common practice to use a structure like below? I would appreciate if you can share your experience using such a structure. Thanks. std::map

 P: n/a On Apr 21, 12:12 am, JDT

 P: n/a James Kanze wrote: On Apr 21, 12:36 am, zeppethef...@gmail.com wrote: >I think a good alternative would be to manually define the comparisonoperator "less" considering that the equality >(a == b) >on a map is given by >!less(a,b) && !less(b,a) >it should be sufficient to write less() as something like >less(a, b){ if (a - b threshold) return false; else return true;} >with threshold a proper small number. That's a nice way to get undefined behavior. Since such a function doesn't define an ordering relationship (which must be transitive), it doesn't meet the requirements for std::map or std::set. On the other hand, assuming a reasonable threshold (EPSILON), what's wrong with: less(float a, float b) { if (fabs(a - b) EPSILON) // difference big enough to be return a < b; // significant else return false; // elements are "equal" } Apr 21 '07 #10

 P: n/a On Apr 21, 4:07 am, red floyd

 P: n/a On Apr 21, 3:07 am, red floyd

 P: n/a On Apr 21, 1:43 am, kostas

 P: n/a On Apr 21, 1:31 am, Rae Westwood wrote: On Fri, 20 Apr 2007 19:52:01 +0000, JDT wrote: It seems that using floats as the first tupelo for an STL map (shown below) can cause problems but I don't remember what the problems were. Is it common practice to use a structure like below? I would appreciate if you can share your experience using such a structure. Thanks. std::map

 P: n/a On Apr 21, 1:02 pm, James Kanze

 P: n/a James Kanze wrote: That's a nice way to get undefined behavior. Since such a function doesn't define an ordering relationship (which must be transitive), it doesn't meet the requirements for std::map or std::set. oh gosh, my bad! :) Regards, Zeppe Apr 21 '07 #16

 P: n/a On Apr 21, 2:56 pm, kostas

 P: n/a Maybe just use a class which represents fractions and use that instead of floats Apr 22 '07 #18

 P: n/a On Apr 22, 12:02 pm, James Kanze

 P: n/a On Apr 21, 2:51 am, James Kanze I think a good alternative would be to manually define the comparison >operator "less" considering that the equality >(a == b) >on a map is given by >!less(a,b) && !less(b,a) >it should be sufficient to write less() as something like >less(a, b){ > if (a - b threshold) > return false; > else > return true; >} >with threshold a proper small number. That's a nice way to get undefined behavior. Since such a function doesn't define an ordering relationship (which must be transitive), it doesn't meet the requirements for std::map or std::set. On the other hand, assuming a reasonable threshold (EPSILON), what's wrong with: less(float a, float b) { if (fabs(a - b) EPSILON) // difference big enough to be return a < b; // significant else return false; // elements are "equal" } What have you changed? You still haven't defined a strict ordering relationship, so you have undefined behavior. There is no undefined behavior. The less() function does produce a total ordering: For any a, b, and c such that less(a, b) returns true and less(b, c) returns true, then it is the case that less( a, c) also returns true. Greg Apr 23 '07 #20

 P: n/a * Greg Herlihy: On Apr 21, 2:51 am, James Kanze On Apr 21, 3:07 am, red floyd >James Kanze wrote:On Apr 21, 12:36 am, zeppethef...@gmail.com wrote:I think a good alternative would be to manually define the comparisonoperator "less" considering that the equality(a == b)on a map is given by!less(a,b) && !less(b,a)it should be sufficient to write less() as something likeless(a, b){ if (a - b threshold) return false; else return true;}with threshold a proper small number.That's a nice way to get undefined behavior. Since such afunction doesn't define an ordering relationship (which must betransitive), it doesn't meet the requirements for std::map orstd::set.On the other hand, assuming a reasonable threshold (EPSILON), what'swrong with:less(float a, float b){ if (fabs(a - b) EPSILON) // difference big enough to be return a < b; // significant else return false; // elements are "equal"} What have you changed? You still haven't defined a strictordering relationship, so you have undefined behavior. There is no undefined behavior. The less() function does produce a total ordering: For any a, b, and c such that less(a, b) returns true and less(b, c) returns true, then it is the case that less( a, c) also returns true. For a std::map the 'less' operation must define a strict weak ordering. "Strict" means that !(a op a) holds for all a. This is true of the 'less' above. Exactly what "weak" means I'm not sure, but the standard's requirement (in §25.3/4) is that 'less' should define an equivalence relation, via bool eq(a,b) { return !less(a,b) && !less(b,a); } which must be transitive, eq(a,b) && eq(b,c) implies eq(a,c) This requirement is not met for the 'less' above. You can have (a,b) such that their difference is less than EPSILON, and (b,c) such that their difference is less than EPSILON, but such that the difference for (a,c) is greater than EPSILON. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Apr 23 '07 #21

 P: n/a On Apr 23, 4:37 am, Greg Herlihy

 P: n/a On Apr 21, 3:07 am, red floyd 1.0 + <2>0.04 + <2>0.04, can be both <1>1.0 and <1>1.1 depending on the binding order of the + operator losing it's associativity :-(. Has anyone come up with a all situations solution for float like numbers? I find myself writing custom code very often in that corner.... Bas Apr 23 '07 #23

 P: n/a On Apr 23, 9:00 pm, Colander I think a good alternative would be to manually define the comparison >operator "less" considering that the equality >(a == b) >on a map is given by >!less(a,b) && !less(b,a) >it should be sufficient to write less() as something like >less(a, b){ > if (a - b threshold) > return false; > else > return true; >} >with threshold a proper small number. That's a nice way to get undefined behavior. Since such a function doesn't define an ordering relationship (which must be transitive), it doesn't meet the requirements for std::map or std::set. On the other hand, assuming a reasonable threshold (EPSILON), what's wrong with: less(float a, float b) { if (fabs(a - b) EPSILON) // difference big enough to be return a < b; // significant else return false; // elements are "equal" } What's wrong is that EPSILON is relative to a and b. What's wrong is that it doesn't define a "strict weak ordering", as defined in and required by the standard. Using a relative epsilon won't change that. -- James Kanze (GABI Software) email:ja*********@gmail.com Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 Apr 24 '07 #24

### This discussion thread is closed

Replies have been disabled for this discussion. 