`<algorithm>`: minmax family are returning wrong match index and may crash

[AlexGuteniev]

Describe the bug

Vectorized minmax family functions return wrong index / value when input contains NaNs.

Generally when input contains NaN, the behavior is undefined, because f strict weak ordering violation.

However, if the input contains only NaN value elements or NaN value elements and only one non-NaN value elements, the behavior appears to be defined: the comparisons is all false, so the strict weak ordering is met.

The below modification of test case fails though.

Command-line test case

From 50a4983bc81ceb867012cbff98081b0ba505c560 Mon Sep 17 00:00:00 2001
From: Alex Guteniev <gu...@gmail.com>
Date: Tue, 18 Jun 2024 09:25:19 +0300
Subject: [PATCH] repro

---
 .../VSO_0000000_vector_algorithms/test.cpp    | 20 +++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/tests/std/tests/VSO_0000000_vector_algorithms/test.cpp b/tests/std/tests/VSO_0000000_vector_algorithms/test.cpp
index 5f817218..cbd6f195 100644
--- a/tests/std/tests/VSO_0000000_vector_algorithms/test.cpp
+++ b/tests/std/tests/VSO_0000000_vector_algorithms/test.cpp
@@ -416,6 +416,22 @@ void test_min_max_element_floating(mt19937_64& gen) {
     }
 }

+template <class T>
+void test_min_max_element_floating_nan(mt19937_64& gen) {
+    // The set of two elements doesn't violate strict weak ordering
+    vector<T> input_of_input{numeric_limits<T>::quiet_NaN(), static_cast<T>(1.61803)};
+
+    uniform_int_distribution<size_t> idx_dis(0, input_of_input.size() - 1);
+
+    vector<T> input;
+    input.reserve(dataCount);
+    test_case_min_max_element(input);
+    for (size_t attempts = 0; attempts < dataCount; ++attempts) {
+        input.push_back(input_of_input[idx_dis(gen)]);
+        test_case_min_max_element(input);
+    }
+}
+
 void test_min_max_element_pointers(mt19937_64& gen) {
     const short arr[20]{};

@@ -905,6 +921,10 @@ void test_vector_algorithms(mt19937_64& gen) {
     test_min_max_element_floating<double>(gen);
     test_min_max_element_floating<long double>(gen);

+    test_min_max_element_floating_nan<float>(gen);
+    test_min_max_element_floating_nan<double>(gen);
+    test_min_max_element_floating_nan<long double>(gen);
+
     test_min_max_element_pointers(gen);

     test_min_max_element_special_cases<int8_t, 16>(); // SSE2 vectors
-- 
2.44.0.windows.1

Expected behavior

The above test pass. The algorithm returns the result as per standard.

UB cases still may fail, any expectation are only about apparently valid cases.

STL version

https://github.com/microsoft/STL/commit/18c09c48f5666e6b1ea2a3724c5f6f9917c4c6fb

Additional context

Originally reported in https://github.com/microsoft/STL/pull/3928#issuecomment-2174232902

[StephanTLavavej]

We talked about this at the weekly maintainer meeting and decided that the cases of all-nans or all-nans-except-one-plain-value aren't worth worrying about, and the Standard is vague on whether they're UB.