Ir al contenido

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

De Wikilibros, la colección de libros de texto de contenido libre.
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:

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

  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: 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]
Tabla de métodos: clase list
assignasigna elementos a la lista
backdevuelve una referencia a el último componente de la lista
begindevuelve un iterator al principio de la lista
clearelimina todos los componentes de la lista
emptytrue si la lista está vacía
enddevuelve un iterator al final de la lista
eraseelimina componentes de la lista
frontdevuelve una referencia al primer componente de la lista
insertinserta componentes en la lista
max_sizedevuelve el número máximo de elementos soportados por la lista
mergeune dos listas
pop_backelimina el último componente de la lista
pop_frontelimina el primer componente de la lista
push_backañade un componente al final de la lista
push_frontañade un componente al frente de la lista
rbegindevuelve un reverse_iterator hacia el final de la lista
removeelimina componentes de la lista
remove_ifelimina condicionalmente componentes de la lista
renddevuelve un reverse_iterator hacia el inicio de la lista
resizecambia el tamaño de la lista
reversepone al revés los componentes de la lista
sizedevuelve el número de componentes en la lista
sortordena la lista
spliceunión de dos listas
swapintercambia el contenido de una lista con el de otra
uniqueelimina componentes duplicados
Librería Estándar de Plantillas