Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C++

std::unordered_map — mapa hash con claves únicas

std::unordered_map almacena pares clave-valor sin garantizar un orden. Aprende a buscar sin insertar, descubre la diferencia entre operator[] y at, y cómo la gestión de los buckets afecta a la validez de los iteradores.

Versión: C++23; repository compiler flag, production runtime not attested

Sintaxis

#include <unordered_map>
std::unordered_map<Key, T> map;

std::unordered_map<Key, T> de <unordered_map> almacena como máximo un valor por cada clave equivalente. El orden de iteración no está especificado. La búsqueda y la inserción tienen un coste medio de O(1) y de O(n) en el peor caso. Las claves equivalentes deben tener el mismo hash; que los hashes coincidan no implica que las claves sean equivalentes.

find(key) no inserta: devuelve un iterador o end(), el iterador situado después del último elemento, que no se debe desreferenciar. operator[] devuelve una referencia al valor e inserta una clave que no existe; con el asignador predeterminado, el nuevo valor se inicializa por valor, así que para int es 0. at(key) no inserta y lanza std::out_of_range si falta la clave. emplace(...) devuelve un par con un iterador y una marca de inserción; un duplicado no sobrescribe el valor.

size() indica el número de elementos, bucket_count() el número de buckets y load_factor() el promedio de elementos por bucket. max_load_factor() consulta el umbral de carga; max_load_factor(z) requiere que z sea positivo. Establece el umbral antes de reserve(n), que reserva espacio para n elementos en total, no para n elementos adicionales. Equivale a rehash(ceil(n / max_load_factor())). rehash(n) garantiza al menos n buckets y suficientes para los elementos actuales y el umbral; la cantidad exacta depende de la implementación.

El rehashing invalida los iteradores, pero no los punteros ni las referencias a los elementos. Una inserción, también mediante operator[], puede provocarlo. clear() elimina todos los elementos, hace que size() sea 0 e invalida las referencias a los elementos eliminados; no lo consideres una garantía de que se libere toda la memoria del contenedor.

Ámbito de esta entrada: C++23. Una opción del compilador en el repositorio no certifica el entorno de ejecución de producción. El texto fuente es un borrador en evolución, no un texto C++23 definitivo; esta entrada no depende de las extensiones más recientes que aparecen allí.

Identificadores de referencia incluidos en esta entrada: std::unordered_map::find, std::unordered_map::end, std::unordered_map::clear, std::unordered_map::operator[], std::unordered_map::max_load_factor, std::unordered_map::reserve, std::unordered_map::rehash, std::unordered_map::size, std::unordered_map::load_factor, std::unordered_map::bucket_count, std::unordered_map::at, std::unordered_map::emplace.

Ejemplos

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    counts.max_load_factor(0.75f);
    counts.reserve(8);

    counts.emplace("apple", 2);
    ++counts["apple"];
    ++counts["pear"];
    const bool inserted = counts.emplace("apple", 99).second;

    if (auto it = counts.find("apple"); it != counts.end()) {
        std::cout << "apple=" << it->second << '\n';
    }
    std::cout << std::boolalpha << "duplicate inserted=" << inserted << '\n';
    std::cout << "pear=" << counts.at("pear") << '\n';
    std::cout << "size=" << counts.size() << '\n';

    counts.rehash(32);
    std::cout << "buckets>=32=" << (counts.bucket_count() >= 32) << '\n';
    std::cout << "load within limit="
              << (counts.load_factor() <= counts.max_load_factor()) << '\n';

    counts.clear();
    std::cout << "size after clear=" << counts.size() << '\n';
}

Resultado

apple=3
duplicate inserted=false
pear=1
size=2
buckets>=32=true
load within limit=true
size after clear=0

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes