Почему компилятору требуется возвращаемый тип в следующих лямбдах
Я реализую рекурсивную DFS как лямбду, передавая себя в качестве параметра. Если я закомментирую логику, которая проверяет, нет ли у текущего узла дочерних элементов, я получаю ошибки сборки, говорящие о том, что лямбда используется до вывода типа.
#include <vector>
int main() {
int root;
std::vector<std::vector<int>> graph;
// ...
// build the tree as adjacency list starting from root
// ...
auto dfs = [&graph](auto self, auto u) {
// if (empty(graph[u])) {
// return;
// }
for (auto v : graph[u]) {
self(self, v);
}
};
dfs(dfs, root);
}
/usr/bin/g++-10 -std=c++20 -Wall -Wextra -Wshadow -pedantic -fdiagnostics-color=always -g -o main main.cpp
main.cpp: In instantiation of ‘main()::<lambda(auto:44, auto:45)> [with auto:44 = main()::<lambda(auto:44, auto:45)>; auto:45 = int]’:
main.cpp:66:18: required from here
main.cpp:63:17: error: use of ‘main()::<lambda(auto:44, auto:45)> [with auto:44 = main()::<lambda(auto:44, auto:45)>; auto:45 = int]’ before deduction of ‘auto’
63 | self(self, v);
| ~~~~^~~~~~~~~
Однако, как только я верну эту логику проверки, если пусто, код компилируется без проблем.
Это потому, что в последнем случае инструкция return дает компилятору подсказку, что лямбда возвращает void и, следовательно, ее тип известен в момент вызова self(self, v)?
В более широком смысле, где я могу прочитать и узнать больше о том, как компиляторы обрабатывают лямбда-определения, чтобы не полагаться на свои сообщения об ошибках и знать, когда необходимо объявлять возвращаемый тип, а когда нет?
Я вижу инфинитивную рекурсию зависимости. Вызов dfs зависит от вызова dfs. Чтобы узнать тип первого аргумента, вам нужно знать его тип. Слишком много auto-с.
ИМО было бы лучше создать класс и удалить лямбду. Было бы легче понять.
Ответы 1
Да, оператор return; — это именно то, что сообщает компилятору возвращаемый тип лямбды. В этом примере оператор говорит, что функция возвращает void.
Без знания типа возвращаемого значения вызов self(self, v); будет некорректным, поскольку вы фактически полагаетесь на вывод auto, не давая компилятору способа понять это.
Язык явно упоминает этот пример в dcl.spec.auto#general-11:
Если переменная или функция с невыведенным типом заполнителя названа выражением ([basic.def.odr]), программа имеет неправильный формат. Однако, как только в функции встречается неотброшенный оператор возврата, тип возвращаемого значения, выведенный из этого оператора, может использоваться в остальной части функции, в том числе в других операторах возврата.
(выделено мной) и предоставляет более простую версию проблемы в вашем коде:
auto sum(int i) { if (i == 1) return i; // sum's return type is int else return sum(i-1)+i; // OK, sum's return type has been deduced }
Это неполное/неправильное. Авто выводило нормально. dfs имеет конкретный выведенный тип и, конечно же, self зависит от него и может упоминаться в том виде, в каком он есть. Проблема в том, что выражение вызова в лямбда-выражении (со всеми конкретными замещенными типами) создает экземпляр оператора вызова, а вывод его возвращаемого типа — это то, что терпит неудачу (зависит от составного выражения, которое является телом лямбда, которое зависит от Звоните оператору). Вы также можете просто указать тип возвращаемого значения. -> void.
Это не является неполным/неправильным, auto действительно не удалось вывести типы, потому что функция была вызвана до того, как компилятору было предоставлено что-либо для вывода возвращаемого типа. В примере видно, что return i присутствует перед рекурсивным вызовом функции, следовательно, компилятор знает, что sum возвращает int, и может правильно обработать return sum(i-1)+i. Если вы измените порядок операторов if, вы увидите ошибки компилятора.
В моем примере довольно ясно, что auto в объявлении dfs относится к возвращаемому типу лямбды, или, если быть более точным, возвращаемому типу оператора вызова, но это все равно с точки зрения вывода auto.
Что такое
vector? Пожалуйста, опубликуйте минимальный воспроизводимый пример.