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 modèles qui stockent et organisent des collections d’objets. Chaque type de conteneur est optimisé pour différents schémas d’accès et opérations. Choisir le conteneur adapté à vos besoins peut avoir un impact significatif sur les performances de votre programme.

Les conteneurs séquentiels maintiennent les éléments dans un ordre précis :

#include <vector>
#include <list>

std::vector<int> vec = {1, 2, 3};  // Tableau dynamique, accès aléatoire rapide
vec.push_back(4);                   // Ajouter à 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);                  // Ajouter au début : O(1)
lst.push_back(4);                   // Ajouter à 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 uniques triés : {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 en moyenne :

#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 essentielle et que l’ordre n’a pas d’importance.

Défi

Facile

Construisons un système de gestion des notes des étudiants qui montre comment différents conteneurs STL répondent à différents besoins. Tu utiliseras plusieurs types de conteneurs pour organiser efficacement les données des étudiants, en choisissant le conteneur approprié pour chaque tâche.

Tu créeras deux fichiers pour organiser ton code :

GradeManager.h : définir une classe GradeManager qui utilise plusieurs conteneurs STL pour gérer les informations des étudiants.
Ta classe doit utiliser :
- Un std::vector<std::string> pour stocker les noms des étudiants dans l'ordre où ils ont été ajoutés
- Une 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émente ces méthodes :
- addStudent(const std::string& name, int grade) : ajoute un étudiant et sa note dans les trois conteneurs
- getGrade(const std::string& name) : renvoie la note correspondant à un nom d'étudiant donné en utilisant la map
- printRoster() : affiche tous les noms des étudiants dans l'ordre où ils ont été ajoutés (depuis le vector), chacun sur une nouvelle ligne
- printGrades() : affiche tous les étudiants avec leurs notes dans l'ordre alphabétique (la map s'en charge automatiquement), au format name: grade sur chaque ligne
- printUniqueGrades() : affiche toutes les notes uniques dans l'ordre croissant (le set s'en charge), séparées par des espaces et suivies d'un saut de ligne
main.cpp : lire les entrées et montrer comment chaque type de conteneur répond à un besoin différent.
Lis six entrées (chacune sur une ligne distincte) :
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ée un GradeManager et ajoute les trois étudiants. Montre ensuite les différents comportements des conteneurs :
1. Afficher Roster (insertion order):, puis appeler printRoster()
2. Afficher Grades (alphabetical):, puis appeler printGrades()
3. Afficher Unique grades:, puis appeler printUniqueGrades()
4. Rechercher la note du deuxième étudiant et afficher <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

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

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: Print "Roster (insertion order):" and call printRoster()
    
    // TODO: Print "Grades (alphabetical):" and call printGrades()
    
    // TODO: Print "Unique grades:" and call printUniqueGrades()
    
    // TODO: Rechercher la note du deuxième étudiant et afficher "<name>'s grade: <grade>"
    
    return 0;
}