La classe deque en C++ ( Bibliothèque STL)
Une deque ou double ended queue (Queue à deux bouts en francais) est un conteneur de séquence avec la fonction d'expansion et de contraction aux deux extrémités.
La classe deque, définie dans le fichier d'en-tête <deque>, est un conteneur de séquence similaire à vecteur (vector) mais avec deux extrémités ouvertes, mais plus efficace en cas d'insertion et de suppression d'éléments. Contrairement aux vecteurs, l'allocation de mémoire contiguë peut ne pas être garantie.
Les opérations d'insertion et suppression des éléments aux deux extrémités sont rapides. Cependant, la capacité supplémentaire d'insertion au début rend une deque moins efficace qu'un vecteur, car cela nécessite que le système alloue de la mémoire supplémentaire pour étendre la deque à chaque extrémité. Cela signifie que si nous avons besoin d'une structure qui ne nécessite pas d'insertion et de suppression à l'avant, il est plus efficace d'utiliser un vecteur qu'une deque. L'insertion et suppression au milieu d'une deque présentent la même inefficacité que dans le cas d'un vecteur.
Construit un objet conteneur deque, en initialisant son contenu dépend de la version du constructeur utilisée :
deque <T> deq; // Construit un conteneur vide, sans éléments. deque <T> deq (n , valeur); // Construit un conteneur avec n éléments. Chaque élément est une copie de val (si fourni). deque <T> deq [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. deque <T> deq (autreDeque); // Construit un conteneur avec une copie de chacun des éléments de autreDeque, dans le même ordre. deque <T> vec = autreDeque; // opérateur d'affectation
Insertion
Le conteneur deque 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.
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 deque .
void push_back (const value_type& val);
Ajoute un nouvel élément à la fin du conteneur deque, 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 deque, juste avant son premier élément actuel. Le contenu de val est copié dans l'élément inséré.
Taille
La classe deque a quatre fonctions membres liées à la taille d'une deque.
deq.size(); // Renvoie la taille actuelle deq.max_size(); // Renvoie la taille maximale deq.resize(n, valeur); // Redimensionner la deque deq.empty(); // Renvoie true si la deque est vide
Accéder aux éléments
La classe deque fournit les fonctions membres suivantes pour accéder aux éléments déjà présents dans la deque.
deq.front(); // Accéder au premier élément deq.back(); // Accéder au dernier élément deq[i]; // Accéder à l'élément à l'indice i deq.at(i); // Accéder à l'élément à l'indice i
Suppression
La classe deque définit plusieurs fonctions membres pour la suppression d'un ou plusieurs éléments dans le conteneur.
deq.pop_back(); // Supprimer le dernier élément deq.pop_front(); // Supprimer le premier élément deq.erase(pos); // Supprimer l'élément pointé par pos deq.erase(premier, dernier); // Supprimer les éléments de la plage [premier, dernier) ; le dernier est exclu deq.clear(); // Supprimer tous les éléments
Les arguments premier et dernier sont des itérateurs.
Exemple complet
#include<iostream> #include<string> #include<deque> // classe deque (conteneur) using namespace std; void afficher(deque <string> deq) { for (int i = 0; i < deq.size (); i++) { cout << deq.at(i) << " "; } cout << endl; } int main ( ){ // définir une deque deque<string> etd; etd.push_back("Mostafa"); etd.push_back("Omar"); etd.push_back("Sara"); etd.push_back("Mohamed"); etd.push_back("Moneim"); etd.push_front("Alex"); cout<< "La taille est : "<< etd.size()<<endl; cout<< "La taille maximale est : "<< etd.max_size()<<endl; // afficher les éléments deque<string>::iterator it = etd.begin(); cout<< "Voici la liste des etudiants : "<<endl; afficher(etd); cout<< '\n'; it=etd.begin(); etd.insert(it+2, "Dounia"); // insérer Dounia deux pas après l'élément pointé par l'itérateur it. cout<< '\n'; it=etd.begin(); cout<< "Voici la liste des etudiants apres insertion : "<<endl; afficher(etd); cout<< '\n'; cout<< '\n'; cout<< "Le premier element est : "<< etd.front() <<endl; cout<< "Le dernier element est : "<< etd.back() <<endl; cout<< "Le 3eme element est : "<< etd.at(2) <<endl; cout<< '\n'; cout<< '\n'; etd.pop_front(); // Supprimer le premier element etd.pop_back(); // Supprimer le dernier element it=etd.begin(); cout<< "Voici la liste des etudiants apres suppression du premier et dernier element : "<<endl; afficher(etd); cout<< '\n'; cout<< '\n'; it=etd.begin(); deque<string>::iterator premier,dernier; // itérateurs à accès aléatoire premier=it+1; // pointer sur le 2eme element (Omar) dernier=it+3; // pointer sur le 4eme element (Sara) etd.erase(premier,dernier); // supprimer les éléments entre Omar et Sara (exclure) cout<< "Voici la liste des etudiants apres suppression des éléments entre Omar et Sara : "<<endl; afficher(etd); return 0; }
Résultat
La taille est : 6 La taille maximale est : 288230376151711743 Voici la liste des etudiants : Alex Mostafa Omar Sara Mohamed Moneim Voici la liste des etudiants apres insertion : Alex Mostafa Dounia Omar Sara Mohamed Moneim Le premier element est : Alex Le dernier element est : Moneim Le 3eme element est : Dounia Voici la liste des etudiants apres suppression du premier et dernier element : Mostafa Dounia Omar Sara Mohamed Voici la liste des etudiants apres suppression des éléments entre Omar et Sara : Mostafa Sara Mohamed
Application
La classe deque peut être utilisée dans toute application qui nécessite une insertion et une suppression aux deux extrémités. Une application qui utilise normalement une deque est la rotation, dans laquelle nous avons une liste de éléments de données que nous voulons faire une rotation n fois. Pour effectuer une rotation dans le sens des aiguilles d'une montre, il faut retirer un élément de l'arrière et l'insérer à l'avant ; pour effectuer une rotation dans le sens inverse des aiguilles d'une montre, il faut retirer un élément de l'avant et l'insérer à l'arrière.
Solution
#include<iostream> #include<string> #include<deque> // classe deque (conteneur) using namespace std; void afficher(deque <string> deq) { for (int i = 0; i < deq.size (); i++) { cout << deq.at(i) << " "; } cout << endl; } int main ( ){ // définir une deque deque<string> etd; etd.push_back("Mostafa"); etd.push_back("Omar"); etd.push_back("Sara"); etd.push_back("Mohamed"); etd.push_back("Moneim"); etd.push_front("Alex"); // afficher les éléments deque<string>::iterator it = etd.begin(); cout<< "Voici la liste des etudiants : "<<endl; afficher(etd); cout<< '\n'; // Effectuer une rotation dans le sens des aiguilles d'une montre d'un élément etd.push_back(etd.front()); etd.pop_front(); cout<< "Voici la liste des etudiants apres la premiere rotation : "<<endl; afficher(etd); cout<< '\n'; // Effectuer une rotation dans le sens inverse des aiguilles d'une montre d'un élément etd.push_front(etd.back()); etd.pop_back(); cout<< "Voici la liste des etudiants apres la 2eme rotation : "<<endl; afficher(etd); return 0; }
Résultat
Voici la liste des etudiants : Alex Mostafa Omar Sara Mohamed Moneim Voici la liste des etudiants apres la premiere rotation : Mostafa Omar Sara Mohamed Moneim Alex Voici la liste des etudiants apres la 2eme rotation : Alex Mostafa Omar Sara Mohamed Moneim