std :: liste dans C++ avec exemple

Par : Benjamin marcheur Benjamin marcheur
Hours Le kit de prรฉparation mis ร  jour

โšก Rรฉsumรฉ intelligent

std :: liste dans C++ est un conteneur de sรฉquence implรฉmentรฉ sous forme de liste doublement chaรฎnรฉe, permettant une insertion et une suppression rapides ร  n'importe quelle position tout en stockant les รฉlรฉments dans une mรฉmoire non contiguรซ et en prenant en charge un accรจs sรฉquentiel bidirectionnel au lieu d'un accรจs alรฉatoire.

  • ๐Ÿ”— Liste doublement chaรฎnรฉe : Chaque รฉlรฉment conserve des liens vers son nล“ud prรฉcรฉdent et suivant, de sorte que les donnรฉes de std::list rรฉsident dans une mรฉmoire non contiguรซ.
  • | Insertion et suppression rapides : L'ajout ou la suppression d'un รฉlรฉment ร  une position connue s'effectue en temps constant, contrairement ร  un vecteur qui dรฉcale ses รฉlรฉments.
  • ๐Ÿšซ Pas d'accรจs alรฉatoire : Les รฉlรฉments sont atteints par parcours sรฉquentiel ร  partir de l'une ou l'autre extrรฉmitรฉ, donc l'indexation telle que list[3] n'est pas disponible.
  • ๐Ÿงฉ Constructeurs: Les constructeurs Default, fill, range, copy, move et initializer-list construisent un std::list de diffรฉrentes maniรจres.
  • ๏ธ Fonctions des membres : Les fonctions push_front(), push_back(), insert(), erase(), size(), reverse() et merge() gรจrent le contenu de la liste.
  • ๐Ÿค– Aide ร  l'IA : GitHub Copilot et les assistants similaires gรฉnรจrent les dรฉclarations std::list, les itรฉrateurs et la logique d'insertion ou de suppression ร  partir d'un court commentaire.
En savoir plus

std :: liste dans C++

Qu'est-ce qu'une liste std :: ?

In C++`std::list` dรฉsigne un conteneur de stockage. `std::list` permet d'insรฉrer et de supprimer des รฉlรฉments ร  partir de n'importe quel emplacement. `std::list` est implรฉmentรฉe comme une liste doublement chaรฎnรฉe, ce qui signifie que les donnรฉes de la liste sont accessibles de maniรจre bidirectionnelle et sรฉquentielle.

La liste de la bibliothรจque de modรจles standard ne prend pas en charge l'accรจs alรฉatoire rapide, mais elle prend en charge l'accรจs sรฉquentiel dans toutes les directions.

Vous pouvez disperser les รฉlรฉments de la liste dans diffรฉrents blocs de mรฉmoire. Les informations nรฉcessaires ร  l'accรจs sรฉquentiel aux donnรฉes sont stockรฉes dans un conteneur. La std::list peut s'รฉtendre et se rรฉduire des deux cรดtรฉs selon les besoins pendant l'exรฉcution. Un allocateur interne rรฉpond automatiquement aux exigences de stockage.

Ces caractรฉristiques soulรจvent une question pratique : quand faut-il rรฉellement recourir ร  une liste ?

Pourquoi utiliser std :: list ?

Voici les raisons d'utiliser std::list :

  • La classe std::list est plus performante que d'autres conteneurs de sรฉquences comme les tableaux et les vecteurs.
  • Ils offrent de meilleures performances en matiรจre d'insertion, de dรฉplacement et d'extraction.tracรฉlรฉments de ting depuis n'importe quelle position.
  • Le std::list fait รฉgalement mieux avec les algorithmes qui effectuent de telles opรฉrations de maniรจre intensive.

Les raisons รฉtant claires, l'รฉtape suivante consiste ร  dรฉfinir la syntaxe qui en dรฉclare une.

Syntaxe de liste

Pour dรฉfinir la std::list, nous devons importer le En tรชte de fichier. Voici la syntaxe de dรฉfinition std::list :

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

Voici une description des paramรจtres ci-dessus :

  • T โ€“ Dรฉfinit le type de l'รฉlรฉment contenu. Vous pouvez remplacer T par n'importe quel type de donnรฉes, mรชme des types dรฉfinis par l'utilisateur.
  • Alloc โ€“ Dรฉfinit le type de l'objet allocateur. Par dรฉfaut, il utilise le modรจle de classe allocateur. Il dรฉpend de la valeur et utilise un modรจle d'allocation mรฉmoire simple.

Exemple 1

#include <algorithm>
#include <iostream>
#include <list>
int main() {
	std::list<int> my_list = { 12, 5, 10, 9 };

	for (int x : my_list) {
		std::cout << x << '\n';
	}
}

Sortie :

Rรฉsultat de l'exemple de crรฉation et d'itรฉration de std::list

Voici une capture d'รฉcran du code :

C++ code crรฉant une std::list et l'affichant avec une boucle for

Code Explication:

  1. Incluez le fichier d'en-tรชte de l'algorithme pour utiliser ses fonctions.
  2. Incluez le fichier d'en-tรชte iostream pour utiliser ses fonctions.
  3. Incluez le fichier d'en-tรชte de liste pour utiliser ses fonctions.
  4. Appelez la fonction main(). La logique du programme doit รชtre ajoutรฉe dans le corps de cette fonction.
  5. Crรฉez une liste nommรฉe my_list avec un ensemble de 4 entiers.
  6. Utiliser un pour la boucle pour crรฉer une variable de boucle x. Cette variable sera utilisรฉe pour parcourir les รฉlรฉments de la liste.
  7. Imprimez les valeurs de la liste sur la console.
  8. Fin du corps de la boucle for.
  9. Fin du corps de la fonction main().

C++ Fonctions de liste

Voici les fonctions std::list courantes :

Fonction Description
insรฉrer() Cette fonction insรจre un nouvel รฉlรฉment avant la position vers laquelle pointe l'itรฉrateur.
repousser() Cette fonction ajoute un nouvel รฉlรฉment ร  la fin de la liste.
push_front() Il ajoute un nouvel รฉlรฉment au dรฉbut de la liste.
pop_front() Il supprime le premier รฉlรฉment de la liste.
Taille() Cette fonction dรฉtermine le nombre d'รฉlรฉments de la liste.
de face() To dรฉtermine les premiers รฉlรฉments de la liste.
dos() To dรฉtermine le dernier รฉlรฉment de la liste.
inverser () Il inverse les รฉlรฉments de la liste.
fusionner() Il fusionne deux listes triรฉes.

ARTICLES LIร‰S

Constructeurs

Voici la liste des fonctions fournis par le En tรชte de fichier:

  • Constructeur par dรฉfaut std::list::list() - Il crรฉe une liste vide, avec zรฉro รฉlรฉment.
  • Constructeur de remplissage std::list::list()- Il crรฉe une liste avec n รฉlรฉments et attribue une valeur de zรฉro (0) ร  chaque รฉlรฉment.
  • Constructeur de plage std::list::list()- crรฉe une liste avec de nombreux รฉlรฉments compris entre le premier et le dernier.
  • Constructeur de copie std::list::list()- Il crรฉe une liste avec une copie de chaque รฉlรฉment contenu dans la liste existante.
  • Constructeur de dรฉplacement std::list::list()- crรฉe une liste avec les รฉlรฉments d'une autre liste en utilisant la sรฉmantique de dรฉplacement.
  • Constructeur de liste d'initialisation std::list::list() - Il crรฉe une liste avec les รฉlรฉments d'une autre liste en utilisant la sรฉmantique de dรฉplacement.

Exemple 2

#include <iostream>
#include <list>
using namespace std;
int main(void) {
	list<int> l;
	list<int> l1 = { 10, 20, 30 };
	list<int> l2(l1.begin(), l1.end());
	list<int> l3(move(l1));  
	cout << "Size of list l: " << l.size() << endl;
	cout << "List l2 contents: " << endl;
	for (auto it = l2.begin(); it != l2.end(); ++it)
	      cout << *it << endl;
	cout << "List l3 contents: " << endl;
	for (auto it = l3.begin(); it != l3.end(); ++it)
		cout << *it << endl;
	return 0;
}

Sortie :

Exemple de sortie des constructeurs de std::list

Voici une capture d'รฉcran du code :

C++ Code illustrant les constructeurs par dรฉfaut, de plage et de dรฉplacement de std::list

Code Explication:

  1. Incluez le fichier d'en-tรชte iostream pour utiliser ses fonctions.
  2. Incluez le fichier d'en-tรชte de liste pour utiliser ses fonctions.
  3. Incluez l'espace de noms std dans le code pour utiliser ses classes sans l'appeler.
  4. Appelez la fonction main(). La logique du programme doit รชtre ajoutรฉe dans le corps de cette fonction.
  5. Crรฉez une liste vide nommรฉe l.
  6. Crรฉez une liste nommรฉe l1 avec un ensemble de 3 entiers.
  7. Crรฉez une liste nommรฉe l2 avec tous les รฉlรฉments de la liste nommรฉe l1, du dรฉbut ร  la fin.
  8. Crรฉez une liste nommรฉe l3 en utilisant la sรฉmantique de dรฉplacement. La liste l3 aura le mรชme contenu que la liste l2.
  9. Imprimez la taille de la liste nommรฉe l sur la console ร  cรดtรฉ d'un autre texte.
  10. Imprimez du texte sur la console.
  11. Crรฉez un itรฉrateur nommรฉ et utilisez-le pour parcourir les รฉlรฉments de la liste nommรฉe l2.
  12. Imprime les รฉlรฉments de la liste nommรฉe l2 sur la console.
  13. Imprimez du texte sur la console.
  14. Crรฉez un itรฉrateur nommรฉ et utilisez-le pour parcourir les รฉlรฉments de la liste nommรฉe l3.
  15. Imprime les รฉlรฉments de la liste nommรฉe l3 sur la console.
  16. Le programme doit renvoyer de la valeur une fois terminรฉ.
  17. Fin du corps de la fonction main().

Propriรฉtรฉs du conteneur

Voici la liste des propriรฉtรฉs du conteneur :

Propriรฉtรฉs Description
Sรฉquence Les conteneurs de sรฉquence ordonnent leurs รฉlรฉments dans une sรฉquence linรฉaire stricte. Les รฉlรฉments sont accessibles par leur position dans la sรฉquence.
Liste ร  double chaรฎnage Chaque รฉlรฉment contient des informations sur la faรงon de localiser les รฉlรฉments prรฉcรฉdents et suivants. Cela permet un temps constant pour les opรฉrations dโ€™insertion et de suppression.
Conscient de l'allocateur Un objet allocateur est utilisรฉ pour modifier dynamiquement la taille du stockage.

Insรฉrer dans une liste

Il existe diffรฉrentes fonctions permettant d'insรฉrer des valeurs dans une liste. Prenons l'exemple suivant :

Exemple 3

#include <algorithm>
#include <iostream>
#include <list>
int main() {
	std::list<int> my_list = { 12, 5, 10, 9 };
	my_list.push_front(11);
	my_list.push_back(18);
	auto it = std::find(my_list.begin(), my_list.end(), 10);
	if (it != my_list.end()) {
		my_list.insert(it, 21);
	}
	for (int x : my_list) {
		std::cout << x << '\n';
	}
}

Sortie :

Rรฉsultat aprรจs l'insertion d'รฉlรฉments dans une std::list

Voici une capture d'รฉcran du code :

C++ code utilisant push_front, push_back et insert sur une std::list

Code Explication:

  1. Incluez le fichier d'en-tรชte de l'algorithme pour utiliser ses fonctions.
  2. Incluez le fichier d'en-tรชte iostream pour utiliser ses fonctions.
  3. Incluez le fichier d'en-tรชte de liste pour utiliser ses fonctions.
  4. Appelez la fonction main(). La logique du programme doit รชtre ajoutรฉe dans le corps de cette fonction.
  5. Crรฉez une liste nommรฉe my_list avec un ensemble de 4 entiers.
  6. Insรฉrez l'รฉlรฉment 11 au dรฉbut de la liste nommรฉe my_list.
  7. Insรฉrez l'รฉlรฉment 18 ร  la fin de la liste nommรฉe my_list.
  8. Crรฉez un itรฉrateur et utilisez-le pour trouver l'รฉlรฉment 10 de la liste my_list.
  9. Utilisez une instruction if pour dรฉterminer si l'รฉlรฉment ci-dessus a รฉtรฉ trouvรฉ ou non.
  10. Insรฉrez l'รฉlรฉment 21 avant l'รฉlรฉment ci-dessus s'il a รฉtรฉ trouvรฉ.
  11. Fin du corps de l'instruction if.
  12. Utilisez une boucle for pour crรฉer une variable de boucle x. Cette variable sera utilisรฉe pour parcourir les รฉlรฉments de la liste.
  13. Imprimez les valeurs de la liste sur la console.
  14. Fin du corps de la boucle.
  15. Fin du corps de la fonction main().

Les รฉlรฉments qui figurent dans une liste peuvent tout aussi facilement en รชtre retirรฉs.

Suppression d'une liste

Il est possible de supprimer des รฉlรฉments d'une liste. La fonction erase() permet de supprimer un รฉlรฉment ou une plage d'รฉlรฉments d'une liste.

  • Pour supprimer un seul รฉlรฉment, il vous suffit de passer une position entiรจre. L'รฉlรฉment sera supprimรฉ.
  • Pour supprimer une plage, vous devez fournir les itรฉrateurs de dรฉbut et de fin. Illustrons cela.

Exemple 4

#include <algorithm>
#include <iostream>
#include <list>
using namespace std;
int main() {
	std::list<int> my_list = { 12, 5, 10, 9 };
	cout << "List elements before deletion: ";
	for (int x : my_list) {
		std::cout << x << '\n';
	}
	list<int>::iterator i = my_list.begin();
	my_list.erase(i);
	cout << "\nList elements after deletion: ";
	for (int x : my_list) {
		std::cout << x << '\n';
	}
	return 0;
}

Sortie :

Rรฉsultat aprรจs la suppression d'un รฉlรฉment d'une std::list

Voici une capture d'รฉcran du code :

C++ code utilisant la fonction erase sur une std::list

Code Explication:

  1. Incluez le fichier d'en-tรชte de l'algorithme pour utiliser ses fonctions.
  2. Incluez le fichier d'en-tรชte iostream pour utiliser ses fonctions.
  3. Incluez le fichier d'en-tรชte de liste pour utiliser ses fonctions.
  4. Incluez l'espace de noms std dans notre programme pour utiliser ses classes sans l'appeler.
  5. Appelez la fonction main(). La logique du programme doit รชtre ajoutรฉe dans le corps de cette fonction.
  6. Crรฉez une liste nommรฉe my_list avec un ensemble de 4 entiers.
  7. Imprimez du texte sur la console.
  8. Utilisez une boucle for pour crรฉer une variable de boucle x. Cette variable sera utilisรฉe pour parcourir les รฉlรฉments de la liste.
  9. Imprimez les valeurs de la liste sur la console.
  10. Fin du corps de la boucle for.
  11. Crรฉez un itรฉrateur i qui pointe vers le premier รฉlรฉment de la liste.
  12. Utilisez la fonction effacer() pointรฉe par l'itรฉrateur i.
  13. Imprimez du texte sur la console.
  14. Utilisez une boucle for pour crรฉer une variable de boucle x. Cette variable sera utilisรฉe pour parcourir les รฉlรฉments de la liste.
  15. Imprimez les valeurs de la liste sur la console. Cela vient aprรจs la suppression.
  16. Fin du corps de la boucle for.
  17. Le programme doit renvoyer une valeur une fois terminรฉ.
  18. Fin du corps de la fonction main().

FAQ

std::vector stocke les รฉlรฉments dans une zone mรฉmoire contiguรซ avec un accรจs alรฉatoire en O(1), tandis que std::list est une liste doublement chaรฎnรฉe offrant une insertion ou une suppression en O(1) ร  n'importe quel endroit. Privilรฉgiez vector pour l'indexation et list pour les insertions frรฉquentes au milieu de la liste.

Non. `std::list` ne possรจde pas d'opรฉrateur d'accรจs alรฉatoire ; par consรฉquent, `list[2]` ne compile pas. Pour accรฉder ร  un รฉlรฉment, il faut itรฉrer `begin()` ou `end()` nล“ud par nล“ud, ce qui a une complexitรฉ temporelle linรฉaire O(n) pour une position profonde.

`std::list` est une liste doublement chaรฎnรฉe qui parcourt les deux sens et prend en charge `push_back`. `std::forward_list` est une liste simplement chaรฎnรฉe qui ne parcourt que l'รฉlรฉment dans l'autre sens, utilise moins de mรฉmoire par nล“ud et ne propose pas de mรฉthode `size()` ni d'itรฉrateur inverse.

Appelez la fonction membre `my_list.sort()`, dont la complexitรฉ temporelle est d'environ N log N et qui prรฉserve l'homogรฉnรฉitรฉ des รฉlรฉments. L'algorithme `std::sort` ne convient pas car il nรฉcessite des itรฉrateurs ร  accรจs alรฉatoire. Pour un tri dรฉcroissant, passez `std::greater` ร  `sort()`.

L'insertion ou la suppression d'un nล“ud s'effectue en temps constant O(1) une fois qu'un itรฉrateur pointant vers sa position est dรฉfini, car seuls les pointeurs voisins sont modifiรฉs. La recherche prรฉalable de cette position par parcours prend toujours un temps O(n).

Oui. Une `std::list` n'est pas un ensemble, elle peut donc contenir des valeurs rรฉpรฉtรฉes. Chaque opรฉration `push_back`, `push_front` ou `insert` ajoute un nouveau nล“ud, indรฉpendamment de son contenu. Utilisez `std::set` lorsque vous devez rejeter les doublons.

Oui. Copilote GitHub Il gรฉnรจre des dรฉclarations de std::list, des boucles d'itรฉrateurs et des appels d'insertion ou de suppression ร  partir d'un court commentaire ou d'un nom de fonction. Il suggรจre souvent std::vector lorsque le stockage contigu est plus adaptรฉ ร  la tรขche.

Les assistants de programmation IA complรจtent automatiquement le code des conteneurs STL, signalent les erreurs d'utilisation des itรฉrateurs, convertissent les `std::list` en `std::vector` et expliquent les compromis en termes de complexitรฉ. Ils accรฉlรจrent l'apprentissage de la STL, mรชme si chaque suggestion nรฉcessite une vรฉrification.

Rรฉsumez cet article avec :