Optimisation for finding floating key in c++ map

Question

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?

Answer 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.

Answer 2

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.