Trying to find the minimum element of 2D vector with lambda

Question

I'm currently trying to find the minimum element of a 2D vector. I'm trying to practice using C++11 lambda functions and figured this might be good practice, but can't seem to get it compiling.

I'm aware that I could do the following:

vector<vector<int>> matrix = {
                                {1, 2, 3, 4, 5 },
                                {6, 7, 8, 9, 10 },
                                {5, 6, 8, 1, 12 },
                                {1, 7, 2, 4, 18 },
};

int result = std::numeric_limits<int>::max();
for(const auto& row : matrix)
{
  int minElemInRow = *std::min_element(row.begin(), row.end());
  result = std::min(result , minElemInRow);
}
return result;

but was wondering if the same could be done with a lambda function. Currently, this is my best attempt:

vector<vector<int>> matrix = {
                                {1, 2, 3, 4, 5 },
                                {6, 7, 8, 9, 10 },
                                {5, 6, 8, 1, 12 },
                                {1, 7, 2, 4, 18 },
};

return *std::min_element(matrix.begin(), matrix.end(), 
  [](const auto& row)
  {
    return *std::min_element(row.begin(), row.end());
  });

I get the error: error C2672: 'operator __surrogate_func': no matching overloaded function found

How I feel it should be working is that the outer min_element will pass in a row at a time (which is just a reference to a vector), from which I can return the smallest, which will then be compared against other rows.

I thought that the problem might be that the lambda would be receiving an iterator to a vector of ints rather than a reference to the vector of ints, but dereferencing doesn't seem to be helping.

Is there a better way to be doing what I'm trying to do?

@assembly_wizard pointed out that min_element wants a predicate which can compare two of the item passed it. That is two rows. This leads to the following code:

vector<vector<int>> matrix = {
                                {1, 2, 3, 4, 5 },
                                {6, 7, 8, 9, 10 },
                                {5, 6, 8, 1, 12 },
                                {1, 7, 2, 4, 18 },
};

auto i = std::min_element(matrix.begin(), matrix.end(),
        [](const auto& lhs, const auto& rhs)
{
        return *std::min_element(lhs.begin(), lhs.end()) <
            *std::min_element(rhs.begin(), rhs.end());
});

This will find the row with the smallest element. Though I can make that work by wrapping it in yet another std::min_element, that's getting way more complex than to be remotely helpful. If anyone has a better suggestion, I'd love to hear it!

Answer 1

Just a little simpler: With std::for_each you iterate over each vector in matrix, and obtain the minimum element of them. As min is captured by reference, you get the min of all of them.

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3, 4, 5 },
        {6, 7, 8, 9, 10 },
        {5, 6, 8, 1, 12 },
        {1, 7, 2, 4, 18 },
    };

    int min = std::numeric_limits<int>::max();

    std::for_each(matrix.begin(), matrix.end(), 
        [&min](const auto& v) 
        { 
           min = std::min(*min_element(v.begin(), v.end()), min);
        }
    );

    std::cout << "Minimum element is: " << min << std::endl;
}

Answer 2

I've compiled a working version that does what I've mentioned in the comments:

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<std::vector<int>> matrix = {
        {1, 2, 3, 4, 5 },
        {6, 7, 8, 9, 10 },
        {5, 6, 8, 1, 12 },
        {1, 7, 2, 4, 18 },
    };

    std::vector<int> row_minimums(matrix.size());
    std::transform(matrix.begin(), matrix.end(), row_minimums.begin(), [](const auto& row) {
        return *std::min_element(row.begin(), row.end());
    });
    auto i = *std::min_element(row_minimums.begin(), row_minimums.end());

    std::cout << "Minimum element is: " << i << std::endl;
}

See it in action on godbolt

This will take the minimum of each row separately, so we get row_minimums which is a vector of ints, and then it takes the minimum of these to get the final result between all the rows.

The only thing making this code worse than the for loop version, is that it keeps all of the row_minimums in memory at once, before running min_element on them. Unfortunately I don't know of a way to do this simultaneously, but I'm not the greatest STL expect, so maybe there is a way.

Other options you might consider is first concatenating the 2D matrix into a 1D vector and then using min_element on it, or the option you've included in your edit where you call min_element 3 times.

Also, this SO answer seems to have interesting info regarding solutions using the boost library which might be better, but I'm not sure exactly what they are.