2

可能重复：
std:map 中的浮点键

好吧，我知道在某些情况下，您想提供一个特殊功能来进行双打比较。这种情况可能包括您进行算术运算的时间，因为您在浮点算术中进行了舍入。

但是，有时使用 < 或 > 比较双打是安全的吗？

假设我有一次计算的双精度列表，我需要对其进行排序或用作映射中的键（即 std::map），并且我保证之后没有任何额外的算术运算。

如果我使用迭代器遍历集合，我可以保证我的排序顺序是正确的吗？

我想我可以通过这种方式获得更多的性能。

4

3 回答 3

5

只要您从不添加任何 NaN 值，使用<比较doublea 中的值总是安全的。std::map用于映射的比较必须是严格的弱排序，它具有以下要求（C++03 §23.1.2/2 和 §25.3/3-4）：

  • 定义equiv(a, b)为!(a < b) && !(b < a)。那么，两者<和都equiv必须是传递关系：
    1. 如果a < b和b < c，则a < c必须为真
    2. 如果equiv(a, b)和equiv(b, c)，则equiv(a, c)必须为真

double值比较当然满足这些公理，除非将 NaN 值混入其中。NaN 有一个奇怪的属性，即它们不等于所有值（包括它们自己！）但不小于或大于任何值：

NaN < 0    // false
NaN <= 0   // false
NaN == 0   // false
NaN > 0    // false
NaN >= 0   // false
NaN != 0   // true
NaN < NaN  // false
NaN <= NaN // false
NaN == NaN // false (!!!)
NaN > NaN  // false
NaN >= NaN // false
NaN != NaN // true (!!!)

这会导致问题，因为根据上述规则，NaN具有equiv(x, NaN)对 all 为真的属性x，通过传递性意味着所有值都是等价的，除了非 NaN 值显然不等价。

于 2012-11-12T19:52:32.527 回答
4

是的，operator<在集合或地图中使用标准。大多数模糊double比较器不够严格，无法在 amap或中使用set。（并希望您在访问所述地图时不会弄乱浮点模式......）

我建议使用multimapor multiset，因为您认为相等的两个值可能略有不同。如果您已经期待多个条目，您应该更好地处理几乎相等的条目。

接下来，在搜索热门内容时lower_bound(x - epsilon)，upper_bound(x + epsilon)为了在地图中捕获不在您认为的位置的条目。

即，这里是“这是double在这个multiset<double>”代码：

typedef std::multiset<double> double_set;
std::pair< double_set::iterator, double_set::iterator >
get_equal_range( double_set& s, double d, double epsilon = 0.00001 )
{
  auto lower = s.lower_bound( d-epsilon );
  auto upper = s.upper_bound( d+epsilon );
  return std::make_pair( lower, upper );
}
std::pair< double_set::const_iterator, double_set::const_iterator >
get_equal_range( double_set const& s, double d, double epsilon = 0.00001 )
{
  auto lower = s.lower_bound( d-epsilon );
  auto upper = s.upper_bound( d+epsilon );
  return std::make_pair( lower, upper );
}
bool TestMembership( double_set const& s, double d, double epsilon = 0.00001 )
{
  auto range = get_equal_range( s, d, epsilon );
  return range.first != range.second;
}

因此，给定的double可以映射到一系列条目，或者在set.

从下面的一个很好的答案中被盗：如果你通过，默认的双倍operator<会搞砸你map或搞砸。setNaN

将东西放入map和set（和多个版本）时，您必须保持严格的弱排序规则。如果你失败了，你会出现看似随机的崩溃，并且偶尔会出现无限循环：和中的代码map对于set排序失败并不健壮。

于 2012-11-12T19:31:13.843 回答
3

在地图或集合中使用标准“<”至关重要，因为您尝试引入的任何软糖因素都会破坏他们用于组织容器的严格排序。不幸的是，这意味着你可能很难找到一个元素，除非你有确切的值。

您可以将lower_boundandupper_bound与低于和高于所需搜索值的值一起使用，以生成该值必须位于的范围。

于 2012-11-12T19:32:13.163 回答