C++ std::strong_orderと浮動小数点数型totalOrder

C++20標準ライブラリのstd::strong_order関数オブジェクト*1は、IEEE 754準拠の浮動小数点数型に対する全順序比較（totalOrder predicate）を実装する。

#include <compare>
#include <concepts>
#include <iostream>
#include <limits>
#include <map>
#include <string>

template<std::floating_point T>
struct totalOrder {
  static_assert(std::numeric_limits<T>::is_iec559);
  bool operator()(T x, T y) const noexcept
    { return std::strong_order(x, y) < 0; };
};

using MapType = std::map<double, std::string, totalOrder<double>>;
// using MapType = std::map<double, std::string>; とすると
// キー比較にはstd::less<double>経由で言語組込の比較演算子<が利用され、
// 負のゼロ(-0.)や各種NaNをキーに用いると予期しない結果をもたらす。

const double qnan = std::numeric_limits<double>::quiet_NaN();
const double snan = std::numeric_limits<double>::signaling_NaN();

MapType m;
m[42] = "42";
m[-0.] = "-0";
m[+0.] = "+0";
m[-qnan] = "-qNaN";
m[+qnan] = "+qNaN";
m[-snan] = "-sNaN";
m[+snan] = "+sNaN";

std::cout
  << m[42] << "\n"     // 42
  << m[-0.] << "\n"    // -0
  << m[+0.] << "\n"    // +0
  << m[-qnan] << "\n"  // -qNaN
  << m[+qnan] << "\n"  // +qNaN
  << m[-snan] << "\n"  // -sNaN
  << m[+snan] << "\n"; // +sNaN

ノート：GCC/libstdc++とLLVM/libcxxの浮動小数点数型totalOrder実装は、NaNペイロード部の比較に関してIEEE 754仕様通りではない気がする（§5.10 d-3-iii）。特殊事情でもない限り浮動小数点数型を辞書型キーに使うべきではないし、totalOrder仕様に依存する処理は好ましくないと思う。

C++20 17.11.6/p1-2より一部引用。

1 The name strong_order denotes a customization point object (16.4.2.2.6). Given subexpressions E and F, the expression strong_order(E, F) is expression-equivalent (16.3.11) to the following:

(snip)

Otherwise, if the decayed type T of E is a floating-point type, yields a value of type strong_ordering that is consistent with the ordering observed by T's comparison operators, and if numeric_limits<T>::is_iec559 is true, is additionally consistent with the totalOrder operation as specified in ISO/IEC/IEEE 60559.

(snip)

2 The name weak_order denotes a customization point object (16.4.2.2.6). Given subexpressions E and F, the expression weak_order(E, F) is expression-equivalent (16.3.11) to the following:

(snip)

Otherwise, if the decayed type T of E is a floating-point type, yields a value of type weak_ordering that is consistent with the ordering observed by T’s comparison operators and strong_order, and if numeric_limits<T>::is_iec559 is true, is additionally consistent with the following equivalence classes, ordered from lesser to greater:

together, all negative NaN values;

negative infinity;

each normal negative value;

each subnormal negative value;

together, both zero values;

each subnormal positive value;

each normal positive value;

positive infinity;

together, all positive NaN values.

(snip)

IEEE 754-2019, 3.4, 5.10より一部引用。

3.4 Binary interchange format encodings
(snip)
In binary interchange formats, all number and NaN encodings are canonical.
(snip)

5.10 Details of totalOrder predicate
For each supported arithmetic format, an implementation shall provide the following predicate that defines an ordering among all operands in a particular format:

boolean totalOrder(source, source)

totalOrder(x, y) imposes a total ordering on canonical members of the format of x and y:

a) If x < y, totalOrder(x, y) is true.

b) If x > y, totalOrder(x, y) is false.

c) If x = y:

1) totalOrder(-0, +0) is true.

2) totalOrder(+0, -0) is false.

3) If x and y represent the same floating-point datum:

i) If x and y have negative sign, totalOrder(x, y) is true if and only if the exponent of x ≥ the exponent of y

ii) otherwise totalOrder(x, y) is true if and only if the exponent of x ≤ the exponent of y.

d) If x and y are unordered numerically because x or y is NaN:

1) totalOrder(-NaN, y) is true where -NaN represents a NaN with negative sign bit and y is a floating-point number.

2) totalOrder(x, +NaN) is true where +NaN represents a NaN with positive sign bit and x is a floating-point number.

3) If x and y are both NaNs, then totalOrder reflects a total ordering based on:

i) negative sign orders below positive sign

ii) signaling orders below quiet for +NaN, reverse for -NaN

iii) lesser payload, when regarded as an integer, orders below greater payload for +NaN, reverse for -NaN.

Neither signaling NaNs nor quiet NaNs signal an exception. For canonical x and y, totalOrder(x, y) and totalOrder(y, x) are both true if x and y are bitwise identical.
NOTE -- totalOrder does not impose a total ordering on all encodings in a format. In particular, it does not distinguish among different encodings of the same floating-point representation, as when one or both encodings are non-canonical

yohhoyの日記

技術的メモをしていきたい日記

C++ std::strong_orderと浮動小数点数型totalOrder