std:: deque

std::deque (double-ended queue) est une séquence indexée qui permet des insertions et suppressions rapides à son début et à sa fin. De plus, l'insertion et la suppression à chaque extrémité d'un deque n'invalident jamais les pointeurs ou références vers les autres éléments.

Contrairement au std::vector , les éléments d'un deque ne sont pas stockés de manière contiguë : les implémentations typiques utilisent une séquence de tableaux de taille fixe alloués individuellement, avec une comptabilité supplémentaire, ce qui signifie que l'accès indexé à un deque doit effectuer deux déréférencements de pointeur, comparé à l'accès indexé du vector qui n'en effectue qu'un.

Le stockage d'un deque est automatiquement étendu et réduit selon les besoins. L'extension d'un deque est moins coûteuse que l'extension d'un std::vector car elle n'implique pas la copie des éléments existants vers un nouvel emplacement mémoire. En revanche, les deques ont généralement un coût mémoire minimal important ; un deque contenant un seul élément doit allouer son tableau interne complet (par exemple 8 fois la taille de l'objet sur libstdc++ 64 bits ; 16 fois la taille de l'objet ou 4096 octets, selon la valeur la plus grande, sur libc++ 64 bits).

La complexité (efficacité) des opérations courantes sur les deques est la suivante :

• Accès aléatoire - constant O(1) .
• Insertion ou suppression d'éléments à la fin ou au début - constant O(1) .
• Insertion ou suppression d'éléments - linéaire O(n) .

std::deque satisfait aux exigences de Container , AllocatorAwareContainer , SequenceContainer et ReversibleContainer .

#include <deque>
#include <iostream>
int main()
{
    // Créer un deque contenant des entiers
    std::deque<int> d = {7, 5, 16, 8};
    // Ajouter un entier au début et à la fin du deque
    d.push_front(13);
    d.push_back(25);
    // Itérer et afficher les valeurs du deque
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25