STL - sequenze, iteratori e container (vector, list, string)

In questa pagina 6

Gestire una serie di dati significa fare sempre le stesse cose: inserire i dati in un contenitore (vector, list, array, ...), leggerli (stampa, accesso), trovarli (da un indice, da un valore, da una proprietà), modificare il contenitore (aggiungere, rimuovere, ordinare). Alcuni esempi di operazioni: trovare la temperatura più alta, trovare i valori più grandi di 8800, trovare le differenze tra due sequenze, calcolare la somma degli elementi. Queste operazioni prescindono da come i dati sono memorizzati. La Standard Template Library (STL) è la parte della libreria standard che le rende scrivibili una volta sola.

Che cosa offre la STL

Contenitori: vector, list, map, ... (STL - container associativi (map e set) per quelli associativi).
Algoritmi generici: sort, find, accumulate, ... (STL - algoritmi, predicati e lambda cattura -> tipo { corpo } definisce la funzione sul posto e può catturare le variabili locali per valore ([=], [x]) o per riferimento ([&], [&x]). sort(b, e) ordina con < e sort(b, e, cmp) con un criterio, solo su iteratori random access; copy richiede spazio a destinazione.STL - algoritmi, predicati e lambda →).

I contenitori sono molti ma hanno un accesso unificato: cambiare il tipo di un contenitore non deve avere impatto sull'algoritmo, e si scrive codice aggiuntivo solo per funzioni nuove, non per cambiare contenitore. Per ottenerlo servono: accesso ai dati indipendente da come e con quale tipo sono salvati, accesso safe, visita facile delle strutture, salvataggio compatto, aggiunta/rimozione/ricerca veloci, disponibilità degli algoritmi più comuni. Lo strumento è il template (C++ - template e programmazione generica) e il concetto chiave è la sequenza.

Sequenze e iteratori

Definizione (sequenza). Una sequenza è un intervallo di elementi con un inizio e una fine, indicato [begin, end): begin è il primo elemento, end è il primo elemento dopo l'ultimo. La sequenza si gestisce tramite iteratori.

Definizione (iteratore). Un iteratore è un oggetto che identifica un elemento di una sequenza (o uno dopo l'ultimo). Ricorda un puntatore, e ne ha la sintassi.

operazione	significato
`*it`	l'elemento a cui `it` si riferisce (dereferenziazione, anche in scrittura)
`++it`	passa all'elemento successivo
`it1 == it2`, `it1 != it2`	confronto: stesso elemento?
`--it`, `it + n`, `it[n]`	solo per gli iteratori che lo permettono (random access, vedi sotto)

Poiché end è uno dopo l'ultimo, si cicla con p != end, non si dereferenzia mai end, e una sequenza vuota è semplicemente quella con begin == end: la lista vuota è un caso non speciale. Gli iteratori non servono solo per il contenitore intero: due iteratori qualsiasi definiscono la sotto-sequenza [first, last).

Disaccoppiare algoritmi e dati

Per scrivere software di valenza generale conviene separare due elementi: le collezioni di dati e gli algoritmi, che interagiscono spesso. L'interazione passa per un'interfaccia il più possibile standard, e la STL la fornisce con gli iteratori.

Lato algoritmo: non serve conoscere la struttura dati, basta usare i suoi iteratori. Un algoritmo di ordinamento può funzionare senza conoscere i dettagli del contenitore.
Lato contenitore: non serve conoscere gli algoritmi, basta esporre gli iteratori. Un vector non ha bisogno di sapere come lo ordina sort.

Esempio: una funzione template che restituisce l'elemento di valore massimo in [first, last). Funziona su qualunque sequenza.

high/high.cppcpp

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

// Restituisce l'elemento in [first, last) che ha il valore piu' alto (se la sequenza e' vuota: last)
template <typename Iterator>
Iterator high(Iterator first, Iterator last)
{
    Iterator high = first;
    for (Iterator p = first; p != last; ++p)
        if (*high < *p)
            high = p;
    return high;
}

int main()
{
    vector<int> v{3, 9, 4, 7};
    list<string> l{"mela", "pera", "zucca", "banana"};
    double a[] = {1.5, 0.5, 8.25, 2.0};

    cout << *high(v.begin(), v.end()) << '\n';          // iteratori di vector<int>
    cout << *high(l.begin(), l.end()) << '\n';          // iteratori di list<string>
    cout << *high(a, a + 4) << '\n';                    // un puntatore e' un iteratore
    cout << *high(v.begin(), v.begin() + 2) << '\n';    // anche una sotto-sequenza: [3, 9)

    vector<int> vuoto;
    cout << (high(vuoto.begin(), vuoto.end()) == vuoto.end()) << '\n';   // sequenza vuota: begin == end
}

Uscita eseguita: 9, zucca, 8.25, 9, 1. La stessa funzione lavora su un vector<int>, su una list<string> (l'ordine è lessicografico, quindi zucca è il massimo), su un array C (un puntatore è un iteratore valido), su una sotto-sequenza [v.begin(), v.begin()+2) (massimo di 3, 9) e, per la sequenza vuota, restituisce last (qui end(), quindi il confronto vale 1). L'unico requisito è che gli elementi supportino <.

Linked list e il suo iteratore

La lista concatenata è una struttura gestita così: ogni elemento (nodo) sa chi lo precede e chi lo segue (si vedano le Liste concatenate in C). In STL:

cpp

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

Operazioni di una lista: quelle di vector senza [] (costruttore, size, ...), più insert ed erase, più gli iteratori. Perché è escluso []? Per arrivare all'elemento i bisogna percorrere i nodi: sarebbe un'operazione lineare camuffata da accesso diretto. In STL un iteratore è un membro della classe contenitore (list<T>::iterator) e begin(), end(), insert ed erase restituiscono iteratori. L'iteratore di lista contiene un puntatore al nodo e implementa ++, --, *, ==, !=.

Un'implementazione completa ma parziale (niente copia e spostamento), con la quale funzionano perfino gli algoritmi STL:

minilist/minilist.cppcpp

#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;

template <typename Elem>
struct Link {
    Link* prev;
    Link* succ;
    Elem val;
};

template <typename Elem>
class MyList {                                   // lista doppiamente concatenata, MOLTO parziale
    Link<Elem>* first = nullptr;
    Link<Elem>* last = nullptr;
public:
    class iterator {                             // l'iteratore e' un membro del container
        Link<Elem>* curr;
        MyList* owner;
        friend class MyList;
    public:
        // questi cinque tipi dicono agli algoritmi STL che iteratore e': bidirezionale
        using iterator_category = bidirectional_iterator_tag;
        using value_type = Elem;
        using difference_type = ptrdiff_t;
        using pointer = Elem*;
        using reference = Elem&;

        iterator(Link<Elem>* p, MyList* o) : curr{p}, owner{o} {}
        iterator& operator++() { curr = curr->succ; return *this; }
        iterator& operator--() { curr = curr ? curr->prev : owner->last; return *this; }
        Elem& operator*() const { return curr->val; }
        bool operator==(const iterator& b) const { return curr == b.curr; }
        bool operator!=(const iterator& b) const { return curr != b.curr; }
    };
    MyList() = default;
    MyList(initializer_list<Elem> l) { for (const Elem& e : l) push_back(e); }
    MyList(const MyList&) = delete;              // (non trattate qui: copia e spostamento)
    MyList& operator=(const MyList&) = delete;
    ~MyList() { while (first) pop_front(); }

    iterator begin() { return iterator{first, this}; }
    iterator end() { return iterator{nullptr, this}; }      // "uno dopo l'ultimo"

    void push_back(const Elem& v)
    {
        Link<Elem>* n = new Link<Elem>{last, nullptr, v};
        if (last) last->succ = n; else first = n;
        last = n;
    }
    void push_front(const Elem& v)
    {
        Link<Elem>* n = new Link<Elem>{nullptr, first, v};
        if (first) first->prev = n; else last = n;
        first = n;
    }
    void pop_front() { erase(begin()); }
    iterator insert(iterator p, const Elem& v)        // inserisce PRIMA di p, restituisce il nuovo
    {
        if (p.curr == nullptr) { push_back(v); return iterator{last, this}; }
        Link<Elem>* n = new Link<Elem>{p.curr->prev, p.curr, v};
        if (p.curr->prev) p.curr->prev->succ = n; else first = n;
        p.curr->prev = n;
        return iterator{n, this};
    }
    iterator erase(iterator p)                         // rimuove p, restituisce il successivo
    {
        Link<Elem>* x = p.curr;
        Link<Elem>* next = x->succ;
        if (x->prev) x->prev->succ = x->succ; else first = x->succ;
        if (x->succ) x->succ->prev = x->prev; else last = x->prev;
        delete x;
        return iterator{next, this};
    }
    Elem& front() { return first->val; }
    Elem& back() { return last->val; }
};

template <typename C>
void stampa(C& c)
{
    for (auto p = c.begin(); p != c.end(); ++p) cout << *p << ' ';
    cout << '\n';
}

int main()
{
    MyList<string> norse_gods;                   // l'esempio del corso
    norse_gods.push_back("Odin");
    norse_gods.push_back("Thor");
    norse_gods.push_front("Freia");
    stampa(norse_gods);                          // Freia Odin Thor

    auto p = find(norse_gods.begin(), norse_gods.end(), string{"Odin"});    // algoritmo STL!
    if (p != norse_gods.end()) { p = norse_gods.insert(p, "Loki"); }
    stampa(norse_gods);                          // Freia Loki Odin Thor
    cout << "*p = " << *p << '\n';               // insert ha restituito l'iteratore al nuovo elemento

    p = norse_gods.erase(p);                     // rimuove Loki, restituisce il successivo
    cout << "dopo erase, *p = " << *p << '\n';   // Odin
    stampa(norse_gods);

    MyList<int> vuota;
    cout << "lista vuota: begin == end? " << (vuota.begin() == vuota.end()) << '\n';
    auto ult = norse_gods.end(); --ult;
    cout << "ultimo = " << *ult << '\n';
}

Uscita eseguita:

Freia Odin Thor
Freia Loki Odin Thor
*p = Loki
dopo erase, *p = Odin
Freia Odin Thor
lista vuota: begin == end? 1
ultimo = Thor

Che cosa mostra:

begin() è il puntatore al primo nodo, end() un iteratore con puntatore nullo ("uno dopo l'ultimo"); su una lista vuota first è nullo e quindi begin() == end().
std::find funziona sulla nostra lista, perché MyList::iterator offre *, ++ e ==, e dichiara con cinque using di che categoria è (bidirezionale: ++ e --). Senza quelle dichiarazioni (iterator_category, value_type, ...) gli algoritmi della libreria non saprebbero che cosa è.
insert(p, v) inserisce prima di p e restituisce un iteratore al nuovo elemento; erase(p) restituisce un iteratore al successivo. L'idioma è p = lista.erase(p): dopo l'erase il vecchio p non è più valido.
--end() richiede di sapere dov'è l'ultimo nodo: qui l'iteratore tiene un puntatore alla lista. Le slide non lo trattano (la loro operator-- fa curr = curr->prev, quindi --end() sarebbe un errore con end() nullo).

`auto`

I nomi dei tipi degli iteratori sono lunghi e rendono il codice complesso. Il tipo di p in vector<T>::iterator p = v.begin(); è per forza quello, perché si inizializza con v.begin(): il compilatore lo può dedurre. La keyword auto lo fa.

tipi_iteratori/tipi_iteratori.cppcpp

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

template <typename T>
void user_lungo(vector<T>& v, list<T>& lst)
{
    // vector<T>::iterator dipende dal parametro T: serve 'typename' (le slide lo omettono)
    for (typename vector<T>::iterator p = v.begin(); p != v.end(); ++p) cout << *p << ' ';
    typename list<T>::iterator q = find(lst.begin(), lst.end(), T{42});
    cout << (q != lst.end()) << '\n';
}

template <typename T>
void user_auto(vector<T>& v, list<T>& lst)       // con auto il problema non si pone
{
    for (auto p = v.begin(); p != v.end(); ++p) cout << *p << ' ';
    auto q = find(lst.begin(), lst.end(), T{42});
    cout << (q != lst.end()) << '\n';
}

int main()
{
    vector<int> v{1, 2, 3};
    list<int> l{40, 42};
    user_lungo(v, l);
    user_auto(v, l);

    auto x = 123;                                // int
    auto c = 'y';                                // char
    auto& r = x;                                 // int&
    auto y = r;                                  // int: le reference non si "trascinano"
    auto s1 = "San Antonio";                     // const char*, NON string!
    string s2 = "Fredericksburg";                // string
    cout << sizeof(x) << ' ' << sizeof(c) << ' ' << (&r == &x) << ' ' << (&y != &x)
         << ' ' << (sizeof(s1) == sizeof(void*)) << ' ' << s2.size() << '\n';
}

Uscita eseguita: 1 2 3 1 (due volte) e 4 1 1 1 1 14. Tre osservazioni.

Errore nelle slide. Il codice delle slide scrive for (vector<T>::iterator p = v.begin(); ...) e list<T>::iterator q = find(...) dentro una funzione template, senza typename: non compila (missing 'typename' prior to dependent type name 'vector<T>::iterator', provato anche con C++20). Dentro un template vector<T>::iterator dipende da T, e il compilatore deve sapere che è un tipo: serve typename vector<T>::iterator, oppure auto, che fa sparire il problema. Nelle slide c'è anche un find(lst.begin(); lst.end(); T{42}) con punti e virgola al posto delle virgole.
auto ha un uso più generale (auto x = 123; è un int, auto c = 'y'; un char, auto& r = x; un int&, auto y = r; un int: le reference non si "trascinano"), ma può dare ambiguità: auto s1 = "San Antonio"; è un const char*, non una string. Il corso lo consiglia solo per gli iteratori.
Un puntatore è un iteratore: &r == &x è vero, y invece è una copia.

Tre contenitori a confronto: `vector`, `string`, `list`

	`vector`	`string`	`list`	`char[]` (array C)
memoria	contigua, espandibile	contigua, espandibile	nodi sparsi, espandibile	contigua, dimensione fissa decisa a compile-time
`[]`	sì	sì	no	sì (puntatore)
controllo dei limiti	`at()` su richiesta	`at()`		no
`insert`/`erase`	inefficienti (spostano elementi), invalidano iteratori	idem	efficienti, senza spostare gli altri elementi	non esistono
`begin`/`end`	sì	sì	sì	no (né dimensione)
`==`	confronta gli elementi	confronta gli elementi	confronta gli elementi	confronta i puntatori
operazioni di testo		`+`, `+=`		`strcmp` ecc.

Un programma che dimostra le differenze (eseguito):

contenitori/contenitori.cppcpp

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

int main()
{
    // ---- vector: insert ed erase spostano gli elementi; iteratori da rimpiazzare ----
    vector<int> v{0, 1, 2, 3, 4, 5};
    vector<int>::iterator p = v.begin();
    ++p; ++p; ++p;                               // p -> elemento di valore 3
    cout << "*p = " << *p << '\n';
    p = v.insert(p, 99);                         // p vecchio NON e' piu' valido: si usa il valore restituito
    cout << "dopo insert: *p = " << *p << ", v =";
    for (int x : v) cout << ' ' << x;
    cout << '\n';
    p = v.erase(p);                              // erase restituisce l'iteratore al successivo
    cout << "dopo erase: *p = " << *p << ", size = " << v.size() << '\n';

    // ---- vector: at() controlla, [] no; capacity e contiguita' ----
    vector<int> w;
    int riallocazioni = 0;
    size_t cap = w.capacity();
    for (int i = 0; i < 100; ++i) {
        w.push_back(i);
        if (w.capacity() != cap) { ++riallocazioni; cap = w.capacity(); }
    }
    cout << "100 push_back: riallocazioni = " << (riallocazioni > 1 ? "piu' di una" : "una") << '\n';
    cout << "contigui: " << (&w[1] == &w[0] + 1) << '\n';

    // ---- string contro char[] ----
    string s1 = "cia", s2 = "ciao";
    s1 += 'o';                                   // concatenazione
    cout << "string ==: " << (s1 == s2) << ", " << s1 + "!" << ", size " << s1.size() << '\n';
    char a[] = "ciao", b[] = "ciao";             // array stile C: due blocchi distinti
    const char* pa = a; const char* pb = b;
    cout << "char[] con ==: " << (pa == pb) << " (confronta i puntatori), strcmp: " << (strcmp(a, b) == 0) << '\n';
    cout << "sizeof(a) = " << sizeof(a) << " (4 caratteri + il terminatore)" << '\n';

    // ---- list: insert/erase senza spostare, niente [] ----
    list<int> l{10, 20, 30};
    auto q = l.begin();
    ++q;                                         // -> 20
    int* indirizzo_20 = &*q;
    l.insert(l.begin(), 5);                      // i nodi esistenti non si spostano
    l.push_back(40);
    cout << "list: l.size() = " << l.size() << ", elemento 20 allo stesso indirizzo: " << (indirizzo_20 == &*q) << '\n';
    cout << "*q ancora valido = " << *q << '\n';
    // l[1];                                     // errore: list non ha operator[]
    l.erase(q);                                  // si invalida solo q
    for (int x : l) cout << x << ' ';
    cout << '\n';
    cout << "== tra vector:" << (vector<int>{1, 2} == vector<int>{1, 2}) << ", tra list:" << (list<int>{1} == list<int>{2}) << '\n';
}

Uscita:

*p = 3
dopo insert: *p = 99, v = 0 1 2 99 3 4 5
dopo erase: *p = 3, size = 6
100 push_back: riallocazioni = piu' di una
contigui: 1
string ==: 1, ciao!, size 4
char[] con ==: 0 (confronta i puntatori), strcmp: 1
sizeof(a) = 5 (4 caratteri + il terminatore)
list: l.size() = 5, elemento 20 allo stesso indirizzo: 1
*q ancora valido = 20
5 10 30 40
== tra vector:1, tra list:0

`insert` ed `erase` con `vector`: gli iteratori

Inserire o rimuovere un elemento in mezzo a un vector obbliga a spostare gli elementi che seguono (e può far riallocare tutto il blocco se la capacità non basta). Conseguenze:

è inefficiente: un problema per collezioni molto grandi;
rende non validi gli iteratori che puntano al vector: dopo v.insert(p, 99) il vecchio p e tutti gli altri iteratori (q nella figura delle slide) non vanno più usati. Si usa il valore restituito da insert/erase, come nel programma (p = v.insert(p, 99), p = v.erase(p)).

Con la lista il problema non si ripropone: insert ed erase non spostano gli altri nodi, quindi gli iteratori e i puntatori agli altri elementi restano validi (nel programma &*q non cambia dopo insert e push_back); si invalida solo l'iteratore dell'elemento rimosso.

Overview dei contenitori STL

contenitore	struttura
`vector`	array dinamico contiguo
`list`	lista doppiamente concatenata
`deque`	coda a due estremità
`map`, `multimap`	albero bilanciato e ordinato di coppie (chiave, valore)
`unordered_map`, `unordered_multimap`	tabella hash
`set`, `multiset`, `unordered_set`, `unordered_multiset`	solo chiavi
`array`	array di dimensione fissa

(I contenitori associativi sono in STL - container associativi (map e set).)

Che cos'è un contenitore STL: la definizione è complessa, ma di fatto un contenitore:

è una sequenza di elementi [begin(), end());
supporta la copia (costruttore di copia, assegnamento);
chiama il tipo dei propri elementi value_type;
ha tipi iteratore iterator e const_iterator. Gli iteratori offrono *, ++ (pre e post), ==, !=; quelli di vector offrono anche --, [], + e - (random access iterator);
offre insert(), erase(), front(), back(), push_back(), pop_back(), size(), ...; vector e map offrono anche [];
offre gli operatori di confronto ==, !=, <, <=, >, >=.

Le categorie di iteratori si riflettono sugli algoritmi: sort richiede iteratori random access (quindi funziona su vector, non su list, che ha una propria list::sort); find si accontenta di iteratori di input.

Domande d'esame

1. Descrivere il concetto di contenitore STL, di accesso uniforme ai dati e lo strumento usato. Due esempi di contenitori e come sono strutturati. Traccia. Un contenitore è una sequenza [begin(), end()) copiabile, con value_type, iterator/const_iterator, insert/erase, size, confronti. L'accesso uniforme è dato dagli iteratori: algoritmi e contenitori parlano solo tramite iteratori (*, ++, ==), quindi l'algoritmo non cambia se cambia il contenitore. Esempi: vector (array dinamico contiguo, [], insert costosi) e list (nodi Link con prev/succ, insert senza spostamenti, niente []).

2. Perché insert() su un vector invalida gli iteratori e su una list no? Traccia. Nel vector gli elementi sono contigui: inserire sposta quelli successivi (e può riallocare il blocco), quindi gli iteratori vecchi puntano a posizioni diverse o a memoria rilasciata; si usa il valore restituito. Nella list si collegano solo i puntatori dei nodi vicini; gli altri nodi non si muovono.

3. Differenza tra string e char[]. Traccia. string conosce la sua dimensione, ha iteratori, at(), +, +=, è espandibile, == confronta il contenuto; char[] è un array C di dimensione fissa, senza begin()/end() né controllo, == e << si riferiscono al puntatore al primo elemento (si confronta con strcmp).

Versione ripasso

STL = contenitori (vector, list, map, ...) + algoritmi generici (sort, find, accumulate), con accesso unificato: cambiare contenitore non cambia l'algoritmo.
Sequenza [begin, end): end = primo elemento dopo l'ultimo; sequenza vuota = begin == end. Iteratore = identifica un elemento: *, ++, ==, != (random access anche --, [], +, -). Un puntatore è un iteratore.
Disaccoppiamento: gli algoritmi usano solo iteratori, i contenitori espongono solo iteratori. Esempio: template<typename Iterator> Iterator high(Iterator first, Iterator last) (richiede < sugli elementi); funziona con vector<int>, list<string>, array C (high(a, a+4)).
Lista: Link {prev, succ, val}, list {first, last}; niente [] (costo lineare). list<T>::iterator è una classe membro con puntatore al nodo (++, --, *, ==, !=); begin, end, insert (prima di p, restituisce il nuovo), erase (restituisce il successivo): p = l.erase(p). Per usarla con gli algoritmi STL servono iterator_category e gli altri tipi. Liste concatenate in C: Liste concatenate.
auto per i tipi degli iteratori; typename serve in un template (typename vector<T>::iterator, le slide lo omettono). auto s = "testo"; è const char*: solo per gli iteratori.
vector: contiguo, [], at() con controllo, espandibile, insert/erase inefficienti e invalidano gli iteratori (usare il valore restituito). string: come vector con +, +=, == sul contenuto. char[]: dimensione fissa, niente iteratori, == confronta i puntatori. list: insert/erase senza spostare, non invalida gli altri iteratori, niente [].
Contenitori: vector, list, deque, map/multimap (albero bilanciato), unordered_* (hash), set/multiset, array (STL - container associativi (map e set)). Un contenitore STL: sequenza copiabile con value_type, iterator, const_iterator, insert, erase, front, back, push_back, pop_back, size, confronti.
Errori tipici: dereferenziare end(), usare un iteratore dopo insert/erase su vector, [] su list, == tra char[], scordare typename, auto con letterali stringa.
Codice (high/high.cpp):

high/high.cppcpp

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

// Restituisce l'elemento in [first, last) che ha il valore piu' alto (se la sequenza e' vuota: last)
template <typename Iterator>
Iterator high(Iterator first, Iterator last)
{
    Iterator high = first;
    for (Iterator p = first; p != last; ++p)
        if (*high < *p)
            high = p;
    return high;
}

int main()
{
    vector<int> v{3, 9, 4, 7};
    list<string> l{"mela", "pera", "zucca", "banana"};
    double a[] = {1.5, 0.5, 8.25, 2.0};

    cout << *high(v.begin(), v.end()) << '\n';          // iteratori di vector<int>
    cout << *high(l.begin(), l.end()) << '\n';          // iteratori di list<string>
    cout << *high(a, a + 4) << '\n';                    // un puntatore e' un iteratore
    cout << *high(v.begin(), v.begin() + 2) << '\n';    // anche una sotto-sequenza: [3, 9)

    vector<int> vuoto;
    cout << (high(vuoto.begin(), vuoto.end()) == vuoto.end()) << '\n';   // sequenza vuota: begin == end
}

Codice (minilist/minilist.cpp):

minilist/minilist.cppcpp

#include <algorithm>
#include <cstddef>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;

template <typename Elem>
struct Link {
    Link* prev;
    Link* succ;
    Elem val;
};

template <typename Elem>
class MyList {                                   // lista doppiamente concatenata, MOLTO parziale
    Link<Elem>* first = nullptr;
    Link<Elem>* last = nullptr;
public:
    class iterator {                             // l'iteratore e' un membro del container
        Link<Elem>* curr;
        MyList* owner;
        friend class MyList;
    public:
        // questi cinque tipi dicono agli algoritmi STL che iteratore e': bidirezionale
        using iterator_category = bidirectional_iterator_tag;
        using value_type = Elem;
        using difference_type = ptrdiff_t;
        using pointer = Elem*;
        using reference = Elem&;

        iterator(Link<Elem>* p, MyList* o) : curr{p}, owner{o} {}
        iterator& operator++() { curr = curr->succ; return *this; }
        iterator& operator--() { curr = curr ? curr->prev : owner->last; return *this; }
        Elem& operator*() const { return curr->val; }
        bool operator==(const iterator& b) const { return curr == b.curr; }
        bool operator!=(const iterator& b) const { return curr != b.curr; }
    };
    MyList() = default;
    MyList(initializer_list<Elem> l) { for (const Elem& e : l) push_back(e); }
    MyList(const MyList&) = delete;              // (non trattate qui: copia e spostamento)
    MyList& operator=(const MyList&) = delete;
    ~MyList() { while (first) pop_front(); }

    iterator begin() { return iterator{first, this}; }
    iterator end() { return iterator{nullptr, this}; }      // "uno dopo l'ultimo"

    void push_back(const Elem& v)
    {
        Link<Elem>* n = new Link<Elem>{last, nullptr, v};
        if (last) last->succ = n; else first = n;
        last = n;
    }
    void push_front(const Elem& v)
    {
        Link<Elem>* n = new Link<Elem>{nullptr, first, v};
        if (first) first->prev = n; else last = n;
        first = n;
    }
    void pop_front() { erase(begin()); }
    iterator insert(iterator p, const Elem& v)        // inserisce PRIMA di p, restituisce il nuovo
    {
        if (p.curr == nullptr) { push_back(v); return iterator{last, this}; }
        Link<Elem>* n = new Link<Elem>{p.curr->prev, p.curr, v};
        if (p.curr->prev) p.curr->prev->succ = n; else first = n;
        p.curr->prev = n;
        return iterator{n, this};
    }
    iterator erase(iterator p)                         // rimuove p, restituisce il successivo
    {
        Link<Elem>* x = p.curr;
        Link<Elem>* next = x->succ;
        if (x->prev) x->prev->succ = x->succ; else first = x->succ;
        if (x->succ) x->succ->prev = x->prev; else last = x->prev;
        delete x;
        return iterator{next, this};
    }
    Elem& front() { return first->val; }
    Elem& back() { return last->val; }
};

template <typename C>
void stampa(C& c)
{
    for (auto p = c.begin(); p != c.end(); ++p) cout << *p << ' ';
    cout << '\n';
}

int main()
{
    MyList<string> norse_gods;                   // l'esempio del corso
    norse_gods.push_back("Odin");
    norse_gods.push_back("Thor");
    norse_gods.push_front("Freia");
    stampa(norse_gods);                          // Freia Odin Thor

    auto p = find(norse_gods.begin(), norse_gods.end(), string{"Odin"});    // algoritmo STL!
    if (p != norse_gods.end()) { p = norse_gods.insert(p, "Loki"); }
    stampa(norse_gods);                          // Freia Loki Odin Thor
    cout << "*p = " << *p << '\n';               // insert ha restituito l'iteratore al nuovo elemento

    p = norse_gods.erase(p);                     // rimuove Loki, restituisce il successivo
    cout << "dopo erase, *p = " << *p << '\n';   // Odin
    stampa(norse_gods);

    MyList<int> vuota;
    cout << "lista vuota: begin == end? " << (vuota.begin() == vuota.end()) << '\n';
    auto ult = norse_gods.end(); --ult;
    cout << "ultimo = " << *ult << '\n';
}

STL - sequenze, iteratori e container (vector, list, string)

Che cosa offre la STL

Sequenze e iteratori

Disaccoppiare algoritmi e dati

Linked list e il suo iteratore

`auto`

Tre contenitori a confronto: `vector`, `string`, `list`

`insert` ed `erase` con `vector`: gli iteratori

Overview dei contenitori STL

Domande d'esame

Esercizi su questo argomento

Teoria collegata

STL - sequenze, iteratori e container (vector, list, string)

Che cosa offre la STL

Sequenze e iteratori

Disaccoppiare algoritmi e dati

Linked list e il suo iteratore

auto

Tre contenitori a confronto: vector, string, list

insert ed erase con vector: gli iteratori

Overview dei contenitori STL

Domande d'esame

Esercizi su questo argomento

Teoria collegata

`auto`

Tre contenitori a confronto: `vector`, `string`, `list`

`insert` ed `erase` con `vector`: gli iteratori