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

CKTIS / C++

std::map — un mapa ordenado de claves únicas

std::map almacena pares clave-valor según el orden del comparador y admite como máximo un elemento por cada clave equivalente. Aprende búsquedas que no modifican el mapa, inserción, borrado y transferencia de nodos, y por qué operator[] no sirve para comprobar si una clave existe.

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

Sintaxis

#include <map>
std::map<Key, T> m;
std::map<Key, T, Compare> ordered;

std::map<Key, T, Compare> de <map> almacena elementos std::pair<const Key, T> en el orden del comparador; de forma predeterminada usa std::less<Key>. Compare debe definir un orden débil estricto. Las claves son equivalentes si !comp(a, b) && !comp(b, a), no necesariamente si a == b. El mapa admite una sola clave de ese tipo; un iterador permite modificar el valor, pero no la clave.

Para seleccionar la sobrecarga de std::map::insert que inserta un solo elemento, construye explícitamente un elemento del tipo value_type del mapa: m.insert(value_type{key, value}). Esta sobrecarga devuelve un par iterador-bool: si ya existe una clave equivalente, el bool es false y el valor almacenado no se sobrescribe. Si tanto key como value pueden convertirse implícitamente a value_type, m.insert({key, value}) puede seleccionar en su lugar la sobrecarga que recibe un std::initializer_list<value_type>, devuelve void e intenta insertar dos elementos. En el ejemplo con std::map<int, int>, la llamada con llaves selecciona la sobrecarga de un solo elemento. std::map::find devuelve un iterador o std::map::end; end() señala la posición posterior al último elemento y no debe desreferenciarse. std::map::contains devuelve bool, mientras que std::map::count devuelve 0 o 1. std::map::equal_range devuelve un rango semiabierto [first, last) con cero o un elemento. Estas búsquedas no insertan elementos y cuestan O(log n).

std::map::operator[] devuelve una referencia al valor; si falta la clave, inserta un elemento nuevo con esa clave. Con el asignador predeterminado, el valor asociado se inicializa por valor (por ejemplo, a 0 para int), lo que requiere que T sea construible por defecto. Un asignador personalizado puede cambiar la forma en que se construye el elemento. No uses [] solo para comprobar la presencia. std::map::erase(key) devuelve el número de elementos eliminados; erase(it) devuelve el iterador siguiente y requiere un iterador desreferenciable. std::map::size devuelve el número de elementos en O(1). La inserción normal y el borrado por clave cuestan O(log n); el borrado mediante iterador es O(1) amortizado. Insertar no invalida iteradores ni referencias; borrar solo invalida los que apuntan a elementos eliminados.

std::map::extract separa un nodo sin copiar ni mover su elemento; si la clave no existe, devuelve un handle vacío. Comprueba empty() antes de key(); la clave separada puede cambiarse antes de volver a insertar el nodo. std::map::merge transfiere nodos de tipos compatibles sin copiar ni mover elementos; las claves en conflicto permanecen en el origen. La transferencia de nodos requiere asignadores iguales. El ejemplo usa operaciones disponibles en C++23; el documento enlazado es un borrador en evolución, no la norma definitiva de C++23. La opción del compilador del repositorio no certifica el entorno de producción.

Ejemplos

#include <iostream>
#include <map>
#include <utility>

int main() {
    std::map<int, int> m{{2, 20}};
    auto result = m.insert({2, 99});
    std::cout << std::boolalpha << "inserted=" << result.second << '\n';
    m[1] += 10;
    if (auto it = m.find(2); it != m.end()) {
        std::cout << "found=" << it->second << '\n';
    }
    auto [first, last] = m.equal_range(2);
    std::cout << "contains=" << m.contains(2)
              << " count=" << m.count(2)
              << " range=" << (first != last) << '\n';

    auto node = m.extract(1);
    if (!node.empty()) {
        node.key() = 3;
        m.insert(std::move(node));
    }
    std::map<int, int> source{{2, 200}, {4, 40}};
    m.merge(source);
    std::cout << "erased=" << m.erase(2)
              << " size=" << m.size()
              << " source=" << source.size() << '\n';
    for (const auto& [key, value] : m) {
        std::cout << key << ':' << value << '\n';
    }
}

Resultado

inserted=false
found=20
contains=true count=1 range=true
erased=1 size=2 source=1
3:10
4:40

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