Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité
Introduction et syntaxe de base
Pointeurs et fonctions
Programmation OO
Structures de données
La bibliothèque standard (STL)

La classe deque en C++ ( Bibliothèque STL)

 

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
                

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.