std::minmax_element处理含std::optional的vector时比较逻辑错误的解决方法

我定义了包含嵌套std::optional的结构体，想要查找结构体中H字段的A值的最小和最大值，但使用std::minmax_element得到的结果不准确，目前只能拆分比较函数分别用std::min_element和std::max_element，有没有更简洁的方式继续使用std::minmax_element？

原代码 #

#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_)
{
    // 如果两个H字段都有值，比较它们的A值
    if (a_.H.has_value() && b_.H.has_value()) 
    {
        return a_.H->A < b_.H->A;
    }
    // 如果只有一个H字段有值，返回false
    else
    {
        return false;
    }
}

bool CompareHMMax(const HM& a_, const HM& b_)
{
    // 如果两个H字段都有值，比较它们的A值
    if (a_.H.has_value() && b_.H.has_value()) 
    {
        return a_.H->A < b_.H->A;
    }
    // 如果只有a的H字段有值，视为更大，返回false
    else if (a_.H.has_value()) 
    {
        return false;
    }
    // 如果两个H字段都为空，或只有b的H字段有值
    else {
        return false;
    }
}

bool CompareHMMin(const HM& a_, const HM& b_)
{
    // 如果两个H字段都有值，比较它们的A值
    if (a_.H.has_value() && b_.H.has_value()) 
    {
        return a_.H->A < b_.H->A;
    }
    // 如果只有a的H字段有值，视为更小，返回true
    else if (a_.H.has_value()) 
    {
        return true;
    }
    // 如果两个H字段都为空，或只有b的H字段有值
    else 
    {
        return false;
    }
}

int main()
{
    // 创建包含HM结构体的vector并初始化数据
    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);

    // 打印结果
    std::cout << "正确的最小A值: " << min->H->A << "\n";
    std::cout << "正确的最大A值: " << max->H->A << "\n";
    std::cout << "使用minmax_element得到的错误最小A值: " << minmax.first->H->A << "\n";
    std::cout << "使用minmax_element得到的错误最大A值: " << minmax.second->H->A << "\n";

    return 0;
}

原输出 #

正确的最小A值: 0.9
正确的最大A值: 2.3
使用minmax_element得到的错误最小A值: 1.8
使用minmax_element得到的错误最大A值: 2.1

解决方案 #

问题出在原CompareHM不满足std::minmax_element要求的严格弱序规则。当两个元素中有一个H字段为空时，该函数始终返回false，导致算法无法正确判断元素间的逻辑顺序，最终得到错误结果。

我们只需要定义一个符合严格弱序的比较函数，统一处理所有场景：

• 若a有H、b无H：a视为更小，返回true
• 若a无H、b有H：a视为更大，返回false
• 若两者都无H：视为等价，返回false
• 若两者都有H：直接比较A值大小

修改后的代码如下：

#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_)
{
    // 优先处理有/无H的情况
    if (a_.H.has_value() != b_.H.has_value())
    {
        // 有H的元素排在无H的前面（视为更小）
        return a_.H.has_value();
    }
    // 两个都有H，比较A值
    else if (a_.H.has_value())
    {
        return a_.H->A < b_.H->A;
    }
    // 两个都无H，视为等价
    return false;
}

int main()
{
    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);
    
    // 验证结果
    std::cout << "minmax_element得到的最小A值: " << minmax.first->H->A << "\n";
    std::cout << "minmax_element得到的最大A值: " << minmax.second->H->A << "\n";

    return 0;
}

输出结果 #

minmax_element得到的最小A值: 0.9
minmax_element得到的最大A值: 2.3

这样就可以用单个比较函数配合std::minmax_element同时获取正确的最小和最大值，无需拆分调用std::min_element和std::max_element。

内容的提问来源于stack exchange，提问作者Brinck