2

I would like to ask a question that is related to this: Floating point keys in std:map

I make a std::map with a double as the key to some other type MyType, i.e: 

map<double,MyType> myMap;

The question I have is this: Given that myMap.find(...) is std::map's optimised way of finding keys (see How sets, multisets, maps and multimaps work internally), is the method in Floating point keys in std:map significantly unoptimised? Could I implement something more efficient?

Community
  • 1
  • 1
kd88
  • 1,054
  • 10
  • 21
  • I've always thought that using a `double` as a map key is a bad idea as they don't satisfy *strict weak ordering* due to floating point imprecision. Am I wrong? – Bathsheba Dec 11 '13 at 12:12
  • @Bathsheba the linked solution proposes the use of a double tolerance that should fix this problem. – Ivaylo Strandjev Dec 11 '13 at 12:13
  • Map keys must come with a strict weak ordering, which is not the case for `double` with the default comparator. Beware. – Kerrek SB Dec 11 '13 at 12:22
  • @KerrekSB Can you elaborate on the strict weak thing? Is this because of the "special" values, like positive and negative zero, and NaN and such, which behave oddly in comparisons? Or am I missing something wrt. "regular" floating-point values as well? – jalf Dec 11 '13 at 12:26
  • 1
    @jalf: Just NaN. NaN ruins the ordering. – Kerrek SB Dec 11 '13 at 12:44
  • Though I think you could legitimately just silently ignore NaN (or throw an exception, which is probably better). There is no meaningful way you could store NaN in a map, nor are you able to retrieve it. Insofar, it does not really matter whether it disturbs the sorting. A map can only hold one value for one key, but there exists more than just one NaN. However, since you can't compare NaN to anything, you can't distinguish them, so no matter what you do, you could only ever add a single NaN to a map (a different NaN would occupy the same value), but you would still not be able to retrieve it! – Damon Dec 11 '13 at 14:24
  • On a second thought, the same is probably true for infinity. If something is already "infinite" it makes no observable difference when it is yet a bigger than another value that is "infinite". So you could, again, store at most one +inf and one -inf key in the map, but you would never be able to retrieve it (not without "cheating", anyway), since you cannot know if any other infinite value that you compare against is the same. – Damon Dec 11 '13 at 14:34
  • For example, given this: `int main() { using dbl = std::numeric_limits; std::map m; m[dbl::max()+1.0] = 1; m[dbl::max()+1.0e20] = 2; m[dbl::max()+1.0e300] = 3; printf("%u", m[dbl::infinity()]); return 0; }` what would one expect as output, `1`, `2`, or `3`? Obviously only `3`, but `1` or `2` should be valid, retrieveable outputs too. – Damon Dec 11 '13 at 14:51

2 Answers2

1

It is not significantly unoptimized. First of all the asymptotic complexity will be the same(O(log(n))) for all operations, only comparison will be a constant factor slower. In fact I don't think you can get any better because you can not perform comparison of doubles in any better way that is safe at the same time.

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • Would it also be possible to confirm whether casting the double to a string and instead defining the map as `map myMap;` would be more or less efficient than the [proposed solution](http://stackoverflow.com/questions/6684573/floating-point-keys-in-stdmap)? I understand that string casting and string comparisons are relatively 'slow' but if the ability to use `map::find()` makes up for this then perhaps it is more efficient? – kd88 Dec 11 '13 at 13:24
  • 1
    You are still able to use map::find in the proposed solution. it will simply use a custom comparison operator, still its complexity will be as expected. Using strings on the other hand will make comparisons significantly slower(up to the length of the string representation of a double) and may make your map perform way worse. Proposed solution is already quite good don't try to improve it using such "hacky" optimizations. – Ivaylo Strandjev Dec 11 '13 at 13:27
1

STL containers are "optimized" in the sense that they meet the performance requirements defined by the standard. While one can't say they are perfect, the requirements are already pretty tight (i.e. O(log(N)) for element search in a map), so it would be a pretty ungrateful job to reimplement them. I'd say, better pick the one which best suits you and leave them as they are.

DarkWanderer
  • 8,739
  • 1
  • 25
  • 56