c++vectorstlstl-algorithm

STL algorithm to get a per-vector-component min/max


I have a std::vector<vec3> points where vec3 has float x, y, z.

I want to find the min/max bounds of all the points. I.e. the min and max of all vec3::x, vec3::y, vec3::z separately in the vector of points.

I see that STL has std::minmax_element() which is almost what I want, but it assumes there is a min/max of the whole element.

I've found STL std::reduce() which can do min/max individually with a custom BinaryOp reduce function. The below code gives an example.

Unlike minmax_element(), reduce() needs two passes over the data. Is there an STL way to do it in one?

Yes, the right answer is to just write a simple loop myself, but I'm curious what STL has.

struct vec3 { float x, y, z; };

vec3 min(const vec3& a, const vec3& b)
{
    return vec3{
        min(a.x, b.x),
        min(a.y, b.y),
        min(a.z, b.z)
        };
}

vec3 max(const vec3& a, const vec3& b)
{
    return vec3{
        max(a.x, b.x),
        max(a.y, b.y),
        max(a.z, b.z)
        };
}

std::pair<vec3, vec3> minmax_elements(const std::vector<vec3>& points)
{
    vec3 vmin = std::reduce<std::vector<vec3>::const_iterator, vec3, vec3(const vec3&, const vec3&)>(
        points.cbegin(), points.cend(), points.front(), min);
    vec3 vmax = std::reduce<std::vector<vec3>::const_iterator, vec3, vec3(const vec3&, const vec3&)>(
        points.cbegin(), points.cend(), points.front(), max);
    return {vmin, vmax};
}

Side question: I had to give std::reduce explicit template parameters. Why can't the compiler deduce BinaryOp, the function type for min/max.


Solution

  • Of course you can use a lambda with std::reduce on a std::pair<vec3, vec3> collext both min and max at the same time.

    std::pair<vec3, vec3> minmax_elements(const std::vector<vec3>& points)
    {
        assert(!points.empty());
        return std::reduce(points.cbegin(), points.cend(), std::make_pair(points.front(), points.front()),
            [](std::pair<vec3, vec3> const& current, vec3 const& v2)
            {
                return std::make_pair(min(current.first, v2), max(current.second, v2));
            });
    }
    

    However ask yourself, brevity is really worth it. Personally I consider the following approach easier to understand and would prefer this implementation.

    std::pair<vec3, vec3> minmax_elements(const std::vector<vec3>& points)
    {
        assert(!points.empty());
        std::pair<vec3, vec3> result(points.front(), points.front());
    
        for (auto iter = points.begin() + 1; iter != points.end(); ++iter)
        {
            result.first = min(result.first, *iter);
            result.second = max(result.second, *iter);
        }
        return result;
    }