Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

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

Sources