Terugwaarts itereren in C

Dit is korter dan sommige van mijn andere berichten, maar ik zie steeds mensen die dit fout doen. In het tijdperk van LLM's is dit zelfs erger geworden.

Stel dat je een buffer en een teller hebt en je moet hier om een of andere reden terugwaarts doorheen itereren:

_Bool find_last(size_t count, int *haystack, int needle, size_t *where);

Bijna iedereen kan de voorwaartse versie op de automatische piloot schrijven:

for(size_t i = 0; i < count; i++){
    if(haystack[i] == needle){
        *where = i;
        return 1;
    }
}
return 0;

Daarom proberen velen hetzelfde te doen, maar dan terugwaarts:

for(size_t i = count - 1; i >= 0; i--){
    // zoek needle
}

Maar dat werkt helemaal niet! i >= 0 is tautologisch waar (moderne compilers zullen hiervoor waarschuwen). Erger nog: als count 0 is, wordt i onmiddellijk SIZE_MAX.

Oké, dus ze proberen de volgende versie:

for(ssize_t i = count - 1; i >= 0; i--){
    // zoek needle
}

Dit werkt in de praktijk met een signed index, maar introduceert enkele problemen:

• Je indexvariabele is nu signed, wat problemen kan veroorzaken bij gebruik in expressies vanwege de conversieregels van C.
• ssize_t is een POSIX-standaard, dus op Windows moet je dit zelf definiëren.
• Als je type 32-bit is, kun je tegen promotieproblemen aanlopen en misschien zelfs tegen truncatieproblemen.
• Deze schrijfwijze van de loop is overgecompliceerd en vereist elke keer een speciale inspectie. Heb je de conditie in de tweede clausule wel correct geformuleerd?

De juiste methode

Het vermijden van deze problemen brengt ons bij de eigenlijke, juiste manier om terugwaarts te itereren in C:

for(size_t i = count; i--; ){
    // zoek needle
}

Dit is veel eenvoudiger! Laten we het analyseren:

De sleutel is de postdecrement-operator op i. Deze verlaagt i met één, maar geeft de waarde terug die i had vóór de operatie. In dit geval betekent dit dat i in het lichaam van de loop altijd binnen de grenzen valt, aangezien de waarde na initialisatie wordt verlaagd (waardoor deze maximaal count - 1 is), terwijl de conditie controleert of de waarde eerder 0 was; in dat geval eindigt de loop. i zal wrappen, maar unsigned wrap-around is goed gedefinieerd in C, dus dat is geen probleem.

De definitieve versie

_Bool find_last(size_t count, int *haystack, int needle, size_t *where){
    for(size_t i = count; i--; ){
        if(haystack[i] == needle){
            *where = i;
            return 1;
        }
    }
    return 0;
}

Door het op deze manier te doen, hoef je niet te klooien met het converteren naar een signed loop-index. Kijk hoe simpel die loop is! Je kunt in één oogopslag zien of iemand de reverse loop correct heeft geïmplementeerd of niet.

Dus alsjeblieft! Als je iemand ziet die terugwaarts probeert te itereren, laat ze dan deze methode zien!

***

Alle code in dit artikel is vrijgegeven in het publieke domein.