LINQ等效于std::分区

Question

什么是基于LINQ的函数，它将满足谓词的所有项放在序列的前面，比如C++的std::partition？

Answer 1

如果我理解您想要实现的目标，一个更简单的解决方案是OrderByDescending:

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    return s.OrderByDescending(predicate);
}

这是因为bool实现了IComparable<bool>，而false位于true之前。因此，predicate评估为true的项目将被放在结果集中的第一位。

这里有一个手工实现，以防万一你感兴趣。我还没有做任何基准测试，但这次可能会更快¹

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    List<T> falses = new List<T>();
    foreach(var t in s) 
    {
        if (predicate(t)) 
        {
            yield return t;
        }
        else
        {
            falses.Add(t);
        }
    }
    foreach (var t in falses)
    {
        yield return t;
    }
}

^{1:手工溶液是O(n(，但OrderBy被认为是O(nlogn。然而，根据OrderBy方法的实现细节，它们的执行可能几乎相同}

Answer 2

我的最佳镜头：

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    var split = s.GroupBy(predicate);
    return split
        .Where(kv => kv.Key)
        .Single()
        .Concat(split
            .Where(kv => !kv.Key)
            .Single());
}

Answer 3

使用SelectMany，您可以改进自己的答案：

IEnumerable<T> Partition<T>(IEnumerable<T> s, Func<T, bool> predicate)
{
    return s.GroupBy(predicate).SelectMany(xs => xs);
}