Hub Taller STL
Taller de Estructuras Dinámicas (STL) • Módulo 0

Fundamentos de la STL:
¿Por qué STL?, auto e Iteradores

Docente: Tomás Assenza

Algoritmos y Estructuras de Datos • UTN - Facultad Regional Santa Fe

Dos Frases antes de Arrancar

"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

¿Por Qué Estudiar Estructuras Dinámicas (STL)?

1. Competencias de Programación

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.

2. Entrevistas Laborales

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.

3. Investigación y Desarrollo (I+D)

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.

4. Funciones Pre-armadas y Seguras

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.

La Palabra Clave auto (C++11)

¿Qué hace 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.

Vital en la STL

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;
}
                            

Iteradores: El "Puntero" de la STL

Un iterador es una variable que apunta a un elemento dentro de una estructura de datos y nos permite recorrerla ("iterarla"):

rend()
antes
begin()
1
4
5
6
rbegin()
8
end()
fin

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().

Uso y Navegación con Iteradores

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
                            

Búsqueda Rápida: find, lower_bound y upper_bound

s.find(x)

Busca x en el contenedor. Si no existe, devuelve exactamente s.end().

s.lower_bound(x)

Retorna un iterador al primer elemento mayor o igual a x (≥ x).

s.upper_bound(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)
                                

Laboratorio en Vivo: auto e Iteradores

OneCompiler - Probá lower_bound y upper_bound

¡Fin del Módulo 0!

Ya tenés las herramientas base (auto e iteradores). Pasemos al primer contenedor estrella.

Volver al Hub Ir al Módulo 1: std::vector