Programación en C++/Librería Estándar de Plantillas/Listas
| ← Librería Estándar de Plantillas |
C++ List estándar
[editar]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
[editar]A modo de ejemplo, podemos pensar en una lista conteniendo datos numéricos ingresados desde algún 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)
[editar]Una de las tareas comunes 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 orden 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.
Veamos un 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
[editar]Por defecto, todos los objetos resultantes de la plantilla list poseen un método 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
[editar]Las tareas de buscar, remplazar e insertar son comunes en el uso de listas de datos. La plantilla de clase list no da el soporte para la búsqueda de datos, pero dicha tarea puede implementarse muy fácilmente. 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 encontrar 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
[editar]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: método 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: método 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
[editar]| assign | asigna elementos a la lista |
| back | devuelve una referencia a el último componente de la lista |
| begin | devuelve un iterator al principio de la lista |
| clear | elimina todos los componentes de la lista |
| empty | true si la lista está vacía |
| end | devuelve un iterator al final de la lista |
| erase | elimina componentes de la lista |
| front | devuelve una referencia al primer componente de la lista |
| insert | inserta componentes en la lista |
| max_size | devuelve el número máximo de elementos soportados por la lista |
| merge | une dos listas |
| pop_back | elimina el último componente de la lista |
| pop_front | elimina el primer componente de la lista |
| push_back | añade un componente al final de la lista |
| push_front | añade un componente al frente de la lista |
| rbegin | devuelve un reverse_iterator hacia el final de la lista |
| remove | elimina componentes de la lista |
| remove_if | elimina condicionalmente componentes de la lista |
| rend | devuelve un reverse_iterator hacia el inicio de la lista |
| resize | cambia el tamaño de la lista |
| reverse | pone al revés los componentes de la lista |
| size | devuelve el número de componentes en la lista |
| sort | ordena la lista |
| splice | unión de dos listas |
| swap | intercambia el contenido de una lista con el de otra |
| unique | elimina componentes duplicados |
| ← Librería Estándar de Plantillas |