Conteneurs de la STL

Fait partie de la section Programmation Orientée Objet du Journey C++ de Coddy — leçon 71 sur 104.

Les conteneurs STL sont des classes templates qui stockent et organisent des collections d'objets. Chaque type de conteneur est optimisé pour différents modèles d'accès et opérations. Choisir le bon conteneur pour vos besoins peut avoir un impact significatif sur les performances de votre programme.

Les conteneurs de séquence maintiennent les éléments dans un ordre spécifique :

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Tableau dynamique, accès aléatoire rapide
vec.push_back(4);                   // Ajout à la fin : O(1) amorti
int x = vec[2];                     // Accès par index : O(1)

std::list<int> lst = {1, 2, 3};    // Liste doublement chaînée
lst.push_front(0);                  // Ajout au début : O(1)
lst.push_back(4);                   // Ajout à la fin : O(1)

Les conteneurs associatifs stockent les éléments dans un ordre trié pour une recherche rapide :

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Éléments triés uniques : {1, 3, 4}
s.insert(2);                        // Insertion : O(log n)
bool found = s.count(3);            // Vérifier l'existence : O(log n)

std::map<std::string, int> ages;   // Paires clé-valeur, triées par clé
ages["Alice"] = 25;                 // Insertion/mise à jour : O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Accès : O(log n)

Les conteneurs non ordonnés utilisent des tables de hachage pour une recherche encore plus rapide dans le cas moyen :

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Insertion : O(1) en moyenne
scores["player2"] = 200;
std::cout << scores["player1"];    // Accès : O(1) en moyenne

Utilisez vector lorsque vous avez besoin d'un accès aléatoire rapide, list pour des insertions fréquentes au milieu, map/set lorsque vous avez besoin de données triées, et unordered_map lorsque la vitesse de recherche est critique et que l'ordre n'a pas d'importance.

Défi

Facile

Construisons un système de gestion des notes des étudiants qui démontre comment différents conteneurs STL servent à des fins différentes. Vous utiliserez plusieurs types de conteneurs pour organiser efficacement les données des étudiants, en choisissant le bon conteneur pour chaque tâche.

Vous créerez deux fichiers pour organiser votre code :

GradeManager.h : Définissez une classe GradeManager qui utilise plusieurs conteneurs STL pour gérer les informations des étudiants.
Votre classe doit utiliser :
- Un std::vector<std::string> pour stocker les noms des étudiants dans l'ordre où ils ont été ajoutés
- Un std::map<std::string, int> pour associer chaque nom d'étudiant à sa note
- Un std::set<int> pour suivre toutes les notes uniques qui ont été attribuées
Implémentez ces méthodes :
- addStudent(const std::string& name, int grade) — ajoute un étudiant avec sa note dans les trois conteneurs
- getGrade(const std::string& name) — retourne la note pour un nom d'étudiant donné en utilisant la map
- printRoster() — affiche tous les noms d'étudiants dans l'ordre où ils ont été ajoutés (à partir du vecteur), chacun sur une nouvelle ligne
- printGrades() — affiche tous les étudiants avec leurs notes par ordre alphabétique (la map gère cela automatiquement), formaté comme name: grade sur chaque ligne
- printUniqueGrades() — affiche toutes les notes uniques par ordre croissant (le set gère cela), séparées par des espaces suivis d'un saut de ligne
main.cpp : Lisez les entrées et démontrez comment chaque type de conteneur sert un objectif différent.
Lisez six entrées (chacune sur une ligne séparée) :
1. Nom du premier étudiant
2. Note du premier étudiant (entier)
3. Nom du deuxième étudiant
4. Note du deuxième étudiant (entier)
5. Nom du troisième étudiant
6. Note du troisième étudiant (entier)
Créez un GradeManager et ajoutez les trois étudiants. Ensuite, démontrez les différents comportements des conteneurs :
1. Affichez Roster (insertion order): suivi de l'appel à printRoster()
2. Affichez Grades (alphabetical): suivi de l'appel à printGrades()
3. Affichez Unique grades: suivi de l'appel à printUniqueGrades()
4. Recherchez la note du deuxième étudiant et affichez <name>'s grade: <grade>

Par exemple, avec les entrées 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

Remarquez comment le vecteur préserve l'ordre d'insertion (Charlie, Alice, Bob), la map trie automatiquement par clé (Alice, Bob, Charlie), et le set ne stocke que des valeurs uniques dans l'ordre trié (85 apparaît une fois, pas deux). Chaque type de conteneur excelle dans des tâches différentes !

Aide-mémoire

Les conteneurs STL sont des classes templates pour stocker et organiser des collections d'objets. Chaque type est optimisé pour différentes opérations.

Conteneurs de Séquence

Maintiennent les éléments dans un ordre spécifique :

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Dynamic array, fast random access
vec.push_back(4);                   // Add to end: O(1) amortized
int x = vec[2];                     // Access by index: O(1)

std::list<int> lst = {1, 2, 3};    // Doubly-linked list
lst.push_front(0);                  // Add to front: O(1)
lst.push_back(4);                   // Add to end: O(1)

Conteneurs Associatifs

Stockent les éléments dans un ordre trié pour une recherche rapide :

#include <map>
#include <set>

std::set<int> s = {3, 1, 4, 1};    // Unique sorted elements: {1, 3, 4}
s.insert(2);                        // Insert: O(log n)
bool found = s.count(3);            // Check existence: O(log n)

std::map<std::string, int> ages;   // Key-value pairs, sorted by key
ages["Alice"] = 25;                 // Insert/update: O(log n)
ages["Bob"] = 30;
std::cout << ages["Alice"];        // Access: O(log n)

Conteneurs Non Ordonnés

Utilisent des tables de hachage pour une recherche plus rapide dans le cas moyen :

#include <unordered_map>

std::unordered_map<std::string, int> scores;
scores["player1"] = 100;            // Insert: O(1) average
scores["player2"] = 200;
std::cout << scores["player1"];    // Access: O(1) average

Choisir le Bon Conteneur

vector : Accès aléatoire rapide
list : Insertions fréquentes au milieu
map/set : Données triées nécessaires
unordered_map : Vitesse de recherche critique, l'ordre n'importe pas

Essayez vous-même

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

using namespace std;

int main() {
    // Lire les entrées pour trois étudiants
    string name1, name2, name3;
    int grade1, grade2, grade3;
    
    cin >> name1;
    cin >> grade1;
    cin >> name2;
    cin >> grade2;
    cin >> name3;
    cin >> grade3;
    
    // TODO: Créer un objet GradeManager
    
    // TODO: Ajouter les trois étudiants au GradeManager
    
    // TODO: Afficher "Roster (insertion order):" et appeler printRoster()
    
    // TODO: Afficher "Grades (alphabetical):" et appeler printGrades()
    
    // TODO: Afficher "Unique grades:" et appeler printUniqueGrades()
    
    // TODO: Rechercher la note du deuxième étudiant et afficher "<name>'s grade: <grade>"
    
    return 0;
}