La classe list, définie dans l'en-tête <list>, est un conteneur de séquence implémenté comme une liste doublement chaînée. Chaque nœud possède une section de données et deux pointeurs : un vers le nœud précédent et un vers le nœud suivant.
Pas d'accès aléatoire La classe
list ne supporte pas l'opérateur [] ni la fonction at(). Pour accéder à un élément arbitraire, il faut utiliser un itérateur qui se déplace jusqu'à la position souhaitée.| Critère | array / vector / deque | list |
|---|---|---|
| Accès aléatoire | O(1) | O(n) via itérateur |
| Insertion / suppression en tête ou queue | O(n) / O(1) | O(1) |
| Insertion / suppression au milieu | O(n) | O(1) si itérateur déjà positionné |
| Mémoire contiguë | Oui | Non |
Syntaxe et construction
template <class T, class Alloc = allocator<T>> class list;list<T> liste; // Conteneur vide
list<T> liste(n, valeur); // n copies de valeur
list<T> liste(debut, fin); // Copie de la plage [debut, fin)
list<T> liste(autreListe); // Copie d'une autre liste
list<T> liste = autreListe; // Opérateur d'affectationExemple — Différentes constructions
#include <iostream>
#include <list>
using namespace std;
void afficher(list<int> liste) {
for (int elem : liste) cout << elem << " ";
cout << "\n";
}
int main() {
list<int> liste1; // vide
list<int> liste2 = {12, 5, 10, 9}; // 4 éléments
list<int> liste3(4, 2); // {2, 2, 2, 2}
list<int> liste4 = liste2; // copie
cout << "Liste1 : "; afficher(liste1);
cout << "Liste2 : "; afficher(liste2);
cout << "Liste3 : "; afficher(liste3);
cout << "Liste4 : "; afficher(liste4);
return 0;
}Sortie
Liste1 : Liste2 : 12 5 10 9 Liste3 : 2 2 2 2 Liste4 : 12 5 10 9
Insertion
liste.push_back(val); // Ajouter en fin
liste.push_front(val); // Ajouter en tête
// insert — retourne un itérateur vers le 1er élément inséré
liste.insert(position, val); // 1 élément avant position
liste.insert(position, n, val); // n copies de val
liste.insert(position, premier, dernier); // plage [premier, dernier)
liste.insert(position, {a, b, c}); // liste d'initialisationTaille
liste.size(); // Taille actuelle
liste.max_size(); // Taille maximale supportée
liste.empty(); // true si videAccès aux éléments
liste.front(); // Premier élément
liste.back(); // Dernier élément
// Accès à un élément intermédiaire : utiliser un itérateur
list<int>::iterator it = liste.begin();
advance(it, 2); // avancer de 2 positions
cout << *it; // accéder à l'élémentSuppression
liste.pop_back(); // Dernier élément
liste.pop_front(); // Premier élément
liste.erase(pos); // Élément pointé par pos
liste.erase(premier, dernier); // Plage [premier, dernier)
liste.clear(); // Tous les éléments
// Fonctions spécifiques à list
liste.remove(valeur); // Efface toutes les occurrences de valeur
liste.remove_if(predicat); // Efface si le prédicat retourne true
liste.unique(); // Efface les doublons adjacents
liste.unique(predicat); // Efface les adjacents pour lesquels predicat est vraiOpérations avancées — Splice, Merge, Sort
liste.splice(pos, autre, premier, dernier); // Déplace [premier, dernier) avant pos
liste.merge(autreListe); // Fusionne deux listes triées
liste.sort(); // Tri croissant
liste.sort(comparaison); // Tri avec comparateur personnaliséExemple complet
#include <iostream>
#include <list>
using namespace std;
void afficher(list<int> liste) {
for (int elem : liste) cout << elem << " ";
cout << "\n";
}
bool comparaison(int a, int b) { return (a > b); } // ordre décroissant
int main() {
list<int> liste;
liste.push_back(2);
liste.push_back(5);
liste.push_back(10);
liste.push_back(5);
liste.push_back(4);
liste.push_front(1);
liste.push_front(25);
cout << "Taille : " << liste.size() << endl;
cout << "Taille max : " << liste.max_size() << endl;
cout << "Premier : " << liste.front() << endl;
cout << "Dernier : " << liste.back() << endl;
cout << '\n';
cout << "Liste initiale : \n"; afficher(liste);
cout << '\n';
list<int>::iterator it = liste.begin();
liste.insert(++it, 30); // insérer 30 après le 1er élément
liste.insert(it, 4, 7); // insérer 4 fois la valeur 7
cout << "Après insertion de 30 et de 4×7 : \n"; afficher(liste);
liste.pop_back();
liste.pop_front();
cout << "Après pop_front / pop_back : \n"; afficher(liste);
liste.remove(5);
cout << "Après remove(5) : \n"; afficher(liste);
liste.unique();
cout << "Après unique() : \n"; afficher(liste);
liste.sort();
cout << "Après sort() ASC : \n"; afficher(liste);
liste.sort(comparaison);
cout << "Après sort() DESC : \n"; afficher(liste);
return 0;
}Sortie
Taille : 7 Taille max : 384307168202282325 Premier : 25 Dernier : 4 Liste initiale : 25 1 2 5 10 5 4 Après insertion de 30 et de 4×7 : 25 30 7 7 7 7 1 2 5 10 5 4 Après pop_front / pop_back : 30 7 7 7 7 1 2 5 10 5 Après remove(5) : 30 7 7 7 7 1 2 10 Après unique() : 30 7 1 2 10 Après sort() ASC : 1 2 7 10 30 Après sort() DESC : 30 10 7 2 1
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.