Попытка найти минимальный элемент 2D-вектора с помощью лямбда
В настоящее время я пытаюсь найти минимальный элемент 2D-вектора. Я пытаюсь попрактиковаться в использовании лямбда-функций С++ 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, это становится намного сложнее, чем быть отдаленно полезным. Если у кого-то есть лучшее предложение, я хотел бы услышать его!
Я понимаю. В этом есть смысл. Итак, я могу исправить это, чтобы найти строку с минимальным элементом, но есть ли способ просто найти наименьший элемент 2D-вектора в одной строке?
Вы можете попробовать использовать std::transform сначала с вашей лямбдой, а затем снова min_element с результатом преобразования, или std::reduce с вызовом min_element один раз внутри лямбды и сравнением результата самостоятельно. Я думаю, что оба они не так просты, как вам хотелось бы.
Попался! Да, это звучит намного сложнее, чем я предполагал.
Проблема здесь в том, что std::transform не возвращает итератор. Но оказывается, что есть boost::make_transform_iterator, если можно использовать boost. В противном случае посмотрите на этот трюк — stackoverflow.com/a/26089938/2566065
Уф, это кажется мне слишком сложным, не могли бы вы разбить это как ответ? Я постоянно пытаюсь научиться лучше использовать STL, но, честно говоря, еще не прикасался к boost. Легко быть ошеломленным.
Ответы 2
Я скомпилировал рабочую версию, которая делает то, что я упомянул в комментариях:
#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_element 3 раза.
Кроме того, этот ответ SO, кажется, содержит интересную информацию о решениях, использующих библиотеку boost, которые могут быть лучше, но я не уверен, что именно они собой представляют.
Это потрясающе :) Большое спасибо! Есть ли причина, по которой вы решили использовать преобразование, а не присваивание?
Назначение куда? Я сопоставил каждую строку с целым числом, поэтому создал новый вектор с помощью transform.
Чуть проще:
С помощью 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;
}
Любить это! Это выглядит ближе к тому, что я пытался сделать!
min_elementпринимает функцию сравнения, то есть лямбду, которая берет две строки и говорит, какая из них меньше