List

Introducción

Una lista nos permite almacenar elementos de cualquier tipo debido a su capacidad de template. A diferencia de los vector, estos elementos de la lista no están situados de forma contigua en memoria. Los elementos de una lista están linkados entre sí proporcionando mayor flexibilidad en memoria.

Anteriormente para generar una lista necesitábamos crearla desde cero e implementar tanto la parte de almacenamiento como la parte de control de este almacén en memoria. Con una lista de las STL esto ya no es necesario porque ya nos viene preparada y lista para ser usada.

Consideraciones

Hay que tener en cuenta ciertas consideraciones para poder trabajar con las listas de las STL.

Constructores

Como todos sabéis, los objetos necesitan constructores, pero las listas de las STL, hacen uso en determinados casos de los constructores copias de los objetos.

Normalmente los constructores copia no son tan comúnmente implementados como los constructores por defecto. Yo concretamente os recomiendo que para todos aquellos objetos que vayáis a introducir en la lista, defináis el constructor copia de ese objeto

CObjeto::CObjeto( const CObjeto &inObj);

Operador =

Todo objeto que vaya a ser introducido en una lista debe tener implementado o sobrecargado el operador ‘=’.

const CObjeto CObjeto::operator= (const CObjeto &inObj);

Operador <

Si queremos llamar a las funciones de ordenación de los objetos de dentro de la lista, estos tendrán que tener implementado el operador ‘<’ para que la lista los sepa ordenar.

Este operador NO es necesario mientras no se quieran ordenar los elementos, por lo tanto es opcional.
Funciones con ‘const’

Relacionado con el apartado del operador ‘=’, como el parámetro que recibe es un objeto marcado como const, todas las funciones de ese objeto que se utilicen en el operador ‘=’ deben ser de tipo const para eliminar posibles errores de código.

Un ejemplo podría ser el siguiente:

unsigned int GetNumero() const;

Implementación:

unsigned int CObjeto::GetNumero() const
{
    return (m_iNum);
}

En el código anterior podemos observar como la función está marcada como const y es apta para ser utilizada en el cuerpo del operador ‘=’. De no marcar a la función como const, el compilador dará un error cuando este compilando el código del operador ‘=’.

Declaración

Para declarar en nuestro código una lista y poder utilizarla será necesario incluir en nuestro código el include <list>. Una vez declarado este include, ya podemos declarar nuestra lista indicando que tipo de objetos contendrá.

#include <list>
 
void main()
{
    std::list<int> lList1;
    std::list<float> lList2;
    std::list<CObject> lList3;
 
}

Los objetos lista pertenecen al namespace std, esto implica que cada uno de los objetos lista deberá ser precedido en su declaración por el prefijo std:: para indicar que es de ese namespace.

Si queremos simplificar este aspecto, solo tenemos que añadir una línea después de los includes de nuestro código como podemos ver a continuación.

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
    list<float> lList2;
    list<CObject> lList3;
}

Esa línea nos indica que nuestro código ya conoce el namespace std y que por ello ya no es necesario preceder a los objetos de dicho espacio con su nombre.

Añadir elementos

Una vez disponemos de de un objeto lista declarado ya podemos empezar a añadir elementos a este.

Para poder añadir elementos el objeto lista nos proporciona dos funciones muy sencillas de utilizar, estas son push_back(…) y el push_front(…).

push_back(…)

La función push_back(…) nos realiza la inserción de un elemento al final de esta misma. Es decir, este elemento será colocado detrás del que tenia la última posición.

A continuación podemos ver un ejemplo de esta función:

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
 
    lList1.push_back(1);
    lList1.push_back(4);
    lList1.push_back(2);
    lList1.push_back(7);
}

En el código anterior podemos observar como las listas siguen la misma metodología en esta función que los vectores. El resultado del código anterior es de { 1, 4, 2, 7 }.

push_front(…)

La función push_front(…), a diferencia de la anterior función, inserta los elementos siempre al principio de la lista.

A continuación podemos ver un emeplo:

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
 
    lList1.push_back(1);
    lList1.push_back(4);
    lList1.push_back(2);
    lList1.push_back(7);
    lList1.push_front(29);
}

En el código anterior podemos observar como la función push_front(…) deja el elemento al principio de la lista. El resultado final de este código es de { 29, 1, 4, 2, 7 }.

NOTA: Como la naturaleza de las listas no es la de mantener los elementos contiguos en memoria, el hecho de insertar un elemento al principio de la lista es igual de eficiente que insertar ese mismo elemento al final. Esto NO ocurre con los vectores.

Consultar elementos

Una de las opciones básicas de las listas es la de poder consultar los elementos que esta contiene.

En el caso del vector, nosotros tenemos el operador […] con el cual podemos acceder al elemento directamente con un índice.

En una lista tenemos otros métodos para poder acceder a los elementos de esta:

++Iterators

Mediante los iterators nosotros podemos acceder a cualquier elemento de la lista y hacer lo que queramos con él.

Para poder hacer uso de los iteradores necesitaremos primero de todo definir como mínimo un iterador que sea acorde con el tipo de nuestra lista.

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
    list<int>::iterator iTer1;
}

En el código anterior podemos observar como definimos un iterador para listas de tipo list<int>.

Este iterador nos sirve para poder ‘viajar’ por los elementos de la lista, para hacer esto solo tenemos que inicializar el iterador a un elemento de la lista y utilizar posteriormente el operador ++ para ir de elemento en elemento.

En el siguiente ejemplo podemos observar cómo vamos desde el inicio de la lista hasta el final de la lista pasando por cada uno de los elementos.

También comentar que para poder acceder a los elementos apuntados por un iterador será necesario tratar a este iterador como si de un puntero al elemento se tratara.

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
 
    lList1.push_back(1);
    lList1.push_back(4);
    lList1.push_back(2);
    lList1.push_back(7);
 
    for(list<int>::iterator iTer = lList.begin(); iTer1 != lList1.end(); NULL )
    {
        *iTer = 5;
        iTer++;
    }
}

En el código anterior inicializamos una lista con algunos elementos y después de ello utilizamos un bucle para poder acceder elemento a elemento.

Fijémonos que definimos una variable iterator que igualamos al iterador que apunta al principio de la lista, la condición de salida es que ese iterador sea diferente al iterador que apunta al final de la lista y la condición de incremento la colocamos dentro del propio bucle.

El acceso al objeto para poder modificarlo se hace a trabes del contenido del propio iterador.

NOTA: Esta idea de ‘viajar’ a lo largo de los elementos de una lista no está limitada a solo desde principio a fin (begin() a end() ), ya que nosotros somos los que marcamos de que iterador a que iterador viajamos.

Eliminar elementos

Una vez ya sabemos como añadir elementos y como consultarlos / modificarlos, llega el turno a las funciones para poder eliminarlos de la lista.

Pop_front()

Esta función nos elimina el primer elemento de la lista, haciendo que el segundo elemento ahora sea el primero que nos encontremos.

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
 
    lList1.push_back(1);
    lList1.push_back(4);
    lList1.push_back(2);
    lList1.push_back(7);
 
lList1.pop_front();
}

El código anterior nos da como resultado la lista { 4, 2, 7 }

Pop_back()

Esta función nos elimina el último elemento de la lista, haciendo que el penúltimo elemento quede ahora como último elemento.

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
 
    lList1.push_back(1);
    lList1.push_back(4);
    lList1.push_back(2);
    lList1.push_back(7);
 
    lList1.pop_back();
}

Este código nos da como resultado la lista { 1, 2, 4 }

erase(…)

La función erase(…) nos sirve para eliminar un elemento de la lista apuntado por un iterador. Esta función nos dota de la habilidad para poder borrar el elemento que queramos de la lista.

Antes de mirar el ejemplo es necesario explicar que esta función devuelve un iterador que apunta al elemento justo después del elemento eliminado. Esto es así porque una vez eliminador el elemento apuntado por el iterador, este iterador queda invalidado.

Que un puntero quede invalidado significa que está apuntando a un trozo de memoria que ya no pertenece al programa. Para subsanar esto, la función erase(…) nos devuelve un iterador que tendremos que substituir por nuestro antiguo iterador.

#include <list>
 
using namespace std;
 
void main()
{
    list<int> lList1;
 
    lList1.push_back(1);
    lList1.push_back(4);
    lList1.push_back(2);
    lList1.push_back(7);
 
    for(list<int>::iterator iTer = lList1.begin(); iTer1 != lList1.end(); NULL )
    {
        if((*iTer) == 2)
        {
            iTer = lList1.erase(iTer);
        }
        else
        {
            ++iTer;
        }
    }
}

El código anterior es el código por defecto para borrar un elemento de la lista a nuestra elección según una condición.

Fijémonos en cómo funciona.

Primero de todo definimos un bucle el cual sea capaz de viajar por todos los elementos de la lista como hemos hecho en anteriores casos.

Insertamos una condición para borrar un elemento de la lista, esta condición la realizamos accediendo al elemento para consultarlo como si de un puntero de tratara.

Si es necesario borramos ese elemento, el elemento borrador ese aquel apuntado por el iterador iTer. Seguidamente este iterador es substituido por el iterador que nos devuelve la función erase(…) para poder ser consistente con el algoritmo.

Si no hemos encontrado el elemento que estamos buscando, continuamos viajando incrementando el iterador, en este caso realizamos la operación ++ antes para no tener errores en elementos limites como el primer o ultimo elemento de la lista.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License