Floating Point Keys in Std:Map

Floating point keys in std:map

You could implement own compare function.

#include <functional>

class own_double_less : public std::binary_function<double,double,bool>
{
public:
  own_double_less( double arg_ = 1e-7 ) : epsilon(arg_) {}
  bool operator()( const double &left, const double &right  ) const
  {
    // you can choose other way to make decision
    // (The original version is: return left < right;) 
    return (abs(left - right) > epsilon) && (left < right);
  }
  double epsilon;
};
// your map:
map<double,double,own_double_less> mymap;

Updated: see Item 40 in Effective STL!
Updated based on suggestions.

Reliably using doubles as std::map keys

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);

Optimisation for finding floating key in c++ map

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.

Tolerant key lookup in std::map

You can't change the ordering of the map after it's created (and you should just use plain old operator< even for the floating point type here), and you can't even use a "tolerant" comparison operator as that may vioate the required strict-weak-ordering for map to maintain its state.

However you can do the tolerant search with lower_bound and upper_bound. The gist is that you would create a wrapper function much like equal_range that does a lower_bound for "value - tolerance" and then an upper_bound for "value + tolerance" and see if it creates a non-empty range of values that match the criteria.

Alternative to floating point as key

Since std::map maintains its keys in order, using std::less, there really isn't a problem using floating-point keys provided that:

• you are only using the map to keep the keys in order; or
• you are prepared to do lookups using some strategy which is not dependent on strict key equality, such as "nearest key" (or "nearest key if close enough"), or interpolation; or
• the way you compute key values is stable, so you can rely on the computation to produce a lookup value which is present in the map.

To implement either "closest key" or "interpolated value", you'll want to find the bracketing keys; that is, largest key not greater than the search key and the smallest key not less than the search key. The second of these can be found with std::map::lower_bound, and the first is either the same key (if it's equal), the previous key, or non-existent (if the value is less than every key).

I don't see any advantage to using an integer key instead. How would you look up the integer corresponding to a floating point value without doing precisely the same computation? (And if you can guarantee that you will always be looking up values using precisely the same number as you used to store them, then floating point isn't going to cause you any grief at all.)

map with double keys C++

A std::map has no issue with using doubles as key. It uses < to compare keys and two keys are equivalent when !(a < b) && !(b < a). That's fine. The issues do arise when you expect floating point numbers to be exact when in fact they are not.

For example:

std::map<double,int> m{{0.3,0},{1.0,2},{2.0,2},{3.0,3}};
for (const auto& e : m) std::cout << e.first << " " << e.second << "\n";

Output is:

0.3 0
1 2
2 2
3 3

But now consider this:

auto it = m.find(0.1 + 0.2);
if (it == m.end()) std::cout << "not found\n";

Searching 0.1 + 0.2 will not find the key 0.3, because doubles are not exact and the output is

not found

TL;DR: Do not use floating point numbers for prices or currencies. When you need prices with cents then use int cents:

std::map<int, Stock> ordered_stocks;
for (const auto& e : ordered_stocks) {
      std::cout << "dollars: " << e.first / 100 << "\n";
      std::cout << "stock: " << e.second << "\n";
}

Are IEEE floats valid key types for std::map and std::set?

I suspect the restrictions should be taken as referring to the relation's behavior on the values actually used as keys, not necessarily on all values of the type. Don't have time at the moment to go through the standard looking for "smoking gun" language that refers to actual container elements rather than all values of the type.

Similar case: what if a comparator (for a container of pointers or smart pointers) calls a virtual function, and somebody links a derived class of the type it compares, which overrides the virtual function in a way that makes the comparator not a strict weak order? Does the program become undefined even if nobody ever actually uses that derived class?

If in doubt, you can support NaN with a comparator that is a strict weak order:

bool operator()(double a, double b) {
    if ((a == a) && (b == b)) {
        return a < b;
    }
    if ((a != a) && (b != b)) return false;
    // We have one NaN and one non-NaN.
    // Let's say NaN is less than everything
    return (a != a)
}

The last two lines "optimize" to return (b == b);, although I'm not sure the comment optimizes with it.

I think Tomalak has convinced me the language does say the whole type needs to be ordered.

This makes little sense, since a map doesn't conjure values out of nowhere, it only uses values that it's given (and copies of them), but the question is about the rules, and them's the rules as far as I know. C++0x is the same. I wonder if there's a defect report, or any point submitting one.

It's also annoying in that on (very rare) systems where std::less is slow for pointers, you can't use < as the comparator in a map of pointers, even if you know that the pointers are all to elements of the same array. Shame.

Another option is to use the following class as the key type, so keys are checked for NaN only on entry to the map, not on every comparison as above.

struct SaneDouble {
    double value;
    SaneDouble (double d) : value(d) {
        if (d != d) throw std::logic_error();
    }
    static friend bool operator<(SaneDouble lhs, SaneDouble rhs) {
        return lhs.value < rhs.value;
    }
    // possibly a conversion to double
};

This raises another question - clearly someone could create a SaneDouble and then set its value to NaN (assuming the implementation lets them get one from somewhere without crashing). So are "elements of SaneDouble" strict-weak-ordered or not? Does my half-hearted attempt to create a class invariant in the constructor make my program undefined even if nobody actually breaks the invariant, simply because they could and therefore the results of doing so are "elements of SaneDouble"? Is it really the intention of the standard that the program's behavior is defined if and only if value is marked private? Does the standard actually define anywhere what "the elements" of a type are?

I wonder whether we should interpret "elements of Key" to mean that the comparator induces a strict weak order on some elements of Key. Presumably including the ones actually used. "I have doughnuts" doesn't mean I have every doughnut. It's a stretch, though.

---

Related Topics