Bibliothèque standard C++ : conteneurs STL, algorithmes et itérateurs
Ce que tu dois retenir
std::vector est le tableau dynamique par défaut.
Un itérateur généralise la notion de pointeur pour parcourir un conteneur.
Les algorithmes STL évitent d'écrire des boucles manuelles.
Conteneur + itérateurs + algorithmes = code générique et efficace.
Teste-toi
◆ Teste-toi
1. Quel conteneur STL correspond à un tableau dynamique contigu en mémoire offrant un accès direct par indice ?
Voir la réponseMasquer
Réponse : A — A. std::vector
std::vector stocke ses éléments dans un tableau contigu, ce qui permet un accès en O(1) par indice, contrairement à std::list (liste chaînée) ou std::map (associatif).
2. Que renvoie v.end() pour un conteneur v ?
Voir la réponseMasquer
Réponse : B — B. Un itérateur après le dernier élément
end() renvoie un itérateur de fin, situé après le dernier élément valide, ce qui délimite l'intervalle semi-ouvert [begin, end[.
3. Quel en-tête faut-il inclure pour utiliser std::sort ?
Voir la réponseMasquer
Réponse : A — A. <algorithm>
Les algorithmes génériques comme sort, find, count sont déclarés dans <algorithm> ; <numeric> contient accumulate, etc.
4. Quelle est la complexité moyenne de std::sort sur n éléments ?
Voir la réponseMasquer
Réponse : B — B. O(n log n)
std::sort utilise un tri introsort, de complexité moyenne O(n log n).
5. Quel algorithme STL permet de trouver la première occurrence d'une valeur dans un intervalle ?
Voir la réponseMasquer
Réponse : A — A. std::find
std::find renvoie un itérateur sur le premier élément égal à la valeur cherchée, ou end() si absent.
6. Quel type d'itérateur permet un accès aléatoire direct avec it + n ?
Voir la réponseMasquer
Réponse : D — D. Itérateur à accès aléatoire
Seuls les itérateurs à accès aléatoire supportent l'addition d'un entier pour sauter directement à une position, comme ceux de vector ou array.
7. std::map est un conteneur :
Voir la réponseMasquer
Réponse : B — B. Associatif trié par clé
std::map associe des clés à des valeurs et maintient les clés triées, typiquement dans un arbre binaire de recherche.
8. Que fait std::accumulate(v.begin(), v.end(), 0) avec un vecteur d'entiers v ?
Voir la réponseMasquer
Réponse : B — B. Calcule la somme des éléments
std::accumulate additionne les éléments de l'intervalle à la valeur initiale 0, renvoyant la somme totale.