The Standard Template Library (STL) sequence container deque arranges elements of a given type in a linear arrangement and, like vectors, allow fast random access to any element and efficient insertion and deletion at the back of the container. However, unlike a vector, the deque class also supports efficient insertion and deletion at the front of the container.
template < class Type, class Allocator=allocator<Type> > class deque
- The element data type to be stored in the deque.
- The type that represents the stored allocator object that encapsulates details about the deque's allocation and deallocation of memory. This argument is optional, and the default value is allocator<Type>.
The choice of container type should be based in general on the type of searching and inserting required by the application. Vectors should be the preferred container for managing a sequence when random access to any element is at a premium and insertions or deletions of elements are only required at the end of a sequence. The performance of the list container is superior when efficient insertions and deletions (in constant time) at any location within the sequence is at a premium. Such operations in the middle of the sequence require element copies and assignments proportional to the number of elements in the sequence (linear time).
Deque reallocation occurs when a member function must insert or erase elements of the sequence:
- If an element is inserted into an empty sequence, or if an element is erased to leave an empty sequence, then iterators earlier returned by begin and end become invalid.
- If an element is inserted at the first position of the deque, then all iterators, but no references, that designate existing elements become invalid.
- If an element is inserted at the end of the deque, then end and all iterators, but no references, that designate existing elements become invalid.
- If an element is erased at the front of the deque, only that iterator and references to the erased element become invalid.
- If the last element is erased from the end of the deque, only that iterator to the final element and references to the erased element become invalid.
Otherwise, inserting or erasing an element invalidates all iterators and references.