Diccionarios (Map)

• Conocimientos mínimos: nociones básicas de complejidad
• Recomendamos leer primero el artículo sobre conjuntos.

Ya discutimos la importancia de poder representar conjuntos de manera que insertar, remover y buscar un elemento sean operaciones efectuadas rápidamente. Sin embargo, un conjunto no siempre es suficiente para nuestras necesidades.

Por ejemplo, supongamos que tenemos un diccionario en el que cada palabra válida tiene una definición y un usuario puede ir agregando y quitando palabras junto con la definición de cada una. Además, en cualquier momento nos pueden pedir que imprimamos la definición de una palabra. Queremos que todas estas operaciones sean realizadas rápidamente.

Si bien es posible modelar esto como un conjunto de pares (palabra, definición), es poco descriptivo y sería mejor tratar de usar una estructura pensada para este uso en particular. Como este problema es tan importante, la estructura que lo modela se llama diccionario. Para generalizar los nombres, llamaremos clave a la palabra a definir y valor a su definición. Así, para cada clave existe un valor asociado a ella. Por ejemplo, para la clave árbol, el diccionario nos devolverá el valor “Planta perenne, de tronco leñoso y elevado, que se ramifica a cierta altura del suelo.”

La estructura que modela diccionarios en C++ se llama map. Debido a su uso tan extendido, es muy usual decir que la clave casa “mappea” al valor “Planta perenne, de tronco leñoso y elevado, que se ramifica a cierta altura del suelo.”.

Los diccionarios son usados en varios contextos, no solo en el que dio origen a su nombre. Por ejemplo, en un texto enorme podemos querer saber cuántas veces aparece cada palabra en él. Podemos pensar en un diccionario en el que cada palabra que aparezca en el texto sea una clave y su número de repeticiones sea el valor. Así, a medida que vayamos recorriendo el texto iremos agregando las palabras nuevas (con cantidad de repeticiones igual a 1) e iremos incrementando la cantidad de repeticiones de las palabras que ya hayan aparecido anteriormente.

Si bien tal vez no asociemos la palabra inglesa map con este significado, es importante notar que en computación se utiliza la palabra map para significar “asociar una clave a un valor”. Para poder utilizar maps en C++ debemos incluir su biblioteca así: #include <map>.

Para crear el map debemos indicar de qué tipo será la clave y de qué tipo será el valor. Usaremos de ahora en más el segundo ejemplo visto, en el que la clave será una palabra y su valor la cantidad de repeticiones de la misma.

map<string, int> dicc;

Insertar un par (clave, valor) en un map es lo mismo que en un array.

dicc["arbol"] = 1;

Este código agrega la clave arbol con valor 1. Notar que si antes existía esta clave con otro valor, dicho valor se sobreescribirá. Más claramente,

dicc["arbol"] = 2;
//...
dicc["arbol"] = 1;

sólo guardará la asociación entre arbol y el número 1, y se olvidará que alguna vez estuvo asociado al número 2.

Una propiedad interesante de los map es que si la clave no existe, se la inicializa con algún valor default. Por ejemplo, en el caso de los enteros, se inicializa el valor en cero. Esto quiere decir que el siguiente código tiene sentido aún si la clave casa no existía antes.

dicc["casa"]++;

Si la clave casa existía anteriormente, simplemente incrementará en uno la cantidad anterior. Si la clave casa no existía, se creará con 0 repeticiones y luego se incrementará en 1, dejando la clave casa con un valor asociado de 1. ¡Usen esta propiedad con cuidado! Puede llevar a errores en el programa si no se usa adecuadamente.