06 · Conjuntos, mapas y pares
Aprender a programar · Ruta de Aprendizaje
Antes de empezar. Variables, strings y ciclos: 00 - Programar desde cero. Para el ejemplo con una lista de pares, también vector: 03 - Arreglos y búsqueda lineal.
🎯 Objetivos
Al terminar este módulo sabes:
- Crear un
pair, leer sus dos componentes y entender cómo se comparan. - Usar
setpara “¿ya lo vi?” y contar distintos. - Usar
mappara contar frecuencias y asociar llave → valor. - Elegir qué información conservar según las preguntas del problema.
📖 La lección
pair: dos datos que forman una unidad
Imagina que guardas el nombre y la edad de una persona. Son dos datos de
tipos distintos, pero pertenecen a la misma persona. pair<T, U> los
reúne en un solo valor: T es el tipo del primero y U el del segundo.
pair<string, int> persona = {"Ana", 12};
cout << persona.first << " " << persona.second << "\n"; // Ana 12
persona.second++; // ahora guarda {"Ana", 13}Las llaves {...} dan los valores iniciales. .first accede al primer
componente y .second al segundo. Esos nombres no significan siempre
«nombre» y «edad»: tú decides qué representa cada posición. En
pair<int, int> casilla = {2, 5}, pueden representar fila y columna.
Un par tiene exactamente dos componentes; una lista de tamaño variable
se representa con un vector.
Si el diagrama no cabe, deslízalo horizontalmente.
También puedes guardar varios pares en un vector:
vector<pair<string, int>> personas = {{"Ana", 12}, {"Luis", 14}};
cout << personas[1].first << "\n"; // Luispersonas[1] elige el segundo par; .first elige su primer componente.
Así el nombre y la edad se mantienen juntos al mover u ordenar el registro.
Al comparar dos pares se compara primero .first; solo si empatan se
compara .second. Por ejemplo, (2, 5) < (3, 1) y (2, 5) < (2, 8).
Una pregunta, tres formas de guardar datos
Para una lista de nombres, podrías necesitar conservar cada registro,
saber quién apareció o contar cuántas veces apareció cada persona.
pair agrupa datos; set y map guardan colecciones y responden preguntas
distintas. Veamos qué conserva cada una.
set: elementos únicos, siempre ordenados
Partimos de un conjunto vacío. vistos.insert(4) guarda el 4;
repetir esa inserción deja un solo 4. vistos.count(4) responde 1
(presente) y vistos.count(7) responde 0 (ausente). Ahora repetimos esas
operaciones para cada dato de la entrada:
// supone: int n; // cuántos números vienen
set<int> vistos;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (vistos.count(x)) cout << x << " es repetido\n";
vistos.insert(x); // si ya estaba, no pasa nada: el set no repite
}
cout << "distintos: " << vistos.size() << "\n";Si llegan 4, 4, 7, 4, el conjunto termina como {4, 7}. count(4)
es 1, aunque el 4 haya llegado tres veces: en un set, count responde
si existe (1) o no existe (0). size() da la cantidad de valores distintos.
erase(4) borra el 4 si está; si no está, no cambia nada.
Recorrerlo visita sus valores de menor a mayor, no en orden de llegada.
Los elementos también pueden ser pares. Para contar casillas distintas:
set<pair<int, int>> casillas;
casillas.insert({2, 5});
casillas.insert({2, 5}); // misma fila Y misma columna: no se repite
casillas.insert({2, 8}); // otra casilla, aunque comparta fila
cout << casillas.size() << "\n"; // 2La igualdad considera ambos componentes. Su recorrido será (2, 5),
(2, 8), siguiendo la comparación de pares que acabamos de ver.
map: de llave a valor
Un map<llave, valor> asocia cada llave con un valor. En
map<string, int>, la llave puede ser una palabra y el valor su frecuencia.
Cada entrada reúne ambos datos como un par: .first es la llave y
.second su valor. A diferencia de un conjunto, podemos actualizar el
contador de una palabra sin crear otra llave.
Vamos a contar frecuencias:
// supone: int n; // cuántas palabras vienen
map<string,int> veces;
for (int i = 0; i < n; i++) {
string palabra;
cin >> palabra;
veces[palabra]++; // si no existía, parte en 0 y suma 1
}
for (pair<string,int> par : veces) // cada elemento del map ES un par
cout << par.first << ": " << par.second << "\n";veces[x] crea la entrada con 0 si no existe — por eso veces[x]++ funciona
directo. Recorrer un map lo entrega ordenado por llave.
En el for, par es una copia de cada entrada; imprimirla sirve para
consultarla, pero cambiar par.second no cambia el mapa. Para actualizar
una frecuencia, usamos veces[palabra].
Consultar con [] también puede insertar. Si "chau" no estaba,
leer veces["chau"] crea esa llave con valor 0. Si solo quieres saber si
existe, usa veces.count("chau"): devuelve 0 o 1 sin modificar el mapa.
No confundas esa presencia con la frecuencia almacenada. veces.size()
cuenta llaves distintas, y veces.erase("chau") elimina la entrada completa.
Si el diagrama no cabe, deslízalo horizontalmente.
Sigue la traza del contador con la entrada hola chao hola ok hola ok:
| palabra leída | veces[palabra]++ deja | el map completo (ordenado por llave) |
|---|---|---|
| hola | hola → 1 | {hola: 1} |
| chao | chao → 1 | {chao: 1, hola: 1} |
| hola | hola → 2 | {chao: 1, hola: 2} |
| ok | ok → 1 | {chao: 1, hola: 2, ok: 1} |
| hola | hola → 3 | {chao: 1, hola: 3, ok: 1} |
| ok | ok → 2 | {chao: 1, hola: 3, ok: 2} |
Por eso el ciclo final imprime chao: 1, hola: 3, ok: 2 — en orden
alfabético, aunque las palabras llegaron en otro orden.
Con una misma entrada hola chao hola ok hola ok, un vector conserva las seis palabras en ese orden; un conjunto conserva {chao,hola,ok}; un mapa de frecuencias conserva {chao:1,hola:3,ok:2}. El conjunto permite saber quién apareció; solo el vector recuerda cuándo y solo el mapa de frecuencias resume cuántas veces.
¿Cuál uso?
| Necesito… | Estructura |
|---|---|
| saber si algo ya apareció | set |
| contar cuántas veces aparece cada cosa | map<llave,int> |
| guardar dos datos como una unidad | pair<T, U> |
| solo recorrer en orden de llegada | vector |
Como referencia de rendimiento, insertar, buscar y borrar en set y map ordenados cuesta O(log n) comparaciones; esa notación se desarrolla en 07 - Cuánto se demora tu programa. Además, comparar strings también depende de su longitud. Un pair solo agrupa dos valores: no es una colección con búsquedas O(log n). Si quieres
ver cómo funcionan por dentro y la lista completa de operaciones, cada una
tiene su página: set y multiset y map (clave-valor) — o todas juntas
en el Catálogo de estructuras. (Existen también versiones “sin orden” que
prometen ser más rápidas, unordered_set y unordered_map, pero traen una
trampa: mejor conocerlas después de dominar estas.)
🏋️ Práctica
Práctica directa: Frecuencias de palabras
Lee n (1 a 100) y n palabras. Imprime cada palabra distinta y su frecuencia, en orden alfabético. Entrada: 4 / sol luna sol sol. Salida: luna 1 / sol 3.
En los ejemplos de entrada y salida, / separa líneas; no se escribe en el archivo.
Idea para comprobar tu solución
El mapa conserva la frecuencia y ordena por llave. Un set no podría recuperar el 3.
Variación: Contar sin perder el orden pedido
Lee n códigos enteros (1 ≤ n ≤ 100000, códigos entre 0 y 10⁹). Imprime cada código distinto y su frecuencia, en orden creciente de código. Para 8 2 8 9 2 8, las parejas son 2 2, 8 3, 9 1.
Una pista, si la necesitas
Distingue el número de códigos distintos del total de apariciones.
Contrastar el razonamiento
Un mapa de frecuencias conserva ambas cosas. Un set perdería las repeticiones. También puedes ordenar un vector y contar cada bloque de iguales; compara tiempo y memoria de las dos opciones.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Reacciones | Nacional 2022 | contador por letra con map |
| 2 | Cuenta de goles | Regional 2025 | sets para separar lo seguro de lo ambiguo |
| 3 | El lokómon de Olivier | Regional 2022 | sets de valores prohibidos y filtrado |
| 4 | ⭐ Sistemas interestelares | Nacional 2015 | frecuencias con ids gigantes (el arreglo no alcanza) |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Boy or Girl (236A) | ★ (800) | caracteres distintos con set |
| 2 | Andryusha and Socks (780A) | ★★ (800) | set como “cajón abierto/cerrado” |
| 3 | ⭐ Registration System (4C) | ★★★ (1300) | map<string,int> en vivo |
| 4 | ⭐ Same Differences (1520D) | ★★★ (1200) | desafío para elegir la representación |
Un ejemplo para pensar
El mapa contiene {chao:1,hola:3,ok:2}. ¿Qué diferencia hay entre consultar veces.count("nuevo") y leer veces["nuevo"]? ¿Cambia size()?
Compara el código y predice su salida antes de ejecutarlo:
map<string, int> veces = {
{"chao", 1}, {"hola", 3}, {"ok", 2}
};
int existe = veces.count("nuevo");
cout << existe << " " << veces.size() << "\n";
int frecuencia = veces["nuevo"];
cout << frecuencia << " " << veces.size() << "\n";Una lectura que modifica la colección
countdevuelve 0 y conserva las tres llaves.[]insertanuevocon frecuencia 0 y devuelve ese cero: ahorasize()vale 4. Una llave presente con contador cero no significa que esa palabra apareciera en la entrada. Para consultar presencia sin insertar, usacountofind.
← 05 - Ordenamiento · Ruta de Aprendizaje · 07 - Cuánto se demora tu programa →