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

vwoqyblh 于 2023-06-25 发布在其他

关注(0)|答案(2)|浏览(222)

我在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++

来源：https://stackoverflow.com/questions/76509081/stdminmax-element-comparer-for-a-vector-with-stdoptional-is-incorrect

2条答案

按热度按时间

kpbwa7wx1#

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

但如果a与b相当，情况显然不是这样。顺便说一下，这也是为什么你不能对包含NaN的float s的范围进行排序的原因（参见Is NaN a valid key value for associative containers?）。
与Min和Max关系不同，我们不能简单地将std::nullopt视为正/负无穷大值。

C++17或更早版本

在旧的C++标准中，可以使用remove-erase习惯用法中的std::remove_if就地消除std::nullopt元素：

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_if就足够了。显然，总是可以选择分别使用std::min_element和std::max_element。

C++20

我们可以使用std::ranges::filter_view来查看没有任何std::nullopt元素的范围，允许std::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）回复(0）举报 2023-06-25

zzzyeukh2#

一个大问题是，为了使用std::minmax_element，你需要决定一个无值的optional应该大于还是小于一个有值的可选值。不可能两者都是一个简单的解决方案是排除H是无值的HM s，首先通过划分vector。
您也可以使用defaultoperator<=>来简化此操作。对于optional：

仅当lhs和rhs都包含值时，才比较包含的值（使用相应的运算符T）。否则
当且仅当LHS和RHS都不包含值时，认为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;
};

然后将vector分区，以将HM与无值H放在vector的最后：

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

Demo
如果你不想对vector进行分区，你也可以使用ranges::filter_view，比如Jan showed，只是你不需要自定义比较器。
在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的工作原理与上面的相同。

展开查看全部

赞(0）回复(0）举报 2023-06-25

我来回答

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

2条答案

C++17或更早版本

C++20

相关问题

热门标签

最新问答