Crash in ranges::nth_element with std::numeric_limits::infinity

[mathysie]

In our code we use ranges::nth_element to partial sort the 10 highest doubles in a set of 2000, possibly containing infinity. Since version 0.13 however in some cases there is a crash.

The crash happens in nth_element.hpp, line 162. The code states if (i == --j). j is the 0th element of the array however, resulting in a out of bounds write.

I however did not succeed in reproducing the crash with a small example, so RangesCrashExample.txt is a cpp-file with my example and the data used in our sorting algorithm. This example has 2000 doubles with 8 entries std::numeric_limits<double>::infinity() and the comparison is std::greater{}.

I compile using Visual Studio 16.11.19 with the MSVC 19.29 compiler.

[ericniebler]

I don't think this is a bug. The elements must be partially ordered, IIRC. The presence of inf in the range violates the algorithm's preconditions.

[mathysie]

Thank you for the quick response!

If I check the docs (https://en.cppreference.com/w/cpp/algorithm/nth_element), there is no mention of a precondition apart from having two random access iterators pointing to the first en last elements of the range. Furthermore, according to (https://www.gnu.org/software/libc/manual/html_node/Infinity-and-NaN.html) we have (infinity < infinity) == false. Therefore I do not expect issues when sorting ranges containing infinities as infinity is not defined as smaller than infinity.

I'll check whether the MSVC-compiler defers from this and applies (infinity < infinity) == true.

[ericniebler]

For a and b to be partially ordered relative to each other, at most one of these must be true:

a < b b < a

That's not true for infinity.

[ericniebler]

:facepalm: I'm thinking of NaN.

[mathysie]

Yes, we initially made this mistake as well. We previously used NaN and got good results due to the used compiler, as the real behaviour of comparison with NaN and double is undefined. To make the results compiler-independent we refactored NaN to infinity to have all defined comparisons and pushed the code to production with the ranges v3-library of date 2021-11-02.

After updating to version 0.12, the given input started to crash.

I tested the comparisons with infinity, which gave the following output:

double a = std::numeric_limits<double>::infinity();
double b = std::numeric_limits<double>::infinity();

std::cout << std::boolalpha << (a < b) << std::endl;  // false
std::cout << std::boolalpha << (a > b) << std::endl;  // false
std::cout << std::boolalpha << (a == b) << std::endl; // true

Furthermore, comparison infinity with a 'standard' double gives:

double a = 42.37;
double b = std::numeric_limits<double>::infinity();

std::cout << std::boolalpha << (a < b) << std::endl;  // true
std::cout << std::boolalpha << (a > b) << std::endl;  // false
std::cout << std::boolalpha << (a == b) << std::endl; // false

This seems to me like infinity having a well-defined partial ordering in our input vector.

Whereas NaN does indeed not have a well-defined partial ordering with our compiler:

double a = std::numeric_limits<double>::quiet_NaN();
double b = std::numeric_limits<double>::quiet_NaN();

std::cout << std::boolalpha << (a < b) << std::endl;  // false
std::cout << std::boolalpha << (a > b) << std::endl;  // false
std::cout << std::boolalpha << (a == b) << std::endl; // false

[mathysie]

So in my opinion the algorithm should support infinity along with double's