Tentando encontrar o elemento mínimo do vetor 2D com lambda

Dec 10 2020

Atualmente, estou tentando encontrar o elemento mínimo de um vetor 2D. Estou tentando praticar o uso de funções lambda do C ++ 11 e percebi que isso pode ser uma boa prática, mas não consigo fazer a compilação.

Estou ciente de que posso fazer o seguinte:

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;

mas queria saber se o mesmo poderia ser feito com uma função lambda. Atualmente, esta é minha melhor tentativa:

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());
  });

Recebo o erro: erro C2672 : 'operator __surrogate_func': nenhuma função sobrecarregada correspondente encontrada

Acho que deveria estar funcionando que o min_elemento externo passará em uma linha por vez (que é apenas uma referência a um vetor), a partir do qual posso retornar o menor, que será então comparado com outras linhas.

Achei que o problema poderia ser que o lambda estaria recebendo um iterador para um vetor de ints em vez de uma referência ao vetor de ints, mas a desreferenciação não parece estar ajudando.

Existe uma maneira melhor de fazer o que estou tentando fazer?

@assembly_wizard apontou que min_element quer um predicado que possa comparar dois dos itens passados. São duas linhas. Isso leva ao seguinte código:

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());
});

Isso encontrará a linha com o menor elemento. Embora eu possa fazer isso funcionar envolvendo-o em outro std :: min_element, isso está ficando muito mais complexo do que ser remotamente útil. Se alguém tiver uma sugestão melhor, eu adoraria ouvir!

Respostas

2 assembly_wizard Dec 10 2020 at 08:30

Compilei uma versão funcional que faz o que mencionei nos comentários:

#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;
}

Veja em ação em Godbolt

Isso levará o mínimo de cada linha separadamente, então obtemos row_minimumsqual é um vetor de ints, e então é necessário o mínimo deles para obter o resultado final entre todas as linhas.

A única coisa que torna este código pior do que a forversão em loop, é que ele mantém tudo row_minimumsna memória de uma vez, antes de executá min_element-lo. Infelizmente, não conheço uma maneira de fazer isso simultaneamente, mas não sou o melhor STL que esperava, então talvez haja uma maneira.

Outras opções que você pode considerar são primeiro concatenar a matriz 2D em um vetor 1D e então usá min_element-la, ou a opção que você incluiu em sua edição onde você chama min_element3 vezes.

Além disso, esta resposta do SO parece ter informações interessantes sobre soluções usando a boostbiblioteca que podem ser melhores, mas não tenho certeza de quais são.

1 Loreto Dec 10 2020 at 14:52

Um pouco mais simples: com std :: for_each você itera sobre cada vetor na matriz e obtém o elemento mínimo deles. Conforme mincapturado por referência, você obtém o mínimo de todos eles.

#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;
}