std::mapDocente: Tomás Assenza
Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe
std::map? Del Índice a la Clave• 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).
• 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.
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".
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)
[] 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.
Para verificar si una clave existe sin insertarla, usá siempre if (mapa.count(clave)) (que devuelve 1 si está o 0 si no está).
// 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)
}
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;
}
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.
"Para un conjunto de N palabras, contar la frecuencia de cada una. Luego, responder M consultas con la frecuencia de la palabra correspondiente."
#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;
}
}
std::map
Ya sabés asociar claves a valores y contar frecuencias con std::map. Pasemos a conjuntos sin repetidos con std::set.