UTN Santa Fe

AEDD / UTN SANTA FE

Ingeniería en Sistemas de Información • Algoritmos y Estructuras de Datos
C++ STL
TALLER DE ESTRUCTURAS DINÁMICAS
Hub Interactivo Asincrónico • Cápsulas de Video + Práctica en Vivo

Taller de Estructuras Dinámicas (Librería STL)

Dominá los contenedores dinámicos y algoritmos de la Standard Template Library de C++. Cada módulo combina una cápsula explicativa en video, diapositivas interactivas paso a paso y un laboratorio C++ embebido para resolver problemas de programación competitiva y entrevistas técnicas.

6 Módulos Temáticos
Videos Cortos On-Demand
OneCompiler C++ Integrado
Enfoque Prog. Competitiva

Módulos del Taller (Cápsulas de Video & Diapositivas)

6 Módulos
Módulo 0 • Base O(1) / O(log N)

Intro, auto e Iteradores

Fundamentos de la STL y Punteros Lógicos

¿Por qué estudiar estructuras dinámicas? Inferencia de tipos con auto y navegación universal de contenedores mediante iteradores y búsquedas binarias.

  • STL en programación competitiva (ICPC), entrevistas e I+D
  • Inferencia de tipos con auto y legibilidad de código
  • Iteradores: begin(), end(), rbegin(), rend() y *it
  • Búsqueda con find(x), lower_bound(x) y upper_bound(x)
Laboratorio: Radares de cota inferior/superior en tiempo real
Módulo 1 • Secuencial Acceso O(1)

std::vector & Sort

Arreglos Dinámicos, Matrices y <algorithm>

El contenedor más versátil de C++. Arreglos que crecen en tiempo de ejecución, ordenamiento personalizado de struct y matrices dinámicas.

  • Tamaño físico = lógico dinámico: push_back(), pop_back(), resize()
  • Acceso v[i], front(), back(), insert(), clear()
  • sort() ascendente, greater<int>() y comparador de struct
  • *max_element, *min_element y matrices vector<vector<T>>
Práctica: Cálculo de la Mediana de N mediciones
Módulo 2 • Asociativo O(log N) / O(1)

std::map

Diccionarios Clave → Valor

Reemplazá el índice numérico por una clave de cualquier tipo (string, char, int). Orden lexicográfico automático de claves.

  • Asociación clave-valor mediante mapa[clave] = valor
  • Claves no consecutivas y ordenadas automáticamente
  • Verificación de existencia sin insertar con mapa.count(clave)
  • Recorrido con pair<K,V> / auto (.first y .second)
Práctica: Tendencias de Twitter (Frecuencia y M consultas)
Módulo 3 • Asociativo O(log N) / O(1)

std::set & Variantes

Conjuntos Ordenados, Unordered y Multiset

Colecciones que mantienen sus elementos automáticamente ordenados y sin duplicados, más sus variantes hash y multi-clave.

  • Inserción y deduplicación automática con miSet.insert(x)
  • Prohibición del operador [] y recorrido por elementos
  • Variantes: unordered_set, multiset y unordered_multiset
  • Cuándo elegir O(log N) ordenado vs O(1) con tabla de hash
Práctica: Lista de Compras de Valentina (Beecrowd 2729)
Módulo 4 • Adaptador Tope O(1)

std::stack (Pilas)

Estructura LIFO (Last-In, First-Out)

Estructura donde solo es posible acceder al elemento en el tope, tanto para añadirlo como para consultarlo o eliminarlo.

  • Principio LIFO: el último en entrar es el primero en salir
  • Restricción estricta: acceso exclusivo mediante pila.top()
  • Primitivas en O(1): push(x), pop() y empty()
  • Patrón clásico de emparejamiento y anidamiento de símbolos
Práctica: Fórmulas Bien Formadas de Ayelén (([[{}]]))
Módulo 5 • Colas y Bicolas Extremos O(1)

queue & deque

Colas FIFO, Priority Queue y Doble Extremo

Colas FIFO tradicionales, colas de prioridad (heaps) y colas doblemente terminadas que permiten operar en ambos extremos e indexar.

  • queue (FIFO): push(), front(), back() y pop()
  • priority_queue de máximo y de mínimo con greater<int>
  • deque: push_front(), push_back(), pop_front(), pop_back()
  • Ventana deslizante de eventos recientes con descarte automático
Prácticas: Colectivero Misterioso + Centro de Monitoreo CME

Laboratorio Visual & Bibliografía Recomendada

Herramientas Extra
Laboratorio Interactivo C++ Memory Sandbox

Visualizador & Debugger STL

Animación en memoria y depuración paso a paso

Inspeccioná en tiempo real cómo se comportan en memoria vector, map, set, stack, queue y deque. Ejecutá línea por línea los problemas del taller o probá métodos en el sandbox libre.

push_back / pop Iteradores en vivo Árbol / Clave-Valor LIFO vs FIFO

Competitive Programmer's Handbook

Antti Laaksonen (CSES) • Capítulos 4: Data Structures & Iterators

PDF

Referencia Oficial C++ (cppreference)

Documentación técnica completa de contenedores y complejidades

Abrir

Guía Rápida: ¿Qué Contenedor STL Uso en mi Problema?

Cheat-Sheet
Necesidad en el Problema Estructura Recomendada Operaciones Clave Complejidad Típica
Arreglo dinámico, ordenar datos o acceder por posición i vector<T> push_back(x), v[i], sort(v.begin(), v.end()) Acceso O(1) • Sort O(N log N)
Contar frecuencias o asociar una clave (ej. string) a un valor map<K, V> / unordered_map m[clave]++, m.count(clave) O(log N) ordenado • O(1) prom. hash
Guardar elementos sin repetidos y saber rápido si uno existe set<T> / unordered_set s.insert(x), s.find(x), s.lower_bound(x) O(log N) ordenado • O(1) prom. hash
Procesar el último elemento ingresado o validar anidamientos (paréntesis) stack<T> push(x), top(), pop() O(1) en tope
Simular una fila por orden de llegada (FIFO) queue<T> push(x), front(), pop() O(1) en extremos
Insertar y borrar tanto al principio como al final (ventana deslizante) deque<T> push_front(x), push_back(x), pop_back(), d[i] O(1) en ambos extremos e índice

Docente a cargo del Taller

Tomás Assenza (tassenza@frsf.utn.edu.ar)

Cátedra

Algoritmos y Estructuras de Datos (AEDD) — UTN Facultad Regional Santa Fe
MÓDULO 1
std::vector y <algorithm>