Hub Taller STL
Taller de Estructuras Dinámicas (STL) • Módulo 2

std::map
Diccionarios y Pares Clave → Valor

Docente: Tomás Assenza

Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe

¿Qué es std::map? Del Índice a la Clave

Conceptos Generales

• El acceso sigue siendo mediante [], pero se cambia el concepto de índice numérico por clave.

• A cada clave existente en un mapa le corresponde un único valor asociado.

• Las claves no necesitan ser valores consecutivos y pueden ser de cualquier tipo (string, int, char).

Orden Automático

• El mapa mantiene sus elementos automáticamente ordenados por sus claves de forma lexicográfica (o de menor a mayor).

• Cada acceso o inserción en map cuesta O(log N).

• Si no necesitamos orden, existe unordered_map que opera en O(1) promedio mediante hashing.

.first: "algoritmos"
12 .second (valor)
.first: "c++"
45 .second (valor)
.first: "stl"
28 .second (valor)
.first: "utn"
99 .second (valor)

Declaración, Inicialización y Acceso

Incluimos la cabecera: #include <map>


// 1. DECLARACION
// map<tipoDeDatoClave, tipoDeDatoValor> nombreDelMapa;
map<string, int> nombreDelMapa; // Mapa con 0 elementos

// 2. INICIALIZACION CON PARES {clave, valor}
map<string, int> edades {
    {"Ana", 20},
    {"Bruno", 22},
    {"Carla", 19}
}; // Mapa con 3 pares clave-valor (ordenados por clave)

// 3. ACCESO Y MODIFICACION DE ELEMENTOS
edades["Bruno"] = 23; // Modifica el valor asociado a "Bruno"
edades["Diego"] = 21; // Como "Diego" no existia, el mapa aumenta en 1
                      // su tamaño y asocia el valor 21 a la clave "Diego".
                    

Funciones Integradas de std::map


map<int, int> mapa1 { {1, 10}, {2, 20}, {3, 30} };
map<int, int> mapa2 { {4, 40}, {5, 50}, {6, 60} };

// empty() y size():
cout << mapa1.empty(); // Imprime 0 (false)
cout << mapa1.size();  // Imprime 3

// Intercambiar contenidos de dos mapas:
mapa1.swap(mapa2);
// mapa1 pasa a tener los pares de mapa2 y viceversa

// Consultar si una clave existe sin crearla:
cout << mapa1.count(4);  // Devuelve 1 (existe)
cout << mapa1.count(99); // Devuelve 0 (no existe)
                            

Detalle clave sobre [] vs count()

Si hacés if (mapa["hola"] == 0) para ver si una clave existe, el operador [] crea automáticamente la clave "hola" con valor 0 y agranda el mapa.

Buena práctica

Para verificar si una clave existe sin insertarla, usá siempre if (mapa.count(clave)) (que devuelve 1 si está o 0 si no está).

Comparación y Recorrido de Mapas

1. Comparación Puntual vs Total


// Comparar el valor de una clave puntual
// contra el valor de otra:
if (mapa1["clave1"] == mapa2[5]) {
    // Compara solo los valores devueltos por []
}

// Comparar dos mapas del mismo tipo completo:
if (mapa1 == mapa2) {
    // True si tienen igual tamaño y coinciden
    // todos sus pares (clave, valor)
}
                            

2. Recorrido por Elementos (pair / auto)


// Forma explicita con pair<Clave, Valor>:
for (pair<string, int> elemento : mapa1) {
    cout << "clave: " << elemento.first
         << " valor: " << elemento.second << endl;
}

// Forma abreviada con auto (recomendada):
for (const auto &elemento : mapa1) {
    cout << "clave: " << elemento.first
         << " valor: " << elemento.second << endl;
}
                            

Ejemplo de Aplicación: Tendencias

Práctica Map

Twitter es una red social que permite a los usuarios enviar mensajes públicos de hasta 240 caracteres. Generalmente dentro de la red se generan "tendencias" gracias a un análisis que hace la plataforma sobre la cantidad de ocurrencias de una palabra durante un período determinado.

Como sos un ingeniero en sistemas de la UTN - FRSF (y, obviamente, un apasionado de los Algoritmos y Estructuras de Datos), decidiste trabajar ahí. Para iniciar, te solicitaron que generes un sistema que reciba un número N de palabras (con repetidas entre ellas), y un número M de consultas. Para cada consulta, deberás indicar cuántas apariciones tiene cada palabra.

Antes de resolver, simplificamos el problema:

"Para un conjunto de N palabras, contar la frecuencia de cada una. Luego, responder M consultas con la frecuencia de la palabra correspondiente."

Resolución Paso a Paso: Frecuencia de Palabras


#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
    map<string, int> frecuencias;
    int n, m;
    string palabra;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> palabra;
        frecuencias[palabra]++;
    }

    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> palabra;
        cout << frecuencias[palabra] << endl;
    }
}
                        

Laboratorio en Vivo: Tendencias con std::map

OneCompiler - C++ Sandbox (Ejecutá o modificá las consultas)

¡Fin del Módulo 2!

Ya sabés asociar claves a valores y contar frecuencias con std::map. Pasemos a conjuntos sin repetidos con std::set.

Módulo 1: std::vector Volver al Hub Ir al Módulo 3: std::set