Deque<T>

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.


Eficiencia

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

Especificación

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);
    

Requisitos


Ejercicios

  1. Crea un programa que utilice deque<T>
  2. Escribe un programa que pruebe la eficiencia de vector<T> y deque<T> respecto a los arrays de C