What's the most (performance) efficient and readable way to 'split' a generic list based on a condition?

(highly simplified example) I have a generic list of strings:

var strings = new List<string> { "abc", "owla", "paula", "lala", "hop" };

I'm looking for the most efficient way to split this list into a list with elements that meet a condition and a list of elements that don't meet that same condition.

Func<string, bool> condition = s => s.IndexOf("o") > -1;
Predicate<string> kickOut = s => s.IndexO开发者_开发百科f("o") > -1;
var stringsThatMeetCondition = strings.Where(condition);
strings.RemoveAll(kickOut);
var stringsThatDontMeetCondition = strings;

Is there a way to do this with looping only once through the original list?

---

Use some linq:

var matches = list.Select(s => s.IndexOf("o") > -1).ToList();
var notMatches = list.Except(matches).ToList();
list.Clear();
list.AddRange(matches);

Update: as has been mentioned in the comments, be careful mutating the list as linq methods try to be on-demand, they will not iterate the list until you start looking into the IEnumerable. However in my case, I call ToList, which effectively causes it to run through the entire list of items.

---

This would do it:

IEnumerable<T> FilterAndRemove(this List<T> list, Func<T, bool> pred)
{
  List<T> filtered = new List<T>();
  int i = 0;
  while(i < list.Count)
  {
     if (pred(list[i]))
     {
        filtered.Add(list[i]);
        list.RemoveAt(i);
     }
     else
     { 
        ++i;
     }
  }
  return list;
}

But am sure you have already thought of something similar. Can you please update your answer with the kind of efficiency that you seek?

Note that two filtering runs with pred and !pred over the original list would still be O(n) and not at all inefficient. Especially considering that you'd get the full benefit of lazy evaluation for both result sets. See also Rob's answer.

This algorithm is in O(n^2).

Instead removing each element, you can also collect them in a new list and copy them over to the input list before returning. This will also get you O(n).

One more option for O(n) would be switching to a linked list.

---

Why not just use

var stringsThatMeetCondition = strings.Where(condition);
var stringsThatDontMeetCondition = strings.Where(x => !condition(x));

Of course, you end up applying the condition to each element in the list twice. To avoid this you might want to write a generic splitting function, which wouldn't be as neat.

---

Func<string, bool> condition = ...;
var groupedStrings = strings.GroupBy(condition)
var stringsMeetingCondition = groupedStrings.FirstOrDefault(g => g.Key);
var stringsNotMeetingCondition = groupedStrings.FirstOrDefault(g => !g.Key);