c++ - std :map 中的浮点键

Question

下面的代码应该可以找到 key 3.0在 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);
}

在上面的例子中，contains将永远是 false . 我目前的解决方法是乘以 t乘 0.1 而不是加 0.1，如下所示:

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

现在的问题:

有没有办法在 std::map 中引入模糊比较？如果我使用 double key ？ float 比较的常见解决方案通常类似于 a-b < epsilon .但是我看不到使用 std::map 的直接方法来做到这一点。 . 我真的必须封装double吗？输入一个类并覆盖operator<(...)实现这个功能？

Answer 1

所以在 std::map 中使用 double 作为键存在一些问题.

首先，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;
  }
};

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

(在我的订购中，我无缘无故地将 NaN 设置为大于所有 double ，包括 +inf。小于所有 double 也可以)。

所以要么使用默认的operator< ，或以上safe_double_less ，或类似的东西。

接下来，我建议使用 std::multimap或 std::multiset ，因为您应该期望每次查找都有多个值。您不妨让内容管理成为日常工作，而不是极端情况，以增加代码的测试覆盖率。 (我很少推荐这些容器)加上这个 block operator[] , 不建议在使用浮点键时使用。

您要使用 epsilon 的地方是您查询容器的时候。不要使用直接接口(interface)，而是创建一个这样的辅助函数:

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

适用于 std::map和 std::set (和 multi 版本)。

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

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

要测试 key 是否存在，请执行以下操作:

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

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

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

如果您对 std::set 使用浮点键或 std::map ，几乎可以肯定从不做.find或 []在他们身上，因为这很可能是错误的来源。您可以将它用于自动排序的内容集合，只要确切的顺序无关紧要(即，一个特定的 1.0 领先或落后，或者与另一个 1.0 完全相同)。即便如此，我还是会使用 multimap/多集，因为我不会依赖碰撞或缺乏碰撞。

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