0

Is there a way to make min/max (std::min_element) ignore all NANs? I mean, it seems to ignore NANs in the middle but not if the first element is NAN.

Sample:

template <typename T> inline void GetMinMax(const T* data, const int len, T& min, T& max)
{
    min = *std::min_element(data, data + len);
    max = *std::max_element(data, data + len);
}

float min, max;
std::array<float, 4> ar1 = { -12, NAN, NAN, 13 };
GetMinMax<float>(&ar1[0], ar1.size(), min, max); //min: -12. max: 13

std::array<float, 4> ar2 = { -12, 3, 13, NAN };
GetMinMax<float>(&ar2[0], ar2.size(), min, max);//min: -12. max: 13

std::array<float, 4> ar3 = { NAN, -12, 3, 13 };
GetMinMax<float>(&ar3[0], ar3.size(), min, max);//min: -nan(ind). max: -nan(ind)  !!!!
Pedro77
  • 5,176
  • 7
  • 61
  • 91
  • 1
    Related, be aware of [`std::minmax_element`](https://en.cppreference.com/w/cpp/algorithm/minmax_element). It finds both in a single pass. – Igor Tandetnik May 18 '22 at 22:13
  • @Pedro77 What you need is to write the algorithm minmax_element_if.:) – Vlad from Moscow May 18 '22 at 22:17
  • Which implementation are you using? gcc seems to ignore the NAN's everywhere. Edit: Oh, my bad. It just didn't change the incoming values so I don't get `-nan(ind)` but `-12 13` out for the last one, no matter what values I put in the array. – Ted Lyngmo May 18 '22 at 22:19
  • 1
    Are we allowed to change the order of elements in the array? – David G May 18 '22 at 22:24
  • Hey, you are using `ar2` in the last one. That confused my results. You should change that to `ar3`. [Example](https://godbolt.org/z/7s7TzfdP5) – Ted Lyngmo May 18 '22 at 22:25
  • Some interesting findings here on comparisons against NaN [What is the result of comparing a number with NaN?](https://stackoverflow.com/questions/31225264/what-is-the-result-of-comparing-a-number-with-nan) _"...which requires that all comparisons but != involving NaN report false..."_ – Richard Critten May 18 '22 at 22:37
  • 3
    Your program exhibits undefined behavior, as the built-in `<` operator doesn't satisfy the requirements of strict weak ordering in the presence of NaNs. That it appears to work when NaN is not the first element is merely an accident. – Igor Tandetnik May 18 '22 at 23:02
  • @IgorTandetnik, just copy paste and run. It wasn't an accident. – Pedro77 May 19 '22 at 02:26
  • @TedLyngmo mistype. Fixed now. – Pedro77 May 19 '22 at 02:27
  • @IgorTandetnik thanks for the minmax_element. But it also bugs out and returns -nan(ind) for min. – Pedro77 May 19 '22 at 02:33
  • 1
    Undefined behavior is undefined. "Seems to work" is one possible manifestation of undefined behavior. You cannot point to the result of a program's execution as proof that the program does not exhibit undefined behavior. – Igor Tandetnik May 19 '22 at 03:05
  • 1
    Tangent: https://youtu.be/2FAi2mNYjFA?t=3960 ... if you've got some time at hand check out Sean Parent's explanation on how NaN breaks find(). – Martin Ba May 19 '22 at 09:22

2 Answers2

0

NAN compares with other numbers is screwy, see What is the result of comparing a number with NaN?.

So what you need to do is to provide a custom compare function so that NAN isn't the element std::min_element returns. Probably just make "NAN < x" return false and "x < NAN" return true. Similar for ">" for std::max_element. Or try overloading <=>.

Note: the solution might depend on your implementation of the STL, depending on which comparison operator the implementation uses.

Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42
  • The problem is what to return for `NaN < NaN` I can't think of a correct answer given that `NaN == NaN` is defined to be false. – Richard Critten May 19 '22 at 09:44
  • true, false, does it matter. One `NaN` is as bad as another. This would only matter if the data contains only `NaN`. I would pick the answer so that the first `NaN` is returned for the STL I'm using. – Goswin von Brederlow May 19 '22 at 10:05
  • With 2 NaNs (or more) in the container strict-weak-ordering would be violated leading to UB. – Richard Critten May 19 '22 at 10:31
  • @RichardCritten technically true, practically not. As long as min_element < any_other_element everything will work with a sequential access. Might not work with tree based containers but they probably explode when inserting 2 `NaN` before you even get to `std::min_element`. – Goswin von Brederlow May 19 '22 at 10:34
  • @RichardCritten Logically, NaN < anything is false, as is NaN > anything. It's disconnected from the graph. In an ideal world there would be a specialization of `std::max_element` for numeric types like `double` that aren't closed under ordering, that skips NaNs. – Spencer May 19 '22 at 16:46
0

The safest path is to remove all the NaNs values from the range before applying any min-max standard algorithm.

Consider a possible implementation of std::min_element1:

template<class ForwardIt>
ForwardIt min_element(ForwardIt first, ForwardIt last)
{
    if (first == last) return last;
 
    ForwardIt smallest = first;       // <-- If the first is a NaN...
    ++first;
    for (; first != last; ++first) {
        if (*first < *smallest) {     // <-- This condition will always be FALSE
            smallest = first;
        }
    }
    return smallest;                  // <-- An iterator to a NaN is returned
}

More formally, the C++ Standard2 specifies:

27.8.1 General [alg.sorting.general]

The operations in [alg.sorting] defined directly in namespace std have two versions: one that takes a function object of type Compare and one that uses an operator<.

Compare is a function object type ([function.objects]) that meets the requirements for a template parameter named BinaryPredicate ([algorithms.requirements]). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool ([conv]), yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation.

For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in [alg.binary.search], comp shall induce a strict weak ordering on the values.

The term strict refers to the requirement of an irreflexive relation (!comp(x, x) for all x), and the term weak to requirements that are not as strong as those for a total ordering, but stronger than those for a partial ordering. If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the requirements are that comp and equiv both be transitive relations:

(4.1) comp(a, b) && comp(b, c) implies comp(a, c)

(4.2) equiv(a, b) && equiv(b, c) implies equiv(a, c)

The problem, given any float value x, is that the following hold:

x < NaN == false and NaN < x == false, but x != NaN

Only considering the subset of the float values which are not NaNs we can fulfill the requirement.

1) https://en.cppreference.com/w/cpp/algorithm/min_element

2) I'm quoting the draft at https://eel.is/c++draft/alg.sorting.general , emphasis mine.

Bob__
  • 12,361
  • 3
  • 28
  • 42