Double ended queue
deque (usually pronounced like "deck") is an irregular acronym of double-ended queue. Double-ended queues are a kind of sequence containers. As such, their elements are ordered following a strict linear sequence.
Deques may be implemented by specific libraries in different ways, but in all cases they allow for the individual elements to be accessed through random access iterators, with storage always handled automatically (expanding and contracting as needed).
Deque sequences have the following properties:
- Individual elements can be accessed by their position index.
- Iteration over the elements can be performed in any order.
- Elements can be efficiently added and removed from any of its ends (either the beginning or the end of the sequence).
Therefore they provide a similar functionality as the one provided by vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence and not only at its end. On the drawback side, unlike vectors, deques are not granted to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics.
Both vectors and deques provide thus a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors are very similar to a plain array that grows by reallocating all of its elements in a unique block when its capacity is exhausted, the elements of a deques can be divided in several chunks of storage, with the class keeping all this information and providing a uniform access to the elements. Therefore, deques are a little more complex internally, but this generally allows them to grow more efficiently than the vectors with their capacity managed automatically, specially in large sequences, because massive reallocations are avoided.
For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists.
In their implementation in the C++ Standard Template Library, deques take two template parameters:
template < class T, class Allocator = allocator<T> > class vector;
|
Where the template parameters have the following meanings:
- T: Type of the elements.
- Allocator: Type of the allocator object used to define the storage allocation model. By default, the allocator class template for type T is used, which defines the simplest memory allocation model and is value-independent.
In the reference for the deque member functions, these same names are assumed for the template parameters.
Member functions
| operator= | Copy container content (public member function) |
Iterators:
| begin | Return iterator to beginning (public member function) |
| end | Return iterator to end (public member function) |
| rbegin | Return reverse iterator to reverse beginning (public member function) |
| rend | Return reverse iterator to reverse end (public member function) |
Capacity:
| size | Return size (public member function) |
| max_size | Return maximum size (public member function) |
| resize | Change size (public member functions) |
| empty | Test whether container is empty (public member function) |
Element access:
| operator[] | Access element (public member function) |
| at | Access element (public member function) |
| front | Access first element (public member function) |
| back | Access last element (public member function) |
Modifiers:
| assign | Assign container content (public member function) |
| push_back | Add element at the end (public member function) |
| push_front | Insert element at beginning (public member function) |
| pop_back | Delete last element (public member function) |
| pop_front | Delete first element (public member function) |
| insert | Insert elements (public member function) |
| erase | Erase elements (public member function) |
| swap | Swap content (public member function) |
| clear | Clear content (public member function) |
Allocator:
Member types
of
template <class T, class Allocator=allocator<T> > class deque;
| member type | definition |
|---|
| reference | Allocator::reference |
| const_reference | Allocator::const_reference |
| iterator | Random access iterator |
| const_iterator | Constant random access iterator |
| size_type | Unsigned integral type (usually same as size_t) |
| difference_type | Signed integral type (usually same as ptrdiff_t) |
| value_type | T |
| allocator_type | Allocator |
| pointer | Allocator::pointer |
| const_pointer | Allocator::const_pointer |
| reverse_iterator | reverse_iterator<iterator> |
| const_reverse_iterator | reverse_iterator<const_iterator> |
