Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::map — um mapa ordenado de chaves únicas

std::map guarda pares chave-valor pela ordem do comparador e admite, no máximo, um elemento por cada chave equivalente. Aprende a fazer pesquisas sem alterar o mapa, inserir, apagar e transferir nós, e percebe porque é que operator[] não verifica a presença de uma chave.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

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

std::map<Key, T, Compare> de <map> guarda elementos std::pair<const Key, T> pela ordem do comparador; por predefinição, usa std::less<Key>. Compare tem de definir uma ordem fraca estrita. As chaves são equivalentes quando !comp(a, b) && !comp(b, a), não necessariamente quando a == b. O mapa admite apenas uma chave deste tipo; um iterador permite alterar o valor, mas não a chave.

Para selecionar a sobrecarga de std::map::insert que insere um único elemento, constrói explicitamente um elemento do tipo value_type do mapa: m.insert(value_type{key, value}). Esta sobrecarga devolve um par iterador-bool: se já existir uma chave equivalente, o bool é false e o valor guardado não é substituído. Se tanto key como value puderem ser convertidos implicitamente para value_type, m.insert({key, value}) pode selecionar a sobrecarga que recebe um std::initializer_list<value_type>, devolve void e tenta inserir dois elementos. No exemplo com std::map<int, int>, a chamada com chavetas seleciona a sobrecarga de um único elemento. std::map::find devolve um iterador ou std::map::end; end() aponta para depois do último elemento e não pode ser desreferenciado. std::map::contains devolve bool, enquanto std::map::count devolve 0 ou 1. std::map::equal_range devolve um intervalo semiaberto [first, last) com zero ou um elemento. Estas pesquisas não inserem elementos e têm custo O(log n).

std::map::operator[] devolve uma referência ao valor; se a chave não existir, insere um novo elemento com essa chave. Com o alocador predefinido, o valor associado é inicializado por valor (a 0 para int, por exemplo), o que exige que T possa ser construído por omissão. Um alocador personalizado pode alterar a forma como o elemento é construído. Não uses [] apenas para verificar a presença. std::map::erase(key) devolve o número de elementos apagados; erase(it) devolve o iterador seguinte e exige um iterador desreferenciável. std::map::size devolve o número de elementos em O(1). A inserção normal e a remoção por chave têm custo O(log n); a remoção por iterador é O(1) amortizado. A inserção não invalida iteradores nem referências; a remoção invalida apenas os relativos aos elementos apagados.

std::map::extract separa um nó sem copiar nem mover o elemento; uma chave inexistente produz um handle vazio. Verifica empty() antes de key(); podes alterar a chave separada antes de voltar a inserir o nó. std::map::merge transfere nós de tipos compatíveis sem copiar nem mover elementos; as chaves em conflito ficam na origem. A transferência de nós exige alocadores iguais. O exemplo usa operações disponíveis em C++23; o documento ligado é um projeto em evolução, não a norma C++23 definitiva. A opção de compilação do repositório não certifica o ambiente de produção.

Exemplos

#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

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes