std::minmax_element comparer for a vector with std::optional is incorrect

Question

I have a struct within a struct of std::optionals, and I am trying to find the minimum and maximum value within the struct. However, using std::minmax_element seems to be inaccurate, and I've had to split the comparison function and use std::min_element and std::max_element instead. Is there a way to approach this that will allow me to still use std::minmax_element and be cleaner?

#include <iostream>
#include <vector>
#include <optional>
#include <algorithm>

struct AE
{
    double A;
    double E;
};

struct HM
{
   std::optional<AE> H;
   std::optional<AE> M;
};


bool CompareHM(const HM& a_, const HM& b_)
{
    // If both H fields have a value, compare them by A
    if (a_.H.has_value() && b_.H.has_value()) 
    {
        return a_.H->A < b_.H->A;
    }
    // If only one H field has a value, set to false
    else
    {
        return false;
    }
}

bool CompareHMMax(const HM& a_, const HM& b_)
{
    // If both H fields have a value, compare them by A
    if (a_.H.has_value() && b_.H.has_value()) 
    {
        return a_.H->A < b_.H->A;
    }
    // If only one H field has a value, consider it larger
    else if (a_.H.has_value()) 
    {
        return false;
    }
    // If both H fields are empty, or if just b has a value
    else {
        return false;
    }
}

bool CompareHMMin(const HM& a_, const HM& b_)
{
    // If both H fields have a value, compare them by A
    if (a_.H.has_value() && b_.H.has_value()) 
    {
        return a_.H->A < b_.H->A;
    }
    // If only one H field has a value, consider it smaller
    else if (a_.H.has_value()) 
    {
        return true;
    }
    // If both H fields are empty, or if just b has a value
    else 
    {
        return false;
    }
}

int main()
{
    // Create a vector of HM structs with some data
    std::vector<HM> vec = {
        HM{AE{1.8, 4.5}, AE{7.2, 4.1}},
        HM{AE{2.3, 3.4}, std::nullopt},
        HM{std::nullopt, AE{6.7, 8.9}},
        HM{AE{0.9, 2.1}, std::nullopt},
        HM{AE{1.8, 4.2}, AE{7.6, 9.0}},
        HM{std::nullopt, AE{0.7, 13.5}},
        HM{std::nullopt, AE{0.5, 19.3}},
        HM{AE{2.1, 4.2}, std::nullopt},
    };

    auto minmax = std::minmax_element(vec.begin(), vec.end(), CompareHM);
    auto min = std::min_element(vec.begin(), vec.end(), CompareHMMin);
    auto max = std::max_element(vec.begin(), vec.end(), CompareHMMax);

    // Print the results
    std::cout << "Correct Min A value: " << min->H->A << "\n";
    std::cout << "Correct Max A value: " << max->H->A << "\n";
    std::cout << "Incorrect Min A value using minmax_element: " << minmax.first->H->A << "\n";
    std::cout << "Incorrect Max A value using minmax_element: " << minmax.second->H->A << "\n";

    return 0;
}

Output:

Correct Min A value: 0.9
Correct Max A value: 2.3
Incorrect Min A value using minmax_element: 1.8
Incorrect Max A value using minmax_element: 2.1

Answer 1

A big problem is that in order to use std::minmax_element you need to decide if a valueless optional should be greater or less than an optional with a value. It can't be both. A simple solution is to exclude the HMs where H is valueless by partitioning the vector first.

You could also default operator<=> to make this simpler. For optional:

• The contained values are compared (using the corresponding operator of T) only if both lhs and rhs contain values. Otherwise,
• lhs is considered equal to rhs if, and only if, both lhs and rhs do not contain a value.
• lhs is considered less than rhs if, and only if, rhs contains a value and lhs does not.

That works fine with algorithms requiring strict week ordering, so:

struct AE {
    double A;
    double E;
    
    auto operator<=>(const AE& other) const = default;
};

struct HM {
    std::optional<AE> H;
    std::optional<AE> M;

    auto operator<=>(const HM&) const = default;
};

Then partition the vector to put the HMs with a valueless H last in the vector:

auto pp = std::stable_partition(vec.begin(), vec.end(), [](auto&& hm) {
    return hm.H.has_value();
});

Then minmax_element can do its job:

auto [min, max] = std::minmax_element(vec.begin(), pp);

Demo

If you don't want to partition the vector you can also use a ranges::filter_view like Jan showed, except that you'd exclude the custom comparator.

---

In C++17 and older you could define operator< for the two classes in order for the simplification to work. Still no need for the complicated custom comparators:

struct AE {
    double A;
    double E;

    bool operator<(const AE& other) const {
        return std::tie(A, E) < std::tie(other.A, other.E);
    }
};

struct HM {
    std::optional<AE> H;
    std::optional<AE> M;

    bool operator<(const HM& other) const {
        return std::tie(H, M) < std::tie(other.H, other.M);
    }
};

Partitioning and calling minmax_element would work the same as above.

Answer 2

CompareHM does not induce a strict weak ordering, which is why std::minmax_element gives you nonsense results.

A strict weak ordering needs to be transitive, and incomparable elements break this:

a < std::nullopt && std::nullopt < b   =>   a < b

This implication needs to be true for a strict weak ordering, but clearly isn't when std::nullopt is incomparable.

Incomparability needs to be a transitive relationship, i.e.

a incomparable_to std::nullopt  &&  b incomparable_to  =>  a incomparable_to b

But this is clearly not the case if a is comparable to b. On a side note this is also why you cannot sort ranges of floats that contain NaN (see Is NaN a valid key value for associative containers?).

Unlike in your Min and Max relations, we cannot simply treat std::nullopt as a positive/negative infinity value.

C++17 or Older

In older C++ standards, you could eliminate std::nullopt elements in-place using std::remove_if in the remove-erase idiom:

vec.erase(std::remove_if([](const HM& h) {
    return !h.has_value();
}, vec.end());
auto minmax = std::minmax_element(vec);
std::cout << minmax.first->H->A << ' ' << minmax.second->H->A << '\n';

Actually, it would be sufficient to use just std::remove_if if your goal is only to find the minimum and maximum element. Obviously, there's always the option of using std::min_element and std::max_element separately.

C++20

We could use std::ranges::filter_view to get a view of our range without any std::nullopt elements inside, allowing std::ranges::minmax_element to work correctly.

auto filter = std::ranges::filter_view(vec, [](const HM& h) {
    return h.H.has_value();
});

auto minmax = std::ranges::minmax_element(filter, CompareHM);
std::cout << minmax.min->H->A << ' ' << minmax.max->H->A << '\n';