Próbuję znaleźć minimalny element wektora 2D z lambdą

Dec 10 2020

Obecnie próbuję znaleźć minimalny element wektora 2D. Próbuję poćwiczyć używanie funkcji lambda w C ++ 11 i doszedłem do wniosku, że może to być dobra praktyka, ale nie wydaje się, żebym ją kompilował.

Mam świadomość, że mógłbym wykonać następujące czynności:

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;

ale zastanawiał się, czy to samo można zrobić z funkcją lambda. Obecnie jest to moja najlepsza próba:

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

Pojawia się błąd: błąd C2672 : „operator __surrogate_func”: nie znaleziono pasującej przeciążonej funkcji

Wydaje mi się, że powinno działać, ponieważ zewnętrzny element min_element będzie przechodził w jednym rzędzie na raz (co jest tylko odniesieniem do wektora), z którego mogę zwrócić najmniejszy, który zostanie następnie porównany z innymi wierszami.

Pomyślałem, że problem może polegać na tym, że lambda będzie otrzymywała iterator do wektora ints, a nie odniesienie do wektora ints, ale dereferencja nie wydaje się pomagać.

Czy jest lepszy sposób na robienie tego, co próbuję zrobić?

@assembly_wizard wskazał, że min_element potrzebuje predykatu, który może porównać dwa elementy, które mu przekazały. To jest dwa rzędy. Prowadzi to do następującego kodu:

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

Spowoduje to znalezienie wiersza z najmniejszym elementem. Chociaż mogę wykonać tę pracę, opakowując ją w jeszcze jeden element std :: min_element, jest to o wiele bardziej złożone niż bycie pomocnym zdalnie. Jeśli ktoś ma lepszą sugestię, bardzo chciałbym ją usłyszeć!

Odpowiedzi

2 assembly_wizard Dec 10 2020 at 08:30

Skompilowałem działającą wersję, która robi to, o czym wspomniałem w komentarzach:

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

Zobacz to w akcji na godbolt

To zajmie minimum każdego wiersza osobno, więc otrzymamy, row_minimumsktóry jest wektorem liczb całkowitych, a następnie potrzeba minimum z nich, aby uzyskać ostateczny wynik między wszystkimi wierszami.

Jedyną rzeczą, która sprawia, że ​​ten kod jest gorszy od forwersji pętli, jest to, że zachowuje wszystkie pliki row_minimumsw pamięci naraz, przed uruchomieniem min_elementna nich. Niestety nie znam sposobu, aby to zrobić jednocześnie, ale nie jestem największym oczekiwaniem STL, więc może jest sposób.

Inne opcje, które możesz rozważyć, to najpierw połączenie macierzy 2D w wektor 1D, a następnie użycie min_elementna nim, lub opcja, którą umieściłeś w swojej edycji, w której dzwonisz min_element3 razy.

Wydaje się również, że ta odpowiedź SO zawiera interesujące informacje dotyczące rozwiązań korzystających z boostbiblioteki, które mogą być lepsze, ale nie jestem pewien, jakie dokładnie one są.

1 Loreto Dec 10 2020 at 14:52

Trochę prościej: za pomocą std :: for_each iterujesz po każdym wektorze w macierzy i uzyskujesz ich minimalny element. Jak minwidać przez odniesienie, otrzymujesz min z nich wszystkich.

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