Попытка найти минимальный элемент 2D-вектора с помощью лямбда

Dec 10 2020

В настоящее время я пытаюсь найти минимальный элемент 2D-вектора. Я пытаюсь попрактиковаться в использовании лямбда-функций C ++ 11 и решил, что это может быть хорошей практикой, но, похоже, не могу его скомпилировать.

Я знаю, что могу сделать следующее:

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;

но мне было интересно, можно ли сделать то же самое с лямбда-функцией. На данный момент это моя лучшая попытка:

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

Я получаю сообщение об ошибке: ошибка C2672 : 'operator __surrogate_func': соответствующая перегруженная функция не найдена

Как я считаю, это должно работать, так это то, что внешний min_element будет проходить по строке за раз (что является просто ссылкой на вектор), из которого я могу вернуть наименьшее значение, которое затем будет сравниваться с другими строками.

Я думал, что проблема может заключаться в том, что лямбда будет получать итератор для вектора целых чисел, а не ссылку на вектор целых чисел, но разыменование, похоже, не помогает.

Есть ли лучший способ делать то, что я пытаюсь сделать?

@assembly_wizard указал, что min_element нужен предикат, который может сравнивать два элемента, переданных ему. Это две строки. Это приводит к следующему коду:

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

Это найдет строку с наименьшим элементом. Хотя я могу заставить это работать, заключив его в еще один std :: min_element, это становится намного сложнее, чем быть полезным удаленно. Если у кого-то есть предложение получше, я хотел бы его услышать!

Ответы

2 assembly_wizard Dec 10 2020 at 08:30

Я скомпилировал рабочую версию, которая делает то, что я упоминал в комментариях:

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

Посмотрите это в действии на Godbolt

Это займет минимум каждой строки отдельно, поэтому мы получим row_minimumsвектор целых чисел, а затем потребуется минимум из них, чтобы получить окончательный результат между всеми строками.

Единственное, что делает этот код хуже, чем forверсия цикла, - это то, что он сохраняет row_minimumsв памяти все сразу, прежде чем запускать min_elementих. К сожалению, я не знаю, как сделать это одновременно, но я не лучший из тех, кого ожидают от STL, так что, возможно, способ есть.

Другие варианты, которые вы можете рассмотреть, - это сначала объединить 2D-матрицу в 1D-вектор, а затем использовать min_elementего, или вариант, который вы включили в свое редактирование, где вы вызываете min_element3 раза.

Кроме того, этот ответ SO, похоже, содержит интересную информацию о решениях с использованием boostбиблиотеки, которая может быть лучше, но я не уверен, что именно они.

1 Loreto Dec 10 2020 at 14:52

Чуть проще: с помощью std :: for_each вы перебираете каждый вектор в матрице и получаете минимальный из них элемент. Как minвидно из ссылки, вы получите их минимум.

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