Llistes i Iteradors

Els vectors, com que tenen els elements consecutius a memòria, tenen problemes a l'hora d'inserir i esborrar, perquè han de moure tots els elements. Això implica que aquestes operacions són $O(n)$ en vectors, és a dir: amb un cost proporcional a la mida del vector.

En aquest tema introduïm un nou contenidor, la llista, la característica principal del qual és que permet insercions a qualsevol punt amb un cost $O(1)$, és a dir, independent de la mida.

Les llistes permeten inserir i esborrar ràpidament en qualsevol posició

Una llista és un contenidor que permet inserir i esborrar elements en qualsevol posició de manera ràpida. Per aconseguir-ho, està formada per nodes (com els anells d'una cadena) enllaçats entre si (simple o doblement).

Les llistes NO tenen índexs, perquè no hi ha manera de calcular la posició d'un element a partir del primer (com en el cas dels vectors). Només es pot accedir als elements mitjançant iteradors.

En llistes, inserir i esborrar és O(1), però accedir i recórrer és més car

Inserció i esborrat: Degut a l'estructura interna, inserir o esborrar un element en una llista només requereix canviar 4 punters (4 adreces de memòria), així que la inserció i l'esborrat són $O(1)$, és a dir, independents de la mida de la llista.

Recorregut: Però el preu a pagar és que, com que els elements no són consecutius a memòria, un recorregut és molt més lent (en dos ordres de magnitud!). Això és degut a la velocitat de la jerarquia de memòria, als nivells de cache i al fet que accedir a posicions seqüencialment accelera l'accés. (És interessant entendre els temps d'accés de diverses operacions.)

Accés aleatori: En un cas encara pitjor, per accedir a una posició arbitrària $i$ d'un vector, aplicant una proporcionalitat, podem calcular a quina posició de memòria està. Però en una llista, per accedir a la posició $i$-èsima, necessitem visitar totes les anteriors, ja que és una cadena de punters impossible de preveure.

Les llistes comparteixen mètodes amb vectors i afegeixen insert i erase

Els mètodes de les llistes són equivalents als dels vectors, incloent alguns mètodes nous que s'apliquen a tots dos: insert i erase.

Exemple: inserim cada element al lloc ordenat amb insert

#include <list>
#include <iostream>
using namespace std;

void sorted_insert(list<int>& L, int x) {
	list<int>::iterator it = L.begin();
	while (it != L.end() and *it < x) {
		++it;
	}
	L.insert(it, x); // cost O(1)
}

int main() {
	list<int> L;
	int x;
	while (cin >> x) {
		sorted_insert(L, x);
	}
	for (int x : L) {
		cout << x << endl;
	}
}

Els iteradors són marcadors de posició per recórrer i modificar contenidors

Un iterador és un objecte que representa una posició en un contenidor. És com una fletxa que marca una posició, sense afectar el contenidor. Els iteradors permeten tenir "marcadors" a posicions d'una llista, per exemple, i indicar on volem fer certes operacions. També permeten indicar intervals d'elements a recórrer (com en el cas de sort).

begin() apunta al primer element i end() al sentinella final

Els iteradors tenen un tipus específic per a cada contenidor, per exemple els següents són dos iteradors, un per un vector i un altre per una llista:

vector<int>::iterator vit = my_vector.begin();
list<int>::iterator lit = my_list.begin();

El tipus d'un iterador realment "pertany a" (per això els ::) la classe del contenidor. La raó és poder posar el mateix nom iterator a tots els iteradors, però que se sàpiga de quina classe són. Si diguéssim que tenim una classe desconeguda de contenidor C, llavors C::iterator seria un iterador als elements d'aquesta classe.

Donat un contenidor, es poden obtenir iteradors al principi i al final de la seqüència d'elements. Però s'utilitzen intervals asimètrics, on el primer element està dins el contenidor i l'últim a fora. És a dir, begin() és un iterador al primer element del vector, però end() és un punter a un element fictici passat l'últim element. Es pot dir, doncs, que end() és com un sentinella.

Un iterador es pot assignar (=), incrementar (++), comparar (==, !=) i desreferenciar (*), que és accedir a l'element d'aquella posició. Amb aquestes poques operacions es poden fer recorreguts a una llista o un vector pràcticament amb el mateix codi.

Com que una llista no té índexs, l'única manera de manipular-ne els elements és a través d'iteradors:

list<int> L = {1, 2, 3, 4, 5};
list<int>::iterator it = L.begin(); // it apunta al 1r element
it++; // 2n element
it++; // 3r element
while (it != L.end()) {
	*it += 10; // sumem 10 a l'actual
	it++;
}
// L = {1, 2, 13, 14, 15}

advance permet moure un iterador diverses posicions d'un sol cop

En llistes, com que no hi ha índexs, avançar $i$ elements requeriria un bucle, i per això la STL inclou la funció advance(it, n) que fa avançar un iterador it en n posicions.

list<int> L {1, 2, 3, 4, 5};
list<int>::iterator it = L.begin();
advance(it, 3); // it++; it++; it++;
*it *= 10;
// L = {1, 2, 3, 40, 5}

Amb iteradors podem fer recorreguts ascendents, constants i descendents

Donada una llista com

list<int> L = {1, 2, 3, 4, 5};

Un recorregut per tots els seus elements en ordre ascendent seria:

for (list<int>::iterator it = L.begin(); it != L.end(); it++) {
	*it += 1;
}

Un recorregut per tots els elements d'una llista const seria:

for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
	cout << *it << endl;
}

Un recorregut en ordre descendent seria:

for (list<int>::reverse_iterator rit = L.rbegin(); rit != L.rend(); rit++) {
	cout << *rit << endl;
}

(Interessant l'ús d'una r al nom de l'iterador, igual que amb els mètodes, per distingir-los i que no hi hagi confusió.)

insert col·loca un element abans de l'iterador indicat

Els iteradors van molt bé per indicar a on cal fer certes coses. Com per exemple, insertar i esborrar, el punt fort de les llistes. El següent codi en mostra un exemple:

list<string> L = {"abc", "xyz"};
list<string>::iterator it = L.begin();
it = L.insert(it, "000"); // insereix al principi i obté iterador a "000"
advance(it, 2);      // it++; it++;
L.insert(it, "lmo"); //
it = L.end();
L.insert(it, "999");
// L = {"000", "abc", "lmo", "xyz", "999"}

La inserció es fa de tal manera que l'element insertat quedarà a la posició que l'iterador apuntava, i per tant la resta d'elements han de moure's cap al final del contenidor.

En insercions en bucle, cal reajustar l'iterador per no repetir o saltar elements

Però, per què insert retorna un iterador? En el cas de que volguem fer vàries insercions en bucle, és molt important adonar-se que, pel que fa a la iteració, el fet d'insertar ens fa anar un element cap enrere, perquè si estem a un element, i a l'insertar aquest es desplaça més enllà, és com si haguéssim retrocedit, i encara que el bucle incrementi l'iterador, tornarem a estar a on estàvem.

Exemple 1: afegir un '0' abans de cada dígit entre '1' i '9':

void prefix_digits_with_zero(list<char>& L) {
	list<char>::iterator it = L.begin();
	while (it != L.end()) {
		if (*it >= '1' && *it <= '9') {
			it = L.insert(it, '0'); // en inserir ens movem "cap enrere"!
			advance(it, 2);         // saltem el '0' i després el dígit
		} else {
			it++;
		}
	}
}

Exemple 2: Insereix un 0 abans dels nombres negatius

void insert_zeros_before(list<double>& L) {
	for (auto it = L.begin(); it != L.end(); it++) {
		if (*it < 0) {
			it = L.insert(it, 0); // Inserir "endarrereix" l'iterador!!
			it++;                 // saltar el nou insertat!
		}
	}
}

Exemple 3: Insereix un 0 després dels nombres negatius

void insert_zeros_after(list<double>& L) {
	for (auto it = L.begin(); it != L.end(); it++) {
		if (*it < 0) {
			it++;                 // posar-se al següent (end ok!)
			it = L.insert(it, 0); // inserir abans del següent
		}
	}
}

erase esborra l'element actual i retorna el següent iterador vàlid

El següent codi esborra un element a la posició indicada per un iterator.

list<char> L = {'a', 'b', 'c', 'd', 'e'};
list<char>::iterator it = L.begin();
it++;
it++;
L.erase(it); // esborrem la 'c'
// L = {'a', 'b', 'd', 'e'}

L'esborrat es fa de tal manera que l'element després de l'esborrat quedarà a la posició que l'iterador apuntava, i per tant la resta d'elements han de moure's cap al principi del contenidor, és a dir, s'apropen a la posició de l'iterador.

En general, els esborrats puntuals no tenen dificultat, perquè encara que l'iterador que tinguem no s'invalidi, no passa res. Però erase retorna un iterador com a resultat, per a què serveix això? El retorn d'erase és precisament el següent element, perquè si estem al mig d'una iteració, ens interessa poder reprendre el fil i seguir la iteració en el següent element.

En esborrats en bucle, cal aprofitar el retorn d'erase per continuar bé

Així doncs l'erase també té un problema amb els esborrats en bucle, en part perquè els iteradors s'invaliden, però també per una raó similar a insert, perquè així com insert fa moure els elements més enllà quan n'insertes un, erase fa l'invers: quan esborres un element, la resta s'apropen a la posició de l'iterador. I cal tenir en compte això per fer les iteracions correctament.

Exemple 1: eliminar tots els negatius d'una llista de reals

void erase_negative(list<double>& L) {
	list<double>::iterator it = L.begin();
	while (it != L.end()) {   // `while` perquè no sempre hi ha un it++!
		if (*it < 0) {
			it = L.erase(it); // Esborrar **avança** l'iterador!!
		} else {
			it++;
		}
	}
}

Exemple 2: eliminar zeros abans d'un enter negatiu

void erase_zero_before_negative(list<int>& L) {
    auto it = L.begin();
    while (it != L.end()) {
        auto next = it;
        ++next;
        if (*it == 0 and next != L.end() and *next < 0) {
            it = L.erase(it);
        } else {
            ++it;
        }
    }
}

Aquesta funció recorre la llista, i cada cop que troba un zero seguit d'un nombre negatiu, esborra el zero. El retorn d'erase permet seguir correctament la iteració sense invalidar l'iterador principal.

Els iteradors reversos simplifiquen els recorreguts del final al principi

Com que l'interval begin - end és asimètric i end està fora del contenidor, fer iteracions cap enrere pot ser incòmode amb iteradors "normals":

list<int>::iterator it = L.end(); // no és l'últim (cal fer it-- primer)
for (it--; it != L.begin(); it--) {
    cout << *it << endl;
}
cout << *it << endl;

El codi queda molt extrany i confús perquè:

1. Al principi no comencem amb l'últim element, cal fer it-- per estar-hi a sobre (es fa a la primera part del for).

2. Com que begin() no és un sentinella, el seu element anterior està indefinit, i llavors no queda clar que poguem posar it >= L.begin(), ja que farem it-- tot seguit, així que per estar segurs cal fer la iteració fins el segon element i a fora del bucle processar el primer.

És molt molest haver de fer l'esforç mental de fer iteracions així en general, per això existeix un tipus d'iterador per moure's des del final cap al principi.

Les iteracions cap enrere són equivalents a les normals excepte en el nom dels iteradors i els mètodes, d'altra manera seria molt més empipador escriure aquests recorreguts.

list<int> L {1, 2, 3, 4, 5};
list<int>::reverse_iterator rit = L.rbegin(); // últim element (no el end!)
rit++; // penúltim element
rit++; 
while (rit != L.rend()) {
	*rit += 10;
	rit++;
}
// L = {10, 20, 30, 4, 5}

En contenidors constants cal usar const_iterator per recórrer sense modificar

En una funció com:

double suma_llista(const list<double>& L) { ... }

on no és possible modificar la llista, utilitzar un list<int>::iterator dóna un error de compilació, perquè un iterador normal no garanteix que no modificarà l'element. En aquests casos cal utilitzar un const_iterator:

double suma_llista(const list<double>& L) {
	double suma = 0.0;
	for (list<double>::const_iterator it = L.begin(); it != L.end(); it++) {
		suma += *it;
	}
	return suma;
}

En combinació amb els iteradors inversos, hi ha 4 possibilitats:

auto evita escriure tipus d'iterador massa llargs

Com que els tipus d'iteradors poden ser molt llargs d'escriure:

// Iterador a una llista d'iteradors a vectors... XD
list<vector<int>::iterator>::iterator it = L.begin();

sovint s'utilitza la paraula reservada auto, de C++, amb la qual es pot demanar al compilador que "dedueixi" el tipus directament de l'iterador, per estalviar-nos haver-lo d'escriure. Al principi utilitzar auto és un auto-engany (🤯), perquè si no tenim clar els tipus d'iteradors és fàcil confondre's, però a la llarga auto és molt útil per facilitar la lectura d'un programa.

Amb auto un bucle ascendent d'una llista es converteix en:

for (auto it = L.begin(); it != L.end(); it++) {
    cout << *it << endl;
}

El mateix patró d'iteradors funciona en vector amb pocs canvis

Simplement substituint list per vector, podem escollir el contenidor que ens convé més, sense canviar el codi.

Tot i que cal recordar:

• Invalidació d'iteradors: en un vector, insert i erase també invaliden els iteradors, malgrat que això pugui semblar paradoxal, però és perquè al créixer, un vector pot saltar a una altra zona de memòria per falta d'espai per créixer, per tant cal seguir utilitzant els iteradors que retornen insert i erase igualment!

Les llistes només compensen en casos amb moltes insercions i pocs recorreguts

Tot i que les llistes tenen un cost d'inserció i esborrat $O(1)$, no s'utilitzen amb massa freqüència com podria semblar perquè les CPUs modernes penalitzen el recorregut d'estructures a memòria amb punters enllaçats, i és difícil trobar un cas d'ús en què s'insereixi i s'esborri en punts intermitjos molt més del que es recorre el contenidor.