std：：minmax_element 带有 std：：optional 的向量的比较器不正确

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

提问人：Brinck 提问时间：6/20/2023 更新时间：6/20/2023 访问量：129

问：

我在 std：：optionals 的结构中有一个结构，我正在尝试在结构中找到最小值和最大值。但是，使用 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_)
{
    // 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;
}

输出：

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
C++ 向量 minmax std可选

评论

1赞 Pepijn Kramer 6/20/2023
不，这是一个正确的结果，您没有严格的命令（当两个项目都未设置时）。请参阅比较的要求。它必须导致完全的 stict 排序
0赞 NathanOliver 6/20/2023
你自相矛盾：如果只有一个 H 字段有一个值，则认为它更小，或者如果只有 b 有一个值，则两者都返回 falseHMMax
0赞 Brinck 6/20/2023
@Pepijn Kramer，我得到的是，为了实现所有 H 的合理比较，我必须过滤掉任何无效的 H 元素。然后我可以使用 std：：minmax_element 并使其更简单，对吗？
0赞 Jan Schultke 6/20/2023
@PepijnKramer这是不正确的。比较需要严格的弱排序。
1赞 HolyBlackCat 6/20/2023
@JanSchultke 我相信你实际上不能对 NaN 进行排序：stackoverflow.com/questions/8096817/......

答：

3赞 Jan Schultke 6/20/2023 #1

CompareHM不会诱发严格的弱排序，这就是为什么会给你无意义的结果。std::minmax_element

严格的弱排序需要是传递的，而无与伦比的元素打破了这一点：

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

对于严格的弱排序来说，这种含义必须是正确的，但显然不是不可比拟的。std::nullopt

不可比性需要是一种传递关系，即

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

但是，如果与 . 顺便说一句，这也是为什么不能对包含 NaN 的 s 范围进行排序的原因（请参阅 NaN 是关联容器的有效键值吗？）。abfloat

与 ur 和 关系不同，我们不能简单地将其视为正/负无穷大值。MinMaxstd::nullopt

C++ 17 或更早版本

在较旧的 C++ 标准中，您可以使用删除-擦除习惯用语就地消除元素：std::nulloptstd::remove_if

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';

实际上，如果您的目标只是找到最小和最大元素，则使用它就足够了。 显然，总是可以选择单独使用 和。std::remove_ifstd::min_elementstd::max_element

C++20

我们可以用来查看我们的范围，而无需内部任何元素，从而可以正常工作。std::ranges::filter_viewstd::nulloptstd::ranges::minmax_element

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';

评论

0赞 Ted Lyngmo 6/20/2023
一个 - 我总是忘记范围的力量：-）ranges::filter_view
3赞 Ted Lyngmo 6/20/2023 #2

一个大问题是，为了使用，您需要决定 valueless 是否应该大于或小于 a value 的可选。不能两者兼而有之。一个简单的解决方案是通过对第一个进行分区来排除 s 是无值的。std::minmax_elementoptionalHMHvector

你也可以让它更简单。为：defaultoperator<=>optional

  • 仅当 lhs 和 rhs 都包含值时，才会比较包含的值（使用相应的运算符 ）。否则T
  • 当且仅当 LHS 和 RH 都不包含值时，LHS 才被视为等于 RHS。
  • 当且仅当 RHS 包含值而 LHS 不包含值时，才认为 LHS 小于 RHS。

这适用于需要严格周排序的算法，因此：

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;
};

然后对 进行分区，将 s 与无值的最后放在 ：vectorHMHvector

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

然后可以完成它的工作：minmax_element

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

演示

如果你不想分区，你也可以使用一个像 Jan 显示的那样，除了你会排除自定义比较器。vectorranges::filter_view

在 C++17 及更早版本中，您可以为这两个类定义，以便简化工作。仍然不需要复杂的自定义比较器：operator<

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);
    }
};

分区和调用的工作方式与上述相同。minmax_element

上一个：对对象的可选引用：最佳方式？

下一个：我可以让 std：：optional&lt;std：：exception&gt;：：value（） 返回（多态）继承的异常，而不是 std：：exception 吗？