Adaptadores de Contenedores y Contenedores Especiales

Aprende sobre stack, queue, priority_queue y tipos de vocabulario modernos como span, string_view y optional. Comprende cuando los adaptadores simplifican tu codigo.

Que Son los Adaptadores de Contenedores?

Los adaptadores de contenedores son envoltorios alrededor de contenedores existentes que proporcionan una interfaz restringida. Imponen un patron de acceso especifico ocultando la API completa del contenedor:

- std::stack — LIFO (Ultimo en Entrar, Primero en Salir), respaldado por deque por defecto
- std::queue — FIFO (Primero en Entrar, Primero en Salir), respaldado por deque por defecto
- std::priority_queue — max-heap, respaldado por vector por defecto

Los adaptadores no proporcionan iteradores — solo puedes acceder al elemento superior/frontal. Esta restriccion es intencional: hace que la intencion del codigo sea mas clara y previene el mal uso accidental.

Stack y Queue en Accion

Las pilas y colas son estructuras de datos fundamentales usadas en analisis sintactico, BFS/DFS, sistemas de deshacer y planificacion de tareas.

stack_queue.cpp

#include <stack>
#include <queue>
#include <string>
#include <iostream>

// Check if parentheses are balanced using a stack
bool is_balanced(const std::string& expr) {
    std::stack<char> stk;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stk.empty()) return false;
            char top = stk.top();
            stk.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stk.empty();
}

int main() {
    std::cout << std::boolalpha;
    std::cout << is_balanced("({[]})") << '\n';   // true
    std::cout << is_balanced("({[}])") << '\n';   // false

    // Queue — BFS-style task processing
    std::queue<std::string> tasks;
    tasks.push("compile");
    tasks.push("link");
    tasks.push("run tests");

    while (!tasks.empty()) {
        std::cout << "Processing: " << tasks.front() << '\n';
        tasks.pop();   // removes from front
    }
}

Priority Queue (Heap)

std::priority_queue es un max-heap por defecto — top() devuelve el elemento mas grande. Para un min-heap, usa std::greater como comparador.

priority_queue.cpp

#include <queue>
#include <vector>
#include <functional>
#include <iostream>
#include <string>

struct Task {
    int priority;
    std::string name;
};

int main() {
    // Max-heap (default) — largest first
    std::priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(10);
    max_heap.push(50);
    max_heap.push(20);

    while (!max_heap.empty()) {
        std::cout << max_heap.top() << ' ';  // 50 30 20 10
        max_heap.pop();
    }
    std::cout << '\n';

    // Min-heap — smallest first
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(10);
    min_heap.push(50);
    std::cout << "Min: " << min_heap.top() << '\n';  // 10

    // Custom comparator with lambda
    auto cmp = [](const Task& a, const Task& b) {
        return a.priority < b.priority;  // higher priority first
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_queue(cmp);
    task_queue.push({3, "low priority"});
    task_queue.push({10, "critical"});
    task_queue.push({7, "medium"});

    while (!task_queue.empty()) {
        auto& t = task_queue.top();
        std::cout << "[" << t.priority << "] " << t.name << '\n';
        task_queue.pop();
    }
}

std::span — Vista No Propietaria de Datos Contiguos (C++20)

std::span es una vista ligera y no propietaria sobre una secuencia contigua de elementos. Reemplaza el patron propenso a errores de pasar pares (puntero, tamano).

span_example.cpp

#include <span>
#include <vector>
#include <array>
#include <iostream>
#include <numeric>

// span accepts vector, array, C-array — anything contiguous
void print_stats(std::span<const int> data) {
    if (data.empty()) return;
    std::cout << "Size: " << data.size() << '\n';
    std::cout << "First: " << data.front() << '\n';
    std::cout << "Last:  " << data.back() << '\n';

    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum:   " << sum << '\n';

    // Subviews
    auto first3 = data.first(3);   // first 3 elements
    auto last2  = data.last(2);    // last 2 elements
    auto mid    = data.subspan(1, 3);  // 3 elements starting at index 1
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::array<int, 5> arr = {10, 20, 30, 40, 50};
    int c_arr[] = {100, 200, 300, 400, 500};

    print_stats(vec);     // works with vector
    print_stats(arr);     // works with array
    print_stats(c_arr);   // works with C-array
}

string_view y optional

std::string_view (C++17) es una referencia no propietaria y de solo lectura a un string. Evita el costo de copiar o asignar std::string para funciones que solo necesitan leer:

void greet(std::string_view name) {  // sin copia, sin asignacion
    std::cout << "Hello, " << name << '\n';
}
greet("world");               // funciona con literales de string
greet(std::string{"world"});  // funciona con std::string

std::optional (C++17) representa un valor que puede o no estar presente — un reemplazo con seguridad de tipos para "valores magicos" o punteros crudos para indicar ausencia:

std::optional<int> find_index(std::span<const int> data, int target) {
    for (int i = 0; i < data.size(); ++i)
        if (data[i] == target) return i;
    return std::nullopt;  // no encontrado
}
auto idx = find_index(vec, 42);
if (idx) std::cout << "Found at " << *idx << '\n';
std::cout << idx.value_or(-1) << '\n';  // -1 si esta vacio

Error común

Como std::string_view y std::span son no propietarios, pueden quedar colgantes facilmente si los datos subyacentes son destruidos:

std::string_view bad() {
    std::string temp = "hello";
    return temp;  // COLGANTE — temp se destruye al final del ambito
}

Nunca devuelvas un string_view o span a una variable local. Son seguros para parametros de funciones (los datos del llamador sobreviven a la llamada), pero peligrosos como valores de retorno a menos que puedas garantizar que la fuente sobrevive a la vista.

Lo mismo aplica a std::span — internamente es solo un puntero y un tamano, sin semantica de propiedad.

Buena práctica

Usa adaptadores de contenedores cuando quieras imponer una disciplina sobre como se accede a los elementos:

- Usa std::stack en lugar de un deque o vector crudo cuando solo el acceso LIFO sea significativo. Esto hace la intencion obvia y previene el acceso aleatorio accidental.
- Usa std::queue para procesamiento FIFO (colas de tareas, BFS).
- Usa std::priority_queue para planificacion, algoritmo de Dijkstra, o cualquier escenario donde siempre quieras el elemento extremo.

Si necesitas iteracion, consultas de tamano en puntos arbitrarios o acceso a mitad de secuencia, usa el contenedor subyacente directamente.

Puntos clave

Los adaptadores de contenedores (stack, queue, priority_queue) restringen la interfaz para imponer disciplina de uso
std::priority_queue es un max-heap por defecto — usa std::greater para un min-heap
std::span (C++20) proporciona una vista no propietaria sobre datos contiguos, reemplazando pares (puntero, tamano)
std::string_view (C++17) evita copiar strings para uso de solo lectura — pero cuidado con las referencias colgantes
std::optional (C++17) es la forma con seguridad de tipos de representar "tal vez no hay valor" sin valores centinela magicos
Las vistas no propietarias (span, string_view) nunca deben sobrevivir a los datos que referencian

Quiz — Pon a prueba tus conocimientos

(15 XP)

1. Que adaptador de contenedor proporciona comportamiento FIFO (Primero en Entrar, Primero en Salir)?

2. Que tipo devuelve `std::priority_queue<int>` desde `top()` por defecto?

3. Por que es peligroso devolver un `std::string_view` a un `std::string` local?

Contenedores Asociativos: map, set, unordered_map

Iteradores: El Pegamento de la STL