auto e Iteradores
Docente: Tomás Assenza
Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe
"There are only two hard things in Computer Science: cache invalidation and naming things."
— Phil Karlton
"The best way to prepare [to be a programmer] is to write programs, and to study great programs that other people have written."
— Bill Gates
En torneos como ICPC, Codeforces o LeetCode no hay tiempo para programar un árbol balanceado o un Quicksort desde cero: la STL te los da optimizados en 1 línea.
Las entrevistas técnicas (Google, Meta, Mercado Libre) evalúan si sabés elegir entre un arreglo, un diccionario (`map`) o un conjunto (`set`) para bajar la complejidad.
En proyectos académicos y de ingeniería en la UTN necesitás estructuras que crezcan dinámicamente según el volumen real de datos de entrada.
En todas las estructuras de la STL, los elementos sin asignación se inicializan por defecto en 0 (o vacíos). No contienen basura de memoria.
auto (C++11)auto?Le indica al compilador que infiera automáticamente el tipo de dato de la variable a partir del valor con el que se inicializa.
En estructuras anidadas o iteradores, evita escribir tipos kilométricos como map<char, int>::iterator y mejora muchísimo la legibilidad.
Nota al margen: auto y = "Hola"; infiere const char* (arreglo de chars). Si querés un std::string, inicializalo a partir de un string.
auto x = 5; // int
auto y = "Soy una cadena de caracteres";
cout << x << endl;
cout << y << endl;
map<char, int> m = {{'a', 1}, {'b', 2}, {'c', 3}};
// Recorrido explicito con pair:
for (pair<char, int> thisPair : m) {
cout << thisPair.first << ": "
<< thisPair.second << endl;
}
// Recorrido limpio con auto:
for (auto thisPair : m) {
cout << thisPair.first << ": "
<< thisPair.second << endl;
}
Un iterador es una variable que apunta a un elemento dentro de una estructura de datos y nos permite recorrerla ("iterarla"):
begin() apunta al primer elemento real de la estructura.
rbegin() apunta al último elemento real (recorrido inverso).
¡Cuidado! end() apunta una posición después del último elemento. Sirve como marca de fin: nunca hagas *estructura.end().
1. Declaración Clásica vs auto:
// Declaracion explicita:
set<int>::iterator it = miSet.begin();
set<int>::reverse_iterator rit = miSet.rbegin();
// Con auto (mucho mas comodo!):
auto it = miSet.begin();
2. Recorridos con for y while:
for (auto it = miSet.begin(); it != miSet.end(); it++) {
cout << *it << " ";
}
auto it = miSet.begin();
while (it != miSet.end() && *it < 6) {
it++;
}
3. Desreferenciación (*it), avance y retroceso:
set<int> miSet = {1, 4, 5, 6, 8};
auto it = miSet.begin();
// Acceso al valor apuntado con *:
cout << *it << endl; // Imprime 1
// Avanzar al siguiente elemento:
it++;
cout << *it << endl; // Imprime 4
// Retroceder al elemento anterior:
it--;
cout << *it << endl; // Imprime 1
find, lower_bound y upper_boundBusca x en el contenedor. Si no existe, devuelve exactamente s.end().
Retorna un iterador al primer elemento mayor o igual a x (≥ x).
Retorna un iterador al primer elemento estrictamente mayor a x (> x).
set<int> s = {1, 4, 6, 7, 8};
auto it = s.find(5);
if (it == s.end()) {
// 5 no esta en la estructura
}
auto it1 = s.lower_bound(5); // *it1 vale 6 (>= 5)
auto it2 = s.upper_bound(5); // *it2 vale 6 (> 5)
auto it3 = s.lower_bound(6); // *it3 vale 6 (>= 6)
auto it4 = s.upper_bound(6); // *it4 vale 7 (> 6)
auto e Iteradores
Ya tenés las herramientas base (auto e iteradores). Pasemos al primer contenedor estrella.