De ce contează?
Imaginează-ți agenda din telefon: la fiecare nume ai un singur număr. Cauți
„Maria" și obții instant numărul ei; nu te interesează al câtelea contact a fost
salvat. Un nume nu apare de două ori, iar lista e afișată alfabetic. Exact asta
îți oferă un map: o cheie unică (numele) îți dă o valoare (numărul), iar cheile
stau mereu ordonate.
Ce este
Un map este un dicționar cheie → valoare: fiecărei chei îi corespunde
exact o valoare. Cheile sunt unice (nu poți avea două intrări cu aceeași
cheie) și sunt ținute mereu sortate crescător.
Te bazezi pe el când vrei să asociezi o informație de o alta: nume → telefon,
cuvânt → de câte ori apare, cod produs → preț. Operațiile de bază — inserare,
căutare, ștergere și accesul m[cheie] — costă O(log n), pentru că în spate
map este un arbore binar echilibrat. Tocmai de aceea poate parcurge cheile în
ordine fără să-ți coste nimic în plus.
Atenție la o subtilitate care prinde pe toată lumea: m[cheie] creează cheia
cu valoarea implicită (0 pentru int) dacă ea nu există încă. Deci simpla scriere
m[cheie] poate mări map-ul fără să vrei. Ca să verifici dacă o cheie există
fără s-o creezi, folosești m.count(cheie) sau m.find(cheie).