std::map y std::set: El orden garantizado mediante árboles

std::map y std::set son contenedores asociativos que almacenan elementos de forma estrictamente ordenada basándose en sus claves. Mientras que std::unordered_map utiliza una tabla de hash para ofrecer $O(1)$ en promedio, estos contenedores implementan estructuras de árboles de búsqueda binaria auto-equilibrados (específicamente árboles rojo-negro). Esto significa que la complejidad para la búsqueda, inserción y borrado es siempre $O(\log n)$, garantizando un rendimiento predecible incluso en el peor de los casos.

Debes recurrir a ellos cuando la semántica de ordenación sea una parte integral de tu lógica de negocio —por ejemplo, si necesitas iterar sobre elementos en un orden específico o realizar búsquedas de rangos— o cuando necesites asegurar que no haya duplicados de forma eficiente. Sin embargo, ten cuidado: el uso de operator[] en un std::map no es una operación de solo lectura; si la clave no existe, el contenedor insertará un elemento nuevo con un valor inicializado por defecto (zero-initialized), lo que puede causar fugas de memoria lógicas o estados inconsistentes. Si necesitas consultar un elemento en un contexto const o sin riesgo de inserción accidental, la opción correcta es find() o at().

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <stdexcept>

// Estructura para demostrar un comparador personalizado
struct Sensor {
    int id;
    std::string modelo;

    // Para usar un objeto como clave en std::set o std::map, 
    // necesitamos definir el operador de ordenación (strict weak ordering).
    bool operator<(const Sensor& other) const {
        return id < other.id;
    }
};

int main() {
    // std::set: Almacena sensores únicos y los mantiene ordenados por su ID.
    std::set<Sensor> sensores_activos;

    // std::map: Mapea el ID del sensor a su estado (string para el ejemplo).
    std::map<int, std::string> registro_estados;

    // std::multimap: Permite múltiples valores para la misma clave.
    // Útil para logs donde varios eventos ocurren con el mismo timestamp (clave).
    std::multimap<int, std::string> logs_sistema;

    // 1. Inserción eficiente con emplace
    // emplace construye el objeto directamente en el nodo del árbol, evitando copias.
    sensores_activos.emplace(101, "Termómetro");
    sensores_activos.emplace(305, "Presión");
    sensores_activos.emplace(202, "Humedad");

    registro_estados.emplace(101, "Operativo");
    registro_estados.emplace(305, "Alerta");
    registro_estados.emplace(202, "Mantenimiento");

    // Logs con claves duplicadas (timestamp 1000)
    logs_sistema.emplace(1000, "Sistema iniciado");
    logs_sistema.emplace(1000, "Conexión establecida");
    logs_sistema.emplace(1005, "Sensor 101 reportando...");

    // 2. Búsqueda segura
    int id_buscado = 305;
    auto it = registro_estados.find(id_buscado);
    if (it != registro_estados.end()) {
        // it->first es la clave (const), it->second es el valor
        std::cout << "Estado del sensor " << id_buscado << ": " << it->second << "\n";
    }

    // 3. Búsquedas de rango con lower_bound y upper_bound
    // Buscamos el primer sensor con ID >= 200
    auto lb = sensores_activos.lower_bound({200, ""});
    if (lb != sensores_activos.end()) {
        std::cout << "Primer sensor desde ID 200: " << lb->modelo << " (ID: " << lb->id << ")\n";
    }

    // 4. Manejo de duplicados en multimap usando equal_range
    std::cout << "Logs para el timestamp 1000:\n";
    auto range = logs_sistema.equal_range(1000);
    for (auto i = range.first; i != range.second; ++i) {
        std::cout << "  - " << i->second << "\n";
    }

    // 5. El peligro de operator[] y la seguridad de at()
    try {
        // at() lanza std::out_of_range si la clave no existe. Es seguro para const.
        std::cout << "Estado de sensor 999: " << registro_estados.at(999) << "\n";
    } catch (const std::out_of_range& e) {
        std::cerr << "Error controlado con at(): " << e.what() << "\n";
    }

    // Cuidado: esto inserta el ID 500 con un string vacío ("") en el mapa
    std::cout << "Valor de sensor 500 (inserción accidental): '" << registro_estados[500] << "'\n";

    return 0;
}

Como puedes ver en el ejemplo, std::map almacena sus elementos como pares std::pair<const Key, Value>. Es crucial notar que la clave es const; si pudieras modificar la clave directamente dentro del árbol, romperías la propiedad de ordenación y el árbol quedaría corrupto, haciendo que las búsquedas fallaran. Por eso, para cambiar una clave, debes eliminar el elemento antiguo e insertar uno nuevo.

Cuando utilizas emplace, el compilador intenta construir el objeto directamente en el espacio de memoria ya reservado para el nodo del árbol, minimando el uso de constructores de copia o movimiento. En el caso de std::multimap, la función equal_range es especialmente potente: devuelve un std::pair de iteradores que definen el rango de elementos que comparten la misma clave, lo cual es mucho más eficiente que iterar manualmente y comparar claves.

Por último, recuerda la diferencia semántica entre find() y operator[]. Mientras que find() te devuelve un iterador al end() si la clave no existe, operator[] tiene un efecto secundario: la inserción. En sistemas de alta disponibilidad o de alta carga, estas inserciones accidentales pueden inflar el consumo de memoria de forma silenciosa y difícil de rastrear.

El error frecuente

Un error clásico ocurre al intentar usar std::map dentro de funciones que reciben el contenedor por referencia constante (const std::map<K, V>&).

void check_status(const std::map<int, std::string>& status_map, int id) {
    // ERROR DE COMPILACIÓN: operator[] no es una función const
    // porque puede insertar elementos.
    if (status_map[id] == "Error") { 
        // ...
    }

    // FORMA CORRECTA:
    auto it = status_map.find(id);
    if (it != status_map.end() && it->second == "Error") {
        // ...
    }
}

Este error es sutil porque, en el código que no es const, status_map[id] parece inofensivo, pero en un entorno de producción donde los mapas son grandes o se comparten entre hilos, ese “pequeño” efecto secundario de inserción puede invalidar iteradores en otros hilos o causar un crecimiento descontrolado de la memoria. Si el código no compila con std::out_of_range (usando at()), el error suele ser una inserción silenciosa que se manifiesta mucho después como un bug de lógica.

N° 85