Siirry sisältöön

C/Ehdollinen poisto taulukosta

Wikikirjastosta
< C

Varsin usein on tarpeen käydä läpi taulukko, poistaen sieltä jotkin alkiot siten että jäljelle jäävät siirtyvät taaksepäin. Tyypillinen, mutta huono tapa tehdä tämä on käyttää for-looppia, jossa käydään alkiot järjestyksessä ja jokaisen poiston jälkeen siirretään loppuja taaksepäin yhden alkion verran. Tämä on paitsi hidasta, myös erittäin virhealtista, sillä jos loopin indeksi kuitenkin kasvaa myös poiston jälkeen, tulee vahingossa ohitettua poistetusta alkiosta seuraava.

Parempi ratkaisu on käyttää kahta iteraattorimuuttujaa, joista yksi ilmaisee lukukohdan ja toinen kirjoituskohdan:

 #include <stdio.h>
 
 int main(void) {
   int array[10] = { 10, 12, 55, 7, 42 };
   size_t size = 5;
 
   // Remove all odd values
   size_t w = 0;  // Write iterator
   for (size_t r = 0; r < size; ++r) { // Read all elements
     if (array[r] % 2 == 1) continue;  // Is the value odd?
     array[w++] = array[r];  // Copy value from position r to position w, then increment w
   }
   size = w;  // Only w elements remain, the rest is garbage
 
   // Print the array
   for (size_t i = 0; i < size; ++i) {
     if (i > 0) printf(", ");
     printf("%d", array[i]);
   }
   printf("\n");
 }

Alussa r ja w juoksevat kumpikin samoilla arvoilla, siten että kopiointia suoritetaan itse asiassa paikoillaan, siis array[0] = array[0] ja array[1] = array[1]. Tällainen operaatio ei toki varsinaisesti tee mitään, mutta siitä ei ole harmiakaan (ei kannata välittää optimoinnista - kääntäjä kyllä osaa sen oikein hyvin). Kun luvun 55 kohdalla suoritetaan poisto, eli continue hyppää loopin seuraavalle kierrokselle, kopioinnin ohi, jää w jälkeen r:stä ja tietoa aletaan oikeasti liikuttaa paikasta toiseen, siis parin ohitetun alkion jälkeen kopioidaan luku 42 (array[2] = array[4]) ja lopulta w:n arvoksi jää 3, joka onkin taulukon lopullinen koko.