C++ Double-ended Queues

Double-ended queues (or deques) are similar to vectors, except that they allow fast insertions and deletions at both the beginning and the end of the container.

C++ deques are commonly implemented as dynamically allocated arrays that can grow at both ends. This guarantees constant time access, amortized constant time insertion and deletion at either end of the deque, and linear time insertion and deletion from the middle of the deque.

Constructorscreate deques and initialize them with some data
Operatorscompare, assign, and access elements of a deque
assignassign elements to a deque
atreturns an element at a specific location
backreturns a reference to last element of a deque
beginreturns an iterator to the beginning of the deque
clearremoves all elements from the deque
emptytrue if the deque has no elements
endreturns an iterator just past the last element of a deque
eraseremoves elements from a deque
frontreturns a reference to the first element of a deque
insertinserts elements into the deque
max_sizereturns the maximum number of elements that the deque can hold
pop_backremoves the last element of a deque
pop_frontremoves the first element of the deque
push_backadd an element to the end of the deque
push_frontadd an element to the front of the deque
rbeginreturns a reverse_iterator to the end of the deque
rendreturns a reverse_iterator to the beginning of the deque
resizechange the size of the deque
sizereturns the number of items in the deque
swapswap the contents of this deque with another

Notes

The name deque is pronounced “deck”, and stands for “double-ended queue.” Knuth reports that the name was coined by E. J. Schweppe. See section 2.2.1 of Knuth for more information about deques. (D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms, second edition. Addison-Wesley, 1973.)