OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Diccionarios (Map) ======

  * **Conocimientos mínimos**: nociones básicas de complejidad
  * Recomendamos leer primero [[cpp-avanzado:set|el artículo sobre conjuntos]].

===== Motivación =====

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. 

===== Implementación en C++ =====

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>''.

==== Crear un diccionario ====

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.

<code cpp>
map<string, int> dicc;
</code>

==== Asignar valor a una clave ====

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

<code cpp>
dicc["arbol"] = 1;
</code>

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,

<code cpp>
dicc["arbol"] = 2;
//...
dicc["arbol"] = 1;
</code>

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.

<code cpp>
dicc["casa"]++;
</code>

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.

==== Remover una clave y su valor asociado ====
FIXME
==== Buscar una clave ====
FIXME

==== Buscar la clave más cercana a cierto elemento =====
FIXME
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
