Iteradores: El Pegamento de la STL
Comprende las categorias de iteradores, desde iteradores de entrada hasta iteradores contiguos. Aprende la aritmetica de iteradores, la convencion begin/end y como los iteradores conectan contenedores con algoritmos.
La Abstraccion de Iteradores
Los iteradores son el pegamento entre los contenedores y los algoritmos de la STL. En lugar de escribir N algoritmos para M contenedores (N*M implementaciones), la STL define una interfaz comun de iteradores. Cada contenedor proporciona iteradores, y cada algoritmo opera sobre rangos de iteradores — dando N+M implementaciones que trabajan juntas.
Un iterador es un objeto que:
1. Apunta a un elemento en una secuencia
2. Puede ser desreferenciado (*it) para acceder al elemento
3. Puede ser incrementado (++it) para moverse al siguiente elemento
4. Puede ser comparado (it != end) para detectar el final de la secuencia
Diferentes categorias de iteradores soportan diferentes conjuntos de operaciones, formando una jerarquia de la mas debil a la mas fuerte.
Categorias de Iteradores
Las categorias de iteradores de C++ forman una jerarquia (cada nivel incluye las capacidades de todos los niveles inferiores):
| Categoria | Operaciones | Contenedores de Ejemplo |
|---|---|---|
| Input | Lectura, avance de un solo paso (++, *, ==) | istream_iterator |
| Output | Escritura, avance de un solo paso (++, *=) | ostream_iterator, back_inserter |
| Forward | Lectura/escritura, avance de multiples pasos | forward_list, unordered_set |
| Bidirectional | Forward + retroceso (--) | list, set, map |
| Random Access | Bidirectional + saltos (+n, -n, [], <) | deque |
| Contiguous (C++17) | Random Access + elementos adyacentes en memoria | vector, array, string |
Los algoritmos declaran la categoria minima que requieren. std::sort necesita iteradores de acceso aleatorio, por lo que funciona con vector pero no con list (que proporciona su propia funcion miembro sort()).
La Convencion begin/end
Cada contenedor de la STL proporciona begin() y end() — un rango semi-abierto [begin, end) donde end apunta un elemento despues del ultimo. Las funciones libres std::begin() y std::end() funcionan con contenedores, arreglos C y cualquier tipo que proporcione miembros .begin() y .end().
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>
int main() {
std::vector<int> vec = {5, 3, 1, 4, 2};
// Member functions
auto first = vec.begin(); // points to 5
auto last = vec.end(); // points past 2
// Free functions — preferred for generic code
auto first2 = std::begin(vec);
auto last2 = std::end(vec);
// Works with C-arrays too
int arr[] = {10, 20, 30};
std::sort(std::begin(arr), std::end(arr));
// const iterators — read-only access
auto cit = vec.cbegin(); // const_iterator
// *cit = 99; // ERROR: cannot modify through const_iterator
// Reverse iterators — iterate backward
for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
std::cout << *rit << ' '; // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
}
std::cout << '\n';
}Utilidades de Iteradores: next, prev, advance, distance
El encabezado
#include <iterator>
#include <vector>
#include <list>
#include <iostream>
int main() {
std::vector<int> vec = {10, 20, 30, 40, 50};
// std::next — returns iterator n positions forward (default 1)
auto it = std::next(vec.begin(), 2); // points to 30
std::cout << *it << '\n'; // 30
// std::prev — returns iterator n positions backward
auto it2 = std::prev(vec.end()); // points to 50
std::cout << *it2 << '\n'; // 50
// std::advance — modifies iterator in place (no return)
auto it3 = vec.begin();
std::advance(it3, 3); // now points to 40
std::cout << *it3 << '\n'; // 40
// std::distance — number of increments from first to last
auto d = std::distance(vec.begin(), vec.end()); // 5
std::cout << "Distance: " << d << '\n';
// These work with non-random-access iterators too
std::list<int> lst = {1, 2, 3, 4, 5};
auto lit = std::next(lst.begin(), 2); // O(n) for list, O(1) for vector
std::cout << *lit << '\n'; // 3
auto ld = std::distance(lst.begin(), lst.end()); // O(n) for list
std::cout << "List distance: " << ld << '\n'; // 5
}Iteradores de Insercion e Iteradores de Flujo
Los iteradores de insercion permiten que los algoritmos inserten en contenedores en lugar de sobrescribir elementos existentes. Los iteradores de flujo adaptan los flujos de E/S a la interfaz de iteradores.
#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
int main() {
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;
// back_inserter — calls push_back on each assignment
std::copy(src.begin(), src.end(), std::back_inserter(dst));
// dst: {1, 2, 3, 4, 5}
// front_inserter — calls push_front (works with deque, list)
// inserter — calls insert at a given position
// ostream_iterator — write to an output stream
std::copy(dst.begin(), dst.end(),
std::ostream_iterator<int>(std::cout, ", "));
std::cout << '\n'; // 1, 2, 3, 4, 5,
// istream_iterator — read from an input stream
std::istringstream iss("10 20 30 40");
std::vector<int> from_stream(
std::istream_iterator<int>(iss),
std::istream_iterator<int>() // end-of-stream sentinel
);
// from_stream: {10, 20, 30, 40}
}Incrementar un iterador mas alla de end() o decrementar antes de begin() es comportamiento indefinido. Lo mismo aplica a desreferenciar end() — es un centinela, no un elemento valido.
Un error comun es escribir it + 1 sin verificar si it ya esta en o cerca del final:
auto it = vec.end();
++it; // UB — mas alla del final
*it; // UB — desreferenciando end()Siempre verifica la validez del iterador antes de las operaciones. Usa std::next y std::prev con verificaciones de distancia, o usa bucles range-based for que manejan los limites automaticamente.
Al escribir funciones genericas que operan sobre secuencias:
1. Acepta pares de iteradores (o ranges en C++20) en lugar de contenedores especificos
2. Usa typename o auto para el tipo del iterador
3. Usa std::distance en lugar de resta (que requiere acceso aleatorio)
4. Usa std::next/std::prev en lugar de aritmetica +/-
5. En C++20, prefiere concepts para restringir los requisitos de iteradores:
template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }Esto asegura que tu codigo funcione con la mayor variedad de contenedores.
- Los iteradores desacoplan contenedores de algoritmos — el principio fundamental de diseno de la STL
- Existen seis categorias de iteradores: input, output, forward, bidirectional, random access, contiguous
- Usa las funciones libres
std::begin()/std::end()para codigo generico que funcione con contenedores y arreglos C std::next,std::prev,std::advance,std::distancefuncionan en todas las categorias de iteradores- Los iteradores de insercion (
back_inserter,front_inserter,inserter) permiten que los algoritmos hagan crecer los contenedores - Nunca desreferencies
end()ni incrementes mas alla de el — ambos son comportamiento indefinido
Quiz — Pon a prueba tus conocimientos
(15 XP)1. Que categoria de iterador requiere `std::sort`?
2. Que crea `std::back_inserter(vec)`?
3. Cual es la complejidad temporal de `std::distance(first, last)` en un `std::list`?