Removing items from a list during iteration

Standard practice is to iterate over the list backwards like so:

for( int i = items.Count - 1; i >= 0; --i )
{
    if( shouldRemove( items[i] ) )
        item.RemoveAt( i );
}

This approach doesn’t use any extra memory which is nice, but it’s
O((n/2)2) run time (assuming RemoveAt() is O(n)) is less so.

A clever approach I found from Abe Pralle that is O(n) is to fill the gaps as you remove and iterate and then finally truncate the list at the end. Another way to think about it is bubbling the items that need removal to the end of the list.

int gap = 0;
for( int i = 0; i < items.Count; ++i )
{
    if( !shouldRemove( items[i] ) )
    {
        items[gap] = items[i];
        ++gap;
    }
}

items.RemoveRange( gap, items.Count - gap );

Pretty cool!