La STL: containers, iterators, algorithms

La STL no es solo "algunas clases útiles". Es un patrón de diseño para C++ genérico: los containers own u organizan elementos, los iterators describen posiciones en secuencias, y los algorithms operan sobre ranges de iterators. Esa separación deja que std::sort funcione sobre un std::vector, que std::find_if funcione sobre muchas estructuras recorribles, y que std::span pase una vista contigua no-owning sin perder longitud. El modelo mental es: elegí la estructura de datos por ownership y layout, después usá algorithms para la operación.

El reset: los containers responden "¿dónde viven los elementos?", los iterators responden "¿cómo los recorro?", y los algorithms responden "¿qué operación aplico a ese recorrido?"

Cómo funciona de verdad

Los containers vienen en familias con distintas promesas de layout y complejidad:

Familia	Ejemplos	Forma
Sequence	`std::vector`, `std::array`, `std::deque`, `std::list`	elementos ordenados, layout elegido
Associative	`std::map`, `std::set`	lookup ordenado tipo árbol, orden estable
Unordered associative	`std::unordered_map`, `std::unordered_set`	lookup por hash table, sin orden sorted
Adaptors	`std::stack`, `std::queue`, `std::priority_queue`	interfaz restringida sobre otro container
Views	`std::span`, ranges views	vista no-owning o lazy sobre elementos

std::vector<T> es el sequence container por defecto porque es contiguo, compacto y cache-friendly. Puede realocar, lo que invalida punteros, referencias e iterators a su storage. std::list<T> mantiene estables direcciones de nodos en muchas operaciones, pero paga allocation por nodo y mala locality. std::map da keys ordenadas y lookup logarítmico. std::unordered_map da lookup constante promedio, pero hashing, rehashing y worst-case behavior importan.

Los iterators son punteros generalizados. Algunos solo pueden avanzar; algunos son bidireccionales; algunos son random-access; los contiguous iterators exponen memoria adyacente. Los algorithms declaran sus requirements mediante iterator categories o concepts. Sorting necesita random access. Finding solo necesita traversal input/forward. Por eso elección de algorithm y container están acopladas sin que cada algorithm nombre cada container.

Los algorithms suelen tomar half-open ranges: [first, last). El primer iterator apunta al primer elemento; el último apunta uno-pasado-el-final. Eso coincide con rangos de punteros C y evita un elemento centinela. C++20 ranges agrega overloads que toman objetos range directamente, pero el contrato es el mismo: el algorithm trabaja sobre un range válido y asume que sus precondiciones se cumplen.

Artefacto ejecutable: containers más algorithms

El demo ejecutable vive en examples/modern-cpp/the-stl-containers-iterators-algorithms/. Guarda records en un std::vector, ordena con un algorithm, busca con un predicado, transforma a otro container y demuestra realocation de vector sin dereferenciar un puntero inválido.

cd examples/modern-cpp/the-stl-containers-iterators-algorithms
./run.sh

La capa de algorithms se lee como operaciones sobre ranges:

std::sort(samples.begin(), samples.end(), [](const Sample &left, const Sample &right) {
    return left.cycles < right.cycles;
});

auto first_slow = std::find_if(samples.begin(), samples.end(), [](const Sample &sample) {
    return sample.cycles >= 30;
});

std::transform(samples.begin(), samples.end(), std::back_inserter(cycles),
               [](const Sample &sample) {
                   return sample.cycles;
               });

La prueba de realocation es cuidadosa:

std::vector<int> growth{1, 2, 3};
const int *before = growth.data();
std::size_t before_capacity = growth.capacity();
while (growth.capacity() == before_capacity) {
    growth.push_back((int)growth.size() + 1);
}
const int *after = growth.data();

std::cout << (before != after) << "\n";

Compara direcciones después de realocation, pero nunca dereferencia before. Dereferenciar eso sería un bug de use-after-invalidation.

Fallas típicas y trade-offs

Iterator invalidation es invalidación real de lifetime. Después de que un vector realoca, los punteros, referencias e iterators viejos hacia su storage están muertos.
Las precondiciones de algorithms son contratos. std::sort necesita un range válido y un comparator que se comporte como strict weak ordering. Violar eso no es "sort se puso raro"; es tu contrato fallando.
La elección de container es una decisión de performance. std::list evita relocation pero suele perder locality. std::vector reloca pero muchas veces es más rápido porque la memoria es contigua.
Las views no own. std::span y muchas ranges views son borrow-like. Si muere el storage subyacente, la view cuelga.
end() no es un elemento. Es un sentinel/past-the-end iterator. Dereferenciarlo es inválido.
Debug iterators no son el lenguaje. Algunos modos debug de biblioteca estándar cazan iterators inválidos. Los builds release normalmente confían en vos.

En la práctica

Default a std::vector hasta que una restricción diga lo contrario. Es simple, cache-friendly y compatible con algorithms.
Usá algorithms para declarar intención. std::find_if, std::count_if, std::sort y std::transform son más buscables y menos propensos a error que loops custom para operaciones comunes.
Reservá cuando conocés el crecimiento. vector.reserve() evita realocations repetidas y preserva iterators hasta exceder capacidad.
Mantené cortos los lifetimes de iterators. Guardá índices o IDs estables si un container va a mutar.
Usá std::span en bordes. Lleva puntero más longitud sin tomar ownership, un reemplazo más limpio para muchos pares T* más count.

Conecta con: Templates y generic programming · Referencias, const y overloading · Move semantics y value categories · Data layout y cache-friendliness · Aritmética de punteros y stride · Arrays y array-to-pointer decay

Fuentes

cppreference - Containers library - familias de containers, storage management, tabla de iterator invalidation y contexto de complejidad. https://en.cppreference.com/w/cpp/container
cppreference - Iterator library - iterator categories, iterator traits, sentinels y concepts de iterators C++20. https://en.cppreference.com/w/cpp/iterator
cppreference - Algorithms library - familias de algorithms estándar, range requirements, sorting, finding, transforming y operaciones numéricas. https://en.cppreference.com/w/cpp/algorithm
cppreference - Ranges library - vocabulario C++20 de ranges y views sobre pares iterator/sentinel. https://en.cppreference.com/w/cpp/ranges
C++ working draft - [containers.general] - resumen estándar de requirements y familias de containers. https://eel.is/c++draft/containers.general
C++ working draft - [iterators] - wording estándar para iterator requirements y concepts. https://eel.is/c++draft/iterators
C++ working draft - [algorithms] - wording estándar para requirements de algorithms y familias de operaciones. https://eel.is/c++draft/algorithms