6 std::vector et les conteneurs modernes 6.2.1 Créer un vector avec une taille initiale . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Une taille gérée automatiquement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Pourquoi la capacité est-elle supérieure à la taille ? . . . . . . . . . . . . . . . . . . . . . . . 6.13 vector et mémoire contiguë . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.14 Attention aux pointeurs et références après réallocation . . . . . . . . . . . . . . . . . . . . . 6.15 vector ou tableau dynamique manuel ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2026 – C++ Partie III std::vector et les conteneurs modernes

Accueil

std::vector et les conteneurs modernes Pourquoi des conteneurs ? Dans les premiers chapitres de la partie III du cours, nous avons appris à créer des tableaux dynamiques avec l’instruction double∗ p = new double[n]; puis à libérer la mémoire avec Cette approche permet de comprendre précisément le fonctionnement de l’allocation dynamique, ce qui est fondamental pour bien comprendre ce chapitre et les précédents sur les pointeurs intelligents. L’ennui c’est que cette méthode impose au programmeur de gérer lui-même les éléments suivants : • l’allocation de la mémoire ; • la libération de cette mémoire ; • la taille du tableau ; • les éventuels changements de taille ; • les déplacements. Depuis C++11, le C++ est dit « moderne » et fournit des classes spécialement conçues pour gérer des collections d’objets, ces objets sont appelés des conteneurs. Parmi eux, le plus important est le conteneur : Un vector représente une séquence dynamique d’objets stockés de manière contiguë en mémoire. Le std:: est un namespace de la standard library 1 Notre premier vector Pour pouvoir utiliser std::vector, il faut d’abord inclure : 1. std est l’abréviation de standard et désigne l’espace de noms (namespace) de la bibliothèque standard C++. STL signifie Standard Template Library. Historiquement, la STL est une bibliothèque générique fondée sur les templates, notamment à l’origine des conteneurs, des itérateurs et des algorithmes intégrés à la bibliothèque standard C++. Les termes STL et bibliothèque standard C++ ne sont donc pas strictement synonymes. 2026 – C++ Partie III std::vector et les conteneurs modernes au début du programme ou du fichier concerné. Un vector peut être créé sans devoir préciser sa taille : std::vector<double> valeurs; Cette instruction crée un objet de type : qui ne contient initialement aucun élément. Nous pouvons ensuite lui ajouter des éléments : valeurs.push_back(3.14); 2 valeurs.push_back(2.71); 3 valeurs.push_back(1.41); Le vector contient maintenant trois éléments et sa taille vaut : Il n’est donc pas nécessaire de connaître à l’avance le nombre d’éléments que contiendra finalement un vector car sa taille peut évoluer pendant l’exécution du programme. Créer un vector avec une taille initiale Si le nombre initial d’éléments est connu, il est également possible de le préciser lors de la construction std::vector<double> valeurs(1000); Cette instruction ne fixe cependant pas une taille maximale, elle crée immédiatement un vector contenant 1000 éléments. Le vector pourra ensuite continuer à grandir ou, au contraire, voir sa taille diminuer. valeurs.push_back(3.14); porte sa taille à 1001 éléments. Une taille gérée automatiquement Avec une allocation dynamique manuelle double∗ p = new double[1000]; la taille choisie lors de cette allocation ne peut pas être simplement augmentée. Pour obtenir une zone plus grande, il faudrait notamment allouer une nouvelle zone de mémoire, transférer les données et libérer l’ancienne zone, de plus, la libération de la mémoire reste sous la responsabilité du programmeur : Avec un vector, ces opérations de gestion de la mémoire sont prises en charge automatiquement et vector applique le principe RAII : lorsque l’objet valeurs est détruit, les ressources qu’il possède sont automatiquement libérées.

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes Accéder aux éléments Comme avec un tableau classique, nous pouvons utiliser l’opérateur [] : std::cout << valeurs[0] << ’\n’; Le premier élément possède l’indice 0 et le dernier élément possède l’indice valeur.size()−1. La taille d’un vector Un avantage fondamental de vector est qu’il connaît sa propre taille, nous pouvons donc écrire : std::cout << valeurs.size() << ’\n’; retourne le nombre d’éléments actuellement contenus dans le vector. Avec un pointeur brut : cette information n’existe pas dans le pointeur lui-même, c’est le programmeur qui doit généralement conserver la taille dans une autre variable mais avec vector, la taille fait partie de l’objet. Un vector possède deux notions différentes qui sont : La taille correspond au nombre d’éléments réellement présents, elle est donnée par : La capacité correspond au nombre d’éléments que le vector peut actuellement contenir dans la mémoire déjà réservée sans devoir effectuer une nouvelle allocation. Cette capacité est fournie par la fonction std::cout << v.size() << ’\n’; std::cout << v.capacity() << ’\n’; Puis ajoutons progressivement des éléments

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes for (int i = 0; i < 20; ++i) std::cout << « taille =  » La taille augmente d’une unité à chaque ajout mais la capacité, en revanche, n’augmente pas nécessairement d’une unité à chaque fois. Le vector réserve généralement de la mémoire supplémentaire afin d’éviter une allocation à chaque nouvel élément. Pourquoi la capacité est-elle supérieure à la taille ? Imaginons qu’un vector possède exactement autant de mémoire que nécessaire. Après : il faudrait réserver de la mémoire pour un élément et après : il faudrait réserver une nouvelle zone capable de contenir deux éléments et ainsi de suite. Une telle stratégie provoquerait un très grand nombre d’allocations et de copies ou déplacements. Pour éviter cela, vector réserve généralement davantage d’espace que nécessaire et la situation peut être représentée ainsi : éléments utilisés Les valeurs exactes de croissance de la capacité ne sont pas imposées par le langage et peuvent dépendre de l’implémentation. Lorsque la taille atteint la capacité disponible et qu’un nouvel élément doit être ajouté, le vector doit généralement obtenir une nouvelle zone de mémoire plus grande et ce mécanisme peut être résumé ainsi : ancienne zone de mémoire allocation d’une nouvelle zone plus grande copie ou déplacement des éléments libération de l’ancienne zone

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes Cette opération est appelée une réallocation et nous retrouvons ici directement la sémantique de déplacement étudiée dans le chapitre précédent. Si les éléments du vector peuvent être déplacés efficacement, leur transfert vers la nouvelle zone de mémoire peut être beaucoup moins coûteux qu’une copie complète. Observer l’adresse Nous pouvons observer les réallocations avec la fonction : qui retourne l’adresse du premier élément de la zone de stockage contiguë, par exemple 4 int main(int argc, const char ∗ argv[]) { for (int i = 0; i < 2000000000; ++i) if (i % 500000000 == 0) std::cout << « taille =  » << static_cast<const void∗>(v.data()) return EXIT_SUCCESS; taille = 1 capacite = 1 adresse = 0x1007c1c10 taille = 500000001 capacite = 536870912 adresse = 0x765c00000 3 taille = 1000000001 capacite = 1073741824 adresse = 0xe5c000000 4 taille = 1500000001 capacite = 2147483648 adresse = 0x7000000000 5 Program ended with exit code: 0 Lorsque l’adresse retournée par data() change, une nouvelle zone de mémoire a été utilisée. Cette expérience permet de voir concrètement que le vector gère dynamiquement son stockage. Lorsqu’on connaît approximativement le nombre d’éléments qu’un vector devra contenir, il est possible de réserver à l’avance une certaine capacité, par exemple

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes Cette instruction demande au vector de disposer d’une capacité suffisante pour au moins 1000 éléments ne crée pas 1000 éléments. Après cette instruction : peut toujours valoir : est au moins égal à : • reserve() modifie la capacité, pas la taille. • Il permet de limiter le nombre de réallocations lorsqu’on connaît à l’avance l’ordre de grandeur du nombre d’éléments à stocker. modifie au contraire le nombre d’éléments réellement contenus dans le vector. Après cette instruction : Les éléments nécessaires ont effectivement été créés. Il faut donc distinguer soigneusement : réserve de la mémoire pour au moins n éléments, fixe le nombre d’éléments à n.

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes Initialiser un vector Plusieurs formes d’initialisation sont possibles. Nous pouvons créer cinq entiers initialisés à zéro : std::vector<int> v(5); ou encore créer cinq entiers contenant tous la valeur 7 : std::vector<int> v(5, 7); Nous pouvons également créer directement une liste de valeurs : std::vector<int> v{10, 20, 30, 40}; Attention à la différence entre std::vector<int> v(5); std::vector<int> v{5}; La première crée cinq éléments, la seconde crée un seul élément contenant la valeur 5. Cette différence provient du mécanisme d’initialisation par liste. Nous pouvons naturellement utiliser un indice : for (std::size_t i = 0; i < v.size(); ++i) std::cout << v[i] << ’\n’; Mais le C++ moderne permet également une boucle basée directement sur les éléments : for (int valeur : v) std::cout << valeur << ’\n’; Cette construction est appelée range-based for et si nous voulons modifier directement les éléments du vector, nous pouvons utiliser une référence : for (int& valeur : v) Pour parcourir sans copie et sans modification : for (const int& valeur : v) std::cout << valeur << ’\n’; Cette dernière écriture devient particulièrement intéressante lorsque les éléments sont des objets de taille

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes Accès avec [] ou at() pour parcourir vector, cet accès ne vérifie pas que l’indice est valide et si l’indice est hors limites, le comportement du programme est indéfini. vector fournit également la méthode qui effectue une vérification sur l’indice, si l’indice est invalide, une exception de type : vérification supplémentaire Supprimer des éléments Le dernier élément peut être supprimé avec : La taille diminue alors d’une unité et pour supprimer tous les éléments on peut faire la taille vaut zéro, la capacité n’est cependant pas nécessairement réduite, le vector peut conserver sa zone de mémoire afin de pouvoir être rempli à nouveau efficacement. vector et mémoire contiguë Un vector stocke ses éléments de manière contiguë, donc pour : std::vector<int> v{10, 20, 30}; les éléments sont disposés conceptuellement comme : dans une même zone de mémoire. Cette propriété permet notamment : int∗ p = v.data();

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes std::cout << p[0] << ’\n’; std::cout << p[1] << ’\n’; La fonction data() est particulièrement utile lorsqu’une API ancienne attend un pointeur vers un tableau Attention aux pointeurs et références après réallocation La réallocation possède une conséquence très importante, considérons : Si une réallocation intervient, les éléments sont transférés vers une nouvelle zone de mémoire, donc l’ancien peut alors désigner une zone qui n’est plus valide. Le même problème peut concerner les références et les itérateurs vers les éléments. Il faut donc bien retenir : Une opération qui provoque une réallocation peut invalider les pointeurs, références et itérateurs désignant les éléments du vector. vector ou tableau dynamique manuel ? Établissons la comparaison double∗ p = new double[n]; std::vector<double> v(n); Le vector fournit notamment : • la gestion automatique de la mémoire ; • la connaissance de sa taille ; • le redimensionnement ; • l’ajout et la suppression d’éléments ;

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes • la copie correcte ; • le déplacement ; • une interface compatible avec les algorithmes de la bibliothèque standard. Dans la majorité des programmes modernes, un tableau dynamique manuel ne constitue donc plus le choix • Pour représenter une séquence dynamique d’objets, std::vector doit généralement être préféré à une allocation manuelle avec new[]. • L’étude de new[] reste cependant indispensable pour comprendre ce que le conteneur gère Les autres conteneurs std::vector n’est qu’un des conteneurs fournis par la bibliothèque standard. Parmi les autres conteneurs importants, nous rencontrerons notamment : • std::array : tableau de taille fixe ; • std::deque : séquence permettant notamment des insertions efficaces aux deux extrémités ; • std::list : liste doublement chaînée ; • std::set : ensemble de valeurs uniques ; • std::map : association entre clés et valeurs ; • std::unordered_map : association basée sur une table de hachage. Tous ces conteneurs répondent à des besoins différents, il n’est donc pas utile de les considérer comme des variantes interchangeables et le choix dépend essentiellement des opérations que le programme devra std::vector est un conteneur dynamique stockant ses éléments de manière contiguë qui applique le principe RAII et gère automatiquement sa mémoire. Sa taille est donnée par : et sa capacité par : Les deux notions sont différentes, on a également les méthodes 1. push_back() ajoute un élément. 2. reserve() réserve de la capacité sans modifier la taille. 3. resize() modifie le nombre d’éléments. Lorsque la capacité devient insuffisante, une réallocation peut être nécessaire et cette réallocation peut déplacer les éléments vers une nouvelle zone de mémoire et invalider les pointeurs « manuels », références et itérateurs qui les désignaient.

Accueil

2026 – C++ Partie III std::vector et les conteneurs modernes Dans la majorité des cas où une séquence dynamique est nécessaire, std::vector doit être préféré à une gestion manuelle avec new[] et delete[].

Accueil

P4-Chap-06 std::vector et les conteneurs modernes

Accueil

Termes à ajouter au glossaire