CKTIS / C++
std::deque : file à deux extrémités avec accès aléatoire
std::deque offre des opérations rapides aux deux extrémités et l’accès aléatoire, mais ne garantit pas un tampon contigu unique pour tous ses éléments.
Version : C++23
Syntaxe
template<class T, class Allocator = std::allocator<T>>
class deque;
void push_front(const T& value);
void push_back(const T& value);
void pop_front();
void pop_back();std::deque<T> de <deque> est un conteneur séquentiel à itérateurs random access. Insérer ou effacer un élément à l’une des extrémités prend un temps constant, tandis qu’une opération au milieu est linéaire. Contrairement à std::vector, les éléments ne sont pas nécessairement contigus ; &d[0] n’est donc pas le début d’un tableau couvrant toute la deque.
Une insertion au milieu invalide tous les itérateurs et références. Une insertion à une extrémité invalide tous les itérateurs mais préserve les références aux éléments existants. Effacer le dernier élément invalide l’itérateur past-the-end et les accès aux éléments supprimés ; effacer le premier mais pas le dernier ne touche que les éléments supprimés, tandis qu’un effacement central invalide tout. Ainsi, pop_front() sur une deque d’un élément efface aussi le dernier élément et invalide end().
operator[] ne contrôle pas l’indice, alors que at() lance std::out_of_range. front(), back() et pop_* exigent un conteneur non vide. Le traitement fréquent des deux extrémités est l’usage naturel ; pour un bloc contigu ou des itérateurs stables après ajout, il faut reconsidérer le conteneur.
Exemples
#include <deque>
#include <iostream>
int main() {
std::deque<int> values;
values.push_back(2);
values.push_back(3);
values.push_front(1);
values.pop_back();
std::cout << values.size() << ' ' << values.front() << ' ' << values.back() << '\n';
}
Résultat
2 1 2
std::deque → 2 1 2