🔗 Punteros y referencias
Guía de referencia para entender el & que aparece en las firmas de funciones,
qué es exactamente un iterador, y por qué en competencia casi nunca se usan
punteros de verdad. Volver a Referencia.
Cuándo leer esto: cuando te topes con el primer
const vector<int>&— pasa en el módulo 08 de la Ruta de Aprendizaje — o cuando quieras entender qué devuelvelower_bound. Solo necesitas saber lo de los módulos 00 a 06: variables, funciones,vectoryset. (La última sección usastruct, que la ruta no alcanza a enseñar; va explicado ahí mismo.)No necesitas dominar punteros para competir. Sí necesitas leer el
&sin asustarte y entender los iteradores, porque aparecen en toda la STL.
Referencias (&): otro nombre para lo mismo
Una referencia es un apodo: int& alias = a; hace que alias y a sean la
misma variable. Cambiar una cambia la otra.
Eso importa de verdad en los parámetros de funciones, donde decide si la función trabaja sobre tus datos o sobre una fotocopia:
void sin_amp(vector<int> v) { v[0] = 99; } // trabaja sobre una COPIA
void con_amp(vector<int>& v) { v[0] = 99; } // trabaja sobre el ORIGINAL
vector<int> a = {1, 2, 3};
sin_amp(a); cout << a[0]; // 1 — el original no se enteró
con_amp(a); cout << a[0]; // 99 — sí lo cambióDesde afuera las dos se llaman igual (sin_amp(a) y con_amp(a)), y ahí está
lo traicionero: el & solo se ve en la firma, pero cambia todo. Y no solo
el resultado — también el costo: copiar un vector de 10⁶ elementos en cada
llamada convierte un algoritmo lineal en cuadrático. Esa es la trampa de TLE
más difícil de ver, porque tu algoritmo sí era correcto.
Por eso existe la tercera forma, que es la que más vas a escribir:
// const & : recibe el original SIN copiarlo, y promete no modificarlo
// (el compilador te avisa si lo intentas)
long long suma(const vector<int>& v) { ... }Regla práctica: todo contenedor se pasa como const T&; si de verdad
necesitas modificarlo, T& a secas; nunca por copia.
El mismo & aparece al recorrer:
for (int x : v) x *= 2; // x es una copia: NO cambia el vector
for (int& x : v) x *= 2; // x es el elemento: SÍ lo cambiaCómo leer una firma de verdad
Estas son firmas reales de las páginas de este vault. Leerlas es la mitad de la utilidad de esta guía:
vector<int> bfs(int s, const vector<vector<int>>& g);“bfs recibe un nodo s y el grafo g —sin copiarlo y sin modificarlo— y
devuelve un vector de enteros.” El & está ahí por velocidad; el const, para
avisarte que el grafo sale intacto.
void duplicar(vector<int>& v);“Recibe el vector original y lo va a modificar” — cuando veas un & sin
const, el resultado sale por ahí, no por el return.
Iteradores: posiciones dentro de un contenedor
Un iterador se comporta como un puntero a un elemento. Es lo que devuelven
lower_bound, find, begin y end:
set<int> s = {2, 4, 6};
auto it = s.lower_bound(3); // "posición del primer elemento >= 3"
if (it != s.end()) cout << *it << "\n"; // 4 — el * lee el valor(auto significa “compilador, deduce tú el tipo”: el tipo real de un iterador
es largo y nadie lo escribe a mano.)
Dos cosas que hay que saber leer:
*itlee el valor que hay en esa posición. Sin el*tienes la posición, no el número.it != s.end()es la forma de preguntar “¿encontró algo?”.end()no es el último elemento: es la marca de “se acabó”, una posición después del final.
Por eso sort(v.begin(), v.end()) significa “ordena desde el principio hasta el
final”, y lower_bound(...) - v.begin() convierte una posición en un índice.
Punteros de verdad
Un puntero guarda una dirección de memoria. Se pide con & y se lee con *:
int a = 9;
int* p = &a; // p apunta a la casilla donde vive a
cout << *p; // 9 — desreferenciar: "lo que hay en esa dirección"
*p = 7; // escribe a través del puntero: ahora a vale 7nullptr es el valor que significa “no apunta a nada”; leer *p cuando
p == nullptr es un RTE (segmentation fault).
Por qué en competencia se usan índices, no punteros
Las estructuras con nodos (árboles, tries, segment trees)
podrían enlazarse con punteros… pero casi nadie lo hace. En su lugar se guardan
los nodos en un vector y se enlazan por índice:
// struct = varios campos con nombre, juntos bajo una etiqueta
struct Nodo { int valor; int hijo; };
vector<Nodo> nodos;
nodos.push_back({10, -1}); // valor 10, sin hijo (-1 = "ninguno")
nodos.push_back({20, -1});
nodos[0].hijo = 1; // "apunta" al nodo 1 por su índice
cout << nodos[nodos[0].hijo].valor; // 20Es más rápido (memoria contigua), más fácil de depurar (un índice se imprime;
una dirección no dice nada), no hay que liberar nada, y resetear la estructura
entre casos de prueba es nodos.clear(). Por eso las páginas del vault usan
este patrón.
⚠️ Trampas
- Olvidar el
&en el parámetro: compila, funciona… y da TLE, con el algoritmo correcto (ver Complejidad computacional). *itsin comprobarit != end(): si la búsqueda falló estás leyendo la marca de fin. RTE o basura.- Referencia a algo que se movió: si guardas
int& r = v[0];y después hacesv.push_back(...), el vector puede realocarse yrqueda apuntando a memoria vieja. Guarda el índice, no la referencia.
🧪 Autoevaluación
void f(vector<int> v) { v[0] = 99; }
vector<int> a = {1, 2, 3};
f(a);
cout << a[0];Respuesta 1
Imprime 1. Sin
&,frecibió una copia: modificó la copia y la tiró al terminar. Convoid f(vector<int>& v)imprimiría 99.
vector<int> b = {1, 2, 3};
for (int x : b) x *= 2;
cout << b[0] << b[1] << b[2];Respuesta 2
Imprime 123: sin cambios. Cada
xes una copia del elemento. Confor (int& x : b)imprimiría 246.
set<int> s = {2, 4, 6};
auto it = s.find(5);
cout << *it;Respuesta 3
Comportamiento indefinido (basura o RTE): el 5 no está, así que
finddevolviós.end(), yend()no apunta a ningún elemento. Siempreif (it != s.end())antes de usar*it.
long long suma(const vector<int>& v);Respuesta 4
“Recibe el vector sin copiarlo (
&) y promete no modificarlo (const), y devuelve unlong long.” Es la firma que deberías escribir por defecto para cualquier función que reciba un contenedor.
Relacionado: Complejidad computacional (por qué copiar cuesta) · Catálogo de estructuras (dónde aparecen los iteradores) · volver a Referencia.