std::deque

H συγκεκριμένη κλάση περιγράφει ένα double-ended queue, δηλαδή μία ουρά η οποία επιδέχεται γρήγορης εισαγωγής και διαγραφής στοιχείων στην αρχή και στο τέλος της. Η διπλοουρά είναι δομή ανάλογη με τη δομή vector ως προς τον τρόπο που την διαχειριζόμαστε προγραμματιστικά. Η βασική διαφορά από τη vector είναι ότι επιτρέπει την γρήγορη ένθεση και διαγραφή όχι μόνο στο τέλος, αλλά και στην αρχή της δομής. Για τον λόγο αυτό, εκτός από τις συναρτήσεις push_back και pop_back, παρέχει και τις συναρτήσεις push_front και pop_front για ένθεση και διαγραφή ενός στοιχείου από την αρχή της ουράς.

Όσον αφορά την εσωτερική υλοποίηση της deque αυτή είναι αρκετά διαφορετική σε σχέση με το vector. Κατά κανόνα, αποτελείται από ένα σύνολο πινάκων οι οποίοι δεσμεύονται διακριτά μεταξύ τους, καθώς αυξάνονται οι ανάγκες αποθήκευσης περιεχομένου στη δομή. Επιπλέον, διαθέτει ένα πίνακα δεικτών που χρησιμεύει στη διαχείριση των επιμέρους πινάκων που αποτελούν το περιεχόμενο της δομής και του δείκτες begin και end που προσδιορίζουν την αρχή και το τέλος των περιεχομένων (δες το παρακάτω ενδεικτικό σχήμα). Η δομή υποστηρίζει Random Access Iterators, όπως και ο container vector.

• Η πράξη της ένθεσης ή της διαγραφής από την αρχή ή από το τέλος του πίνακα έχει σταθερό κόστος (O(1)).
• Η πράξη της ένθεσης ή της διαγραφής από το μέσο του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται αριστερότερα ή δεξιότερα κατά μία θέση και η επίδοσης τη εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με την αρχή ή το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα (Ο(Ν)).
• Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα (Ο(Ν)).
• Η πρόσβαση στο i-στο στοιχείο της δομής έχει σταθερό κόστος Ο(1).