Programmazione Scientifica++: Lezione 18

La Standard Template Library (STL)

Docente

Argomenti di Oggi

La Standard Template Library (STL)
- Non reinventare la ruota
I Container Fondamentali
- Addio Array C: Il trionfo di std::vector
- Dizionari: Trovare dati per Chiave con std::map
Muoversi nei Dati
- Gli Iteratori (Il Ponte Universale)
- Il Range-based For Loop (La magia del C++11)
Algoritmi Pronti all’Uso
- <algorithm>: Sort, Find, e molto altro

Reinventare la Ruota

Nelle lezioni precedenti avete imparato l’allocazione dinamica della memoria (new/delete e gli Smart Pointers). Siete ora in grado di costruire il vostro personale Array ridimensionabile, o la vostra lista concatenata.

Ma nella programmazione reale non si fa MAI.

Scrivere strutture dati a mano significa esporre il proprio software a decine di bug invisibili, buffer overflow e inefficienze computazionali. Se vi serve una lista, un albero, o un dizionario, usate quello fornito dal linguaggio.

La Standard Template Library (STL)

Il cuore pulsante dell’ecosistema C++ è la STL (Standard Template Library).

Creata originariamente da Alexander Stepanov, è una gigantesca collezione di codice già pronto, iper-ottimizzato da decenni, che si installa automaticamente assieme al compilatore g++.

Come suggerisce il nome, è pesantemente basata sui Template (Lezione 16). Questo significa che la STL vi fornisce lo “stampo” vuoto, e voi ci inserite dentro il tipo che volete (int, double, Layer, std::unique_ptr<Layer>).

I Tre Pilastri della STL

L’architettura della STL è un capolavoro di ingegneria del software basata su tre concetti indipendenti ma interconnessi:

Containers (I Contenitori): Le strutture dati fisiche che tengono i dati in RAM (es. Vettori, Liste, Code, Mappe).
Algorithms (Gli Algoritmi): Funzioni matematiche pronte all’uso (ordinamento, ricerca, inversione) che non appartengono a un contenitore specifico.
Iterators (Gli Iteratori): Il “ponte” universale. Sono puntatori intelligenti che permettono agli Algoritmi di scorrere dentro i Containers, mantenendoli completamente disaccoppiati.

I Container (I Contenitori di Dati)

Esistono dozzine di Container nella STL, scelti in base alla complessità computazionale (Big O notation) dell’operazione che dovete fare più spesso.

Sequenziali: I dati sono in fila indiana (std::vector, std::list, std::deque).
Associativi: I dati sono organizzati per chiave di ricerca (std::map, std::set).
Adattatori: Cambiano l’interfaccia di altri container (std::queue FIFO, std::stack LIFO).

Inizieremo dal Re indiscusso dei container: std::vector.

Addio Array C (Buffer Overflow)

Ripassiamo perché gli Array del C (int arr[10];) sono il male.

int main() {
    int voti[3] = {28, 30, 24};
    
    // Il C non fa NESSUN CONTROLLO!
1    voti[5] = 18;
    
    // Non posso aggiungerne un quarto senza distruggere
    // l'array e ricrearne uno più grande a mano!
}

1: Questa riga scrive il numero 18 nella RAM di un altro programma o variabile. Si chiama Buffer Overflow, ed è la causa del 90% delle vulnerabilità hacker del pianeta.

Il Cavallo di Battaglia: `std::vector`

Lo std::vector (richiede #include <vector>) risolve tutto. È un Array Dinamico. Si ridimensiona da solo!

#include <vector>
#include <iostream>

int main() {
    std::vector<double> loss_history; // Vettore vuoto!
    
1    loss_history.push_back(0.99);
    loss_history.push_back(0.85);
    loss_history.push_back(0.40);
    
    std::cout << "Epoche processate: " << loss_history.size() << "\n";
    std::cout << "Loss all'epoca 0: " << loss_history[0] << "\n";
}

1: push_back accoda un nuovo elemento in fondo al vettore, e se la RAM non basta, ingrandisce il vettore automaticamente!

Allocazione Dinamica Automatica

Come fa il vector a non farvi fare delete?

Al suo interno, il std::vector è una Classe RAII. Contiene un puntatore dinamico allocato nello Heap. Quando il vettore va “fuori scope” (es. finisce il main), il suo Distruttore viene chiamato, ed esso invocherà automaticamente il delete[] sull’array interno, azzerando i Memory Leaks.

È un contenitore sicuro, pulito ed efficientissimo.

La Magia dell’Heap Contiguo

Il vector garantisce che i suoi elementi siano allocati in modo strettamente contiguo in memoria. Se l’elemento 0 è all’indirizzo 0x1000, l’elemento 1 sarà a 0x1004 (se sono interi).

Note

Questa è la proprietà più importante in assoluto per il Machine Learning! Le CPU moderne usano la Cache Memory. Leggere byte contigui in memoria è ordini di grandezza più veloce che saltellare in posizioni casuali della RAM (come farebbe una std::list).

Nel 99% dei casi, se vi serve una lista di oggetti, usate std::vector.

Size vs Capacity (Sotto il cofano)

Vi siete mai chiesti cosa succede quando fate push_back in un vettore pieno? Il vettore è costretto a chiedere al sistema operativo un nuovo blocco di RAM più grande, copiare tutti i vecchi dati, e distruggere il blocco vecchio.

Questa operazione (Reallocation) è LENTISSIMA. Per evitarla, il vettore chiede sempre molta più RAM di quanta gliene serva.

size(): Quanti elementi ci sono davvero nel vettore.
capacity(): Per quanti elementi c’è spazio prima di dover fare una catastrofica Reallocation.

Vettori Multidimensionali (Matrici)

Poiché i Template permettono di inscatolare qualsiasi cosa, potete inscatolare un Vettore dentro un Vettore! È così che si crea una Matrice dinamica in C++.

#include <vector>

int main() {
    int righe = 28;
    int colonne = 28;
    
    // Matrice 28x28 riempita di Zeri (0.0)
    std::vector<std::vector<double>> immagine(righe, std::vector<double>(colonne, 0.0));
    
    // Scriviamo un pixel!
    immagine[14][14] = 255.0; // Centro dell'immagine
}

(Nel vostro progetto finale userete librerie ottimizzate come Eigen per le matrici, ma la logica è identica!).

Il Vettore nella Rete Neurale

Eravamo rimasti alla Lezione 16 con la necessità di inglobare questo concetto nell’architettura della nostra Rete.

Uniamo il Potere dei Vettori con il C++11 (unique_ptr e move):

#include <vector>
#include <memory>

class Sequential {
private:
    // Array Dinamico di Puntatori Esclusivi a Layer
    std::vector<std::unique_ptr<Layer>> net;

public:
    void add(std::unique_ptr<Layer> l) {
        net.push_back(std::move(l)); // NESSUN LEAK, MAI!
    }
};

Il Vettore farà tutto il lavoro sporco. Noi penseremo solo all’algoritmo di training.

Dizionari: `std::map`

L’indice numerico di un array va bene se avete una sequenza. Ma se avete un Database? Supponiamo di voler salvare i nomi di vari Layer e la loro grandezza (numero di neuroni). Non vogliamo usare un array e iterare ogni volta per cercare il nome!

Vogliamo usare una Chiave (Stringa) per estrarre un Valore (Intero).

Questo contenitore Associativo in C++ si chiama std::map (o Dizionario in Python).

L’accesso per Chiave

La sintassi di std::map è tanto elegante quanto potente. Il primo Template parameter è il tipo della Chiave, il secondo è il tipo del Valore.

#include <map>
#include <string>
#include <iostream>

int main() {
    //        CHIAVE      VALORE
    std::map<std::string, int> dimensioni;
    
    // Inserimento intuitivo tramite operator[]
1    dimensioni["Dense_Input"] = 784;
    dimensioni["Dense_Hidden"] = 128;
    
    std::cout << "Neuroni Hidden: " << dimensioni["Dense_Hidden"] << "\n";
}

1: Creazione e Assegnazione in una singola riga! Se la chiave non esiste, viene creata al volo.

Sotto il Cofano: Red-Black Trees (Log N)

Dietro le quinte, std::map non usa un array, ma una struttura dati complessa chiamata Albero Rosso-Nero (Red-Black Tree).

Mantiene le chiavi sempre perfettamente Ordinate (alfabeticamente per le stringhe). Cercare un elemento tra un milione di chiavi richiede solo \(\approx 20\) step (Complessità computazionale: \(O(\log N)\)).

Se vi serve pura e bruta velocità e non vi interessa l’ordinamento, esiste una variante chiamata std::unordered_map (Hash Table) con complessità teorica \(O(1)\).

Inserimento e Ricerca Base

Come si usano i dizionari nella vita reale? Spesso li riempirete per salvare l’iperparametri di addestramento.

std::map<std::string, double> config;

config["LearningRate"] = 0.01;
config["Momentum"] = 0.9;
config["WeightDecay"] = 0.0001;

// Recupero il valore associato
double lr = config["LearningRate"];

Questa sintassi (tramite l’operatore parentesi quadra []) è la più usata al mondo.

Ma nasconde un difetto terribile.

L’Inconveniente Silenzioso dell’operatore `[]`

Warning

IL BUG PIÙ INSIDIOSO DEL C++ SULLE MAPPE

Cosa succede se, per un errore di battitura, cercate di leggere una chiave che non esiste?

std::cout << "Learning Rate: " << config["LearningRat"]; // Sbagliato il nome!

Il C++ non andrà in crash. E non vi darà Errore! Invece, secernerà silenziosamente una nuova chiave "LearningRat" nella mappa, e la inizializzerà al valore di default (zero). La stampa dirà Learning Rate: 0, sfalsando tutti i vostri calcoli matematici senza che ve ne accorgiate!

Usare il metodo `.find()` in sicurezza

Se non siete sicuri al 100% che la chiave esista, non usate MAI l’operatore [] per fare letture! Usate invece il metodo sicuro .find().

Esso restituisce un puntatore speciale (un Iteratore) che punta alla coppia Trovata. Se non la trova, punta all’abisso finale (ovvero a config.end()).

// .find() non crea MAI nulla. Cerca e basta.
auto it = config.find("LearningRat");

if (it != config.end()) {
    std::cout << "Trovato! Valore: " << it->second << "\n"; // 'second' è il valore
} else {
    std::cout << "ERRORE CRITICO! Parametro inesistente!\n";
}

Come muoversi nei Dati?

Torniamo allo std::vector. Come facciamo a stampare tutti i numeri al suo interno? Fin dal 1970 avete imparato a usare un contatore numerico i:

std::vector<double> v = {1.1, 2.2, 3.3};

for (int i = 0; i < v.size(); i++) {
    std::cout << v[i] << "\n";
}

Funziona perfettamente. Ma sapete perché? Perché l’accesso v[i] è istantaneo (memoria contigua). E se i dati non fossero contigui? (Esempio: gli Alberi di std::map). Come fate un ciclo su un Albero? Lì non esiste nessun “indice i-esimo”!

Gli Iteratori (Il Ponte Universale)

Per risolvere l’iterazione sulle strutture dati complesse (Alberi, Grafo, Liste concatenate), la STL usa gli Iteratori.

Un Iteratore si comporta esattamente come un Puntatore grezzo del C (*ptr), ma è un oggetto intelligente che sa come “scavalcare” da un nodo all’altro della struttura dati quando gli dite di avanzare (ptr++), ignorando l’effettiva architettura di RAM sottostante!

`begin()` e `end()`

Tutti i Container STL posseggono due funzioni magiche: - container.begin(): Restituisce un iteratore che punta al primissimo elemento. - container.end(): Restituisce un iteratore che punta nel vuoto cosmico sùbito dopo l’ultimo elemento. Serve solo come limite di terminazione.

Usando questi due limiti, è possibile iterare su qualsiasi contenitore dell’Universo senza sapere come sia fatto dentro.

Il For Loop della “Vecchia Scuola” (C++98)

Prima del 2011, si scriveva un ciclo universale tramite Iteratori in questo modo terribile e prolisso:

std::vector<double> v = {1.1, 2.2, 3.3};

// Sintassi terrificante del C++98
for (std::vector<double>::iterator it = v.begin(); it != v.end(); ++it) 
{
    // Dereferenzio il puntatore con l'asterisco per avere il valore fisico
    std::cout << *it << "\n"; 
}

Lungo, difficile da leggere, pieno di keyword incomprensibili. Molti studenti odiavano il C++ per colpa di righe del genere.

Il Miracolo del C++11

Nel 2011, i designer del C++ hanno capito che la sintassi era indigeribile, e hanno creato due strumenti mastodontici per semplificarci la vita.

1. La keyword auto: Dice al compilatore: “Ehi, sei intelligente, lo sai qual è il tipo che esce da v.begin(). Scrivitelo da solo senza farmi impazzire”.

auto it = v.begin(); // 'it' diventa automaticamente un iterator!

2. Il Range-based For Loop: Un costrutto speciale che nasconde del tutto la logica degli iteratori begin() ed end() sotto al tappeto!

Range-based For Loop

È la sintassi definitiva, quella che userete nel 99% dei vostri file. Significa letteralmente: “Per ogni elemento all’interno del contenitore”.

std::vector<double> v = {1.1, 2.2, 3.3};

// "Per ogni 'valore' nel vettore 'v'"
for (double valore : v) {
    std::cout << valore << "\n";
}

Basta. Niente iteratori, niente asterischi, niente size(). Il C++ fa tutto il lavoro noioso in background garantendo le massime performance.

La Regola d’Oro di `auto`

Attenzione però, il codice della slide precedente crea una Copia Fisica del valore a ogni iterazione! Se al posto di double avessimo avuto dei DenseLayer, clonare il Layer ad ogni ciclo sarebbe catastrofico.

Tip

Ecco il Vangelo dei For Loop in C++11:

for (auto x : v) -> Sola Lettura. Fa una Copia. Usare solo per tipi piccoli (int, double).
for (auto& x : v) -> Lettura/Scrittura. Usa Reference. Se modifichi x, modifichi l’originale in v.
for (const auto& x : v) -> Sola Lettura, ma usa Reference. Zero copie. Massima Sicurezza. È IL VOSTRO DEFAULT ASSOLUTO PER OGGETTI GRANDI!

Ciclare su una Mappa (Coppie)

Il Range-Based For Loop diventa magico sulle Mappe! Dato che una mappa associa una Chiave a un Valore, ogni elemento che vi torna indietro durante il ciclo è un oggetto doppio, di tipo std::pair. Esso possiede una variabile .first (la chiave) e .second (il valore).

std::map<std::string, double> config = {{"LearningRate", 0.01}, {"Momentum", 0.9}};

// const auto& perché le stringhe sono pesanti da copiare!
for (const auto& coppia : config) { 
    std::cout << "Parametro: " << coppia.first 
              << " | Valore: " << coppia.second << "\n";
}

`std::algorithm` (Perché scrivere For?)

E se invece di stampare i numeri volessimo contare quante Loss negative ci sono nell’array? O sommarle? O trovare la massima?

I novizi scrivono a mano cicli for enormi con contatori, flag temporanei e variabili d’appoggio.

I programmatori esperti aprono la <algorithm>. Questa super-libreria usa gli Iteratori per fornirvi la funzione matematica universale in una sola riga di codice pulito.

Esempi di Algoritmi (sort, find)

Includete sempre <algorithm> prima di usarli! Quasi tutti prendono un begin() e un end() come coordinate in cui operare.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {99, 10, 50, 5};
    
    // Ordinamento crescente in un colpo solo (QuickSort ottimizzato)
    std::sort(v.begin(), v.end()); 
    // Ora v è {5, 10, 50, 99}
    
    // Trova l'elemento massimo in tutto l'array
    auto max_it = std::max_element(v.begin(), v.end());
    std::cout << "Il numero più grande è: " << *max_it << "\n";
}

Con 2 righe avete risparmiato 20 righe di noioso codice manuale ad alto rischio bug.

Esercizio Pratico: Dizionario dei Pesi (10 min)

Usiamo l’incredibile potenza della STL.

Crea StlTest.cpp; includi <iostream>, <map>, <string>.
Nel main, istanzia una std::map<std::string, double> Pesi.
Inserisci tre neuroni con pesi arbitrari (es. Pesi["N1"] = 0.5; Pesi["N2"] = -1.2; ...).
Prova a stampare il valore di un neurone inesistente "N99" con la quadra []. Guarda cosa succede.
Usa invece .find(): verifica che non crei la chiave.
Con un Range-Based For Loop (const auto& x : Pesi) stampa tutte le coppie: nota che sono ordinate alfabeticamente.

Programmazione Scientifica++: Lezione 18

Argomenti di Oggi

Reinventare la Ruota

La Standard Template Library (STL)

I Tre Pilastri della STL

I Container (I Contenitori di Dati)

Addio Array C (Buffer Overflow)

Il Cavallo di Battaglia: std::vector

Allocazione Dinamica Automatica

La Magia dell’Heap Contiguo

Size vs Capacity (Sotto il cofano)

Vettori Multidimensionali (Matrici)

Il Vettore nella Rete Neurale

Dizionari: std::map

L’accesso per Chiave

Sotto il Cofano: Red-Black Trees (Log N)

Inserimento e Ricerca Base

L’Inconveniente Silenzioso dell’operatore []

Usare il metodo .find() in sicurezza

Come muoversi nei Dati?

Gli Iteratori (Il Ponte Universale)

begin() e end()

Il For Loop della “Vecchia Scuola” (C++98)

Il Miracolo del C++11

Range-based For Loop

La Regola d’Oro di auto

Ciclare su una Mappa (Coppie)

std::algorithm (Perché scrivere For?)

Esempi di Algoritmi (sort, find)

Esercizio Pratico: Dizionario dei Pesi (10 min)

Il Cavallo di Battaglia: `std::vector`

Dizionari: `std::map`

L’Inconveniente Silenzioso dell’operatore `[]`

Usare il metodo `.find()` in sicurezza

`begin()` e `end()`

La Regola d’Oro di `auto`

`std::algorithm` (Perché scrivere For?)