Deleting from a list while iterating

["Martin v. Löwis"]

Rhamphoryncus schrieb:
>> This is different from the other approaches in that it doesn't
>> modify items. If you wanted a new list, you could incrementally
>> build one already in the first pass, no need to collect the
>> indices first (as BlackJack explains).
> 
> I didn't feel this distinction was worth mentioning, since "oldlist[:]
> = newlist" is so trivial.  The only solution that really avoids making
> a copy is the reverse-iteration one.

The distinction is relevant for performance, as the slice assignment
has a complexity linear with the number of elements.

Whether making a copy is expensive depends on the precise data: the
solution that makes the copy in reverse may have quadratic complexity
(if the number of removed elements increases with the list size);
the version that appends all remaining elements to a new list and
then does slice assignment should behave better-than-quadratic
(in recent versions, it should give you linear performance).

Regards,
Martin