2

重複の可能性:
std:map の浮動小数点キー

double 比較を行うための特別な関数を提供したい場合があることは知っています。このようなケースには、浮動小数点演算で丸めが発生するため、算術演算を行う場合が含まれる可能性があります。

しかし、ダブルスを比較するために < または > を使用しても安全な場合はありますか?

一度計算された double のリストがあり、それを並べ替えるか、マップのキーとして使用する必要があるとします (つまり、std::map)。その後、追加の算術演算がないことを保証します。

イテレータを使用してコレクションをトラバースした場合、ソート順が正しいことを保証できますか?

この方法でより多くのパフォーマンスを得ることができると思います。

4

3 に答える 3

5

NaN 値を追加しない限り、 a の値<を比較するために使用しても常に安全です。マップに使用される比較は、厳密な弱い順序付けである必要があり、これには次の要件があります (C++03 §23.1.2/2 および §25.3/3-4):doublestd::map

  • として定義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 (!!!)

これは問題を引き起こします。なぜなら、上記のルールの下では、は all に対して true でNaNあるプロパティを持っているためです。これは、推移性により、非 NaN 値が明らかに等価でないことを除いて、すべての値が等価であることを意味します。equiv(x, NaN)x

于 2012-11-12T19:52:32.527 に答える
4

はい、operator<セットまたはマップで標準を使用します。ほとんどのあいまい比較演算子は、またはdoubleで使用できるほど厳密ではありません。（そして、上記のマップにアクセスしているときに浮動小数点モードをいじっていないことを願っています...）mapset

multimapまたはを使用することをお勧めしmultisetます。これは、等しいと思われる 2 つの値がわずかに異なる可能性があるためです。すでに複数のエントリが予想される場合は、ほぼ等しいエントリをより適切に処理する必要があります。

次に、ヒットを検索するときに、思った場所にないマップ内のエントリをキャッチするために実行しますlower_bound(x - epsilon)。upper_bound(x + epsilon)

つまり、ここに「is this doublein this 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

mapand set(および複数のバージョン) に配置する場合は、厳密な弱い順序付け規則を維持する必要があります。失敗すると、一見ランダムなクラッシュが発生し、時折無限ループが発生します。 と のコードはmap、set順序付けの失敗に対して堅牢ではありません。

于 2012-11-12T19:31:13.843 に答える
3

マップまたはセットで標準の '<' を使用することは非常に重要です。導入しようとするファッジ ファクターは、コンテナーを編成するために使用する厳密な順序付けを破壊するからです。残念ながら、これは、正確な値がない限り、要素を見つけるのに苦労する可能性があることを意味します.

目的の検索値のすぐ下または上の値でlower_boundとを使用して、値が必要な範囲を作成できます。upper_bound

于 2012-11-12T19:32:13.163 に答える