Menu

Listes dans STL

lists stl

Essayez Notre Instrument Pour Éliminer Les Problèmes

Apprenez à tout savoir sur les listes de la STL et leur mise en œuvre.

Les listes sont des conteneurs séquentiels. Les listes contiennent des éléments dans des emplacements non contigus. Nous avons discuté des tableaux et des vecteurs dans nos précédents tutoriels.

Dans le cas des conteneurs de tableaux et de vecteurs, comme ces conteneurs stockent des données dans une mémoire contiguë, l'opération d'insertion au milieu de ces conteneurs s'avère très coûteuse car nous devons déplacer les éléments existants en conséquence pour faire de la place pour le nouvel élément.

=> Voir ici pour explorer la liste complète des didacticiels C ++.

Listes dans STL

c ++ par rapport à java

Ce que vous apprendrez:

Aperçu

La liste est un conteneur qui surmonte cet inconvénient des conteneurs de tableaux et de vecteurs. Cela nous permet d'insérer des éléments n'importe où dans la liste sans causer beaucoup de surcharge. Mais les listes sont plus lentes que les vecteurs en ce qui concerne la traversée.

Dans ce tutoriel, nous verrons l'implémentation des listes en STL ainsi que les différentes opérations de traversée, de manipulations et d'accès aux listes avec des exemples.

Notez que la majorité des opérations de liste sont similaires à celles des vecteurs et que les lecteurs qui ont déjà lu notre tutoriel sur les vecteurs n'auront donc pas de problèmes pour interpréter les concepts de liste.

Déclaration et initialisation

Pour implémenter le conteneur de liste et utiliser tous ses avantages, nous devons inclure un fichier d'en-tête dans notre programme.

#include

La déclaration générale du conteneur de liste est

std::list listName;

Par exemple,nous pouvons déclarer une liste nommée «mylist» de type int comme suit:

std::list mylist;

Nous pouvons également initialiser la liste au moment de la déclaration ou y ajouter des éléments en utilisant l'une des opérations qu'elle prend en charge.

Voyons comment nous pouvons initialiser la liste que nous avons créée ci-dessus.

std::list mylist = {1, 1, 2, 3, 5};

L'initialisation ci-dessus sera mise en mémoire comme indiqué ci-dessous:

Déclaration et initialisation

Une fois que nous initialisons la liste, nous pouvons accéder aux éléments d'une liste à l'aide d'un itérateur. Les fonctions Iterator «begin» et «end» nous aident à parcourir les éléments de la liste.

Noter: L'itérateur pour la liste prend également en charge d'autres itérateurs tels que les itérateurs inverses (rbegin, rend), les itérateurs constants (cbegin, cend) et les itérateurs inverses constants (crbegin, crend) et peut être utilisé de la même manière que les vecteurs.

L'exemple suivant le montre.

#include #include #include #include using namespace std; int main() { list mylist = {1, 1, 2, 3, 5}; cout<<”List elements are: “; list::iterator it; for(it=mylist.begin();it!=mylist.end();++it) cout<<*it<<” “; }

Production:

Les éléments de la liste sont: 1 1 2 3 5

Ainsi dans l'exemple ci-dessus, nous avons déclaré une liste de la séquence de Fibonacci. Ensuite, nous déclarons un itérateur du même type que list puis en utilisant la boucle for, nous imprimons le contenu de la liste du début à la fin.

Passons maintenant aux opérations ou fonctions que nous fournit le conteneur de liste dans STL.

Opérations de liste

  • Insérer: Utilisé pour insérer un élément à la position donnée. Renvoie un itérateur pointant vers le premier élément inséré.

insert (pos, num_elem, elem)

Où,

pos => Position à laquelle les nouveaux éléments doivent être insérés.
num_elem => Nombre d'éléments à insérer; la valeur par défaut est 1.
item => Valeur réelle à insérer.

Comprenons la fonction d'insertion en prenant un exemple.

#include #include // for list operations using namespace std; int main() { list mylist = {1,1,2}; list::iterator it = mylist.begin(); // iterator to point to 4th position advance(it,` 3); // inserts 3 at 4th position mylist.insert(it, 3); cout << 'The list after inserting' << ' 1 element using insert() is : '; for (list::iterator i = mylist.begin();i != mylist.end();i++) cout << *i << ' '; cout << endl; }

Production:

La liste après avoir inséré 1 élément en utilisant insert () est: 1 1 2 3

Ceci est un exemple pour insérer un seul élément au 4eposition dans la liste qui est finalement la dernière position. D'abord, nous avons une liste pour laquelle nous avons défini l'itérateur pointant vers le début de la liste. Ensuite, nous déplaçons cet itérateur vers le 4eposition, puis appelez insert pour insérer 1 élément.

Nous pouvons également insérer plus d'un élément, en spécifiant le deuxième paramètre dans la fonction d'insertion. Chaque fois qu'il n'est pas spécifié, la valeur par défaut est 1.

  • repousser :Ajoute un nouvel élément à la fin de la liste.
  • push_front :Ajoute un nouvel élément au début de la liste.

Voyons un exemple qui montre l'utilisation des fonctions push_back et push_front.

#include #include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3}; cout<<'List elements are: '; printlist(mylist); mylist.push_front(0); mylist.push_back(5); cout<<' List contents after push_front and push_back: '; printlist(mylist); }

Production:

Les éléments de la liste sont: 1 1 2 3

Contenu de la liste après push_front et push_back: 0 1 1 2 3 5

Dans cet exemple, nous créons et listons d'abord les deux éléments, un chacun à l'avant et à l'arrière en utilisant respectivement les fonctions push_front et push_back. La sortie affiche la liste modifiée une fois les deux fonctions exécutées.

  • pop_back :Supprime le dernier élément de la liste, réduisant ainsi la taille de la liste de 1.
  • pop_front :Supprime le premier élément de la liste, réduisant ainsi la taille de la liste de 1.

L'exemple suivant montre l'utilisation des opérations pop_back et pop_front de la liste.

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); mylist.pop_front(); mylist.pop_back(); cout<<' List contents after push_front and push_back: '; printlist(mylist); }

Production:

Les éléments de la liste sont: 1 1 2 3 5

Liste du contenu après push_front et push_back: 1 2 3

Comme décrit dans la définition des opérations, chacune des opérations pop_front et pop_back supprime l'élément de l'avant et de l'arrière de la liste, c'est-à-dire respectivement le premier et le dernier élément de la liste et donc chaque fois qu'elle réduit la taille de la liste de 1.

  • Taille :Renvoie la taille de la liste, c'est-à-dire le nombre d'éléments dans la liste.
  • vider :Vérifie si la liste est vide.
  • effacer :Supprime un élément ou une plage d'éléments de la liste.
  • dégager :Supprime tous les éléments de la liste en lui donnant la taille 0.

Vous trouverez ci-dessous un exemple pour démontrer l'utilisation de toutes les fonctions ci-dessus, c'est-à-dire taille, vide, effacer et effacer.

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); cout<<'size of the list: '<

Production:

Les éléments de la liste sont: 1 1 2 3 5
taille de la liste: 5
Liste après effacement du premier élément: 1 2 3 5
Nouvelle taille de la liste: 4
taille de la liste après effacement: 0

Le programme ci-dessus démontre les quatre fonctions liées à la capacité de la liste. On voit que la taille de la liste diminue de 1 lorsque l'on efface 1 élément de la liste. Alors que lorsque nous appelons une opération d'effacement sur la liste, la taille est 0, ce qui signifie que tous les éléments de la liste sont supprimés.

  • de face :Renvoie la valeur du premier élément de la liste.
  • retour :Renvoie la valeur du dernier élément de la liste.
  • échanger :Échange le contenu d'une liste avec le contenu d'une autre liste de même taille et type.
  • sens inverse :Un algorithme qui inverse la liste.
  • Trier :Trie la liste donnée.

L'exemple ci-dessous montre l'utilisation des fonctions avant, arrière, inverse, tri et échange.

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); cout<<' Front of the list: '<

Production:

Les éléments de la liste sont: 1 1 2 3 5

Devant de la liste: 1
Retour de la liste: 5

Liste inversée: 5 3 2 1 1

Contenu de la liste impaire: 1 3 5 7 9

Après l'échange

ma liste: 1 3 5 7 9
Liste impair: 5 3 2 1 1

Dans ce code, nous imprimons d'abord les valeurs avant et arrière de la liste mylist. Ensuite, cette liste est inversée et la liste inversée est imprimée. Après cela, nous définissons une autre liste de nombres impairs qui n’est dans aucun ordre et nous appelons l’algorithme «Trier» pour trier cette liste. Ensuite, nous échangeons les deux listes à l'aide de la fonction swap et imprimons les listes échangées.

  • épissure :Cette fonction est utilisée pour transférer le contenu d'une liste vers une autre liste à une position spécifiée.

Les deux listes doivent être du même type.

épissure (position, liste);

où,

position => Position à laquelle le contenu de la liste doit être transféré.
list => Liste dont les éléments doivent être transférés.

L'exemple ci-dessous montre l'utilisation de la fonction d'épissure.

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1, 8,13}; cout<<'List elements are: '; printlist(mylist); list seclist = {2,3,5}; cout<<'list to be spliced: '; printlist(seclist); list:: iterator it = mylist.begin(); it ++; it++; mylist.splice(it,seclist); cout<<' List contents after splicing at position 2: '; printlist(mylist); }

Production:

Les éléments de la liste sont: 1 1 8 13
liste à épisser: 2 3 5

Contenu de la liste après épissage en position 2: 1 1 2 3 5 8 13

La Exemple montre que nous utilisons deux listes. Tout d'abord, l'itérateur de ma liste est déplacé vers deux positions, puis la fonction d'épissure est appelée pour transférer le contenu de la deuxième liste vers la troisième position de la première liste.

  • aller :Contrairement à la fonction d'épissure qui peut être utilisée pour transférer le contenu d'une liste à une autre à une position spécifique, l'opération de fusion fusionne directement deux listes pour former une seule liste. Pour l'opération de fusion, les deux listes doivent être triées.

Ci-dessous, un exemple illustrant la fonction de fusion.

#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << ' '; } int main() { std::list mylist = {1, 1,2,3,5,8}; list seclist = {4,6,7}; cout<<'First List: '; printlist(mylist); cout<

Production:

Première liste: 11 2 3 5 8
Deuxième liste: 4 6 7

principales questions d'entrevue java pour les novices

Contenu de la liste après la fusion de deux listes:
1 1 2 3 4 5 6 7 8

Ainsi, dans le programme ci-dessus, nous avons deux listes qui sont triées. Nous appelons l'opération de fusion sur ces deux listes. La liste résultante est une liste triée contenant les éléments des deux listes.

Conclusion

Nous sommes arrivés à la fin de ce tutoriel sur les listes en STL. Nous espérons que ce tutoriel vous aurait donné d'immenses connaissances sur les listes en STL.

=> Vérifiez ici pour voir de A à Z des didacticiels de formation C ++ ici.

lecture recommandée

^