Programación en C++/Librería Estándar de Plantillas/Listas

De Wikilibros, la colección de libros de texto de contenido libre.
Saltar a: navegación, buscar

Editores:

Oscar E. Palacios

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 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)[editar]

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.

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 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[editar]

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:

  1. Obtener un iterador al inicio de la lista
  2. Comparar el elemento apuntado por el iterador con la clave buscada, si no son iguales incrementar el iterador.
  3. 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[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:

  1. erase( iterador );
  2. 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[editar]

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
Librería Estándar de Plantillas