🔗 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é devuelve lower_bound. Solo necesitas saber lo de los módulos 00 a 06: variables, funciones, vector y set. (La última sección usa struct, 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 cambia

Có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:

  • *it lee 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 7

nullptr 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;   // 20

Es 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).
  • *it sin comprobar it != 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 haces v.push_back(...), el vector puede realocarse y r queda 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];
vector<int> b = {1, 2, 3};
for (int x : b) x *= 2;
cout << b[0] << b[1] << b[2];
set<int> s = {2, 4, 6};
auto it = s.find(5);
cout << *it;
long long suma(const vector<int>& v);

Relacionado: Complejidad computacional (por qué copiar cuesta) · Catálogo de estructuras (dónde aparecen los iteradores) · volver a Referencia.