deque<T> es un contenedor diseñado para el almacenamiento sequencial de objectos. Su nombre es una abreviatura de cola doblemente terminada (Double-Ended QUEue). Su funcionamiento es parecido al de vector<T>, pero con la ventaja adicional de poder añadir elementos al principio de forma eficiente. También es aconsejable su uso cuando el tamaño del contenedor vaya a cambiar de forma significativa.
| C array, T[] | vector<T> | deque<T> | list<T> | |
|---|---|---|---|---|
| insertar/borrar al principio | no | lineal | constante | constante |
| insertar/borrar al final | no | constante | constante | constante |
| insertar/borrar en medio | no | lineal | lineal | constante |
| acceder al primer elemento | constante | constante | constante | constante |
| acceder al último elemento | constante | constante | constante | constante |
| acceder a un elemento intermedio | constante | constante | constante | lineal |
| sobrecarga | ninguna | baja | media | alta |
template <class T, class Allocator = allocator>
class deque
{
public:
// typedefs:
typedef iterator;
typedef const_iterator;
typedef Allocator<T>::pointer pointer;
typedef Allocator<T>::reference reference;
typedef Allocator<T>::const_reference const_reference;
typedef size_type;
typedef difference_type;
typedef T value_type;
typedef reverse_iterator;
typedef const_reverse_iterator;
// allocation/deallocation:
deque();
deque(size_type n, const T& value = T());
deque(const deque<T, Allocator>& x);
template <class InputIterator> deque(InputIterator first,
InputIterator last);
~deque();
deque<T, Allocator>& operator=(const deque<T, Allocator>& x);
void swap(deque<T, Allocator>& x);
// accessors:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
size_type size() const:
size_type max_size() const;
bool empty() const;
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// insert/erase:
void push_front(const T& x);
void push_back(const T& x);
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator> void insert(iterator position,
InputIterator first,
InputIterator last);
void pop_front();
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
};
template <class T, class Allocator>
bool operator==(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
template <class T, class Allocator>
bool operator<const deque<T, Allocator>& x,
const deque<T, Allocator>& y);