LINQ equivalent of std::partition

Question

What is a LINQ-based function that places all items which satisfy a predicate at the front of the sequence, like C++'s std::partition?

Answer 1

If I understand what you're trying to achieve, a simpler solution would be OrderByDescending:

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

This works because bool implements IComparable<bool> with false coming before true. So items for which predicate evaluates to true will be placed first in the result set.

And here's a hand-made implementation, just in case you're interested. I haven't done any benchmarks but this one might actually be faster.¹

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: The hand-made solution is O(n), but OrderBy is considered to be O(n log n). However, depending on the implementation details of the OrderBy method, they might perform nearly identically.}