Maîtriser le conteneur std::vector en C++

Le std::vector est un conteneur de tableau dynamique fourni par la Standard Template Library (STL) en C++. Il permet de stocker une séquence d'éléments d'un type donné, et sa taille peut être ajustée dynamiquement.

Principe de fonctionnement

Un std::vector gère un bloc de mémoire contigu sur le tas pour stocker ses éléments. Il maintient trois informations essentielles :

size : Le nombre actuel d'éléments contenus dans le vecteur.
capacity : La quantité totale de mémoire allouée, mesurée en nombre d'éléments que le vecteur peut contenir sans avoir besoin de réallouer.
buffer : Un pointeur vers le début du bloc de mémoire alloué.

Lorsque le size atteint la capacity et qu'un nouvel élément est ajouté, le vecteur doit s'agrandir. Ce processus, appelé réallocation, implique généralement les étapes suivantes :

Allocation d'un nouveau bloc de mémoire plus grand (souvent le double de la capacité précédente).
Copie de tous les éléments existants dans le nouveau bloc.
Libération de l'ancien bloc de mémoire.
Mise à jour des pointeurs et des compteurs internes (size, capacity, buffer).

Opérations et interfaces courantes

Définition, initialisation et affectation

#include <vector>
#include <iostream>

int main() {
    // 1. Constructeur par défaut : crée un vecteur vide.
    std::vector<int> vec1;

    // 2. Crée un vecteur de n éléments initialisés à leur valeur par défaut.
    std::vector<int> vec2(5); // 5 éléments, initialisés à 0.

    // 3. Crée un vecteur de n éléments, chacun initialisé à une valeur spécifique.
    std::vector<int> vec3(5, 10); // 5 éléments, tous valant 10.

    // 4. Initialisation par liste d'initialisation.
    std::vector<int> vec4 = {1, 2, 3, 4, 5};

    // 5. Initialisation à partir d'un autre vecteur.
    std::vector<int> vec5(vec4);

    return 0;
}

Accès aux éléments

Opérateur `[]`

Accède à un élément par son indice, sans vérification des limites. Une utilisation incorrecte peut entraîner un comportement indéfini.

int element = vec[2];       // Accède à l'élément d'indice 2.
vec[5] = 6;                 // Modifie l'élément d'indice 5.

Méthode `at()`

Accède à un élément par son indice, avec une vérification des limites. Si l'indice est hors limites, une exception std::out_of_range est levée.

int element = vec.at(2);    // Accède à l'élément d'indice 2.
vec.at(5) = 6;              // Modifie l'élément d'indice 5.

#include <vector>
#include <iostream>
#include <stdexcept>

int main() {
    std::vector<int> vec = {1, 2, 4, 5, 5, 6};
    try {
        vec.at(13) = 13; // Tentative d'accès hors limites
    } catch (const std::out_of_range& ex) {
        std::cout << ex.what() << '\n'; // Affiche le message d'erreur
    }
    return 0;
}

Méthode `front()`

Retourne une référence au premier élément du vecteur. Ne doit pas être appelée sur un vecteur vide.

int first_element = vec.front();
vec.front() = 6; // Modifie le premier élément.

Méthode `back()`

Retourne une référence au dernier élément du vecteur. Ne doit pas être appelée sur un vecteur vide.

int last_element = vec.back();
vec.back() = 6; // Modifie le dernier élément.

Méthode `data()`

Retourne un pointeur vers le premier élément du tableau sous-jacent. Cela permet d'accéder aux données de manière contiguë, comme avec un tableau C.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Affiche les adresses des deux premiers éléments et du buffer
    std::cout << &vec[0] << std::endl;
    std::cout << &vec[1] << std::endl;
    std::cout << vec.data() << std::endl; // Devrait être identique à &vec[0]

    // Modifie le premier élément via data()
    *vec.data() = 6;
    std::cout << vec[0] << std::endl; // Affiche 6

    return 0;
}

Itérateurs

Itérateurs directs

begin() : Retourne un itérateur pointant sur le premier élément.
end() : Retourne un itérateur pointant sur la position *après* le dernier élément.
cbegin() : Retourne un itérateur constant pointant sur le premier élément.
cend() : Retourne un itérateur constant pointant sur la position *après* le dernier élément.

Les itérateurs constants ne permettent que la lecture des éléments, garantissant que le contenu du conteneur n'est pas modifié.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec(5);

    // Utilisation d'un itérateur direct pour assigner des valeurs
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        *it = 3;
    }

    // Parcours et affichage avec un itérateur direct
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // Parcours avec un itérateur constant
    std::vector<int> const_vec = {1, 2, 3, 4, 5};
    for (auto it = const_vec.cbegin(); it != const_vec.cend(); ++it) {
        std::cout << *it << " ";
        // *it = 10; // Ceci provoquerait une erreur de compilation
    }
    std::cout << std::endl;

    return 0;
}

Itérateurs inversés

rbegin() : Retourne un itérateur inversé pointant sur le dernier élément.
rend() : Retourne un itérateur inversé pointant sur la position *avant* le premier élément.
crbegin() : Retourne un itérateur constant inversé pointant sur le dernier élément.
crend() : Retourne un itérateur constant inversé pointant sur la position *avant* le premier élément.

#include <vector>
#include <iostream>

int main() {
	std::vector<int> v = {1, 2, 3, 4, 5};

	// Parcours inversé avec itérateur inversé
	std::cout << "Parcours inversé : ";
	for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
		std::cout << *rit << " ";
	}
	std::cout << std::endl;

    // Parcours inversé avec itérateur constant inversé
	std::cout << "Parcours inversé constant : ";
	for (auto rit = v.crbegin(); rit != v.crend(); ++rit) {
		std::cout << *rit << " ";
        // *rit = 10; // Erreur de compilation
	}
	std::cout << std::endl;

	return 0;
}

Boucle `for` basée sur la plage (Range-based for loop)

Permet de parcourir les éléments d'un conteneur de manière concise. L'utilisation d'une référence (&) est nécessaire pour modifier les éléments.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Lecture seule
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Modification des éléments
    for (int& num : vec) {
        num *= 2;
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Affichage après modification
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Capacité

`empty()`

Retourne true si le vecteur ne contient aucun élément (size == 0), false sinon.

bool est_vide = vec.empty();

`size()`

Retourne le nombre actuel d'éléments dans le vecteur.

size_t nombre_elements = vec.size();

`max_size()`

Retourne la quantité maximale d'éléments que le vecteur peut théoriquement contenir, limitée par la mémoire disponible et les spécifications de l'implémentation.

size_t max_elements = vec.max_size();

`capacity()`

Retourne le nombre d'éléments que le vecteur peut contenir avant de devoir réallouer de la mémoire.

size_t capacite = vec.capacity();

`resize()`

Redimensionne le vecteur. Si la nouvelle taille est plus grande, les nouveaux éléments sont ajoutés (initialisés par défaut ou avec une valeur spécifiée). Si elle est plus petite, les éléments à partir de la fin sont supprimés.

void resize(size_type count); : Ajoute ou supprime des éléments jusqu'à atteindre count. Les nouveaux éléments sont initialisés par défaut.
void resize(size_type count, const value_type& val); : Comme ci-dessus, mais les nouveaux éléments sont initialisés avec val.

#include <vector>
#include <iostream>

void print_vector(const std::vector<int>& v) {
    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec = {1, 2, 3};

    // Augmentation de la taille, nouveaux éléments initialisés à 0
    vec.resize(5);
    std::cout << "Après resize(5): "; print_vector(vec); // 1 2 3 0 0

    // Augmentation de la taille, nouveaux éléments initialisés à 10
    vec.resize(7, 10);
    std::cout << "Après resize(7, 10): "; print_vector(vec); // 1 2 3 0 0 10 10

    // Réduction de la taille
    vec.resize(2);
    std::cout << "Après resize(2): "; print_vector(vec); // 1 2

    return 0;
}

`reserve()`

Alloue de la mémoire pour que le vecteur puisse contenir au moins n éléments sans réallocation. Si n est inférieur à la capacité actuelle, l'appel n'a aucun effet.

vec.reserve(30); // Assure une capacité d'au moins 30 éléments.

`shrink_to_fit()`

Demande la réduction de la capacité du vecteur pour qu'elle corresponde à sa taille actuelle. Cette opération n'est pas garantie si le vecteur est plein.

vec.shrink_to_fit(); // Libère la mémoire non utilisée.

Exemples de gestion de capacité

Relation entre `size`, `capacity` et `empty`

#include <vector>
#include <iostream>
#include <iomanip>

void print_vector_status(const std::vector<int>& v) {
    std::cout << "Size: " << v.size()
              << ", Capacity: " << v.capacity()
              << ", Is Empty: " << (v.empty() ? "Yes" : "No") << std::endl;
}

int main() {
    std::cout << "Création d'un vecteur vide.\n";
    std::vector<int> v;
    print_vector_status(v);

    std::cout << "\nRéservation de capacité pour 30 éléments.\n";
    v.reserve(30);
    print_vector_status(v);

    std::cout << "\nRedimensionnement à 10 éléments.\n";
    v.resize(10);
    print_vector_status(v); // capacity peut être >= 30

    std::cout << "\nRedimensionnement à 50 éléments.\n";
    v.resize(50);
    print_vector_status(v); // capacity sera probablement > 50

    std::cout << "\nRéduction à 20 éléments.\n";
    v.resize(20);
    print_vector_status(v); // capacity reste inchangée

    std::cout << "\nLibération de la mémoire inutilisée.\n";
    v.shrink_to_fit();
    print_vector_status(v); // capacity devrait maintenant être égale à size

    std::cout << "\nNettoyage du vecteur.\n";
    v.clear();
    print_vector_status(v); // size = 0, capacity reste inchangée

    return 0;
}

Stratégie d'augmentation de capacité

Lors de l'ajout d'éléments et de la nécessité de réallouer, la capacité augmente généralement par un facteur multiplicatif (souvent 1.5 ou 2) pour optimiser les opérations d'ajout fréquentes.

#include <iomanip>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    auto previous_capacity = v.capacity();

    std::cout << "Démonstration de la stratégie d'augmentation de capacité :\n";
    std::cout << std::left << std::setw(10) << "Size"
              << std::setw(15) << "Capacity"
              << "Ratio\n";

    for (int i = 0; i < 100; ++i) {
        v.push_back(i);
        if (v.capacity() != previous_capacity) {
            float ratio = static_cast<float>(v.capacity()) / previous_capacity;
            std::cout << std::left << std::setw(10) << v.size()
                      << std::setw(15) << v.capacity()
                      << ratio << '\n';
            previous_capacity = v.capacity();
        }
    }

    std::cout << "\nTaille finale: " << v.size() << ", Capacité finale: " << v.capacity() << '\n';

    return 0;
}

Modificateurs

`clear()`

Supprime tous les éléments du vecteur. La taille devient 0, mais la capacité peut rester inchangée.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::cout << "Avant clear - Empty: " << (vec.empty() ? "Yes" : "No") << std::endl;

    vec.clear();

    std::cout << "Après clear - Empty: " << (vec.empty() ? "Yes" : "No") << std::endl;
    std::cout << "Capacité après clear: " << vec.capacity() << std::endl; // La capacité peut être conservée

    return 0;
}

`insert()`

Insère des éléments à une position spécifiée.

iterator insert(const_iterator pos, const T& value); : Insère une seule valeur.
iterator insert(const_iterator pos, size_type count, const T& value); : Insère count copies de value.
template< class InputIt > iterator insert(const_iterator pos, InputIt first, InputIt last); : Insère une plage d'éléments.
iterator insert(const_iterator pos, std::initializer_list<T> ilist); : Insère des éléments à partir d'une liste d'initialisation.

#include <vector>
#include <iostream>

void print_vector(const std::vector<int>& v) {
    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    std::cout << "Initial: "; print_vector(vec);

    // 1. Insérer un seul élément
    auto it1 = vec.insert(vec.begin() + 2, 10);
    std::cout << "Après insert(pos, 10): "; print_vector(vec); // 1 2 10 3 4

    // 2. Insérer plusieurs éléments identiques
    vec.insert(vec.end(), 3, 20);
    std::cout << "Après insert(end, 3, 20): "; print_vector(vec); // 1 2 10 3 4 20 20 20

    // 3. Insérer une plage d'éléments
    std::vector<int> anotherVec = {30, 40};
    vec.insert(vec.begin(), anotherVec.begin(), anotherVec.end());
    std::cout << "Après insert(begin, range): "; print_vector(vec); // 30 40 1 2 10 3 4 20 20 20

    // 4. Insérer une liste d'initialisation
    vec.insert(vec.end(), {50, 60});
    std::cout << "Après insert(end, {50, 60}): "; print_vector(vec); // 30 40 1 2 10 3 4 20 20 20 50 60

    return 0;
}

`emplace()`

Construit un élément directement à l'emplacement spécifié, en utilisant les arguments fournis pour le constructeur de l'élément. C'est plus efficace que insert car cela évite la création d'un objet temporaire.

(Exemple non fourni car conceptuel, nécessite une définition de classe plus complexe)

`emplace_back()`

Construit un élément directement à la fin du vecteur, en utilisant les arguments fournis pour le constructeur de l'élément. Plus efficace que push_back.

(Exemple non fourni car conceptuel)

`erase()`

Supprime un ou plusieurs éléments.

iterator erase(const_iterator pos); : Supprime l'élément à la position pos.
iterator erase(const_iterator first, const_iterator last); : Supprime la plage d'éléments [first, last).

#include <vector>
#include <iostream>

void print_vector(const std::vector<int>& v) {
    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << "Initial: "; print_vector(c);

    // Supprimer le premier élément
    c.erase(c.begin());
    std::cout << "Après erase(begin): "; print_vector(c); // 1 2 3 4 5 6 7 8 9

    // Supprimer une plage d'éléments
    c.erase(c.begin() + 2, c.begin() + 5); // Supprime les éléments aux indices 2, 3, 4
    std::cout << "Après erase(begin+2, begin+5): "; print_vector(c); // 1 2 6 7 8 9

    return 0;
}

`push_back()`

Ajoute un nouvel élément à la fin du vecteur. Peut provoquer une réallocation si la capacité est atteinte.

vec.push_back(element); // Ajoute 'element' à la fin.

`pop_back()`

Supprime le dernier élément du vecteur. Ne doit pas être appelée sur un vecteur vide.

vec.pop_back(); // Supprime le dernier élément.

`swap()`

Échange le contenu de deux vecteurs. Cette opération est très efficace car elle ne fait que d'échanger les pointeurs de données internes, sans copier les éléments.

#include <vector>
#include <iostream>

void print_vector(const std::vector<int>& v) {
    for (int num : v) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5};

    std::cout << "Avant swap:\n";
    std::cout << "v1: "; print_vector(v1);
    std::cout << "v2: "; print_vector(v2);

    v1.swap(v2); // Échange le contenu de v1 et v2

    std::cout << "\nAprès swap:\n";
    std::cout << "v1: "; print_vector(v1); // Contient maintenant {4, 5}
    std::cout << "v2: "; print_vector(v2); // Contient maintenant {1, 2, 3}

    return 0;
}

`assign()`

Remplace le contenu du vecteur par un nouveau contenu.

void assign(size_type count, const T& value); : Remplit le vecteur avec count copies de value.
template< class InputIt > void assign(InputIt first, InputIt last); : Remplit le vecteur avec les éléments de la plage [first, last).
void assign(std::initializer_list<T> ilist); : Remplit le vecteur avec les éléments d'une liste d'initialisation.

#include <vector>
#include <iostream>
#include <string>

int main() {
    std::vector<char> characters;

    auto print_vector = [&]() {
        for (char c : characters) {
            std::cout << c << ' ';
        }
        std::cout << '\n';
    };

    // Remplir avec 5 'a'
    characters.assign(5, 'a');
    print_vector(); // a a a a a

    // Remplir avec une plage de caractères d'une chaîne
    const std::string extra = "hello";
    characters.assign(extra.begin(), extra.end());
    print_vector(); // h e l l o

    // Remplir avec une liste d'initialisation
    characters.assign({'C', '+', '+'});
    print_vector(); // C + +

    return 0;
}

Remarques

std::vector ne fournit pas d'interfaces comme push_front ou pop_front car ces opérations seraient inefficaces sur une structure de données basée sur un tableau contigu.

Étiquettes: C++ STL vector Tableau dynamique conteneur

Publié le 27 juillet à 06h32

L'Atelier Monstre

Maîtriser le conteneur std::vector en C++

Principe de fonctionnement

Opérations et interfaces courantes

Définition, initialisation et affectation

Accès aux éléments

Opérateur `[]`

Méthode `at()`

Méthode `front()`

Méthode `back()`

Méthode `data()`

Itérateurs

Itérateurs directs

Itérateurs inversés

Boucle `for` basée sur la plage (Range-based for loop)

Capacité

`empty()`

`size()`

`max_size()`

`capacity()`

`resize()`

`reserve()`

`shrink_to_fit()`

Exemples de gestion de capacité

Relation entre `size`, `capacity` et `empty`

Stratégie d'augmentation de capacité

Modificateurs

`clear()`

`insert()`

`emplace()`

`emplace_back()`

`erase()`

`push_back()`

`pop_back()`

`swap()`

`assign()`

Remarques

Étiquettes Populaires

L'Atelier Monstre

Maîtriser le conteneur std::vector en C++

Principe de fonctionnement

Opérations et interfaces courantes

Définition, initialisation et affectation

Accès aux éléments

Opérateur []

Méthode at()

Méthode front()

Méthode back()

Méthode data()

Itérateurs

Itérateurs directs

Itérateurs inversés

Boucle for basée sur la plage (Range-based for loop)

Capacité

empty()

size()

max_size()

capacity()

resize()

reserve()

shrink_to_fit()

Exemples de gestion de capacité

Relation entre size, capacity et empty

Stratégie d'augmentation de capacité

Modificateurs

clear()

insert()

emplace()

emplace_back()

erase()

push_back()

pop_back()

swap()

assign()

Remarques

Étiquettes Populaires

Opérateur `[]`

Méthode `at()`

Méthode `front()`

Méthode `back()`

Méthode `data()`

Boucle `for` basée sur la plage (Range-based for loop)

`empty()`

`size()`

`max_size()`

`capacity()`

`resize()`

`reserve()`

`shrink_to_fit()`

Relation entre `size`, `capacity` et `empty`

`clear()`

`insert()`

`emplace()`

`emplace_back()`

`erase()`

`push_back()`

`pop_back()`

`swap()`

`assign()`