Programare Competitivă

map și unordered_map din STL

Un map este un dicționar: asociază chei cu valori. Fiecare cheie e unică și are exact o valoare asociată. Cheile sunt mereu sortate.

#include <map>

map<K, V>

map<string, int> varsta;

varsta["Ana"] = 15;
varsta["Mihai"] = 16;
varsta["Elena"] = 14;

cout << varsta["Ana"];    // 15
cout << varsta["Mihai"];  // 16
cout << varsta.size();    // 3

Operații

Operație Ce face Complexitate
m[key] = val Inserează sau actualizează O(log n)
m[key] Acces valoare (creează dacă nu există!) O(log n)
m.count(key) 1 dacă există, 0 dacă nu O(log n)
m.find(key) Iterator la pereche (sau end()) O(log n)
m.erase(key) Șterge perechea O(log n)
m.size() Număr perechi O(1)
m.empty() Verifică gol O(1)

Iterare prin map

Elementele sunt sortate după cheie:

map<string, int> m;
m["banana"] = 3;
m["mar"] = 7;
m["apa"] = 1;

for (auto &p : m)
    cout << p.first << " = " << p.second << endl;
Output:
apa = 1
banana = 3
mar = 7

p.first = cheia, p.second = valoarea.

Frecvența cuvintelor

#include <fstream>
#include <map>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    char s[1001];
    fin.getline(s, 1001);

    map<string, int> fr;
    char *p = strtok(s, " ");

    while (p != NULL) {
        fr[p]++;
        p = strtok(NULL, " ");
    }

    for (auto &pereche : fr)
        fout << pereche.first << ": " << pereche.second << endl;

    return 0;
}

date.in:

ana are ana mere ana

date.out:

ana: 3
are: 1
mere: 1

fr[p]++ funcționează pentru că m[key] creează automat intrarea cu valoarea 0 dacă nu există, apoi o incrementează.

Verificare existență

map<string, int> m;
m["test"] = 5;

// Varianta 1: count
if (m.count("test"))
    cout << "Exista";

// Varianta 2: find
auto it = m.find("test");
if (it != m.end())
    cout << it->second;  // 5

// ATENȚIE: m["inexistent"] CREEAZĂ intrarea cu valoarea 0!
cout << m["inexistent"]; // 0, dar acum "inexistent" există în map!

Nu folosi m[key] pentru verificare! Dacă cheia nu există, o creează automat cu valoare 0. Folosește m.count(key) sau m.find(key).

map cu chei numerice

Funcționează ca un vector de frecvență dar pentru valori oricât de mari:

map<int, int> fr;

fr[1000000000]++;   // funcționează! Nu ai nevoie de vector de 10^9
fr[999999999]++;
fr[1000000000]++;

cout << fr[1000000000]; // 2

Când map vs vector de frecvență?

Vector de frecvență map<int, int>
Valori 0 - 10^6 Da (6 MB) Da
Valori 0 - 10^9 Nu (prea mare) Da
Valori negative Nu Da
Complexitate acces O(1) O(log n)
Memorie Fixă (chiar dacă puține valori) Proporțională cu nr. de valori distincte

unordered_map<K, V>

Varianta neordonată - nu sortează cheile, dar operațiile sunt O(1) în medie (în loc de O(log n)).

#include <unordered_map>

unordered_map<string, int> m;
m["test"] = 5;
cout << m["test"]; // 5 - aceleași operații, dar mai rapid

Comparație

map unordered_map
Ordine Sortată după cheie Fără ordine
Insert/Find O(log n) O(1) mediu
Iterare În ordine Ordine aleatorie
Include <map> <unordered_map>
Cel mai rău caz O(log n) O(n) (coliziuni)

Folosește map când ai nevoie de ordine sau lower_bound/upper_bound. Folosește unordered_map când vrei viteză pură.

Exemplu: prima apariție a fiecărui element

#include <fstream>
#include <map>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n;
    fin >> n;

    map<int, int> prima; // valoare -> prima poziție

    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        if (prima.count(x) == 0)
            prima[x] = i;
    }

    for (auto &p : prima)
        fout << p.first << " apare prima data la pozitia " << p.second << endl;

    return 0;
}

map cu lower_bound / upper_bound

La fel ca la set:

map<int, string> m;
m[10] = "zece";
m[20] = "douazeci";
m[30] = "treizeci";

auto it = m.lower_bound(15); // primul cu cheia >= 15
cout << it->first << " " << it->second; // 20 douazeci

Greșeli frecvente

1. m[key] creează intrarea

map<int, int> m;
cout << m[5]; // 0, DAR acum m conține {5: 0}!
cout << m.size(); // 1, nu 0!

Folosește count sau find pentru verificare.

2. Iterare cu modificare

La fel ca la set, nu modifica map-ul în timp ce iterezi cu iteratori.

3. Confuzia map cu set

  • set<int>: mulțime de valori
  • map<int, int>: perechi cheie-valoare

set stochează valori, map stochează perechi.

Ce să reții

  • map<K, V>: dicționar sortat, cheie-valoare, O(log n) per operație.
  • m[key] accesează SAU creează. m.count(key) verifică fără a crea.
  • unordered_map: nesortată, O(1) mediu, mai rapidă dar fără ordine.
  • Ideal pentru: frecvențe cu valori mari, asocieri cheie-valoare, înlocuire vector de frecvență.
  • Iterarea prin map e în ordinea crescătoare a cheilor.
  • lower_bound/upper_bound funcționează ca la set.
Cuprins Inapoi Inainte