Recorreguts, cerques i modificació de llistes

Per què esquemes?

Gairebé tots els problemes de llistes que trobaràs (a l’examen, al laboratori, al Jutge) són variacions de quatre o cinc idees. Si les reconeixes, el codi surt gairebé sol. Si cada vegada comences de zero, t’equivocaràs en els detalls: un iterador que avança de més, un end() desreferenciat, un element que no es comprova.

Aquest capítol recull aquests esquemes, amb un exemple de cadascun. Al tema de disseny iteratiu els tornaràs a veure, amb vectors i justificant per què són correctes.

1. Recorregut: visitar-los tots

Quan has de mirar tots els elements (sumar-los, comptar-ne, escriure’ls, modificar-los tots):

for (list<T>::const_iterator it = l.begin(); it != l.end(); ++it) {
    tractar *it
}

(Dins d’una plantilla, has d’escriure typename list<T>::const_iterator, o simplement auto.)

// Pre: cert. Post: retorna la suma dels elements de l.
int suma(const list<int>& l) {
    int s = 0;
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it) s += *it;
    return s;
}

Si només llegeixes, també pots escriure for (int x : l) s += x;. Per modificar els elements, cal un iterator normal (i la llista per referència):

// Pre: l = [a1, ..., an]. Post: l = [k*a1, ..., k*an].
void multiplica(list<int>& l, int k) {
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) *it *= k;
}

2. Cerca: aturar-se quan el trobes

Quan busques un element que compleixi una condició i, quan el trobes, ja no cal mirar-ne més:

list<T>::const_iterator it = l.begin();
while (it != l.end() and not condició(*it)) ++it;
// aquí: o bé it == l.end() (no hi és), o bé *it compleix la condició

// Pre: cert. Post: retorna si hi ha algun element negatiu a l.
bool hi_ha_negatiu(const list<int>& l) {
    list<int>::const_iterator it = l.begin();
    while (it != l.end() and *it >= 0) ++it;
    return it != l.end();
}

Dues coses que has de mirar sempre en una cerca:

• L’ordre de la condició del while. Primer it != l.end(), després *it. L’and s’atura si la primera part és falsa, així que mai no es desreferencia end(). Si les gires, quan l’element no hi és, *it es fa amb it == l.end().
• Què vol dir cada sortida. Després del bucle, si it != l.end(), l’has trobat i it hi apunta. Pots fer-lo servir (per consultar-lo, modificar-lo, esborrar-lo o inserir-hi davant).

3. Cercar i modificar: inserir ordenadament

Una cerca que acaba amb una modificació. Tens una llista de puntuacions ordenada de gran a petit (un rànquing) i n’arriba una de nova. Has de trobar el primer element més petit o igual que la nova i inserir-la davant.

// Pre: l està ordenada de gran a petit.
// Post: s'hi ha afegit x i continua ordenada de gran a petit.
void insereix_ordenat(list<int>& l, int x) {
    list<int>::iterator it = l.begin();
    while (it != l.end() and *it > x) ++it;
    l.insert(it, x);
}

list<int>::iterator it = l.begin();
while (it != l.end() and *it > x) ++it;
l.insert(it, x);

Fixa’t que funciona sense cap cas especial:

• Si x és la més gran de totes, el bucle no avança i s’insereix al principi.
• Si és la més petita, it arriba a end() i s’insereix al final.
• Si la llista és buida, it == l.end() des del principi i x passa a ser l’únic element.

Això és gràcies a com està definit insert: insereix davant de l’iterador, i davant d’end() vol dir al final.

4. Dos iteradors

De vegades cal recórrer la llista des de dues bandes alhora. Una llista és capicua si es llegeix igual en tots dos sentits: $[4, 8, 5, 8, 4]$, $[4, 8, 8, 4]$ i $[7]$ ho són. Posem un iterador al principi i un altre al final, i els anem acostant:

// Pre: cert. Post: retorna si l es llegeix igual d'esquerra a dreta que de dreta a esquerra.
bool capicua(const list<int>& l) {
    list<int>::const_iterator ini = l.begin();
    list<int>::const_iterator fi = l.end();
    for (int i = 0; i < int(l.size()) / 2; ++i) {
        --fi;
        if (*ini != *fi) return false;
        ++ini;
    }
    return true;
}

list<int>::const_iterator ini = l.begin();
list<int>::const_iterator fi = l.end();
for (int i = 0; i < int(l.size()) / 2; ++i) {
  --fi;
  if (*ini != *fi) return false;
  ++ini;
}
return true;

fi comença a end() i retrocedeix abans de mirar-lo, perquè end() no és cap element. Amb $n$ elements es fan $\lfloor n/2 \rfloor$ comparacions.

5. Fusió de llistes ordenades

Tens dues llistes ordenades de petit a gran i vols afegir a la primera tots els elements de la segona, mantenint l’ordre.

La manera lenta: per a cada element de b, insereix_ordenat a a. Cada inserció recorre a des del principi: amb $n$ elements a a i $m$ a b, fins a $\Theta(n \cdot m)$. Amb dues llistes de 10.000 elements, cent milions de passos.

La manera ràpida: com que totes dues estan ordenades, recorrem-les alhora amb dos iteradors. L’element de b que toca inserir va davant del primer element d’a que no és més petit. I l’element següent de b serà més gran, així que no cal tornar enrere a a.

// Pre: a i b estan ordenades de petit a gran.
// Post: a conté tots els elements de a i de b, ordenats; b no canvia.
void fusiona(list<int>& a, const list<int>& b) {
    list<int>::iterator ia = a.begin();
    list<int>::const_iterator ib = b.begin();
    while (ia != a.end() and ib != b.end()) {
        if (*ib < *ia) {
            a.insert(ia, *ib);  // el de b va davant del de a
            ++ib;
        }
        else ++ia;
    }
    while (ib != b.end()) {     // si en queden a b, van al final (ia == a.end())
        a.insert(ia, *ib);
        ++ib;
    }
}

while (ia != a.end() and ib != b.end()) {
  if (*ib < *ia) {
      a.insert(ia, *ib);
      ++ib;
  }
  else ++ia;
}
while (ib != b.end()) {
  a.insert(ia, *ib);
  ++ib;
}

Cada volta del primer bucle avança un dels dos iteradors, i el segon bucle avança ib: en total, com a molt $n + m$ passos. Cost $\Theta(n + m)$. És la mateixa idea que la fusió de cues.

6. splice: moure una llista sencera

a.splice(it, b) mou tots els elements de b dins d’a, davant de it. b queda buida.

list<int> x = {1, 2, 3};
list<int> y = {10, 20};
list<int>::iterator it = x.begin();
++it;               // it apunta al 2
x.splice(it, y);    // x = [1, 10, 20, 2, 3], y buida, it continua al 2

El gran avantatge: costa $\Theta(1)$, sigui quina sigui la mida de les llistes. No es copia cap element: només es reenganxen els extrems (veuràs com al tema de punters). Per concatenar dues llistes: a.splice(a.end(), b).

Crear llistes noves

Si vols conservar la llista original i obtenir-ne una de nova, tens dues opcions:

// Una funció que la retorna:
// Pre: cert. Post: retorna una llista amb els elements positius de l, en el mateix ordre.
list<int> positius(const list<int>& l);

// Una acció amb un paràmetre de sortida:
// Pre: r és buida. Post: r conté els elements positius de l, en el mateix ordre.
void positius(const list<int>& l, list<int>& r);

La funció, per exemple, és un recorregut que va afegint al final:

list<int> positius(const list<int>& l) {
    list<int> r;
    for (int x : l) {
        if (x > 0) r.push_back(x);
    }
    return r;
}

Totes dues són correctes. La funció és més còmoda d’usar (list<int> p = positius(l);), i els compiladors actuals eviten copiar la llista que retornes. L’acció et dona més control: per exemple, pots afegir els resultats a una llista que ja tenies.

Errors habituals

Exercicis

// Pre: l no és buida. Post: retorna quants elements de l són més grans que la mitjana.
int per_sobre_mitjana(const list<int>& l) {
    double mitjana = double(suma(l)) / l.size();
    int n = 0;
    for (int x : l) {
        if (x > mitjana) ++n;
    }
    return n;
}

// Pre: cert. Post: retorna la posició (començant per 0) de la primera aparició de x a l,
//      o -1 si no hi és.
int posicio(const list<int>& l, int x) {
    int pos = 0;
    list<int>::const_iterator it = l.begin();
    while (it != l.end() and *it != x) {
        ++it;
        ++pos;
    }
    if (it == l.end()) return -1;
    return pos;
}

// Pre: cert. Post: s'han esborrat els elements iguals a l'anterior.
void treu_repetits_seguits(list<int>& l) {
    if (l.empty()) return;
    list<int>::iterator ant = l.begin();
    list<int>::iterator it = ant;
    ++it;
    while (it != l.end()) {
        if (*it == *ant) it = l.erase(it);
        else {
            ant = it;
            ++it;
        }
    }
}

bool capicua2(const list<int>& l) {
    list<int>::const_iterator ini = l.begin();
    list<int>::const_iterator fi = l.end();
    while (ini != fi) {
        --fi;
        if (ini == fi) return true;      // senar: s'han trobat al mig
        if (*ini != *fi) return false;
        ++ini;
    }
    return true;                         // parell (o buida): s'han creuat
}

// Pre: l = [a1, ..., an]. Post: l = [an, ..., a1].
void inverteix(list<int>& l) {
    if (l.empty()) return;
    list<int>::iterator it = l.begin();
    ++it;  // el primer ja és a lloc: serà l'últim quan els altres passin davant
    while (it != l.end()) {
        l.push_front(*it);
        it = l.erase(it);
    }
}