C++ std:map 中的浮点键

Floating point keys in std:map

提问by pokey909

The following code is supposed to find the key 3.0in a std::mapwhich exists. But due to floating point precision it won't be found.

下面的代码应该3.0在 a 中找到std::map存在的键。但是由于浮点精度，它不会被找到。

map<double, double> mymap;
mymap[3.0] = 1.0;

double t = 0.0;
for(int i = 0; i < 31; i++)
{
  t += 0.1;
  bool contains = (mymap.count(t) > 0);
}

In the above example, containswill always be false. My current workaround is just multiply tby 0.1 instead of adding 0.1, like this:

在上面的示例中，contains将始终为false。我目前的解决方法是乘以t0.1 而不是加 0.1，如下所示：

for(int i = 0; i < 31; i++)
{
  t = 0.1 * i;
  bool contains = (mymap.count(t) > 0);
}

Now the question:

现在的问题是：

Is there a way to introduce a fuzzyCompare to the std::mapif I use doublekeys? The common solution for floating point number comparison is usually something like a-b < epsilon. But I don't see a straightforward way to do this with std::map. Do I really have to encapsulate the doubletype in a class and overwrite operator<(...)to implement this functionality?

std::map如果我使用double键，有没有办法将模糊比较引入到？浮点数比较的常见解决方案通常类似于a-b < epsilon. 但我没有看到用std::map. 我真的必须将double类型封装在一个类中并覆盖operator<(...)以实现此功能吗？

采纳答案by Naszta

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.

更新：参见Effective STL 中的第 40 条！根据建议更新。

回答by Yakk - Adam Nevraumont

So there are a few issues with using doubles as keys in a std::map.

因此，使用双打作为std::map.

First, NaN, which compares less than itself is a problem. If there is any chance of NaNbeing inserted, use this:

首先，NaN比较小于自身是一个问题。如果有任何NaN插入的机会，请使用：

struct safe_double_less {
  bool operator()(double left, double right) const {
    bool leftNaN = std::isnan(left);
    bool rightNaN = std::isnan(right);
    if (leftNaN != rightNaN)
      return leftNaN<rightNaN;
    return left<right;
  }
};

but that may be overly paranoid. Do not, I repeat do not, include an epsilon threshold in your comparison operator you pass to a std::setor the like: this will violate the ordering requirements of the container, and result in unpredictable undefined behavior.

但这可能过于偏执。不要，我再说一遍，不要在传递给 astd::set或类似的比较运算符中包含 epsilon 阈值：这将违反容器的排序要求，并导致不可预测的未定义行为。

(I placed NaNas greater than all doubles, including +inf, in my ordering, for no good reason. Less than all doubles would also work).

（我无缘无故地在我的订单中放置NaN为大于所有doubles，包括+inf。小于所有doubles 也可以工作）。

So either use the default operator<, or the above safe_double_less, or something similar.

所以要么使用 default operator<，要么使用above safe_double_less，或类似的东西。

Next, I would advise using a std::multimapor std::multiset, because you should be expecting multiple values for each lookup. You might as well make content management an everyday thing, instead of a corner case, to increase the test coverage of your code. (I would rarely recommend these containers) Plus this blocks operator[], which is not advised to be used when you are using floating point keys.

接下来，我建议使用 a std::multimapor std::multiset，因为您应该为每次查找期望多个值。您不妨让内容管理成为日常事务，而不是角落案例，以增加代码的测试覆盖率。（我很少推荐这些容器）加上这个块operator[]，当您使用浮点键时不建议使用它。

The point where you want to use an epsilon is when you query the container. Instead of using the direct interface, create a helper function like this:

您想要使用 epsilon 的地方是查询容器时。不使用直接接口，而是创建一个像这样的辅助函数：

// works on both `const` and non-`const` associative containers:
template<class Container>
auto my_equal_range( Container&& container, double target, double epsilon = 0.00001 )
-> decltype( container.equal_range(target) )
{
  auto lower = container.lower_bound( target-epsilon );
  auto upper = container.upper_bound( target+epsilon );
  return std::make_pair(lower, upper);
}

which works on both std::mapand std::set(and multiversions).

它适用于std::map和std::set（和multi版本）。

(In a more modern code base, I'd expect a range<?>object that is a better thing to return from an equal_rangefunction. But for now, I'll make it compatible with equal_range).

（在更现代的代码库中，我希望range<?>从equal_range函数返回一个更好的对象。但现在，我将使其与 兼容equal_range）。

This finds a range of things whose keys are "sufficiently close" to the one you are asking for, while the container maintains its ordering guarantees internally and doesn't execute undefined behavior.

这会找到一系列键与您要求的键“足够接近”的东西，而容器在内部维护其排序保证并且不会执行未定义的行为。

To test for existence of a key, do this:

要测试密钥是否存在，请执行以下操作：

template<typename Container>
bool key_exists( Container const& container, double target, double epsilon = 0.00001 ) {
  auto range = my_equal_range(container, target, epsilon);
  return range.first != range.second;
}

and if you want to delete/replace entries, you should deal with the possibility that there might be more than one entry hit.

如果您想删除/替换条目，您应该处理可能有多个条目命中的可能性。

The shorter answer is "don't use floating point values as keys for std::setand std::map", because it is a bit of a hassle.

简短的回答是“不要使用浮点值作为std::set和std::map”的键，因为这有点麻烦。

If you do use floating point keys for std::setor std::map, almost certainly neverdo a .findor a []on them, as that is highly highly likely to be a source of bugs. You can use it for an automatically sorted collection of stuff, so long as exact order doesn't matter (ie, that one particular 1.0 is ahead or behind or exactly on the same spot as another 1.0). Even then, I'd go with a multimap/multiset, as relying on collisions or lack thereof is not something I'd rely upon.

如果您确实为std::setor使用浮点键std::map，几乎肯定不会对它们执行 a.find或 a []，因为这极有可能是错误的来源。您可以将它用于自动排序的东西集合，只要确切的顺序无关紧要（即，一个特定的 1.0 领先或落后或与另一个 1.0 完全相同）。即便如此，我还是会使用 multimap/multiset，因为我不依赖于碰撞或缺乏碰撞。

Reasoning about the exact value of IEEE floating point values is difficult, and fragility of code relying on it is common.

推理 IEEE 浮点值的确切值很困难，依赖它的代码的脆弱性很常见。

回答by Evgeni Sergeev

Here's a simplified example of how using soft-compare (aka epsilon or almost equal) can lead to problems.

这是一个简化的示例，说明使用软比较（又名 epsilon 或几乎相等）如何导致问题。

Let epsilon = 2for simplicity. Put 1and 4into your map. It now might look like this:

让我们epsilon = 2为简单起见。将1和4放入您的map. 现在可能看起来像这样：

1
 \
  4

So 1is the tree root.

1树根也是如此。

Now put in the numbers 2, 3, 4in that order. Each will replace the root, because it compares equal to it. So then you have

现在，摆在数2，3，4的顺序。每个都将替换根，因为它比较等于它。那么你有

4
 \
  4

which is already broken. (Assume no attempt to rebalance the tree is made.) We can keep going with 5, 6, 7:

这已经坏了。（假设没有尝试重新平衡树。）我们可以继续使用5, 6, 7：

7
 \
  4

and this is even more broken, because now if we ask whether 4is in there, it will say "no", and if we ask for an iterator for values less than 7, it won't include 4.

这甚至更糟糕，因为现在如果我们问是否4在那里，它会说“不”，如果我们要求迭代器的值小于7，它不会包含4。

Though I must say that I've used maps based on this flawed fuzzy compare operator numerous times in the past, and whenever I digged up a bug, it was never due to this. This is because datasets in my application areas never actually amount to stress-testing this problem.

尽管我必须说我过去曾map多次使用基于这个有缺陷的模糊比较运算符的 s，而且每当我发现一个错误时，都不是由于这个原因。这是因为我的应用程序领域中的数据集实际上从未构成对这个问题的压力测试。

回答by Mark Ransom

As Naszta says, you can implement your own comparison function. What he leaves out is the key to making it work - you must make sure that the function alwaysreturns falsefor any values that are within your tolerance for equivalence.

正如Naszta 所说，您可以实现自己的比较功能。他遗漏的是使其工作的关键 - 您必须确保该函数始终返回false在您的等价容差范围内的任何值。

return (abs(left - right) > epsilon) && (left < right);

Edit: as pointed out in many comments to this answer and others, there is a possibility for this to turn out badly if the values you feed it are arbitrarily distributed, because you can't guarantee that !(a<b)and !(b<c)results in !(a<c). This would not be a problem in the question as asked, because the numbers in question are clustered around 0.1 increments; as long as your epsilon is large enough to account for allpossible rounding errors but is less than 0.05, it will be reliable. It is vitally important that the keys to the map are never closer than 2*epsilon apart.

编辑：正如对此答案和其他人的许多评论所指出的那样，如果您提供给它的值是任意分布的，则可能会出现严重后果，因为您无法保证!(a<b)并!(b<c)导致!(a<c). 这在所问的问题中不会成为问题，因为所讨论的数字聚集在 0.1 增量附近；只要您的 epsilon 大到足以解释所有可能的舍入误差但小于 0.05，它就是可靠的。至关重要的是，地图的键之间的距离永远不会小于 2*epsilon。

回答by Jiri Kriz

Using doubles as keys is not useful. As soon as you make any arithmetic on the keys you are not sure what exact values they have and hence cannot use them for indexing the map. The only sensible usage would be that the keys are constant.

使用双打作为键是没有用的。一旦您对键进行任何算术运算，您就不确定它们具有什么确切值，因此无法使用它们来索引地图。唯一合理的用法是键是不变的。