Conteneurs de séquence - list

 

list

Pour utiliser un conteneur list, vous devez inclure le fichier en-tête <list> au début du programme et travailler dans l’espace de noms std. Généralement, la classe list est implémentée sous la forme d’une liste doublement chaînée. Elle fournit les mêmes opérateurs et membres qu’un conteneur vector à l’exception de l’opérateur d’index [], et des fonctions capacity() et reserve().
La gestion de la mémoire étant plus dynamique qu’avec les vector, la classe list peut offrir des opérations de collage, de tri, de fusion et certaines opérations sur le premier élément.

Notre premier exemple illustre l’utilisation de la fonction splice() qui permet d’effectuer un couper-coller entre deux listes. Cette fonction est d’autant plus efficace qu’aucun élément des deux listes n’est modifié. En effet, les pointeurs reliant les nœuds de chaque chaîne sont simplement « redéfinis ».  

Code 8.6 : couper-coller entre deux listes

#include <iostream> 
#include <list> 
using namespace std; 

typedef list<int>  l_entiers; 
typedef list<int>::iterator  Iter_lEntiers; 

//Prototype de la fonction d’affichage 
template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste); 

int main() 
{ 
  // on définit une liste d’entiers avec 5 éléments 
  l_entiers  Liste_1(5); 
  int  j = 0; 
  for (Iter_lEntiers i1 = Liste_1.begin(); i1 != Liste_1.end(); ++i1) 


  • i1 = 5 * j++; 

  cout << "Liste_1" << "\n"; 
  AfficherListe(Liste_1); 

  //On définit une liste d’entiers avec 6 éléments 
  l_entiers  Liste_2(6); 
  j = 0; 
  for (Iter_lEntiers i2 = Liste_2.begin(); i2 != Liste_2.end(); ++i2) 


  • i2 = 100 * j++; 

  cout << "Liste_2" << "\n"; 
  AfficherListe(Liste_2); 

  // On exécute le couper-coller 
  cout << "Après le couper-coller:\n"; 
  Liste_1.splice(++Liste_1.begin(), Liste_2, ++(++Liste_2.begin()), --Liste_2.end()); 
  cout << "Liste_1" << "\n"; 
  AfficherListe(Liste_1); 
  cout << "Liste_2" << "\n"; 
  AfficherListe(Liste_2); 
} 

//Définition de la fonction d’affichage 
template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste) 
{ 
  cout << "Taille = " << une_liste.size() << endl; 
  cout << "Eléments :"; 
  for (typename list<T, A>::const_iterator i = une_liste.begin(); 
                 i != une_liste.end(); ++i) 
    cout << *i << ", "; 
  cout << "\n\n"; 
}


Voici le résultat de l’exécution de ce code : 

Liste_1 
Taille = 5 
Eléments:  0, 5, 10, 15, 20, 

Liste_2 
Taille = 6 
Eléments:  0, 100, 200, 300, 400, 500, 

Après le couper-coller : 
Liste_1 
Taille = 8 
Eléments:  0, 200, 300, 400, 5, 10, 15, 20, 

Liste_2 
Taille = 3 
Eléments:  0, 100, 500,


Vous pouvez facilement ajouter un élément dans une liste en le plaçant en tête de cette dernière. Vous disposez en effet de deux opérations sur le premier élément d’un conteneur list : l’ajout et la suppression. L’exemple du code 8.7 illustre les fonctions push_front() et pop_front() correspondantes (respectivement).  

Code 8.7 : ajout et suppression du premier élément d’une liste

#include <iostream> 
#include <list>  
using namespace std; 

typedef list<int>      l_entiers; 
typedef list<int>::iterator      Iter_lEntiers; 

template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste); 

int main() 
{ 
  // on définit une liste d’entiers avec 5 éléments 
  l_entiers  Liste_1(5); 
  int  j = 0; 
  for (Iter_lEntiers ia = Liste_1.begin(); ia != Liste_1.end(); ++ia) 


  • ia = 5 * j++;

  cout << "Liste_1" << "\n"; 
  AfficherListe(Liste_1); 

  // On supprime le premier élément 
  Liste_1.pop_front(); 
  cout << "On supprime le premier élément:\n"; 
  AfficherListe(Liste_1); 

  // on insère un nouvel élément 
  Liste_1.push_front(0); 
  cout << "On ajoute 0 au début de la liste:\n"; 
  AfficherListe(Liste_1); 
} 

//Définition de la fonction d’affichage 
template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste) 
{ 
  cout << "Taille = " << une_liste.size() << endl; 
  cout << "Eléments :"; 
  for (typename list<T, A>::const_iterator i = une_liste.begin(); 
                 i != une_liste.end(); ++i) 
    cout << *i << ", "; 
  cout << "\n\n"; 
}

On obtient le résultat : 
Liste_1 
Taille = 5 
Eléments:  0, 5, 10, 15, 20, 

On supprime le premier élément: 
Taille = 4 
Eléments:  5, 10, 15, 20, 

On ajoute 0 au début de la liste: 
Taille = 5 
Eléments:  0, 5, 10, 15, 20,


Quand vous travaillez avec une liste, vous pouvez avoir besoin de réorganiser les éléments. La classe list fournit les fonctions sort() pour le tri, reverse() pour inverser l’ordre des éléments et merge() pour fusionner deux listes. Le code 8.8 illustre l’utilisation de ces trois fonctions.  

Code 8.8 : tri, fusion et inversement des éléments de liste

#include <iostream> 
#include <list>  
using namespace std; 

typedef list<int>  l_entiers; 
typedef list<int>::iterator  Iter_lEntiers; 

template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste); 

int main() 
{ 
  // on définit une liste d’entiers avec 5 éléments 
  l_entiers  Liste_1(5); 
  int  j = 0; 
  for (Iter_lEntiers ia = Liste_1.begin(); ia != Liste_1.end(); ++ia) 


  • ia = 5 * j++; 

  cout << "Liste_1 :" << "\n"; 
  AfficherListe(Liste_1); 

  // on définit une liste d’entiers avec 6 éléments 
  l_entiers  Liste_2(6); 
  j = 10; 
  for (Iter_lEntiers ib = Liste_2.begin(); ib != Liste_2.end(); ++ib) 


  • ib = 2 * j--;

  cout << "Liste_2 :" << "\n"; 
  AfficherListe(Liste_2); 

//On crée 2 autres listes à partir des 2 premières 
  l_entiers Liste_3 = Liste_1; 
  l_entiers Liste_4 = Liste_2; 

  //On fusionne les 2 premières 
  cout << "Fusion des listes non triées :\n"; 
  Liste_1.merge(Liste_2); 

  cout << "Liste_1" << "\n"; 
  AfficherListe(Liste_1); 
  cout << "Liste_2" << "\n"; 
  AfficherListe(Liste_2); 

  cout << "On inverse les éléments de Liste_1\n"; 
  Liste_1.reverse(); 
  AfficherListe(Liste_1); 

  cout << "On trie Liste_3 et Liste_4 puis on fusionne:\n"; 
  Liste_3.sort(); 
  Liste_4.sort();  
  Liste_3.merge(Liste_4);  

  cout << "Liste_3" << "\n"; 
  AfficherListe(Liste_3); 
  cout << "Liste_4" << "\n"; 
  AfficherListe(Liste_4); 
} 

//Définition de la fonction d'affichage 
template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste) 
{ 
  cout << "Taille= " << une_liste.size() << endl; 
  cout << "Eléments:"; 
  for (typename list<T, A>::const_iterator i = une_liste.begin(); 
               i != une_liste.end(); ++i) 
    cout << *i << ", "; 
  cout << "\n\n"; 
}

On obtient le résultat suivant : 
Liste_1 
Taille= 5 
Eléments:  0, 5, 10, 15, 20, 

Liste_2 
Taille= 6 
Eléments:  20, 18, 16, 14, 12, 10, 

Fusion des listes non triées : 
Liste_1 
Taille= 11 
Eléments:  0, 5, 10, 15, 20, 20, 18, 16, 14, 12, 10, 

Liste_2 
Taille= 0 
Eléments: 

On inverse les éléments de Liste_1 
Taille= 11 
Eléments:  10, 12, 14, 16, 18, 20, 20, 15, 10, 5, 0, 

On trie Liste_3 et Liste_4 puis on fusionne: 
Liste_3 
Taille= 11 
Eléments:  0, 5, 10, 10, 12, 14, 15, 16, 18, 20, 20, 

Liste_4 
Taille= 0 
Eléments:


Examinons maintenant les opérations de suppression. La classe list fournit les quatre fonctions suivantes : remove() pour supprimer les éléments égaux à son argument, remove_if() pour supprimer les éléments répondant à un certain critère, unique() pour supprimer tous les doublons dans des groupes d’éléments consécutifs et unique() (fonction modèle) pour supprimer des éléments dans des groupes consécutifs mais à partir d’un prédicat. Le code 8.9 illustre l’utilisation de ces fonctions.  

Code 8.9 : suppression d’éléments dans une liste

#include <iostream> 
#include <list>  
using namespace std; 

typedef list<int>    l_entiers; 
typedef list<int>::iterator    Iter_lEntiers; 

template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste); 

int main() 
{ 
  // on définit une liste d’entiers avec 5 éléments 
  l_entiers  Liste_1(5); 
  int  j = 0; 
  for (Iter_lEntiers ia = Liste_1.begin(); ia != Liste_1.end(); ++ia) 


  • ia = 5 * j++;

  cout << "Liste_1" << "\n"; 
  AfficherListe(Liste_1); 

  cout << "On supprime le 5 dans Liste_1:\n"; 
  Liste_1.remove(5); 
  AfficherListe(Liste_1); 

  // on définit une liste d’entiers avec 6 éléments 
  l_entiers  Liste_2(6); 
  j = 10; 
  for (Iter_lEntiers ib = Liste_2.begin(); ib != Liste_2.end(); ++ib) 


  • ib = 2 * j--;

  cout << "Liste_2" << "\n"; 
  AfficherListe(Liste_2); 

  cout << "on colle Liste_1 et Liste_2"; 
  cout << " et on ajoute 10 au début de Liste_1:\n"; 
  Liste_1.splice(++(++Liste_1.begin()), Liste_2); 
  Liste_1.push_front(10);  

  cout << "Liste_1" << "\n"; 
  AfficherListe(Liste_1); 

  cout << "On trie Liste_1:\n"; 
  Liste_1.sort(); 
  AfficherListe(Liste_1); 

 cout<<"Maintenant, on supprime les doublons de Liste_1:"; 
  cout << "\n"; 
  Liste_1.unique(); 
  AfficherListe(Liste_1); 
} 

// 
// On affiche les éléments de la liste 
// 
template<class T, class A> 
void AfficherListe(const list<T, A>& une_liste) 
{ 
  cout << "Taille= " << une_liste.size() << endl; 
  cout << "Eléments:"; 
  for (typename list<T, A>::const_iterator i = une_liste.begin(); 
               i != une_liste.end(); ++i) 
    cout << *i << ", "; 
  cout << "\n\n"; 
}

Voici le résultat de l’exécution de ce code : 
Liste_1 
Taille= 5 
Eléments:  0, 5, 10, 15, 20, 

On supprime le 5 dans Liste_1: 
Taille= 4 
Eléments:  0, 10, 15, 20, 

Liste_2 
Taille= 6 
Eléments:  20, 18, 16, 14, 12, 10, 

on colle Liste_1 & Liste_2 et on ajoute 10 au début de Liste_1: 
Liste_1 
Taille= 11 
Eléments:  10, 0, 10, 20, 18, 16, 14, 12, 10, 15, 20, 

On trie Liste_1: 
Taille= 11 
Eléments:  0, 10, 10, 10, 12, 14, 15, 16, 18, 20, 20, 

Maintenant, on supprime les doublons de Liste_1: 
Taille= 8 
Eléments:  0, 10, 12, 14, 15, 16, 18, 20,


Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)

Réalisé sous la direction de , fondateur de CommentCaMarche.net.

Ce document intitulé «  Conteneurs de séquence - list  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.