...
Eroare Algoritmi și structuri de date · Stive, cozi și liste înlănțuite

RuntimeError: deque mutated during iteration

Pe scurt

Ai adăugat sau scos elemente dintr-un deque în timp ce îl parcurgeai cu for. Pentru o coadă BFS nu parcurge cu for: folosește while coada: nod = coada.popleft(), iar vecinii noi îi adaugi cu append.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

for x in coada parcurge un deque cu un iterator care verifică, la fiecare pas, dacă deque-ul a fost modificat. Dacă între timp ai făcut append, appendleft, pop sau popleft, iteratorul se oprește cu RuntimeError: deque mutated during iteration.

În algoritmi apare aproape mereu la BFS: cineva scrie for nod in coada: și adaugă vecinii în aceeași coadă. Cu o listă obișnuită codul „merge” (lista acceptă append în timpul parcurgerii), de aceea greșeala apare abia după ce treci la deque.

Coada se consumă cu while coada: și popleft(): fiecare nod e scos o singură dată, iar vecinii adăugați sunt procesați la rândul lor. Linia din stivă arată for-ul, nu append-ul care a modificat coada.

De ce apare: cauzele frecvente

1BFS cu for peste coadă

Greșit
PYTHON
coada = deque([start])
for nod in coada:
    for v in vecini[nod]:
        coada.append(v)
Corect
PYTHON
coada = deque([start])
while coada:
    nod = coada.popleft()
    for v in vecini[nod]:
        coada.append(v)

while verifică doar dacă mai sunt elemente; popleft scoate nodul curent fără un iterator care să se strice.

2Ștergere în timpul parcurgerii

Greșit
PYTHON
for x in fereastra:
    if x < prag:
        fereastra.remove(x)
Corect
PYTHON
fereastra = deque(x for x in fereastra if x >= prag)

Construiește un deque nou cu elementele păstrate în loc să-l modifici pe cel parcurs.

3Procesare pe niveluri

Greșit
PYTHON
for nod in coada:
    coada.popleft()
    ...
Corect
PYTHON
for _ in range(len(coada)):
    nod = coada.popleft()
    ...

range(len(coada)) fixează numărul de noduri al nivelului curent înainte de modificări.

Repară tu

Repară eroarea, direct în pagină

Funcția ordine_bfs(start, vecini) trebuie să dea ordinea în care BFS-ul vizitează stațiile. Codul parcurge coada cu for și dă RuntimeError: deque mutated during iteration. Repar-o ca să afișeze A B C D E.

Codul care dă eroarea
PYTHON
from collections import deque

def ordine_bfs(start, vecini):
    coada = deque([start])
    vazut = {start}
    ordine = []
    for nod in coada:
        ordine.append(nod)
        for v in vecini[nod]:
            if v not in vazut:
                vazut.add(v)
                coada.append(v)
    return ordine

vecini = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': []}
print(' '.join(ordine_bfs('A', vecini)))
După reparație, programul afișează
A B C D E
Indiciu

Folosește while coada: și scoate nodul curent cu coada.popleft().

Alte forme ale mesajului

  • RuntimeError: deque mutated during iteration
  • RuntimeError: dictionary changed size during iteration

Cum o eviți pe viitor

Tratează o coadă ca pe o coadă, nu ca pe o listă: o golești cu while coada: și popleft(). Dacă ai nevoie de nivelurile BFS, fixează dimensiunea nivelului cu range(len(coada)) înainte de a scoate. Pentru filtrare, construiește o structură nouă. Aceeași regulă se aplică dicționarelor și set-urilor.

Întrebări frecvente

De ce cu o listă nu primesc eroarea?

Iteratorul listei doar crește un index și nu verifică modificările. BFS-ul cu for nod in lista și append chiar funcționează, dar lista nu se golește niciodată și ține tot în memorie.

Pot parcurge o copie: for nod in list(coada)?

Nu dă eroare, dar nodurile adăugate în timpul parcurgerii nu sunt procesate. Pentru BFS ai nevoie de while.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.