Listas en C++

C++ List estándar

Las listas (Lists) de C++ son secuencias de elementos almacenados en una lista encadenada. Comparadas con los vectores, estas permiten una mayor rapidez de inserción y borrado, pero una menor velocidad de acceso aleatorio. La plantilla list de C++ posee los métodos necesarios para insertar y borrar elementos al inicio, al final o en un punto específico de la lista. En orden de poder usar la plantilla list en nuestro programas debemos incluir la directiva (#include<list>) al inicio del código fuente.

Una simple calculadora

A manera de ejemplo, podemos pensar en una lista conteniendo datos númericos ingresados desde algun dispositivo, en el ejemplo dicho dispositivo será el teclado y los números ingresados se tratarán como reales (doubles). La idea es básica, ya que no se sabe de antemano cuantos serán los números ingresados para ser sumados usamos una lista dinámica por contener a cada uno de los números ingresados. Al final se suman los elementos ingresados y se muestra el resultado de la suma de los mismos.

Un simple ejemplo de uso de la plantilla de clase list

#include <cstdlib>

#include <iostream>

#include <iomanip>

#include <list>

using namespace std;

int main(int argc, char *argv[])

{

    list<double> lalista;

    double num, suma=0;

    cout << "Una sencilla calculadora" << endl;

    do

    {

      cout << "Ingrese un número, 0 para salir: ";

      cin  >> num;

      if (num != 0) lalista.push_back(num);

    }

    while (num != 0);

    cout << "----------" << endl;

    while( !lalista.empty() )

    {

      num = lalista.front();

      cout << setw(10) << num << endl;

      suma += num;

      lalista.pop_front();

    }

    cout << "----------" << endl;

    cout << setw(10) << suma << endl;

    system("PAUSE");

    return EXIT_SUCCESS;

}

Ordenamiento de datos (sort)

Una de las tareas comúnes sobre las listas de datos es el poner en orden a los mismos. Es decir, si tenemos una lista de, por ejemplo, nombres de personas o animales nos gustaría ordenar dicha lista en oden ascendente o descendente. De igual manera, podemos pensar en una lista de números que originalmente se encuentran desordenadamente y nos gustaría ordenar. Así, en C++ la plantilla de clase list da soporte al método sort, que dicho sea de paso, ordena los datos de la lista en forma ascendente, por defecto.

Ejemplo, en el cual se crea una lista de números enteros pseudo-aleatorios.

#include <cstdlib>

#include <iostream>

#include <iomanip>

#include <list>

using namespace std;

 // ejemplo método sort

void ordenar()

{

    list <int> lalista;

    for (int i=0; i < 10; i++)

    {

      lalista.push_back( rand()%100);

    }

     list<int>::iterator it = lalista.begin();

    cout << "Orden original" << endl;

    while( it != lalista.end() )

    {

      cout << setw(10) << *it++ << endl;

    }

     lalista.sort();

    it = lalista.begin();

    cout << "Orden ascendente" << endl;

    while( it != lalista.end() )

    {

      cout << setw(10) << *it++ << endl;

    }

}

int main(int argc, char *argv[])

{

    ordenar();

    system("PAUSE");

    return EXIT_SUCCESS;

}

Ordenamiento descendente

Por defecto, todos los objetos resultantes de la plantilla list poseen un metodo comparador asociado. Dicho comparador utiliza el operador < y debido a ello la función sort() ordenará los elementos de la lista en orden ascendente. Ahora bien, el método sort() puede invocarse sin parámetros como: objeto.sort(); y con parámetros como: objeto.sort(funcion_comparadora);. La segunda forma de solicitud permite pasar a la función sort() una función escrita por el usuario, y en dicha función podemos usar el operador > en lugar del operador < para lograr que los elementos de la lista se clasifiquen en forma descendente. Veamos un simple ejemplo:

#include <cstdlib>

#include <iostream>

#include <list>

using namespace std;

// Comparador genérico

template <class T> int comp(T a, T b)

{

    return a > b;

}

// Ejemplo: orden descendente

void test()

{

    list <string> nombres;

    nombres.push_back("Juan");

    nombres.push_back("Oscar");

    nombres.push_back("Samantha");

    nombres.push_back("Angela");

    nombres.push_back("Wilder");

    nombres.push_back("Carlos");

    nombres.sort(comp<string>);

    list<string>::iterator it = nombres.begin();

    while( it != nombres.end() )

    {

      cout << *it++ << endl;

    }

}

int main(int argc, char *argv[])

{

    test();

    system("PAUSE");

    return EXIT_SUCCESS;

}

Búsqueda e inserción de datos

Las tareas de buscar, remplazar e insertar son comúnes en el uso de listas de datos. La plantilla de clase list no da el soporte para la busqueda de datos, pero dicha tarea puede implementarse muy facilmente. En orden de buscar secuencialmente un elemento específico dentro de una lista se deben seguir los siguientes pasos:

Obtener un iterador al inicio de la lista

Comparar el elemento apuntado por el iterador con la clave buscada, si no son iguales incrementar el iterador.

El segundo paso se repite hasta encontar el elemento buscado o hasta alcanzar el final de la lista

En el siguiente programa se muestra como ejemplo la forma de buscar e insertar un elemento dentro de una lista. La idea es insertar el elemento "Maria" entre los elementos "Jose" y "Pedro". Veamos:

#include <cstdlib>

#include <iostream>

#include <list>

using namespace std;

// Ejemplo: buscar e insertar

void insertar()

{

    list <string> nombres;

    nombres.push_back("Juan");

    nombres.push_back("Jose");

    nombres.push_back("Pedro");

    nombres.push_back("Pablo");

   // Se obtiene un iterador al inicio de la lista 

   list<string>::iterator it = nombres.begin();

    // Buscamos el elemento "Pedro"

    while (*it != "Pedro" && it != nombres.end() ) it++;

    // Insertamos un elemento "Maria" en la posición indicada

    // por el iterador it.

    nombres.insert(it, 1, "Maria");

    it = nombres.begin();

    while( it != nombres.end() )

    {

      cout << *it++ << endl;

    }

}

int main(int argc, char *argv[])

{

    insertar();

    system("PAUSE");

    return EXIT_SUCCESS;

}

Borrar uno o más elementos de una lista

La plantilla list posee 5 métodos que nos permiten borrar elementos:

pop_back borra el último elemento de la lista

pop_front borra el primer elemento de la lista

erase borra uno o más elementos de la lista

remove borra un elemento de la lista

clear borra todos los elementos de la lista

La sintaxis para los métodos pop_back, pop_front y clear es sencilla ya que ninguno de estos requiere de parámetros. Por ejemplo, dado el objeto X de la clase list los métodos mencionados se invocan así:

X.pop_back();

X.pop_front();

X.clear();

El método remove nos permite borrar cualquier elemento por su valor. remove borra todos los elementos cuyo valor sea igual al argumento. La sintaxis de remove es:

remove( valor );

El método erase nos permite borrar cualquier numero de elemento. erase borra un elemento indicado por un iterador o todos los elementos indicados por un iterador inicial y un iterador final. La sintaxis de erase es:

erase( iterador );

erase( iterador inicial, iterador final );

En seguida se presenta un programa con tres ejemplos, uno sobre método remove y dos sobre el método erase.

#include <cstdlib>

#include <iostream>

#include <list>

using namespace std;

// Ejemplo: metodo remove

void test01()

{

    list <string> nombres;

    nombres.push_back("Juan");

    nombres.push_back("Oscar");

    nombres.push_back("Samantha");

    nombres.push_back("Angela");

    nombres.push_back("Wilder");

    nombres.push_back("Carlos");

    nombres.push_back("Oscar");

    list<string>::iterator it = nombres.begin();

    cout << "antes de remove" << endl;

    while( it != nombres.end() )

    {

      cout << "\t" << *it++ << endl;

    }

    cout << endl;

    nombres.remove("Oscar");

    it = nombres.begin();

    cout << "despues de remove" << endl;

    while( it != nombres.end() )

    {

      cout << "\t" << *it++ << endl;

    }

    cout << endl;

}

// Ejemplo 1: metodo erase

void test02()

{

    list <string> nombres;

    nombres.push_back("Juan");

    nombres.push_back("Oscar");

    nombres.push_back("Samantha");

    nombres.push_back("Angela");

    nombres.push_back("Wilder");

    nombres.push_back("Carlos");

    list<string>::iterator it = nombres.begin();

    cout << "antes de erase" << endl;

    while( it != nombres.end() )

    {

      cout << "\t" << *it++ << endl;

    }

    cout << endl;

    nombres.erase( nombres.begin() );

    it = nombres.begin();

    cout << "despues de erase" << endl;

    while( it != nombres.end() )

    {

      cout << "\t" << *it++ << endl;

    }

    cout << endl;

}

// Ejemplo 2: metodo erase

void test03()

{

    list <string> nombres;

    nombres.push_back("Juan");

    nombres.push_back("Oscar");

    nombres.push_back("Samantha");

    nombres.push_back("Angela");

    nombres.push_back("Wilder");

    nombres.push_back("Carlos");

    list<string>::iterator it = nombres.begin();

    cout << "antes de erase" << endl;

    while( it != nombres.end() )

    {

      cout << "\t" << *it++ << endl;

    }

    cout << endl;

    list<string>::iterator ini = nombres.begin();

    list<string>::iterator fin = nombres.end();

    ini++; ini++;

    fin--; fin--;

    nombres.erase( ini, fin );

    it = nombres.begin();

    cout << "despues de erase" << endl;

    while( it != nombres.end() )

    {

      cout << "\t" << *it++ << endl;

    }

    cout << endl;

}

// Entrada del programa

int main(int argc, char *argv[])

{

    system("cls"); test01(); system("PAUSE");

    system("cls"); test02(); system("PAUSE");

    system("cls"); test03(); system("PAUSE");

    return EXIT_SUCCESS;

}

Lista de métodos

Tabla de métodos: clase list
assign	asignar elementos a la lista
back	regresa una referencia a el último componente de la lista
begin	regresa un iterator al principio de la lista
clear	remueve todos los componentes de la lista
empty	true si la lista está vacia
end	regresa un iterator al final de la lista
erase	remueve componentes de la lista
front	regresa una referencia al primer componente de la lista
insert	insertar componentes en la lista
max_size	regresa el número máximo de elementos soportados por la lista
merge	une dos listas
pop_back	remueve el último componente de la lista
pop_front	remueve el primer componente de la lista
push_back	agrega un componente al final de la lista
push_front	agrega un componente al frente de la lista
rbegin	regresa un reverse_iterator hacia el final de la lista
remove	remueve componentes de la lista
remove_if	remueve condicionalmente componentes de la lista
rend	regresa un reverse_iterator hacia el inicio de la lista
resize	cambia el tamaño de la lista
reverse	pone al revez los componentes de la lista
size	regresa el número de componentes en la lista
sort	clasifíca la lista
splice	unión de dos listas
swap	inetrcambia el contenido de una lista con el de otra
unique	remueve componentes duplicados