如何使用STL的minmax算法替换我的“for”循环以查找最小/最大值

Question

我需要从一个包含x和y坐标信息的数据集中找到最小和最大值（最小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算法来进行优化？

- Andre

Answer 1

minmax_element 函数在 Point 对象上运行比较，并返回 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)
}

- Juan Leni

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方法与range for循环方法进行比较，我们可以考虑两个方面：

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

结论：无论是range for还是accumulate/reduce都有一些（不）优点。但也许完全不同的方法才是最好的：如果OP中的cv::Point表示您使用openCV库，那么同样的库有boundingRect函数，它恰好可以实现您想要实现的功能。

- Evgeny Kluev

---

我曾希望STL算法在代码长度方面更加高效。对于范围而言，它更简单。但是你回答了我的问题！最后，我将使用openCV的boundingRect函数。 - Andre