Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::map — una mappa ordinata con chiavi univoche

std::map memorizza coppie chiave-valore nell’ordine del comparatore e ammette al massimo un elemento per ogni chiave equivalente. Scopri la ricerca senza modifiche, l’inserimento, la cancellazione e il trasferimento dei nodi, e perché operator[] non verifica la presenza di una chiave.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

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

std::map<Key, T, Compare> di <map> memorizza elementi std::pair<const Key, T> nell’ordine del comparatore; per impostazione predefinita usa std::less<Key>. Compare deve definire un ordinamento stretto debole. Le chiavi sono equivalenti se !comp(a, b) && !comp(b, a), non necessariamente se a == b. La mappa ammette una sola chiave di questo tipo; un iteratore consente di modificare il valore, ma non la chiave.

Per selezionare l’overload di std::map::insert che inserisce un solo elemento, costruisci esplicitamente un elemento del tipo value_type della mappa: m.insert(value_type{key, value}). Questo overload restituisce una coppia iteratore-bool: se esiste già una chiave equivalente, il bool vale false e il valore memorizzato non viene sovrascritto. Se key e value sono entrambi convertibili implicitamente in value_type, m.insert({key, value}) può invece selezionare l’overload che accetta uno std::initializer_list<value_type>, restituisce void e tenta di inserire due elementi. Nell’esempio con std::map<int, int>, la chiamata con le parentesi graffe seleziona l’overload per un solo elemento. std::map::find restituisce un iteratore oppure std::map::end; end() indica la posizione dopo l’ultimo elemento e non va dereferenziato. std::map::contains restituisce bool, mentre std::map::count restituisce 0 o 1. std::map::equal_range restituisce un intervallo semiaperto [first, last) con zero o un elemento. Queste ricerche non inseriscono elementi e hanno costo O(log n).

std::map::operator[] restituisce un riferimento al valore; se la chiave manca, inserisce un nuovo elemento con quella chiave. Con l’allocatore predefinito, il valore associato viene inizializzato per valore (a 0 per int, ad esempio), il che richiede che T sia costruibile per default. Un allocatore personalizzato può cambiare il modo in cui viene costruito l’elemento. Non usare [] solo per verificare la presenza. std::map::erase(key) restituisce il numero di elementi rimossi; erase(it) restituisce l’iteratore successivo e richiede un iteratore dereferenziabile. std::map::size restituisce il numero di elementi in O(1). L’inserimento normale e la cancellazione per chiave costano O(log n); la cancellazione tramite iteratore è O(1) ammortizzato. L’inserimento non invalida iteratori o riferimenti; la cancellazione invalida solo quelli agli elementi rimossi.

std::map::extract stacca un nodo senza copiare o spostarne l’elemento; una chiave assente produce un handle vuoto. Controlla empty() prima di key(); la chiave staccata si può modificare prima di reinserire il nodo. std::map::merge trasferisce nodi di tipi compatibili senza copiare o spostare gli elementi; le chiavi in conflitto restano nella sorgente. Il trasferimento dei nodi richiede allocatori uguali. L’esempio usa operazioni disponibili in C++23; il documento collegato è una bozza in evoluzione, non la norma C++23 definitiva. Il flag del compilatore del repository non certifica l’ambiente di produzione.

Esempi

#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';
    }
}

Risultato

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

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti