В C++ мы сталкиваемся с двумя проблемами при написании рекурсивной функции, возвращающей диапазон:
Позвольте мне проиллюстрировать это разложением суммы . Вот строгое (не ленивое) решение
std::list<std::list<unsigned int>> SumDecompStrict(unsigned int n)
{
if (n == 0)
return { {} }; // the sum of the empty list is 0 by convention
std::list<std::list<unsigned int>> ret;
for (unsigned int k = 1; k <= n; k++)
{
std::list<std::list<unsigned int>> ll = SumDecompStrict(n - k);
for (auto& l : ll)
l.push_front(k);
ret.splice(ret.end(), std::move(ll));
}
return ret;
}
Теперь я хочу преобразовать это в ленивый генератор разложения суммы, возвращая диапазон, который может выглядеть так:
auto SumDecompLazy(unsigned int n)
{
if (n == 0)
return std::ranges::single_view<std::list<unsigned int>>({}); // the sum of the empty list is 0 by convention
return std::views::iota(1, n+1)
| std::views::transform([n](unsigned int k) {
return SumDecompLazy(n - k)
| std::views::transform([k](std::list<unsigned int>& l) { l.push_front(k); return l; });
}
| std::views::join;
}
Но SumDecompLazy
не скомпилируется из-за двух упомянутых проблем:
std::ranges::single_view<std::list<unsigned int>>({})
отличается от типа рекурсивного случаяSumDecompLazy
от самого себяЭта проблема решается в других языках программирования, например, с помощью типа IEnumerable в C# или его псевдонима seq в F#. Есть ли решение на C++?
Кстати: std::list
— довольно медленный контейнер, вы используете его только из-за push_front
и splice
? Я бы использовал std::vector
и добавил k
сзади.
@Caleth Ты совершенно прав насчет std::vector. Я не оптимизировал эту часть, потому что был сосредоточен на проблеме рекурсии, которую вы решили с помощью std::generator. Мне также нравится Any_view от Jarod42. В любом случае мне придется подождать, моя компания использует C++20.
В C++23 есть std::generator, который позволяет выразить это как сопрограмму, либо явно зацикливая
std::generator<std::list<unsigned int>> SumDecompLoop(unsigned int n)
{
if (n == 0)
co_yield {};
for (unsigned int k = 1; k <= n; k++)
{
for (auto l : SumDecompLoop(n - k))
{
l.push_front(k);
co_yield std::move(l);
}
}
}
или с помощью адаптеров диапазона
std::generator<std::list<unsigned int>>
SumDecompRange(unsigned int n)
{
if (n == 0)
co_yield {};
co_yield std::ranges::elements_of(std::views::iota(1u, n+1)
| std::views::transform([n](unsigned int k) {
return SumDecompRange(n - k)
| std::views::transform([k](std::list<unsigned int> l) { l.push_front(k); return l; });
})
| std::views::join);
}
range-V3 имеет
any_view
. стандарта еще нет...