Essayer de trouver l'élément minimum du vecteur 2D avec lambda

Dec 10 2020

J'essaye actuellement de trouver l'élément minimum d'un vecteur 2D. J'essaie de m'entraîner à utiliser les fonctions lambda C ++ 11 et j'ai pensé que cela pourrait être une bonne pratique, mais je n'arrive pas à le compiler.

Je suis conscient que je pourrais faire ce qui suit:

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;

mais je me demandais si la même chose pouvait être faite avec une fonction lambda. Actuellement, c'est ma meilleure tentative:

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

J'obtiens l'erreur: erreur C2672 : 'opérateur __surrogate_func': aucune fonction surchargée correspondante trouvée

Ce que je pense que cela devrait fonctionner, c'est que le min_element externe passera dans une ligne à la fois (qui n'est qu'une référence à un vecteur), à partir duquel je peux renvoyer le plus petit, qui sera ensuite comparé à d'autres lignes.

Je pensais que le problème était peut-être que le lambda recevrait un itérateur vers un vecteur d'entiers plutôt qu'une référence au vecteur d'ints, mais le déréférencement ne semble pas aider.

Y a-t-il une meilleure façon de faire ce que j'essaie de faire?

@assembly_wizard a souligné que min_element veut un prédicat qui peut comparer deux des éléments qui l'ont passé. Cela fait deux rangées. Cela conduit au code suivant:

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

Cela trouvera la ligne avec le plus petit élément. Bien que je puisse faire que cela fonctionne en l'enveloppant dans un autre std :: min_element, cela devient beaucoup plus complexe que d'être utile à distance. Si quelqu'un a une meilleure suggestion, j'aimerais l'entendre!

Réponses

2 assembly_wizard Dec 10 2020 at 08:30

J'ai compilé une version de travail qui fait ce que j'ai mentionné dans les commentaires:

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

Regardez-le en action sur godbolt

Cela prendra le minimum de chaque ligne séparément, donc nous obtenons row_minimumsquel est un vecteur d'entiers, puis il en faut le minimum pour obtenir le résultat final entre toutes les lignes.

La seule chose qui rend ce code pire que la forversion en boucle, c'est qu'il garde tous les éléments row_minimumsen mémoire à la fois, avant de les exécuter min_element. Malheureusement, je ne connais pas de moyen de faire cela simultanément, mais je ne suis pas le plus grand que la STL attende, alors peut-être qu'il y a un moyen.

D'autres options que vous pourriez envisager sont d'abord de concaténer la matrice 2D dans un vecteur 1D, puis de l'utiliser min_element, ou l'option que vous avez incluse dans votre modification et que vous appelez min_element3 fois.

En outre, cette réponse SO semble avoir des informations intéressantes concernant les solutions utilisant la boostbibliothèque qui pourraient être meilleures, mais je ne suis pas sûr de ce qu'elles sont exactement.

1 Loreto Dec 10 2020 at 14:52

Juste un peu plus simple: avec std :: for_each, vous itérez sur chaque vecteur de la matrice et en obtenez le minimum. Comme cela minest capturé par référence, vous obtenez le minimum de tous.

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