C++ / iterando contenedores

Bienvenidos sean a este post, hoy veremos el concepto de iteracion pero en contenedores.

Los contenedores tambien se pueden iterar porque no dejan de ser colecciones con un conjunto de elementos en su interior. Pero este es un poco distinto a los arrays o colecciones que posee el lenguaje de forma base. Hasta el post anterior, hemos visto algunos. Por ejemplo, vector tiene al operador [] y al metodo at para recuperar un elemento de este. list tiene a front y back para recuperar la primer y ultima posicion respectivamente. stack para esta tarea utiliza a top para recuperar el ultimo valor ingresado. Veamos el siguiente ejemplo:

#include <iostream>
#include <list>

int main()
{
        std::list<int> l;
        for (int i=1; i < 5; i++)
                l.push_back(i);

        for(int i=0; i < l.size(); i++)
                std::cout << l[i] << std::endl;

        return 0;
}

Este es un ejemplo simple con list donde primero agregaremos cuatro valores en un objeto de este tipo. Lo siguiente es utilizar un bucle para recuperar y mostrar los valores almacenados anteriormente. Compilemos y veamos que sucede:

$ g++ cont.cpp -o cont
cont.cpp: In function ‘int main()’:
cont.cpp:11:31: error: no match for ‘operator[]’ (operand types are ‘std::__cxx11::list<int>’ and ‘int’)
   11 |                 std::cout << l[i] << std::endl;
      |                               ^
$

Como pueden ver no se puede compilar porque este operador no existe en list. Pero como podemos recuperar esa informacion? el metodo as simple es usar un for mejorado, para ello tomemos el codigo anterior y hagamos el siguiente cambio:

#include <iostream>
#include <list>

int main()
{
        std::list<int> l;
        for (int i=1; i < 5; i++)
                l.push_back(i);

        for(int e: l)
                std::cout << e << std::endl;

        return 0;
}

En este caso reemplazamos el bucle para mostrar por este mejorado. Donde pasara por todos los elementos del contenedor, lo almacena en una variable y luego la mostraremos en el bloque. El resto sigue siendo el mismo codigo que teniamos antes. Compilemos y veamos como es su salida:

$ ./cont
1
2
3
4
$

Este bucle tiene un pequeño truco donde permite procesar toda la informacion de forma simple pero para obtener un valor puede ser mas complicado pero tenemos un par de metodos que nos permiten trabajar con un bucle normal. Estos son begin y end, donde recuperaremos el valor inicial y final respectivamente de la lista. Pero como podemos recuperar un valor intermedio? Para ello necesitamos un iterator. Este es un objeto que nos permite pasar por las distintas posiciones de un contenedor simplemente apuntando a la direccion donde se encuentra. Tomemos el ejemplo y hagamos el siguiente cambio:

#include <iostream>
#include <list>

int main()
{
        std::list<int> l;
        for (int i=1; i < 5; i++)
                l.push_back(i);

        for(std::list<int>::iterator i = l.begin(); i != l.end(); i++)
                std::cout << *i << std::endl;

        return 0;
}

Observen como manejamos al bucle for. Para poder acceder a los elementos creamos el objeto iterador del tipo de la lista y a este le asignamos la primera posicion o primer elemento de la lista mediante begin. La condicion sera mientras este objeto sea distinto del ultimo elemento almacenado en end. Para poder avanzar simplemente incrementamos la posicion del objeto. Recuerdan cuando hablamos de que las colecciones almacenan de forma secuencial los valores, es decir si incrementamos en uno la direccion de memoria pasara al siguiente elemento y asi sucesivamente en cada pasada. Pero para mostrar el valor en ese segmento de memoria, no usamos al objeto sino al puntero de este. Compilemos y veamos como es la salida:

$ ./cont
1
2
3
4
$

Como pueden ver nos devolvio la informacion contenida en la lista. Para entender mejor el concepto, tomemos el codigo anterior y hagamos el siguiente cambio:

#include <iostream>
#include <list>

int main()
{
        std::list<int> l;
        for (int i=1; i < 5; i++)
                l.push_back(i);

        std::list<int>::iterator li = l.begin();

        std::cout << *li << std::endl;
        std::cout << *li+2 << std::endl;

        return 0;
}

En este caso, simplemente eliminamos el segundo bucle para crear un objeto del tipo iterador y lo iniciamos con el valor de begin. Luego mostramos el valor en este objeto, recuerden que se debe usar un puntero, y para el siguiente caso incrementamos en dos a este puntero para desplazarnos dos posiciones. Compilemos y veamos como es la salida:

$ ./cont
1
3
$

Esto es lo que comentamos en otros posts donde deciamos que las colecciones poseen elementos en forma secuencial donde nos vamos desplazando uno detras del otro para recuperar esos valores. Pero en STL tenemos seis categorias de iteradores:

• input
• output
• forward
• bidireccional
• acceso random
• continuo

Comencemos a hablar brevemente sobre cada uno de ellos. El iterador input nos provee acceso de lectura, mediante el operador de puntero, y podemos variar su posicion con el uso del operador de incrementacion. Otra particularidad, este no soporta multiples pases, podemos usar un iterador para iterar sobre un contenedor solo una vez. El iterador output no provee acceso al elemento pero si permite asignar un valor al mismo. El iterador forward, a diferencia de input si soporta multiples pases. Esto significa que podemos leer el valor del elemento a traves del iterador mas de una vez pero este soporta solo operaciones de incrementacion.

El iterador bidireccional es muy similar a forward pero a diferencia de este permite ubicarnos en cualquier posicion del iterador. Es decir, podemos usar el operador de incrementacion y decrementacion. Por ejemplo, uno que lo soporta el iterador bidireccional es list. El iterador de acceso random nos permite saltar a traves de los distintos elementos mediante la adicion o substracion de un numero al iterador. Este tipo de iterador es soportado por vector.

Ya vimos que cada iterador tiene su accion para poder iterar con los distintos elementos. Siendo algunos para pasar al siguiente pero solo con el operador de incrementacion, asi como otros permite el uso del operador de decrementacion para retroceder y algunos saltar a una posicion de forma aleatoria. Pero estas conductas caen en una sola iteracion, la llamada continua. Estos son aquellos contenedores que tienen asegurado el siguiente elemento a la derecha del otro. Un ejemplo de este tipo es std::array. Funciones como distance usan la informacion del iterador para alcanzar el resultado mas rapido en la ejecucion. Por ejemplo, esta funcion entre dos iteradores bidireccionales toma un tiempo lineal de ejecucion. En cambio, si fueran de tipo random toma un tiempo constante.

La mas importante cualidad de los iteradores es proveer un acoplamiento flexible entre contenedores y algoritmos. STL es basado en tres conceptos:

• conceptos
• algoritmos
• iteradores

Los contenedores pueden ser de distintos tipos pero todos sirven para el mismo proposito: almacenar informacion. Los algoritmos son funciones que trabajan con datos, aunque la mayoria de las veces trabaja con colecciones. Estos representan una manera generica de especificar los pasos que se deberian tomar para manejar los elementos del contenedor. Tomemos como ejemplo lo siguiente, los vector son contenedores continuos y los list son contenedores basados en nodos. Si necesitamos ordenarlos, para ello debemos usar el algoritmo sort. Y para ello necesitamos un conocimiento mas profundo de la estructura fisica del contenedor.

Los iteradores toman esta multiplicidad de implementaciones a un nivel generico. Ellos proveen a los diseñadores de librerias para implementar una sola funcion de orden, la cual solo trabaja con iteradores, abstraccion del tipo contenedor. En el STL, el algoritmo sort trabaja con iteradores y podemos ordenar tanto a vector como list con la misma funcion. Todos estos iteradores descriptos, actualmente son considerados como caracteristicas heredadas. Porque a partir de C++ 20, se introduce un nuevo sistema de iteradores basados en conceptos pero eso sera tema a partir del proximo post.

En resumen, hoy hemos visto como iterar con contenedores, como es que se puede, como se permite, como no se permite, como podemos trabajar de varias formas asi como una breve introduccion a los conceptos. 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.