Bibliothèque standard C++ : conteneurs STL, algorithmes et itérateurs
Fiche de révision · Numérique et sciences informatiques · Term
L'essentiel du cours
Chapitre 1 : Les conteneurs STL
std::vector est le tableau dynamique par défaut.
Chapitre 2 : Les itérateurs
Un itérateur généralise la notion de pointeur pour parcourir un conteneur.
Chapitre 3 : Les algorithmes STL
Les algorithmes STL évitent d'écrire des boucles manuelles.
Chapitre 4 : Combiner les trois
Conteneur + itérateurs + algorithmes = code générique et efficace.
Teste-toi · 8 questions
1.Quel conteneur STL correspond à un tableau dynamique contigu en mémoire offrant un accès direct par indice ?
Voir la réponseMasquer la réponse
Réponse : 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 la réponse
Réponse : 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 la réponse
Réponse : <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 la réponse
Réponse : 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 la réponse
Réponse : 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 la réponse
Réponse : 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 :
- A.Séquentiel
- B.Tableau dynamique
- C.Associatif trié par clé
- D.Adaptateur de pile
Voir la réponseMasquer la réponse
Réponse C : 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 la réponse
Réponse : Calcule la somme des éléments
std::accumulate additionne les éléments de l'intervalle à la valeur initiale 0, renvoyant la somme totale.