La classe list en C++ (bibliothèque STL) <list>

La classe list, définie dans le fichier d'en-tête <list>, est un conteneur de séquence avec une insertion et une suppression rapide à tout moment. Cela signifie que nous pouvons insérer ou supprimer facilement à tout moment dans une liste.

Les listes C++ peuvent être réduites ou étendues des deux côtés au moment de l'exécution. Le besoin de stockage est automatiquement satisfait par l'allocateur interne.

Une liste ne prend pas en charge l'accès aléatoire pour récupérer ou modifier la valeur d'un élément à l'aide de l'opérateur d'index ou de la fonction membre at() car la liste est implémentée comme une liste doublement chainée, pas comme un tableau dans la mémoire tas. Si nous voulons accéder à la liste de façon aléatoire, nous devons utiliser un itérateur qui se déplace jusqu'à l'élément désiré et y accède ensuite.

La figure ci-dessous décrit une liste et montre que chaque nœud possède une section de données et deux pointeurs, l'un pointant vers le nœud précédent et l'autre pointant vers le nœud suivant.

Les conteneurs de liste sont implémentés comme des listes doublement chainées. Les listes doublement chainées peuvent stocker chacun des éléments qu'elles contiennent dans des emplacements de stockage différents et non liés. L'ordre est maintenu en interne par l'association à chaque élément d'un lien (pointeur) vers l'élément qui le précède et d'un lien vers l'élément qui le suit.

Par rapport à d'autres conteneurs de séquence standard de base (array, vector et deque), les listes fonctionnent généralement mieux pour insérer, extraire et déplacer des éléments dans n'importe quelle position du conteneur pour lequel un itérateur a déjà été obtenu, et donc également dans les algorithmes qui font un usage intensif d'entre eux, comme les algorithmes de tri.

Syntaxe

template < class T, class Alloc = allocator<T> > class list;

•  T - Type de l'élément contenu
•  Alloc - Type d'objet d'allocation. Le modèle de classe d'allocateur est utilisé par défaut, ce qui définit le modèle d'allocation de mémoire le plus simple et est indépendant de la valeur.

Si nous voulons faire une liste d'entiers, nous pouvons le faire par le code suivant.

list<int> liste;

Construit un objet conteneur list, en initialisant son contenu dépend de la version du constructeur utilisée :

list <T> liste; // Construit un conteneur vide, sans éléments. 
list <T> liste(n , valeur); // Construit un conteneur avec n éléments. Chaque élément est une copie de val (si fourni).
list <T> liste (debut,fin); // Construit un conteneur avec autant d'éléments que la plage [debut,fin[, chaque élément étant créé à partir de son élément correspondant dans cette plage, dans le même ordre. 
list <T> liste (autreListe); // Construit un conteneur avec une copie de chacun des éléments de autreListe, dans le même ordre.
list <T> liste = autreListe; // opérateur d'affectation
        

Le destructeur C++ std::list::~list() détruit l'objet liste en libérant sa mémoire. Vous pouvez définir le destructeur c++ à l'aide du code suivant.

~list();

Exemple

#include<iostream>
#include<list> // classe list (conteneur)

using namespace std;

void afficher(list <int> liste)
{
    for (int elem : liste) {
		cout << elem <<"  ";
	}
    cout << "\n";
}

int main (){

    list<int> liste1; // liste vide 
    cout<< "Contenu de Liste1 : "<<"\n";
    afficher(liste1);

    list<int> liste2 = { 12, 5, 10, 9 }; // liste avec 4 éléments
    cout<< "Contenu de Liste2 : "<<"\n";
    afficher(liste2);

    list<int> liste3(4,2); // liste avec 4 éléments
    cout<< "Contenu de Liste3 : "<<"\n";
    afficher(liste3);

    list<int> liste4=liste2; // opérateur d'affectation
    cout<< "Contenu de Liste4 : "<<"\n";
    afficher(liste4);

    return 0;
}
        

Résultat

Contenu de Liste1 : 

Contenu de Liste2 :
12  5  10  9
Contenu de Liste3 :
2  2  2  2
Contenu de Liste4 :
12  5  10  9
                

Le conteneur list est étendu en insérant de nouveaux éléments avant l'élément à la position spécifiée. Cela augmente effectivement la taille du conteneur de la quantité d'éléments insérés.

Contrairement aux autres conteneurs de séquence standard, les objets de list sont spécifiquement conçus pour insérer et supprimer efficacement des éléments dans n'importe quelle position, même au milieu de la séquence.

Après l'insertion un itérateur est retourné qui pointe vers le premier élément des éléments nouvellement insérés.

iterator insert (const_iterator position, val);
iterator insert (const_iterator position, n, val); // Nombre d'éléments à insérer (n). Chaque élément est initialisé avec une copie de val.
iterator insert (const_iterator position, premier, dernier); // premier et dernier sont des itérateurs spécifiant une plage d'éléments. Les copies des éléments de la plage [premier, dernier) sont insérées à la position (dans le même ordre).
iterator insert (const_iterator position, liste); // Des copies de ces éléments (liste) sont insérées à la position (dans le même ordre).
        

En plus de la fonction insert nous pouvons utiliser push_back et push_front pour ajouter un nouvel élément à la liste .

void push_back (const value_type& val);

Ajoute un nouvel élément à la fin du conteneur list, après son dernier élément actuel. Le contenu de val est copié dans le nouvel élément.

void push_front (const value_type& val);

Insère un nouvel élément au début du conteneur list, juste avant son premier élément actuel. Le contenu de val est copié dans l'élément inséré.

La classe list a trois fonctions membres liées à la taille d'une liste.

liste.size(); // Renvoie la taille actuelle
liste.max_size(); // Renvoie la taille maximale
liste.empty(); // Renvoie true si la liste est vide
        

La classe list fournit les fonctions membres suivantes pour accéder aux éléments déjà présents dans la liste.

liste.front();  // Accéder au premier élément
liste.back(); // Accéder au dernier élément
        

L'opérateur [] et la fonction at() ne sont pas pris en charge pour la classe list car la classe list ne prend pas en charge l'opérateur d'accès aléatoire. Nous devons explicitement utiliser un itérateur pour accéder aux éléments.

La classe list définit plusieurs fonctions membres pour la suppression d'un ou plusieurs éléments dans le conteneur.

liste.pop_back();  // Supprimer le dernier élément
liste.pop_front();  // Supprimer le premier élément
liste.erase(pos); // Supprimer l'élément pointé par pos
liste.erase(premier, dernier);  // Supprimer les éléments de la plage [premier, dernier)
liste.clear();  // Supprimer tous les éléments
        

Les arguments premier et dernier sont des itérateurs.

La classe list fournit trois nouvelles fonctions pour effacer un ou plusieurs éléments de la liste. Ce qui suit montre comment nous appelons ces fonctions.

liste.remove(valeur); // Efface toutes les occurrences de valeur
liste.remove_if(predicat); // Efface toutes les occurrences pour lesquelles le prédicat est vrai
liste.unique(predicat); // Efface les doublons adjacents si le prédicat est vrai
        

La classe list définit trois autres fonctions : splice(), merge(),et sort()

Liste.splice(pos premier, dernier); // Insère les éléments [premier, dernier) d'une autre liste avant pos
liste.merge(autreList); // Fusionne deux listes triées en une nouvelle liste triée
liste.sort(); // Trie la liste
        

#include<iostream>
#include<list> // classe list (conteneur)

using namespace std;

void afficher(list <int> liste)
{
    for (int elem : liste) {
		cout << elem <<"  ";
	}
    cout << "\n";
}

bool comparaison (int premier, int deuxieme)
{
  return (premier>deuxieme);
}

int main (){

    list<int> liste; // liste vide 
    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<< "La taille est : "<< liste.size()<<endl;
    cout<< "La taille maximale est : "<< liste.max_size()<<endl;

    cout<< "Le premier element est : "<< liste.front() <<endl;
    cout<< "Le dernier element est : "<< liste.back() <<endl;

    cout<< '\n';

    cout<< "Contenu de la liste : "<<"\n";
    afficher(liste);

    cout<< '\n';
    list<int>::iterator it = liste.begin();
    liste.insert(++it, 30); // insérer après le premier élément

    // maintenant l'itérateur est pointé sur la valeur 30
    liste.insert(it, 4, 7); // insérer 4 fois la valeur 7 après 30
    cout<< "Contenu de la liste apres insertion de 30 et 7 : "<<"\n";
    afficher(liste);

    liste.pop_back();  // Supprimer le dernier élément
    liste.pop_front();  // Supprimer le premier élément

    cout<< "Contenu de la liste apres pop: "<<"\n";
    afficher(liste);

    liste.remove(5); // Efface toutes les occurrences de 5
    cout<< "Contenu de la liste apres suppression de 5: "<<"\n";
    afficher(liste);

    liste.unique(); // Efface les doublons adjacents
    cout<< "Contenu de la liste apres la suppression des doublons adjacents : "<<"\n";
    afficher(liste);

    liste.sort(); // Trier la liste dans l'ordre croissant
    cout<< "Contenu de la liste apres le tri ASC : "<<"\n";
    afficher(liste);

    liste.sort(comparaison); // Trier la liste dans l'ordre décroissant
    cout<< "Contenu de la liste apres le tri DESC : "<<"\n";
    afficher(liste);

    return 0;
}
        

Résultat

La taille est : 7
La taille maximale est : 384307168202282325
Le premier element est : 25
Le dernier element est : 4

Contenu de la liste :
25  1  2  5  10  5  4

Contenu de la liste apres insertion de 30 et 7 :
25  30  7  7  7  7  1  2  5  10  5  4
Contenu de la liste apres pop:
30  7  7  7  7  1  2  5  10  5
Contenu de la liste apres suppression de 5:
30  7  7  7  7  1  2  10
Contenu de la liste apres la suppression des doublons adjacents :
30  7  1  2  10
Contenu de la liste apres le tri ASC :
1  2  7  10  30
Contenu de la liste apres le tri DESC :
30  10  7  2  1