Conteneur vector C++

En C++,vectorC'est l'un des conteneurs STL les plus couramment utilisés.

vectorEssentiellement, c'est unUn tableau dynamique qui peut s'étendre automatiquement.Comparé aux tableaux traditionnels, vector ne nécessite pas de gestion manuelle de la mémoire et peut s'étendre automatiquement en fonction du nombre d'éléments.

Car vector possède :

• Stockage contigu en mémoire
• Accès aléatoire rapide
• Écosystème STL complet
• Optimisé pour le cache

Par conséquent, dans le développement C++ moderne, vector est le choix privilégié pour la plupart des scénarios de stockage de données séquentielles.

Caractéristiques principales de vector

• Taille dynamique :vector peut s'étendre et se réduire automatiquement.
• Mémoire contiguë :Les éléments sont stockés de manière contiguë en mémoire, ce qui rend l'accès très efficace.
• Accès aléatoire :Il permet un accès rapide aux éléments par index, avec une complexité temporelle de O(1).
• Gestion automatique de la mémoire :Pas besoin d'appeler manuellement malloc/free.
• Prend en charge les itérateurs :Il peut être facilement utilisé avec les algorithmes STL.

Pourquoi vector est-il rapide ?

Les éléments d'un vector sont disposés de manière contiguë en mémoire :

[1][2][3][4][5]

Cette disposition est très favorable au cache du CPU.

Lorsque le CPU lit le premier élément, il précharge généralement les données suivantes dans le cache à l'avance, donc parcourir un vector est généralement très rapide.

C'est aussi pourquoi dans de nombreux cas :

vector 比 list 更快

Même si list a une complexité théorique de suppression plus faible.

Utilisation de vector

Avant d'utiliser vector, vous devez inclure le fichier d'en-tête :

#include <vector>

Création de vector

Créer un vector vide :

std::vector<int>vec;

Spécifier la taille initiale :

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

Le code ci-dessus crée 5 éléments avec la valeur par défaut de 0.

Spécifier la valeur initiale :

std::vector<int>vec(5, 10);

Résultat de la création :

[10, 10, 10, 10, 10]

Utiliser une liste d'initialisation :

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

Ajout d'éléments

Utilisationpush_back()Ajouter des éléments à la fin :

vec.push_back(100);

La complexité temporelle moyenne de l'ajout d'un élément à la fin d'un vecteur est :

O(1)

Accéder aux éléments

Accéder à l'aide d'indices :

int x = vec[0];

Utilisationat()：

int y = vec.at(1);

Différence :

• []Pas de vérification des limites, plus rapide.
• at()La vérification des limites est effectuée, plus sûre.

Obtenir size

vec.size();

Renvoie le nombre actuel d'éléments.

La différence entre size et capacity

C'est l'un des concepts les plus importants de vector.

std::vector<int>vec;

vec.push_back(1);
vec.push_back(2);

std::cout << vec.size() << std::endl;
std::cout << vec.capacity() << std::endl;

La sortie peut être :

2
4

• size：Nombre actuel d'éléments.
• capacity：La capacité mémoire actuellement allouée.

capacity est généralement supérieure ou égale à size.

C'est parce que vector demande plus d'espace à l'avance pour réduire les réallocations fréquentes.

mécanisme d'expansion de vector

Lorsque la capacité d'un vector est insuffisante, une réallocation se produit :

1. Allouer une mémoire plus grande
2. Copier les anciens éléments
3. Libérer l'ancienne mémoire

Ce processus est relativement coûteux.

Par exemple :

std::vector<int>vec;

for (int i = 0; i < 1000000; i++) {
    vec.push_back(i);
}

Plusieurs réallocations de mémoire peuvent se produire.

reserve() préalloue de l'espace.

Pour éviter des réallocations fréquentes, la mémoire peut être allouée à l'avance :

std::vector<int>vec;

vec.reserve(1000000);

Cela peut réduire :

• Réallocation de mémoire
• Copie d'éléments
• Surcoût de performance

Il s'agit d'une technique d'optimisation très importante dans le développement d'ingénierie.

Parcours de vector

Utilisation d'un indice

for (size_t i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " ";
}

Utilisation d'itérateurs

for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

Boucle for basée sur une plage

for (int element : vec) {
    std::cout << element << " ";
}

Supprimer un élément

Supprimer le troisième élément :

vec.erase(vec.begin() + 2);

Remarque :

Lorsqu'un vector supprime un élément au milieu, les éléments suivants sont décalés vers l'avant en bloc.

Par exemple :

1 2 3 4 5

删除 2 后：

1 3 4 5

Où :

3 4 5

Tous doivent être déplacés.

Par conséquent :

erase() 的时间复杂度为 O(n)

Scénarios où vector n'est pas adapté

• Insertions fréquentes en tête
• Suppressions fréquentes au milieu
• Agrandissements fréquents avec des objets surdimensionnés

Par exemple :

vec.insert(vec.begin(), 100);

C'est une opération relativement lente.

Invalidation d'itérateur

Après la réallocation d’un vector, les adresses mémoire d’origine peuvent devenir invalides.

Par exemple :

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

auto it = vec.begin();

vec.push_back(4);

std::cout << *it;

iciitElles peuvent avoir été invalidées.

Parce que push_back() peut provoquer une réallocation de mémoire.

C’est l’un des pièges les plus courants avec vector.

Remarques sur clear()

vec.clear();

clear() efface uniquement les éléments :

• size devient 0
• La capacité peut encore être conservée.

C’est-à-dire :

clear() 不一定释放内存

Si vous voulez libérer la mémoire :

std::vector<int>().swap(vec);

Ou :

vec.shrink_to_fit();

push_back et emplace_back

Le C++ moderne recommande d’utiliser :

emplace_back()

Par exemple :

vec.push_back(Person("Tom", 20));

Des objets temporaires peuvent être créés.

Et :

vec.emplace_back("Tom", 20);

Il construit l'objet directement en place à l'intérieur du vector.

Généralement plus efficace.

Différences entre vector et array

Complexité des opérations courantes sur vector

Exemple : gestion des notes d'étudiants

Le résultat de sortie est le suivant :

所有成绩: 85 90 78 92 88 
平均成绩: 86.6
删除后成绩: 85 90 92 88 

Résumé

vector est l'une des structures de données les plus importantes et les plus couramment utilisées en C++ moderne.

Ses principaux avantages :

• Redimensionnement dynamique
• Mémoire contiguë
• Accès aléatoire rapide
• Optimisé pour le cache
• Écosystème STL complet

Mais en même temps, notez que :

• Coût de performance de l'expansion
• Faible efficacité de la suppression au milieu
• Problème d'invalidation des itérateurs

Pour la grande majorité des scénarios de stockage séquentiel :

vector 通常都是默认首选容器