c++ - 如何替换我的 'for' 循环以通过 STL mimax 算法找到最小值/最大值

我必须从 a 中找到最小/最大值(最小 x、最小 y、最大 x、最大 y)

vector<cv::Point>

这是我的代码:

vector<cv::Point> contour;

...

Min = Point(640, 480) ;
Max = Point(0,0) ;
for (int j=0; j<(int)contour.size(); j++)
{
    if (contour[j].x < Min.x) Min.x = contour[j].x ;
    if (contour[j].y < Min.y) Min.y = contour[j].y ;
    if (contour[j].x > Max.x) Max.x = contour[j].x ;
    if (contour[j].y > Max.y) Max.y = contour[j].y ;
}

这工作正常。我使用 mimmax STL 开发了一个版本:

auto XminXmax = minmax_element(contour.begin(), contour.end(), [](Point p1,Point p2) {return p1.x < p2.x; });
auto YminYmax = minmax_element(contour.begin(), contour.end(), [](Point p1,Point p2) {return p1.y < p2.y; });
Point Min = Point((*XminXmax.first).x, (*YminYmax.first).y );
Point Max = Point((*XminXmax.second).x, (*YminYmax.second).y );

这也可以正常工作并给出相同的结果。
然而，由于算法 minmax 被调用两次，执行时间是两次。
是否可以通过调用 minmax 算法来优化这一点？

最佳答案

不，不可能通过一次调用 minmax_element 来优化它，因为 minmax_element 不是这个问题的最佳解决方案。

如果您坚持使用某种 STL 算法，请使用 accumulate :

std::accumulate(begin(contour), end(contour), Bound{}, [](Bound acc, Point p)
{
    return Bound{minpos(acc.bottomleft, p), maxpos(acc.topright, p)};
});

但这需要一些准备:

#include <numeric>

struct Point
{
    int x;
    int y;

    Point(int x, int y)
        : x(x), y(y) {}
};

Point minpos(Point a, Point b)
{
    return {std::min(a.x, b.x), std::min(a.y, b.y)};
}

Point maxpos(Point a, Point b)
{
    return {std::max(a.x, b.x), std::max(a.y, b.y)};
}

struct Bound
{
    Point bottomleft;
    Point topright;

    Bound(Point bl = {640, 480}, Point tr = {0, 0})
        : bottomleft(bl), topright(tr) {}
};

将 accumulate 方法与 range for 循环方法进行比较，我们可以考虑两个方面:

可读性。 accumulate 方法稍微更好地表达了从几个点中收集单个边界框的意图。但它会导致代码稍长。

性能。对于这两种方法，gcc(5.3 和 6)生成几乎相同的代码。 Clang 3.8 可以为循环矢量化范围，但不能为 accumulate 做到这一点。从 C++17 开始，我们将标准化并行化 TS。 accumulate 的并行对应物是 reduce 算法，因此 accumulate/reduce 方法将提供更大的灵活性。

结论: range for 和 accumulate/reduce 都有一些(缺点)优势。但可能最好的方法是完全不同的方法:如果 OP 中的 cv::Point 意味着您使用 openCV 库，那么同一个库具有 boundingRect 函数，该函数正是您想要实现的。

关于c++ - 如何替换我的 'for' 循环以通过 STL mimax 算法找到最小值/最大值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35938873/