Une deque (double ended queue — file à deux bouts) est un conteneur de séquence qui permet l'expansion et la contraction aux deux extrémités. Définie dans l'en-tête <deque>, elle est similaire à vector mais avec des insertions et suppressions efficaces en tête et en queue.
Mémoire non contiguë Contrairement à
vector, la deque ne garantit pas une allocation mémoire contiguë. Cela lui permet de s'étendre aux deux extrémités sans recopier tout le contenu, mais la rend moins efficace que vector lorsqu'on n'a pas besoin d'insertions en tête.| Opération | vector | deque |
|---|---|---|
| Insertion/suppression en fin | O(1) amorti | O(1) amorti |
| Insertion/suppression en tête | O(n) | O(1) amorti |
| Insertion/suppression au milieu | O(n) | O(n) |
| Accès aléatoire | O(1) | O(1) |
| Mémoire contiguë | Oui | Non garantie |
Construction
deque<T> deq; // Conteneur vide
deque<T> deq(n, valeur); // n copies de valeur
deque<T> deq(debut, fin); // Copie de la plage [debut, fin)
deque<T> deq(autreDeque); // Copie d'une autre deque
deque<T> deq = autreDeque; // Opérateur d'affectationInsertion
deq.push_back(val); // Ajouter en fin
deq.push_front(val); // Ajouter en tête
// insert — retourne un itérateur vers le 1er élément inséré
deq.insert(position, val); // 1 élément avant position
deq.insert(position, n, val); // n copies de val
deq.insert(position, premier, dernier); // plage [premier, dernier)
deq.insert(position, liste); // liste d'initialisationTaille
deq.size(); // Taille actuelle
deq.max_size(); // Taille maximale supportée
deq.resize(n, val); // Redimensionner (val optionnel pour les nouveaux éléments)
deq.empty(); // true si videAccès aux éléments
deq.front(); // Premier élément
deq.back(); // Dernier élément
deq[i]; // Élément à l'indice i (sans vérification des bornes)
deq.at(i); // Élément à l'indice i (avec vérification — lève une exception)Suppression
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 la plage [premier, dernier)
deq.clear(); // Supprimer tous les élémentsArguments itérateurs Les arguments
premier et dernier dans erase et insert sont des itérateurs. La borne dernier est toujours exclue de la plage traitée.Exemple complet
#include <iostream>
#include <string>
#include <deque>
using namespace std;
void afficher(deque<string> deq) {
for (int i = 0; i < deq.size(); i++)
cout << deq.at(i) << " ";
cout << endl;
}
int main() {
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"); // insère en tête
cout << "Taille : " << etd.size() << endl;
cout << "Taille max : " << etd.max_size() << endl;
cout << "Liste des étudiants : " << endl;
afficher(etd);
cout << '\n';
// Insertion à la position it+2
deque<string>::iterator it = etd.begin();
etd.insert(it + 2, "Dounia");
cout << "Après insertion de Dounia : " << endl;
afficher(etd);
cout << '\n';
cout << "Premier élément : " << etd.front() << endl;
cout << "Dernier élément : " << etd.back() << endl;
cout << "3ème élément : " << etd.at(2) << endl;
cout << '\n';
etd.pop_front();
etd.pop_back();
cout << "Après suppression du premier et dernier : " << endl;
afficher(etd);
cout << '\n';
it = etd.begin();
deque<string>::iterator premier = it + 1; // Omar
deque<string>::iterator dernier = it + 3; // Sara (exclu)
etd.erase(premier, dernier);
cout << "Après suppression entre Omar et Sara : " << endl;
afficher(etd);
return 0;
}Sortie
Taille : 6 Taille max : 288230376151711743 Liste des étudiants : Alex Mostafa Omar Sara Mohamed Moneim Après insertion de Dounia : Alex Mostafa Dounia Omar Sara Mohamed Moneim Premier élément : Alex Dernier élément : Moneim 3ème élément : Dounia Après suppression du premier et dernier : Mostafa Dounia Omar Sara Mohamed Après suppression entre Omar et Sara : Mostafa Sara Mohamed
Application — Rotation de liste
La deque est naturellement adaptée à la rotation : faire avancer ou reculer cycliquement tous les éléments d'une position.
Principe de la rotation
- Rotation horaire (vers l'arrière) : retirer l'élément de tête et l'insérer en queue —
push_back(front())puispop_front(). - Rotation anti-horaire (vers l'avant) : retirer l'élément de queue et l'insérer en tête —
push_front(back())puispop_back().
#include <iostream>
#include <string>
#include <deque>
using namespace std;
void afficher(deque<string> deq) {
for (int i = 0; i < deq.size(); i++)
cout << deq.at(i) << " ";
cout << endl;
}
int main() {
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 << "Liste initiale : " << endl;
afficher(etd);
cout << '\n';
// Rotation horaire (tête → queue)
etd.push_back(etd.front());
etd.pop_front();
cout << "Après rotation horaire : " << endl;
afficher(etd);
cout << '\n';
// Rotation anti-horaire (queue → tête)
etd.push_front(etd.back());
etd.pop_back();
cout << "Après rotation anti-horaire : " << endl;
afficher(etd);
return 0;
}Sortie
Liste initiale : Alex Mostafa Omar Sara Mohamed Moneim Après rotation horaire : Mostafa Omar Sara Mohamed Moneim Alex Après rotation anti-horaire : Alex Mostafa Omar Sara Mohamed Moneim
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.