Iteradores y algoritmos STL

Un contenedor guarda datos; un algoritmo sabe hacer algo con ellos. Lo que falta es un puente, y ese puente es el iterador: un objeto que se comporta como un puntero y sabe moverse por un contenedor concreto. begin() devuelve un iterador al primer elemento, end() devuelve uno a la posición inmediatamente posterior al último, y todo lo demás se construye sobre ese par.

Los algoritmos no saben si trabajas con un std::vector, un std::array o un rango de un std::string: solo piden dos iteradores y confían en que el contenedor sepa recorrerlos.

¿Qué es un iterador?

Piensa en un libro. El contenedor son las páginas; el iterador es el dedo que marca dónde vas. No necesitas saber cuántas páginas hay ni cómo están encuadernadas: solo puedes avanzar una página, leer la que señalas o comprobar si llegaste al final. Cada contenedor implementa esos gestos a su manera, pero todos ofrecen los mismos.

• v.begin() — señala el primer elemento del contenedor.
• v.end() — señala una posición después del último; no contiene un elemento legible.
• *it — lee o escribe el elemento señalado.
• ++it — avanza al siguiente elemento; --it retrocede si el iterador lo permite.
• it != v.end() — condición estándar para saber si quedan elementos.

¿Para qué sirven los iteradores y los algoritmos?

• Ordenar datos por un criterio propio, ascendente o descendente, sin escribir el algoritmo de ordenación.
• Buscar un valor o la primera posición que cumple una condición, y saber con claridad si no existe.
• Resumir una colección: sumar, promediar, contar cuántos elementos superan un umbral.
• Transformar cada elemento en otro, por ejemplo normalizar características antes de entrenar un modelo.
• Separar intención y mecánica: std::count_if dice qué quieres; un bucle for con un contador dice cómo lo haces.

En un pipeline de Machine Learning esto aparece constantemente: filtrar predicciones con probabilidad alta, ordenar resultados por confianza, calcular la media de una métrica o quitar los valores atípicos de un vector antes de escalarlo. Cada una de esas tareas ya existe como algoritmo; escribirlas a mano solo añade líneas donde pueden esconderse errores.

¿Cómo funciona por dentro?

Un iterador de std::vector es, en la práctica, un puntero al elemento. ++it suma sizeof(T) bytes y *it lee esa dirección. Un iterador de std::list es un puntero a un nodo y ++it sigue el enlace siguiente del nodo. Por eso el mismo algoritmo funciona en ambos, pero con costes distintos: avanzar cien posiciones es instantáneo en un vector y lineal en una lista.

Esa diferencia se formaliza en categorías de iterador. Un algoritmo declara qué necesita: std::sort exige acceso aleatorio porque compara elementos en posiciones arbitrarias; std::find solo necesita avanzar hacia adelante. Si el contenedor no ofrece la categoría requerida, el programa no compila, y ese error es una protección, no un obstáculo.

El rango [first, last) también explica la invalidez. Un std::vector guarda sus elementos en un bloque contiguo; si un push_back necesita crecer, reserva otro bloque, copia y libera el anterior. Todos los iteradores que apuntaban al buffer viejo quedan colgando. La regla es simple: si una operación puede cambiar la capacidad, vuelve a pedir begin() y end().

Sintaxis

La forma canónica recorre con un iterador explícito cuando necesitas la posición, y con range-for cuando solo necesitas el valor. Los algoritmos reciben siempre el par de límites y, si hace falta un criterio, una lambda al final.

12345678910111213

std::vector<int> v{3, 1, 2};

for (auto it = v.begin(); it != v.end(); ++it) {  // iterador explícito
    std::cout << *it << ' ';
}

for (int x : v) {                                  // range-for
    std::cout << x << ' ';
}

std::sort(v.begin(), v.end());                     // todo el vector
std::sort(v.begin(), v.begin() + 2);               // solo el prefijo
std::reverse(v.begin(), v.end());                  // invierte el rango

Fíjate en v.begin() + 2: la aritmética de iteradores existe justo porque el vector ofrece acceso aleatorio. En una lista ese + 2 no compila y hay que usar std::next(v.begin(), 2), que avanza paso a paso. La sintaxis cambia según lo que el contenedor puede garantizar.

1234

notas = [15, 8, 19, 12]
notas.sort()
print(notas)            # [8, 12, 15, 19]
print(notas.index(15))  # 2

123456

std::vector<int> notas{15, 8, 19, 12};
std::sort(notas.begin(), notas.end());
auto it = std::find(notas.begin(), notas.end(), 15);
if (it != notas.end()) {
    std::cout << std::distance(notas.begin(), it); // 2
}

Ejemplo básico: ordenar y buscar

12345678910111213141516171819202122

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> notas{15, 8, 19, 12, 17};

    std::sort(notas.begin(), notas.end());

    for (int nota : notas) {
        std::cout << nota << ' ';
    }
    std::cout << '\n';

    const auto it = std::find(notas.begin(), notas.end(), 15);
    if (it != notas.end()) {
        std::cout << "15 esta en la posicion "
                  << std::distance(notas.begin(), it) << '\n';
    }
    return 0;
}

1. std::sort recibe el inicio y el final del rango y reordena los elementos en el mismo vector, sin crear copias.
2. El range-for recorre el vector ya ordenado y lo imprime con espacios: 8 12 15 17 19.
3. std::find devuelve un iterador al primer 15; si no lo encontrara, devolvería notas.end().
4. std::distance cuenta los saltos desde el inicio hasta ese iterador, es decir, la posición 2.

La salida es 8 12 15 17 19 y 15 esta en la posicion 2. Si cambias el 15 por 20, el bloque if no se ejecuta: comprobar el resultado separa un programa correcto de uno que confía en el dato.

Ejemplo intermedio: transformar, acumular y contar

Los algoritmos se encadenan sin contenedores intermedios, solo con iteradores. En este ejemplo cada pérdida de un modelo se convierte en una nota sobre 20, se calcula la media y se cuentan los aprobados. Cada paso es una línea y cada línea dice exactamente lo que hace.

12345678910111213141516171819202122

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<double> perdidas{0.9, 0.4, 0.7, 0.2, 0.5};

    // Convierte cada perdida en una nota de 0 a 20
    std::transform(perdidas.begin(), perdidas.end(), perdidas.begin(),
                   [](double p) { return (1.0 - p) * 20.0; });

    const double suma = std::accumulate(perdidas.begin(), perdidas.end(), 0.0);
    const auto aprobados = std::count_if(perdidas.begin(), perdidas.end(),
                                         [](double nota) { return nota >= 11.0; });

    std::cout << std::fixed << std::setprecision(1);
    std::cout << "Media: " << suma / static_cast<double>(perdidas.size()) << '\n';
    std::cout << "Aprobados: " << aprobados << '\n';
    return 0;
}

std::transform escribe el resultado en el mismo rango de entrada, así que el vector pasa a contener {2, 12, 6, 16, 10}. std::accumulate empieza en 0.0 y suma; el tercer argumento fija el tipo del acumulador, y por eso se escribe 0.0 y no 0, que truncaría los decimales.

Las dos lambdas son funciones anónimas. [](double p) { return (1.0 - p) * 20.0; } no captura nada del exterior; [](double nota) { return nota >= 11.0; } devuelve un bool que count_if usa como filtro. Más adelante verás capturas y mutable; para algoritmos, casi siempre basta esta forma mínima.

La salida es Media: 9.2 y Aprobados: 2. Comprueba el detalle: la media se calcula después de transformar, así que promedia notas y no pérdidas. Ese orden es una decisión de diseño, no un accidente, y conviene escribirlo en un comentario.

Caso práctico: ordenar predicciones por confianza

Un clasificador devuelve una lista de etiquetas con su probabilidad. Para mostrar el resultado al usuario hay que ordenarlas de mayor a menor, quedarse con la primera y comprobar que las probabilidades suman uno. Tres algoritmos resuelven las tres tareas.

123456789101112131415161718192021222324252627282930313233

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

struct Prediccion {
    std::string etiqueta;
    double probabilidad;
};

int main() {
    std::vector<Prediccion> salida{{"gato", 0.42}, {"perro", 0.51}, {"ave", 0.07}};

    std::sort(salida.begin(), salida.end(),
              [](const Prediccion& a, const Prediccion& b) {
                  return a.probabilidad > b.probabilidad;
              });

    std::cout << std::fixed << std::setprecision(2);
    std::cout << "Clase: " << salida.front().etiqueta
              << " (" << salida.front().probabilidad << ")\n";

    const double total = std::accumulate(
        salida.begin(), salida.end(), 0.0,
        [](double acumulado, const Prediccion& p) {
            return acumulado + p.probabilidad;
        });

    std::cout << "Probabilidad total: " << total << '\n';
    return 0;
}

El comparador recibe dos predicciones por referencia constante y devuelve true si la primera debe ir antes. Con > el orden es descendente; con < sería ascendente. Ese comparador debe ser un orden estricto: si devuelve true para (a, b) y también para (b, a), std::sort puede leer fuera del rango y el comportamiento es indefinido.

La salida es Clase: perro (0.51) y Probabilidad total: 1.00. La suma se hace con std::accumulate y una lambda de dos parámetros porque el tipo del elemento (Prediccion) no es el tipo del acumulador (double). Por eso esta versión necesita la operación personalizada y no la suma por defecto.

Visualización: el iterador avanzando

La traza muestra dónde apunta el iterador en cada paso. Observa cuándo find encuentra el valor y cuándo devuelve end(): ese segundo caso provoca los fallos en producción.

—

Recorre los pasos dos veces: it cambia de valor mientras v permanece idéntico, y el caso «no encontrado» devuelve un iterador legal, end(), que depende de ti comparar.

Errores comunes

El último error es silencioso: el programa compila, el bucle se ejecuta y el vector queda igual. El compilador no puede saber si querías una copia o una referencia.

1234567891011

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{10, 12};
    for (auto nota : notas) {
        nota += 1;   // la copia cambia, el vector no
    }
    std::cout << notas[0] << ' ' << notas[1] << '\n';
    return 0;
}

1234567891011

#include <iostream>
#include <vector>

int main() {
    std::vector<int> notas{10, 12};
    for (auto& nota : notas) {
        nota += 1;   // referencia al elemento real
    }
    std::cout << notas[0] << ' ' << notas[1] << '\n';
    return 0;
}

Buenas prácticas

• Prefiere el algoritmo con nombre: std::count_if antes que un bucle con contador.
• Comprueba siempre el resultado de find contra end(); no asumas que el dato existe.
• Pasa objetos grandes a las lambdas por const&, no por valor.
• Usa const auto& en range-for cuando solo leas.
• No guardes iteradores mientras el contenedor pueda crecer; pide begin() de nuevo.
• Ordena con un comparador que sea un orden estricto y documéntalo si es poco obvio.
• Incluye la cabecera exacta: <algorithm> para sort/find, <numeric> para accumulate.

Ejercicios

std::vector<int> datos{5, 1, 9, 3};
std::sort(datos.(), datos.());

auto it = std::find(datos.begin(), datos.end(), );
std::cout << std::distance(datos.begin(), it);

Soluciones explicadas

En el primer ejercicio el comparador es la pieza delicada. a > b produce orden descendente porque la función responde a la pregunta «¿debe ir a antes que b?». Si escribieras a >= b, dos edades iguales se considerarían anteriores la una a la otra y el orden dejaría de ser estricto; con pocos elementos puede pasar desapercibido, pero es un fallo real.

En el segundo, la clave está en el orden de las operaciones. Primero se obtienen mínimo y máximo del vector original, después se transforma y solo entonces se calcula la media. Si calcularas la media antes de normalizar obtendrías 5.0, un número correcto pero que responde a otra pregunta. Y si usaras std::accumulate(x.begin(), x.end(), 0) en lugar de 0.0, el acumulador sería int y la media se truncaría a 0.

Resumen

• Un iterador es un puntero generalizado que sabe moverse por un contenedor.
• El rango estándar es [begin, end): end() señala una posición después del último y no se desreferencia.
• std::sort, find, count_if, accumulate y transform funcionan con cualquier contenedor que ofrezca la categoría necesaria.
• std::find devuelve end() cuando no encuentra; comprobarlo es obligatorio.
• Las lambdas son el criterio natural de los algoritmos: comparar, filtrar o transformar.
• Modificar la capacidad de un vector invalida los iteradores anteriores.
• Un algoritmo con nombre comunica la intención mejor que un bucle manual equivalente.

Evaluación