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 set para “¿ya lo vi?” y contar distintos.
  • Usar map para 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.

pair<string, int> persona = {"Ana", 12}"Ana"12persona.firstpersona.secondprimer componente: stringsegundo componente: int

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"; // Luis

personas[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"; // 2

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

set<int> vistossiempre ordenado, sin repetidos25914insert(5)ya estaba: no pasa nadainsert(7)entra entre el 5 y el 9map<string,int> vecescada llave, una sola vez, con su valor"chao"1"hola"3"ok"2llavevalorveces["ok"]++ suma 1 al valor de "ok"; si la llaveno existía, primero nace con valor 0

Si el diagrama no cabe, deslízalo horizontalmente.

Sigue la traza del contador con la entrada hola chao hola ok hola ok:

palabra leídaveces[palabra]++ dejael map completo (ordenado por llave)
holahola → 1{hola: 1}
chaochao → 1{chao: 1, hola: 1}
holahola → 2{chao: 1, hola: 2}
okok → 1{chao: 1, hola: 2, ok: 1}
holahola → 3{chao: 1, hola: 3, ok: 1}
okok → 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 cosamap<llave,int>
guardar dos datos como una unidadpair<T, U>
solo recorrer en orden de llegadavector

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.

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.

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):

#ProblemaFaseQué practica
1ReaccionesNacional 2022contador por letra con map
2Cuenta de golesRegional 2025sets para separar lo seguro de lo ambiguo
3El lokómon de OlivierRegional 2022sets de valores prohibidos y filtrado
4⭐ Sistemas interestelaresNacional 2015frecuencias con ids gigantes (el arreglo no alcanza)

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Boy or Girl (236A)★ (800)caracteres distintos con set
2Andryusha 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";

← 05 - Ordenamiento · Ruta de Aprendizaje · 07 - Cuánto se demora tu programa →