You are currently browsing the tag archive for the ‘STL’ tag.

Cuando compilamos patrones de clases (templates) en C++, como los contenedores de la STL, entonces tenemos a veces errores de compilación con mensajes exageradamente largos, que esconden más que aclaran. En este artículo quiero enseñar de como “leer” estos mensajes para fácilmente encontrar el error causante.

Primero debemos entender que el mensaje del compilador intenta mostrar toda la información posible. Según el tipo del problema, diferentes partes del mensaje pueden ser significantes. Por ejemplo, si cambio el allocator estándar de un contenedor por uno diferente, entonces me importará qué dice el mensaje de error sobre este componente. No obstante, en este artículo asumimos un uso básico de contenedores de la STL.

Más concretamente compilamos este trozo de código.

    // Una instancia de un mapa
	std::map mi_mapa;

	// Un iterator a una posición del mapa
	std::map::const_iterator const_itr = mi_mapa.begin();

	// Insertar un nuevo elemento en la posición indicada por el iterador
	mi_mapa.insert(const_itr, std::pair("atributo", "valor"));

Este código falla en la línea mi_mapa.insert.

Descifrando un mensaje de MinGW

Compilando con un compilador MinGW obtenemos el siguiente error para esta línea.

error: no matching function for call to `std::map, std::allocator > >::insert(std::_Rb_tree_const_iterator >&, std::pair)'
C:/opt/Dev-Cpp/include/c++/3.4.2/bits/stl_map.h:360: note: candidates are: std::pair<_Key, std::pair, std::_Select1st >, _Compare, _Alloc>::iterator, bool> std::map<_Key, _Tp, _Compare, _Alloc>::insert(const std::pair&) [with _Key = std::string, _Tp = std::string, _Compare = std::less, _Alloc = std::allocator >]
C:/opt/Dev-Cpp/include/c++/3.4.2/bits/stl_map.h:384: note:                 typename std::_Rb_tree<_Key, std::pair, std::_Select1st >, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::insert(typename std::_Rb_tree<_Key, std::pair, std::_Select1st >, _Compare, _Alloc>::iterator, const std::pair&) [with _Key = std::string, _Tp = std::string, _Compare = std::less, _Alloc = std::allocator >]

El mensaje consiste de tres líneas: primero el error de que no hay una función que corresponde a la llamada y luego dos propuestas del compilador que funciones se podría haber intentado llamar. Como nosotros no hemos escrito la función a que llamamos, sabemos que nuestra llamada debe ser mala.

El truco para descifrar este mensaje largo consiste en eliminar sucesivamente los parámetros de los patrónes (template parameters). Nos fijamos en la primera línea lo que está entre las comas altas (‘): std::map, std::allocator > >::insert(std::_Rb_tree_const_iterator >&, std::pair).

Empezamos a eliminar desde dentro de las paréntesis angulares < > todo lo que nosotros no hemos especificado en ningún sitio. Sí, correcto, simplemente lo borramos. Son parámetros por defecto que no nos interesan. Hemos definido una instancia de std::map. En el mensaje de error, estos dos parámetros de tipo string aparecen, pero luego seguido por un std::less que no hemos puesto en ningún sitio. ¡Así fuera! Lo mismo pasa con el std::allocator. Lo borramos. Haciendo esto nuestro mensaje de error queda más corto: std::map::insert(std::_Rb_tree_const_iterator >&, std::pair).

El método insert tiene dos parámetros. Correcto. El último, es realmente un std::pair, pero el primero es un _Rb_tree_const_iterator de que no sabemos de donde procede. Nuestro primer parámetro en un const_iterator. Pues bien, _Rb_tree_const_iterator contiene la palabra const_iterator y será un tipo interno para representar un iterador a constante a un mapa. ¿Pero por qué tree? Aquí nos ayuda saber que los contenedores asociativos (std::set, std::map, std::multimap) están internamente organizado como un árbol – que es un tree en inglés. Si sustituimos la palabra tree por map, entonces el primer parámetro del método insert tendra el tipo std::_Rb_map_const_iterator >. Como nuestro tipo de iterador no tiene parámetros de patrón, simplemente lo borramos y nos queda nada más que std::_Rb_map_const_iterator.

La primera línea del mensaje de error queda entonces en

std::map::insert(std::_Rb_map_const_iterator&, std::pair)

Esto se parece a la línea donde se produjo el error:

mi_mapa.insert(const_itr, std::pair("atributo", "valor"));

Este parecido entre si no es de extrañar, ya que el mensaje de error hace referencia justamente a esta llamada.

 

Ahora nos fijamos en la segunda línea que contiene una propuesta de función y la acortamos de la misma manera.

C:/opt/Dev-Cpp/include/c++/3.4.2/bits/stl_map.h:360: note: candidates are: std::pair<_Key, std::pair, std::_Select1st >, _Compare, _Alloc>::iterator, bool> std::map<_Key, _Tp, _Compare, _Alloc>::insert(const std::pair&) [with _Key = std::string, _Tp = std::string, _Compare = std::less, _Alloc = std::allocator >]

Primero eliminamos todo el texto de introducción hasta “candidates are:”. Luego eliminamos los _Compare y _Alloc que nosostros no hemos pedido y nos quedamos con esto:

std::pair<_Key, std::pair, std::_Select1st >>::iterator, bool> std::map<_Key, _Tp>::insert(const std::pair&) [with _Key = std::string, _Tp = std::string]

Recordamos que podemos reemplazar tree por map y renombamos _Rb_tree a _Rb_map. Los parámetros de patrón contiene un conjunto de tipos que no nos interesa, así simplemente lo quitamos y nos queda

std::pair std::map<_Key, _Tp>::insert(const std::pair&) [with _Key = std::string, _Tp = std::string]

Si nos ayuda podemos reemplazar _Key y _Tp por std::string como indica la última parte del mensaje. El nombre de espacio std y la palabra clave typename no nos aportan tampoco información, así los eliminamos también.

pair<_Rb_map::iterator, bool> map::insert(const pair&)

Finalmente vemos claro que la función propuesta es un método insert que tomo un tipo pair como entrada.

 

Hacemos el procedimiento a la tercera línea del mensaje de error.

C:/opt/Dev-Cpp/include/c++/3.4.2/bits/stl_map.h:384: note:                 typename std::_Rb_tree<_Key, std::pair, std::_Select1st >, _Compare, _Alloc>::iterator std::map<_Key, _Tp, _Compare, _Alloc>::insert(typename std::_Rb_tree<_Key, std::pair, std::_Select1st >, _Compare, _Alloc>::iterator, const std::pair&) [with _Key = std::string, _Tp = std::string, _Compare = std::less, _Alloc = std::allocator >]

Eliminamos los parámetros de patrones innecesarios, reemplazamos tree por map, sustituimos _Key y _Tp por std::string, y eliminamos std y typename. Y con esto llegamos a esta función propuesta:

_Rb_map::iterator std::map<string, string>::insert(_Rb_map::iterator, const pair&)

Esta propuesta ya se parece bastante a nuestra llamada

mi_mapa.insert(const_itr, std::pairstring, std::string>("atributo", "valor"));

Lo que es diferente es el primer parámetro: nosotros usamos un const_iterator mientras la función propuesta requiere un iterator sin const. Si cambiamos la línea

std::mapstring, std::string>::const_iterator const_itr = mi_mapa.begin();

por

std::mapstring, std::string>::iterator ya_no_const_itr = mi_mapa.begin();

entonces compila.

Entender a Microsoft Visual Studio

Como ejercicio puedes usar las mismas técnicas para entender el resultado de compilación del mismo código con Microsoft Visual Studio.

Error	1	error C2664: 'std::_Tree<_Traits>::iterator std::_Tree<_Traits>::insert(std::_Tree<_Traits>::iterator,const std::pair<_Ty1,_Ty2> &)' : no se puede convertir el parámetro 1 de 'std::_Tree<_Traits>::const_iterator' a 'std::_Tree<_Traits>::iterator'

error C2664: 'std::_Tree<_Traits>::iterator std::_Tree<_Traits>::insert(std::_Tree<_Traits>::iterator,const std::pair<_Ty1,_Ty2> &)' : no se puede convertir el parámetro 1 de 'std::_Tree<_Traits>::const_iterator' a 'std::_Tree<_Traits>::iterator'
1>        with
1>        [
1>            _Traits=std::_Tmap_traits,std::allocator>,false>,
1>            _Ty1=const std::string,
1>            _Ty2=std::string
1>        ]
1>        and
1>        [
1>            _Traits=std::_Tmap_traits,std::allocator>,false>
1>        ]
1>        and
1>        [
1>            _Traits=std::_Tmap_traits,std::allocator>,false>
1>        ]
1>        No hay disponible ningún operador de conversión definido por el usuario que pueda realizar esta conversión, o bien no se puede llamar al operador

Conclusión

Al inicio se pueden copiar los mensajes de error largos a un editor de texto y modificar ahí sucesivamente el mensaje hasta sólo queda la parte significativa. Con un poco de práctica, uno consigue hacer estas reducciones en la mente. La mayor parte del mensaje está “contaminado” por parámetros de patrones por defecto, que se necesitan por razones técnicas pero que no se usan como usuario de una clase.

La experiencia enseña también, que la mayoría de los errores son del mismo estilo: mezclar iterator y const_iterator o confundirse en los parámetros o valores de retorno de métodos sobrecargados.

Referencias

Muchas veces necesitamos reservar memoria dinámica durante la ejecución de un programa. Sin embargo, esto es un proceso relativamente lento, porque el sistema operativo debe buscar un hueco suficientemente grande en el heap, donde se almacenan los objetos dinámicos. Esto se nota, por ejemplo, cuando uno quiere reservar muchos elementos de una lista. En este artículo quiero presentar algunas propuestas, como lenguajes compilados ofrecen alternativas más veloces. Los ejemplos de código serán en C++.

Contenedores pueden instanciar varios elementos de golpe

El tamaño no importa (mucho) a la hora de reservar memoria. Es el número de veces que afecta más. Una primera posibilidad que se ofrece, por lo tanto, es reservar memoria para varios elementos de golpe. Por supuesto, esto es menos optimal respecto al uso de la memoria, pero una técnica ampliamente usado por los contenedores de la biblioteca estándar de C++ (STL).

Un contenedor puede usar el operador new[] estándar para reservar un array de, digamos, 10 elementos y luego gestionar, cuales elementos ya están en uso y cuales no. Esto puede ser relativamente complicado. Sin embargo, se puede hacer a medida para una clase contenedor y también cuando le haga falta. Por lo tanto, es una buena opción.

Sobrecargar el operador new.

Otra opción para una clase, que está ideada para instanciarse a menudo de forma dinámica, es sobrescribir el operador new (y delete) de esta clase. La implementación de este operador sobrecargado suele tener dos elementos. Primero usa el operador new global para pedir memoria al sistema operativo. Segundo, las instancias reservadas se gestionarán por unas variables estáticas de la clase. De esta forma, el depósito de elementos reservados no depende de una instancia en concreto – que es justamente lo que queremos.

El operador new global debe ser precidido por el operador :: para distinguirle del operador sobrecargado. Es decir new MiClase() llamaría al operador sobrecargado, mientras ::new MiClase() al sistema operativo. Si el operador no está sobrecargado, ambas notaciones tienen el mismo efecto. Lo mismo vale para el operador delete.

Separar reserva de memoria y construcción de instancia

La desventaja en pedir muchos elementos de golpe es que se llama el constructor por defecto para todos estos elementos aunque no se usan a priori. Pero a esto hay remedio, porque en C++ se puede separar la reserva de la memoria dinámica de la construcción de una instancia. Si, en lugar del tipo de la clase, reservo un array de char, entonces la reserva no llama a ningún constructor. Cuando quiero instanciar un nuevo elemento llamo al constructor mediante

void* operator new (std::size_t size, void* ptr) throw();

Esta versión del operador new no reserva memoria. Simplemente devuelve el puntero ptr. La manera de construir una instancia de la clase TElement en la memoria ya reservada apuntada por memory_ptr sería

*memory_ptr = * new ((TElement*) memory_ptr) TElement(*source_ptr);

Source_ptr podría ser otra instancia de la misma clase de donde copiar – es decir, la construcción arriba llamaría al constructor de copia. Los parámetros de new son tan variables como los parámetros de los constructores de la clase.

Para destruir un elemento sin liberar memoria llamo explícitamente a su destructor.


(MiClase* ptr)->~MiClase();

Reservar memoria en el stack

La forma más rápida es reservar memoria en el stack en lugar del heap. Esta reserva sucede cada vez que declaro una variable dentro de una función. Si sé que mi cadena de texto no tendrá más que mil bytes, entonces


char a[1001];

consiste en incrementar el puntero del stack, mientras


char* b = new char[1001];

en la búsqueda de un hueco lo suficientemente grande en el heap. La primera manera es muchísimo más rápida que la segunda. Teniendo en cuenta que la reserva dinámica puede, además, introducir errores de programación por olvidarse de liberar la memoria, es casi siempre preferible a ser generoso con la memoria RAM. Los ordenadores de hoy en día tienen de sobra.

Esta reserva en el stack se puede combinar con una gestión individualizada de la memoria. Dentro de mi clase puedo tener un miembro (posiblemente estático)


private: char _memory[1000];

Puedo convertirlo a un objeto de tipo TElement en la forma

TElement* element_ptr(void)
{
    return reinterpret_cast<TElement>(static_cast<char*>(_memory));
}

El static_cast no es obligatorio. Por la complejidad de la construcción conviene encapsularla en un método privado que convierte el almacén de memoria al tipo de clase requerido.

Hay implementaciones de la STL que usan esta técnica. Por ejemplo, la clase std::string contiene un búfer pequeño como miembro de la clase. Esto hace el almacenamiento de cadenas de textos cortos rápido. Si la longitud del string excede el tamaño del búfer, entonces se pide memoria dinámica.

Allocators

Los contenedores de la STL suministran otro mecanismo de cambiar la gestión de memoria mediante una clase allocator. Este allocator aparece como un parámetro en las plantillas de los contenedores. Aunque es una forma sofisticada de separar la gestión de memoria del funcionamiento del contenedor, aporta un problema nuevo: un contenedor con un allocator diferente no tiene el mismo tipo que un contendor con el allocator por defecto. Por lo tanto, dos instancias del mismo contenedor se comportan como dos contenedores distintos.

std::list<int, MiAllocator> miLista;
std::list<int> listaNormal;
listaNormal = miLista // Error: listaNormal y miLista no son de la misma clase

Sin embargo, los contenedores pueden interactuar al nivel de iteradores.

// Esto está permitido.
listaNormal.insert(listaNormal.begin(), miLista.begin(), miLista.end());

Si estás pensando en utilizar allocators personalizados, entonces considerar obligar el uso del contenedor modificado por toda la aplicación, por ejemplo utilizando un typedef que define un tipo de lista propia derivada de la STL.

Conclusión

Hemos visto varias formas de como hacer más rápida la creación de memoria dinámica. El incremento en velocidad se suele pagar por un uso menos óptimo de la memoria. Sin embargo, en la mayoría de los casos, no falta memoria. La gestión individual de la memoria es una tarea compleja y requiere cuidado. Un mal algoritmo para guardar, qué elementos reservados están en uso y cuales no, puede fácilmente acabar con la ventaja, que la administración propia de la memoria podría traer.

En C++ se puede separar la reserva de memoria de la construcción de instancias. La biblioteca STL permite utilizar gestores de memorias propias. Es una herramienta potente pero que puede traer complicaciones a la hora de mezclarla con contenedores con el gestor estándar.

Referencias

La Standard Template Library (STL) de C++ ofrece varios tipos de contenedores como vectores, listas y mapas. Sin embargo, no ofrece algunos contenedores que podrían resultar muy útiles para situaciones determinadas, sobre todo para simulaciones numéricas. Por su utilidad puede ser viable que uno mismo crea estos contenedores en lugar de crear clases particulares para cada tipo de elemento. En la biblioteca libre Boost ya se han incluido algunos de estos contenedores propuestos aquí.

Array multidimensional

Un array de un número de dimensiones variable puede ser útil para calcular tensores matemáticos o combinar datos de varias tablas en una base de datos. El índice en un array multidimensional sería un vector, es decir un array unidimensional, cuya longitud sería la dimensión N.

Una iteración sobre todos los elementos se podría hacer incrementando el primero componente del vector de índice hasta que llegara al número máximo permitido para la dimensión que representa. A continuación se incrementaría el segundo componente, reseteando el primero a cero. Al final el último componente (para la dimensión N) se pasaría por el número máximo permitido y la iteración se terminaría cuando el índice multidimensional sería el vector (0, 0, 0, … N).

Arrays bi- y tridimensionales

Estos arrays podrían ser una particularización de una array multidimensional. Teniendo en cuenta que tienen un uso bastante más frecuente para representar tablas (dos dimensiones) o funciones definidas en el espacio (tres dimensiones), implementaciones particulares podrían optimizar la velocidad.

Árboles

Aunque cada implementación del contenedor std::map usa internamente un árbol, no existe un contenedor árbol. Un árbol genérico permitiría un número variable de hijos en cada nodo. Esto quiere decir que cada nodo tendría un contenedor lineal (array o lista) de referencias a otros nodos.

Un árbol tan genérico podría ser limitado a un árbol binario si el contenedor de nodos hijos podría hacer referencia a dos nodos como máximo. Se podría implementar un árbol binario usando un árbol genérico, pero una implementación particular podría mejorar la velocidad de ejecución. Para el caso de un árbol binario podría valer la pena buscar el código de un std::map, ya que este contenedor implementa un árbol binario.

Un árbol unario, es decir, donde cada nodo sólo puede tener un hijo, sería una lista. Una lista ya existe en la STL como std::list.

Redes

La manera más genérica de entrelazar nodos es mediante un grafo representando una red. Cada nodo puede estar conectado con cualquier otro nodo – incluido él mismo. Como no hay manera de establecer un orden lineal en esta configuración, la única forma es usar otro contenedor como std::list que contiene los nodos y que permite iterar fácilmente sobre todos.

Cada nodo contendría un contenedor con referencias a otros nodos similar a un árbol genérico. Para quitar un nodo del conjunto, podrías usar dos estrategias:

  1. Iterar sobre todos los nodos y eliminar todas las referencias al nodo a eliminar. Esto sería lento porque requiere doble bucle anidado. Uno sobre todos los nodos (excluyendo el nodo a eliminar) y otro sobre todas las referencias en cada nodo.
  2. Guardar en cada nodo, qué otros nodos guardan una referencia a él – similar a una lista doblemente enlazada. Esto complica el modelo el nodo, pero es una estrategia mejor para redes grandes.

Contenedor de acceso aleatorio para una gran cantidad de datos

¿Qué tipo de contenedor usarías si quieres insertar un carácter en medio de un texto de un millón de caracteres? La clase std::string (array) me obligaría a copiar mucho texto para cada tecla que pulso. Una lista haría la inserción rápida pero copiar el texto entero eterno.

Una solución podría ser un contenedor cuyo modelo interior es un std::list<std::deque<> >. Insertar cualquier tamaño de datos causaría en dividir una deque existente en dos e insertar los datos nuevos como una nueva deque en medio. Como habría que dividir la deque existente en dos, se podría hacer una de las dos los suficientemente grande para albergar los datos nuevos y una parte de la vieja dividida. La otra parte sería acortada haciendo los elementos sobrantes inválidos – reduciendo el tamaño con size().

La parte más complicada sería la implementación del iterador de acceso aleatorio, ya que debería empezar a contar al principio de la lista, contando el número de elementos válidos en cada deque hasta llegar a la deque que contiene el índice requerido.

Métodos útiles para este contenedor sería compactar el contenido entero a una deque única o dividir el contenido en deques con un tamaño máximo.

Referencias

Array bidimensional

La Standard Template Library (STL) se llama a veces biblioteca estándar de C++ para distinguirla de la biblioteca estándar de C. Una de las herramientas que la biblioteca STL ofrece son contenedores. Un contenedor es un objeto que contiene un número variable de otros objetos. Todos estos objetos tienen el mismo tipo. Por ejemplo, un contenedor de enteros podría tener el tipo std::vector<int>. En lugar de int se podría poner cualquier otro tipo.

En particular, se podría usar otro contenedor como tipo de elemento. Un objeto de tipo std::vector<std::vector> > sería algo como un array bidimensional. Sin embargo, no sería lo mismo que un array de tipo int[x][y]. Esta última versión crea un array rectangular, es decir una matriz. La versión de std::vector crearía una array dinámico de arrays dinámicos, en que cada línea podría tener un número diferente de columnas – por lo cual se parece a los arrays multidimensionales del lenguaje de programación Java.

Iteradores

Desgraciadamente no hay un contenedor multidimensional en la STL. Una razón es probablemente la iteración sobre todos los elementos. Una tarea de programación común es hacer algo con cada elemento de un contenedor. Esto se hace típicamente en un bucle for del primer al último elemento. La STL ofrece clases especiales llamados iterator. Iteradores son objetos que se comportan como punteros y tienen, como estos, algunas de las siguientes propiedades.

  • Pueden delimitar un rango de valores apuntando al primer y al último elemento. (Más correctamente detrás del último elemento.) Los iteradores se inicializan típicamente con los métodos begin() y end() del contenedor.
  • Pueden acceder al elemento a que apuntan – típicamente con los operadores * y ->.
  • Pueden apuntar al elemento previo o siguiente – típicamente con los operadores -- y ++ de pre-fijo o post-fijo.

Estas operaciones están bien definidas para contenedores lineales, es decir contenedores en que los elementos están ordenados de una forma específica. Esto no quiere decir que estén ordenados lógicamente, por ejemplo números pequeños primero, sino que se puede diferenciar claramente un predecesor y un sucesor de cada elemento. Pero ¿cómo podemos establecer este orden en un array multidimensional? ¿Avanzar al próximo elemento es moverse una columna o una fila más allá?

Iterar sobre una colección multidimensional

Matemáticamente no hay un orden estricto en un espacio multidimensional. No obstante, para resolver nuestro problema de iteración sólo necesitamos cumplir lo siguiente: Una iteración completa pasa por todos los elementos exactamente una vez.

¿Qué quiere decir esto? Quiere decir que no importa si vamos fila por fila o columna por columna (o por cualquier otra forma) cuando un bucle de forma

for (iterator p = container.begin();
     p != container.end();
     ++p)
{
    // Do something with *p or p->
}

pasaría por todos los elemento del array. (Aquí igual te interesa por qué el incremento prefijo es más rápido que postfijo.)

Hay otro problema con los arrays multidimensionales en C++. Habitualmente nos gusta escribir algo como punto[x][y] para referirnos a un elemento en concreto del array punto. No obstante, no hay una método operator[][] que podríamos sobre cargar y el método operator[] sólo permite un parámetro.

Hay varias formas para afrontar este problema.

  • El método operator[] de un contenedor bidimensional podría exportar una referencia a un contenedor unidimensional que igualmente sobrecarga el método operator[]. Es una buena solución pero restringe la libertad de como implementar el contenedor multidimensional.
  • El método operator() permite un número arbitrario de parámetros. En lugar de punto[x][y] escribiríamos punto(x, y). Este sistema es una buena solución para contenedores de un número fijo de dimensiones.
  • Finalmente podríamos sobrecarga el método operator[] usando un índice multidimensional. En lugar de punto[x][y] o punto(x, y) escribiríamos algo como punto[array_index(x, y)]. No es una solución demasiado práctica pero la única aceptable para contenedores con un número de dimensiones variable. Aunque el índice multidimensional sería otra clase que deberíamos crear para este propósito, es probable que ya lo hayamos hecho a la hora de crear las clases de los iteradores para el array multidimensional.

Conclusión

Hemos repasado unos puntos a tener en cuenta a la hora de crear contenedores multidimensionales al estilo con la STL. Como puede llegar a ser laborioso conviene buscarse implementaciones ya hechas como el componente MultiArray de la biblioteca Boost.

Referencias

Categorías de conenedores de la STL
Elementos simples Elementos “aparejados”
std::vector std::map
std::deque std::multimap
std::list
std::set

Los contenedores de la Standard Template Library (STL) de C++ pueden dividirse en dos categorías. La mayoría de los contenedores acoge a elementos simples. Estos contenedores son vector, deque, list y set. Al contrario de los contenedores simples están los contenedores asociativos map y multimap que guaradan a una pareja (pair) de valores: una clave y un valor. Se llaman asociativos porque asocian claves con valores.

Internamente un mapa está implementado como un árbol binario que acoge un elemento simple de tipo pair<T_KEY, T_VALUE>. Desgraciadamente los árboles no son un elemento público de la STL aunque prácticamente todas las versiones los implementan.

Insertar

Un problema práctico con los contenedores asociativos es que insertar un nuevo elemento acaba en líneas muy largas. En lugar de escribir algo tan complicado como

std::map.insert(std::pair<T_KEY, T_VALUE>(my_key,  my_value));

preferiríamos un método

std::map.insert(my_key, my_value);

Desgraciadamente este método no forma parte del estándar. Una solución a este problema es crear una clase propia que hereda del mapa estándar. Esto trae la ventaja que podamos añadir tantas funciones que nos convienen y la desventaja que hay que escribir esta clase. Para hacerla completa debemos al menos ofrecer todos los constructores y métodos de operator=.

Nuestro nuevo método de insertar sería entonces algo así:

template <class T_KEY, class T_VALUE>
class Map : public std::map<T_KEY, T_VALUE>
{
    std::pair<iterator,bool> insert(const T_KEY& key, const T_VALUE& value)
    {
        return insert(std::pair<T_KEY, T_VALUE>(key, value);
    }
};

Operator[] para mapas constantes

Otra función práctica que muchas veces falta es el operator[](const T_KEY& key) para mapas constantes. La versión no constante crea un nuevo elemento para la clave si no existe. En un mapa declarado const no podemos hacer esto, pero podemos arriesgar una excepción. Está en manos del usuario del método de asegurar que sólo llama a operator[] const para claves existentes o capturar las excepciones. Aquí está el código:

template <class T_KEY, class T_VALUE>
class Map : public std::map<T_KEY, T_VALUE>
{
    template <class TKey, class TValue>
    const TValue& operator[](const TKey& key) const
    {
        // Esta línea causa una excepción cuando find devuelve end()
        return this->find(key)->second;
    }
};

Iteradores sólo sobre valores

Otra utilidad que falta son iteradores sólo sobre los valores del mapa, es decir un iterador cuyo operator* no devuelve un std::pair<T_KEY, T_VALUE> sino un T_VALUE. Uno puede conseguir esto escribiendo una clase value_iterator, que contiene el iterador de mapa habitual como elemento. Desafortunadamente esto conlleva mucho trabajo ya que será necesario implementar todas las funciones del iterador convencional – muy especialmente todos los operadores sobrecargados.

Conclusión

En fin, hemos propuesto algunas ideas de como se pueden ampliar contenedores estándar por métodos propios – en este caso el contenedor map. Conviene tener en mente que crear una clase propia que hereda de clases estándar es una manera más limpia de codificar que crear funciones globales, macros o simplemente copiar y pegar las expresiones complejas y feas que la interfaz del contenedor estándar nos obliga a tener.

Referencias

Creo que la palabra clave const aumenta bastante las emociones que uno podrá tener sobre C++: cuando es indudablemente un elemento para elevar el estilo de programación, también es uno que puede complicar bastante la compilación. En este artículo ponemos el enfoque más al por qué de usar entidades constante y como implementarlos en programas reales. He descrito en otro artículo de como y donde se puede usar la palabra clave const.

El compilador puede comprobar si un programa intenta modificar un valor constante. Declarar objetos constantes es, por lo tanto, una ayuda para detectar posibles errores en el código. Como es preferible detectar errores durante el tiempo de compilación – ya que el compilador hace el trabajo de encontrarlos – es en general preferible de programar código que cumple lo que se llama “const-correctness“. Además, la palabra const indica al lector del código que el programador intentó sólo leer de un valor. Sin duda, usar objetos constantes incrementa considerablemente la calidad y el estilo del código.

También es cierto que un programa funciona sin constantes. Por eso hay tendencia de no usarlas. Lo gordo viene cuando uno empieza a usarlas en un código que en general no lo usa. Esto puede causar errores de compilación hasta en la n-ésima llamada anidada a una función, que por alguna razón requiere que un valor no sea constante – aunque sólo lo lea y no lo escribe. Más aún fascinan los errores de la STL (Standard Template Library), que puede causar mensajes de error kilométricos que realmente quieren decir algo como “No puedo convertir el tipo const_iterator en iterator.” Como caramelito adicional hay métodos que sólo existen para un tipo de iterador. Por ejemplo, el operador [] del contenedor mapa sólo acepta un iterador a un mapa modificable.

¿Cómo podemos poner orden en el caos? Pues, básicamente en usar wrappers. En nuestro código usamos constantes de forma correcta. Si tenemos que llamar a una función que no podemos o queremos modificar, entonces convertimos los datos de la constante a una variable. El caso más simple sería una simple asignación.

const int constante = 5;
int parametro = constante;
funcion_sin_const_correctness(parametro);

Si no podemos copiar el valor, entonces podemos usar dos técnicas. Una es la de C mediante punteros.

const int constante = 5;
int& parametro_referencia = *(int*)(void*)(&constante);

La otra es con la expresión de C++ const_cast<TIPO>:

const int constante = 5;
int& parametro_referencia = const_cast<int>(constante);

Esta construcción está en el estándar explícitamente para quitar el const. Por lo tanto es la más comprensible a la hora de hacerlo. Aunque el const_cast se parece visualmente a un patrón (template), no lo es. Es una expresión nativa de C++.

Toma nota que no he puesto una copia de la constante al parámetro sino el parámetro es una referencia al valor. Esto puede ser preferible porque ahorra la llamada a un constructor de copia, pero también incrementa el riesgo que un programa erróneo escribe en la constante.

Lo más complicado suele ser convertir los iteradores de la librería estándar de C++, ya que un const_iterator no es lo mismo que un iterator declarado const. Son dos clases distintas que pueden tener diferencias internas importantes. En este caso no suele quedar otra que hacer apaños.

  • Podemos tener la suerte que en nuestra distribución de la librería estándar se puede construir un iterator con un const_iterator. Esto sería lo más fácil.
  • Podemos averiguar si continuamos con un puntero al objeto en lugar del iterador. Es decir algo como
    Contenedor<int>::const_iterator iterador_constante;
    int* puntero_parametro = &*iterador_constante;
    

    Podemos aprovechar que los punteros también son iteradores – al menos para contenedores de acceso aleatorio como vector y deque y arrays de C.

  • Es posible también que sólo necesitamos el valor del elemento que podemos entonces convertir como los variables y objetos constantes mencionados más arriba.
  • Si tenemos un bucle podemos estudiar si la variable del bucle será un iterator en lugar de un const_iterator.

Aún así puede haber el caso en que no podemos hacer nada más que abandonar la const-correctness. Esto sucede especialmente cuando hemos pasado un const_iterator como parámetro de función. En este caso nos consolamos en haber hecho lo máximo posible aunque no era lo máximo deseable.

En general es preferible usar const porque ayuda a mejorar el estilo del código y reduce errores a la hora ejecución. En la vida real nos podemos enfrentar a situaciones difíciles cuando actualizamos código viejo. Sin embargo, podemos intentar adaptar el mejor estilo posible en cada momento. No suele ser ventajoso mejorar el estilo de todo el código de golpe. Pero si lo mejoramos gradualmente en las partes que estamos tocando, acabamos tener actualizaciones de calidad sin necesidad de tocar código que ya funciona aunque tenga peor estilo.

En este artículo nos dedicamos como podemos usar constantes en C++. Hay otro artículo que trata de por qué conviene usar const.

A primera vista sorprende cuantas cosas pueden se constantes en C++. Se pueden declarar const

  • variables,
  • punteros o las variables a que apuntan (doblemente const),
  • referencias,
  • clases,
  • instancias de clases o
  • sólo miembros de datos dentro de una clase y también
  • métodos de una clase.

Para complicar la cosa aún más se puede usar const para sustituir enum y #define.

Variables constantes

Una variable declarada const no se puede cambiar, es decir, es una constante. No obstante, la palabra const sólo se tiene en cuenta durante el tiempo de compilación. El compilador emite un error cuando encuentra una instrucción que quiere asignar un valor a una constante, pero físicamente el valor de una constante puede estar guardado en la memoria RAM y cuesta poco asignar otro valor a esta posición mediante un uso malintencionado de punteros y casts.

Cuando un compilador optimiza el código ejecutable, entonces puede optar por no leer el valor de la memoria sino incrustarlo directamente en las instrucciones del procesador. Así es posible que el valor en la memoria RAM cambie pero el programa sigue con el valor que el compilador determinó durante la compilación. No obstante, la dirección de la constante sigue siendo válida aunque el ejecutable no lee de ahí.

Tener una representación física en la memoria es lo que distingue una variable declarada const de constantes definidas por enum o #define. Es decir, puedo hacer esto

const int c = 5;
const int* p = &c;  // p apunta a la dirección de c. *p vale 5.

pero no puede hacer esto

enum { CONSTANTE_ENUM };
const enum* pe = &CONSTANTE_ENUM // Error de compilación

Esto es porque una constante de enum sola no tiene tipo sino sólo representa un valor. Lo que convierte un enum en un tipo es el conjunto de los valores de que está formado.

La cosa es aún más complicada con los #define. Es una directiva del preprocesador que reemplaza un texto por otro antes de que el código llegue al compilador. Quiere decir, los nombres de las macros definido por #define no existen para el compilador.

#define CONSTANTE 5
int a = CONSTANTE;  // El compilador ve "int a = 5".

Punteros

Los punteros son variables que guardan una dirección de memoria. Como cualquier variable su valor puede ser constante o no. Los punteros son especiales por no tener sólo un tipo de qué son – una dirección de memoria – pero por tener también otro tipo asociado del valor a que apuntan. Y este valor puede ser constante o variable de forma independiente. Por este motivo puede haber dos const en la definición de un puntero.

      int        variable = 1;
const int        constante = 2;
const int *      puntero_a_constante = &constante;
      int *const puntero_constante_a_variable = &variable;
const int *const puntero_constante_a_constante = &constante;
  • El puntero_a_constante puede apuntar a varios objetos, pero no puede modificarlos. Cadenas de caracteres se definen típicamente así: como const char*.
  • Un puntero_constante_a_variable puede modificar el objeto a que apunta, pero no puede apuntar a otra cosa.
  • Finalmente, un puntero_constante_a_constante ni puede modificar el objeto a que apunta ni apuntar a otro objeto. Por este punto de vista una cadena de texto hardcoded tiene realmente el tipo const char *const. Sin embargo, se usa poco.

Como nota quiero decir también que existe la notación

      int const* puntero

pero se usa menos. De hecho no conviene usarlo porque es más ambiguo: ¿el const se refiere al tipo (int) o a la dirección de memoria (el “*”)?

Referencias

Para las referencias valen básicamente las mismas reglas que para punteros. No obstante hay una importante diferencia: referencias no pueden referirse a otra instancia. Al contrario de punteros las referencias no pueden existir por si mismas sino deben inicializarse a la hora de ser declarada.

      int        variable = 1;
const int        constante = 2;
const int &      referencia_a_constante = constante;

// &const es permitido pero innecesario. Por eso nunca se usa.
      int &const referencia_constante_a_variable = variable;
const int &const referencia_constante_a_constante = constante;

Como las referencias apuntan al mismo objeto durante toda su vida, & y &const es lo mismo, y por eso nunca se escribe &const.

Es fácil hacer un cast para convertir un puntero de un objeto a otro objeto con un tipo diferente. Las referencias, en cambio, tienen el mismo tipo que el objeto a que se refieren y aportan más seguridad contra un cast implícito.  Por eso es preferible usar referencias en lugar de punteros siempre cuando sea posible.

Muy especialmente conviene usar referencias a constantes en lugar de constantes como parámetros de funciones. Se usan igual pero sólo requieren copiar un puntero en lugar de un objeto entero. Es decir, no se llamará un constructor para una referencia.

Clases constantes

Igual como se puede convertir un tipo simple como int a constante, se puede declarar const a una estructura compleja. La construcción const MiClase convierte todos los miembros de esta instancia en constantes. Sólo se les pueden asignar un valor en el constructor y después ya no. Se puede forzar una excepción para un campo en la clase declarándolo mutable, pero en general hay poca razón de hacerlo.

También es posible declarar campos individuales constantes dentro de una clase. Por ejemplo, puedo crear una clase que guarde una posición como una posición inicial constante y un desplazamiento variable.

class MiSitio
{
    double desplazamiento;          // una variable
    const double posicion_inicial;  // una constante
};

El valor de posicion_inicial sería asignado en el constructor de la clase y se quedaría inmodificable durante la vida de la instancia. No obstante, cada instancia puede tener otro valor para posicion_inicial. Por lo tanto un miembro constante no es los mismo que una constante global y común a todas las instancias.

Lo que queda por hacer constante son los métodos de una clase. Métodos constantes “prometen” de no modificar ningún dato dentro de la clase. (Más correctamente ninguno que no sea mutable.) Son los únicos métodos que puedo llamar para una instancia constante.

class MiCosa
{
public:
    int mi_variable;

    void mi_metodo_constante() const
    {
        mi_variable = 0;  // Error de compilación.
        // No debo modificar campos en un método constante.
    };

    void mi_metodo_variable()
    {
        mi_variable = 0;  // Ok
    };
};

const MiCosa cosa;
cosa.mi_metodo_constante();  // Ok
cosa.mi_metodo_variable();   // Error de compilación.
// No puedo llamar a un método NO constante para un objeto constante.

Para complicar la cosa aún más, se pueden definir dos métodos iguales en que una es constante y la otra no. Es algo que usa mucho para los métodos que devuelven iteradores de inicio y final en los contenedores de la STL.

iterator begin(void);
const_iterator begin(void) const;

El método constante devuelve un iterador (puntero) a un objeto constante, mientras la versión variable devuelve un iterador a un objeto variable.

Conclusión

La palabra clave const no es fácil de entender, porque se usa en muchos conceptos. Sin embargo, es la pieza que permite a C++ de ser uno de los pocos lenguajes a conseguir la “const-correctness“. Esta a su vez significa que ya el compilador puede comprobar que no se asigna un valor a algo que sea de sólo lectura. Aunque muchos programadores hacen caso omiso al const, conviene tener una noción de ellos cuando uno trabaja con la STL, ya que muchos errores de compilación (que suelen tener un mensaje largo) se deben a confundir iterator con const_iterator.

Aquellos que buscan más motivación puedo recomendar el artículo “Por qué usar const en C++“. Pero también hay consuelo para quienes buscan la manera de esquivar las constantes: puedo eliminar cualquier const con const_cast.

Lectura adicional

La STL (Standard Template Library) de C++ ofrece dos contenedores muy similares: el famoso std::vector y la poco usada std::deque (Double Ended Queue = cola doblemente terminada). Ambos contenedores ofrecen acceso aleatorio a un bloque de memoria continuo. Es decir, son arrays.

¿Qué es la diferencia? El concepto de un vector es un array con un inicio fijo y un fin variable. Una deque es un array con tanto el inicio como el fin variable. Por eso, el contenedor deque es útil cuando quiero tener un acceso aleatorio como en un vector, pero poder insertar delante el índice cero o eliminar elementos al inicio.

Tanto el vector como la deque son contenedores de acceso aleatorio. Sin embargo, internamente tienen una diferencia importante: un vector garantiza que los elementos están guardados en una memoria continua. Es decir, puedo usar un puntero como iterador. De hecho muchas implementaciones usan punteros como iteradores sobre vectores. La deque a contrario no garantiza guardar los elementos en una memoria contigua. Se puede implementar como un vector con un puntero variable al primer elemento del array. Pero el estándar no lo impone. Se puede implementar también, por ejemplo, como dos vectores – uno creciendo hacia indices más altos, el otro creciendo hacia “abajo” para insertar elementos al inicio del contenedor.

Otra diferencia está en los elementos que se reservan de más. Ambos contenedores tienen el método size() que devuelve el número de elementos válidos en el contenedor, pero sólo vector tiene el método capacity(), que devuelve el número de elementos reservados en la memoria.

Por ejemplo, si el método size() de un vector devuelve cinco, entonces mi array aparenta tener el tamaño cinco. Si el método capacity() de la misma instancia de vector devuelve ocho, entonces habrá memoria reservada para ocho elementos. Si añado un sexto elemento al final del vector, la operación es muy rápida, ya que no hace falta reservar más memoria para el un nuevo objeto: el elemento ya existe físicamente y sólo hace falta construirlo con los datos para el nuevo elemento.

Esta reserva de memoria ayuda a mejorar la velocidad cuando añado elementos a un contenedor. Si no fuera así, el contenedor debería reservar memoria para n+1 elementos, copiar los n que ya tiene y escribir el último al final cada vez cuando añado un elemento nuevo. Por eso los contenedores de la STL pueden reservar memoria para más elementos que corresponde a su tamaño.

Se puede forzar la capacidad mínima de un vector con el método reserve(). El contenedor deque no tiene esta característica. (La deque debería tener un método reserve_front() y reserve_back()para esto, pero esto la STL no lo ofrece.)

Por lo tanto, si quiero añadir a un array ya existente un número de elementos conocidos a priori con el método push_back(), es ventajoso usar un vector. No obstante, si ya conozco el número de elementos a la hora de creación del contenedor no tengo esta limitación. Tanto el vector como la deque tienen un constructor que especifica el número de elementos iniciales. Y lógicamente puedo llamar al método resize() en cada momento para especificar el número de elementos en ambos contenedores.

Compara

std::vector vec;
vec.reserve(numero_de_elementos);
for (int i = 0; i < numero_de_elementos; ++i)
{
    vec.push_back(nuevo_elemento);
}

con

std::vector vec2;
vec2.resize(numero_de_elementos);
for (int i = 0; i < numero_de_elementos; ++i)
{
    vec2[i] = nuevo_elemento;
}

La primera versión con reserve() es más flexible cuando quiero sustituir el vector por una lista. Aún así la mayoría de los programadores usaría la segunda forma con resize() que funciona tanto para la deque como el vector.

La limitación de un vector se manifiesta cuando quiero eliminar i elementos del principio. Como su inicio es fijo y el elemento con el índice i será el nuevo con el índice 0, debo copiar todos los elementos de i a n para que ocupen el rango de índices 0 a n-i. El contenedor deque, en cambio, no necesita borrar los elementos. Simplemente sube un puntero al primer elemento en i posiciones y invalida así los elementos a borrar. Estos elementos se quedan en la memoria para ser reciclados si se añadieran nuevas elementos al principio.

La deque requiere un poco más de gestión por tener el inicio variable, pero teniendo en cuenta que la mayor parte del trabajo de un contenedor es trabajar con los elementos y no con el contenedor mismo, la diferencia es mínima. Por lo tanto, conviene optar por una deque siempre y cuando no esté asegurado que no se quieren eliminar elementos del inicio del array.

Un vector es la elección si quiero reservar un número de elementos conocido después de la creación del contenedor, ya que puedo aprovecharme del método reserve() que la deque no tiene. Sin embargo, la reserva previa de elementos se puede sustituir muchas veces por una construcción con resize().

Pero tampoco hay muchas ocasiones en que necesito añadir elementos al principio de un array. Por lo tanto no extraña que la deque es menos conocida que el vector: simplemente se necesita poco. Pero conviene saber de su existencia.

Escribe tu dirección de correo electrónico para suscribirte a este blog, y recibir notificaciones de nuevos mensajes por correo.

Únete a otros 51 seguidores

Archivos

agosto 2018
L M X J V S D
« Abr    
 12345
6789101112
13141516171819
20212223242526
2728293031