Parcurgere inversă în C++: capcana tipului size_t
Evită scăderea sub zero la indicii fără semn. Înțelege tipul returnat de size și verifică vectorul gol înainte de parcurgerea inversă.
În acest material
O buclă inversă poate părea corectă pe hârtie și totuși să nu se oprească la zero. Dacă indicele are un tip fără semn, condiția i≥0 este mereu adevărată. După scăderea din zero nu obții -1, ci o valoare pozitivă foarte mare, conform aritmeticii tipului fără semn.
De unde apare tipul fără semn
Dimensiunile containerelor sunt exprimate printr-un tip capabil să reprezinte numărări nenegative. size_t este un astfel de tip folosit frecvent pentru dimensiuni. Dacă deduci indicele direct din size(), nu trebuie să presupui că este int.
Problema apare și înaintea buclei. Pentru un container gol, expresia size()-1 scade unu din zero într-un tip fără semn. O conversie ulterioară la int nu este o metodă generală de a repara calculul deja făcut. Stabilește mai întâi dacă există un ultim element.
Numără elementele rămase
O formă robustă păstrează în i numărul de elemente încă de vizitat: începe cu i=n, continuă cât timp i>0 și accesează poziția i-1. Pentru n=3, indicii accesați sunt 2,1,0. Pentru n=0, corpul nu se execută deloc.
Această convenție funcționează atât pentru un tablou clasic cu dimensiune logică n, cât și pentru un vector al cărui n este size(). Diferența este numai sursa dimensiunii; regula accesului rămâne aceeași. Nu accesezi a[i] când i pornește de la n.
La o parcurgere inversă a trei elemente, indicii sunt 2,1,0. Decrementarea unui tip fără semn după zero nu produce -1, ci se înfășoară la o valoare mare.Mărește schema ↗
Când este rezonabil un indice int
Într-o problemă care garantează n≤1000, poți converti dimensiunea validată la int și folosi un indice cu semn care ajunge la -1. Conversia este justificată de limită. Pentru un container arbitrar de mare, aceeași presupunere poate pierde informație și trebuie reanalizată.
Nu amesteca mecanic int și dimensiuni fără semn în comparații. Avertismentele compilatorului privind semnul tipurilor semnalează tocmai locuri unde conversiile pot schimba sensul comparației.
Testele care contează
Verifică dimensiunile 0,1 și 3. La zero nu trebuie să existe niciun acces, la unu exact accesul la indicele 0, iar la trei ordinea trebuie să fie 2,1,0. Urmărește și valoarea indicelui după ultima iterație, nu doar valorile afișate.
Revezi dimensiunea logică a vectorului, tipurile numerice și buclele.
Întrebări frecvente
De ce nu se termină o buclă inversă cu size_t și i>=0?
size_t este fără semn, deci orice valoare a sa este nenegativă. După decrementarea lui zero apare o valoare foarte mare, iar condiția i >= 0 rămâne adevărată.
Ce risc are expresia v.size()-1 pentru un vector gol?
Scăderea se face într-un tip fără semn și nu produce un indice valid. Evită formarea ultimului indice înainte să verifici că există elemente.
Cum parcurg invers fără să scad din zero?
Poți porni un contor de la dimensiune și, cât timp este pozitiv, să procesezi poziția contor minus unu. Alternativ, folosește iteratori inversi; ambele variante trebuie să accepte corect containerul gol.