map — dicționar ordonat cheie-valoare

Ce este un map și de ce îl folosești

Un map este un dicționar cheie → valoare. Fiecare cheie e unică (nu poți avea două intrări cu aceeași cheie) și cheile sunt ținute ordonate crescător, pentru că map e construit pe un arbore binar echilibrat.

De ce contează asta în concursuri? Pentru că un vector de frecvență obișnuit (frec[x]++) funcționează doar când x e un întreg mic, pe care îl poți folosi ca indice. Dar dacă vrei să numeri cuvinte, numere uriașe (până la 10^18) sau perechi, nu ai cum să declari un vector atât de mare. map rezolvă exact asta: cheia poate fi orice tip comparabil, iar fiecare operație costă O(log n).

Pe scurt, alegi map când:

• ai chei care nu sunt indici mici (string-uri, numere mari, perechi);
• vrei rezultatul parcurs sortat după cheie, fără efort suplimentar.

Exemplu pas cu pas: frecvența cuvintelor

Vrem să numărăm de câte ori apare fiecare cuvânt în „mar pere mar mar pere”. Folosim un map<string, int> și incrementăm cu m[cuvant]++:

• citim „mar” → m["mar"] nu există, devine 0, apoi ++ → mar: 1
• citim „pere” → devine 0, apoi ++ → mar: 1, pere: 1
• citim „mar” → există, ++ → mar: 2, pere: 1
• citim „mar” → ++ → mar: 3, pere: 1
• citim „pere” → ++ → mar: 3, pere: 2

Truc-ul m[cuvant]++ merge tocmai datorită efectului secundar al lui []: la prima întâlnire cheia e creată cu 0, apoi incrementată la 1. La numărare e exact ce vrei — dar reține că acest efect te poate încurca dacă doar citești.

Implementare C++

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> frec;

    // numaram cuvintele citite
    string cuvant;
    while (cin >> cuvant) {
        frec[cuvant]++;            // creeaza cheia la 0 daca lipseste, apoi ++
    }

    // verificare PURA: nu cream cheia daca nu exista
    if (frec.count("mar")) {
        cout << "mar apare de " << frec["mar"] << " ori\n";
    }

    // find ne da un iterator catre pereche (sau end() daca lipseste)
    auto it = frec.find("kiwi");
    if (it == frec.end()) {
        cout << "kiwi nu exista\n";
    }

    // parcurgere SORTATA dupa cheie, cu iterator clasic
    for (auto it = frec.begin(); it != frec.end(); it++) {
        cout << it->first << " -> " << it->second << "\n";
        // it->first  = cheia, it->second = valoarea
    }

    // varianta moderna, mai citibila (structured bindings)
    for (auto& [k, v] : frec) {
        cout << k << " : " << v << "\n";
    }
    return 0;
}

Pentru intrarea „mar pere mar mar pere”, parcurgerea afișează cheile ordonate: mar -> 3 apoi pere -> 2.

Complexitate

Toate operațiile trec prin arbore, deci sunt logaritmice — nu O(1) ca la vector:

Vizualizare

Urmărește cum o cheie nouă se așază la locul ei în arbore, păstrând totul ordonat:

Recapitulare

• map e dicționar cheie unică → valoare, ținut ordonat după cheie, cu operații O(log n).
• m[cheie] creează cheia cu valoare implicită la citire — pentru verificare pură folosește count sau find.
• Parcurgi sortat cu it->first / it->second sau cu for (auto& [k, v] : m); alege unordered_map când ordinea nu contează.