#Standard Template Library (STL)
#IntroduzioneLa Standard Template Library (abbr. STL) è una collezione di algoritmi, strumenti e strutture dati pensate per essere facilmente integrate nel codice. Nell’ambito della programmazione competitiva vengono spesso utilizzate per via della loro semplicità d’uso e velocità di implementazione. La documentazione della STL è disponibile su https://www.cppreference.com, da cui è anche possibile consultare la complessità temporale delle operazioni sulle strutture.
Tutte le funzionalità della STL sono racchiuse dal namespace std. Per comodità possiamo includere all’inizio del codice tutto il namespace tramite using namespace std;, in modo da scrivere, per esempio, vector<int> invece di std::vector<int>. Inoltre, ogni funzionalità della STL è racchiusa in una libreria che andrà importata all’inizio del file. Ad esempio, vector sta nella libreria <vector>, sort sta in <algorithm>, e così via. Anche qui possiamo semplificarci la vita usando la libreria <bits/stdc++.h> che include automaticamente quasi1 tutta la STL. Da ora in avanti, assumeremo che il namespace std e <bits/stdc++.h> siano stati importati.
#include <bits/stdc++.h>
using namespace std;
#Strutture datiUna struttura dati è un modo intelligente di organizzare le informazioni per supportare determinate operazioni in maniera efficiente. In questo capitolo studiamo come sfruttare al meglio alcune strutture dati già implementate nella libreria standard C++, cioè vector, queue, pair, set, priority_queue, map.
Alcune strutture dati più complesse non sono implementate nella STL, e andranno perciò implementate a mano. Ci occuperemo di queste strutture nei capitoli futuri.
Inoltre, tutte le strutture della STL supportano queste operazioni:
OperazioneComplessitàDettagli
size()𝒪︀(1)Restituisce il numero di elementi contenuti.
empty()𝒪︀(1)Restituisce true se la struttura non contiene elementi.
#IteratoriUn iteratore è un oggetto che punta a uno specifico elemento della struttura dati. Sotto molti punti di vista è simile a un puntatore. Gli iteratori sono molto utili e vengono usati da molte funzioni della STL. Per accedere all’elemento puntato dall’iteratore, lo precediamo con un * (dereferenziazione). Vediamo un esempio:
vector<int> a = {10, 20, 30};
auto it = a.begin(); // it punta a 10
cout << *it << endl; // stampa 10
it++; // it punta a 20
cout << *it << endl; // stampa 20
Possiamo passare all’elemento successivo con next(it) (oppure incrementando direttamente l’iteratore con ++it o it++), e a quello precedente con prev(it) (oppure --it). Inoltre, è importante notare che se abbiamo una struttura, ad esempio un vettore V, allora V.begin() punta al primo elemento del vettore (se esiste), mentre V.end() punta alla posizione subito dopo l’ultimo elemento (ovvero a memoria non allocata). Se V è vuoto, vale V.begin() == V.end().
#vectorinclusa in <vector>
vector è forse la struttura dati più semplice della STL: può essere pensato come un array dinamico, che si ridimensiona automaticamente quando necessario.
Supporta le seguenti operazioni principali:
OperazioneComplessitàDettagli
push_back(x)𝒪︀(1) ammortizzataAggiunge x in fondo al vettore.
pop_back()𝒪︀(1)Rimuove l’ultimo elemento del vettore.
at(i)𝒪︀(1)Restituisce un riferimento all’elemento in posizione i. Si può ottenere lo stesso effetto (ma senza controllo dei limiti, più veloce) con l’operatore [i].
insert(it, x)𝒪︀(𝑁)2Inserisce x nella posizione indicata dall’iteratore it. Richiede lo spostamento di tutti gli elementi successivi.
erase(it)𝒪︀(𝑁)Rimuove l’elemento nella posizione indicata da it.
clear()𝒪︀(𝑁)Rimuove tutti gli elementi.
front() / back()𝒪︀(1)Restituiscono un riferimento rispettivamente al primo e all’ultimo elemento.
begin() / end()𝒪︀(1)Restituiscono iteratori all’inizio e alla fine del vettore.
resize(n)𝒪︀(𝑁)Ridimensiona il vettore in modo che contenga n elementi. Se n è minore della dimensione attuale, gli elementi in eccesso vengono rimossi; se è maggiore, i nuovi elementi vengono inizializzati con il valore di default (o con il valore passato come secondo argomento opzionale resize(n, val)). Nota bene: resize non rimuove gli elementi già presenti: se n è maggiore della dimensione attuale, gli elementi esistenti rimangono invariati e vengono semplicemente aggiunti nuovi elementi in coda, mentre se n è minore, i primi n elementi vengono mantenuti e solo quelli in eccesso vengono rimossi.
push_back è 𝒪︀(1) ammortizzata perché, quando il vettore esaurisce lo spazio allocato, la sua capacità viene raddoppiata e tutti gli elementi vengono ricopiati in un nuovo blocco di memoria contiguo, il che ha complessità 𝒪︀(𝑁). Per risparmiare tempo, se sappiamo in anticipo quanti elementi avrà il nostro vettore (anche una stima per eccesso va bene), possiamo preallocare la memoria per 𝑛 elementi tramite reserve(n).
Nota bene: alcune operazioni, come push_back, insert o erase, possono invalidare gli iteratori esistenti su un vector (ad esempio se il vettore viene ricopiato in un nuovo blocco di memoria durante un ridimensionamento). Usare un iteratore invalidato genera un comportamento indefinito.
#queueinclusa in <queue>
queue è una struttura dati che implementa una coda FIFO (First In, First Out): l’elemento che viene inserito per primo è anche il primo a essere rimosso. Permette di eseguire le seguenti operazioni:
OperazioneComplessitàDettagli
push(x)𝒪︀(1)Inserisce l’elemento x in fondo alla coda.
pop()𝒪︀(1)Rimuove l’elemento in cima alla coda (il primo inserito).
front() / back()𝒪︀(1)Restituiscono un riferimento rispettivamente al primo e all’ultimo elemento.
La queue permette di rimuovere elementi solo in cima alla coda, non dal fondo.
Vediamo un esempio:
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << q.front() << endl; // stampa 1 (il primo inserito)
cout << q.back() << endl; // stampa 3 (l'ultimo inserito)
q.pop(); // rimuove 1
cout << q.front() << endl; // stampa 2
#pairinclusa in <utility>
pair non è propriamente una struttura dati, ma un semplice contenitore che raggruppa due valori (anche di tipo diverso) in un unico oggetto. È molto usato insieme ad altre strutture della STL (ad esempio dentro un vector<pair<int,int>>). I membri principali sono:
•first: Il primo valore della coppia.•second: Il secondo valore della coppia.Si può creare con make_pair(a, b) oppure direttamente con la sintassi {a, b}.
Inoltre, pair supporta il confronto (<, ==, ecc.) nel seguente modo: confronta prima .first, e solo in caso di parità confronta .second. Questo lo rende molto comodo da usare all’interno di un set o per l’ordinamento (sort) di un vector di coppie.
Vediamo un esempio:
pair<int, string> p = {1, "oii"};
cout << p.first << " " << p.second << endl; // stampa: 1 oii
vector<pair<int, int>> v;
v.push_back({3, 1});
v.push_back({1, 2});
v.push_back({1, 1});
sort(v.begin(), v.end());
// dopo il sort: (1,1), (1,2), (3,1)
#setinclusa in <set>
set è una struttura dati che immagazzina una serie di elementi in modo ordinato, e permette di eseguire le seguenti operazioni:
OperazioneComplessitàDettagli
insert(x)𝒪︀(log𝑁)Inserisce l’elemento x nel set.
erase(x)𝒪︀(log𝑁)Rimuove l’elemento x dal set. Se x non è presente, l’operazione non ha effetto.
find(x)𝒪︀(log𝑁)Trova l’elemento x e restituisce un iteratore a esso. Se x non è presente, restituisce un iteratore all’elemento subito dopo l’ultimo.
begin() / end()𝒪︀(1)Restituiscono iteratori all’inizio e alla fine del set. begin() punta al primo elemento, end() alla posizione subito dopo l’ultimo.
clear()𝒪︀(𝑁)Rimuove tutti gli elementi.
Nota bene: set salva una sola copia degli elementi (ovvero non si possono avere elementi duplicati). Una struttura analoga che consente di memorizzare elementi duplicati è multiset.
Vediamo come usare un set in un semplice esempio:
set<int> s;
s.insert(5);
s.insert(1);
s.insert(3);
s.insert(1); // non ha effetto, 1 è già presente
for (int x : s)
cout << x << " "; // stampa: 1 3 5 (ordinati)
cout << endl;
if (s.find(3) != s.end()) {
cout << "3 è presente nel set" << endl;
}
s.erase(3);
cout << s.size() << endl; // stampa 2
Consideriamo un altro esempio pratico.
Room Allocation CSES
L’Olinfo Hotel vuole ospitare 𝑁 clienti, l’𝑖-esimo dei quali vuole alloggiare in una stanza dal giorno 𝐿𝑖 al giorno 𝑅𝑖. Una stanza non può essere occupata simultaneamente da più persone (cioè affinché due ospiti possano alloggiare nella stessa stanza, i loro intervalli [𝐿𝑖,𝑅𝑖], [𝐿𝑗,𝑅𝑗] devono essere disgiunti). Qual è il numero minimo di stanze affinché l’Olinfo Hotel possa ospitare tutti? Se la risposta è 𝐾, stabilisci per ogni ospite un numero di stanza da 1 a 𝐾.
𝑁≤2⋅105, 1≤𝐿𝑖≤𝑅𝑖≤109.
Prova il problema online: https://cses.fi/problemset/task/1164
Soluzione
Intuitivamente, è ottimale ordinare gli eventi in ordine cronologico, per poi simulare la partenza e l’arrivo di ogni cliente nell’ordine giusto. A questo punto, ogni volta che arriva un cliente, è ottimale assegnargli la stanza libera con numero minimo.
Come trovare la stanza libera con numero minimo? Se controlliamo le stanze una a una, impieghiamo 𝒪︀(𝑁) per cliente nel caso pessimo (ad esempio, se l’unica stanza libera è l’ultima): serve una struttura dati più veloce. Un set è particolarmente adatto perché supporta l’estrazione dell’elemento minimo in tempo 𝒪︀(log𝑁).
Vorremmo quindi inizializzare un set che contiene tutte le stanze libere, ma non sappiamo quante sono. In ogni caso, usiamo al massimo 𝑁 stanze, per cui possiamo inizializzare il set con tutti gli interi da 1 a 𝑁. Ora:
•ogni volta che un nuovo cliente arriva, estraiamo (e rimuoviamo) il minimo elemento dal set;•ogni volta che un cliente lascia l’hotel, aggiungiamo nel set il suo numero di stanza.Attenzione: ogni giorno, è importante processare prima gli arrivi e poi le partenze, altrimenti un cliente potrebbe lasciare una stanza e un altro cliente potrebbe occuparla il giorno stesso.
Segue una possibile implementazione. Nota che stiamo ordinando gli eventi prima per tempo, e a parità di tempo per tipo (prima gli arrivi, poi le partenze).
int n;
cin >> n;
vector<array<int, 3>> eventi;
for (int i = 0, l, r; i < n; i++) {
cin >> l >> r;
eventi.push_back({l, 0, i});
eventi.push_back({r, 1, i});
}
set<int> libere;
for (int i = 1; i <= n; i++)
libere.insert(i);
sort(begin(eventi), end(eventi));
vector<int> stanza(n, -1);
for (auto [tempo, tipo, cliente] : eventi) {
if (tipo == 0) {
stanza[cliente] = *begin(libere);
libere.erase(begin(libere));
} else {
libere.insert(stanza[cliente]);
}
}
cout << *max_element(begin(stanza), end(stanza)) << "\n";
for (auto u : stanza)
cout << u << ' ';
cout << "\n";
#priority_queueinclusa in <queue>
priority_queue è una struttura dati che immagazzina una serie di elementi e permette di accedere rapidamente al massimo tra essi (o al minimo, se configurata opportunamente). Nonostante il nome, una priority_queue è concettualmente più simile a un multiset che a una queue. A differenza di set, non mantiene gli elementi ordinati internamente in modo accessibile, e non supporta iteratori né la ricerca di un elemento arbitrario, ma supporta elementi duplicati. Permette di eseguire le seguenti operazioni:
OperazioneComplessitàDettagli
push(x)𝒪︀(log𝑁)Inserisce l’elemento x nella coda.
pop()𝒪︀(log𝑁)Rimuove l’elemento massimo dalla coda.
top()𝒪︀(1)Restituisce (senza rimuoverlo) l’elemento massimo attualmente presente nella coda.
Sebbene una priority_queue possa sembrare una versione ridotta di multiset, essa presenta un grande vantaggio: è circa 2-5 volte più veloce nelle operazioni di inserimento e rimozione.
Vediamo un esempio:
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1); // duplicato, va bene
cout << pq.top() << endl; // stampa 4 (il massimo)
pq.pop();
cout << pq.top() << endl; // stampa 3
// per ottenere una min-priority_queue:
priority_queue<int, vector<int>, greater<int>> pq_min;
pq_min.push(3);
pq_min.push(1);
pq_min.push(4);
cout << pq_min.top() << endl; // stampa 1 (il minimo)
#mapinclusa in <map>
map è una struttura dati che immagazzina una serie di coppie chiave-valore, mantenute ordinate in base alla chiave. Può essere vista come un set in cui a ogni elemento (la chiave) è associato anche un valore. Permette di eseguire le seguenti operazioni:
OperazioneComplessitàDettagli
insert({k, v})𝒪︀(log𝑁)Inserisce la coppia chiave-valore. Se la chiave k è già presente, insert non ha effetto, mentre [k] = v sovrascrive il valore associato.
erase(k)𝒪︀(log𝑁)Rimuove la coppia con chiave k. Se k non è presente, l’operazione non ha effetto.
find(k)𝒪︀(log𝑁)Trova la chiave k e restituisce un iteratore alla coppia corrispondente. Se k non è presente, restituisce un iteratore all’elemento subito dopo l’ultimo (cioè uguale a end()).
[k]𝒪︀(log𝑁)Restituisce (o crea, se non esiste) un riferimento al valore associato alla chiave k. Attenzione: accedere con [k] a una chiave non presente la inserisce automaticamente nella mappa con un valore di default.
begin() / end()𝒪︀(1)Restituiscono iteratori all’inizio e alla fine della map (in ordine di chiave crescente).
clear()𝒪︀(𝑁)Rimuove tutti gli elementi.
Dereferenziando un iteratore di map si ottiene una pair<K, V>, dove .first è la chiave e .second è il valore.
Vediamo un esempio:
map<string, int> m;
m["oii"] = 3;
m["oia"] = 5;
m.insert({"egoi", 7});
cout << m["oii"] << endl; // stampa 3
for (pair<string, int> p : m) { // p.first è la chiave, p.second il valore
cout << p.first << ": " << p.second << endl; // ordine alfabetico delle chiavi
}
if (m.find("oia") != m.end()) {
cout << "oia è presente" << endl;
}
m.erase("oia");
cout << m.size() << endl; // stampa 2
cout << m["swerc"] << endl; // stampa 0 e inserisce "swerc" con valore 0
#stringinclusa in <string>
string rappresenta una sequenza di caratteri e viene utilizzata per gestire il testo. È possibile accedere ai singoli caratteri tramite il loro indice, che parte da 0, come negli array e nei vector.
Le operazioni più utilizzate sono:
OperazioneComplessitàDettagli
[i] / at(i)𝒪︀(1)Restituiscono il carattere in posizione i.
size() / length()𝒪︀(1)Restituiscono il numero di caratteri della stringa.
push_back(c) / pop_back()𝒪︀(1) ammortizzataAggiungono o rimuovono un carattere alla fine della stringa.
substr(pos, len)𝒪︀(𝑀)Restituisce la sottostringa di lunghezza len che inizia in posizione pos, dove M è la lunghezza della sottostringa.
find(t)𝒪︀(𝑁𝑀)Restituisce la prima posizione in cui compare t, oppure string::npos se non viene trovata.
erase(pos, len) / insert(pos, t)𝒪︀(𝑁)Rimuovono o inseriscono caratteri nella posizione indicata.
Le stringhe possono essere concatenate con + e confrontate direttamente con gli operatori ==, !=, <, <=, > e >=. I confronti lessicografici usano l’ordine dei caratteri.
string s = "grazie";
s += " dario";
s.push_back('!');
cout << s << endl; // stampa: grazie dario!
cout << s.substr(7, 5) << endl; // stampa: dario
auto pos = s.find("dario");
if (pos != string::npos)
cout << pos << endl; // stampa 7
Nota bene: usare cin per leggere una stringa può causare problemi se questa contiene spazi. In particolare, cin legge l’input fino a quando non trova uno spazio o la riga è terminata, quindi la stringa verrebbe “spezzata” a ogni spazio. Se vogliamo leggere una riga per intero possiamo usare getline come illustrato nell’esempio:
string s;
getline(cin, s);
#Problemi consigliati
Tieni aggiornato il catalogo (https://training.olinfo.it/task/catalogo)
Soste in autostrada (https://training.olinfo.it/task/autogrill)
Quantum Brackets (https://training.olinfo.it/task/ois_brackets)
Festa Estiva (https://training.olinfo.it/task/pre-egoi-festaestiva)
Overtakings (https://training.olinfo.it/task/ois_g1)
Concert Tickets (https://cses.fi/alon/task/1091)
Traffic Lights (https://cses.fi/ckvo8q5wh/task/1163)
Mattia e i suoi vasi (https://training.olinfo.it/task/vasi)
1Alcune funzionalità come le PBDS non sono incluse.2𝑁 è il numero di elementi contenuti dentro la struttura dati al momento dell'operazione.