C++ / list – merge y splice

Bienvenidos sean a este post, hoy veremos nuevamente a este contenedor STL.

Continuando con el post anterior donde mencionamos que no era necesario reinventar la polvora y por ende, no es necesario volver a crear los list. Porque estos ya forman parte de los contenedores STL, de los cuales hablamos en este post, y ya hablamos sobre list en el siguiente post:

En ese post hablamos como trabaja y algunas de los metodos que teniamos disponibles. Si tenemos que compararlo con vector no es muy distinto pero como mencionamos en este post es mas del tipo nodo de datos que secuencial. En el post donde hablamos sobre list convertimos un codigo de vector a list con mucha facilidad. Este contenedor soporta los metodos estandar para saber el tamaño y la capacidad, asi como otros para manipular los datos. Veamos un ejemplo simple para comenzar a hablar sobre ellos:

#include <iostream>
#include <list>

void mostrar(std::list<double> l)
{
        int i = 0;
        for(double e: l) {
                std::cout << "[" << i << "]: "<< e << std::endl;
                i++;
        }
        std::cout << "++++++++++++++++++++++++++" << std::endl;
}

int main()
{
        std::list<double> lista;
        lista.push_back(3.14);
        mostrar(lista);
        lista.push_front(4.22);
        mostrar(lista);
        lista.push_back(0.45);
        mostrar(lista);

        return 0;
}

Antes de entrar en el main, hablemos sobre la funcion que usaremos para mostrar el contennido de un objeto tipo list. Esta la usaremos para mostrar no solo cada elemento sino en que posicion se encuentra asi como tambien una linea para mostrar donde termino. Yendo al main, primero creamos un objeto llamado lista y este almacena valores de tipo double. A este le agregamos un valor mediante push_back, mostramos a la lista, luego le agregamos otro mediante push_front, volvemos a mostrarla y agregamos otro valor mediante push_back para finalmente mostrarlo nuevamente. Compilemos y veamos como es la salida:

$ ./list
[0]: 3.14
++++++++++++++++++++++++++
[0]: 4.22
[1]: 3.14
++++++++++++++++++++++++++
[0]: 4.22
[1]: 3.14
[2]: 0.45
++++++++++++++++++++++++++
$

Este codigo lo hice para mostrar como se agregan los valores al inicio y al final mediante sus respectivas funciones. Veamos un metodo que nos puede ser util para nuestras listas. Para ello vamos a modificar el codigo anterior de la siguiente manera:

#include <iostream>
#include <list>

template <typename T>
void mostrar(std::list<T> l)
{
        int i = 0;
        for(T e: l) {
                std::cout << "[" << i << "]: "<< e << std::endl;
                i++;
        }
        std::cout << "++++++++++++++++++++++++++" << std::endl;
}

int main()
{
        std::list<double> lista1{1.4, 0.45, 3.4};
        std::list<double> lista2{3.33, 2.8, 5.1};
        mostrar(lista1);
        lista1.merge(lista2);
        mostrar(lista1);

        return 0;
}

La primera modificacion es en la funcion mostrar. Esta la convertimos a un tipo generico para poder manejar distintos datos en nuestras listas. La funcion sigue siendo la misma pero reemplazamos el tipo a manejar por el generico. En el main, creamos dos listas con distintos valores. Seguimos usando tipo double, lo primero que haremos sera mostrar el valor de lista1. A esta lista le aplicamos el metodo merge y le pasamos como argumento la segunda lista. Esto hara que se una a la primer lista y finalmente mostramos el resultado final de unir las dos listas. Compilemos y veamos como es la salida:

$ ./list
[0]: 1.4
[1]: 0.45
[2]: 3.4
++++++++++++++++++++++++++
[0]: 1.4
[1]: 0.45
[2]: 3.33
[3]: 2.8
[4]: 3.4
[5]: 5.1
++++++++++++++++++++++++++
$

Observen que unio las dos listas pero dandole un orden interno sin respetar el orden que posee en cada lista. Otro metodo similar que disponemos es splice, este copia la lista en otra. Tomemos el codigo anterior y hagamos el siguiente cambio:

#include <iostream>
#include <list>
#include <string>

template <typename T>
void mostrar(std::list<T> l)
{
        int i = 0;
        for(T e: l) {
                std::cout << "[" << i << "]: "<< e << std::endl;
                i++;
        }
        std::cout << "++++++++++++++++++++++++++" << std::endl;
}

int main()
{
        std::list<double> lista1{1.4, 0.45};
        std::list<double> lista2{3.33, 2.8, 5.1, 9.9, 0.1, 7.5};
        lista1.splice(lista1.begin(),lista2);
        mostrar(lista1);

        return 0;
}

En este codigo hicimos unos pequeños cambios. El primero son los valores en cada lista, reducimos en uno y agregamos mas en otro. El segundo cambio es el metodo para unir las listas, usamos a splice. Como primer argumento usamos a begin para poder tener un objeto iterador que indica desde donde debe empezar a copiar y luego la lista desde donde sacaremos la informacion. Compilemos y veamos como es la salida:

$ ./list
[0]: 3.33
[1]: 2.8
[2]: 5.1
[3]: 9.9
[4]: 0.1
[5]: 7.5
[6]: 1.4
[7]: 0.45
++++++++++++++++++++++++++
$

Vean como copio todos los elementos de lista2 a la otra pero no los reemplazo sino simplemente desplazo a los existentes para ubicarlos despues del ultimo valor de la lista que copiamos. Y en este caso si respeto el orden de cada posicion en las listas. Volvamos al codigo anterior y realicemos el siguiente cambio:

lista1.splice(lista1.end(),lista2);

En lugar de decirle que lo ubique al inicio de la lista lo haga al final. Compilemos y veamos como es la salida:

$ ./list
[0]: 1.4
[1]: 0.45
[2]: 3.33
[3]: 2.8
[4]: 5.1
[5]: 9.9
[6]: 0.1
[7]: 7.5
++++++++++++++++++++++++++
$

Lo mismo que antes pero esta vez los elementos que copiamos se agregaron despues del ultimo dato de la lista original. Este puede ser mas util comparado con merge, porque respeta las posiciones de los valores en la lista. Esta es otra forma practica de como podemos pasar informacion en distintas secciones de la memoria sin tener ninguna necesidad de reinventar la polvora.

En resumen, hoy hemos visto a list, un poco mas a fondo despues que hablamos de las estructuras de datos, tambien algunas opciones nuevas que no mencionamos anteriormente, asi como unos ejemplos practicos. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.