inicio GeNeura cursos

List<T>

El contenedor list<T> utiliza una lista doblemente enlazada para almacenar sus elementos. Su principal ventaja es la eficiencia de las operaciones de inserción y borrado, independientemente de la posición de la lista en la que se realicen. Como aspectos negativos podemos destacar dos: no podemos acceder a sus elementos de forma aleatoria, y el costo de las operaciones básicas es sensiblemente mayor que con los otros tipos de contenedores.


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 list
{
  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:

    list();
    list(size_type n, const T& value = T());
    template <class InputIterator> list(InputIterator first, 
                                        InputIterator last);
    list(const list<T, Allocator>& x);
    ~list();
    list<T, Allocator>& operator=(const list<T, Allocator>& x);
    void swap(list<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();
    bool empty() const;
    size_type size() const;
    size_type max_size() 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):

  // special mutative operations on list:

    void splice(iterator position, list<T, Allocator>& x);
    void splice(iterator position,
                list<T, Allocator>& x,
                iterator i);
    void splice(iterator position,
                list<T, Allocator>& x, 
                iterator first,
                iterator last);
    void remove(const T& value);
    template <class Predicate> void remove_if(Predicate pred);
    void unique();
    template <class BinaryPredicate> 
    void unique(BinaryPredicate binary_pred);
    void merge(list<T, Allocator>& x);
    template <class Compare> void merge(list<T, 
                                        Allocator>& x, Compare comp);
    void reverse();
    void sort();
    template <class Compare> void sort(Compare comp);
};

template <class T, class Allocator>
bool operator==(const list<T, Allocator>& x,
                const list<T, Allocator>& y);

template <class T, class Allocator>
bool operator<const list<T, Allocator>& x,
              const list<T, Allocator>& y);
    

Requisitos


Ejercicios

  1. Crear un programa que use algunas de las propiedades más importantes de vector<T>
  2. Escribe un programa que pruebe la eficiencia de list<T> respecto a los arrays de C, vector<T> y deque<T>
  3. Crea y utiliza una clase que cumpla todos los requisitos necesarios para ser utiizada dentro de un list<T>