La Biblioteca de Plantillas Estándar (STL) de C++ proporciona una colección de estructuras de datos y algoritmos versátiles. Comprender y utilizar eficazmente la STL puede mejorar significativamente la eficiencia y la claridad del código, especialmente en contextos como la programación competitiva.

Contenedores Comunes de la STL

Vector

#include <vector>

Un vector es una estructura de almacenamiento secuencial que se asemeja a un array pero con la capacidad de redimensionarse dinámicamente. Almacena sus elementos de forma contigua en memoria.

Operaciones Frecuentes

• Construcción: std::vector<T> nombre(tamaño, valor_inicial);. Permite inicializar un vector con un tamaño y valor especificados.
• Agregar elemento: push_back(elemento);. Añade un elemento al final del vector. Complejidad amortizada O(1).
• Eliminar elemento: pop_back();. Elimina el último elemento del vector. Complejidad O(1).
• Acceso por índice: operator[];. Permite acceder a un elemento mediante su índice. Complejidad O(1).
• Obtener tamaño: size();. Devuelve el número actual de elementos. Complejidad O(1).
• Limpiar: clear();. Elimina todos los elementos del vector. Complejidad O(N).
• Verificar si está vacío: empty();. Devuelve true si el vector no contiene elementos, false en caso contrario. Complejidad O(1).
• Redimensionar: resize(nuevo_tamaño, valor_predeterminado);. Cambia el tamaño del vector, añadiendo o eliminando elementos según sea necesario.

Casos de Uso

Los vectores son una alternativa superior a los arrays C-style en la mayoría de los casos debido a su flexibilidad y gestión automática de memoria. Son ideales para matrices dinámicas donde las dimensiones pueden variar o ser muy grandes, evitando desbordamientos de pila.

Consideraciones

• Preasignación de memoria: Si el tamaño final es conocido, es más eficiente inicializar el vector con ese tamaño directamente en lugar de usar push_back repetidamente. Esto evita reasignaciones costosas.
• Tipo size_t: El tipo devuelto por size() es size_t, que puede causar desbordamientos si se multiplica por sí mismo en sistemas de 32 bits si el tamaño es muy grande.

Pila (Stack)

#include <stack>

Una pila implementa el principio LIFO (Last-In, First-Out). Se basa en otros contenedores como deque.

Operaciones Frecuentes

• Construcción: std::stack<T> nombre;.
• Apilar: push(elemento);. Añade un elemento en la cima.
• Desapilar: pop();. Elimina el elemento de la cima.
• Ver cima: top();. Devuelve una referencia al elemento en la cima sin eliminarlo.

Restricción: No se puede acceder a elementos intermedios ni iterar sobre una pila.

Cola (Queue)

#include <queue>

Una cola implementa el principio FIFO (First-In, First-Out). Se basa en deque por defecto.

Operaciones Frecuentes

• Construcción: std::queue<T> nombre;.
• Encolar: push(elemento);. Añade un elemento al final de la cola.
• Desencolar: pop();. Elimina el elemento del frente de la cola.
• Ver frente: front();. Devuelve una referencia al elemento en el frente.
• Ver final: back();. Devuelve una referencia al elemento en el final.

Restricción: No se puede acceder a elementos intermedios ni iterar sobre una cola.

Cola de Prioridad (Priority Queue)

#include <queue>

Una cola de prioridad es una estructura que permite el acceso eficiente al elemento de mayor (o menor) prioridad. Se implementa comúnmente usando un montículo binario.

Operaciones Frecuentes

• Construcción: std::priority_queue<T, Contenedor, Comparador> nombre;. Por defecto, es un max-heap (el mayor elemento está en la cima). Para un min-heap, se usa std::greater<T> como comparador.
• Insertar: push(elemento);. Complejidad O(log N).
• Extraer: pop();. Elimina el elemento de la cima. Complejidad O(log N).
• Ver cima: top();. Devuelve el elemento de mayor prioridad. Complejidad O(1).

Restricción: Solo se puede acceder al elemento de la cima.

Conjunto (Set)

#include <set>

Un conjunto almacena elementos únicos, ordenados (generalmente mediante un árbol rojo-negro). Ofrece inserción, eliminación y búsqueda en tiempo logarítmico.

Operaciones Frecuentes

• Construcción: std::set<T, Comparador> nombre;.
• Insertar: insert(elemento);. Complejidad O(log N).
• Eliminar: erase(elemento);. Complejidad O(log N).
• Buscar: find(elemento);. Devuelve un iterador al elemento si existe, o end() en caso contrario. Complejidad O(log N).
• Contar: count(elemento);. Devuelve 1 si el elemento existe, 0 en caso contrario. Complejidad O(log N).
• Iteración: Se puede recorrer usando iteradores.

Consideraciones: No tiene acceso por índice. Los elementos no se pueden modificar directamente; se deben eliminar y volver a insertra.

Mapa (Map)

#include <map>

Un mapa almacena pares clave-valor, donde las claves son únicas y ordenadas (basado en un árbol rojo-negro). Proporciona búsqueda, inserción y eliminación en tiempo logarítmico.

Operaciones Frecuentes

• Construcción: std::map<KeyType, ValueType, Comparador> nombre;.
• Acceso/Inserción/Actualización: operator[];. Si la clave no existe, se inserta con un valor predeterminado. Complejidad O(log N).
• Insertar/Actualizar (alternativa): insert_or_assign(clave, valor); (C++17).
• Buscar: find(clave);. Devuelve un iterador al par clave-valor. Complejidad O(log N).
• Eliminar: erase(clave);. Complejidad O(log N).
• Contar: count(clave);. Devuelve 1 si la clave existe, 0 en caso contrario. Complejidad O(log N).
• Iteración: Se puede recorrer mediante iteradores, obteniendo pares clave-valor.

Consideraciones: El uso de operator[] puede insertar una clave si no existe, lo cual puede ser un efecto secundario no deseado. La iteración sobre mapas no proporciona índices directos.

String

#include <string>

La clase std::string es la forma estándar de manejar cadenas de caracteres en C++.

Operaciones Frecuentes

• Construcción: std::string s = "texto";, std::string s(tamaño, caracter);.
• Concatenación: Operadores + y +=. += es preferible para eficiencia al añadir repetidamente.
• Acceso: operator[] para caracteres individuales.
• Subcadena: substr(indice_inicio, longitud);.
• Búsqueda: find(subcadena, indice_inicio);. Devuelve la posición o std::string::npos.
• Conversión: Funciones como std::to_string, std::stoi, std::stoll, etc. (C++11).

Consideraciones: El método find tiene una complejidad O(N*M) (donde N y M son las longitudes de la cadena y subcadena), no es un algoritmo KMP.

Par (Pair)

#include <utility>

Almacena exactamente dos elementos, que pueden ser de tipos diferentes.

Operaciones Frecuentes

• Construcción: std::pair<T1, T2> p = {valor1, valor2}; o std::make_pair(valor1, valor2);.
• Acceso: p.first y p.second.
• Comparación: Operadores ==, !=, <, etc., que comparan lexicográficamente.

Útil para devolver múltiples valores desde una función o como claves en mapas/conjuntos.

Algoritmos Comunes de la STL

std::sort

Ordena un rango de elementos. Por defecto, de menor a mayor. Acepta un comparador personalizado.

// Orden ascendente
std::sort(vec.begin(), vec.end());

// Orden descendente
std::sort(vec.begin(), vec.end(), std::greater<int>());

// Comparador personalizado
bool customCompare(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    if (a.second != b.second) {
        return a.second < b.second; // Ordenar por segundo elemento
    }
    return a.first > b.first; // Si los segundos son iguales, ordenar el primero en orden descendente
}
std::sort(pairs.begin(), pairs.end(), customCompare);

La complejidad es típciamente O(N log N).

std::lower_bound y std::upper_bound

Realizan búsquedas binarias en un rango ordenado.

• lower_bound(first, last, valor): Devuelve un iterador al primer elemento que no es menor que valor (es decir, >= valor).
• upper_bound(first, last, valor): Devuelve un iterador al primer elemento que es mayor que valor (es decir, > valor).

Ambos tienen una complejidad de O(log N). Son cruciales para encontrar eficientemente posiciones en datos ordenados.

std::vector<int> data = {2, 4, 4, 4, 7, 9};
// Encontrar el primer elemento >= 4
auto it_lower = std::lower_bound(data.begin(), data.end(), 4); // apunta al primer 4

// Encontrar el primer elemento > 4
auto it_upper = std::upper_bound(data.begin(), data.end(), 4); // apunta al 7

// Calcular el número de ocurrencias de 4
int count = std::distance(it_lower, it_upper); // o it_upper - it_lower

std::reverse

Revierte el orden de los elementos en un rango.

std::vector<int> v = {1, 2, 3, 4, 5};
std::reverse(v.begin(), v.end()); // v ahora es {5, 4, 3, 2, 1}

La complejidad es O(N).

std::max y std::min

Devuelven el mayor o menor de dos o más valores.

int max_val = std::max(10, 20); // 20
int min_val = std::min({1, 5, 2, 8}); // 1 (C++11 y superior)

std::unique

Elimina elementos duplicados adyacentes de un rango. Devuelve un iterador al final del nuevo rango de elementos únicos. El tamaño del contenedor no cambia; los elementos al final quedan indefinidos.

std::vector<int> v = {1, 2, 2, 3, 3, 3, 4, 2};
std::sort(v.begin(), v.end()); // v es {1, 2, 2, 3, 3, 3, 4, 2} -> {1, 2, 2, 3, 3, 3, 4} si no se ordena primero
// Después de ordenar: {1, 2, 2, 3, 3, 3, 4}
auto last = std::unique(v.begin(), v.end());
// v ahora es {1, 2, 3, 4, ?, ?, ?, ?} donde '?' son los elementos restantes. 'last' apunta al primer '?'
v.erase(last, v.end()); // Elimina los elementos redundantes al final
// v es {1, 2, 3, 4}

Requiere que el rango esté ordenado para eliminar todas las duplicaciones. La complejidad es O(N).

Funciones Matemáticas

Incluyen operaciones como abs, sqrt, pow, ceil, floor, log, etc. Es importante tener cuidado con la precisión de punto flotante y considerar alternativas enteras o algoritmos específicos (como la búsqueda binaria para raíces cuadradas o exponenciación rápida para potencias) cuando la precisión es crítica.

std::gcd y std::lcm

(C++17) Calculan el máximo común divisor y el mínimo común múltiplo, respectivamente.

int common_divisor = std::gcd(12, 18); // 6
int common_multiple = std::lcm(12, 18); // 36

Para versiones anteriores de C++ o compiladores específicos (como g++), se puede usar __gcd.