Contenidors, memòria i iteradors

Per què?

Fins ara hem estat utilitzant els vectors.

En aquest tema aprendràs altres estructures d’aquest estil: piles, cues, llistes, conjunts i diccionaris.
Totes són contenidors: objectes que en guarden d’altres.
I totes són genèriques: les fas servir amb el tipus d’element que vulguis, entre angles (stack<int>, list<string>…), com el vector.

Estructures lineals

Una estructura lineal guarda els elements en fila, l’un darrere l’altre:

Cada element (menys l’últim) té un següent, i cada element (menys el primer) té un anterior.

El vector és una estructura lineal, i la majoria de les d’aquest tema també.
La diferència és com es guarden a la memòria.

Com es guarden a la memòria

La memòria de l’ordinador és una fila molt llarga de caselles.
Cada casella té un número, la seva adreça, que diu on és.
Les adreces s’escriuen en hexadecimal, amb 0x al davant.

1. El vector: tot seguit

Un vector guarda tots els elements en un sol bloc, l’un just a continuació de l’altre.
Es diu que el vector és contigu a la memòria.

Com que van seguits, el vector sap on és cada element sense buscar-lo: v[i] és $i$ caselles després de v[0].

• v[2] és a la casella $\texttt{0x101} + 2 = \texttt{0x103}$. Per trobar v[1000] tampoc no cal passar pels d’abans: és una suma, i ja hi és.

Alerta: el bloc no pot tenir forats.
Si insereixes o esborres un element enmig, tots els de després s’han de desplaçar.

2. Les estructures d’aquest tema: en nodes

Les estructures d’aquest tema no van en un sol bloc.

A la llista, per exemple, cada element es guarda en un tros a part, que es diu node, allà on hi hagi lloc a la memòria.
Cada node guarda l’element i l’adreça del node següent (i la de l’anterior).
Així la fila es manté, encara que els nodes estiguin repartits per tota la memòria.

Com que el lloc on és cada node no diu res, la llista es dibuixa en ordre, seguint les fletxes:

Això té dues conseqüències, al revés que el vector:

• Inserir o esborrar enmig és ràpid: només canvien les fletxes dels nodes del costat. No es mou cap altre element.

• Anar a la posició $k$ és lent: no hi ha cap suma que digui on és el node $k$. Has de començar pel primer i seguir les fletxes, $k$ vegades.

Alerta: aquesta diferència es nota molt quan hi ha molts elements.
En un vector d’un milió d’elements, inserir al principi vol dir desplaçar-ne un milió; en una llista, canviar dues fletxes.
En una llista d’un milió d’elements, arribar a l’últim vol dir seguir un milió de fletxes; en un vector, fer una suma.

Per això una llista no té l[k].
Per moure-t’hi necessites una altra cosa: un iterador.

Iteradors

Un iterador és un objecte que assenyala un element d’un contenidor, com si hi posessis el dit a sobre.
Des d’aquell element, el pots fer avançar al següent o retrocedir a l’anterior, seguint les fletxes.

Cada contenidor té el seu tipus d’iterador, que s’escriu amb el nom del contenidor al davant:

list<int>::iterator it;

Aquestes són les operacions bàsiques:

Per recórrer tota la llista, comences a begin() i avances fins que arribes a end():

list<int> l = {3, 8, 1, 5};
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    cout << *it << ' ';     // escriu 3 8 1 5
}

• El bucle s’atura quan it arriba al final, i per això mai no fa *it a end().

Ho veuràs amb calma a Llistes i iteradors.

Els contenidors de la STL

La biblioteca estàndard de C++ (la STL) ja porta aquests contenidors fets.
A PRO2 faràs servir sobretot aquests:

T és el tipus dels elements: el que poses entre angles.

Tens el resum de totes les operacions al chuletari.

Exercicis

list<int> l = {4, 9, 2, 7};
list<int>::iterator it = l.begin();
++it;
++it;
cout << *it << ' ';
--it;
cout << *it << ' ';