C++ / adaptadores de contenedores

Bienvenidos sean a este post, hoy veremos otro nombre que pueden tener dos temas ya vistos.

Hace un tiempo, en una serie de posts hablamos sobre los contenedores STL y sus integrantes. Recientemente, hablamos sobre estructuras de datos y en ellas mencionamos a dos contenedores como son list y vector. En esta serie de posts mencionamos unos llamados stack y queue, donde comentamos que no eran contenedores sino estructura de datos pero que tampoco llegaban a esta categoria.

Si tenemos que resumirlo, tanto stack como queue son un envoltorio para los contenedores. Otro tema que surge es relacionaod a stack, esta palabra esta en casi todas partes y hasta ahora lo hemos utilizado para describir un segmento de memoria para objetos con duracion de almacenamiento automatico. Este segmento se lo denomina asi porque toma la estrategia de ubicacion/remocion en memoria.

Si repasamos como trabajan, cuando los ingresamos son empujados (pushed) al stack y sacados (pop) en la destruccion. Los objetos son eliminados en el orden inverso al que fueron ingresados, mas usualmente denominados como LIFO, y como este segmento de memoria trabaja de la misma manera que describimos es la razon por la que se denomina como stack.

Nota:
LIFO, Last-In-First-Out.

Para poder realizar la tarea anterior, utilizamos al metodo push pero este en realidad usa a push_back para agregar informacion. Por esta razon, para implementar a stack se usa un vector, asi como tambien este posee dos parametros template; siendo uno de estos el contenedor. Sin importar el que escojamos, este debe tener una funcion miembro push_back y el contenedor predeterminado para stack y queue es deque. Esto es asi porque nos permite insertar elementos tanto al inicio como al final y es muy similar a vector. Vamos a analizar el siguiente codigo:

#include <iostream>
#include <stack>

int main()
{
        std::stack<int> st;
        for (int i=1; i < 4; i++)
                st.push(i);

        for(int i = 0; i < 4; i++) {
                std::cout << st.top()  << std::endl;
                st.pop();
        }

        return 0;
}

Un ejemplo simple donde veremos varias cosas. Primero tenemos un bucle donde mediante push agregaremos un valor al stack, el valor es el de cada pasada en el bucle. Luego tenemos otro bucle donde primero mostraremos el ultimo valor ingresado y despuues mediante pop lo sacaremos, y volvemos a repetir el proceso unas cuatro veces. Compilemos y veamos como es la salida:

$ ./cont
3
2
1
Violación de segmento
$

Observen que nos devolvio una violacion de segmento, esto es asi porque intentamos buscar un valor en un stack vacio. Para solucionarlo, debemos modificar el codigo de la siguiente manera:

#include <iostream>
#include <stack>

int main()
{
        std::stack<int> st;
        for (int i=1; i < 4; i++)
                st.push(i);

        while(!st.empty()) {
                std::cout << st.top()  << std::endl;
                st.pop();
        }

        return 0;
}

En este caso, hicimos un cambio simple. Reemplazamos el bucle por un while donde actuara mientras el stack no este vacio. El bloque es el mismo que el anterior lo mismo que el resto del codigo. Compilemos y veamos la nueva salida:

$ ./cont
3
2
1
$

Con esto tenemos solucionado el problema y podemos observar como se cumplio el LIFO. Donde el primer objeto que sale, es justamente el ultimo que ingresamos.

El otro adaptador de contenedores que disponemos es queue, es similar a stack pero su conducta es distinta porque en este aplicamos FIFO, el primero que entra es el primero que sale. Si bien en queue seguimos teniendo a push y pop para ingresar y remover elementos respectivamente, estos tienen a denominarlos mas como enqueue para agregar, y dequeue para removerlos. Pero a diferencia de stack podemos ver al primer elemento y ultimo agregado. Para ello usamos a front y back respectivamente. Analicemos el siguiente ejemplo:

#include <iostream>
#include <queue>

int main()
{
        std::queue<int> q;
        for (int i=1; i < 5; i++)
                q.push(i);

        while(!q.empty()) {
                std::cout << "front:\t" <<  q.front()  << std::endl;
                std::cout << "back:\t" << q.back()  << std::endl;
                std::cout << "++++++++++++++++++++++"  << std::endl;
                q.pop();
        }

        return 0;
}

Este es muy similar al codigo anterior pero agregaremos cuatro valores al queue, en lugar del stack, y luego usamos un while muy similarr al anterior donde trabajaremos con el queue mientras no este vacio. En este mostraremos los valores de front y back para luego aplicar un pop y eliminar el valor en front. Recuerden que el primero en entrar es el primero en salir. Compilemos y veamos como es la salida:

$ ./cont
front:  1
back:   4
++++++++++++++++++++++
front:  2
back:   4
++++++++++++++++++++++
front:  3
back:   4
++++++++++++++++++++++
front:  4
back:   4
++++++++++++++++++++++
$

Observen como son los valores iniciales, y como solo varia el de front por lo mencionado anteriormente. Sale el primero en ingresar, y a medida que los eliminamos se reemplaza con el siguiente a diferencia de stack. Esto genera un efecto como si los valores estuvieron en una fila, queue, y a medida que salen de la misma son reemplazados por el siguiente.

Estos dos se los considera adaptadores de contenedores porque como mencionamos al inicio del post, no son contenedores pero tampoco aplican totalmente a estructura de datos. Pero al envolver un contenedor nos pueden ser muy utiles para algunas tareas. Si tienen curiosidad para ver un poco mas sobre los tres contenedores mencionados aqui les dejo los tres postss donde hablamos de ellos:

En resumen, hoy hemos visto a adaptadores de contenedores, en realidad un tema que habiamos visto hace tiempo, asi como un repaso general y algunas particularidades de cada uno, y porque son denominados como adaptadores. 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.