Classes de conteneurs C++<list>
La bibliothèque standard C++ fournit un riche ensemble de fonctionnalités, parmi lesquelles<list>est une classe de conteneur très importante pour stocker des collections d'éléments, prenant en charge les itérateurs bidirectionnels.
<list>est un conteneur de séquence dans la bibliothèque de modèles standard C++ (STL) qui permet une insertion et une suppression rapides d'éléments à n'importe quelle position dans le conteneur. Contrairement aux tableaux ou aux vecteurs (<vector>) différent,<list>n'a pas besoin de spécifier une taille à la création et peut ajouter ou supprimer des éléments à n'importe quelle position sans réallouer de mémoire.
Syntaxe
Les suivantes sont<list>Quelques opérations de base des conteneurs :
- Inclure le fichier d'en-tête :
#include <list> - Déclarer une liste :
std::list<T> mylist;, oùTEst le type des éléments stockés dans la liste. - Insérer des éléments :
mylist.push_back(value); - Supprimer un élément :
mylist.pop_back();oumylist.erase(iterator); - Accéder aux éléments :
mylist.front();etmylist.back(); - Parcourir la liste : utilisation d'itérateurs
for (auto it = mylist.begin(); it != mylist.end(); ++it)
Fonctionnalités
- Itération bidirectionnelle：
<list>fournit des itérateurs bidirectionnels, permettant de parcourir les éléments en avant et en arrière. - Taille dynamique: Contrairement aux tableaux,
<list>La taille peut changer dynamiquement, sans avoir besoin de préallouer une quantité fixe de mémoire. - Insertion et suppression rapides: les éléments peuvent être rapidement insérés ou supprimés à n'importe quelle position de la liste, sans avoir besoin de déplacer un grand nombre d'éléments comme ce serait le cas avec les vecteurs.
Déclaration et initialisation
<list>La déclaration et l'initialisation sont similaires à celles des autres conteneurs :
#include <iostream>
#include <list>
int main() {
std::list<int> lst1; // 空的list
std::list<int> lst2(5); // 包含5个默认初始化元素的list
std::list<int> lst3(5, 10); // 包含5个元素，每个元素为10
std::list<int> lst4 = {1, 2, 3, 4}; // 使用初始化列表
return 0;
}
Exemple
Voici un exemple utilisant<list>Un exemple simple, incluant la création d'une liste, l'ajout d'éléments, le parcours de la liste et l'affichage des résultats.
Exemple
#include <iostream>
#include <list>
int main() {
// créer une liste de type entier
std::list<int> numbers;
// ajouter des éléments à la liste
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// accéder au premier élément de la liste et l'afficher
std::cout << "Premier élément : " << numbers.front() << std::endl;
// accéder au dernier élément de la liste et l'afficher
std::cout << "Dernier élément : " << numbers.back() << std::endl;
// Parcourir la liste et afficher tous les éléments
std::cout << "Éléments de la liste : ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// Supprimer le dernier élément de la liste
numbers.pop_back();
// Parcourir à nouveau la liste et afficher tous les éléments
std::cout << "Éléments de la liste après suppression du dernier élément : ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
// créer une liste de type entier
std::list<int> numbers;
// ajouter des éléments à la liste
numbers.push_back(10);
numbers.push_back(20);
numbers.push_back(30);
// accéder au premier élément de la liste et l'afficher
std::cout << "Premier élément : " << numbers.front() << std::endl;
// accéder au dernier élément de la liste et l'afficher
std::cout << "Dernier élément : " << numbers.back() << std::endl;
// Parcourir la liste et afficher tous les éléments
std::cout << "Éléments de la liste : ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// Supprimer le dernier élément de la liste
numbers.pop_back();
// Parcourir à nouveau la liste et afficher tous les éléments
std::cout << "Éléments de la liste après suppression du dernier élément : ";
for (std::list<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
Sortie :
First element: 10 Last element: 30 List elements: 10 20 30 List elements after removing the last element: 10 20
Fonctions membres courantes
Les suivantes sont<list>Quelques fonctions membres couramment utilisées :
| Fonction | Description |
|---|---|
push_back(const T& val) |
Ajouter un élément à la fin de la liste chaînée |
push_front(const T& val) |
Ajouter un élément en tête de la liste chaînée |
pop_back() |
Supprimer l'élément à la fin de la liste chaînée |
pop_front() |
Supprimer l'élément en tête de la liste chaînée |
insert(iterator pos, val) |
Insérer un élément à une position spécifiée |
erase(iterator pos) |
Supprimer l'élément à une position spécifiée |
clear() |
Effacer tous les éléments |
size() |
Retourner le nombre d'éléments dans la liste chaînée |
empty() |
Vérifier si la liste chaînée est vide |
front() |
Retourner le premier élément de la liste chaînée |
back() |
Retourner le dernier élément de la liste chaînée |
remove(const T& val) |
Supprimer tous les éléments égaux à une valeur spécifiée |
sort() |
Trier les éléments de la liste chaînée |
merge(list& other) |
Fusionner une autre liste chaînée triée |
reverse() |
Inverser la liste chaînée |
begin() / end() |
Retourner les itérateurs begin/end de la liste chaînée |
Exemple
1. Opérations de base
Exemple
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {10, 20, 30};
// Insérer et supprimer des éléments
lst.push_front(5); // Insérer 5 en tête
lst.push_back(40); // Insérer 40 en queue
lst.pop_front(); // Supprimer l'élément de tête
lst.pop_back(); // Supprimer l'élément de queue
// Afficher le contenu de la liste chaînée
std::cout << "Éléments de la liste : ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {10, 20, 30};
// Insérer et supprimer des éléments
lst.push_front(5); // Insérer 5 en tête
lst.push_back(40); // Insérer 40 en queue
lst.pop_front(); // Supprimer l'élément de tête
lst.pop_back(); // Supprimer l'élément de queue
// Afficher le contenu de la liste chaînée
std::cout << "Éléments de la liste : ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
2. Insertion et suppression d'éléments à des positions spécifiques
Exemple
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // Déplacer l'itérateur vers le 3e élément (valeur 3)
lst.insert(it, 10); // Insérer 10 avant le 3e élément
lst.erase(it); // Supprimer le 3e élément
// Afficher le contenu de la liste chaînée
std::cout << "Éléments de la liste : ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // Déplacer l'itérateur vers le 3e élément (valeur 3)
lst.insert(it, 10); // Insérer 10 avant le 3e élément
lst.erase(it); // Supprimer le 3e élément
// Afficher le contenu de la liste chaînée
std::cout << "Éléments de la liste : ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
3. Tri et déduplication
Exemple
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
lst.sort(); // Trier
lst.unique(); // Supprimer les doublons adjacents
// Afficher le contenu de la liste chaînée
std::cout << "Liste triée et unique : ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
lst.sort(); // Trier
lst.unique(); // Supprimer les doublons adjacents
// Afficher le contenu de la liste chaînée
std::cout << "Liste triée et unique : ";
for (const auto& elem : lst) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
4. Fusion et inversion
Exemple
#include <iostream>
#include <list>
int main() {
std::list<int> lst1 = {1, 3, 5, 7};
std::list<int> lst2 = {2, 4, 6, 8};
lst1.merge(lst2); // Fusionner deux listes chaînées triées
lst1.reverse(); // Inverser la liste chaînée
// Afficher le contenu de la liste chaînée
std::cout << "Liste fusionnée et inversée : ";
for (const auto& elem : lst1) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
#include <list>
int main() {
std::list<int> lst1 = {1, 3, 5, 7};
std::list<int> lst2 = {2, 4, 6, 8};
lst1.merge(lst2); // Fusionner deux listes chaînées triées
lst1.reverse(); // Inverser la liste chaînée
// Afficher le contenu de la liste chaînée
std::cout << "Liste fusionnée et inversée : ";
for (const auto& elem : lst1) {
std::cout << elem << " ";
}
std::cout << std::endl;
return 0;
}
Comparaison avec d'autres conteneurs
| Fonctionnalités | std::list | std::vector | std::deque |
|---|---|---|---|
| Structure de la mémoire | Mémoire non contiguë, liste doublement chaînée | Mémoire contiguë | Mémoire contiguë segmentée |
| Performances d'accès | L'accès séquentiel est rapide, l'accès aléatoire est lent | Accès aléatoire rapide | L'accès à la queue et à la tête est rapide |
| Performances d'insertion/suppression | L'insertion et la suppression à n'importe quelle position sont rapides | L'insertion à la fin est rapide, mais au milieu est lente | L'insertion et la suppression en tête et en queue sont rapides |
| Scénarios applicables | Insertion/suppression fréquentes au milieu | Nécessite un accès aléatoire efficace | Besoin d'une insertion/suppression rapide en tête et en queue |
| Stabilité des itérateurs | Stable ; l'insertion ou la suppression d'éléments ne provoque pas d'invalidation | L'insertion et la suppression peuvent invalider les itérateurs | L'insertion et la suppression peuvent invalider les itérateurs |
Notes
<list>Les éléments sont stockés dans l'ordre d'insertion, et non triés par valeur d'élément.- En raison de
<list>Les éléments sont stockés dans différents emplacements mémoire, de sorte qu'il n'est pas adapté aux scénarios nécessitant un accès aléatoire. - Par rapport aux vecteurs,
<list>L'efficacité d'utilisation de la mémoire est faible, car chaque élément nécessite de l'espace supplémentaire pour stocker des pointeurs vers les éléments précédent et suivant.
Grâce à cette introduction simple et à ces exemples, les débutants devraient pouvoir acquérir une compréhension de base du<list>conteneur C++, et commencer à l'utiliser pour résoudre des problèmes concrets.