Why can't I change a set I'm iterating over?

Question

I've seen solutions and workaround suggested, but couldn't find an explanation of the choice not to allow changing sets while iterating over them. Can you please help me understand why this is OK

In [1]: l = [1]

In [2]: for i in l:
            l.append(2*i)
            if len(l)>10:
                    break

In [3]: l
Out[3]: [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

while this is not OK

In [4]: l = {1}

In [5]: for i in l:
            l.add(2*i)
            if len(l)>10:
                    break
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-5-b5bdff4a382b> in <module>()
----> 1 for i in l:
      2         l.add(2*i)
      3         if len(l)>10:
      4                 break
      5

RuntimeError: Set changed size during iteration

What's so bad about changing a set while iterating?

I am aware that the order in set is not defined, so next might have a hard time. Is this the reason?

Martijn Pieters · Accepted Answer · 2016-07-17T20:56:35.310

7

A set is backed by a hash table (see Why is the order in Python dictionaries and sets arbitrary?). Entries in the set are slotted in to that table based on their hash, which in turn determines their order.

Adding or removing items to that hash table will alter the iteration order, sometimes materially as the table can be re-sized (where all existing entries are re-slotted based on the new table size). Because of this iteration can't continue the moment the set has been altered; you'd otherwise are liable to see the same values again, even in a different order.

Lists, on the other hand, have a well-defined ordering. Inserting or deleting items can alter that order, but in a well-defined way. A list iterator thus simply can use an ever-increasing index to find a 'next' item, until that index matches the current list length.

edited Jul 17 '16 at 20:56

answered Jul 17 '16 at 15:50

Martijn Pieters

1,048,767
296
4,058
3,343

Are you sure that the order of iteration in lists is defined, and not simply "falls out of the implementation" and might change? – Elazar Jul 17 '16 at 15:55
@Elazar: yes, I'm sure. Lists have a defined order. Even if you inserted or deleted items, the order is still clearly defined from one manipulation to the next. – Martijn Pieters Jul 17 '16 at 15:56

Elazar · Answer 2 · 2016-07-17T15:53:16.833

0

Forcing the implementation of a collection to allow changing while iterating will restrict it to have very bad performance. Think about linked list and the simple iterator that points to a node. Think about dynamic array that expands and needs to reallocate memory, (hash tables, that is the implementation of dict and set, uses such an array. lists are implemented with such an array) etc.

edited Jul 17 '16 at 15:53

answered Jul 17 '16 at 15:47

Elazar

20,415
4
46
67

score 0 · Answer 3 · edited May 23 '17 at 12:32

First you need to understand a bit about how dicts work. Sets work the same way (in terms of storing keys) under the covers. I don't think I could ever explain this better than Brandon Rhodes at PyCon (the talk answers this question at some point and is a phenomenal reference for the data structures underlying dicts and sets).

Basically for dicts/sets the order of iteration can change as items are added or removed. The same is not true of lists.

Why can't I change a set I'm iterating over?

3 Answers3

Linked