IEnumerable和使用yield return的递归

Question

我有一个 IEnumerable<T> 方法，用于在WebForms页面中查找控件。

这个方法是递归的，在使用 yield return 返回递归调用的值时，我遇到了一些问题，无法返回我想要的类型。

我的代码如下：

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach(Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if(c.Controls.Count > 0)
        {
            yield return c.GetDeepControlsByType<T>();
        }
    }
}

当前代码会抛出“无法转换表达式类型”的错误。然而，如果此方法返回类型为IEnumerable<Object>，则代码可以构建，但输出的类型不正确。

是否有一种方法可以在使用递归的同时使用yield return？

- Jamie Dixon

---

链接到“mrydengrens”在线程“枚举不是本质上IEnumerable的集合？” 上的答案。他的示例代码基于Eric Lippert的博客文章，向您展示如何在Linq中使用堆栈进行递归枚举，从而避免由迭代器可能导致的昂贵内存使用。imho非常有用！ - BillW

顺便说一句，if(c.Controls.Count > 0) --> if(c.Controls.Any())，特别是如果你也在使用yield :) - tymtam

我认为这种情况不适合使用yield。为了完整起见，我提供了一个没有“yield”的实现。请看下面的代码 :) 而且它只有一行 :) - tymtam

在递归函数中应该小心避免使用 yield return，因为内存使用会呈指数级增长。请参考 https://dev59.com/bHI95IYBdhLWcg3w_zas#30300257。 - Colonel Panic

Answer 1

在返回 IEnumerable<T> 的方法中，yield return 必须返回 T，而不是 IEnumerable<T>。

请替换为：

yield return c.GetDeepControlsByType<T>();

使用：

foreach (var x in c.GetDeepControlsByType<T>())
{
  yield return x;
}

- Marcin Seredynski

Answer 2

你需要产生由递归调用生成的每个项目：

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach(Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if(c.Controls.Count > 0)
        {
            foreach (Control control in c.GetDeepControlsByType<T>())
            {
                yield return control;
            }
        }
    }
}

请注意，这种递归的代价是会创建大量迭代器，如果控制树非常深，则可能会导致性能问题。如果要避免这种情况，您基本上需要在方法内部自己进行递归，以确保只创建一个迭代器（状态机）。有关详细信息和示例实现，请参见此问题 - 但这显然也增加了一定的复杂性。

- Jon Skeet

---

在有关 yield 的讨论中，我很惊讶 Jon 没有提到 c.Controls.Count > 0 和 .Any() 的区别 :) - tymtam

@Tymek 实际上在链接的答案中已经提到了。 - user3638471

Answer 3

正如Jon Skeet和Colonel Panic在他们的回答中指出的那样，如果树非常深，使用yield return在递归方法中可能会导致性能问题。

这是一个通用的非递归扩展方法，它执行序列树的深度优先遍历：

public static IEnumerable<TSource> RecursiveSelect<TSource>(
    this IEnumerable<TSource> source, Func<TSource, IEnumerable<TSource>> childSelector)
{
    var stack = new Stack<IEnumerator<TSource>>();
    var enumerator = source.GetEnumerator();

    try
    {
        while (true)
        {
            if (enumerator.MoveNext())
            {
                TSource element = enumerator.Current;
                yield return element;

                stack.Push(enumerator);
                enumerator = childSelector(element).GetEnumerator();
            }
            else if (stack.Count > 0)
            {
                enumerator.Dispose();
                enumerator = stack.Pop();
            }
            else
            {
                yield break;
            }
        }
    }
    finally
    {
        enumerator.Dispose();

        while (stack.Count > 0) // Clean up in case of an exception.
        {
            enumerator = stack.Pop();
            enumerator.Dispose();
        }
    }
}

与Eric Lippert的解决方案不同，RecursiveSelect直接使用枚举器，因此不需要调用Reverse（它会将整个序列缓存到内存中）。

使用RecursiveSelect，OP的原始方法可以简单地重写如下：

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    return control.Controls.RecursiveSelect(c => c.Controls).Where(c => c is T);
}

- Michael Liu

---

为了让这段（优秀的）代码正常工作，我不得不使用 'OfType 将 ControlCollection 转换为 IEnumerable 格式；在 Windows Forms 中，ControlCollection 不可枚举：
return control.Controls.OfType<Control>().RecursiveSelect<Control>(c => c.Controls.OfType<Control>()) .Where(c => c is T); - BillW

Answer 4

其他人已经给出了正确的答案，但我认为在你的情况下不需要使用yield。

这里有一段代码片段可以在不使用yield的情况下实现相同的功能。

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
   return control.Controls
                 .Where(c => c is T)
                 .Concat(control.Controls
                                .SelectMany(c =>c.GetDeepControlsByType<T>()));
}

- tymtam

---

难道不也使用LINQ的yield吗？ ;) - Philipp M

这太棒了。我一直被额外的foreach循环所困扰。现在我可以使用纯函数式编程来完成它！ - jsuddsjr

我喜欢这个解决方案的可读性，但它与使用yield一样面临着迭代器的性能问题。@PhilippM：已验证LINQ使用yield https://referencesource.microsoft.com/System.Core/R/577032c8811e20d3.html - Herman

给一个伟大的解决方案点个赞。 - Tomer W

Answer 5

在你的第二个yield return中，需要返回枚举器中的项，而不是枚举器本身。

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach (Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if (c.Controls.Count > 0)
        {
            foreach (Control ctrl in c.GetDeepControlsByType<T>())
            {
                yield return ctrl;
            }
        }
    }
}

- Rob Levine

Answer 6

Seredynski的语法是正确的，但在递归函数中应该小心避免使用yield return，因为它会导致内存使用率灾难性增长。详情请参见https://dev59.com/lW865IYBdhLWcg3wIa_M#3970171，这种情况在深度上呈指数级增长（我的应用程序中类似的函数使用了10%的内存）。

一个简单的解决方案是使用一个列表并将其与递归一起传递https://codereview.stackexchange.com/a/5651/754

/// <summary>
/// Append the descendents of tree to the given list.
/// </summary>
private void AppendDescendents(Tree tree, List<Tree> descendents)
{
    foreach (var child in tree.Children)
    {
        descendents.Add(child);
        AppendDescendents(child, descendents);
    }
}

或者您可以使用堆栈和while循环来消除递归调用 https://codereview.stackexchange.com/a/5661/754

- Colonel Panic

Answer 7

我认为您需要在可枚举对象中使用yield return返回每个控件。

    public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
    {
        foreach (Control c in control.Controls)
        {
            if (c is T)
            {
                yield return c;
            }

            if (c.Controls.Count > 0)
            {
                foreach (Control childControl in c.GetDeepControlsByType<T>())
                {
                    yield return childControl;
                }
            }
        }
    }

- Torbjörn Hansson

Answer 8

虽然已经有许多好的答案，但我仍然想补充一点：可以使用LINQ方法来达到同样的效果。

例如，原始代码可以重写为：

public static IEnumerable<Control> 
                           GetDeepControlsByType<T>(this Control control)
{
   return control.Controls.OfType<T>()
          .Union(control.Controls.SelectMany(c => c.GetDeepControlsByType<T>()));        
}

- yoel halb

---

三年前已经有人使用了同样的方法提出了一个解决方案。 - Servy

@Servy 尽管它们很相似（顺便说一下，在撰写这篇答案时我错过了它们之间的区别...），但它们仍然不同，因为它使用 .OfType<> 进行过滤，并使用 .Union()。 - yoel halb

“OfType”并没有什么实质性的不同，只是一种较小的风格上的变化。控件不能是多个控件的子级，因此遍历的树已经是唯一的。使用“Union”而不是“Concat”是毫无必要的，因为它会验证已经保证唯一性的序列，因此是一种客观的降级。 - Servy