Reliably using doubles as std::map keys

问题:

One of my coworkers recently brought up an interesting trick to reliably use floating point numbers as keys in something like a std::map in C++.

Assuming you want to case on some floating point value (like price), and you know that these values can only take on discrete values despite representing real numbers (say, at intervals of a certain ticksize), then the following code snippet reliably converts an input price to a long long price key:

double price, ticksize; // Initialized elsewhere
long long priceKey = 0;

if ((price / ticksize) < (ticksize / 2)) {
    priceKey = (long long) (price / ticksize);
} else {
    priceKey = (long long) ((price / ticksize) + (ticksize / 2));
}

For example, if price = 98.05 and ticksize = 0.05, then we end up with the following result:

price / ticksize = 1960.9999999999998
ticksize / 2 = 0.025
priceKey = (long long) 1960.9999999999998 + 0.025 = 1961

priceKey could then go on to be used in something like a std::map<long long, order_t> to reliably retrieve orders at a particular price level.

Is there any case where such logic would fail? I tried working out a proof for myself of why this could work, but I don't think I have enough experience with floating point arithmetic to reason it out.

回答1:

First, you shouldn't divide by ticksize, you should multiply by the inverse of ticksize, which likely would be exactly representable as double considering the application you describe. This inverse would be 20.0 in your example.

Second, you can make the transformation slightly simpler and in my opinion more readable thus:

after multiplying price by the inverse of ticksize, round from double to the nearest integer, either as a long long (function llround) or as a double (function nearbyint). There is no inherent reason why you shouldn't use double as the key of std::map, as long as you use compatible hash and equality functions (the hash function should return the same hash for +0. and -0. if the equality is ==, and probably you shouldn't use NaN as key if you are using == as equality).

In code:

priceKey = llround(price * inverseticksize);