枚举本质上不是 IEnumerable 的集合？

Question

当您想要递归枚举一个分层对象，根据某些条件选择一些元素时，有许多技术示例，例如“扁平化”，然后使用 Linq 进行过滤：就像在这里找到的那​​些示例：

链接文本

但是，当您枚举诸如 Form 的 Controls 集合或 TreeView 的 Nodes 集合之类的内容时，我无法使用这些类型技术，因为它们似乎需要一个参数（扩展方法），该参数是 IEnumerable 集合：传入 SomeForm.Controls 无法编译。

我发现的最有用的东西是：

链接文本< /a>

这确实为您提供了 Control.ControlCollection 的扩展方法，其中包含 IEnumerable 结果，然后您可以将其与 Linq 一起使用。

我已经修改了上面的示例来毫无问题地解析 TreeView 的节点。

public static IEnumerable<TreeNode> GetNodesRecursively(this TreeNodeCollection nodeCollection)
{
    foreach (TreeNode theNode in nodeCollection)
    {
        yield return theNode;

        if (theNode.Nodes.Count > 0)
        {
            foreach (TreeNode subNode in theNode.Nodes.GetNodesRecursively())
            {
                yield return subNode;
            }
        }
    }
}

这就是我现在使用扩展方法编写的代码：

    var theNodes = treeView1.Nodes.GetNodesRecursively();

    var filteredNodes = 
    (
        from n in theNodes
            where n.Text.Contains("1")
                select n
    ).ToList();

我认为可能有一种更优雅的方法可以在传入约束的情况下执行此操作。

我想知道是否可以定义这样的过程是通用的，这样：在运行时我可以将集合的类型以及实际的集合传递给通用参数，因此代码独立于它是 TreeNodeCollection 还是 Controls.Collection。

我还想知道是否有比第二个链接（上面）中显示的方法更便宜？更快？）以 Linq 可用的形式获取 TreeNodeCollection 或 Control.ControlCollection 。

Leppie 在链接到第一个（上面）的 SO 帖子中关于“SelectMany”的评论似乎是一个线索。

我对 SelectMany 的实验是：好吧，称它们为“灾难”。 :)

感谢任何指点。我花了几个小时阅读我能找到的所有涉及这些领域的 SO 帖子，并漫无目的地进入了“y-combinator”这样的奇特事物。我可能会补充说，这是一次“谦卑”的经历:)

Answer 1

这段代码应该可以解决问题，

public static class Extensions
{
    public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        foreach (var item in collection.OfType<T>())
        {
            yield return item;

            IEnumerable<T> children = selector(item).GetRecursively(selector);
            foreach (var child in children)
            {
                yield return child;
            }
        }
    }
}

这是一个如何使用它的示例

TreeView view = new TreeView();

// ...

IEnumerable<TreeNode> nodes = view.Nodes.
    .GetRecursively<TreeNode>(item => item.Nodes);

更新：响应 Eric Lippert 的帖子。

这是使用 中讨论的技术的一个大大改进的版本关于迭代器的一切。

public static class Extensions
{
    public static IEnumerable<T> GetItems<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        Stack<IEnumerable<T>> stack = new Stack<IEnumerable<T>>();
        stack.Push(collection.OfType<T>());

        while (stack.Count > 0)
        {
            IEnumerable<T> items = stack.Pop();
            foreach (var item in items)
            {
                yield return item;

                IEnumerable<T> children = selector(item).OfType<T>();
                stack.Push(children);
            }
        }
    }
}

我使用以下基准测试技术进行了简单的性能测试。结果不言而喻。树的深度对第二种解决方案的性能只有边际影响；而第一个解决方案的性能会迅速下降，当树的深度变得太大时，最终会导致 StackOverflowException 。

Answer 2

您似乎走在正确的道路上，上面的答案有一些好主意。但我注意到所有这些递归解决方案都有一些深刻的缺陷。

假设所讨论的树总共有 n 个节点，最大树深度为 d <= n。

首先，它们消耗树深度的系统堆栈空间。如果树结构非常深，那么这可能会破坏堆栈并使程序崩溃。树深度 d 为 O(lg n)，取决于树的分支因子。更糟糕的情况是根本没有分支——只有一个链表——在这种情况下，只有几百个节点的树将破坏堆栈。

其次，您在这里所做的是构建一个迭代器，该迭代器调用一个迭代器，该迭代器调用另一个迭代器……这样顶部迭代器上的每个 MoveNext() 实际上都会执行一系列调用，成本又是 O(d)。如果在每个节点上执行此操作，则调用的总成本为 O(nd)，最坏情况为 O(n^2)，最好情况为 O(n lg n)。你可以比两者都做得更好；没有理由不能在时间上呈线性。

诀窍是停止使用小型、脆弱的系统堆栈来跟踪下一步要做什么，并开始使用堆分配的堆栈来显式跟踪。

您应该将 Wes Dyer 的相关文章添加到您的阅读列表中：

https://blogs.msdn.microsoft.com/wesdyer/2007/03/23/all-about-iterators/

他在最后给出了一些编写递归迭代器的好技巧。

Answer 3

我不确定 TreeNodes，但您可以使用 System.Linq 来创建表单 IEnumerable 的 Controls 集合，例如

var ts = (from t in this.Controls.OfType<TextBox>
                 where t.Name.Contains("fish")
                 select t);
//Will get all the textboxes whose Names contain "fish"

抱歉，我不知道如何进行递归，关闭我的头顶。

Answer 4

基于 mrydengren 的解决方案：

public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
    Func<T, IEnumerable> selector,
    Func<T, bool> predicate)
{
    foreach (var item in collection.OfType<T>())
    {
        if(!predicate(item)) continue;

        yield return item;

        IEnumerable<T> children = selector(item).GetRecursively(selector, predicate);
        foreach (var child in children)
        {
            yield return child;
        }
    }
}


var theNodes = treeView1.Nodes.GetRecursively<TreeNode>(
    x => x.Nodes,
    n => n.Text.Contains("1")).ToList();

编辑：for BillW

Answer 5

我猜你正在要求这样的东西。

public static IEnumerable<T> <T,TCollection> GetNodesRecursively(this TCollection nodeCollection, Func<T, TCollection> getSub)
 where T, TCollection: IEnumerable
{   
    foreach (var theNode in )
    {
        yield return theNode;
        foreach (var subNode in GetNodesRecursively(theNode, getSub))
        {
            yield return subNode;
        }
    }
}

var all_control = GetNodesRecursively(control, c=>c.Controls).ToList();