Module 8 - cours du 27 octobre (quiz 7) - matière du final

STL : conteneurs et itérateurs

Leçon Moodle « Itérateurs et conteneurs » | Simulateur de hockey : exercice « Conteneurs » (afficherEquipe, afficherTroisEtoiles) | Horstmann, chapitre sur la bibliothèque standard | Sera mis en pratique au TP4

vector, deque, listset, map, multimapunordered_mapstack, queue, priority_queueItérateurs : begin, end, ++, *InvalidationChoisir un conteneur

1. La bibliothèque standard de structures de données

La STL (Standard Template Library) repose sur trois piliers indépendants : les conteneurs (structures qui stockent des objets), les itérateurs (une façon uniforme de parcourir n'importe quel conteneur) et les algorithmes (module 9), qui travaillent sur des itérateurs et fonctionnent donc avec tous les conteneurs. Les foncteurs et lambdas (module 9) paramètrent les algorithmes. Tout est générique : vector<T>, map<K, V>.

Famille	Conteneurs	Organisation	Points forts
Séquentiels	`vector`, `deque`, `list`, `array`, `forward_list`	ordre d'insertion, choisi par le programmeur	vector : accès par indice et insertion en fin ; deque : aussi en tête ; list : insertion et suppression n'importe où sans déplacer les autres
Associatifs ordonnés	`set`, `multiset`, `map`, `multimap`	arbre équilibré trié par `operator<` de la clé	recherche, insertion, suppression en O(log n) ; parcours trié
Associatifs non ordonnés	`unordered_set`, `unordered_map` (+ multi)	table de hachage	recherche en O(1) en moyenne ; pas d'ordre
Adaptateurs	`stack`, `queue`, `priority_queue`	interface restreinte au-dessus d'un autre conteneur	LIFO, FIFO, file de priorité (le plus grand d'abord)

Opérations communes et spécifiques

Pièges

m[cle] insère la clé avec une valeur par défaut si elle n'existe pas : pour tester la présence, utilisez find ou count. Et operator[] n'existe pas sur une map constante.
Les clés d'un set ou d'une map sont constantes : on ne modifie pas une clé en place (on supprime et on réinsère). Le type de clé doit avoir operator< (ou on fournit un comparateur, module 9).
list n'a ni [] ni at : on avance avec un itérateur. sort de <algorithm> ne marche pas sur une liste (itérateurs non aléatoires) : utiliser l.sort().
pop_back, pop_front, pop ne retournent pas l'élément : lire back() / front() / top() avant.

2. Les itérateurs

Un itérateur est un objet qui désigne un élément d'un conteneur et sait passer au suivant : un pointeur généralisé. Chaque conteneur fournit begin() (premier élément) et end() (position après le dernier : ne jamais le déréférencer). Les opérations : *it (l'élément), it->membre, ++it, et la comparaison it != fin.

Catégorie	Conteneurs	Opérations
Accès aléatoire	vector, deque, array, string	`++ -- + n - n it[n] < >` ; `sort` exige cette catégorie
Bidirectionnel	list, set, map, multiset, multimap	`++ --` seulement : pas de `it + 2`, utiliser `std::advance(it, 2)` ou `std::next(it, 2)`
Avant (forward)	forward_list, unordered_*	`++` seulement

Fonctions utilitaires (<iterator>) : std::distance(a, b) (nombre d'éléments entre deux itérateurs), std::advance(it, n), std::next(it, n), std::prev(it).

Insérer et supprimer avec des itérateurs

Invalidation d'itérateurs

vector : push_back et insert peuvent réallouer : tous les itérateurs, pointeurs et références deviennent invalides. erase invalide ceux qui suivent la position.
list, set, map : seuls les itérateurs vers l'élément supprimé sont invalidés ; les insertions n'invalident rien.
Supprimer en parcourant : toujours it = c.erase(it); dans la branche de suppression, et ++it seulement dans l'autre branche.

3. Choisir le bon conteneur

Besoin	Conteneur
Accès par indice, ajout en fin, parcours rapide (le choix par défaut)	`vector`
Ajouts et retraits fréquents aux deux extrémités	`deque`
Insertions et suppressions fréquentes au milieu, itérateurs stables, pas d'accès par indice	`list`
Éléments uniques, parcours trié, test d'appartenance rapide	`set`
Association clé → valeur, parcours trié par clé (dictionnaire, comptage)	`map`
Plusieurs valeurs par clé	`multimap`
Association sans besoin d'ordre, vitesse maximale	`unordered_map`
Dernier entré, premier sorti / premier entré, premier sorti / le plus prioritaire d'abord	`stack` / `queue` / `priority_queue`

Complexités à retenir : vector [] O(1), push_back O(1) amorti, insert au milieu O(n) ; list insert/erase O(1) à une position connue, mais trouver la position O(n) ; set/map O(log n) par opération ; unordered O(1) en moyenne.

Exemple du simulateur de hockey : afficher une équipe par numéro de chandail

L'exercice « Conteneurs » demande d'afficher les membres d'une équipe triés par numéro, à partir d'une liste de tous les membres : on copie la liste, on retire l'équipe adverse, on recopie dans un conteneur trié. Un set avec un comparateur (foncteur, module 9) trie automatiquement.

4. À retenir

vector par défaut ; list pour insérer/supprimer au milieu sans accès par indice ; set/map pour l'unicité, le tri et la recherche rapide ; unordered_map pour la vitesse sans ordre ; stack/queue/priority_queue comme adaptateurs.
Itérateur : begin(), end() (après le dernier), *it, it->, ++it, !=. const_iterator pour lire, reverse_iterator pour l'envers. Seuls vector et deque supportent it + n.
m[k] crée ; find/count testent ; it->first clé constante, it->second valeur.
Supprimer en parcourant : it = c.erase(it). vector : réallocation = invalidation totale.

Quiz rapide - Module 8

Que désigne v.end() ?

Le dernier élément
Le premier élément
La position après le dernier élément ; on ne le déréférence jamais
La taille du vecteur

L'intervalle d'un conteneur est [begin, end[ : end sert de sentinelle de fin de boucle.

Pourquoi écrire it != v.end() plutôt que it < v.end() ?

C'est plus rapide
< n'existe que pour les itérateurs à accès aléatoire (vector, deque) ; != fonctionne pour tous les conteneurs
< ne compile jamais sur des itérateurs
Par convention seulement

Un code écrit avec != reste correct si on remplace le vector par une list.

Que fait m["x"] sur une map<string, int> m qui ne contient pas « x » ?

Lance out_of_range
Retourne 0 sans rien insérer
Retourne m.end()
Insère la clé « x » avec la valeur 0 et retourne une référence vers cette valeur

D'où l'intérêt de m["x"]++ pour compter, et le danger de tester la présence avec [].

Quel conteneur pour insérer et supprimer souvent au milieu, sans jamais accéder par indice ?

list
vector
map
stack

Insertion et suppression en O(1) à une position connue par itérateur, sans déplacer les autres éléments.

Quel est le contenu de s après set<int> s; s.insert(3); s.insert(1); s.insert(3); s.insert(2); et dans quel ordre est-il parcouru ?

{3, 1, 3, 2} dans l'ordre d'insertion
{3, 1, 2} dans l'ordre d'insertion
{1, 2, 3} en ordre croissant
{3, 2, 1} en ordre décroissant

Unique et trié par operator< ; size() vaut 3.

Comment supprimer correctement l'élément désigné par it au cours d'un parcours de vector ?

v.erase(it); ++it;
it = v.erase(it); sans incrémenter
v.erase(it); --it;
delete it;

erase invalide it et retourne l'itérateur sur l'élément suivant.

Après auto it = v.begin(); v.push_back(5); sur un vector :

it désigne toujours le premier élément
it désigne 5
it vaut end()
it peut être invalide si push_back a réalloué

Toute insertion dans un vector peut déplacer tous les éléments en mémoire.

Comment accéder à la clé et à la valeur via un itérateur de map ?

it->first et it->second
it.key() et it.value()
*it et it[1]
it->cle et it->valeur

Un élément de map est une pair<const K, V>.

Pourquoi sort(l.begin(), l.end()) ne compile-t-il pas pour une list ?

Les listes sont toujours triées
sort n'existe pas dans la STL
sort exige des itérateurs à accès aléatoire ; list n'offre que des bidirectionnels : utiliser l.sort()
Les listes ne sont pas copiables

La liste fournit ses propres sort, remove, unique, merge, splice.

Que retourne st.pop() sur une stack<int> ?

L'élément retiré
Rien (void) : il faut lire top() avant
Un itérateur
true si la pile n'est pas vide

Même convention pour pop_back, pop_front et queue::pop.

Quelle est la complexité de la recherche d'une clé dans une map de n éléments ?

O(1)
O(n)
O(n log n)
O(log n)

Arbre binaire équilibré. unordered_map : O(1) en moyenne.

Que fait std::advance(it, 3) ?

Avance l'itérateur de 3 positions, même pour une list
Retourne le troisième élément
Insère 3 éléments
Ne compile que pour vector

it + 3 ne compile que pour les itérateurs à accès aléatoire ; advance s'adapte (3 incrémentations pour une list).

Peut-on modifier la clé d'un élément de set via son itérateur ?

Oui, avec *it = nouvelleValeur
Oui, avec it->first = ...
Non : les éléments d'un set sont constants ; il faut supprimer puis réinsérer
Oui, si le set est non const

Modifier une clé casserait l'ordre de l'arbre.

Quel type d'itérateur utiliser dans une méthode const pour parcourir un attribut vector<Moteur> moteurs_ ?

vector<Moteur>::iterator
vector<Moteur>::const_iterator (ou auto it = moteurs_.cbegin())
Moteur*
reverse_iterator

Dans une méthode const, begin() retourne déjà un const_iterator ; un iterator ne compile pas.

Exercices à développement

map

Compter les mots

Écrivez map<string, int> compterMots(const vector<string>& mots), puis une fonction qui affiche les mots apparaissant au moins deux fois, par ordre alphabétique, et enfin une fonction qui retourne le mot le plus fréquent (le premier dans l'ordre alphabétique en cas d'égalité).

Solution

listItérateurs

Insertion triée dans une liste

Écrivez void insererTrie(list<int>& l, int val) qui insère val dans une liste triée en gardant le tri, avec un itérateur (pas d'indice). Puis void retirerPairs(list<int>& l) de deux façons : avec une boucle et erase, puis avec remove_if de la liste.

Solution

Simulateur de hockeyset, multimap

Les trois étoiles

Match possède list<Joueur*> joueurs_. Écrivez void Match::afficherTroisEtoiles() const qui affiche les trois joueurs ayant marqué le plus de buts (toutes équipes confondues), en copiant les joueurs dans un conteneur approprié. Proposez une version avec multimap et une avec vector + tri (module 9).

Solution

Un set ne conviendrait pas : deux joueurs avec le même nombre de buts seraient considérés comme un doublon par un comparateur sur les buts.

Conception

Quel conteneur ?

Pour chaque situation, choisissez le conteneur et justifiez : (1) l'historique des commandes d'un éditeur avec « annuler » ; (2) les clients qui attendent au comptoir ; (3) le répertoire téléphonique nom → numéro ; (4) les numéros de chandail déjà attribués (vérifier rapidement qu'un numéro est libre) ; (5) les tâches à exécuter par priorité ; (6) les notes d'un étudiant par cours, un cours pouvant avoir plusieurs notes ; (7) une file d'attente où l'on retire aussi par l'avant et par l'arrière.

Solution

stack : dernier entré, premier annulé.
queue : premier arrivé, premier servi.
map<string, string> (ou unordered_map si l'ordre alphabétique est inutile).
set<int> (ou unordered_set) : unicité et count en O(log n) ou O(1).
priority_queue : top() donne la plus prioritaire.
multimap<string, double>, ou map<string, vector<double>>.
deque : pop_front et pop_back en O(1).

AffichageItérateurs