如何通过 STL mimax 算法替换我的 'for' 循环以查找 min/max

Question

我必须从

中找到 min/max 值（最小 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 算法来优化它？

Answer 1

minmax_element 对 Point 个对象运行比较，并将 return Point 个对象。

x和y值是独立的，min(x)和min(y)很可能属于不同的对象。

对于这种特殊情况，我会使用 for range。

Min = Point(640, 480) ;
Max = Point(0,0) ;
for (auto &p : contour)
{
    Min.x = std::min(p.x, Min.x)
    Min.y = std::min(p.y, Min.y)
    Max.x = std::max(p.x, Max.x)
    Max.y = std::max(p.y, Max.y)
}

Answer 2

不，单次调用 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方法与范围循环方法进行比较，我们可以考虑两个方面：

可读性。 accumulate 方法稍微更好地表达了从多个点中收集单个边界框的意图。但它会导致代码稍长。
性能。对于这两种方法，gcc（5.3 和 6）生成几乎相同的代码。 Clang 3.8 可以对循环的范围进行矢量化，但不能对 accumulate 进行矢量化。从 C++17 开始，我们将对 parallelizm TS 进行标准化。 accumulate 的并行对应是 reduce 算法，因此 accumulate/reduce 方法将允许更多的灵活性。

结论：range for 和 accumulate/reduce 都有一些（缺点）优点。但可能完全不同的方法是最好的方法：如果 OP 中的 cv::Point 意味着你使用 openCV 库，那么同一个库有 boundingRect 函数，它完全符合你想要实现的功能。

如何通过 STL mimax 算法替换我的 'for' 循环以查找 min/max

How to replace my 'for' loop to find min/max by STL mimax algorithm

c++

algorithm

stl

minmax