Contenitori STL

Fa parte della sezione Programmazione orientata agli oggetti del percorso C++ di Coddy. Lezione 71 di 104.

I contenitori STL sono classi template che memorizzano e organizzano raccolte di oggetti. Ogni tipo di contenitore è ottimizzato per diversi schemi di accesso e operazioni. Scegliere il contenitore giusto per le tue esigenze può influire significativamente sulle prestazioni del tuo programma.

I contenitori sequenziali mantengono gli elementi in un ordine specifico:

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Array dinamico, accesso casuale rapido
vec.push_back(4);                   // Aggiunta in fondo: O(1) ammortizzato
int x = vec[2];                     // Accesso per indice: O(1)

std::list<int> lst = {1, 2, 3};    // Lista doppiamente concatenata
lst.push_front(0);                  // Aggiunta all'inizio: O(1)
lst.push_back(4);                   // Aggiunta in fondo: O(1)

I contenitori associativi memorizzano gli elementi in ordine ordinato per consentire ricerche rapide:

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Elementi unici ordinati: {1, 3, 4}
s.insert(2);                        // Inserimento: O(log n)
bool found = s.count(3);            // Verifica dell'esistenza: O(log n)

std::map<std::string, int> ages;   // Coppie chiave-valore, ordinate per chiave
ages["Alice"] = 25;                 // Inserimento/aggiornamento: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Accesso: O(log n)

I contenitori non ordinati usano tabelle hash per una ricerca media ancora più veloce:

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Inserimento: O(1) in media
scores["player2"] = 200;
std::cout << scores["player1"];    // Accesso: O(1) in media

Usa vector quando ti serve un accesso casuale rapido, list per inserimenti frequenti nel mezzo, map/set quando ti servono dati ordinati e unordered_map quando la velocità di ricerca è fondamentale e l’ordine non è importante.

Sfida

Facile

Costruiamo un sistema di gestione dei voti degli studenti che mostri come i diversi contenitori STL siano adatti a scopi diversi. Userai più tipi di contenitori per organizzare in modo efficiente i dati degli studenti, scegliendo il contenitore giusto per ogni attività.

Creerai due file per organizzare il codice:

GradeManager.h: definisci una classe GradeManager che usa più contenitori STL per gestire le informazioni sugli studenti.
La tua classe dovrebbe usare:
- Un std::vector<std::string> per memorizzare i nomi degli studenti nell'ordine in cui sono stati aggiunti
- Un std::map<std::string, int> per associare ogni nome di studente al relativo voto
- Un std::set<int> per tenere traccia di tutti i voti unici assegnati
Implementa questi metodi:
- addStudent(const std::string& name, int grade): aggiunge uno studente con il relativo voto a tutti e tre i contenitori
- getGrade(const std::string& name): restituisce il voto di uno studente specificato usando la mappa
- printRoster(): stampa tutti i nomi degli studenti nell'ordine in cui sono stati aggiunti (dal vettore), ciascuno su una nuova riga
- printGrades(): stampa tutti gli studenti con i relativi voti in ordine alfabetico (la mappa lo gestisce automaticamente), nel formato name: grade su ogni riga
- printUniqueGrades(): stampa tutti i voti unici in ordine crescente (se ne occupa l'insieme), separati da spazi e seguiti da un carattere di nuova riga
main.cpp: leggi gli input e mostra come ogni tipo di contenitore sia adatto a uno scopo diverso.
Leggi sei input (ciascuno su una riga separata):
1. Nome del primo studente
2. Voto del primo studente (intero)
3. Nome del secondo studente
4. Voto del secondo studente (intero)
5. Nome del terzo studente
6. Voto del terzo studente (intero)
Crea un GradeManager e aggiungi tutti e tre gli studenti. Poi mostra i diversi comportamenti dei contenitori:
1. Stampa Roster (insertion order):, poi chiama printRoster()
2. Stampa Grades (alphabetical):, poi chiama printGrades()
3. Stampa Unique grades:, poi chiama printUniqueGrades()
4. Cerca il voto del secondo studente e stampa <name>'s grade: <grade>

Per esempio, con gli input Charlie, 85, Alice, 90, Bob, 85:

Roster (insertion order):
Charlie
Alice
Bob
Grades (alphabetical):
Alice: 90
Bob: 85
Charlie: 85
Unique grades:
85 90 
Alice's grade: 90

Nota come il vettore mantenga l'ordine di inserimento (Charlie, Alice, Bob), la mappa ordini automaticamente le chiavi (Alice, Bob, Charlie) e l'insieme memorizzi solo i valori unici in ordine crescente (85 compare una sola volta, non due). Ogni tipo di contenitore è ideale per attività diverse!

Provalo tu

#include <iostream>
#include <string>
#include "GradeManager.h"

using namespace std;

int main() {
    // Leggi i dati di input per tre studenti
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Crea un oggetto GradeManager
    
    // TODO: Aggiungi tutti e tre gli studenti a GradeManager
    
    // TODO: Stampa "Roster (insertion order):" e chiama printRoster()
    
    // TODO: Stampa "Grades (alphabetical):" e chiama printGrades()
    
    // TODO: Stampa "Unique grades:" e chiama printUniqueGrades()
    
    // TODO: Cerca il voto del secondo studente e stampa "<name>'s grade: <grade>"
    
    return 0;
}