Changing a collection during a loop in Python

Why this matters

A program often needs to go through a list and throw some items away. A shopping cart removes sold-out products. A log reader drops empty lines. A game removes dead enemies after each turn. The loop that does this looks simple, and the first version usually runs without an error.

The trouble shows up on some inputs only. In Python, a list loop may skip some items and print a wrong answer with no error at all. A dict or set loop fails loudly with RuntimeError, but only on the first removal. Both problems come from the same cause: the loop keeps a pointer (a stored position) to a place in the collection, and the removal moves things around under that pointer.

This lesson covers that cause, shows why each container behaves the way it does, and ends with the safe ways to remove items. The lessons on lists and on dicts in this module explained how each container stores its items. This lesson uses that idea and does not repeat it.

The idea: a bookmark in a book that is being rewritten

An iterator is a bookmark. It remembers where you are in a collection, and it knows how to move to the next item. A for loop in Python creates an iterator for you.

Imagine you are reading a book and you hold a bookmark at page 40. A friend tears out page 12. Now page 40 is the 39th page, and your bookmark still says 40. You open to the bookmark and read the wrong page, or you skip one.

A list works the same way. A list iterator stores a position, such as "item number 2". If an item before that position is removed, the item you wanted moves to position 1, and the position now points at a different item. Python's list iterator does not check for this change. It keeps counting, so the loop moves past the item that slid into the gap.

A first example: a list that loses an item

Here is a list of numbers. The loop removes every even number as it goes.

The output is:

[1, 3, 5]

This answer is right, but only by luck. The loop removes 2, which shifts 3 into position 1, where 2 was. The loop then moves on to position 2, which now holds 4. So 3 is never checked. The loop removes 4 next. The list now has three items, so the loop ends without checking 5. The skipped numbers, 3 and 5, are odd, so the answer is right by luck.

Change the input so the skipped number is even, and the answer is wrong:

The output is:

[2, 2, 3] -> [2, 3]

The first 2 is removed, which shifts the second 2 into position 0. The loop moves on to position 1, which holds the 3. The second 2 is skipped and stays in the list. The program prints a wrong answer, and nothing in the output says so.

Here is the rule for lists: removing an item during a loop over the same list moves the later items one place to the left, so the loop skips the item that moves into the gap. The loop gives no warning.

Removing the last item never causes a skip, because nothing moves into its place. Removing an item at or before the loop's position moves the next item into a slot the loop has already passed, so that item is skipped. A test with a short list may pass while a longer list fails.

Dicts and sets raise an error

Dicts and sets check their size on every step of a loop. Adding or removing a key during the loop makes the next step raise RuntimeError. Python does not skip items in these cases. It stops the loop at once, which is easier to debug.

The output is:

caught: Set changed size during iteration

The same error appears for a dict, with the message dictionary changed size during iteration. The error appears on the step after the change, so the loop body has already run for the item that caused it. The error is a safe failure, and the fix is the same as for the list case: loop over a copy.

Safe ways to remove items in Python

There are four safe patterns. Pick the one that matches what you need.

A list comprehension

A list comprehension builds a new list that keeps the items you want. It is the shortest form, and it is safe because the loop never changes the list it reads. When the test is a single condition, this is usually the best choice.

The output is:

['java', 'fun']

The name words now refers to the new list. If other names point to the old list and must see the change, use slice assignment instead. The line words[:] = [w for w in words if len(w) >= 3] replaces the items inside the same list object, so every name that points to it sees the new items.

A while loop with an index

A while loop that keeps its own index can remove items safely, as long as the index moves forward only when nothing was removed. After a removal, the item that slid into the gap has not been checked yet, so the index must stay where it is.

The output is:

[4, 7, 3]

The index i is the loop's own bookmark. When nums[i] is negative, the code deletes it, and the next value moves into position i. The index stays put, so that value is checked on the next pass. When the value is kept, the index moves forward. This pattern works well when you need the position as well as the value, because the index is always correct.

A backward index loop

You can also start at the end and move backwards. Removing an item at position i only moves items that come after i. Those have already been checked, so the loop does not miss anything.

The output is:

[1, 2, 4, 5]

The range range(len(back) - 1, -1, -1) counts down from the last index to 0. This pattern is harder to read than a comprehension, so use it only when the position matters.

Collect first, then remove

A fourth option is to make a list of the items to remove, and then remove them after the loop. This is the simplest to reason about, and it costs some extra memory. Use it when the test is complicated or when you need to log each removed item.

For dicts and sets, this is the usual pattern. The next section uses it.

Dicts behave the same way

A dict has the same trap, and it raises the error shown earlier. The safe patterns for dicts are a comprehension that builds a new dict, or a list of keys to delete after the loop.

The output is:

{'pear': 3}

The list comprehension reads the dict first and gives a plain list of the keys to remove. The for loop then removes them from the dict, and the loop is not reading the dict at that time, so there is no error. A dict comprehension does the same job in one line: stock = {k: v for k, v in stock.items() if v > 0}.

A longer example: drop long tasks and keep a total

Real loops often need more than a single test. They read the item, add it to a total, print it, and then decide whether to remove it. The index pattern handles all of these, as long as every change goes through the index.

The output is:

dropping report
dropping lunch
left: [Task(name='email', minutes=5), Task(name='call', minutes=30)]
removed minutes: 135

The loop body does three things with each item: it reads the item, it updates a total, and it removes the item. The removal happens at the index i, and the index moves forward only when the item is kept, so every task is checked exactly once.

Removing consecutive repeats

This example removes an item when it equals the item just before it in the output. The check looks at the last kept item, not at the list being read, so the loop does not need to step back through the list.

The output is:

[1, 2, 3, 1]

The last 1 is kept, because it is not next to another 1. The check out and out[-1] == x first asks whether out has any items. Without that test, the first value would look at out[-1] on an empty list and raise IndexError.

Iterators and the C++ comparison

In C++, an iterator for a vector usually holds the address of one item. When an item is erased, the later items move, and the iterator can point at the wrong item or at memory that no longer holds one. The library does not check, so the program may crash or print a wrong answer. The C++ standard calls the change invalidation, and using the iterator afterwards is undefined behavior. The fix in C++ is to use the value that erase returns, which is a valid iterator to the next item.

Python's list iterator does not hold an address. It holds an index, and it checks the current length on each step. That is why Python never crashes in this case and why it skips items instead. The bug has the same shape in both languages, but the symptom differs. In Python the symptom is a wrong answer with no error for lists, and a RuntimeError for dicts and sets.

Common mistakes

Calling remove or del inside a loop over the same list. The later items move, and the loop skips one. Use a comprehension, a while loop with an index, or a backward index loop.

Assuming a silent run is a correct run. Removing the first 2 from [2, 2, 3] prints an answer and raises no error, but the second 2 stays. A test that never has two equal items in a row can hide this bug.

Advancing the index after a removal. In a while loop, i += 1 must run only when nothing was removed. If the index moves after a delete, the item that slid into the gap is skipped.

Looping over a dict and deleting from it. This raises RuntimeError. Loop over a list of keys instead, as the dict example shows.

Using del on an item that is not there. del lst[i] raises IndexError when i is outside the list. Check the index against len(lst) in the loop condition.

Practice

Exercise 1. What does this Python code print? Does it raise an error?

xs = ["a", "b", "c", "d"]
for s in xs:
    if s == "c":
        xs.remove(s)
print(xs)

Show the answer: it prints ['a', 'b', 'd'] and raises no error. The removed item is "c", which is the third of four. After the removal the list has three items. The loop moves to position 3, sees that it is past the end, and stops. The item "d" is skipped. It moves into position 2, which the loop has already passed, so the loop never checks it.

Exercise 2. Write a loop that removes every word shorter than 3 characters from a list named words. Use a while loop with an index.

Show the answer:

i = 0
while i < len(words):
    if len(words[i]) < 3:
        del words[i]
    else:
        i += 1

With words equal to ["go", "java", "is", "fun", "a"], the result is ["java", "fun"]. The same result comes from words[:] = [w for w in words if len(w) >= 3].

Exercise 3. You have a dict named scores. Remove every entry whose score is below 50. Do not loop over the dict while you delete from it.

Show the answer:

for name in [n for n, s in scores.items() if s < 50]:
    del scores[name]

With scores equal to {"Ana": 72, "Ben": 40, "Cy": 55}, the result is {"Ana": 72, "Cy": 55}. A dict comprehension gives the same result: scores = {n: s for n, s in scores.items() if s >= 50}, but it makes a new dict rather than changing the old one.

Exercise 4. Remove every negative number from a list nums and keep the order of the rest. Do it in place, so that other names that point to the list see the change.

Show the answer: nums[:] = [x for x in nums if x >= 0]. The slice on the left replaces the items inside the same list object. With nums equal to [4, -2, 7, -9, 3], the result is [4, 7, 3].

Exercise 5. Run the list example that removes 2 from [2, 2, 3]. The output is [2, 3], which is wrong, because both 2s should be removed. Change the loop so that every 2 is removed. Explain what changed.

Show the answer: the new loop must not skip the item that moves into the gap. A while loop with an index, or a comprehension that drops every 2, removes both twos. The output is [3]. The original loop removed one 2 and skipped the second one, because the second 2 moved into the spot the loop had already passed. The change is that the new code either keeps its place after a removal or builds a new list.

Summary

• An iterator is a bookmark into a collection. Changing the collection can make the bookmark point at the wrong item.
• A for loop over a list does not check for changes, so removing an item skips the item that moves into its place. The result can be wrong with no error.
• A for loop over a dict or set raises RuntimeError on the next step after a size change.
• Use a list comprehension, a while loop with an index that moves only when nothing was removed, a backward index loop, or a list of items to remove after the loop.
• Slice assignment, words[:] = ..., changes a list in place and keeps every name pointing to it.