set, map și unordered_map: dicționare și hash

std::set păstrează valori distincte, iar std::map asociază fiecărei chei o valoare. Variantele ordonate permit parcurgerea după cheie. std::unordered_map folosește hashing pentru acces mediu rapid, fără să promită o ordine de parcurgere.

Aceste containere sunt utile când valorile nu se potrivesc într-un vector de frecvență mic. Pentru chei precum un miliard sau numere negative, alocarea unei celule pentru fiecare valoare posibilă ar fi costisitoare sau nepractică.

Cum funcționează

Un set răspunde dacă o valoare este prezentă și o păstrează o singură dată. Inserarea aceleiași valori din nou nu îi mărește dimensiunea. Pentru a păstra multiplicitatea există multiset sau un map de frecvențe, în funcție de operațiile cerute. Într-un map<int,int>, cheia poate fi valoarea citită, iar valoarea asociată numărul aparițiilor.

Expresia ++frequency[x] funcționează deoarece operator[] creează cheia absentă cu o valoare int inițializată la zero. Această proprietate este utilă la numărare, dar poate produce inserări nedorite când vrei doar să verifici existența. Pentru citire fără modificare folosim find și comparăm iteratorul rezultat cu end(). at poate citi o cheie existentă, dar aruncă o excepție dacă aceasta lipsește.

Un tabel hash transformă cheia într-un cod și o distribuie într-un compartiment. Chei diferite pot ajunge în același compartiment; această situație se numește coliziune și trebuie rezolvată prin verificarea egalității, nu prin presupunerea că hash-ul identifică unic cheia. Biblioteca se ocupă de organizare, dar distribuția slabă sau intrările nefavorabile pot afecta timpul.

Programul citește 0 <= n <= 100000 de întregi și apoi o cheie de căutat. Construiește trei containere pentru a compara rolurile lor. Într-o soluție finală ai păstra numai structurile necesare. Afișarea ordonată folosește map, iar interogarea finală folosește unordered_map fără inserare. Aici containerul asociativ este chiar structura studiată, nu o înlocuire de sintaxă a unui algoritm pe tablou cu indici consecutivi.

Exemplu urmărit pas cu pas

Pentru valorile 7,-2,7,1000000000,-2, set conține trei chei. map le parcurge în ordinea -2,7,1000000000 și asociază frecvențele 2,2,1.

Căutarea cheii 8 în tabelul hash întoarce end(), iar programul afișează zero fără să creeze cheia. Dacă am folosi hashFrequency[8], am modifica structura prin adăugarea unei frecvențe zero. Rezultatul numeric ar coincide, dar dimensiunea și memoria ar putea fi diferite după multe interogări absente.

Implementare C++17

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
int main() {
    int n;
    std::cin >> n;
    std::map<int, int> frequency;
    std::set<int> distinct;
    std::unordered_map<int, int> hashFrequency;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        ++frequency[x];
        distinct.insert(x);
        ++hashFrequency[x];
    }
    std::cout << distinct.size() << '\n';
    for (const auto &entry : frequency)
        std::cout << entry.first << ':' << entry.second << '\n';
    int query;
    std::cin >> query;
    auto it = hashFrequency.find(query);
    std::cout << (it == hashFrequency.end() ? 0 : it->second) << '\n';
}

De ce funcționează și cât costă

La fiecare citire, frecvența cheii curente crește exact o dată, iar celelalte rămân neschimbate. Setul conține exact cheile întâlnite. Map și unordered_map reprezintă aceeași asociere logică, deși ordinea și organizarea internă diferă.

Operațiile de căutare și inserare în set/map au cost logaritmic în numărul cheilor. În unordered_map sunt în medie constante, dar pot fi liniare în cel mai rău caz. Memoria este proporțională cu numărul cheilor distincte, cu un cost administrativ mai mare decât al unui tablou compact.

Greșeli frecvente

Nu presupune că unordered_map afișează crescător sau păstrează ordinea inserării. Nu modifica un container în timpul parcurgerii fără să verifici regulile de invalidare. Nu confunda o cheie absentă cu o cheie prezentă având valoarea zero.

Exersează

Vrei să afișezi frecvențele crescător după valoare. Este suficientă parcurgerea unui unordered_map?

Rezolvare explicată: Nu, ordinea sa nu este garantată. Folosește map sau extrage și sortează cheile înainte de afișare. Alegerea trebuie să țină cont de toate operațiile cerute.

Continuă să înveți

Vectori de frecvență, complexitate și STL și iteratori.

Întrebări frecvente

Când aleg vector de frecvență și când map?

Vectorul este potrivit pentru un domeniu numeric mic și dens. Map este util pentru chei rare, mari sau pentru parcurgere ordonată, acceptând un cost logaritmic.

set păstrează dublurile?

Nu. Fiecare cheie apare o singură dată. Pentru multiplicitate folosește multiset sau un dicționar de frecvențe.

unordered_map garantează O(1)?

Garantează comportamentul mediu specific operațiilor hash, nu un timp constant pentru orice intrare. Coliziunile pot produce operații liniare în cazul nefavorabil.

Ce este o coliziune hash?

Două chei distincte sunt distribuite în aceeași zonă a tabelului. Ele trebuie diferențiate prin egalitatea cheilor, nu prin codul hash singur.

De ce folosesc find la o interogare?

find verifică prezența fără să insereze cheia absentă. operator[] poate modifica dicționarul chiar dacă pare folosit doar pentru citire.