Esercizio - Confronto tra list e vector (terzo appello 2021-22, teoria)

Domanda aperta 2 del terzo appello 2021-22 (30 giugno 2022) del corso di Laboratorio di Programmazione, Ing. Informatica UniPD. Teoria: STL - sequenze, iteratori e container (vector, list, string)La STL (Standard Template Library) fornisce contenitori (vector, list, map, ...) e algoritmi generici (sort, find, accumulate, ...) tenuti insieme da una interfaccia unificata: la sequenza, un intervallo [begin, end) di elementi gestito tramite iteratori (oggetti che identificano un elemento: * dereferenzia, ++ avanza, == e != confrontano; end è il primo elemento dopo l'ultimo, quindi una sequenza vuota ha begin == end). Gli algoritmi conoscono solo gli iteratori e i contenitori espongono solo iteratori, così i due mondi sono disaccoppiati e cambiare contenitore non cambia l'algoritmo. Un iteratore di lista è una classe annidata con un puntatore al nodo; auto deduce il tipo dell'iteratore. vector (contiguo, [] e at(), insert/erase costosi e che invalidano gli iteratori), string (un vector di char con + e +=), list (nodi concatenati, insert/erase senza spostare gli altri elementi, niente []) e char[] (array C: dimensione fissa, niente iteratori, == confronta i puntatori) a confronto.STL - sequenze, iteratori e container (vector, list, string) →; per strutture dati analoghe Liste concatenateLista concatenata semplice: nodi allocati dinamicamente collegati da puntatori; inserimento e rimozione in testa, scorrimento, ricerca, inserimento ordinato, deallocazione; confronto dei costi con l'array; versione in Python.Liste concatenate → e Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →; il confronto con map è in Esercizio - Confronto tra map e vector (secondo appello 2021-22, teoria).

Testo. Si consideri il concetto di Lista in C++. Descrivere approfonditamente le caratteristiche di una Lista (std::list), le differenze, i vantaggi e gli svantaggi rispetto a un oggetto di tipo Vettore (std::vector).

std::list: come è fatta

std::list è una lista doppiamente concatenata: ogni elemento sta in un nodo separato, collegato al precedente e al successivo.

template<typename Elem>
struct Link {
    Link* prev;      // elemento precedente
    Link* succ;      // elemento successivo
    Elem val;
};
template<typename Elem> struct list {
    Link<Elem>* first;
    Link<Elem>* last;
};

first                                            last
  |                                               |
  v                                               v
[ nullptr | Odin | succ ] <-> [ prev | Thor | succ ] <-> [ prev | Freia | nullptr ]

Caratteristiche:

• non fornisce operator[] (né at()): per raggiungere il $k$-esimo elemento bisogna scorrere la lista; si lavora con gli iteratori (begin(), end(), ++, --, *);
• fornisce le operazioni abituali dei contenitori: size(), empty(), front(), back(), push_back(), push_front(), pop_back(), pop_front(), e soprattutto insert() ed erase();
• insert() ed erase() non spostano gli altri elementi: si riaggiustano solo i puntatori dei nodi vicini, in tempo costante una volta noto il punto;
• espandibile: cresce un nodo alla volta;
• gli iteratori restano validi dopo un insert o un erase (a parte quello dell'elemento cancellato);
• == confronta gli elementi; ha un suo sort() membro (l'algoritmo std::sort richiede iteratori ad accesso casuale, che la lista non ha);
• se è vuota, begin() == end(): la condizione di lista vuota non è un caso speciale.

Confronto con std::vector

Vantaggi della lista: inserire e togliere in qualunque punto senza spostare dati; iteratori stabili; nessuna riallocazione del buffer (le prestazioni sono prevedibili, specie con elementi grandi); inserimento e rimozione in testa. Svantaggi: niente accesso casuale; più memoria per elemento; cattiva località (i nodi sono sparsi, la cache lavora male); non adatta all'ordinamento con std::sort.

Quando usare l'una o l'altra. vector è la scelta predefinita: accesso diretto, memoria compatta. list serve quando ci sono molte inserzioni/cancellazioni in mezzo a una collezione grande, o quando si devono conservare iteratori validi mentre la collezione cambia.

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

int main()
{
    list<int> l {10, 20, 30, 40};
    vector<int> v {10, 20, 30, 40};

    // list: nessun operator[]; si lavora con gli iteratori
    // cout << l[1];                                  // errore: list non ha operator[]
    auto p = l.begin();
    ++p; ++p;                                         // punta a 30
    auto q = l.insert(p, 25);                         // inserisce PRIMA di p, senza spostare nessun elemento
    cout << "list dopo insert: ";
    for (int x : l) cout << x << ' ';
    cout << "| *p = " << *p << " (p e' ancora valido), *q = " << *q << '\n';

    l.erase(q);                                       // toglie 25
    l.push_front(5);                                  // inserimento in testa: O(1)
    l.pop_back();
    cout << "list: ";
    for (int x : l) cout << x << ' ';
    cout << "| front = " << l.front() << ", back = " << l.back() << '\n';

    // vector: [] e at(); insert in mezzo sposta gli elementi e invalida gli iteratori
    auto pv = v.begin() + 2;
    pv = v.insert(pv, 25);                            // si DEVE riassegnare pv col valore restituito
    cout << "vector dopo insert: ";
    for (int x : v) cout << x << ' ';
    cout << "| v[2] = " << v[2] << ", v.at(4) = " << v.at(4) << '\n';

    cout << "confronto ==: " << (l == list<int>{5, 10, 20, 30}) << ", "
         << (v == vector<int>{10, 20, 25, 30, 40}) << '\n';
    cout << "ordinamento: ";
    list<int> disordinata {3, 1, 2};
    disordinata.sort();                               // list ha il suo sort(): std::sort vuole iteratori random access
    for (int x : disordinata) cout << x << ' ';
    cout << '\n';
    return 0;
}

list dopo insert: 10 20 25 30 40 | *p = 30 (p e' ancora valido), *q = 25
list: 5 10 20 30 | front = 5, back = 30
vector dopo insert: 10 20 25 30 40 | v[2] = 25, v.at(4) = 40
confronto ==: 1, 1
ordinamento: 1 2 3 

• Sulla lista: insert(p, 25) inserisce prima di p e restituisce un iteratore al nuovo elemento; *p vale ancora 30 e p è valido; cout << l[1] non compilerebbe (type 'std::list<int>' does not provide a subscript operator).
• Sul vector: v[2], v.at(4) funzionano; pv = v.insert(pv, 25) riassegna pv col valore restituito, perché gli elementi sono stati spostati.
• sort() membro per la lista; std::sort(l.begin(), l.end()) non compilerebbe.